智能优化算法（三）：遗传算法

1.问题描述

\quad 在利用启发式算法求解问题时，我们常常需要应用遗传算法解决函数最值问题，也是遗传算法在数学中最常应用到的方面，遗传算法的思想是通过种群的迭代最后求解出某一函数的最值 (最大值/最小值) 或者极值 (极大值与极小值)，具体的问题描述与见下文。
\quad 利用二进制编码的遗传算来求解函数优化问题:
$$\max f(x)=x+10\sin (5x)+7\cos (4x)\text{s.t.x}\in [0,10]$$

2.遗传算法

2.1.算法概述

\quad 遗传算法（Genetic Algorithm, GA）是一种基于自然选择和遗传学原理的优化算法。它模仿了生物进化过程，通过模拟自然选择、交叉、变异等遗传操作，逐步优化问题的解。遗传算法是进化算法的一种，广泛应用于优化问题、机器学习、人工智能等领域。
\quad 其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。
\quad 遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

2.2.编码操作

\quad 遗传算法的解空间与编码空间的可能需要进行适当的转换，也就是说适值计算需要在解空间内进行，而遗传运算是对编码空间操作的，所以要进行两个空间的转换,单体的数值的转化如图1所示，常常利用二进制编码与十进制编码的转化方法，同时整体种群的变异，交叉等操作都需要在二进制编码上进行，如图2所示。

2.3.选择操作

\quad 在遗传算法每一代的遗传方面，就涉及到了选择操作，选择概率的计算方法，按比例的适应度函数、基于排序的适应度计算等，其中选择算法有轮盘赌选择、随机遍历抽样、截断选择、锦标赛选择等方法，我们最常利用轮盘赌方法来进行选择操作。
\quad 轮盘赌选择（Roulette Wheel Selection）是一种遗传算法中常用的选择方法。它的基本思想是根据个体的适应度值来决定其被选择的概率，类似于在轮盘上抽签。首先，我们计算种群中每个个体的适应度值，适应度值反映了个体在当前问题中的表现。然后，将这些适应度值归一化，转换为每个个体的选择概率，确保所有个体的选择概率加起来等于1。接着，计算累积概率（即累积适应度值），每个个体的累积概率表示从第一个个体到当前个体的总选择概率。然后在选择个体时，生成一个0到1之间的随机数r，然后通过比较这个随机数与累积概率，确定选择的个体。如果随机数r小于某个累积概率CDF_i，则选择对应的第i个个体。这样，每个个体被选择的概率与其适应度成正比，适应度越高的个体被选择的概率越大。

2.4.交叉操作

\quad 交叉（Crossover）是指在遗传算法中，一对父代个体发生染色体交叉交换的操作，交叉发生的概率叫做交叉率，通常用Pc表示，常设定为0.8至0.9。根据编码方式的不同，交叉操作有多种形式：对于二进制和整数编码，常见的交叉方法包括单切点交叉、双切点交叉和均匀交叉；对于顺序编码，则使用部分映射交叉、顺序交叉和循环交叉；对于实数编码，则包括离散交叉和线性重组等方法。

\quad 其中，单切点交叉（Single-Point Crossover） 是最基础的一种交叉方法，适用于二进制和整数编码。在单切点交叉中，首先在父代个体的基因序列中随机选择一个切点，然后将两个父代个体在该切点处分开，交换彼此的基因部分，以生成新的子代个体。例如，假设有两个父代个体A和B，切点选择在第k位，那么子代个体C和D的基因序列将是父代个体A和B在切点k处分开的部分进行交换，从而生成新的个体。单切点交叉的优点是实现简单，能够有效地在基因之间进行信息重组，促进解空间的探索。

2.5.变异操作

\quad 变异率（Mutation Rate），用Pm表示，是遗传算法中控制染色体上基因发生变异的概率，通常设置得较小，一般在0.05以下，以维持种群的稳定性。变异操作首先需要根据变异率Pm，随机选择NPPm个个体进行变异，其中NP是种群大小。对于每个被选中的个体，再随机选择round(LPm)个基因进行变异，将这些基因的值进行取反，即0变成1，1变成0。最终，将变异后的个体更新到种群中，并保留最优个体fBest在新种群中，以确保最优解不会丢失。这种变异操作通过引入基因的多样性，帮助算法避免陷入局部最优解，同时保持种群的优秀特征。

2.6.算法流程

\quad 遗传算法的基本流程包括几个关键步骤。首先，生成初始种群，通过随机方式创建一组个体。接下来，计算每个个体的适应度值，评估其在目标函数中的表现。然后，根据适应度值选择个体进入下一代，常用的选择方法包括轮盘赌选择和锦标赛选择。选择后的个体进行交叉操作，模拟基因重组，生成新的子代个体。接着，对新生成的个体进行变异操作，引入基因变异，以增加种群的多样性。更新种群时，将新个体与旧种群结合，可能需要替换一些旧个体，并保留最优个体以确保优秀基因的传递。最后，检查是否满足终止条件，如达到最大代数或适应度收敛，若满足条件则结束算法，输出当前代中最优个体作为近似解。这些步骤帮助遗传算法逐步优化解的质量，并在复杂的解空间中寻找最优解。

3.算法实现

3.1.MATLAB代码实现

%%%%%%%%%%%%%%%%%%%%标准遗传算法求函数极值%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%初始化参数%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all; %清除所有变量
close all; %清图
clc; %清屏
tic;
NP=100; %种群数量
L=20; %二进制数串长度
Pc=0.8; %交叉率
Pm=0.7; %变异率
G=100; %最大遗传代数
Xs=10; %上限
Xx=0; %下限
%编码方式采用二进制编码方法
f=randi([0,1],NP,L); %随机获得初始种群
%%%%%%%%%%%%%%%%%%%%%%%%%遗传算法循环%%%%%%%%%%%%%%%%%%%%%%%%
for k=1:G
%%%%%%%%%%%%将二进制解码为定义域范围内十进制%%%%%%%%%%%%%%
for i=1:NPU=f(i,:);m=0;for j=1:L%将二进制编码转化为十进制m=U(j)*2^(j-1)+m;end%将解码结果映射到[Xx,Xs]区间x(i)=Xx+m*(Xs-Xx)/(2^L-1);Fit(i)= func2(x(i));%带入值进行计算
endmaxFit=max(Fit); %最大值
minFit=min(Fit); %最小值
rr=find(Fit==maxFit);%获取最优结果对应的索引
fBest=f(rr(1,1),:); %历代最优个体
xBest=x(rr(1,1));%获取最好的结果
Fit=(Fit-minFit)/(maxFit-minFit); %归一化适应度值
%%%%%%%%%%%%%%%%%%基于轮盘赌的复制操作%%%%%%%%%%%%%%%%%%%
sum_Fit=sum(Fit);
fitvalue=Fit./sum_Fit;%将适应度转化为被选择的概率
fitvalue=cumsum(fitvalue);%变成当前被选择时的累计概率
ms=sort(rand(NP,1));%生成随机数
fiti=1;newi=1;
%轮盘赌选择个体
while newi<=NPif (ms(newi))<fitvalue(fiti)nf(newi,:)=f(fiti,:);newi=newi+1;elsefiti=fiti+1;end
end
%%%%%%%%%%%%%%%%%%%%%%基于概率的交叉操作%%%%%%%%%%%%%%%%%%
for i=1:2:NP%简单地随机交叉操作p=rand;%随机生成一个p如果p小于pc，执行交叉操作，反正不执行。if p<Pc%随机选择交叉的位置q=randi([0,1],1,L);for j=1:Lif q(j)==1;temp=nf(i+1,j);nf(i+1,j)=nf(i,j);nf(i,j)=temp;endendend
end
%%%%%%%%%%%%%%%%%%%基于概率的变异操作%%%%%%%%%%%%%%%%%%%%%%%
i=1;while i<=round(NP*Pm)%随机选择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);%0,1的位置取反endi=i+1;endf=nf;f(1,:)=fBest; %保留最优个体在新种群中trace(k)=maxFit; %历代最优适应度
end
xBest; %最优个体
figure
plot(trace)
xlabel('迭代次数')
ylabel('目标函数值')
title('适应度进化曲线')
print(gcf,'C:\Users\Zeng Zhong Yan\Desktop\GA','-dpng','-r600')

3.2.Python代码实现

import numpy as np
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['Times New Roman'] # 用来正常显示中文标签
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号
# 定义优化的目标函数
def func1(x):return x + 10 * np.sin(5 * x) + 7 * np.cos(4 * x)# 初始化参数
NP = 100  # 种群大小
L = 20  # 二进制字符串的长度
Pc = 0.8  # 交叉率
Pm = 0.9  # 变异率
G = 50  # 最大代数
Xs = 10  # 上界
Xx = 0  # 下界# 生成初始种群
f = np.random.randint(0, 2, (NP, L))# 遗传算法循环
trace = np.zeros(G)
for k in range(G):# 将二进制字符串解码为十进制数x = 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 = np.array([func1(xi) for xi in x])maxFit = np.max(Fit)minFit = np.min(Fit)rr = np.where(Fit == maxFit)[0]fBest = f[rr[0], :]  # 记录当前代的最优个体xBest = x[rr[0]]# 归一化适应度值Fit = (Fit - minFit) / (maxFit - minFit)# 轮盘赌选择sum_Fit = np.sum(Fit)fitvalue = Fit / sum_Fitfitvalue = np.cumsum(fitvalue)  # 计算累积适应度值ms = np.sort(np.random.rand(NP))  # 生成并排序随机数new_population = np.zeros_like(f)fiti = 0newi = 0while newi < NP:if ms[newi] < fitvalue[fiti]:new_population[newi, :] = f[fiti, :]newi += 1else:fiti += 1# 交叉操作for i in range(0, NP, 2):if np.random.rand() < Pc:q = np.random.randint(0, 2, L)for j in range(L):if q[j] == 1:new_population[i, j], new_population[i+1, j] = new_population[i+1, j], new_population[i, j]# 变异操作for i in range(round(NP * Pm)):h = np.random.randint(0, NP)for j in range(round(L * Pm)):g = np.random.randint(0, L)new_population[h, g] = 1 - new_population[h, g]f = new_populationf[0, :] = fBest  # 保留最优个体在新种群中trace[k] = maxFit  # 记录每代的最优适应度值print("最优个体:", xBest)# 绘制适应度进化曲线
plt.plot(trace)
plt.xlabel('The number of iterations',fontsize=14)
plt.ylabel('The value of the objective function',fontsize=14)
plt.title('Fitness Evolution Curve ',fontsize=18)
plt.savefig('GA.svg', dpi=600,bbox_inches='tight')
plt.show()

4.参考文献

[1]https://blog.csdn.net/LOVEmy134611/article/details/111639624
[2]https://blog.csdn.net/zyx_bx/article/details/115188782
[3]https://baike.baidu.com/item/
[4]https://chatgpt.com/