组合优化问题的求解

目前求解组合优化问题的方法主要有精确算法和启发式算法两大类。在求解规模较小的问题时，精确算法较为实用，求得结果较为精确。但在求解规模较大的问题时，精确算法较难实现，因此，选用启发式算法，启发式算法可以在有限的时间内找到满意解。

1． 精确算法

精确算法指可求出最优解的算法，主要针对数学模型进行求解，计算量一般随问题规模的增大而呈指数增长，所以多用于规模较小的问题。目前常用的精确算法有分支界定法、动态规划法、割平面法等。

（1）分支界定法［171］

分支界定法（Branch and Bound Method）是由Land和Diog提出， Daskin修正的。它可以用于全部整数型和部分整数型规划。分支定界法思路清晰、方法直观，但需要反复运用单纯形法求解，增大了计算工作量。

（2）动态规划法［171］

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划是美国数学家贝尔曼（R．Bellman）在1957年提出的。他在《动态规划》中指出应用动态规划求优时的最优化原则就是：“作为整个过程的最优策略具有这样的性质：即无论初始状态如何，对前面的决策所形成的状态而言，余下的所有决策必须构成一个最优策略。”这个原则就是我们建立动态规划数学模型的理论依据。

（3）割平面法

割平面法是由高莫瑞（R．E．Gomory）在1958年提出的，故又称为Gomory割平面法。它的基本思路是：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止。如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解。这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解（包括原已得到的非整数最优解），而把所有的整数解都保留下来，故称新增加的约束条件为割平面。当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解。即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。

总的来说，精确性算法是基于精确数学的方法，这类方法对数据的确定性和准确性有严格的要求。而实际生活中很多信息具有很高的不确定性，有些只能用随机变量或模糊集合，乃至语言变量来描述。此外，由于实际问题的复杂性，往往造成问题的规模很大，而利用精确方法求解往往难以满足大规模的组合优化问题的要求。

2． 启发式算法

前面我们讲到在实际中，需要解决许多复杂的组合优化问题。但是，一般情况下采用传统的精确算法难以进行有效的求解。因此提出了启发式算法，它主要针对于用传统精确算法所不能求解的优化问题。

1975年，美国Michigan大学的J．H．Holland教授及其学生、同事提出了遗传算法（Genetic Algorithms）。这种优化方法模仿生物种群中优胜劣汰的选择机制，通过种群中优势个体的繁衍进化来实现优化的功能。

1977年，Glover提出了禁忌搜索算法（Tabusearch，TS），几乎同时P．Hansen也做了类似的研究。它是一个著名的智能启发式搜索算法。这种方法将记忆功能引入最优解的搜索过程中，通过设置禁忌区阻止搜索过程中的重复，从而大大提高了寻优过程的搜索效率。

1983 年，Kirkpatrick 提出了模拟退火算法（Simulated Annealing）。这种方法模拟热力学中退火过程能使金属原子达到能量最低状态的机制，通过模拟的降温过程按波尔兹曼（Boltzmann）方程计算状态间的转移概率来引导搜索，从而使算法具有很好的全局搜索能力。

20世纪90年代初，意大利学者Dorigo等提出了蚁群优化算法（Ant Colony Optimization），这种算法借鉴蚂蚁群体利用信息素相互传递信息来实现路径优化的机理，通过记忆路径信息素的变化来解决组合优化问题。它尤其适用于处理传统搜索方法难以解决的复杂和非线性问题。

1995年，Kennedy和Eberhart提出了粒子群优化算法（Particle Swarm Optimization）。这种算法模仿鸟类和鱼类群体觅食迁徙中，个体与群体协调一致的机理，通过群体最优方向、个体最优方法和惯性方向的协调来求解实数优化问题。近年来该方法已经成为新的研究热点。

1999年，Linhares提出了捕食搜索算法（Predatory Search）。这种算法模拟猛兽捕食中大范围搜寻和局部蹲守的特点，通过设置全局搜索和局部搜索间变换的阈值来协调两种不同的搜索模式，从而实现了对全局搜索能力和局部搜索能力的兼顾。

此外，近年来，还提出了模仿食物链中物种相互依存的人工生命算法（Atificial Life Algorithms）；模拟人类社会多种文化间的认同、排斥、交流和改变等特性的文化算法（Cultural Algorithms）等各具特点的智能优化算法。在此不多做阐述。

相对于传统精确算法，以上算法具有一些共同的特点：

（1）不以达到某个最优性条件或找到理论上的精确最优解为目标，而是更看重计算的速度和效率；

（2）对目标函数和约束函数的要求十分宽松；

（3）算法的基本思想都是来自对某种自然规律的模仿，具有人工智能的特点；

（4）算法含有一个多个体的种群，寻优过程实际上就是种群的进化过程。