• 备战数学建模37-遗传算法GA(攻坚战1)

    目录

    一、遗传算法的概念

    1.1、基本概念

     1.2、遗传算法的基本过程

     1.3、遗传算法的具体步骤

    二、遗传算法经典案例

    2.1、遗传算法求解函数极大值问题

    2.2、遗传算法求解函数极小值问题

    2.3、遗传算法求解旅行商问题(TSP)

    2.4、遗传算法求解背包问题

    一、遗传算法的概念

    1.1、基本概念

    遗传算法(Genetic Algorithm,GA):模仿生物的遗传进化原理，通过选择、交叉、变异等操作，使得种群个体的适应性不断提高，物竞天择，适者生存。智能算法，全局搜索寻优。

    遗传算法的特点如下：

     遗传算法的应用领域比较广泛，具体涉及的应用领域如下：

    我们看三个概念，即个体，种群，适应度。初始解组成的是个体，多个个体组成的称为种群，适应度是指衡量个体适应高低的，适应度函数一般就是指的目标函数。

     下面看一下编码和解码的概念，本文中的编码和解码如下，编码是指将原来的个体改变成能进行选择，交叉，和变异等操作的染色体的过程。而解码就是将染色体转换成为原始的个体，即最优解。编码是遗传算法解决问题的先决条件和关键步骤，常用的编码方式有：二进制编码，浮点数编码等。一般来说，二进制编码比浮点型编码的搜索能力更强，浮点型编码在种群多样性的操作更具多样性。

    下面看一下遗传操作的选择，交叉与变异。选择操作就是选择好的进行遗传，交叉就是随机配对，变异就是改变基因到其对应的基因。

     1.2、遗传算法的基本过程

    遗传算法的基本过程如下：主要包括：收集问题参数并编码成染色体，初始化种族群体，通过选择交叉，变异等遗传操作更新群体，并计算群体的适应度，直到达到迭代次数或者适应度值不发生改变，则终止循环，并对染色体进行解码，即可得到问题的最优解。

    下面看一下遗传算法的具体步骤：

    首先，我们需要确定决策变量和约束条件，这个通常根据题意获得。然后建立模型，需要确定目标函数，然后需要找出个体，并对个体进行编码，编码是非常重要的，常用的编码方式是二进制编码。

    标准的遗传算法基本是采用二进制编码，就是将个体(决策变量)用二进制串连在一起，构成染色体。编码完成，最后留下满足适应度函数的染色体后，还需要进行解码成个体，所以需要确定解码方法。其实就是还原成原来的决策变量。

    然后，我们需要确定个体适应度的量化方法，即确定适应度函数，通过适应度函数去求解最优的决策变量，一般比较常用的就是直接将目标函数作为适应度函数，当然也有其它方法去确定适应度函数。

     

     

    有了适应度函数后，我们就可以确定选择，交叉和变异的方式，个体选择常用的方法是按比例适应度分配，个体的适应度在总适应度的比例越大，即被选取的概率越大，遗产因子就会在种群中逐渐扩大。

    计算出每个个体的选择概率后，我们就使用轮盘赌法进行选择，其实就是概率越大，轮盘所占比例越大，被选中的可能越大。

    遗传的相关操作除了选择之外，还有交叉和变异，我们下面看一下交叉操作，交叉其实就是序列的交换，交叉率不宜过大，也不宜过小，一般取0.4-0.9。

     

     下面看一下变异操作，对于二进制编码的变异，就是将1变成0，或者将0变成1，也应该选取合适的变异率，变异率过大和过小都不好。

     

     1.3、遗传算法的具体步骤

     遗传算法的具体步骤如下：首先对个体编码成染色体，初始化群体并计算解码后的适应值，然后进行遗传操作形成下一代群体， 判断是否满足要求，不满足则继续迭代，直到满足要求或者达到迭代次数。

    二、遗传算法经典案例

    2.1、遗传算法求解函数极大值问题

     用标准遗传算法求函数f(x)=x+10sin(5x)+7cos(4x) 的最大值，其中 x 的取值范围为[0,10]。这是一个有多个局部极值的函数。

    下面是使用遗传算法求解该函数模型最大值的具体步骤：

    （1）初始化种群数目为 NP=50，染色体的编码方式选择二级制编码，二进制编码长度为 L=20，遗传算法的最大进化迭代数为 G=100，交叉概率 取Pc=0.8，变异概率取Pm=0.1。

    （2）产生初始种群，将二进制编码转换成十进制，计算个体适应度值，并进行归一化；采用基于轮盘赌的选择操作、基于概率的交叉和变异操作，产生新的种群，并把历代的最优个体保留在新种群中，进行下一步遗传操作。

    （3）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。

    优化结束后，其适应度进化曲线如下图所示，最优个体 x= 7.8569，函数 f(x)的最大值为 24.8554。这个值不是固定的，每次执行都会有些许波动。

    遗传算法的具体流程图如下：

     完整的matlab代码如下，注释很全：

    1. %遗传算法求函数极值
    2. clear 
    3. clc
    4. NP = 50; %种群数量
    5. L = 20; %二进制位串长度
    6. Pc = 0.8; %交叉率
    7. Pm = 0.1; %变异率
    8. G = 100; %最大遗传迭代次数
    9. Xs = 10; %个体最小值
    10. Xx = 0; %个体最大值
    11. f = randi([0,1],NP,L); %随机获得初始种群
    12. %遗传算法
    13. for k = 1:G
    14.     for i = 1:NP
    15.         U = f(i,:); %遍历每个种群
    16.         m = 0;
    17.         for j = 1:L %遍历种群的每个二进制位
    18.             m = U(j)*2^(j-1)+m ; %将二进制转换成十进制
    19.         end
    20.         x(i) = Xx+m*(Xs-Xx)/(2^L-1); %对染色体进行解码得到个体
    21.         Fit(i) = func1(x(i)); %通过目标函数计算个体的适应度
    22.     end
    23.     maxFit = max(Fit); %适应度最大值
    24.     minFit = min(Fit); %适应度最小值
    25.     rr = find(Fit==maxFit); %找到适应度最大值的的位置
    26.     fBest = f(rr(1,1),:); %最适应的种群
    27.     xBest = x(rr(1,1)); %最适应的染色体，即个体
    28.     Fit = (Fit-minFit)/(maxFit-minFit); %归一化适应度值
    29.     
    30.     %基于轮盘赌法的选择操作
    31.     sum_Fit = sum(Fit) ; %对适应度进行求和
    32.     fitvalue = Fit./sum_Fit; %求每个适应度被选中的概率
    33.     fitvalue = cumsum(fitvalue) ; %得到累加后的概率
    34.     ms = sort(rand(NP,1)) ; %随机生成概率值，并由小到大排序
    35.     fiti = 1;
    36.     newi = 1;
    37.     while newi <= NP
    38.         if ms(newi) < fitvalue(fiti) %如果随机生成的概率值小于被选中的概率
    39.             nf(newi,:) = f(fiti,:); %找到选择出来的染色体
    40.             newi = newi+1;
    41.         else %不满足条件，继寻找合适的染色体
    42.             fiti = fiti+1;
    43.         end
    44.     end
    45.     %交叉操作，就是二进制对应0和1的互换
    46.     for i = 1:2:NP  %遍历种群
    47.         p = rand ; %随机产生的一个概率
    48.         if p > Pc %要保证随机产生的概率大于交叉率
    49.             q = rand(1,L);
    50.             for j = 1:L
    51.                 if q(j)==1 %只要随机产生的位置等于1，就进行交叉
    52.                     %将被选择的二级制进行交换，即交叉
    53.                     temp = nf(i+1,j);
    54.                     nf(i+1,j) = nf(i,j);
    55.                     nf(i,j) = temp;
    56.                 end
    57.             end
    58.         end
    59.     end
    60.     %变异操作，就是二进制取反操作
    61.     i = 1;
    62.     while i <= round(NP*Pm)
    63.         h = randi([1,NP],1,1); %随机选取一个需要变异的染色体
    64.         for j = 1:round(L*Pm)
    65.             g = randi([1,L],1,1); %随机选取需要变异的基因数
    66.             nf(h,g) =~ nf(h,g); %取反变异
    67.         end
    68.         i = i+1;
    69.     end
    70.     f = nf; %更新种群
    71.     f(1,:) = fBest; %保留最优个体在新种群中
    72.     trace(k) = maxFit; %保存最优的适应度
    73. end
    74. disp('最优个体如下：') ;
    75. disp(xBest) ;
    76. disp('函数最大值：') ;
    77. disp(func1(xBest)) ;
    78. figure
    79. plot(trace)
    80. xlabel('迭代次数')
    81. ylabel('目标函数值')
    82. title('适应度进化曲线')

    适应度函数即目标函数如下：

    1. function result = func1(x)
    2. fit = x+10*sin(5*x)+7*cos(4*x);
    3. result = fit;
    4. end

    迭代过程的适应度进行如下，最终的值在24.85左右，即函数的最值为24.85左右。

    2.2、遗传算法求解函数极小值问题

    （1）初始化种群数目为 NP=100，染色体的编码方式选择二级制编码，二进制编码长度为 L=10，遗传算法的最大进化迭代数为 G=1000，交叉概率 取Pc=0.8，变异概率取Pm=0.1。

    （2）产生初始种群，将二进制编码转换成十进制，计算个体适应度值；采用基于轮盘赌的选择操作、基于概率的交叉和变异操作，产生新的种群，并把历代的最优个体保留在新种群中，进行下一步遗传操作。

    （3）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。

    1. %遗传算法求函数极值
    2. clear 
    3. clc
    4. NP = 100; %种群数量
    5. L = 10; %二进制位串长度
    6. Pc = 0.8; %交叉率
    7. Pm = 0.1; %变异率
    8. G = 1000; %最大遗传迭代次数
    9. Xs = 20; %个体上限
    10. Xx = -20; %个体下线
    11. f = randi([0,1],NP,L); %随机获得初始种群
    12. %遗传算法
    13. for k = 1:G
    14.     for i = 1:NP
    15.         U = f(i,:); %遍历每个种群
    16.         m = 0;
    17.         for j = 1:L %遍历种群的每个二进制位
    18.             m = U(j)*2^(j-1)+m ; %将二进制转换成十进制
    19.         end
    20.         x(i) = Xx+m*(Xs-Xx)/(2^L-1); %对染色体进行解码得到个体
    21.         Fit(i) = -func2(x(i)); %通过目标函数计算个体的适应度
    22.     end
    23.     maxFit = max(Fit); %适应度最大值
    24.     %minFit = min(Fit); %适应度最小值
    25.     rr = find(Fit==maxFit); %找到适应度最小值的的位置
    26.     fBest = f(rr(1,1),:); %最适应的种群
    27.     xBest = x(rr(1,1)); %最适应的染色体，即个体
    28.    % Fit = (Fit-minFit)/(maxFit-minFit); %归一化适应度值
    29.     
    30.     %基于轮盘赌法的选择操作
    31.     sum_Fit = sum(Fit) ; %对适应度进行求和
    32.     fitvalue = Fit./sum_Fit; %求每个适应度被选中的概率
    33.     fitvalue = cumsum(fitvalue);  %得到累加后的概率
    34.     ms = sort(rand(NP,1)) ; %随机生成概率值，并由小到大排序
    35.     fiti = 1;
    36.     newi = 1;
    37.     while newi <= NP
    38.         if ms(newi) < fitvalue(fiti) %如果随机生成的概率值小于被选中的概率
    39.             nf(newi,:) = f(fiti,:); %找到选择出来的染色体
    40.             newi = newi+1;
    41.         else %不满足条件，继寻找合适的染色体
    42.             fiti = fiti+1;
    43.         end
    44.     end
    45.     %交叉操作，就是二进制对应0和1的互换
    46.     for i = 1:2:NP  %遍历种群
    47.         p = rand ; %随机产生的一个概率
    48.         if p > Pc %要保证随机产生的概率大于交叉率
    49.             q = rand(1,L);
    50.             for j = 1:L
    51.                 if q(j)==1 %只要随机产生的位置等于1，就进行交叉
    52.                     %将被选择的二级制进行交换，即交叉
    53.                     temp = nf(i+1,j);
    54.                     nf(i+1,j) = nf(i,j);
    55.                     nf(i,j) = temp;
    56.                 end
    57.             end
    58.         end
    59.     end
    60.     %变异操作，就是二进制取反操作
    61.     i = 1;
    62.     while i <= round(NP*Pm)
    63.         h = randi([1,NP],1,1); %随机选取一个需要变异的染色体
    64.         for j = 1:round(L*Pm)
    65.             g = randi([1,L],1,1); %随机选取需要变异的基因数
    66.             nf(h,g) =~ nf(h,g); %取反变异
    67.         end
    68.         i = i+1;
    69.     end
    70.     f = nf; %更新种群
    71.     f(1,:) = fBest; %保留最优个体在新种群中
    72.     trace(k) = -maxFit; %保存最大的适应度
    73. end
    74. disp('最优个体如下：') ;
    75. disp(xBest) ;
    76. disp('函数最小值：') ;
    77. disp(func2(xBest)) ;
    78. figure
    79. plot(trace)
    80. xlabel('迭代次数')
    81. ylabel('目标函数值')
    82. title('适应度进化曲线')

    适应度函数如下：

    1. function result=func2(x)
    2. summ=sum(x.^2);
    3. result=summ;
    4. end

    运行结果如下：

     

    2.3、遗传算法求解旅行商问题(TSP)

    [旅行商问题]（TSP）。假设有一个旅行商人要拜访全国31个省会城市，他需要选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。对路径选择的要求是：所选路径的路程为所有路径之中的最小值。全国31个省会城市的坐标为［1304 2312；3639 1315；4177 2244；37121399；3488 1535；3326 1556；3238 1229；4196 1004；4312 790；4386 570；3007 1970；2562 1756；2788 1491；2381 1676；1332695；3715 1678；3918 2179；4061 2370；3780 2212；3676 2578；4029 2838；4263 2931；3429 1908；3507 2367；3394 2643；34393201；2935 3240；3140 3550；2545 2357；2778 2826；2370 2975］。

    （1）初始化种群数目为NP=200,最大遗传迭代数目为G=1000，染色体基因个数为N=31，即城市数目。

    （2）产生初始种群，计算个体适应度值，即路径长度；采用基于概率的方式选择进行操作的个体；对选中的成对个体，随机交叉所选中的成对城市坐标，以确保交叉后路径每个城市只到访一次；对选中的单个个体，随机交换其一对城市坐标作为变异操作，产生新的种群，进行下一次遗传操作。

    （3）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。

    Matlab代码如下：

    1. %遗传算法解决TSP问题
    2. clear 
    3. close all; 
    4. clc;   
    5. C=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...
    6.     3238 1229;4196 1044;4312  790;4386  570;3007 1970;2562 1756;...
    7.     2788 1491;2381 1676;1332  695;3715 1678;3918 2179;4061 2370;...
    8.     3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;...
    9.     3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;...
    10.     2370 2975];%省会城市坐标
    11. N=size(C,1);%C的行数,即城市数目
    12. D=zeros(N);%N*N的零矩阵，初始化任意两个城市距离间隔矩阵
    13. %求任意两个城市距离间隔矩阵
    14. for i=1:N
    15.     for j=1:N
    16.         D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
    17.     end
    18. end
    19. NP=200;%种群数目
    20. G=1000;%最大遗传迭代数
    21. f=zeros(NP,N);%NP*N的零矩阵，用于存储种群
    22. F=[];%种群更新中间存储
    23. for i=1:NP
    24.     f(i,:)=randperm(N);%1~N之间的随机数，随机生成初始种群
    25. end
    26. R=f(1,:);%用于存储最优种群
    27. len=zeros(NP,1);%用于存储路径长度
    28. fitness=zeros(NP,1);%用于存储归一化适应值
    29. gen=0;
    30. %遗传算法循环，小于最大遗传迭代次数，则继续更新下一代
    31. while gen<G
    32.     %计算路径长度
    33.     for i=1:NP
    34.         len(i,1)=D(f(i,N),f(i,1));
    35.         for j=1:(N-1)
    36.             len(i,1)=len(i,1)+D(f(i,j),f(i,j+1));
    37.         end
    38.     end
    39.     maxlen=max(len);%最长路径
    40.     minlen=min(len);%最短路径
    41.     %更新最短路径
    42.     rr=find(len==minlen);
    43.     R=f(rr(1,1),:);
    44.     %计算归一化适应值
    45.     for i=1:length(len)
    46.         fitness(i,1)=(1-((len(i,1)-minlen)/(maxlen-minlen+0.001)));
    47.     end
    48.     %选择操作
    49.     nn=0;
    50.     for i=1:NP
    51.         if fitness(i,1)>=rand
    52.             nn=nn+1;
    53.             F(nn,:)=f(i,:);
    54.         end
    55.     end
    56.     [aa,bb]=size(F);
    57.     while aa<NP
    58.         nnper=randperm(nn);
    59.         A=F(nnper(1),:);
    60.         B=F(nnper(2),:);
    61.         %交叉操作
    62.         W=ceil(N/10);%交叉点个数
    63.         p=unidrnd(N-W+1);%随机选择交叉范围，从p到p+W
    64.         for i=1:W
    65.             x=find(A==B(p+i-1));
    66.             y=find(B==A(p+i-1));
    67.             temp=A(p+i-1);
    68.             A(p+i-1)=B(p+i-1); 
    69.             B(p+i-1)=temp;
    70.             temp=A(x); 
    71.             A(x)=B(y); 
    72.             B(y)=temp;
    73.         end
    74.         %变异操作
    75.         p1=floor(1+N*rand());
    76.         p2=floor(1+N*rand());
    77.         while p1==p2
    78.             p1=floor(1+N*rand());
    79.             p2=floor(1+N*rand());
    80.         end
    81.         tmp=A(p1); 
    82.         A(p1)=A(p2); 
    83.         A(p2)=tmp;
    84.         tmp=B(p1); 
    85.         B(p1)=B(p2); 
    86.         B(p2)=tmp;
    87.         F=[F;A;B];
    88.         [aa,bb]=size(F);
    89.     end
    90.     if aa>NP
    91.         F=F(1:NP,:);%保持种群规模为n
    92.     end
    93.     f=F;%更新种群
    94.     f(1,:)=R;%保留每代最优个体
    95.     clear F;
    96.     gen=gen+1 ;
    97.     Rlength(gen)=minlen;
    98. end
    99. figure
    100. for i=1:N-1
    101.     plot([C(R(i),1),C(R(i+1),1)],[C(R(i),2),C(R(i+1),2)],'bo-');
    102.     hold on;
    103. end
    104. title(['优化最短距离:',num2str(minlen)]);
    105. figure
    106. plot(Rlength)
    107. xlabel('迭代次数')
    108. ylabel('目标函数值')
    109. title('适应度进化曲线')

    运行结果如下：

     

     

    2.4、遗传算法求解背包问题

    [0-1背包问题]。有N件物品和一个容量为V的背包。第i件物品的体积是c(i)，价值是w(i)。求解将哪些物品放入背包可使物品的体积总和不超过背包的容量，且价值总和最大。假设物品数量为10，背包的容量为300。每件物品的体积为［95，75，23，73，50，22，6，57，89，98］，价值为［89，59，19，43，100，72，44，16，7，64］。

    （1）初始化种群数目为Np =50，染色体基因维数为L=10，最大进化代数为G=100。

    （2）产生二进制初始种群，其中1表示选择该物品，0表示不选择该物品。取适应度值为选择物品的价值总和，计算个体适应度值，当物品体积总和大于背包容量时，对适应度值进行惩罚计算。

    （3）对适应度进行归一化，采用基于轮盘赌的选择操作、基于概率的交叉和变异操作，产生新的种群，并把历代的最优个体保留在新种群中，进行下一步遗传操作。

    （4）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。
     

    matlab代码如下：

    1. %遗传算法解决0-1背包问题
    2. clear  
    3. close all;
    4. clc; 
    5. NP = 50;%种群规模
    6. L = 10;%物品件数
    7. Pc = 0.8;%交叉率
    8. Pm = 0.05;%变异率
    9. G = 100;%最大遗传代数
    10. V = 300;%背包容量
    11. C = [95,75,23,73,50,22,6,57,89,98]; %物品体积
    12. W = [89,59,19,43,100,72,44,16,7,64];%物品价值
    13. afa = 2; %惩罚函数系数
    14. f = randi([0,1],NP,L);%随机获得初始种群
    15. maxFit = 0 ;
    16. %遗传算法循环部分
    17. for k = 1:G
    18.     %适应度计算,即计算总价值
    19.     for i = 1:NP
    20.          Fit(i) = func4(f(i,:),C,W,V,afa);
    21.     end
    22.     maxFit = max(Fit);%最大价值
    23.     minFit = min(Fit);%最小价值
    24.     rr = find(Fit==maxFit);
    25.     fBest = f(rr(1,1),:);%历代最优个体
    26.     Fit = (Fit - minFit)/(maxFit - minFit);%归一化适应度值
    27.     %基于轮盘赌的选择
    28.     sum_Fit = sum(Fit); %求适应度和
    29.     fitvalue = Fit./sum_Fit;%求被选中的概率
    30.     fitvalue = cumsum(fitvalue);%累加
    31.     ms = sort(rand(NP,1)); %随机生成的概率，并按照由小到大排序
    32.     fiti = 1;
    33.     newi = 1;
    34.     while newi <= NP
    35.         if (ms(newi)) < fitvalue(fiti) %被选中的概率大于随机生成的
    36.             nf(newi,:) = f(fiti,:); %选择复制
    37.             newi = newi + 1;
    38.         else
    39.             fiti = fiti + 1;
    40.         end
    41.     end
    42.     %基于概率的交叉操作
    43.     for i = 1:2:NP
    44.         p = rand;
    45.         if p > Pc
    46.             q = randi([0,1],1,L);          
    47.             for j = 1:L
    48.                 if q(j)==1;
    49.                     temp = nf(i + 1,j);
    50.                     nf(i + 1,j) = nf(i,j);
    51.                     nf(i,j) = temp;
    52.                 end
    53.             end
    54.         end
    55.     end
    56.     %基于概率的变异操作
    57.     for m = 1:NP
    58.         for n = 1:L
    59.             r = rand(1,1);
    60.             if r < Pm
    61.                 nf(m,n) = ~nf(m,n);
    62.             end
    63.         end
    64.     end
    65.     f = nf;
    66.     f(1,:) = fBest; %保留最优个体在新种群中
    67.     trace(k) = maxFit; %历代最优适应度
    68. end
    69. disp('最优个体如下：') ;
    70. disp(fBest) ;
    71. disp('最大价值如下：') ;
    72. disp(maxFit) ;
    73. figure
    74. plot(trace)
    75. xlabel('迭代次数')
    76. ylabel('目标函数值')
    77. title('适应度进化曲线')

    适应度函数的代码如下：

    1. %适应度函数，求物品价值总和
    2. function result = func4(f,C,W,V,afa)
    3. fit = sum(f.*W); %物品价值总和
    4. TotalSize = sum(f.*C); %物品总体积
    5. if TotalSize <= V %物品总体积小于背包容量
    6.     fit = fit;
    7. else %物品总体积大于背包容量
    8.     fit = fit - afa * (TotalSize - V);
    9. end
    10. result = fit;
    11. end

    运行结果如下：其实10个物品，1表示选择该物品，0表示不选择该物品，最后的最大总价值为388

     

  • 相关阅读:
    Android 打包和安装命令二合一的好用脚本
    Swagger的界面太丑，试试knife4j的接口文档吧
    二叉搜索树
    C语言：简单的用二维数组打印杨氏三角
    数据结构从入门到实战——顺序表的应用
    ASP.NET Core 6框架揭秘实例演示[15]：针对控制台的日志输出
    Spring MVC：数据绑定
    降低打新的预期
    Cisco 与 Intel路由器的对连配置实例
    Vue3 企业级优雅实战 - 组件库框架 - 7 组件库文档的开发和构建
  • 原文地址：https://blog.csdn.net/nuist_NJUPT/article/details/126081432