【布局优化】基于遗传算法的的无线传感器网(WSN)覆盖优化Matlab源码

2021-12-20 09:38:07

一、WSN模型

二、遗传算法

• 遗传算法（Genetic Algorithm，GA）是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则，它最初由美国Michigan大学的J. Holland教授于1967年提出。 • 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。因此，第一步需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

• 遗传算法有三个基本操作：选择（Selection）、交叉（Crossover）和变异（Mutation）。 • （1）选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁衍子孙。根据各个个体的适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代种群中。选择的依据是适应性强的个体为下一代贡献一个或多个后代的概率大。 • （2）交叉。通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。将群体中的各个个体随机搭配成对，对每一个个体，以交叉概率交换它们之间的部分染色体。 • （3）变异。对种群中的每一个个体，以变异概率改变某一个或多个基因座上的基因值为其他的等位基因。同生物界中一样，变异发生的概率很低，变异为新个体的产生提供了机会。

遗传算法的基本步骤：

1)编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的丌同组合便构成了丌同的点。 2)初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始进化。 3)适应度评估：适应度表明个体或解的优劣性。丌同的问题，适应性函数的定义方式也丌同。

4)选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择体现了达尔文的适者生存原则。 5)交叉：交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。 6)变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样， GA中变异发生的概率很低，通常取值很小。

遗传算法工具箱：

• MATLAB内嵌遗传算法工具箱: gadst • Sheffield大学遗传算法工具箱: gatbx • 北卡罗来纳大学遗传算法工具箱: gaot

initializega函数：

ga函数：

遗传算法优化BP神经网络初始权值与阈值：

三、代码

%%遗传算法主函数
clc;
clear all;
close all;
warning off

%%遗传算法参数
maxgen=200; %进化代数，也即是迭代次数
sizepop=20; %种群规模，个体数，也即是染色体数
pcross=[0.6];   %交叉概率，[0,1]之间为什么写成数组的形式？
pmutation=[0.01];%变异概率，【0,1】之间
lenchrom=[1 1 1 1 1];%每个变量的字符串长度，如果是浮点型变量，则长度都为1
bound=[0,0.9*pi;
    0,0.9*pi;
    0,0.9*pi;
    0,0.9*pi;
    0,0.9*pi];

%%个初始化
individuals=struct('fitness',zeros(1,sizepop),'chrom',[]);%种群结构体
avgfitness=0;%种群平均适应度
bestfitness=0;%种群最佳适应度
bestchrom=[];%适应度最好的染色体
bf=[];%记录种群最佳适应度
af=[];%记录种群平均适应度

%%初始化种群
for i=1:sizepop
    individuals.chrom(i,:)=Code(lenchrom,bound);%随机产生一个种群
    x=individuals.chrom(i,:);
    individuals.fitness(i)=fun(x);%计算染色体适应度
end        %以上完成了初始化种群，并计算了初始化种群每个个体的适应度

%%找最好的染色体
[bestfitness bestindex]=min(individuals.fitness);%得到初始化种群的最小的适应度函数值和位置。（函数值最小，那么倒数也就是适应度就最大,在轮盘赌操作的时候再去倒数）
bestchrom=individuals.chrom(bestindex,:);%适应度最好，也就是函数值最小的染色体编号
avgfitness=sum(individuals.fitness)/sizepop;%染色体平均适应度
trace=[];%记录每一代进化中最好的适应度和平均适应度，可以用来绘图反映是否过早收敛

%%进化开始
for i=1:maxgen
    %选择
    individuals=Select(individuals,sizepop);%返回被选中的染色体sizepop条和对应被选中染色体的适应度
    avgfitness=sum(individuals.fitness)/sizepop;%经过选择之后的种群的平均适应度
    %交叉
    individuals.chrom=Cross(pcross,lenchrom,individuals.chrom,sizepop,bound);%返回交叉后的染色体群
    %变异
    individuals.chrom=Mutation(pmutation,lenchrom,individuals.chrom,sizepop,[i,maxgen],bound);
    
    %%非线性寻优，可以被注释掉，注释掉之后就是一般的遗传算法
    %每进化10代，以所得值为初始值进行非线性寻优，这是将遗传算法和非线性规划的函数寻优算法结合起来，nonlinear
    if(mod(i,10)==0)
        individuals.chrom=nonlinear(individuals.chrom,sizepop);
    end
    
    %%计算适应度
    for j=1:sizepop
        x=individuals.chrom(j,:);       
        individuals.fitness(j)=fun(x);
    end
    
    %找到最优染色体及他们在种群中的位置
    [newbestfitness,newbestindex]=min(individuals.fitness);
    
    %进行更新，代替上一次进化中最好的染色体
    if bestfitness>newbestfitness       %如果新一代染色体的函数值小，也就是适应度高
        bestfitness=newbestfitness;     %那么把新的适应度赋值给bestfitness
        bestchrom=individuals.chrom(newbestindex,:);%把新的当前最好的染色体给bestchrom
    end
    avgfitness=sum(individuals.fitness)/sizepop;
    
    bf=[bf bestfitness];
    af=[af avgfitness];
    
    %trace=[trace,avgfitness bestfitness];%记录每一代进化中最好的适应度和平均适应度
end %进化结束

%绘制图像分析
[r,c]=size(bf);
plot([1:c],bf,'r-',[1:c],af,'b--','LineWidth',2);
title(['函数值曲线' '终止代数=' num2str(maxgen)]);
xlabel('进化代数');
ylabel('函数值');
ylim([1.5 8]);
legend('各代最佳值','各代平均值');
disp('函数值            变量');
grid on
%窗口显示
disp([bestfitness x]);

% %绘制图像分析
% [r c]=size(trace);%计算trace的行列
% figure(1)
% plot([1:r]',trace(:,1),'r-',[1:r]',trace(:,2),'b--');
% title(['函数值曲线' '终止代数=' num2str(maxgen)]);
% xlabel('进化代数');
% ylabel('函数值');
% legend('各代平均值','各代最佳值');
% disp('函数值            变量');
% grid on
% %窗口显示
% disp([bestfitness x]);

四、参考文献

完整代码下载https://www.cnblogs.com/ttmatlab/p/14882966.html

码农公寓