遗传算法【Genetic Algorithm（GA）】求解函数最大值(MATLAB and Python实现）

一、遗传算法基础知识

来自B站视频的笔记：      【超容易理解】手把手逐句带你解读并实现遗传算法的MATLAB编程（结合理论基础）_哔哩哔哩_bilibili       

1、遗传算法

         使用“适者生存”的原则，在遗传算法的每一代中，根据个体在问题域的适应度值和从生物学借鉴来的再造方法(复制、变异、交叉)进行个体选择，产生比原个体更适应环境的近似解。

2、模式定理

        二值字符集(0，1}，由此产生通常的 0，1字符串。增加一个通配符“*”，既可以做 1，也可以做 0。二值字符集{0，1}可以扩展为三值字符集{0，1，*}，由此可以产生 0010，001*，*11*01*这类的字符串。

3、遗传算法的本质

        是对模式所进行的一系列运算。通过选择操作将当前群体中的优良群体遗传到下一代群体中，通过交叉操作进行模式的重组，通过变异操作进行模式的突变通过这些遗传运算，一些较差的模式逐步被淘汰，而一些较好的模型逐渐被遗传和进化最终就可以达到问题的最优解。

         多个字符串隐藏着多个不同的模式，长度为L的字符串，隐藏着个不同的模式，不同的模式所匹配的字符串个数不同，引入模式阶。

4、模式阶

        模式 001*0*的阶数为 4，而 0*****的阶数为 1，说明一个模式阶数高，说明确定性越高，样本个数越少。

5、定义距

        在模式 H中第一个确定位置和最后一个确定位置之间的距离,称之为模式距。

        在遗传算法的选择、交叉、变异算子的作用下，具有低阶，短定义距，并且平均适应度高于群体平均适应度的模式在子代将呈指数级增长，最终趋向全局的最优点。

        遗传算法使用群体搜索技术，通过对当前种群施加选择、交叉、变异等一系列遗传操作产生新一代种群，并逐步使种群进化到包含近似最优解的状态。

6、二进制编码精度

        For Example 求取实数区间[0,4]上函数的最大值，传统的方法是不断调成自变量本身，直到获取函数的最大值，而遗传算法不对参数本身做调整，首先先编码，形成位串在对位串进行进化操作。【0，64】←我们可以由长度为 6的位串表示变量 x，从“000000”到“111111”并将中间的取值映射到实数区间[0,4]，每个相邻的值之间的阶跃值为 4/63=0.0635。也就是编码精度。精度高，解的质量高，计算量大，耗时长。

【注】个人感觉2~6讲的是把问题的解编码成01串的理论过程。感兴趣问问AI或者搜其他文献。

7、适应度

        生物种群个体适应生存环境的能力，用于评价个体优劣的数学函数。GA 算法在进化搜索中基本不需要外部信息，仅仅依靠适应度。

 8、构造适应度函数的方法

        1）目标函数映射成适应度函数（常用）；

        2）基于序的目标函数等。

 9、遗传操作

        优选强势个体的“选择”(选择算子)，个体间交换基因产生新个体的“交叉(交叉算子)，个体基因突变而产生新个体的“变异”(变异算子)。

        9.1 选择算子:

        根据个体适应度，按照一定规则，从第t代群体P(t)中选择优良个体遗传到下一代 P(t+1)中。

        轮盘赌选择法:

        它是基于比例的选择，利用个体适应度所占比例的大小来决定子代保留的可能性。若每
个个体i的适应度为 fi，种群大小为 NP，则他被选取的概率为:

        个体适应度越大，被选择的机会越大，为了选择交叉个体，需要进行多轮选择，每一轮产生一个[0,1]均匀随机数，将该随机数作为选择指针来确定被选择个体。

        9.2 交叉算子

        将群体 P(t)中选中的各个个体随机搭配，对每一对个体以交叉概率 Pc 交换他们的染色体，通过交叉，遗传算法的搜索能力得以飞跃提高。

        9.3 交叉算子步骤

        从交配池中随机取出要交配的一对个体，然后，根据串长度L，对要交配的一对个体，对要交配的一对个体，随机选取[1,L-1]中的一个或者多个整数K作为交叉位置，最后，根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交换各自的部分基因，从而形成新的一对个体。

        9.4 变异算子

        对群体中的每个个体，以变异概率Pm,将某一个或某一些基因座上的基因值17.改变为其他的等位基因值，0-1，1-0 根据个体编码方式的不同，变异方式有:实值变异(对相应的基因值用取值范围内的其他随机值取代)，二进制变异(对应的基因取反)。

        9.5 变异算子步骤

        首先，对种群中所有个体按事先设定的变异概率判断是否进行变异，然后，对进行变异的个体随机选择变异位进行变异。

10、标准遗传算法

        优化变量由二进制算法进行描述，多个优化变量的二进制变化串接在一起组成染色体。在创建初始群体的过程中，代表个体的二进制串是在一定字长的限制下随机产生的，交叉算子作用在交叉概率选中的两个染色体上，随机选中交叉位置，将两个染色体上对应于这两个位置上的二进制数值进行交换，生成新的个体，而变异算子的作用在变异概率随机选中的个体上，一般是随机选定变异位，将该位的二进制值取反，生成一个新的个体。

二、遗传算法的流程

        初始化

        设置进化代数计数器 g=0,最大迭代数G,随机生成 NP个个体作为初始群体P(0);个体评价:计算群体P(t)中各个个体的适应度;

        选择操作

        将选择算子应用于群体，根据个体适应度满招一定的原则将优良个体传递给下-代群体。

        交叉运算

         将交叉算子应用于群体，对选中的个体以某一概率交换他们之间部分的染色体产生新的个体;

        变异运算

        将变异算子应用于群体，对选中的个体，以某一种概率改变某一个基因值为他的等位基因。   

        循环操作        

        群体 P(t)经过选择、交叉、变异运算后得到下一代种群P(t+1)，计算适应度值根据适应度进行排序，准备进行下一次变异操作。终止判断条件:如果 g<G，则 g=g+1，转到个体评价步骤，如果 g>G,则次进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。

三、关键参数说明

        种群规模 NP:影响着种群的最终结果以及遗传算法的执行效率，NP 一般取 10~200;

        交叉概率 Pc:交叉操作的使用频率，一般取 0.25~1

        变异概率 Pm:辅助性搜索操作，一般取 0.001~0.1

        终止进化代数:一般取 100~1000 之间。

四、实例分析

函数图像

MATLAB代码

%{ 
使用遗传算法求函数y = x+10*sin(5*x)+7*cos(4*x) 最大值
%}
clear ;
close all;
clc;

%% 函数图像显示
x1 = 0:0.01:10;
plot(x1,func1(x1))
xlabel("x")
ylabel("f(x)")
title("f(x)= x+10*sin(5*x)+7*cos(4*x)")

%% 参数设置
NP = 50;     %种群数量，即每一代中包含的个体数量
L = 20;      %二进制数串长度，用于对个体进行编码
Pc=0.8;      %交叉率，控制交叉操作的概率
Pm=0.1;      %变异率
G=100;       %最大遗传代数，即算法的迭代次数
Xs=10;       %变量x上限
Xx=0;        %变量x下限
f=randi([0,1],NP,L) ;%随机获得初始种群规模（NP*L的0-1矩阵）:f= randi([区间下限，区向上限],种群规模（行数）,编码长度（列数）

%预分配内存，提升运行速度（可有可无）
trace1=zeros(1,G);                  %历代最优适应度
trace2=zeros(1,G);                  %平均适应度
trace3=zeros(1,G);                  %最小适应度
x= zeros(1,NP);                     %解矩阵
Fit=zeros(1,NP);                    %适应度矩阵
nf=zeros(NP,L);                     %n次迭代种群

%% 遗传算法循环
for k=1:G 
    %% 将二进制解码为定义域范围内十进制
    for i=1:NP 
        U=f(i,:);                    %第一条染色体
        m=0;
        for j=1:L
            m=U(j)*2^(j-1)+m;        %将每个样本由二进制转变为十进制
        end
        x(i)=Xx+m*(Xs-Xx)/(2^L-1);   %将染色体解码到定义城
        Fit(i) = func1(x(i));        %计算每个样本的适应度
    end 
    maxFit=max(Fit);                 %最大值
    minFit=min(Fit);                 %最小值
    rr=find(Fit==maxFit);            %最大值在Fit数组中的位置，返回一个数组.
    fBest=f(rr(1,1),:);              %历代最优个体
    xBest=x(rr(1,1));                %最优适应度对应的染色体
    Fit=(Fit-minFit)/(maxFit-minFit);%归化适应度值
    
    %% 复制操作 （基于轮盘赌)
    sum_Fit=sum(Fit);                %计算种群中所有群近应值的和
    fitvalue=Fit./sum_Fit;           %计算每个种群的选择概率
    fitvalue=sum(fitvalue);          %计算每个种群的累计概率
    ms= sort(rand(NP,1));            %随机生成_(0,1)的有序概率密度NP大小向量,对生成的随机数进行升序排序
    fiti=1;
    newi=1;
    while newi<=NP                   %这是一种随机的复制方式，但总趋势是将适应度比较大的遗传下去
        if ms(newi)<fitvalue(fiti)  %随机新种群概率 < 种群选择概率
            nf(newi,:)= f(fiti,:);   %新种群的第newi行=此次选择的种群
            newi= newi+1;
        else
            fiti=fiti+1;
        end
    end
    
    %% 交叉操作 （基于概率）
    for i=1:NP-1
        p=rand ;                      %随机生成一个[0,1]的概率p
        if p<Pc                       %控制交叉的染色体总数
            q=randi([0,1],1,L);       %随机生成要交叉的基因位置
            for j=1:L
                if q(j)== 1            %f 此点f中值为1
                    temp=nf(i+1,j);    %记录此时选择过程中的新种群第i+1行。k列的值
                    nf(i+1,j)=nf(i,j); %新种群第i+1行。k列的值=新种群第i行。k列的值
                    nf(i,j)=temp;      %新种群第i行，k列的值=上面记录的值,即两条相邻染色体在指定位置进行交叉
                end
            end
        end
     end
           
      %% 变异操作（基于概率）
     i=1;
     while i<=round(NP*Pm)             %控制变异染色体总数
          h=randi([1,NP],1,1);         %随机选取一个需要变异的染色体
          for j= 1:round(L*Pm)         %控制变异染色体总数
              g=randi([1,L],1,1);      %随机需要变异的某因数
              nf(h,g)=~nf(h,g);
          end
          i=i+1;
     end
     
      f=nf;                           %新一代种群
      f(1,:)=fBest;                   %保留最优个体在新种群中
      trace1(k)=maxFit;               %历代最优适应度
      trace2(k)=mean(Fit);            %平均适度值
      trace3(k)=minFit;               %最小值
      
end

%% 迭代过程图形化展示
xBest;
figure
hold on
plot(1:k,trace1(1:k),'r')           %历代最优适应度
% plot(1:k,trace2(1:k),'b')         %平均适度值
% plot(1:k,trace3(1:k),'g')         %最小值
title('最优个体适应度','fontsize',12);
xlabel('进化代数','fontsize',12);
ylabel('适应度','fontsize',12);
legend('最大值','平均适应值','最小值')

%% 保存为GIF
frame= getframe(gcf);
imind= frame2im(frame);
[imind,cm]=rgb2ind(imind,256);
if i==1
    imwrite(imind,cm,'Z1.gif','gif','Loopcount',inf,'DelayTime',0);
else
    imwrite(imind,cm,'Z1.gif','gif','WriteMode','overwrite','DelayTime',0);
end

%% 结果打印
fprintf('最优个体编码：\n')
disp(fBest)
% 每次迭代最优值
fprintf('每次迭代最优值：\n')
disp(trace1)
% 每次迭代的平均适应度值
fprintf('每次迭代的平均适应度值：\n')
disp(trace2)
% 每次迭代的最差值
fprintf('每次迭代最差值：\n')
disp(trace3)
    
 
function y = func1(x)
%% 多极值函数
% x= 7.86  f(x)max=24.8534
y = x+10*sin(5*x)+7*cos(4*x);
end
      

 【使用AI工具DeepSeek一键转换为Python代码】

Python代码

import numpy as np
import matplotlib.pyplot as plt
from PIL import Image

def func1(x):
    return x + 10 * np.sin(5 * x) + 7 * np.cos(4 * x)

# 显示函数图像
x1 = np.arange(0, 10, 0.01)
y1 = func1(x1)
plt.plot(x1, y1)
plt.xlabel('x')
plt.ylabel('f(x)')
plt.title('f(x)=x+10*sin(5x)+7*cos(4x)')
plt.show()

# 参数设置
NP = 50        # 种群数量
L = 20         # 二进制串长度
Pc = 0.8       # 交叉率
Pm = 0.1       # 变异率
G = 100        # 遗传代数
Xs = 10        # x上限
Xx = 0         # x下限
f = np.random.randint(0, 2, (NP, L))  # 初始种群

trace1 = np.zeros(G)  # 历代最优适应度
trace2 = np.zeros(G)  # 平均适应度
trace3 = np.zeros(G)  # 最差适应度

# 遗传算法主循环
for k in range(G):
    # 解码并计算适应度
    x = np.zeros(NP)
    Fit = np.zeros(NP)
    for i in range(NP):
        U = f[i, :]
        m = sum(U[j] * (2 ** j) for j in range(L))  # 二进制转十进制
        x[i] = Xx + m * (Xs - Xx) / (2 ** L - 1)
        Fit[i] = func1(x[i])
    
    maxFit = np.max(Fit)
    minFit = np.min(Fit)
    rr = np.where(Fit == maxFit)[0]
    fBest = f[rr[0], :]
    xBest = x[rr[0]]
    
    # 归一化适应度
    if maxFit == minFit:
        Fit_normalized = np.ones(NP)
    else:
        Fit_normalized = (Fit - minFit) / (maxFit - minFit)
    
    # 轮盘赌选择
    sum_Fit = np.sum(Fit_normalized)
    if sum_Fit == 0:
        fitvalue = np.ones(NP) / NP
    else:
        fitvalue = Fit_normalized / sum_Fit
    cum_prob = np.cumsum(fitvalue)
    
    # 生成新种群
    nf = np.zeros_like(f)
    ms = np.sort(np.random.rand(NP))
    newi, fiti = 0, 0
    while newi < NP and fiti < NP:
        if ms[newi] < cum_prob[fiti]:
            nf[newi] = f[fiti]
            newi += 1
        else:
            fiti += 1
    
    # 交叉操作
    for i in range(NP - 1):
        if np.random.rand() < Pc:
            q = np.random.randint(0, 2, L)
            mask = q.astype(bool)
            # 交换相邻个体的基因
            temp = nf[i, mask].copy()
            nf[i, mask] = nf[i+1, mask]
            nf[i+1, mask] = temp
    
    # 变异操作
    num_mutants = int(round(NP * Pm))
    for _ in range(num_mutants):
        h = np.random.randint(0, NP)
        num_genes = int(round(L * Pm))
        genes = np.random.choice(L, num_genes, replace=False)
        nf[h, genes] = 1 - nf[h, genes]
    
    # 保留最优个体
    nf[0] = fBest
    f = nf.copy()
    
    # 记录数据
    trace1[k] = maxFit
    trace2[k] = np.mean(Fit)
    trace3[k] = minFit

# 绘制适应度变化曲线
plt.plot(trace1, 'r', label='Max Fitness')
#plt.plot(trace2, 'b', label='Average Fitness')
#plt.plot(trace3, 'g', label='Min Fitness')
plt.xlabel('Generation')
plt.ylabel('Fitness')
plt.title('Fitness Evolution')
plt.legend()
plt.show()

# 输出结果
print("Optimal solution x:", xBest)
print("Maximum fitness:", maxFit)