集装箱装载问题的模拟退火遗传算法 [日期：2005-12-19] 来源：电子技术应用 作者：江 娜 丁香乾 刘同义 张红兰 [字体：容器中，以获得某种最佳的效益。从计算复杂性理论来讲，装箱问题属于NP完全问题，求解极为困难。

遗传算法采用了生物进化论的思想，通过自然选择和适者生存的竞争策略来解优化问题；模拟退火起源于统计物理方法，并首先被Kirkpatrick等引入组合优化领域。遗传算法的全局搜索性能较强，便是其容易过早收敛，而且在进化后期搜索效率较低，种群的进化缓慢；需模拟退火算法具有较强的局部搜索能力，并且能使搜索过程避免陷入局部最优解，但是把握搜索过程的能力不强，运行效率不高。本文通过将模拟退火的思想引入遗传算法，使两者有效地结合，缓解了遗传算法的选择压力，增强了遗传算法的全局收敛性，避免在搜索过程中陷入局部最优。

1 遗传算法

遗传算法最早由美国Michigan大学的J.Holland教授提出，起源于上世纪60年代人们自然和人工自适应系统的研究，是基于Darwin进化论和Mendel的遗传学说的一种全局优化概率搜索算法，它模拟了生物界中的生命进化机制，在人工系统中实现特定目标的优化。对于复杂的优化问题，遗传算法无需建模和进行复杂的运算。与传统的搜索算法不同，遗传算法把优化问题的解的搜索空间转化为遗传空间，从代表问题可能潜在问题的解的搜索空间转化为遗传空间，从代表问题可能潜在解集的一个种群开始，其中种群中的每一个体对应问题的一个解，称为染色体。初代种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，按预先根据目标函数确定的适应度函数计算各个体对问题环境的适应值，再根据个体的适应值对个体对应的染色体进行选择，使适应性好的梁色体比适应性差的染色体有更多的繁殖机会；然后进行交叉、变异等遗传操作产生新一代群体。如此循环，逐步向优化的种群进化。

遗传算法的主要特点是：遗传算法的处理对象不是参数本身，而是对参数集进行编码的个体；遗传算法采用同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估；遗传算法仅使用问题的目标函数进行工作，不需要其他的先决条件或辅助信息；遗传算法不是采用确定性规则进行工作，而是采用概率的变化迁规则来指导其搜索方法；遗传算法具有隐形并行性，可以在较大的解空间迅速寻优。

标准的遗传算法求解过程如下：

（1）初始化遗传算法的控制参数，如群体规模N、变异概率pm、交叉概率pc；

(2)随机产生初始解群p(t)={p0p1p2…pn}，个体的数目一定，每个个体表示为染色体的基因编码；

（3）计算群体中每个个体的适应函数值；

遗传算法在搜索过程中基本不利于外部信息，仅以适应度函数为依据，利用种群中每个个体的适应度值进行搜索。因此适应度函数的选取至关重要，将直接影响遗传算法的收敛速度以及能否找到最优解。解的好坏用适宜度函数值的大小评估，适应度的函数值越大，解的质量越好。

（4）根据个体的适应度选择复制再生个体，适应函数值大的个体的复制概率大；

选择是指以一定的概率从种群中选择优胜个体，淘汰质个体的操作。选择的过程是一种基于适应的优胜劣汰的过程，是用来确定得组或交叉个体，以及被选个体将产生多少个子代个体。

（5）按照一定的交叉概率和交叉方法，对现有解群中的个体体交叉操作,生成新个体。

交叉是指对两个相互配对的染色体以某种方式相互交换部分基因，从而形成两个新的个体，交叉是遗传算法的核心。

（6）按照一定的变异概率和变异方法，对交叉后的个体进行变异操作；

变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因替换，从而形成一个新的个体。

（7）由交叉和变异产生了一新一代种群，若满足收敛条件，遗传进化过程结束；否则转（3）。

2 模拟退火算法

模拟退火算法是基于Monte Carlo迭代求解法后种启发式随机搜索算法，它模拟固体物质退火过程的热平衡问题与随机搜索寻优问题的相似性来达到寻找全局最优或近似全局最优的目的。在搜索最优解的过程中，模拟退火法除了可以接受优化解外，还有一个随机接受准则（Metropolis