遗传算法（一）基本遗传算法(SGA)及MATLAB源码
发布时间
阅读量：
阅读量
遗传算法（Genetic Algorithm）作为一种广泛应用的智能优化技术，在理论和应用领域均取得了显著进展。该技术的核心在于模拟自然选择和基因重组的过程以实现全局优化，并已在多个领域展现出强大的适应能力与潜力。值得注意的是，《遗传算法GA(Genetic Algorithm)入门知识梳理》一文通过深入浅出的方式向读者介绍了这一基础概念及其核心原理，并在文章结尾附带的七个相关链接进一步激发了读者的兴趣。本文补充了自身对于遗传算法的理解分析，并提供了相应的代码实现。
//挖坑
- [笔记（一） 核心遗传算法]
- [笔记（二） 遗传算法的性能优化与改进]
- [笔记（三） 遗传算法在组合优化问题中的应用]
- [笔记（四） 基于MATLAB的遗传算法工具箱应用]
根据遗传算法基础知识，写出伪代码如下：
Initialization();
while less than maximum iterations
Crossover(parent, pCross) -> childrenCross
Mutation(parent, pMutation) -> childrenMutate
[childrenCross; cihldrenMutate] -> children
Calculate the fitness of children
select(children) -> parent
if Satisfy terminal condition
break
end
end总体流程较为直接，则是先建立初始种群，并对其进行交叉重组和变异操作；具体来说，则是先建立初始种群，并对其进行交叉重组和变异操作；随后通过模拟自然选择的机制筛选出适应度较高的个体；最后迭代上述步骤以生成下一代。在构建初始群体时需注意采用合适的编码策略（此处待完善）。
下面给出具体MATLAB代码实现：
%%
%编码方式： 基本二进制编码
%Input: FitFunc: Any function
% pCrossover: probability of crossover, default 0.5
% pMutation: probability of mutation, default 0.04
% GroupNum: number of individuals of the virtual group, default 30
% MaxIter: maximum iterations
% MaxRepeat: (optional)determine the convergence standard 判断收敛
%parent.fitness
%parent.chrom
function Result = MyGA(FitFunc, pCrossover, pMutation, GroupNum, MaxIter, MaxRepeat)
%Default parameters
if nargin < 6
MaxRepeat = 10;
if nargin < 5
MaxIter = 1000;
if nargin < 4
GroupNum = 50;
if nargin < 3
pMutation = 0.04;
if nargin < 2
pCrossover = 0.5;
end
end
end
end
end
Result = [];
epsilon = 1e-5;
iter = 0;
iRepeat = 1;
bit = 22;
thisMax = 0;
parent = InitGroup(GroupNum, FitFunc, bit); %Generate initial population
while iter < MaxIter
children1 = Crossover(parent, pCrossover/iter^0.1); %Return crossovered chromes
children.chrom = [];
children.fitness = [];
children.chrom = Mutation([parent.chrom; children1], pMutation/iter^0.1);
children.fitness = CalcFit(children.chrom, FitFunc, bit);
children = select(children, GroupNum);
parent = children;
iter = iter + 1;
%parent.chrom;
%[m, I] = max(parent.fitness)
if (thisMax-max(parent.fitness))/max(parent.fitness) < epsilon
iRepeat = iRepeat + 1;
else
iRepeat = 1;
end
thisMax = max(parent.fitness);
disp(thisMax)
Result = [Result; thisMax];
end
end
%Encoding method: 普通二进制编码
function parent = InitGroup(GroupNum, FitFunc, bit)
parent.fitness = [];
parent.chrom = [];
for i = 1:GroupNum
item = dec2bin(fix(rand*2^bit));
while size(item, 2) < bit
item = ['0', item];
end
parent.chrom = [parent.chrom; item];
end
parent.fitness = CalcFit(parent.chrom, FitFunc, bit);
end
%User Define 自定义解码方式
function Decode = Decoding(Population, bit)
Decode = bin2dec(Population) * 2 / (2^bit)+1;
end
%Calculate Fitness
function Fitness = CalcFit(Population, Fun, bit)
DecodedPop = Decoding(Population, bit);
Fitness = Fun(DecodedPop);
end
%roulette selcting method
function newPop = select(parent, PopNum)
%Add: The best survive?
cumFit = cumsum(parent.fitness)/sum(parent.fitness);
%[M, I] = max(parent.fitness);
%newPop.chrom(1,:) = parent.chrom(I, :);
%newPop.fitness = parent.fitness(I);
for i = 1 : PopNum
index = find (cumFit - rand > 0);
newPop.chrom(i,:) = parent.chrom(index(1),:);
newPop.fitness(i) = parent.fitness(index(1));
end
end
function childrenChrom = Crossover(parent, pCrossover)
[PopNum, bit] = size(parent.chrom);
childrenChrom = [];
%[M, I] = max(parent.fitness);
%childrenChrom = parent.chrom(I, :); %Parent with highest fitness
for i = 1 : PopNum/2
RandCross = rand(1);
if RandCross < pCrossover
i = fix(rand(1)*PopNum + 1);
j = fix(rand(1)*PopNum + 1);
while i == j
i = fix(rand(1)*PopNum + 1);
j = fix(rand(1)*PopNum + 1);
end
BreakPoint = fix(rand(1)*bit + 1);
temp = parent.chrom(i, 1:BreakPoint);
parent.chrom(i, 1:BreakPoint) = parent.chrom(j, 1:BreakPoint);
parent.chrom(j, 1:BreakPoint) = temp;
childrenChrom = [childrenChrom; parent.chrom(i, :); parent.chrom(j, :)];
end
end
end
function childrenChrom = Mutation(chrom, pMutation)
[PopNum, bit] = size(chrom);
childrenChrom = chrom;
for i = 1:PopNum
for j = 1:bit
if rand < pMutation
childrenChrom(i, j) = '1'-childrenChrom(i, j)+'0';
end
end
end
end解几个简单的例子
简单一元函数
在 [1,3] 区间上，用MATLAB求得在 x=2.0288 时函数有最大值 1.8197 。
该函数在整个定义域内仅存在一个极大值点，在这种情况下，采用遗传算法的方法能够较为简便地获得这一结果。
MyGA(@myFun)
其中myFun为上文所述的函数，即为遗传算法中的适应度函数。
MyGA(@myFun);
1.8185
1.8123
1.8184
1.8193
1.8193
1.8193
1.8193
1.8195
1.8196
1.8196
1.8196
1.8196
1.8196
1.8196
1.8194
1.8196
1.8196
1.8196
1.8197
1.8196
1.8196
1.8196
1.8197
1.8197
iter =
25选取一组代表样本输出结果。其中定义为算法收敛判定条件下的相对误差阈值epsilon，并设定其值为1\times 10^{-3}。
全部评论 (0)
还没有任何评论哟~