下载掌阅APP，畅读海量书库
立即打开
组合优化问题是最优化问题的一类。最优化问题可以自然地分成两类：一类是连续变量的问题，另一类是离散变量的问题。其中，具有离散变量的问题称为组合问题。在连续变量的问题里，一般是求一组实数或者一个函数；在组合问题里，是从一个无限集或者可数无限集里寻找一个较优对象，如一个整数，一个集合，一个排列或者一个图。一般地，这两类问题具有不同的特点与不同的求解方式。
组合优化问题通常可描述为：Ω={ s 1 ， s 2 ，…， s n }为所有状态构成的解空间， C （ s i ）为状态 s i 对应的目标函数值，要求寻找最优解 s * ，使得
∀ s i ∈Ω， C （ s * ）=min C （ s i ）
组合优化往往涉及排序、分类、筛选等问题。
min f （ x ）
s . t . x ∈ S ， S ∈ X （ S ， X ：拥有有限个或可数无限个解的离散集合）
式中， f （ x ）是目标函数； x 是问题的解； X 是解空间； S 是可行解空间（可行域）， X 包含 S 。
如果 S 是有限集合，从理论上讲，只要遍历所有的组合，就能找到最优解，然而随着问题规模的增大， S 中解的个数会迅速增大，实际上要想遍历所有的解，几乎是不可能的。
所谓组合优化，是指在离散的、有限的数学结构上，寻找一个（或一组）满足给定约束条件并使其目标函数值达到最小的解，即在离散状态下求极值的问题。把某种离散对象按某个确定的约束条件进行安排，当已知合乎这种约束条件的特定安排存在时，寻求这种特定安排在某个优化准则下的极大解或极小解。组合优化的理论基础包括线性规划、非线性规划、整数规划、动态规划、网络分析等，组合优化技术提供了一个快速寻求极大解或极小解的方法。
具体而言，组合优化问题的目标是从组合问题的可行解集中尽可能地求出最优解。组合优化往往涉及排序、分类、筛选、分配等问题，它是运筹学的一个重要分支，在信息技术、经济管理、工业制造、交通运输、通信网络等领域得到广泛的应用。
1.约束性
在不同的应用背景下，组合优化问题往往具有一个或多个约束条件，如各变量间的优先级关系、变量取值范围等。例如，测试任务调度是一类典型的组合优化问题，一般而言，测试任务之间存在各种相关性，因此在测试过程中需要严格遵守任务的先后顺序，即任务优先级约束。同时，由于仪器的测试能力有限，必须为任务分配可以处理本次测试任务的仪器，即资源约束。
2.离散性
在组合优化问题中，变量是离散的，解空间也是离散的，由大量散点组成。例如：测试任务调度就是一个离散问题，测试任务以及所选仪器均是离散的。对于该类问题，梯度下降法、牛顿法等连续优化方法的使用受限，最初是利用数学规划或离散系统建模的方法来解决。
3.计算复杂性
在组合优化问题中，随着变量数的增加，解空间呈指数倍增长，具有组合爆炸效应，从计算时间复杂度来看是一个NP难题（Non-Deterministic Polynomial Problem），求解非常困难。在NP类问题中有这样一些问题，如果其中有一个存在（不存在）有效算法，那么所有其他问题也都存在（不存在）有效算法，这些问题被称为NP-完备问题或NPC问题。绝大多数组合优化问题都是NP-完备的。
例如，测试任务调度问题实际分为两个部分，一是测试任务的合理调度，二是测试资源的优化配置，这两方面相互影响。从测试任务的角度讲，不同的任务序列的全排列有 n 种（ n 为任务个数）。从测试资源的角度讲，测试任务可选的测试方案组合的总数是按任务个数的指数规律增加的。也就是说，测试任务调度问题是一个在若干约束条件下的组合优化问题，随着任务和资源个数的增加，解空间急速增大，求解难度增大。
4.多目标
传统的组合优化问题以求最小值或最大值为目标，可以转化为最小化或最大化问题。随着应用场景复杂程度的增加，组合优化问题呈现出多目标的趋势，如何使多个目标相互协调，在满足约束条件的前提下满足问题的需要，成为组合优化问题的一大难点。例如，对于调度问题来说，针对不同的应用场景，需要满足的调度目标一般不同，甚至可能在某些情况下需要同时满足多个方面的调度目标的需求，而且这些目标之间往往是有冲突的。比如调度时间最短、资源的总负荷最小等。所以，多目标使组合优化问题的求解更加困难。
一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全（难）问题，求解该类问题往往无法利用导数信息，精确得到全局最优解的“有效”算法一般是不存在的。
1.旅行商问题
旅行商问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题。经典的TSP可以描述为一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。
2.加工调度问题
加工调度问题是由任务排序子问题和资源分配子问题组成，包括柔性车间调度（Flexi-ble Job-shop Scheduling Problem，FJSP）、并行机调度（Parellel Machine Scheduling Program，PMSP）、测试任务调度（Test Task Scheduling Problem，TTSP）等，广泛应用于制造业、服务业、云计算、物联网等领域。该类问题可以归纳为一个特定约束条件下的组合优化问题，它由一系列顺序或并行执行的任务（如工件、测试任务等调度需求）组成，每个任务需占用一定的资源并可能存在资源冲突，任务间相互独立或具有局部优先级关系，其调度目标是将所有任务以合理的顺序和方式分配给相互独立的资源，达到资源利用率高、系统可靠性强等目的。
3.0-1背包问题
背包问题（Knapsack Problem）是一种组合优化的NP完全问题。问题可以描述为给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。例如，寻找最少浪费的方式来削减原材料，选择投资和投资组合，选择资产支持资产证券化等。可见，背包问题在各种决策领域中有广泛的应用。
4.装箱问题
经典的装箱问题要求把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱子数目最少。装箱问题广泛存在于工业生产中，包括服装行业的面料裁剪，运输行业的集装箱货物装载，加工行业的板材型材下料，印刷行业的排样和现实生活中包装、整理物件等。在计算机科学中，多处理器任务调度、资源分配、文件分配、内存管理等底层操作均是装箱问题的实际应用，甚至还出现在一些棋盘形、方块形的数学智力游戏中。装箱问题的研究文献分布面很广，在运筹学、计算机辅助设计、计算机图形学、人工智能、图像处理、大规模集成电路逻辑布线设计、计算机应用科学等诸多领域都有装箱问题最新的研究动态和成果出现，从这个角度来讲，布局问题涉及了工业生产的方方面面，也足以证明了装箱问题的应用前景日趋广泛。
5.图着色问题
图着色问题（Graph Coloring Problem，GCP）又称着色问题，是最著名的NP-完全问题之一。它由地图的着色问题引申而来：用多种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。图着色问题大体分为两类，即顶点着色和边着色。顶点着色中，给定无向图，用每种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色。在边着色问题中，给定无向图，用每种颜色为图中的每条边着色，并使相邻两条边有着不同的颜色。图着色问题应用领域广泛，如交通管理系统中交叉路口的信号灯设计、不相容化学制品的分库储藏问题、排课时间表问题、会场安排问题等。
求解组合优化问题的方法可以分为精确算法和近似算法两类。常用的精确算法有动态规划法、分支定界法和枚举法。
动态规划法是运筹学的一个分支，是求解决策过程最优化的常用方法。对于组合优化这类离散问题，由于解析数学无法发挥作用，动态规划便成为一种非常有用的工具。动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
一般来说，只要问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解，则可以考虑用动态规划解决。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复，以解决最优化问题的算法策略。由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经做出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自上向下，一步一步地做出贪心选择；而分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地求解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，也允许其通过自身子问题的解做出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知最优值的那些子集不再做进一步分支。这样，解的许多子集就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。这种算法一般可以求得最优解，但不适用于大规模解空间的搜索。
随着组合优化问题的发展，问题解空间越来越大，早已超出了精确算法的求解能力。目前，人们尚未找到任何一个NP-完备问题的有效算法。但在很多实际应用中，人们只需找到NP-完备问题的“不错的”解，而不必是最优解。因而，近似算法成为求解组合优化问题的方法之一。近似算法分为基于数学规划（最优化）的近似算法、启发式算法和基于智能优化的近似算法。
1）基于数学规划的近似算法是根据对问题建立的数学规划模型，运用如拉格朗日松弛、列生成等算法以获得问题的近似解。拉格朗日松弛算法求解问题的主要思想是分解和协调。首先对于组合优化问题，其数学模型须具有可分离性。通过使用拉格朗日乘子向量将模型中复杂的耦合约束引入目标函数，使耦合约束解除，形成松弛问题，从而分解为一些相互独立的易于求解的子问题，设计有效的算法求得所有子问题的最优解。利用乘子的迭代更新实现子问题解的协调。列生成算法是一种已经被认可的成功用于求解大规模线性规划、整数规划及混合整数规划问题的算法。与智能优化算法相比，基于数学规划的近似算法的优点是通过建立问题的数学模型，松弛模型中难解的耦合约束或整数约束，得到的松弛问题的最优解可以为原问题提供一个下界。同时，基于数学规划的近似算法还具有很好的自我评价功能，通过算法运行给出的问题的近优解（或最优解）为原问题提供一个上界，上界与下界进行比较，可以衡量算法的性能。
2）启发式算法是根据求解问题的特点，按照人们经验的或某种规则设计的。这是一种构造式算法，比较直观、快速，利用问题的知识设计求解的方法步骤，具有操作简单的优点，但所得解的质量不一定好。
3）基于智能优化的近似算法是基于一定的优化搜索机制，并具有全局优化性能的一类算法。这类智能优化算法常见的有：模拟退火算法（Simulated Algorithm，SAA）、遗传算法（Genetic Algorithm，GA）、蚁群算法（Ant Colony Optimization，ACO）、迭代局部搜索算法（Iterated Local Search，ILS）、禁忌搜索算法（Tabu Search，TS）、分散搜索算法（Scatter Search，SS）、粒子群算法（Particle Swarm Optimization，PSO）等，这些算法也称超启发式算法（Meta-heuristic）。
智能优化算法是一种通用的算法框架，只要根据具体问题特点对这种算法框架结构进行局部修改，就可以直接应用它去解决不同的问题。这类算法本身不局限于某类问题，具有实践的通用性，适应于求解工业实际问题，在较快地处理大规模数据的同时得到令人满意的解。基于智能优化的近似算法，采用不同的搜索策略和优化搜索机制，寻找问题的近似最优解，具有很好的求解优势。虽然基于智能优化的近似算法不能保证求得全局最优解，但因其高效的优化性能、无需问题特殊信息、易于实现且速度较快等优点，受到诸多领域广泛的关注和应用。基于智能优化的近似算法成为求解复杂组合优化问题主要的有效方法。