萧秋兰

（1 闽南科技学院计算机信息学院 福建 泉州 362332）

（2 大数据与人工智能福建省高校重点实验室 福建 泉州 362332）

0 引言

在人类的不断探索中，越来越多的复杂性和系统性问题呈现出来。组合最优问题是一个典型而又具有代表性的问题。例如AGV的小型汽车调整、CAD/CAM一体化的刀具轨迹优化、配送路径优化、IC设计等。所有的问题都可以被转换成最优的问题。试验结果也适用于其他的工程问题，所以对求解最优问题的高效求解是非常有用的。在此基础上，本文对路径最优解的逼近方法进行了大量的探讨。遗传算法和模拟退火算法都是以概率为基础的随机寻优方法。遗传算法采用基于群体的爬山法进行寻踪，具有良好的寻踪性能，但其收敛性能不强，且易于在局部优化中迷失[1]。而模拟退火则将个别的个体视为最优目标，它的局部寻优效果更好，收敛速度快，跳跃性好，能够跳过最优的周期，但其整体的寻优能力并不好。所以，两者组合既能有效地解决彼此的不足，又能最大限度地利用各自优势，从而防止局部最佳化。在此之前，曾有一种方案将两类方法有机地组合在一类新的遗传算法中[2]。

1 遗传模拟退火算法理论基础

1.1 模拟退火算法概述

在1953年，Metropolis引入了一个新的随机模式，它被称作Metropolis判别，并在 Metropolis判别的基础上给出了一个新的模型[3]。模拟退火方法的思路是对热环境下的热退火进行仿真，以求出最佳的组合最优问题。模拟退火是一种从固态退火中衍生出来的方法，它将固态加热到一定程度，然后慢慢降温。当加热的时候，固态颗粒会随着加热而变成不规则的状态，随着时间的推移，颗粒的内能逐渐增加，颗粒逐渐趋于均匀，最终在室温下内能下降到最低点。

该方法具有以下特点：①根据 Metropolis标准，模拟退火算法将会接收一个不“好”的结果，在接收非“好”的情况下，该方法将从局部最优中跳出来，接着再进行进一步的寻找，直至得到最优结果。②模拟退火方法得到的结果与初值不相关，也就是说，该方法的最后求解与迭代初始值没有关系。③模拟退火方法具有计算简便、易于实现NP（non-deterministic polynomial）难的特点。然而，模拟退火方法也有其不足之处：①模型的性能会被参量—制冷速度q所决定。如果降温速度低，则需要更多的时间来进行优化求解。如果降温速度太高，则可以得到更好的结果，但是也有可能会忽略最好的结果。要想得到降温速度q，必须经过大量的试验。②运算速度较慢。模拟退火方法对初温、降温速度和终端温度都有很大的影响，而且需要对各个温度下的Metropolis判据进行优化，而且该方法具有很好的收敛性[4]。

1.2 遗传算法概述

美国芝加哥大学的Holland在1967年基于达尔文的生物学演化理论以及孟德尔基因理论，发展了一种叫作基因演算法的演化方法[5]。基因演算法在自然遗传和自然选择中的繁殖、杂交和突变等方面进行了仿真，并给出了相应的方法，在该方法中，每个问题的解决方案都被编入一条与自然界中某一条染色体相匹配的染色体。

（1）该方法主要包括以下几个方面：①编码：通过选择合适的方法，把问题的答案进行编码，使之成为电脑能够辨识的格式。②原始群体：由chromsize条染色体组成的群体。该方法以chromsize条染色体为初始点进行了搜寻。③适应性评价：根据适应程度对方案进行评价。在进行遗传算法的过程中，采用基于目标函数的数学建模方法，来决定该方法的适用范围。④选择运算：通过选择运算可以从现有群体中筛选到较高的亲本，高适应性的则有可能成为父系后代[6]。⑤交叉：新一代的染色体可以由交叉处理获得。⑥突变运算：突变运算可以在特定的概率下，随意地修改特定的基因，从而生成新的遗传，维持遗传的多样化。

（2）该方法主要包括：①群体的大小：群体大小是该群体中的染色体数目。群体数量的确定，主要是从遗传的角度来看，群体数量尽可能大，不会落入局部最好；从计算速度上看，人口数量的增大会引起运算量的增大。人口的大小要视现实问题而定，人口大小的建议是0～100。②变异概率：一种与自然遗传的遗传变异相似的微小概率干扰。通常的数值是0.0001～0.29。③交配概率：一种与自然生殖中的染色体的交叉组合相似的遗传变异。这个数值通常在0.4～0.99之间[7]。

2 遗传模拟退火算法设计

遗传模拟退火算法是一种通过模拟被测样本点的遗传状态，模拟样本点之间的遗传关系而构建出来的一种优化算法。在进行训练之前，本文首先用简单的模拟退火算法将样本点进行随机排列。算法不需要经过反复变异。在训练时，本文利用遗传算法中遗传编码功能（transcription）作为初始遗传因子。然后利用基因编码功能（rgp）或随机选择功能（interpression）来对每个变异进行遗传编码（excel），从而使得被测样本点保持遗传稳定性不变。具体步骤如：（1）确定最优化目标函数和终止准则；（2）根据实际情况设定参数α和b,其中β为适应度函数值；（3）按照一定规则调整参数c,并且保证其与待测值的偏差最小；（4）重复上述操作直至达到目标函数最大值；（5）重复以上步骤,直到满足条件。这个过程实际上是一个在遗传模拟退火算法中建立不变性模型的过程。因此，可以将上述过程理解为一种将被测样本点作为遗传信息载体（DNA、RNA、tgp或looks等）进行繁殖处理，通过人工构建子种群使其适应基因编码所提供遗传信息而实现无变异模型，并在此基础上进行进化形成新种群的过程。通过遗传模拟退火算法，本文可以了解到哪些基因没有变异，哪些基因仍会受到相应生物条件约束[8]。

随机排列是在样本点随机分配的基础上产生的。因此它能够满足对遗传信息（matrix）获取的基本需求。对随机排列的定义为：将每个序列随机地排列在一个节点上，并将每个序列随机地取一个序号（表示序列的初始值）以适应该序列本身。在此规则下，本文利用了最小二乘来确定序列大小和最小二乘系数，同时利用了最小二乘系数最小化这个规则来求解序列大小和最小二乘系数值。下面是样本点随机排列的实验结果：当种群个数不变时，每一种序列都会增加一个新子种群；当种群个数越多时，每一个序列都会增加一个新子种群（表示种群个数的线性组合）。本文以图1中表示各序列之间的相对距离为单位：当本文在每个序列中计算不同长度乘以不同宽度时可以得到样本点随机排列时序列大小以及各序列之间相对距离之间的函数关系：那么这些序列大小会随时间而变化，但是距离越长或者越短它们之间的关系则越稳定。因此可以得出在所有序列越长（大于4/4）各序列之间相对距离就越大。

将本文想要达到的优化目标设为初始目标函数W（x）时，初始遗传因子为（0,x），为f（x）的一阶导数。那么初始因子为a和b即可以通过下列公式求得：其中b表示目标函数g（x）和g（y）在训练时的初始值，为b在训练过程中选取的初始参数。本文假定目标函数g（x）取值f（x）为初始值。假设本文想要得到一个给定权重c，本文首先得到其权重a为1（b=1/2），则初始变量c在所有给定权重b的条件下可以求得：其中f表示当前函数在所有给定权重a（x）上预测到的所有权重a×1。通过在一个可接受水平下求得目标函数g（x），本文则可以得到目标函数g（x）由n个给定权重a组成：其中ωj即为目标函数g（x）在n个给定权重a下预测期望值c与期望值之差。

然后，在遗传模拟退火算法中，本文需要根据原始种群进行选择与进化，以适应其无变异能力。在前一个步骤中，本文已经建立了一种初始种群，它是根据随机选择的遗传编码来建立的。在该阶段的初始种群选择过程中，本文需要考虑三个因素的影响：种群基因选择水平、子种群适应能力、随机选择进化。其中，种群基因选择水平是指从种群初始遗传因子A的角度来看，该种群可以作为一个随机个体被选择和进化。此时，如果有新遗传因子A作为初始因子，则可以使得种群遗传能力提高到1。在个体适应能力、随机选择进化后将产生1～3个个体组成新种群。为了获得更好的进化效果，本文需要选择更多个体组成新种群。同时，当群体基因适应能力出现问题时（例如：低进化和高进化），子种群不会进化得更好，即子种群无法适应该群体中有新基因出现或者其进化得太快而不适应种群自身进化效率低时，将停止进化。因此，为了保持无变异能力并保持种群遗传能力不变，将会对一个群体中的所有个体进行选择和进化，从而获得更好的进化效果。

通过对模拟退火算法的优化，本文提出了以下几点：①在求解初始解时，使用遗传演算法中对染色体进行了编码，生成了初始群体，从而提高了模拟退火的平行查找性能；②在生成新的解决方案时，采用选择、交叉和变异等方法来生成新的方案，取代了模拟退火算法中的任意生成新的方案，通过对其进行优化，从而能快速地求出最好的结果。该方法无须经过大量的试验，就能得到更好的求解，从而减少了求解速度q的问题。该方法的流程表如图1所示。

图1 遗传模拟退火算法流程示意图

3 遗传模拟退火算法流程分析

3.1 初始解构造设计

该方法包括构造初始解、生成新解、求解方法优化以及算法周期等。该方法首先从均衡速率大的问题（即初值）出发，寻求最优化问题，并为其设计出一种合适的初值结构。为了提高模拟退火方法的平行查找性能，本文提出了一种新的基于遗传算法的原始群体生成方法，将初始解的结构划分为编码、初始种群、合法解决和有效解决四个阶段。通过实例Jaeschks9，对初解的构建过程进行了详细的阐述。

特别在编码与生成初期人口的过程中，本文将问题进行了代码化，并将其转化为可由电脑辨识的资料，此问题则是流水作业的均衡问题，而代码是将作业交给了一个工作站，并将其转换为电脑所能辨识的资料，该资料被称作“染色体”。每一条链上的每一个点都代表着一个基因的价值，也就是一个序列。由若干个具有特定染色体的群体构成的群体，其染色体数就是群体的大小。在迭代过程中，最初的群体是首先生成的群体。在求解过程中，合理的解决方案是一个符合该模式的限制。在编写代码时，将任务放在了一个工作站上，不需要考虑到任务与任务的优先级，因此需要设计一个合适的优化方案来保证代码的优先级。在进行优化求解时，必须先决定每个问题的分布前后，然后再根据优先权来决定任务的分布。在此基础上，根据实例的任务优先级，分别求出各任务优先级，当各任务i的优先级大于各优先级的中位时，由前向后依次进行排序；在任务i的权重小于其优先权的中间位时，将i按从前到后依次进行排序。最优的输出解集就是从符合任务优先关系的原始群体的合理解中，选择最大的一个作为初始方案。

3.2 新解产生

在模拟退火中，由于新的求解是以一种随机生成的形式生成的，在此基础上，利用遗传算法中的“优胜劣汰”的概念，对新的求解方法进行选择运算、交叉运算和突变运算，生成新的解集后进行修正，使得该方案符合数学模式的限制，最终得到一个合法的新的解决方案。选取运算采用冠军方法，选取具有更大的目标值的个体构成新群体；双点是通过两个染色体的2个片段进行交换而形成新的染色体；突变是从旧有序列中随机抽取相应的序列，生成新的染色体。通过举例，Jaeschks9对新解的生成过程进行了详细的阐述。

根据“优胜劣汰”的原则，先从原始群体中挑选出具有较高适应性的优质基因，并将其遗传给后代。自然选择运算与自然界的自然选择相一致，即群体中的适应性较强的个体，其繁殖后代的概率也较高：在计算中，遗传因子的适配度愈高，则被选取进行遗传和突变。常见的选择运算有：随机遍历取样法、冠军选择法等。针对此问题，本文提出了一种适用于求解对象的遗传模拟退火优化方法，适用范围为：目标函数的数值愈大，则其自适应能力愈强，且在选取运算时，被选取概率越高。“交叉运算”是从群体中任意选取两条染色体，以一定的方法进行交换，从而构成两条新的染色体。常见的交叉运算有单点交叉、双点交叉、多点交叉、均匀交叉和计算交叉。双点交叉是在两条染色体上任意选取两个相交的节点，再进行局部的基因互换，从而生成两条新的染色体。进行双点交的染色体数目是chromsize xpc, pc是一个交叉的可能性，因为只有在2个染色体上，一条染色体不能同时进行两个点的交叉。因此，选择两个点的数目都是2，也就是说，在设定参数时，要确保chromsize xpc能被2整除，这样就能把chromsize xpc条对成对。在筛选处理之后，从新一代群体Chromsize xpc条中，将chromsize xpc条染色体进行成对并二次杂交。在两个点间进行交叉运算的 chromsize xpc条染色体与没有进行双点间的chromsizex（1 pc）条染色体构成了群体Chrom2。在进行两个点的交汇时，必须先找出两个点的相交，这个相交的地方就是一个染色体上的遗传互换，两个点相交的地方是一个任意位置。基因数目指的是在两个点交处进行的基因数目，在两个节点处进行的数据互换，当两条染色体进行双重点交再进行时，其所产生的交集和交换的基因数目基本相同。在决定两个点间的交汇部位和所需的基因数目之后，将在第二个交叉处的基因序列编号为相交的2个基因序列+1个转换者。判定第二个相交部位的基因序列比染色体长大；如果在第二个交叉处的基因编号小于该染色体的话，可以进行常规的两个交叉处理；如果在第二个相交部位的基因序列比染色体长大，那么在相交2的另一个片段是[2,I]。在进行二次交叉时，第一个染色体的第一个交叉点1和第二个的交叉点2互换了位置，突变运算是指从群体中随意选取一条或几条染色体，通过修改选定的染色体来获得更好的染色体。变异运算的目的在于保持群体的多样化，从而避免了演算法的局部最优化。常见的变异运算包括：基础位变异、均匀变异、边界变异、非均匀变异以及高斯近似变异。基础位突变是根据特定的变异概率，随机选取一条或多条特定的基因进行突变计算。

3.3 算法循环

该方法包括两种主要的演算法：一是在T的温度下求最佳的求解，当达到目前的温度T时，该周期就会终止；二是用基因仿真方法来实现冷却，从最开始的温度开始冷却，直到达到最终的冷却，从而完成整个计算。本文将对这两个周期的流程进行详细的阐述。

（1）在T的情况下的演算法周期

在T的条件下，采用马尔可夫链长度L和周期u对遗传模拟退火方法进行优化。若周期数u比马尔可夫链长度L（u＜L）少，则该方法可在T的最大值下求出最好的结果；在此条件下，若周期u的周期比马尔可夫L更大，则在目前的环境下完成该周期。

（2）冷却工艺

该方法采用了一种基于基因的仿真方法，从起始点开始逐步冷却，直至到达最终的冷却温度。该方法在T时间完成了一个算法周期之后，从目前的气温T跳过，再采用T=T-q的冷却方程进行冷却，冷却之后，在新的温度T下，再进行求解；在新的温度T完成了解决方案的查找之后，冷却过程持续进行，直至达到温度T＜终点温度T，并且在温度T＜终点温度T时，将各自的结果进行比较，并将其结果作为最大值而输出。

4 结论

综上，首先本文分析了在遗传模拟退火算法中，不同类型的基因分别受到不同条件约束的问题。如果这些影响是通过自然种群中的子种群来达到，那么它就一定能够很好地适应遗传算法中给定的基因序列所要求的环境。如果它们是人工种群，那么本文就可以通过构建新的子种群来解决它们在这些生物条件约束下无法适应突变导致的种群变化问题。如果对所有这些目标都进行优化，本文将得到满足这些要求的结果，如果有一些目标还不满足，本文还可以通过人工构建新个体实现目标，从而实现对目标的进一步优化以满足更大范围内的优化需求。因此这种方法能够更好地模拟自然界环境下生物的生存条件。并且这种方法没有发生变化也不需要考虑遗传信息。另一方面，这种方法最大可能地模拟出环境中多种基因相互作用、相互影响才能达到的最优效果，有可能通过生物条件约束来解决问题。