自适应遗传算法

自适应遗传算法

该文主要介绍了自适应遗传算法的基本原理及其应用实例分析。作为基于生物进化的优化工具，在进行函数全局搜索时具有不易陷入局部最小值的能力，并能有效避免传统迭代方法所面临的循环问题。本文着重阐述了自适应遗传算法的核心机理及其实证研究过程。具体而言，在其理论基础部分，则系统阐述了该算法的主要组成部分：编码机制、解码过程、交叉操作、变异处理以及选择策略等环节中最为关键的是交叉与变异操作的作用机制。为了提高算法性能，在实现过程中采用了动态调整交配与变异概率的方式来实现

遗传算法最初由Holland提出，旨在通过通过自然系统的自适应行为来设计具有自适应功能的软件系统，该方法属于进化算法的一种。遗传算法通过对函数自变量范围进行基因编码、交配、基因变异、计算函数适应度值、选择较优值到下一代、种群繁殖后重复上述操作的方法，逐渐逼近最优值。自适应遗传算法通过改变不同适应度值下的交叉和变异几率，能提升计算效率并加快算法的收敛速度。
1.自适应遗传算法的实现步骤
（1）编码
编码是用一组有序数列来表征自变量，类似于基因来表征一个生物。只不过不同于自然界中的生物，自然界中大部分生物的基因是双链，而在算法计算中自变量的基因是单链，这样便于表征、杂交和变异。
编码按代码数制类型不同主要分为二进制编码和十进制编码，二进制编码格式整齐，易于理解；但十进制编码容易观察且不用数制转换，故本文采用十进制数编码。例如对于自变量x∈(a , b)（其中a , b为给定的自变量区间，且b ＞ a），可将（b - a）分为（ ≥2）份，每个数字用一个（ ≥2）位数字序列表示，这个数字序列即为基因编码。
（2）解码
解码是运算过程中需要将基因反变换成自变量的实际大小进行处理而进行的编码还原，即基因乘以解码器即可将基因转化为实际数值。对于上例中的编码，解码器选择如下：

（3）交配（也叫交叉）
交配是基因之间以一定几率相互交叉而改变原来的序列。方法如下：
设初始种群中随机产生了两个基因分别为：
![（，，……，） 初始个体1

其中 初始个体

用轮盘法则随机确定一个1到之间的整数（1＜＜）作为交叉位数，然后交换该整数位以后的数字，交叉后的基因分别如下：
![（，，……，，，……，） 交配后个体1

（, , …, , , …,）经过交配处理后的个体O_{\text{individual}+}

交配是遗传算法区别于其他算法的主要特征之一，交配效果也直接影响算法结果的有效性。交配概率太大会破坏种群现有结构，丢失优异个体；交配概率太小种群进化较慢，收敛速度慢，不易找到最优解。虽然传统的遗传算法根据大量实例给出一个经验值范围0.4-0.99，但显然任何一个固定的交配值都是不公平的。一个适应度大的个体应该尽可能地保留到下一代，而一个适应度小的个体应想法重复利用，否则在筛选中依然会被筛选掉，从而丢失一部分计算价值。所以基于此想法，研究人员提出了自适应交配方法，即根据适应度的大小自动调节交配几率，具体方法如下：
对于任意一代的种群中，优先算出该种群的平均适应度和最大适应度，通过-构建自适应指标。当判断任意个体时，计算该个体的适应度f后，通过公式
![（-f）/（-） f≥

= （2.2）

#链接至该平台

其中为该个体的自适应交叉概率；一般令=1，即适应度小于平均值的个体直接交叉；初始时可取0.5，根据寻优结果另行调整。
（4）变异
变异类似于基因突变，即在个体交叉过程中或交叉后某个数字产生随机变化，这种变化类似于生物体的基因突变，因此叫变异。
变异性质跟交叉相似，是遗传算法另一个重要特征，而且对种群进化影响很大。变异概率太小时，种群多样性下降迅速，容易导致有效基因的迅速丢失且不易修补；当变异概率太大时，会增加种群多样性，但是对种群现有结构破坏较大。因此，选择合适的变异概率，可以增加遗传算法的有效性。
![（-f）/（-） f≥

= （2.3）

f＜](https://ad.itadn.com/c/weblog/blog-img/images/2024-12-09/3jgiLXNPuxTQ7h51qkmbtoHWZY9f.png)

其中为该个体的自适应变异概率；一般设定=1作为适应度阈值；初始时可取=0.5，并根据优化结果进行相应调整。
（5）选择
选择是遗传算法中的关键步骤之一，在进化算法中也是一项普遍应用的操作方式。其基本原理是将当前种群与上一代种群合并后，依据各体的适应度函数值大小筛选出表现更为优秀的子代进入下一轮繁殖过程。这一过程模拟了自然界中适者生存的基本法则。本文采用了轮盘赌法则来进行个体的选择。
自适应遗传算法的程序流程图如图1所示。

图1 自适应遗传算法的程序框图
2.验证自适应遗传算法
用自适应遗传算法求约束优化问题
![max \(\)=0.5-\( -0.5)/

s.t. -4≤\(\)=≤4

在约束条件下寻求最优解的问题中，请注意以下参数设置：将初始种群数量设定为N=100，并选择繁殖代数G=200次；设定交叉概率为1.0以及变异概率为0.5；限定自变量范围在区间[-4, 4]之间；基因编码长度取值范围限定在（1,9）区间内，并且基因位点数目D=2个。
(1) 编程实现
随后对自变量区域实施基因编辑操作，并将编辑后的基因序列如下：

其中i=1,2,…,100, 生成的随机数取值范围在1至10之间，并作为对应自变量序列使用。
基于交配、变异和选择三个基本步骤进行编码实现, 具体实现过程见附件中的Matlab程序。
（2）结果分析
函数的三维曲面图形及等高线分布如图2、图3所示，
图形顶端最高点坐标标注为(0, 0, 1)，并通过该特征对算法有效性进行验证。

图2 图3
采用自适应遗传算法进行计算，在本研究中生成了初始种群如图4所示；其中自变量覆盖了整个搜索空间，并且物种多样性较高。随着时间推进，在函数搜索空间中逐渐向适应度最大值区域靠拢的状态下进行评估；而每个个体都在向最优个体靠拢的状态下进行评估，并呈现出逐步趋同的趋势；此外通过对比适应度曲线的变化趋势可以看出该算法具有良好的收敛性。经过200次迭代后，在图5中展示了变量分布情况；从图形中可以看到经过进化后种群位置集中在函数最大值附近；此时函数的最大值点坐标确定为（x, y, z）=（0.000027467, 0.000031419, 1），与理论上的精确解（0, 1）非常接近；并且计算所得的最大误差限仅为约 3.14%。

图4 初始种群变量分布图 图5 迭代200次变量分布图

图6显示了适应度曲线的变化趋势 图7则描绘了最大与平均适应度差值随迭代次数的变化情况
4. 结论
对于一般约束优化问题而言,自适应遗传算法展现出良好的收敛速度和较高的精度,能够迅速逼近全局最优解.其在工程应用中具有广泛的适用性,特别适用于对复杂工况的优化计算,对于提高计算效率和结果可靠性均具有重要的参考价值.

自适应遗传算法程序如下：

参数设置------------------------------------------------------------------------------------------

初始种群生成-------------------------------------------------------------------------------------

结果保存------------------------------------------------------------------------------------------

图形绘制------------------------------------------------------------------------------------------

     scatter(x(:,1), x(:, 2));
    axis([-4, 4, -4, 4]);
    title(['第', num2str(gen), '次迭代']);xlabel('变量X'); ylabel('变量Y');
    base_path = 'D:\Program Files\MATLAB\R2016a\bin\genetic algorithm\zi_shi_ying';
    cnt = num2str(save_pic_cnt);%数字转化为字符串
    tail_path = '.jpg';
    frame = getframe(A);%将绘图捕捉为电影帧，每帧保存一个列向量
    im=frame2im(frame);
    path_img = [base_path, cnt, tail_path];%D:\Program Files\MATLAB\R2016a
    ...bin\genetic algorithm\zi_shi_ying50.jpg，即文件位置+文件名+格式
    % imwrite(im, path_img);
    % save_x(:, :, save_pic_cnt) = x;
    save_pic_cnt = save_pic_cnt + 1;%帧数累加，共50次
    end
    for count_2=1:NP
    fitness(count_2)=func(x(count_2,:), mode);%每代中每个个体对应z值
    end
    fitness_ = fitness;
    %[fitness_min,index0] = min(fitness);
    %fitness_max = max(fitness);
    [fitness_max,index0] = max(fitness);%返回所有个体产生的z值的最大值
    fitness_average = sum(fitness)/(length(fitness));  %每代种群中个体的平均z值
    collect_fit_average(gen) = fitness_average;   % 保存每代中得到的平均适应度
    collect_fitmax_subtract_fit_average(gen) = fitness_max - fitness_average;
    fitness_min = min(fitness);%最小z值
    best_indiv = x(index0,:);  % 每代个体中最优的个体即为第index0行的行向量
    best_solution(gen) = fitness_max;%每代对应的最优解即为最大z值
    % 计算归一化的适应度值---------------------------------------------------------------------
    fitness = (fitness - fitness_min)/(fitness_max - fitness_min);%此时最大值变为1
    fitness_sum = sum(fitness);%相对适应度的和
    fitness = fitness./fitness_sum;%相对适应度/适应度和
    fitness = cumsum(fitness);%从前向后累加，最后一个值为100/100  
    % 轮盘赌选择-----------------------------------------------------------------------------------
    newi = 1;
    while newi<=NP  %每代都会随机选择一个符合要求的新个体，共100个
    random_num = rand();   % 生成随机数
    if random_num<fitness(1)%random小于随机生成的第一个z值的相对适应度
        clone_x(newi, :) = x(1, :);
        newi = newi+1;
    else
        for ct=1:(NP-1) %1:99
            if random_num>fitness(ct) && random_num<fitness(ct+1)
                clone_x(newi,:) = x(ct,:);
                newi = newi+1;
                break;  %跳出for循环，输出newi并继续进行while循环
            end
        end
    end
    end  %对应while
    % disp(clone_x - x);

实施交叉变异策略----------------------------------------------------------------