改进的遗传退火算法在地下结构方法中的应用

在大量的求解大规模问题的实际应用中，传统的单一的搜索优化算法得到的优化结果往往不够理想，对多种算法进行混合的思想已经逐渐成为提高传统算法优化性能的一个重要且有效的途径。

遗传算法是基于适者生存的一种高度并行、随机和自适应的优化算法，在一定条件下具有全局收敛特性，并已广泛应用于机器学习、控制、优化等领域。但对于基本的遗传算法而言，在实际应用时，往往会出现早熟收敛和收敛性能差等缺点。

模拟退火算法是在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解。但对于基本的模拟退火算法而言，在实际应用中，当问题规模不可避免地增大时，返回一个高质量的近似解的时间花费将难以承受。

为了避免基本遗传算法和基本模拟退火算法的缺点，综合二者的优点，产生了一种新的混合优化策略—改进的遗传退火算法（Modified Genetic Algorithm and Simulated Annealing，MGASA）。MGASA算法不仅对基本遗传算法和基木模拟退火算法进行了算法思想融合，还引入了机器学习原理，引入模拟退火算法作为遗传算法中的种群变异算子，并将模拟退火算法中的Metropolis抽样过程与遗传算法相结合，不仅充分发挥了遗传算法并行搜索能力强的特点，而且增强和改进了遗传算法的进化能力：另外，利用机器学习原理来指导种群的建立，使优化过程在很短时间内获得最优解，提高了系统的收敛性能和收敛速度；同时，利用机器学习的记忆功能，避免了最优解的丢失。

1.MGASA算法思想介绍

1）MGASA算法的基本框架

MGASA算法综合了遗传算法的全局并行搜索能力强和模拟退火算法的局部串行搜索能力强的特点，采用并行和串行相结合的结构。外层在模拟退火算法产生的各个温度下进行遗传算法的操作，内层对各子种群进行搜索，初始解来源于遗传算法中的进化，模拟退火算法经Metropolis抽样过程得到的解又成为遗传算法中进行下一步进化时的初始种群。这样的框架结构有效地避免了遗传算法易早熟和局部搜索能力不强的缺点，增强了算法的全局和局部搜索能力。

2）知识库的建立

知识库建立的合理性和信息的存储方式直接影响到信息的存储和提取速率，因此，建立一个合理的知识库，不仅能够提高数据的存储和提取速率，还能够合理分配资源，减少资源耗费。

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

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

（3）优化结果库。用来存储每次遗传算法优化计算后所得到的温度调节参数和最优解，以使再次遇到相同工况时可以直接检索到最优结果。

3）机器学习过程

基本遗传算法中选取的初始种群的好坏及多样性，将会影响基本遗传算法的迭代次数和是否能达到最优解。根据这一特点，我们首先使用机器学习的方法来为遗传算法产生一部分初始群体，再利用随机产生的方式为遗传算法产生另一部分的初始群体，以此来提高初始群体的适应性和多样性，加快进化过程。此外，我们还将机器学习的方法加入到遗传交叉和变异中，即在遗传交叉和变异结束后使用机器学习的分类操作，将种群划分为若干类，作为模拟退火操作的初始种群。

4）学习记忆功能

Metropolis等人在1953年提出的采样法就是以一定概率接受新产生的状态作为当前状态，即模拟退火算法中使用的Metropolis接受准则，在温度t下，由当前状态i产生新状态j，二者的能量分別为Ei和Ej。若Ej＜Ei，则接受新状态j为当前状态；否则，若概率pr=exp[-（Ej-Ei）/（kt）]大于[0，1]间内的随机数，则仍旧接受新状态为当前状态，若不成立，则保留状态i为当前状态，其中k为玻耳兹曼常数。然而，在搜索过程中执行etropolis概率接受准则时，不可避免地会遗失最优解。因此，MGASA算法引入机器学习方法中的记忆功能，将产生过的最优解存入知识库，在搜索过程中首先进行知识库的査询，以此来避免最优解的丢失，提高进化能力。

5）模拟退火算法中的Metropolis抽样与遗传算法的混合

将模拟退火算法中的基于概率突跳的Metropolis抽样过程混合到遗传算法中，可以对遗传算法中的变异操作进行概率控制操作，并可以通过模拟退火算法中的控制初温的操作来控制遗传算法初始搜索的行为；控制温度的高低可以控制突跳能力的强弱，高温下的强突跳有利于避免陷入局部极小，低温下的趋化性有利于提高局部搜索能力；控制降温速率可控制突跳能力的下降幅度；控制抽样次数可控制各温度下的搜索能力，避免了变异概率难以选取且克服了基本遗传算法易早熟收敛的缺点。

2.改进的算法流程(www.xing528.com)

改进的算法流程如图4-3所示。

步骤1：初始化算法参数。初温t=t0，退温速率为λ，k=0。

步骤2：搜索知识库，判断是否有符合条件的最优解和初始种群。若有，则调用部分初始种群，并随机生成另一部分，然后从数据库中调用最优解：否则，随机生成初始种群。

步骤3：评价当前种群的个体。

步骤4：判断算法的收敛准则。如果满足，则转到步骤9：否则，转到步骤5。

步骤5：随机选择个体与种群中的最优个体进行交叉操作，产生新个体。如果新个体适值优于当前最优解，则进行种群更新：否则，保留当前种群和最优解并分类存储到知识库。

图4-3　改进算法流程

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

步骤7：对n个子种群的个体进行定步长抽样的模拟退火操作，以概率min[l，exp（-ΔE/（tk））]接受后代，更新种群和知识阵库。

步骤8：进行退温操作tk=λ·tk-1，λ∈（0，1），转到步骤4。

步骤9：输出本次优化结果。

步骤10：判断是否再次进行优化，若是则转到步骤2；否则，转到步骤11。

步骤11：输出最终优化结果。

3.算法的优点

MGASA的优点如下：

（1）增强了搜索效率。MGASA既具有基本遗传算法所具有的全局并行搜索能力，又具有模拟退火算法所具有的局部集中搜索能力，可以跳出局部极小。

（2）机器学习原理的引入。引入机器学习原理，将先前优化过的工艺流程存储起来，当再次遇到相同工況时，可以通过査询数据库直接获取结果，避免了重复计算，提高了算法的进化速度。如果对当前査询结果不满意，可以从先前存储的种群中抽取部分个体作为初始种群中的一部分，其余个体随机生成，既保证了初始种群的多样化，也使初始种群保持了较高的平均适值，使得优化迭代次数大大减少。

（3）增强进化能力。将最优解存入知识库，在搜索过程中首先查询知识库，避免了最优解的丢失，提高了进化能力。