在这里插入图片描述

作者:非妃是公主
专栏:《智能优化算法》
博客地址https://blog.csdn.net/myf_666
个性签:顺境不惰,逆境不馁,以心制境,万事可成。——曾国藩
在这里插入图片描述

专栏推荐

专栏名称专栏地址
软件工程专栏——软件工程
计算机图形学 专栏——计算机图形学
操作系统专栏——操作系统
软件测试专栏——软件测试
机器学习专栏——机器学习
数据库专栏——数据库
算法专栏——算法

遗传算法也是一种效果很棒的智能优化算法,它主要借鉴了自然界中生物进化的思想,采用优胜劣汰的策略,利用选择、交叉、变异三个过程,对解进行不断的迭代,最终趋向于最优解。


一、生物进化

谈到遗传算法,不得不谈生物进化,因为遗传算法就是模仿生物繁殖后代的思想演变而来的,可以说是一种仿生学的算法。

自然选择学说认为,适者生存,生物想要存活下去,就必须进行生存斗争。生存斗争包括种内、种间以及生物和环境之间的斗争三个方面。

在斗争过程中,具有有利变异的个体容易存活下来,并且有更多的机会将有利变异传递给后代;具有不利变异的个体就容易被淘汰,产生后代的机会也就少得多。因此,凡是在生存斗争中获胜的个体都是对环境适应性比较强的个体。达尔文把这种在生存斗争中适者生存,不适者淘汰的过程叫做自然选择。1


二、遗传算法原理

而遗传算法就是借鉴了上述生物进化中的优化策略,对一个目标问题进行优化的。

具体地说,它将问题的解抽象成一个编码,许多个编码构成了一个种群,每个编码都对应得到目标问题的一个解,其中根据可行解的目标函数值的不同,定义这个个体的强弱。越强的个体越容易生存下来(选择),进行后代的繁衍(交叉、变异),越弱的个体就优先被淘汰。

生物进化中的术语遗传算法中的术语
群体可行解集
个体可行解
染色体可行解的编码
基因可行解编码中的一位(1个bit)
适应度评价函数值(越高,代表解越好)
选择选择操作(比如根据概率进行轮盘赌选择可行解)
交叉交叉操作(编码的单点交叉、多点交叉)
变异变异操作(编码的按位取反)

三、遗传算法的优点

  1. 以决策变量的编码作为运算对象。这种编码的方式对于计算机来求解十分方便,具有独特的优越性。
  2. 遗传算法以目标函数值作为搜索信息,避免了求导。在很多问题中,求导是无法做到的或者很困难做到的。
  3. 选择、交叉、变异操作包括了很多群体信息。这些信息避免搜索了许多的点,相当于具有一种隐含的并行性。
  4. 遗传算法基于概率。随着过程的进化,参数对搜索结果的影响很小很小。
  5. 具有自组织、自适应、自学习等特性。

四、算法具体流程

1. 整体流程

  1. 初始化;
  2. 个体评价;
  3. 选择运算;
  4. 交叉运算;
  5. 变异运算;
  6. 终止条件判断。

流程图如下:

no
yes
初始化种群
适应度评价
是否结束
选择运算
交叉运算
变异运算
结束

2. 细节处理

Ⅰ. 群体规模 N P NP NP

群体规模影响遗传优化的最终结果以及遗传算法的执行效率。一般 NP取10~200。

  • N P NP NP 太小时,遗传优化效果(相比于最优解准确度)一般不会太好。
  • 较大的群体规模可以减小陷入局部最优解的概率,但意味着较大的计算复杂度。

Ⅱ. 交叉概率 P c P_c Pc

交叉概率 P c P_c Pc控制着交叉操作的频率,较大的频率可以曾倩遗传算法开辟新的搜索区域的能力。

  • 如果太大,容易生成不好的后代,收敛性差;
  • 如果太小,搜索能力差。

Ⅲ. 变异概率 P m P_m Pm

保持群体多样性。一般去0.001~0.1

  • 太大,容易陷入随机搜索,导致重要基因丢失。
  • 太小,没有效果。

3. 遗传运算终止代数 G G G

一般视具体问题而定,取值可在 100~1000 之间。

  • 太大,浪费算力,种群衰退。
  • 太小,优化过程没有收敛。

五、仿真实例:求解函数最大值

1. 题目

用标准遗传算法求函数 f ( x ) = x + 10 s i n ( 5 x + 7 c o s ( 4 x ) f( x ) =x+10sin(5x +7cos(4x) f(x)=x+10sin(5x+7cos(4x)的最大值,其中的取值范围为 [ 0 , 10 ] [0,10] [010]


2. 分析

通过matlab作图可知,该函数存在多个局部极值,如下图所示:
在这里插入图片描述

  1. 初始化种群NP=50,染色体编码长度L=20,最大进化代数G=50,交叉概率为 P c = 0.8 P_c=0.8 Pc=0.8,变异概率为 P m = 0.1 P_m=0.1 Pm=0.1
  2. 产生初始种群,将二进制编码转换成十进制,计算个体适应度值,并进行归一化;采用基于轮盘赌的选择操作、基于概率的交叉和变异操作产生新的种群,并把历代的最优个体保留在新种群中,进行下一步的遗传操作。
  3. 判断是否满足终止条件。满足,结束;不满足,继续迭代。

3. matlab求解

matlab求解代码如下,其中主要思路及较为复杂的点,已在注释中说明。

%%%%%%%%%%%%%%%%%%%%标准遗传算法求函数极值%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%初始化参数%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;              %清除所有变量
close all;              %清图
clc;                    %清屏
NP=50;                  %种群数量
L=20;                   %二进制数串长度
Pc=0.8;                 %交叉率
Pm=0.1;                 %变异率
G=100;                  %最大遗传代数
Xs=10;                  %上限
Xx=0;                   %下限
f=randi([0,1],NP,L);        %随机获得初始种群
finalMax=0;
finalXBest=0;
%%%%%%%%%%%%%%%%%%%%%%%%%遗传算法循环%%%%%%%%%%%%%%%%%%%%%%%%
for k=1:G % 跌代的总代数
    %%%%%%%%%%%%将二进制解码为定义域范围内十进制%%%%%%%%%%%%%%
    for i=1:NP    % 遍历所有个体
        U=f(i,:); % 将第 i 个个体读取出来
        m=0;      % 存储的二进制对应的十进制数字
        for j=1:L % 按位把二进制转化为十进制
            m=U(j)*2^(j-1)+m;
        end
        x(i)=Xx+m*(Xs-Xx)/(2^L-1); % 把十进制数字m转换到对应的定义域内
        Fit(i)= func1(x(i));       % 计算适应度函数
    end
    maxFit=max(Fit);           %最大值

    minFit=min(Fit);           %最小值
    rr=find(Fit==maxFit);      %找出最优个体的下标索引
    fBest=f(rr(1,1),:);        %当代最优个体的二进制编码
    xBest=x(rr(1,1));          %当代最优个体对应的十进制值
    if maxFit>finalMax
        finalMax=maxFit;
        finalXBest=xBest;
    end
    Fit=(Fit-minFit)/(maxFit-minFit);  %归一化适应度值
    %%%%%%%%%%%%%%%%%%基于轮盘赌的选择操作%%%%%%%%%%%%%%%%%%%
    sum_Fit=sum(Fit);          %对所有个体的适应度进行一个求和
    fitvalue=Fit./sum_Fit;     %让所有个体加起来适应度值为1,便于进行概率计算
    fitvalue=cumsum(fitvalue); %consum是累加当前索引及以前的索引对应的值,比如[1 2 3],consume后返回[1 3 6]
    ms=sort(rand(NP,1));       %生成一个NP * 1的向量,并从小到大排序,轮盘赌的关键操作。(均匀分布)
    fiti=1;
    newi=1;
    while newi<=NP                   % 这个while循环是轮盘赌的精髓,如果适应度(存活概率)越大的个体,随机数越容易连续着比他小
        if (ms(newi))<fitvalue(fiti) % 优胜个体,多复制几个
            nf(newi,:)=f(fiti,:);    % 复制
            newi=newi+1;             % 新个体计数+1
        else                         % 劣汰个体,少复制或者干脆直接跳过去
            fiti=fiti+1;
        end
    end   
    %%%%%%%%%%%%%%%%%%%%%%基于概率的交叉操作%%%%%%%%%%%%%%%%%%
    for i=1:2:NP               % 此处步长为2,主要是相邻两个个体进行交叉
        p=rand;                % 生成一个随机数
        if p<Pc                % 以Pc的概率进行交叉
            q=randi([0,1],1,L);% 随机生成一个交叉序列,0位不变异,1位变异
            for j=1:L
                if q(j)==1     % 交叉的基因,不交叉的基因直接跳过
                    temp=nf(i+1,j);
                    nf(i+1,j)=nf(i,j);
                    nf(i,j)=temp;
                end
            end
        end
    end
    %%%%%%%%%%%%%%%%%%%基于概率的变异操作%%%%%%%%%%%%%%%%%%%%%%%
    i=1;
    while i<=round(NP*Pm)
        h=randi([1,NP],1,1);      %随机选取一个需要变异的个体(染色体)
        for j=1:round(L*Pm)       %Pm是变异概率,L * Pm四舍五入得到变异的基因数量
            g=randi([1,L],1,1);   %随机需要变异的基因数
            nf(h,g)=~nf(h,g);
        end
        i=i+1;
    end
    f=nf;                           %更新种群
                                    %由于轮盘赌选择的时候,在前面的个体更容易被选中,
    f(1,:)=fBest;                   %如果最优个体在后面,则不一定被选中,这步操作是要保留最优个体(二进制)在新种群中
    trace(k)=maxFit;                %历代最优适应度
end
xBest                               %最后一代最优个体
finalXBest                          %最优个体
figure
plot(trace)
xlabel('迭代次数')
ylabel('目标函数值')
title('适应度进化曲线')

其中目标函数(适应度函数)的定义如下:

%%%%%%%%%%%%%%%%%%%%%%%%%适应度函数%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function result=func1(x)
fit= x+10*sin(5*x)+7*cos(4*x);
result=fit;

4. 求解结果及分析

可以看到,遗传算法的收敛速度较快,如下:

在这里插入图片描述

同时,遗传算法收敛性很棒的特点,经过多次测试,最后一代的最优个体就是所有代中的最优个体,即:在该问题中种群没有发生退化,导致目标函数出现震荡的现象。

在这里插入图片描述


六、遗传算法的一些改进方向

在现有文献中,对遗传算法的改进主要集中在以下方面:编码机制(如何编码(转化问题))、选择策略(怎么去选择?)、交叉算子(怎么交叉?)、变异算子(怎么变异)、特殊算子和参数设计。

每一个遗传算法的应用都要涉及到上述问题,上面的案例代码中包含了这些方面一种解决办法,当然,后续的改进还有许多。

此外,还存在着和差分进化算法、免疫算法、蚁群算法等结合起来的混合遗传算法,可以综合遗传算法和其它算法的优点,提高效率和求解质量。2

the end……

遗传算法到这里就要结束啦~~到此既是缘分,欢迎您的点赞评论收藏关注我,不迷路,我们下期再见!!

😘😘😘 我是Cherries,一位计算机科班在校大学生,写博客用来记录自己平时的所思所想!
💞💞💞 内容繁杂,又才疏学浅,难免存在错误,欢迎各位大佬的批评指正!
👋👋👋 我们相互交流,共同进步!

:本文由非妃是公主发布于https://blog.csdn.net/myf_666,转载请务必标明原文链接:https://blog.csdn.net/myf_666/article/details/129166215


  1. 百度百科——自然选择 ↩︎

  2. 包子阳,智能优化算法及其matlab实例.电子工业出版社. ↩︎

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐