[科普中国]-组合优化算法

组合优化（或称为离散优化）是一门古老而又年轻的学科，著名数学家Fermat，Euler等都为其形成和发展作出过重要贡献二十世纪后半叶。伴随着工业科技革命和现代管理科学的发展，特别是计算机技术的突飞猛进和在各行业的广泛应用，组合优化已壮大成为运筹学的一个独立分支。一些数百年前数学家们偶然想到的问题和方法，已在网络通信、物流管理、交通规划等行业发挥了重要的作用，这是他们当时所不曾想到的。这从另一方面寓示了这学科的巨大前景。

组合（最）优化问题是最优化问题的一类。最优化问题似乎自然地分成两类：一类是连续变量的问题，另一类是离散变量的问题。具有离散变量的问题，我们称它为组合的。在连续变量的问题里，一般地是求一组实数，或者一个函数；在组合问题里，是从一个无限集或者可数无限集里寻找一个对象——典型地是一个整数，一个集合，一个排列，或者一个图。一般地，这两类问题有相当不同的特色，并且求解它们的方法也是很不同的。对于具有离散变量的问题，从有限个解中寻找最优解的问题就是组合最优化问题。

设F是有限集，c是F到R(实数集)的映射，即C是定义在F上的一个函数。求f∈F，使得对于任意的y∈F，有

成立。上述问题我们简记为：求

一个组合最优化问题可用二元组(F，c)表示，其中F表示可行解区域，F中的任何一个元素称为该问题的可行解，c表示目标函数。满足 的可行解，f*称为该问题的最优解。

组合优化算法(optimal combination algorithm)一类在离散状态下求极值的问题。把某种离散对象按某个确定的约束条件进行安排，当已知合乎这种约束条件的特定安排存在时，寻求这种特定安排在某个优化准则下的极大解或极小解的间题。组合最优化的理论基础含线性规划、非线性规划、整数规划、动态规划、拟阵论和网络分析等。组合最优化技术提供了一个快速寻求极大解或极小解的方法1。

组合最优化的特点是可行解集合为有限点集。只要将有限个点逐一比较目标值的大小，该问题最优解就一定可以得到。但是枚举是以时间为代价的，有的枚举时间还可以接受，有的则不能接受。设问题的规模为n，如果存在一个多项式p(n)，使得算法最多执行p(n)个基本步骤便可得到解答，则这种算法称为多项式时间算法。

多少年来，人们试图寻找解答各种组合问题的多项式时闻算法，这种研究工作在一些问题上已取得成功，其中包括最短路问题、最小支撑树问题、网络最大流问题、最小费用流以及运输问题等等。本文研究的无容量限制的带固定费用的最小费用流问题及带费用约束的紧急运输问题也都找到了多项式时间算法。

随着实践的发展，出现了越来越多的组合优化问题都很难找到求最优解的多项式时间算法。经过几代数学家的努力，他们研究整理了一类难以求解的组合优化问题，迄今为止还没有一个能我到最优解的多项式时间算法。例如，最大团问题，TSP问题，点覆盖问题，3-SAP问题等等都属于这一类问题。

这一类组合优化问题归为所谓的NP-hard问题。受人类认识能力的限制，目前人们只能假设这一类难解的组合优化问题不存在求最优解的多项式时间算法。正因为一些组合优化问题还没有找到求最优解的多项式时间算法，而这些组合优化问题又有非常强的实际应用背景，人们不得不尝试着为这些问题设计近似算法(Approximate Algorithm)、启发式算法(Heuristic Algorithm)、或者遗传算法(Genetic Algorithm)等。

我们将寻找能在较短时间（多项式时间）内得到接近予最优解的算法，称之为近似算法(approximation
　　algorithm)。衡量近似算法的优劣可从两个方面来看，一是算法的时间复杂性，二是它得到的解值与最优解值的接近程度。

近似算法能够保证计算结果与最优结果相比较的差别不超过某一常数α，且α一般较小，但是算法比较复杂，在计算机上编程时比较困难。

启发式算法通常很简单，很容易在计算机上实现，一般情况下也能够保证计算结果同最优结果差别不超过某一常数α，但是相对于近似算法要大。也有一些启发式算法无法保证解的近似度，但计算结果通常都比较理想。常见的启发式算法有NF(Next Fit)近似算法，FF(First Fit)近似算法．FFD(First Fit Decreasing)近似算法，BF(best Fit)，BFD(Best Fit Deceasing)近似算法等。

遗传算法简称GA，是一种借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适应的搜索方法，由于遗传算法的寻优过程是从大量的点构成的种群开始平行进行、逐步优化，避免了局部优化结果的产生，并且，遗传算法不要求函数满足可导性质，因此遗传算法常用来解决传统搜索方法解决不了或很难解决的问题，计算结果与最优结果差别一般也很小，但是计算时间相对较长，而且无法从理论上保证计算结果的好坏2。

与其他启发式搜索方法一样，遗传算法在形式上是一种迭代方法，它从一组解（ 群体）出发，模拟生物体的进化机制，采用复制、交叉、变异等遗传操作，在继承原有优良基因的基础上，生成具有更好性能指标的下一代解的群体，不断迭代，直到搜索到最优解或满意解为止。用遗传算法解决组合优化问题的一般方法：

（1）确定群体规模I（整数）及遗传操作的代数（整数）。初试代数k = 1，使用随机方法或其他方法产生I 个可能解Xi （ 1