摘自： 百度百科：组合优化

组合优化问题

概念

组合优化（或称为离散优化）是一门古老而又年轻的学科，著名数学家Fermat，Euler等都为其形成和发展作出过重要贡献二十世纪后半叶。伴随着工业科技革命和现代管理科学的发展，特别是计算机技术的突飞猛进和在各行业的广泛应用，组合优化已壮大成为运筹学的一个独立分支。一些数百年前数学家们偶然想到的问题和方法，已在网络通信、物流管理、交通规划等行业发挥了重要的作用，这是他们当时所不曾想到的。这从另一方面寓示了这学科的巨大前景。
组合（最）优化问题是最优化问题的一类。最优化问题似乎自然地分成两类：一类是连续变量的问题，另一类是离散变量的问题。具有离散变量的问题，我们称它为组合的。在连续变量的问题里，一般地是求一组实数，或者一个函数；在组合问题里，是从一个无限集或者可数无限集里寻找一个对象——典型地是一个整数，一个集合，一个排列，或者一个图。一般地，这两类问题有相当不同的特色，并且求解它们的方法也是很不同的。对于具有离散变量的问题，从有限个解中寻找最优解的问题就是组合最优化问题。

数学定义

设F是有限集，c是F到R(实数集)的映射，即C是定义在F上的一个函数。求f∈F，使得对于任意的y∈F，有
组合优化 - 图1
成立。上述问题我们简记为：求
组合优化 - 图2
一个组合最优化问题可用二元组(F，c)表示，其中F表示可行解区域，F中的任何一个元素称为该问题的可行解，c表示目标函数。满足
组合优化 - 图3
的可行解，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<=i<=n，k = 1）组成初始解群。
（2）对于群体中每一个个体Xi （ k），计算其适应度 f（Xi （ k））。
（3）若whiie（！结束条件）
对于群体中每一个体Xi（ k ），计算其生存概率
组合优化 - 图4
根据生存概率Pi （ k），在群体中选择父体执行遗传操作，包括复制、交叉、变异，得到一个新的解群体，此时k = k + 1，转（2）步。
（4）满足条件，结束操作。
遗传算法解决问题的第一步是确定编码方案，而编码方案的选取在很大程度上依赖于问题的性质及遗传算子的设计。组合优化问题都具有不同程度的约束条件，如TSP问题要求每个城市只能经过一次等，那么在编码方案和遗传算子的设计上就有了一些特殊的要求。因此，在求解组合优化问题算法的具体实现过程中，主要工作包括确定编码方案和设计遗传算子（交叉、变异等）。
编辑 语音

应用

典型的组合优化问题有：
旅行商问题（Traveling Salesman Problem－TSP）；
加工调度问题（Scheduling Problem，如Flow-Shop，Job-Shop）；
0-1背包问题（Knapsack Problem）；
装箱问题（Bin Packing Problem）；
图着色问题（Graph Coloring Problem）；
聚类问题（Clustering Problem）等。
这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。
参考资料

    1. 董振宁. 几个组合优化问题的研究[D]. 山东大学, 2004.
    1. 马立肖, 王江晴. 遗传算法在组合优化问题中的应用[J]. 计算机工程与科学, 2005, 27(7):72-73.

学术论文

WIKI：组合最优化【中文】

组合最优化，在应用数学和理论计算机科学的领域中，组合优化是在一个有限的对象集中找出最优对象的一类课题。在很多组合优化的问题中，穷举搜索／枚举法是不可行的。组合优化的问题的特征是可行解的集是离散或者可以简化到离散的，并且目标是找到最优解。常见的例子有旅行商问题和最小生成树。二维的例子，比如服装厂做衣服，衣服分成很多块，这些块需要从布料上切下来。怎么切，剩下的废布料最少？三维的例子，如集装优化。
组合优化的难处，主要是加进来拓扑分析，不同的拓扑形态下，不同部分的约束关系便不同，算法也就要调整。如果给定一个拓扑形态，组合优化往往就退化成一个整数优化的问题了。

WIKI：Combinatorial optimization【英文原文】