95信息：理论与观点信息记录材料2022年12月第23卷第12期0引言在人类的不断探索中，越来越多的复杂性和系统性问题呈现出来。组合最优问题是一个典型而又具有代表性的问题。例如AGV的小型汽车调整、CAD/CAM一体化的刀具轨迹优化、配送路径优化、IC设计等。所有的问题都可以被转换成最优的问题。试验结果也适用于其他的工程问题，所以对求解最优问题的高效求解是非常有用的。在此基础上，本文对路径最优解的逼近方法进行了大量的探讨。遗传算法和模拟退火算法都是以概率为基础的随机寻优方法。遗传算法采用基于群体的爬山法进行寻踪，具有良好的寻踪性能，但其收敛性能不强，且易于在局部优化中迷失[1]。而模拟退火则将个别的个体视为最优目标，它的局部寻优效果更好，收敛速度快，跳跃性好，能够跳过最优的周期，但其整体的寻优能力并不好。所以，两者组合既能有效地解决彼此的不足，又能最大限度地利用各自优势，从而防止局部最佳化。在此之前，曾有一种方案将两类方法有机地组合在一类新的遗传算法中[2]。1遗传模拟退火算法理论基础1.1模拟退火算法概述在1953年，Metropolis引入了一个新的随机模式，它被称作Metropolis判别，并在Metropolis判别的基础上给出了一个新的模型[3]。模拟退火方法的思路是对热环境下的热退火进行仿真，以求出最佳的组合最优问题。模拟退火是一种从固态退火中衍生出来的方法，它将固态加热到一定程度，然后慢慢降温。当加热的时候，固态颗粒会随着加热而变成不规则的状态，随着时间的推移，颗粒的内能逐渐增加，颗粒逐渐趋于均匀，最终在室温下内能下降到最低点。该方法具有以下特点：①根据Metropolis标准，模拟退火算法将会接收一个不“好”的结果，在接收非“好”的情况下，该方法将从局部最优中跳出来，接着再进行进一步的寻找，直至得到最优结果。②模拟退火方法得到的结果与初值不相关，也就是说，该方法的最后求解与迭代初始值没有关系。③模拟退火方法具有计算简便、易于实现NP（non-deterministicpolynomial）难的特点。然而，模拟退火方法也有其不足之处：①模型的性能会被参量—制冷速度q所决定。如果降温速度低，则需要更多的时间来进行优化求解。如果降温速度太高，则可以得到更好的结果，但是也有可能会忽略最好的结果。要想得到降温速度q，必须经过大量的试验。②运算速度较慢。模拟退火方法对初温、降温速度和终端温度都有很大的影响，而且需要对各个温度下的Metropolis判据进行优化，而且该方法具有很好...
