打开文本图片集
集装箱班轮航线配船是制订船舶生产计划的中心环节，是复杂的、多因素的系统优化问题，其目的是充分利用现有条件和资源，以最少的投入或消耗，换取最大的产出或效益。随着运筹学的兴起和发展，特别是线性规划理论及方法的逐步完善，各种新型数学方法，如遗传算法、神经网络算法、模拟退火算法等被用于班轮航线配船上，各种数学模型相继建立。
本文将遗传算法与模拟退火算法相结合，从而优化模型设计过程，提高求解效率，克服传统遗传算法的缺陷，避免陷入局部最优。
1 遗传算法与模拟退火算法的结合
1.1 遗传算法和模拟退火算法的原理
遗传算法是借鉴适者生存、优胜劣汰的生物界进化规律而演化出的随机搜索算法，是由美国密歇根大学HOLLAND教授于1975年首先提出的新型全局优化搜索算法。遗传因子经过迭代能启发式地自适应搜索具有全局最优解的较小区域，并以较大的概率趋向于全局最优解。利用该原理能够有效解决许多常规优化方法难以解决的复杂优化问题。
模拟退火算法最早于1983年由KIRKPATRICK等用于组合优化领域，是基于蒙特卡罗迭代求解策略的随机寻优算法，基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。其从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解中概率性地跳出并最终趋于全局最优解。
1.2 遗传算法和模拟退火算法的局限性
遗传算法处理的对象不是参数本身，而是对参数集进行编码后的个体。由于应用了编码技术，可直接对结果对象进行操作，不存在求导和函数连续性的限定，因此适用于各类优化问题。然而，由于遗传算法采用根据适应度值大小来决定个体是否被复制的选择机制，容易出现来源于同一种群的个体被大量繁衍的情况，形成近亲繁殖，造成算法的局部搜索和过早收敛。由此可见，遗传算法具有一定的局限性，主要表现如下：（1）遗传算法属于启发式算法，求得的是近似解，求解效率有限；（2）需针对问题设计合适的编码方式，编码方式的优劣直接影响求解质量；（3）除非模型能提供最优解参考值，否则不能确定演算结果是否最佳；（4）由于此方法为群体同步搜寻，因此会占用计算机内存空间，影响演算速度。
理论上模拟退火算法以1的概率收敛，但局限性也较明显[1]，主要表现如下：（1）实际设计算法时算法结果存在波动性；（2）为寻找最优解，通常要求较高的初温、较稳的降温速率、较低的终止温度以及各温度下足够多次的抽样，优化过程较长，受计算速度和计算时间的限制，难以保证计算结果为全局最优点，优化效果不理想；（3）由于马尔可夫链的长度不易控制，在每一温度下很难判定是否达到平衡状态，反映到计算过程中就是实现Metropolis准则的次数不易控制。
1.3 构造混合遗传—模拟退火算法
遗传算法与模拟退火算法相结合是解决两种算法各自局限性问题的有效途径，具体来说有以下四方面的结合。[2]
（1）优化结构的互补 模拟退火算法采用串行优化结构，而遗传算法采用群体并行搜索方法，两者结合能使模拟退火算法成为并行算法，在提高自身优化性能的同时作为自适应的变异操作，增强和补充遗传算法的进化能力。
（2）优化操作的结合 模拟退火算法每一时刻仅保留1个解，缺乏冗余和历史搜索信息；而遗传算法的复制操作能在下一代中保留种群的优良个体，交叉操作能使后代在一定程度上继承父代的优良模式，变异操作能增强种群中个体的多样性，这些不同作用的操作相结合，丰富了优化过程中解空间的搜索结构，增强了全空间的搜索能力。
（3）优化行为的互补 由于复制操作对当前种群外的空间无搜索能力，种群中个体分布“畸形”使交叉操作的进化能力有限，而小概率变异操作很难增加种群的多样性，因此，若收敛准则设计得不好，则会出现进化缓慢或早熟收敛的现象，结合后并行化的抽样过程可优化算法的时间性能。
（4）削弱参数选择的苛刻性 设计算法时需依靠大量的试验和经验来确定两者相结合后算法各方面的搜索能力均得到提高，因此，对算法参数的选择不必过分严格。研究表明，混合算法在采用单一算法参数时，优化性能和鲁棒性均有大幅度的提升，尤其是针对较大规模的复杂问题。
2 利用混合遗传—模拟退火算法求解班轮航线配船问题
2.1 班轮航线配船问题描述及模型建立
参考文献：
[1] 段姹莉，陈波．VB环境下的模拟退火算法求指派问题[J]．电脑知识与技术，2008，4（8）：2153-2155.
[2] 丁香乾，韩运实，张晓丽．自适应遗传算法解决集装箱装载问题的方法探讨[J]．中国海洋大学学报：自然科学版，2004，34（5）：844-848.
（编辑：张婕 收稿日期：2010-12-17）