《1 前言》

1 前言

随着计算机技术的发展,生物智能、人工智能、计算智能间相互增强,构成了能力更为有效的智能技术,如把单一的计算方法相互融合构成复合的计算方法,以避免其固有缺点,萃取各自优点的目的。

遗传算法在仿真中有其通用性,对领域的依赖性程度低,不受搜索空间限制性假设约束,不要求连续性、可导或单峰等,被广泛应用,但同时存在收敛效率低、过早收敛等缺点,而退火算法正好以局部搜索能力见长。将退火算法与遗传算法融合,使算法得到改进,利用退火算法中局部搜索最优值的较好能力解决了遗传算法中局部搜索能力不佳带来的问题。

《2 算法分析》

2 算法分析

《2.1 遗传算法的理论》

2.1 遗传算法的理论

遗传算法[1]是一种借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适应搜索算法。它是由复制、杂交和变异三种算子组成。遗传算法的优越性主要在搜索过程中不易陷入局部最优,求解过程不需要求导,由于它固有的并行性,遗传算法适用于大规模并行计算。遗传算法中关键的算法靠复制、杂交和变异三种算子来完成,完全依赖于运算速度,而对数学方法依赖性不高。

遗传算法较适合于传统搜索方法所不能解决的复杂问题和非线性问题。然而,实际应用中遗传算法存在编码、迭代次数、种群规模的限制,造成强选择性压力,导致遗传搜索过早收敛。

《2.2 退火算法》

2.2 退火算法

模拟退火算法[2]来源于固体退火原理。用固体退火模拟组合优化问题,将内能 模拟为目标函数值,温度演化成控制参数 t,即得到解决组合优化问题的模拟退火算法:由初始解 和控制参数初值 开始,对当前解重复“产生新解 → 计算目标函数差 → 接受或舍弃”的迭代,并逐步衰减 t  值,算法终止时的当前解即为所得近似最优解。退火过程由冷却进度表(cooling schedule)控制,包括控制参数的初值 t  及其衰减因子 Δt、每个 t  值时的迭代次数 L 和停止条件

《3 遗传算法与退火算法融合》

3 遗传算法与退火算法融合

通过遗传算法与退火算法的分析,把其各自的优良特性保留下来,得到改进的遗传算法即退火 - 遗传算法。过程如下:

Step 1 给定群体规模 N - size 和算法中其他系数值,选择初温时的系数 T0,退温时系数 a,交叉和变异操作时的系数 PcPm 和终止规则 q,令迭代计数器 k =0;

Step 2 随机产生 N - size 个染色体作为初始种群 N0,计算各染色体的目标函数值,确定初温,令初始最优解 S =Jmin,并令终止累加计数器 p = 0;

Step 3 计算染色体的适应函数值 fxi ),实施最优保留策略;

Step 4 重新计算染色体的目标函数值,按交叉概率 Pc 与变异概率 Pm 执行遗传算法的交叉操作,分别实施最优保留策略;

Step 5 执行基于 Metropolis 判别准则的复制策略,产生下代群体 Nk+1

Step 6 执行退温操作,令 Tk+1 = βTkk = k +1;

Step 7 计算出新一代群体的目标函数值,令 S′ = Jmin

Step 8 判断 S′  是否小于 S,如果为真,令 S = S′p = 0,否则 p = p +1;

Step 9 判断 p 是否大于或等于 q,如果是,则以 S  作为最终解输出并停止计算。否则,返回 Step 3。

对算法过程描述如下:

1)初始种群产生。随机产生 N - size 个长度 ll 为生料配比三率值———石灰石饱和系数 Kh、硅率 n 和铝率 P)的染色体作为初始种群,每一个染色体内为生料号的一个随机序列。

2)初温的确定及退温操作。初温的确定选择 T0Nδ 的形式,其中 N 为充分大的数,可以选试验值 N = 500;δ = JmaxJminJmax 为初始种群中最大的目标函数值(期望的配比三率值),Jmin 为初始种群中最小的目标函数值。退温函数选用常用的 Tk+1 = βTk 形式,其中 0 <β<1。

3)适应函数。适应值是构造遗传算法中的关键,在搜索过程的收敛速度中起着至关重要的作用,这里定义适应函数为 fxi ) = α(1 - αi-1i = 1,2,…,N - size。式中 xi 为种群排序后第 i  个个体;α 为系数,为保持样本多样性取 α = 0.01 ~ 0.03。

4)选择算子。采用比例选择算子,该算子是一种回放式随机采样的方法,以旋转赌轮 N - size 次为基础,每次旋转都可选择一个进入子代种群。父代个体 xi  被选择的概率

5)交叉、变异算子。采用贪心交叉算子,即在个体编码串中随机设置一个交叉点,在两个父代个体中以该交叉点分别向右和向左搜索,找到与前一个个体较小三率值的编码时,则将该编码加入子代。

6)新个体复制策略。以经过遗传算法选择复制、交叉、变异操作的群体作为初始群体,运用基于 Metropolis 判别准则的复制策略[3],产生下一代群体。首先实施最优保留策略,然后在染色体 i  的领域中随机产生新个体 ji j 竞争进入下一代。令 Δf =fxj)- fxi),若 Δf <0,则把 xj  复制到下一代群体,否则以 exp ( -Δ/Tk ) >random [ 0,1 ]作为复制 xj  到下一代群体的条件。

7)终止规则。通过监控进化群体中最小目标函数值 Jmin 的变化情况来判断算法是否终止。当连续 q 代没有发生变化时,即可认为算法收敛并终止算法。

这种算法不需要特殊的选择方法,减轻了原有遗传算法的选择压力。交叉操作是遗传算法中的主要因子,寻优过程主要通过它来实现,退火遗传算法吸取了这一思想,对所选交叉个体均实施交叉操作,并且把交叉和变异后的子代同父代竞争,通过 Bolt-zmann 机制来接收子代,不但有利于优良个体的保留,同时防止了早熟收敛的问题。随着进化过程的进行,温度逐渐下降,接收劣质解的概率也逐渐减小,有效地利用了遗传算法的爬山特性,提高了算法的收敛速度。

《4 仿真实例》

4 仿真实例

为评价退火遗传算法的性能好坏,仿真实例验证水泥生料配比,水泥的熟料三率值:石灰石饱和系数 Kh、硅率 n 和铝率 P,这三个值决定了水泥的质量与经济效益。采用了文献 [4] 中所提供的原料、粉煤灰等数据,沿用其目标函数、评价函数,并以退火 -遗传算法的过程步骤和结果与文献 [4] 的遗传算法结果进行对比,依此考察其效果。

目标函数为

J = w1KhiKh02 + w2ni  -  n02 + w3 Pi - P02

与文献[4]中相同。其最优形式为

min (J) = min (w1Khi - Kh02 + w2ni  - n02 + w3Pi  - P02 ),

其中 w1w2w3 为加权系数;Khini ,Pi  为各基因串对应的三率值;Kh0n0P0 为期望的三率值。

熟料窑热耗为 4.6 MJ/kg,实际的熟料三率值(i = r 时):Khr = 0.87 ± 0.01,nr = 2.2 ± 0.1,Pr = 1.1 ± 0.1。对于目标函数,算法的全局收敛性尤其重要。退火 -遗传算法与遗传算法的控制参数如表 1。

《表1》

表1 控制参数

Table 1 controls parameter

考虑它们的平均求解特性。由于在文献 [4] 中未说明计算运行次数,故在计算中同时列出了遗传算法在 800 次和 2 700 次运算后的运算结果,以此与改进的计算结果对比,计算见表 2。

《表2》

表2 仿真结果对比

Table 2 simulation result contrast

注: 1,3 循环 800 次;2 循环 2 700 次;4 循环 1 000 次;第一行是文献 [4] 中的计算结果。

结果表明,文献 [4] 中的结果非常接近于遗传算法的 2 700 次运算的结果,同时与退火 -遗传算法运算 800 次和 1 000 次的结果误差也相差无几。这说明,改进的遗传算法大大减少了运算的次数,加快了运算的速度,同时,改进的遗传算法替代遗传算法节省了时间,并不失其原有的并行、非线性计算等优良特性。

《5 结语》

5 结语

通过将模拟退火的思想引入遗传算法,使得遗传算法的性能得到了改善,增强了进化算法的全局收敛性,并且使算法在进化后期有较强的爬山性能,加快了算法的收敛速度。此外,对水泥配比计算的对比,改进的遗传算法对速度及精确度都有很大的提高。此方法可以推广到其他行业的选料配比计算中,具有工程应用价值。