基于学习机制的退火并行遗传算法：地下结构方法

对于基本的遗传算法而言，在给定的时间内可以搜索到问题的最好解，并且在大系统优化与控制中也已得到了初步的应用。但在实际求解大规模或超大规模问题时，基本的遗传算法往往还是会出现局部搜索不敏感及早熟收敛和最优解丢失等缺点。

因此，我们选择了基本遗传算法的改进算法并行遗传算法，在并行遗传算法的基础上进行改进。并行遗传算法在基本遗传算法的基础上引入多种群并行进化，并使用迁移算子进行种群间的信息交流，避免了基本遗传算法中出现的未成熟收敛。

模拟退火算法是由Metropolis等提出的，在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，使用串行结构，局部搜索能力强。由此，针对并行遗传算法中出现的局部搜索不敏感的问题，我们在并行的遗传算法中引入模拟退火算法的思想，采用并行和串行相合的两层结构，在整体构造上采用了粗粒度并行框架，增强了算法的全局搜索能力：局部搜索引入模拟退火算法思想作为并行遗传算法产生种群的变异算子，增强和补充了并行遗传算法的局部搜索能力。

此外，在综合了并行遗传算法与模拟退火算法的优点的同时，为了避免并行遗传算法搜索过程中出现最优解丢失的问题，新的混合优化策略（PGASA算法）还引入了机器学习原理，增加了种群的平均适值，有效地避免了最优解丢失的问题，加快了并行遗传算法的进化速度。

1.PGASA混合算法的基本思想

PGASA混合算法的设计主要针对并行遗传算法易早熟和局部搜索能力差的缺点进行改进，改进之处有以下三点：

（1）算法的整体构造采用并行搜索和串行搜索相结合的两层结构。

（2）模拟退火算法作为并行遗传算法产生种群的变异算子。

（3）引入机器学习原理构造初始种群的学习机制。

PGASA算法的执行分为并行搜索阶段、串行搜索阶段和种群迁移阶段。并行搜索阶段侧重于全局搜索，提高了种群的全局搜索能力；串行搜索阶段主要是增强算法的局部搜索能力，使算法能够跳出局部极小的“陷阱”；种群迁移阶段主要使种群能够朝着最佳方向迁移，提高了算法的收敛速度，其特点如下所述。

1）并行和串行结合的互补机制

由于并行遗传算法的全局收敛与种群多样性存在矛盾，所以全局搜索与局部搜索互相融合对算法的整体性能提高具有很大的作用。将种群分为多个子种群进行并行优化，通过选择对子种群进行最优个体保存，迁移算子进行种群间的信息交流，这是算法搜索的并行层次。在并行的框架中嵌入串行结构，对并行的子种群进行进化时将模拟退火算法嵌入并行遗传算法的框架中，两种机制互补。

2）串行层次局部微调

对于并行遗传算法而言，变异算子对种群多样性起着重要的作用。变异概率小，算法的收敛速率快，但是容易陷入局部极小：变异概率大，算法全局搜索能力强，但是收敛速率慢。单一遗传算法很难选取合适的变异参数，PGASA算法使用模拟退火算法作为并行遗传算法的变异算子，将基于概率突跳的Metropolis抽样过程混合到并行遗传算法中，可以起到概率可控的变异操作，降低算法对变异参数的依赖。变异外层在各温度下进行并行遗传算法的操作，内层对各子种群进行搜索，初始解来源于并行遗传算法的进化，模拟退火算法经Metropolis抽样过程得到的解又成为并行遗传算法进一步进化的初始种群。

控制初温可控制初始搜索行为，控制温度的高低可控制突跳能力的强弱，高温下的强突跳有利于避免陷入局部小，低温下的趋化性有利于提高局部搜索能力，控制降温速率可控制突跳能力的下降幅度，控制抽样次数可控制各温度下的搜索能力，避免了变异概率难以选取、并行遗传算法易早熟收敛的缺点。模拟退火算法的串行优化和并行遗传算法的群体并行相结合避免了基本遗传算法易早熟和局部搜索能力不强的缺点，增强了算法的全局和局部搜索能力。

3）机器学习引导种群的建立

PGASA算法引入机器学习原理，建立种群知识库，指导初始种群的建立，如图4-4所示。以往子种样的建立是随机进行的，有可能导致种群中大部分个体的适应度和最佳个体的适应度差别不大，降低了种群的多样性，导致早熟的发生。另外，随机选择容易造成最优解的丢失。知识库建立的合理性和信息存储的方式直接影响到信息的存储和提取速度，因此，建立一个合理的知识库，不仅能够提高数据的存储和提取速度，而且还能合理分配资源，减少资源耗费。

知识库的建立与更新如图4-4所示，下面对图4-4做简要说明。

1）初始种群库用来存储各种工況下最后一次迭代所产生的染色体群，由于遗传算法的整体进化性，使得最后一次迭代产生染色体群的平均适值是最优的，将这一结果记录下来，当再次进行优化计算时，可以将存储过的染色体群的全部或一部分用做初始种群的一部分，这样可以使初始种群有一个较高的平均适值，从而能够有效地减少进化次数。

2）索引库将每次迭代后产生的种群划分为若干类，记录分类索引号。每类中平均适值较高的将作用在不同子种群上的交叉操作产生的所有新个体与父代种群进行整体择优筛选，从而加速种群的进化过程。

图4-4　建立种群知识库的流程

3）优化结果库用来存储每次优化计算后所得到的最优解。这样，当再次遇到相同工况时可以直接检索到最优结果。(www.xing528.com)

4）知识库的更新将每次优化后的结果存入知识库，知识库内的记录会快速增长，为了提高知识库的检索效率，对知识库内的数据动态进行更新。每次检索知识库时，对于工艺参数和工艺约束相同的记录，如果当前种群的适值f大于知识库中的种群适值，则删除知识库中的原记录，并将当前记录存入知识库。这样，可以保持知识库内的个体适值比较高，同时可以控制知识库的规模，提高知识库的处理速度。

2.混合算法流程与优点

混合算法总体框架如图4-5所示。

图4-5　混合算法总体框架

混合算法流程的执行步骤如下。

步骤1：针对车间调度的问题初始化参数，编码采用Gen等提出的基于工序的编码方法。初始种群从知识库随机抽取一部分染色体，用随机生成的编码链的算法生成初始群体另一半个体的染色体编码串。

步骤2：划分成n个并行的子种群，并计算每个子种群的适应值。在求解车间调度问题时，利用加工系统最小完成时间作为衡量标准。

步骤3：判断收敛准则是否满足。以最大进化代数为终止准则，对车间调度问题使用最大进化代数作为工件数与机器数的乘积。如果满足收敛准则，则转到步骤11。

步骤4：对每个子种群进行独立进化，基于子种群进行遗传选择操作。

步骤5：对每个子种群进行交叉操作，保留优良个体。

步骤6：对每个子种群中的个体进行变异操作，保留最佳个体并划分为n个子种群作为SA的初始种群，同时进行种群更新和知识库更新，存储最优状态和温度调节参数。

步骤7：对n个子种群的个体进行定步长抽样的模拟退火操作，以概率min{l，exp[-ΔE/（tk）]}接受后代，更新种群和知识库（其中，ΔE是能量变迁的差值，t是温度，k为玻耳兹曼常数）。

步骤8：进行退温操作tk←λtk-1，λ∈（0，1）。

步骤9：计算种样间的亮争力。

步骤10：各子种群如果获得了比种群i中个体更好的个体，则用人工选择操作更新i中较差的个体，然后在子种样个体中再进行迁移替换。转到步骤3。

步骤11：将部分最优解存入知识库，并输出最优解。

3.算法的优点

1）在遗传算法的整体构造上使用并行框架，加速了遗传算法的搜索过程，而且能够增加种群的多样性，抑制早熟的发生，从而提高解的质量。

2）引入了机器学习原理，将先前优化过的工艺流程存储起来，当再次遇到相同工况时，可以通过査询数据库直接获取结果，从而避免了重复计算，这一点对于大型的复杂优化问题特別有利。如果对当前查询结果不满意，可以将当前最优解和先前存储的种群中各抽取部分个体作为初始种群中的一部分，其余个体随机生成，这样既保证了初始种群的多样化，同时也使初始种群保持了较高的平均适值，使得优化迭代次数大大减小。

3）模拟退火算法的引入，克服了遗传算法爬山能力弱的特点，结合了遗传样体进化和模拟退火算法具有较强的避免迂回搜索的特点，实现了快速的全局优化。

模拟退火算法来源于固体退火原理，即将固体加温至充分高，再让其徐徐冷却，是近年来应用比较广泛的智能优化算法之一，具有算法简单、并行性、善于搜索复杂区域的优点。本章主要介绍了一种改进的遗传算法和基于学习机制的退火并行遗传算法，前者引入了机器学习原理，并将模拟退火算法中的Metropoli抽样过程与遗传算法相结合，可以较快地找到高质量的近似解；后者在并行遗传退火混合算法中引入学习机制，有效避免了算法中期易出现的未成熟收敛情况。

应用神经网路系统进行工程结构优化，可通过电子电路模拟或计算仿真求解。由于一般的神经网络系统具有有限个渐近稳定平衡点，也就是说，系统能量函数具有有限个局部极小点。为了获得全局最优（或虽非最优，但所希望的较优）解，可采用模拟退火法。