一文读懂GA遗传算法(原理+案例+源码)-夜雨聆风

一文读懂GA遗传算法(原理+案例+源码)

前段时间给大家分享了非线性优化算法系列详解（梯度法、高斯牛顿、LM法）等基于数值求解的非线性优化算法，它们都是基于梯度的局部搜索方法，无法获得全局最优解，今天为大家分享一个全局优化算法–遗传算法。

遗传算法（Genetic Algorithm，GA）最早于20世纪70年代提出,是模拟生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解的方法。包含的三种基本遗传操作为选择、交叉、变异，整个算法流程包括以下五步：

1. 种群初始化

核心思想：设置种群参数，在解空间中随机生成一组候选解，构成初始种群。

具体实现：

编码方式：将问题的解编码为一组染色体，常用二进制编码、实数编码等

种群规模：通常设置为50-200个个体，规模过小容易早熟收敛，过大则计算成本增加

初始化策略：完全随机生成，或结合启发式信息生成部分优质个体

2. 适应度函数设计

核心思想：通过适应度函数量化每个个体的优劣程度，为选择操作提供依据。

关键要点：

适应度函数设计：直接决定最终结果优劣，需准确反映个体质量

最大化问题：适应度 = 目标函数值
最小化问题：适应度 = 1/(目标函数值 + ε) 或采用线性变换
评价标准：适应度值越高，个体越优秀，生存和繁殖机会越大

例如：在旅行商问题(TSP)中，适应度可设为路径总距离的倒数，路径越短适应度越高。

3. 选择操作

核心思想：模拟适者生存，根据适应度筛选优秀个体，用于产生下一代。

常用方法：

轮盘赌选择：个体被选概率 = 个体适应度/总适应度，实现简单，但高适应度个体可能垄断
锦标赛选择：随机选k个个体，取最优，常用k=2或3
排序选择：按适应度排序，基于排名选择，适合适应度差异大的情况
精英保留：直接将最优个体复制到下一代，防止优秀基因丢失

4. 交叉操作

核心思想：模拟遗传学中的基因重组操作，两个父代个体交换基因片段，产生继承双方特征的新个体。

根据初始化种群时不同的编码方式，常用的交叉操作有：

二进制编码：

单点交叉：随机选切断点，交换后半部分

父代1:11010|101→子代1:11010|011

父代2:00101|011→子代2:00101|101

多点交叉：多个切断点，增强探索能力

均匀交叉：每个基因位独立决定是否交换

实数编码：

算术交叉：子代 = α×父代1+(1-α)×父代2

启发式交叉：向较优父代方向搜索

排列编码（如TSP问题）：

部分映射交叉(PMX)、顺序交叉(OX)、循环交叉(CX)等，需保持排列合法性

交叉概率：并不是每次迭代都有交叉操作，概率通常设为0.6~0.9，控制基因重组频率。

5. 变异操作

核心思想：模拟遗传学中的基因突变操作，以极小概率随机改变个体某些基因值，维持种群多样性，防止陷入局部最优。

根据初始化种群时不同的编码方式，常用的变异操作有：

二进制编码：采用位翻转变异，即随机选几位，0变1或1变0
实数编码：采用高斯变异、均匀变异，给实数基因添加随机扰动
排列编码：采用交换变异、插入变异、逆序变异，需要保持排列约束

变异概率：同样并不是每次迭代都有变异操作，有一个概率通常设为0.001到0.1，必须保持较低，因为过高会导致算法退化为随机搜索，过低会导致种群多样性不足，易早熟收敛

算法案例：装配线平衡问题

在装配线上，装配操作的具体分配关系到装配效率，随即产生了装配线平衡问题。在装配线上有两个重要的约束：节拍约束和优先关系约束。

节拍约束：要求每个工位上的装配操作必须在生产时间节拍内完成；
优先关系约束：要求装配操作的前序完成后才能加工其后续操作，例如电视机安装必须先装内部元器件后才能封装外壳。

第I类装配线平衡问题：给出任务分配要求用到的工人数量最少。

对于下表这个项目任务，给出了项目序号、作业时间和先行任务。例如任务1需要完成任务2和任务4后才能作业，需耗费1个时间单位。

首先对问题进行建模，设：

则目标函数为最少的工人数量：

然后设定一系列的约束条件：

一个任务只能分配到一个工位上：

任务间的优先级关系约束：

各工位时间不得大于生产节拍：

各工位分配的任务不能超过总数N:

编写相关代码完成迭代优化求解：

首先初始化种群

%% 初始化种群num1=100;     %种群规模num2=500;     %进化代数num3=20;      %选择操作时的最优个体数目pc=0.6;       %交叉概率pm=0.05;      %变异概率P=zeros(num,num);  %记录各任务优先级关系的矩阵[row,col]=size(S);for i=1:row   %得到优先级矩阵    P(S(i,1),S(i,2))=1;endpop=zeros(num1,num+1);  for i=1:num1   %初始化种群使其满足优先级关系     while 1    %确定每个种群的第一个任务         m=randi(num,'int8');         sum=0;         for i_=1:num             sum=sum+P(i_,m);         end         if sum==0             pop(i,1)=m;  %放置第一个任务             break;         end     end       for j=2:num  % 确定每个种群后面的任务         while 1             ff=0;             m=randi(num,'int8');             for k=1:j-1     %判断所生产的任务前面是否已安排                 if m==pop(i,k)                     ff=1;                     break;                 end             end             if ff==1                 continue;             end                  sum=0;             for k=1:j-1    %前面安排的任务中是m前序的数目                 sum=sum+P(pop(i,k),m);             end             sum_=0;             for i_=1:num   %任务m的所有优先前序                sum_=sum_+P(i_,m);             end             if sum_==sum                 pop(i,j)=m;                 break;             end         end     end end

然后再根据目标函数设置适应度函数

function [pop]=fitness_function(pop) %求适应度函数，即求工人数目global ct  T[num1,num]=size(pop);for i=1:num1    M=0;    tt=0;    for j=1:num-2        tt=tt+T(pop(i,j));        if(tt<=ct)&&(tt+T(pop(i,j+1))>ct) %确定每个工人的工作时间在生产节拍内            M=M+1;            tt=0;        end        if j==num-2            M=M+1;            tt=0;        end    end    pop(i,num)=M;  %求得的工人数end

然后编写选择操作相关代码

function [pop]=select(pop,c) %选择操作[s,t]=size(pop);m=(pop(:,t))';mmax=zeros(1,c);mmin=zeros(1,c);m1=m;num=1;while num<c+1 %取m值大的c个个体    [a,mmax(num)]=max(m1);    m1(mmax(num))=0;    num=num+1;endm2=m;num=1;while num<c+1  %取m值小的c个个体    [b,mmin(num)]=min(m2);    m2(mmin(num))=a+1;    num=num+1;endfor i=1:c %用m值大的样本替代m值小的    pop(mmax(i),:)=pop(mmin(i),:);end

然后再编写交叉相关代码

function [pop]=cross(pop) %交叉操作global P[s,t]=size(pop);pop1=pop;n=randperm(s); %每次进化种群随机排序for i=1:s-1    point=randi(t-1,'int8');%选择一个随机交叉点    x1=n(i);  %随机取两行交叉    x2=n(i+1);     mid=pop(x1,1:point);  %将x1的左面和x2的左面交换    pop(x1,1:point)=pop(x2,1:point);    pop(x2,1:point)=mid;    a1=pop(x1,1:t-1);    a2=pop(x2,1:t-1);%c2为交换后的个体    b1=[]; b=[];j_=1;     for j=1:point %寻找a1重复元素插入b1        len=length(a1);        if len==point            break;        end        for k=point+1:len            if a1(j)==a1(k)                b(j_)=k;                j_=j_+1;            end            b1=[b1 a1(k)];        end    end    a1(b)=[];  %删除a1中重复的数据    b2=[];b=[];j_=1;     for j=1:point %寻找a2重复元素插入b2        len=length(a2);        if len==point            break;        end        for k=point+1:len            if a2(j)==a2(k)                b(j_)=k;                j_=j_+1;            end            b2=[b2 a2(k)];        end    end     a2(b)=[];  %删除a2中重复的数据    if isempty(b1)&&isempty(b2)  %将重复元素按优先级插入原编码        pop(x1,1:t-1)=a1;        pop(x2,1:t-1)=a2;    else        if length(a1)==point            c1=[];c2=[];        else            c1=a1(point+1:length(a1));            c2=a2(point+1:length(a2));%c2为删除重复点后交叉点后半部分数据        end        for j=1:length(b1)            b=b1(j);            len=length(c2);            if len==0                c2=[c2 b];            elseif len==1                if P(b,c2(len))==1                    c2=[b c2];                else                    c2=[c2 b];                end            else                for k=1:len                    if P(b,c2(k))==1                        break;                    end                end                if k==1                    c2=[b c2];                else                    if k==len                        if P(b,c2(len))==1                            c2=[c2(1:len-1),b,c2(len)];                        else                            c2=[c2 b];                        end                    else                        c2=[c2(1:k-1),b,c2(k:len)];                    end                end            end        end        for j=1:length(b2)            b=b2(j);            len=length(c1);            if len==0                c1=[c1 b];            elseif len==1                if P(b,c1(len))==1                    c1=[b c1];                else                    c1=[c1 b];                end            else                for k=1:len                    if P(b,c1(k))==1                        break;                    end                end                if k==1                    c1=[b c1];                else                    if k==len                        if P(b,c1(len))==1                            c1=[c1(1:len-1),b,c1(len)];                        else                            c1=[c1 b];                        end                    else                        c1=[c1(1:k-1),b,c1(k:len)];                    end                end            end        end        pop(x1,1:t-1)=[a1(1:point) c1];        pop(x2,1:t-1)=[a2(1:point) c2];    endend  %进行交叉变异pop=fitness_function(pop);  % 计算适应度for i=1:s  %新种群与变异前对比取优    if pop1(i,t)<pop(i,t)        pop(i,:)=pop1(i,:);    endend

最后再编写变异相关代码

function [pop]=mutate(pop) %变异操作global P[s,t]=size(pop);pop1=pop;for i=1:s    %进行变异    point=randi(t-2,'int8'); %随机选择变异点    aa=pop(i,1:t-1);    b=aa(point);    aa(point)=[];    len=length(aa);    for j=1:len        if P(b,aa(j))==1            break;        end    end    if j==1        pop(i,1:t-1)=[b aa];    elseif j==len        if P(b,aa(len))==1            pop(i,1:t-1)=[aa(1:len-1) b aa(len)];        else            pop(i,1:t-1)=[aa b];        end    else        pop(i,1:t-1)=[aa(1:j-1) b aa(j:len)];    end     end [pop]=fitness_function(pop);   % 计算适应度for i=1:s  %与变异前比较取优    if pop1(i:t)<pop(i,t)        pop(i,:)=pop1(i,:);    endend

进行生物进行迭代优化

for k=1:num2    % 开始迭代优化计算    pop=fitness_function(pop);  % 计算适应度    pop=select(pop,num3);  % 选择操作    p2=rand;    if p2<=pm        pop=mutate(pop);   % 变异操作    end    gen(k)=min(pop(:,num+1));end

优化得到的最后实验结果如下表所示：

最少需要5个工人，任务分配流程：

工位一：先分配任务1，完成任务1的时间是1秒，生产节拍为7秒，剩余6秒的时间，可以继续分配任务，可以选择的有任务2和4，选择任务2；此后工作时间6秒，剩余时间1秒，不能进行下一个任务分配，工位一任务分配完成。
工位二：先分配任务4，完成时间3秒，剩余时间4秒，后续可分配任务中有任务3，任务5，任务7，只有任务3满足要求可以分配。
工位三：分配任务5，完成时间5秒，工位三任务分配完成。
工位四：分配任务7，完成时间5秒，工位四任务分配完成。
工位五：最后只有任务6没有分配，只能安排任务6，所有任务完成。

工人任务分配和总的花费时间如图所示

总的工作时间：

空闲时间：

装配平衡效率

本期的分享就到这里啦，如果觉得本文还不错的话就给个免费的赞和在看吧！！！