摘要：智能算法已经成为解决大规模组合优化问题的有效方法，但每一种算法又有各自的适用域和局限性，因而算法融合的思想便开始被研究应用，大量研究也表明算法的混合策略有更高的优化效率。首先阐述目前常用的几种智能算法思想，分析各自优缺点，继而针对单一算法的不足，探讨了几种算法混合优化策略思想，最后对进一步的研究做出展望。
关键词：遗传算法；模拟退火算法；禁忌搜索；蚁算法；混合优化策略 1 智能优化算法概述
1.1 遗传算法
遗传算法（Genetic Algorithms，GA）是由美国Michigan大学的John H. Holland教授及其同事于1975年提出的一种借鉴生物界自然大报恩寺
选择和自然遗传机制的随机化搜索算法。
适配函数、交叉概率和变异概率的设定对算法的优化结果有直接的影响。GA开创了在解空间中从多出发点搜索问题最优解的先河，其优点如下：①利用变量的编码方式，而不使用变量本身；②在解空间中从多出发点搜索，具有隐含并行搜索特性，可大大减少陷入局部极小的可能；③直接利用目标函数的函数值信息，而不使用函数的导数或其它的辅助信息；④使用概率转移规则，而不采用确定性的转移规则。 但GA也有其自身的一些局限性，如：①在求解超大规模的优化问题时，GA的应用会有限制。是因为GA在进化搜索过程中，每代总要维持一个较大的体规模，从而使计算次数呈多项式时间增加，限制
了GA的使用；②易“早熟”。一方面，GA中最重要的遗传算子-交叉算子使体中的染体具有局部相似性，从而使搜索停滞不前。另一方面，变异概率太小，以至于不能使搜索转向其它的解空间进行
搜索；③爬山能力差。也是由变异概率低造成的。
波尔
1.2 模拟退火算法
模拟退火算法（Simulated Annealing，SA）的思想最早是由Metropolis等与1953年提出的，起源与统计物理学方法，1983年Krikpatrick等将其用于组合优化。是在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻目标函数的全局最
优解，即在局部能概率性地跳出并最终趋于全局最优。
新状态产生函数、新状态接受函数、退温函数、抽样稳定准则和退火结束准则（简称三函数两准则）以及初始温度是直接影响算法优
化结果的主要环节。
模拟退火算法的实验性能具有质量高、初值鲁棒性强、通用易实现的优点。但是，为寻到最优解，算法通常要求较高的初温、较慢的降温速率、较低的终止温度以及各温度下足够多次的抽样，因而模拟
退火算法往往优化过程较长。
1.3 禁忌搜索算法
禁忌搜索（Tabu Search，TS）是由Glover于1986年提出的一种
全局逐步寻优算法，是对局部邻域搜索的一种扩展。禁忌搜索最重要的思想是标记对应搜索到的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不
同的有效搜索途径的探索。
邻域函数、禁忌对象、禁忌表和藐视准则，构成了禁忌搜索算法的关键。
TS是在搜索过程中使用记忆功能的先驱者，TS算法的主要优点是：①TS使用了记忆功能，在搜索过程中可以接受劣解，因此具有较强的“爬山”能力；②新解不是在当前解的邻域中随机产生，而或是优于“best so far”的解，或是非禁忌的最佳解，因此选取优良解的
概率远远大于其他解。
后滕久美子>制动力分配缺点：①对初始解有较强的依赖性；②初始解只有一个，迭代搜
索过程是串行的，仅是单一状态的移动，而非并行搜索。
1.4 蚁算法
蚁算法（Ant Colony Algorithm，ACA）是Dorigo M等人于1991年提出的。经观察发现，蚂蚁个体之间是通过一种称之为信息素（pheromone）的物质进行信息传递的。在运动过程中，蚂蚁能够在它所经过的路径上留下该种信息素，而且能够感知信息素的浓度，并以此指导自己运动方向，倾向于朝着信息素浓度高的方向移动。因此，蚁的集体行为便表现出一种信息正反馈现象：某一路经上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过
这种信息的交流达到搜索食物的目的。
基本蚁算法的优点：①较强的鲁棒性。对该算法模型稍加修改，便可以应用于其它问题；②分布式计算。该算法是一种基于种的拟生态系统算法，具有本质并行性；③易于与其它方法混合。该算法很
容易与多种启发式算法结合，以改善算法的性能。
基本蚁算法的不足之处：①需要较长的计算时间，容易出现停
滞现象；②没有考虑信息素增量与路段的重要性的关系。
2 混合优化策略研究
算法混合的目的是使两种算法有机结合，保存各自优点，弱点被
克服或者被削弱，以提高算法的优化效率。
2.1 GASA组合优化策略
与遗传算法的总体运行过程相类似，遗传模拟退火算法是从一组随机产生的初始解（初始种）开始全局最优解的搜索过程，它先通过选择、交叉、变异等遗传操作来产生一组新的个体，然后在独立对所产生出的各个个体进行模拟退火过程，以其结果作为下一代体中
的个体。如此反复，直到满足某个终止条件为止。
GASA混合优化策略流程如图1所示。
图1 GASA混合策略流程图
GASA的特点：①优势互补。通过优化机制的融合，使得串行化的SA转化为并行化；通过SA对个体的进一步操作，补充了GA的进化能力，避免搜索结果陷入局部最优解；②是一个两层并行搜索结构。进程层次上，混合算法在各温度下串行地依次进行GA和SA搜
索，是一种两层串行结构。在空间层次上，GA提供了并行搜索结构，使SA转化成并行SA算法，因此混合算法始终进行体并行优化；
禁书③搜索行为可控。GASA可通过退温历程（即初温、退温函数、抽样次数）加以控制。
2.2 GATS 组合优化策略
GATS组合策略的思想是：把TS独有的记忆功能引入到GA进化搜索过程之中，构造新的重组算子TSR，使用TS作为GA的变异算子TSM，来改进GA的爬上能力。
GATS混合优化策略流程如图2所示。
图2 GASA混合策略流程图
GATS混合优化策略特点：①综合了GA具有多出发点和TS的记忆功能和爬山能力强的特点；②TSR算子作为重组算子。使用一个长度为T的禁忌表，表中记录染体的适应值，渴望水平取作父代体适应值的平均值。进行TSR操作时，首先把子代的适应值同渴望水平相比较，如果比渴望水平好，则破禁。即这个子代染体进入到下一代之中；如果子代比渴望水平差，但不属于禁忌，也接受这个子代；若是属于禁忌，则选择最好的那个父代进入到下一代中；③TSM 变异算子。使得变异操作变成一个TS搜索过程，利用评价函数和禁忌表来决定最后的输出结果，提高爬山能力。
2.3 ACAGA
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议