遗传算法在组合优化问题中的应用

组合优化是运筹学的一个分支，同时也是计算机科学和数学科学所研究的内容[1，2]。一些数百年前数学家们偶然想到的问题和方法，已在网络通信、物流管理、交通规划等行业发挥了重要的作用，这也预示了这一交叉学科必然有着巨大的前景。

随着生产调度、最优化等组合优化问题的复杂化和大规模化，基于运筹学的传统寻优算法，如动态规划法、爬山法、分支定界等基于专家系统的逼近法已无法适用。这是因为，当组合优化问题的规模很大时，其求解难度呈指数增长，如SAT 问题和旅行商问题（TSP）。

SAT 问题是理论计算机科学的核心问题，是最早被证明为NP完全的问题，也是一大类NP完全问题的核心。研究解决SAT 问题的有效算法不仅具有重大的理论意义，而且在智能规划、智能决策、定理证明、电路设计和优化计算等诸多领域都有很大的实际应用价值。(www.xing528.com)

TSP是一个经典的组合优化问题，问题的解的组合数有（n-1）！ /2个，如此庞大的搜索空间，使得一般的算法都望尘莫及，而借助于演化算法较强的全局搜索能力和很好的普适性，则可以使得原本不可能计算的问题得到有效求解。TSP是一个NP-难度问题，是许多领域内出现的多种复杂问题的集中概括和简化形式，与交通规则、管道铺设、VLSI芯片设计、高速信息交换、自动路由寻址等一系列问题直接相关。因此，有效的解决TSP，不仅在可计算理论上具有重要的理论意义，同时具有重要的实际应用价值。

组合优化研究的是具有有限个可行解的优化问题。虽然在理论上这类优化问题的最优解可以用简单的穷举法找到，但在实际上是不可行的。这是因为实际问题的可行解的数量非常之多，以至于用穷举法不可能在合理的时间内求出问题的最优解。有一类称之为NP-难度的组合优化问题，这一类问题的可行解的数目与问题的规模呈指数增长，这一类问题没有已知的多项式时间的算法，目前求解这一类问题主要是用启发式算法或近似算法。近年来，智能优化算法在组合优化中的应用日益受到重视，特别是在求解NP-难度问题中取得了良好的结果，显示了它的巨大潜力。本章介绍如何用遗传算法求解组合优化问题。