当前位置：首页 > news >正文

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

news 来源：原创 2025/5/20 2:58:10

一、遗传算法基础知识

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

1、遗传算法

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

2、模式定理

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

3、遗传算法的本质

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

多个字符串隐藏着多个不同的模式，长度为L的字符串，隐藏着 $2^{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，则他被选取的概率为:

$pi=fi/\sum_{i=1}^{NP}fi$

个体适应度越大，被选择的机会越大，为了选择交叉个体，需要进行多轮选择，每一轮产生一个[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:Lm=U(j)*2^(j-1)+m;        %将每个样本由二进制转变为十进制endx(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;elsefiti=fiti+1;endend%% 交叉操作 （基于概率）for i=1:NP-1p=rand ;                      %随机生成一个[0,1]的概率pif p<Pc                       %控制交叉的染色体总数q=randi([0,1],1,L);       %随机生成要交叉的基因位置for j=1:Lif q(j)== 1            %f 此点f中值为1temp=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列的值=上面记录的值,即两条相邻染色体在指定位置进行交叉endendendend%% 变异操作（基于概率）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);endi=i+1;endf=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==1imwrite(imind,cm,'Z1.gif','gif','Loopcount',inf,'DelayTime',0);
elseimwrite(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 Imagedef 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) / NPelse:fitvalue = Fit_normalized / sum_Fitcum_prob = np.cumsum(fitvalue)# 生成新种群nf = np.zeros_like(f)ms = np.sort(np.random.rand(NP))newi, fiti = 0, 0while newi < NP and fiti < NP:if ms[newi] < cum_prob[fiti]:nf[newi] = f[fiti]newi += 1else: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] = fBestf = nf.copy()# 记录数据trace1[k] = maxFittrace2[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)