|
上一篇里介绍了遗传算法的理论知识，这一篇就是实践啦，都是特别简单适合初学者联系的例子。都是《智能优化算法及其MATLAB实例》里面的例子，加了一些个人的理解，就当是简单讲解一下吧。没有书的小伙伴可以借鉴一下。
例1：计算函数
的最小值，其中个体x的维数n=10，这是一个简单的平方和函数，只有一个极小点x=（0,0,...,0），理论上最小值分f(0,0,...,0)=0。
解：
（1）这里的选择和交叉我们选择的是‘君主方案’，就是根据群体适应度值高低排序的基础上，用最优个体与其他偶数位的所有个体进行交叉每次交叉产生两个新个体，交叉后对新产生的群体进行多点变异产生新群体，再计算其适应度值，然后和父群合并，按照适应度值进行排序，选择前NP个个体为新群体。
（2）还有一个办法使用了谢菲尔德大学遗传算法工具箱基于遗传算法的随机优化搜索，也挺好用的，这里给大家分享了网盘地址链接：pan.baidu.com/s/1Yw3xupItO3oQL9DHbYT4kQ
提取码：d2hu
有需要的可以直接下载，解压之后直接复制到toolbox里面就可以了。还有这个博客介绍了这个工具箱的用法，非常详细
接下来的程序还是主要是比较容易理解的书上的例子。首先初始化参数：
clear all;
close all;
clc;
D=10; %基因数目
NP=100; %染色体数目
Xs=20; %上限
Xx=-20; %下限
G=1000; %最大遗传代数
f=zeros(D,NP); %初始种群赋空间
nf=zeros(D,NP); %子种群赋空间
Pc=0.8; %交叉概率
Pm=0.1; %变异概率
f=rand(D,NP)*(Xs-Xx)+Xx; %随机获得初始种群
接下来是将适应度升序排列用到了sort这个函数
%按适应度升序排列
for np=1:NP
MSLL(np)=func2(f(:,np));
end
[SortMSLL,Index]=sort(MSLL);
Sortf=f(:,Index);
这个里面我再提一句这个sort函数，它使MSLL中的元素按升序排列，SortMSLL里面是排好的，Index里是标号，举个栗子:
A=[3 6 5; -7 2 4;10 -9]
[aa,bb]=sort(A)
aa=[3 5 6;-7 2 4;-9 0 1];
bb=[1 3 2;1 2 3;3 2 1];
如果想要降序排列sort(A,'desend')就可以了。
%遗传算法循环
for gen=1:G
%采用主君方案进行选择交叉操作
Emper=Sortf(:,1); %君主染色体
Nopoint=round(D*Pc); %每次交叉点的个数
Popoint=randi([1,D],Nopoint,NP/2); %交叉基因的位置
nf=Sortf;
for i=1:NP/2
nf(:,2*i-1)=Emper;
nf(:,2*i)=Sortf(:,2*i);
for k=1:Nopoint
nf(Popoint(k,i),2*i-1)=nf(Popoint(k,i),2*i);
nf(Popoint(k,i),2*i)=Emper(Popoint(k,i));
end
end
%变异操作
for m=1:NP
for n=1:D
r=rand(1,1);
if r
例2：旅行商问题（TSP问题）。假设有一个旅行商人要拜访全国31个省会城市，他需要选择所有需要走的路径，路径的限制是每一个城市只能拜访一次，而且要回到原来出发的城市，对路径的要求是为所有路径中的最小值。
全国31个省会城市的坐标为
[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...
3238 1229;4196 1044;4312 790;4386 570;3007 1970;2562 1756;...
2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;...
3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;...
3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;...
2370 2975];
解：选择基于概率的方式进行选择操作，对于选中的成对个体，随机交叉所选中的成对坐标，以确保每个城市只到达一次，对于选中的单个个体，随机交换一对城市坐标作为变异操作，产生新种群。
首先还是初始化：
clear all;
close all;
clc;
C=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...
3238 1229;4196 1044;4312 790;4386 570;3007 1970;2562 1756;...
2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;...
3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;...
3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;...
2370 2975]; %31个省会城市坐标
N=size(C,1); %TSP问题的规模，即城市数目
D=zeros(N); %任何两个城市距离间隔矩阵
%求任意两个城市距离间隔矩阵
for i=1:N
for j=1:N
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
end
end
NP=200; %种群规模
G=1000; %最大遗传代数
f=zeros(NP,N); %用于储存种群
F=[]; %种群更新中间储存
for i=1:NP
f(i,:)=randperm(N); %随机生成初始种群
end
R=f(1,:); %存储最优解
len=zeros(NP,1); %存储路径长度
fitness=zeros(NP,1); %存储归一化适应度值
gen=0;
%遗传算法循环
while gen=rand
nn=nn+1;
F(nn,:)=f(i,:);
end
end
[aa,bb]=size(F);
while aaNP
F=F(1:NP,:); %保存种群规模为NP
end
f=F; %更新种群
f(1,:)=R; %保留每代最优个体
clear F;
gen=gen+1;
Rlength(gen)=minlen;
end
figure
for i=1:N-1;
plot([C(R(i),1),C(R(i+1),1)],[C(R(i),2),C(R(i+1),2)],'bo-');
hold on;
end
plot([C(R(N),1),C(R(1),1)],[C(R(N),2),C(R(1),2)],'ro-');
title(['优化最短距离:',num2str(minlen)]);
figure
plot(Rlength)
xlabel('迭代次数')
ylabel('目标函数值')
title('适应度进化曲线')
这个题比较特别的就是使用了主君方案进行交叉，步骤的话都还比较容易理解。
例3:0-1背包问题，有N件物品和容积为V的包，第i件物品的容积是c(i),价值是w(i)，求将这些物品放入包中，使物体的总容积不超过背包容积，且总价值和最大。假设物品数量为10，背包容量为300.每件物品的体积为[95,75,23,73,50,22,6,57,89,98];价值为[89,59,19,43,100,72,44,16,7,64];
解：产生二进制初始种群，1表示选择该物品，0表示不选择。适应度值为所选物品价值的和，当总体积大于背包容积时，进行惩罚计算。
选择操作用的还是上一篇文章中介绍过的‘轮盘赌’的方法，和基于概率的交叉和变异工作。
clear all;
close all;
clc;
NP=50; %种群规模
L=10; %物品件数
Pc=0.8; %交叉率
Pm=0.05; %变异率
G=100; %最大遗传代数
V=300; %背包容量
C=[95,75,23,73,50,22,6,57,89,98]; %物品体积
W=[89,59,19,43,100,72,44,16,7,64]; %物品价值
afa=2; %惩罚函数系数
f=randi([0,1],NP,L); %随机获得初始种群
%遗传算法循环
for k=1:G
%适应度计算你
for i=1:NP
Fit(i)=func4(f(i,:),C,W,V,afa);
end
maxFit=max(Fit); %最大值
minFit=min(Fit); %最小值
rr=find(Fit==maxFit);
fBest=f(rr(1,1),:); %历代最优个题
Fit=(Fit-minFit)/(maxFit-minFit); %归一化适应度值
%基于轮盘赌的复制操作
sum_Fit=sum(Fit);
fitvalue=Fit./sum_Fit; %选择概率
fitvalue=cumsum(fitvalue); %累计概率
ms=sort(rand(NP,1)); %随机生成NP个0-1之间的数
fiti=1;
newi=1;
while newi<=NP %转盘转NP次
if (ms(newi))
优化结果为[1 0 1 0 1 1 1 0 0 1],价值总和为388.
要说的都写在注释里啦，这个例子比较好理解。
因为这些算法里用到了很多随机生成的量作为输入量，除了最后一个例子，其他两个例子每次运行的结果都会有些差别，但是大概还是稳定在一定范围内的，但是像第二个例题每次的差别还是有一丢丢大我觉得，这也刚好体现出了遗传算法局部搜索能力不一定是最好的，还有‘早熟’等缺陷。并不是适用于所有问题。
（编辑：通辽站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
