遗传模拟退火算法的优化研究_萧秋兰.pdf

95信息：理论与观点信息记录材料 2022年12月 第23卷第12期 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 条染色体为初始点进行了搜寻。适应性评价：根据适应程度对方案进行评价。在进行遗传算法的过程中，采用基于目标函数的数学建模方法，来决定该方法的适用范围。选择运算：通过选择运遗传模拟退火算法的优化研究萧秋兰1,2 （1 闽南科技学院计算机信息学院 福建 泉州 362332）（2 大数据与人工智能福建省高校重点实验室 福建 泉州 362332）【摘要】遗传算法和模拟退火算法都是以概率为基础的随机寻优方法。遗传算法采用群体爬山法进行搜索，搜索性能虽好，但爬坡性能不佳，且收敛性能不佳，很容易在局部优化中迷失。而模拟退火则将个别的个体视为最优目标，它的局部寻优效果更好，收敛速度更快，跳跃性更好，能够跳过最优的周期，但整体的寻优能力并不好。这两种方法既能克服彼此的不足，又能最大限度地利用它们的优势，从而防止局部最优化。为了解决遗传算法与模拟退火方法的不足，本文采用了遗传模拟退火方法。首先进行了遗传模拟退火的优化，其次对初始解构造、生成新解和求解周期进行了分析，最后用一个解析式实例 Jaeschks9 对该方法的初始解构造、生成和求解周期进行了详尽的阐述。【关键词】遗传模拟退火算法；优化设计；模拟仿真【中图分类号】TP39 【文献标识码】A 【文章编号】1009-5624（2022）12-0095-04DOI:10.16009/13-1295/tq.2022.12.05296 信息：理论与观点信息记录材料 2022年12月 第23卷第12期 算可以从现有群体中筛选到较高的亲本，高适应性的则有可能成为父系后代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）上预测到的所有权重 a1。通过在一个可接受水平下求得目标函数 g（x），本文则可以得到目标函数 g（x）由 n 个给定权重 a 组成：其中 j即为目标函数 g（x）在 n 个给定权重 a 下预测期望值 c 与期望值之差。然后，在遗传模拟退火算法中，本文需要根据原始种群进行选择与进化，以适应其无变异能力。在前一个步骤中，本文已经建立了一种初始种群，它是根据随机选择的遗传编码来建立的。在该阶段的初始种群选择过程中，本文需要考虑三个因素的影响：种群基因选择水平、子种群适应能力、随机选择进化。其中，种群基因选择水平是指从种群初始遗传因子 A 的角度来看，该种群可以作为一个随机个体被选择和进化。此时，如果有新遗传因子 A 作为初始因子，则可以使得种群遗传能力提高到 1。在个体适应能力、随机选择进化后将产生 1 3 个个体组成新种群。为了获得更好的进化效果，本文需要选择更多个体组成新种群。同时，当群体基因适应能力出现问题时（例如：低进化和高进化），子种群不会进化得更好，即子种群无法适应该群体中有新基因出现或者其进化得太快而不适应种群自身进化效率低时，将停止进化。因此，为了保持无变异能力并保持种群遗传能力不变，将会对一个群体中的所有个体进行选择和进化，从而获得更好的进化效果。通过对模拟退火算法的优化，本文提出了以下几点：在求解初始解时，使用遗传演算法中对染色体进行了编码，生成了初始群体，从而提高了模拟退火的平行查 97信息：理论与观点信息记录材料 2022年12月 第23卷第12期 找性能；在生成新的解决方案时，采用选择、交叉和变异等方法来生成新的方案，取代了模拟退火算法中的任意生成新的方案，通过对其进行优化，从而能快速地求出最好的结果。该方法无须经过大量的试验，就能得到更好的求解，从而减少了求解速度 q 的问题。该方法的流程表如图 1 所示。图 1 遗传模拟退火算法流程示意图3 遗传模拟退火算法流程分析3.1 初始解构造设计该方法包括构造初始解、生成新解、求解方法优化以及算法周期等。该方法首先从均衡速率大的问题（即初值）出发，寻求最优化问题，并为其设计出一种合适的初值结构。为了提高模拟退火方法的平行查找性能，本文提出了一种新的基于遗传算法的原始群体生成方法，将初始解的结构划分为编码、初始种群、合法解决和有效解决四个阶段。通过实例 Jaeschks9，对初解的构建过程进行了详细的阐述。特别在编码与生成初期人口的过程中，本文将问题进行了代码化，并将其转化为可由电脑辨识的资料，此问题则是流水作业的均衡问题，而代码是将作业交给了一个工作站，并将其转换为电脑所能辨识的资料，该资料被称作“染色体”。每一条链上的每一个点都代表着一个基因的价值，也就是一个序列。由若干个具有特定染色体的群体构成的群体，其染色体数就是群体的大小。在迭代过程中，最初的群体是首先生成的群体。在求解过程中，合理的解决方案是一个符合该模式的限制。在编写代码时，将任务放在了一个工作站上，不需要考虑到任务与任务的优先级，因此需要设计一个合适的优化方案来保证代码的优先级。在进行优化求解时，必须先决定每个问题的分布前后，然后再根据优先权来决定任务的分布。在此基础上，根据实例的任务优先级，分别求出各任务优先级，当各任务 i 的优先级大于各优先级的中位时，由前向后依次进行排序；在任务 i 的权重小于其优先权的中间位时，将 i 按从前到后依次进行排序。最优的输出解集就是从符合任务优先关系的原始群体的合理解中，选择最大的一个作为初始方案。3.2 新解产生在模拟退火中，由于新的求解是以一种随机生成的形式生成的，在此基础上，利用遗传算法中的“优胜劣汰”的概念，对新的求解方法进行选择运算、