主题 作者
新成员
- 09
- 12
- 0
- 文章类型
- 完全原创 —— 转载请标注作者
遗传算法（GA）原理与代码实现
一、算法简介遗传算法（Genetic Algorithm, GA）是一种模仿自然界中生物进化原理的搜索和优化算法。其基础在于达尔文的自然选择理论，即“适者生存”，并结合了遗传学中的基因突变、交叉重组等概念。遗传算法在多种复杂的优化问题中表现出了强大的适用性和灵活性。它通过模拟自然选择过程中最适合生存的个体传递其基因来求解优化问题。
二、基本组成要素
1. 个体和种群
个体（Individual）：在 GA 中，每个潜在的解决方案被称为一个“个体”。这些个体代表了问题的不同解决方案。
种群（Population）：由一定数量的个体组成，代表了解决方案的搜索空间。每个个体通常由一个数据结构（如字符串、向量）表示，称为“染色体”。
2. 适应度函数（Fitness Function）
适应度函数：这是一个评估个体优劣的关键函数。适应度函数的输入是个体的染色体，输出是个体的适应值，这个值反映了个体解决问题的能力。
3. 遗传操作
选择（Selection）：模拟自然界中的“适者生存”原则，根据个体的适应度选择较优个体进行繁殖。
交叉（Crossover）：在两个个体（父代）之间交换基因信息，生成新的个体（后代）。这模拟了生物的性繁殖过程。
变异（Mutation）：随机更改个体的部分基因，模拟生物遗传过程中的突变现象。
三、算法流程
1. 编码：将问题的解转换成一种适合遗传操作的编码形式，如二进制编码，实数编码，整数编码，符号编码。
2. 初始化：随机生成初始种群。
3. 适应值评估：为每个个体计算适应值。
4. 选择操作：根据适应值进行选择，优秀个体（高适应值个体）有更高的被选中概率。
5. 交叉操作：通过交叉操作产生新的后代。
6. 变异操作：随机变异某些个体的基因。
7. 种群更新：用新生成的后代替换当前种群。
8. 终止条件：达到最大迭代次数或其他终止条件时停止。
四、代码实现（Matlab）
背景：求解一个二次函数（一维函数）在[imath][-10,10][/imath]的最优解
一、适应值函数设置
设置评估适应值的函数，可自行设置。
代码：
function Fitness = GetFits(Population)
Function = @(x) -(x-5).^2; % y = -(x-5)^2
Fitness = Function(Population);
end二、参数设置
问题中用到的参数，为了方便展示我单独列了出来。
代码：
%% 参数设置
function Para = ParaSet()
% 问题的上下界
lb = -10;
ub = 10;
PopSize = 100; % 种群大小
Itermax = 100; % 迭代次数
CrossRate = 0.5;
MutationRate = 0.5; % 变异概率
MutationRange = 0.5; % 变异步长
Para = struct();
Para.lb = lb;
Para.ub = ub;
Para.PopSize = PopSize;
Para.Itermax = Itermax;
Para.CrossRate = CrossRate;
Para.MutationRate = MutationRate;
Para.MutationRange = MutationRange;
end有很多初始化的方法，有兴趣可以自己去了解。这里只用随机函数[imath][lb,ub][/imath]生成种群。
代码：
function Population = Initialization(PopSize,lb,ub)
Population = lb + (ub-lb)*rand(PopSize,1); % 在[lb,ub]范围内生成PopSize个个体
end这里我们采用的是轮盘赌的选择方法，适应值最高的个体有更高的被选中概率。
值得注意的是，由于个体的适应值可能是负值，对概率的计算可能有一定影响，所以我们将他映射到大于 [imath]0[/imath] 的区域来算概率。
计算概率公式：第[imath]i[/imath]个个体被选中的概率：
[imath]P_i[/imath] = ([imath]F_i[/imath]-min(F))/(sum(F-min(F))。
其中 F 为该种群的适应值。
代码：
function select = Selection(Population,Fitness)
%% 轮盘赌
% 计算每个个体被选中的概率
probabilities = (Fitness-min(Fitness))/sum((Fitness-min(Fitness)));
len = size(Fitness,1);
% 有放回的随机采样len个个体，其中概率越高的个体被选中的概率越大。
select = randsample(Population,len,true,probabilities);
end五、交叉操作
交叉操作方法有很多种，如单点交叉，k 点交叉，均匀交叉。本文采用的是单点交叉方法，即随机选择一个交叉点，交换两个个体（父代）交叉点后边的基因信息。
注：在本实例中维度为 1，即基因长度为 1，所以不进行交叉操作。
代码：
function crossed = Crossover(Population,CrossRate)
PopSize = size(Population,1);
GeneLen = size(Population,2);
%% 如果基因长度为1，则不需要交叉操作(没的交叉操作)
if GeneLen <= 1
crossed = Population;
return
end
%% 这里对相邻两个个体按照交叉概率进行单点交叉操作，可以自行设计
crossed = size(Population);
for i = 1:2:PopSize % 每俩个成对进行交叉操作
parent1 = Population(i,:);
parent2 = Population(mod(i+1,PopSize),:); % 防止数组下标溢出
% 交叉概率
if rand > CrossRate % rand为一个[0,1)的随机值，用来判断是否交叉
% 并没有进行交叉操作
continue;
else
% 选择交叉点
crossoverPoint = randi([1,GeniLen-1]);
crossed(i, :) = [parent1(1:crossoverPoint), parent2(crossoverPoint+1:end)];
crossed(mod(i+1, popSize) + 1, :) = [parent2(1:crossoverPoint), parent1(crossoverPoint+1:end)];
end
end
end同样的，变异方法也有很多种，我们这还是选择讲解最简单的且适合这个实例（实数编码）的一种变异操作方法：对选定位上的数值进行小的随机改变。
代码：
function mutated = Mutation(Population, MutationRate,MutationRange)
% 判断每个基因位置是否需要变异
mutationMask = rand(size(Population)) < MutationRate;
[PopSize,GeneLen] = size(Population);
% 对需要变异的基因位置进行小的随机改变
mutationVal = MutationRange*(rand(PopSize,GeneLen)-0.5); % MutationRange为变异步长,因为rand的范围为[0,1),所以“-0.5”来控制变异区间在[-0.5,0.5)这个对称区间里。
mutated = Population + mutationMask.*mutationVal;
end七、整体代码实现
代码：
function Genetic_Algorithm()
%% 参数设置
Para = ParaSet();
lb = Para.lb;
ub = Para.ub;
PopSize = Para.PopSize;
Itermax = Para.Itermax;
CrossRate = Para.CrossRate;
MutationRate = Para.MutationRate;
MutationRange = Para.MutationRange;
Bestmem = nan;
Bestval = -inf;
%% 初始化种群
Population = Initialization(PopSize,lb,ub);
%% 评估初始种群的适应值
Fitness = GetFits(Population);
%% 迭代进化
for iter = 1:Itermax
% 选择操作
select = Selection(Population,Fitness);
% 交叉操作
cross = Crossover(select,CrossRate);
% 变异操作
mutation = Mutation(cross, MutationRate, MutationRange);
% 更新种群
Population = mutation;
Fitness = GetFits(Population);
% 输出最佳解
[bestval, bestindex] = max(Fitness);
if bestval > Bestval
Bestmem = Population(bestindex,:);
Bestval = bestval;
end
disp(['Current Best Solution: ', num2str(Bestmem)]);
disp(['Current Best Fitness: ', num2str(Bestval)]);
fprintf('---Iter %d---\n',iter);
end
disp(['Global Best Solution: ', num2str(Bestmem)]);
disp(['Global Best Fitness: ', num2str(Bestval)]);
end五、实例结果
Current Best Solution: 5
Current Best Fitness: -3.1471e-10
---Iter 100---
可以看出来 100 代足以找到最优解（5,0）并且达到了一个很高的精度，事实上对于这种简单问题，并不需要这么多代，所以可以减少迭代次数或者另设终止条件。
六、总结与评价
1. 这个代码实现了 GA 算法的基本流程，包括初始化种群、选择操作、交叉操作、变异操作、迭代进化。
2. 代码中的各种遗传操作都是最基础的，但是很经典，现在已经有很多 GA 变体了，有兴趣的可以去了解学习，也欢迎联系我进行交流。
3. 原理理解就行，会写代码就行。
4. 下篇预告：ES?DE?PSO?
最后编辑：
