遗传算法matlab程序实例,遗传算法的matlab程序示例
遗传算法matlab程序实例，遗传算法matlab程序实例没错，“遗传交配”也可以做成算法。想想我们的进化史，海洋是我们的家园！从海洋生物到陆地生物，从简单生物到复杂生物.我不禁想起了生物的高考考点。基因、染色体、交配、突变.这些都造成了生物的进化。也许是一种优化算法，——遗传算法(GA)，来源于达尔文的进化论。这个算法是我目前最容易理解的。
1.遗传算法简介
遗传算法是由美国教授约翰霍兰德于1975年提出的。它是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法。它有着蓬勃的“适者生存”和“适者生存”的精。遗传算法常用于解决传统搜索算法无法解决的复杂非线性优化问题。
2.遗传算法的核心概念
我们先来补一下生物书的简单知识：
个体：这个概念很简单，就是我一个人，一个人叫做个体。遗传算法中的个体意味着拥有一套完整染色体的解。
群体：作为一个群体，我们人类是可以相互交配的，所以在理想情况下，不同群体是不可能交配的，也就是不同群体之间的进化过程并不是没有干扰的。
基因：染色体中的一个单位，也可以称为特征成分。
染色体：在生物学上，可以简单理解为只有发生交配，染色体才会发生变化，即只有发生交配，种群的染色体类型才会更加多样化，种群才能进化。在遗传算法中，解释为根据问题类型编码形成的向量或字符串。
编码方式：二进制编码、浮点编码、十进制编码、有序串编码、结构编码等。如果TSP问题与所访问城市的顺序有关，则称为有序串编码。
适应度：适应度由适应度函数计算，其值表示相应个体适应环境的程度。数值越大越好。
选择：按照一定的概率(选择概率)从当前种群中选择优秀的个体，使其会作为父亲繁衍下一代。个体的适应度越大，被选为亲本的概率就越大，优秀的基因也一定会遗传下去！接下来介绍三个选项！
(1)赌法3360根据个体的选择概率生成赌，赌的每个区域的角度与个体的选择概率成正比。然后随机产生一个0~1的数，选择赌中大于随机数的个个体。如下图，个随机数0.81，选择第六个个体，第二个随机数0.32，选择第二个个体。
(2)锦标赛法：从群体中随机选择若干个个体，将适应度最高的个体保存到下一代。重复这个过程，直到保存到下一代的个体数量达到预设数量。
(3)个体保存法：将群体中适应度最高的个体直接到下一代，不进行杂交，保证了遗传算法终止时得到的最终结果一定是前几代都出现过的适应度最高的个体。
变异：类似于生物学中的基因变异，执行变异操作的概率称为变异算子。以下是六种遗传算法中的变异方法。
(1)位点变异：群体中的个体密码串，随机选取一个或多个基因，用变异概率改变这些基因的基因值。
(2)反向突变：在个体代码串中随机选择两个点(反向点)，然后将两点之间的基因值按反向顺序插入到原来的位置。
(3)插入突变：在个体代码串中随机选择一个代码，然后将这个代码插入到随机选择的插入点中间。
(4)互换突变：随机选取染色体的两个基因进行简单交换。
(5)移动突变：随机选择一个基因，将其向左或向右移动一个随机数字。
(6)适应性变异：类似于位点变异，但变异概率随多样性自适应调整
交叉是指两个配对的染色体之间以某种方式交换一些基因，从而形成两个新的个体。交叉操作是遗传算法产生新个体的关键步骤，交叉操作的概率称为交叉算子。主要穿越方式如下：
(1)单点交叉：在单个字符串中随机设置一个交叉点。当进行杂交时，交换该点之前或之后的两个个体的部分结构，并产生两个新的个体。
(2)两点交叉：随机设置两个交叉点，两个交叉点之间的代码串相互交换。
(3)均匀交叉：根据均匀概率提取部分比特。每一位是否被选中都是随机的，与其他位无关。然后，交换两个个体提取比特以形成两个新的个体。
(4)序列交叉：在两条亲本染色体中随机选择起始和终止位置，将亲本染色体1的这个区域的基因到子代1的相同位置，然后在亲本染色体2上依次填充子代1中缺失的基因。
3.遗传算法流程
(1)初始化遗传算法参数，随机产生初始种群；
(2)计算种群中每个个体的适应度值；
(3)进行选择、交叉和变异操作，产生新的种群；
(4)是否满足终止条件，如果满足，则终止，否则跳(2)；
(5)输出解；
4.示例及其matlab代码
为了更具体地解释遗传算法，另一个技巧是用它来解决TSP问题。一个人从一个城市出发，穿越所有给定的城市，让整体的旅行距离尽可能的短。城市坐标分布图如下所示。
TSP _ gaout=tspga (xy，dmat，popsize，iternum，showprog，showresult)%利用遗传算法求解TSP问题tStart=tic%算法定时器nargs=6；因为我=纳金
:nargs-1 %nargin代表函数已输入参数个数 switch i case 0 %产生城市坐标% xy = round(500*rand(40,2));%随机生成40个城市坐标 xy =[307,415;5,429;287,395;395,159;118,226;224,376;285,55;31,55; 248,135;321,262;111,486;419,355;486,156;423,146;253,425;139,456; 373,320;118,128;479,44;310,419;300,292;86,474;45,31;128,292;429,143; 456,414;350,95;363,221;115,197;288,413;405,338;202,104;494,159;45,67; 160,336;256,285;30,85;363,74;278,238;265,454]; case 1 %计算距离矩阵 N = size(xy,1); a =meshgrid(1:N);%生成N*N升序矩阵 dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N);% '为矩阵的转置，reshape把数据生成N*N的矩阵 case 2 %设置种群规模 popSize = 100; case 3 %设置算法迭代次数 IterNum = 1e3; case 4 %是否展示迭代过程 showProg = 1; case 5 %是否展示最终结果 showResult =1; otherwise endend%对输入参数进行检查[N,~] = size(xy);%城市个数、维数[nr,nc] = size(dmat);%距离矩阵的行数和列数if N~=nr || N~=nc error('城市坐标或距离矩阵输入有误')endshowProg = logical(showProg(1));%将数值转变为逻辑值showResult = logical(showResult(1));%画出城市位置分布图figure(1);plot (xy(:,1),xy(:,2),'k.','MarkerSize',14);title('城市坐标位置');%% GA算子、参数设置SelectRate = 0.5; %选择概率crossRate = 0.9; %交叉概率mutationRate = 0.1; %变异概率global_min = Inf; %Inf表示无穷大popRoute = zeros(popSize,N); %存储种群个体路径offspring = zeros(popSize,N); %存储后代种群totaldist = zeros(1,popSize); %记录每一个个体的路径长度minLhistory = zeros(IterNum,1); %存储每一代种群中的路径长度subPath = zeros(1,N); %子代“儿子”BestPath = zeros(1,N);%记录个体for i =1:popSize popRoute(i,:) = randperm(N); %初始化种群，随机生成路线end%% 种群进化for iter = 1:IterNum %计算种群中每一个个体的路径长度和最短长度路径 for i = 1:popSize d = 0; for j = 1:(N-1) d = d + dmat(popRoute(i,j),popRoute(i,j+1));%计算路径起点到终点距离 end totaldist(1,i) = d + dmat(popRoute(i,N),popRoute(i,1));%加上由终点到起点的直线距离 end [minPath,index] = min(totaldist);%找出最短路径长度minPath,索引index minLhistory(iter,1) = minPath; %% 画出迭代过程 if minPath <global_min %如果距离小于前一个距离的话 global_min = minPath;%更新路径长度 BestPath = popRoute(index,:);%记录个体 if showProg %如果需要展示迭代过程的话 figure(2); for i = 1:N-1%画出中间路段 plot([xy(BestPath(i),1),xy(BestPath(i+1),1)],[xy(BestPath(i),2),xy(BestPath(i+1),2)],'bo-','LineWidth',2); hold on; end %画出终点到起点的路线 plot([xy(BestPath(N),1),xy(BestPath(1),1)],[xy(BestPath(N),2),xy(BestPath(1),2)],'ro-','LineWidth',2); title(sprintf('路线距离 = %1.2f，迭代次数 = %d次',global_min,iter)); hold off end end %% 运用锦标赛的方法进行选择 t = 4;%锦标赛选手个数 for k = 1:popSize teamDist = zeros(t,1);%记录每一个参赛选手的路径长度 for i = 1:t randrow = randi(popSize);%从种群中随机选择一个个体 teamDist(i,1) = totaldist(1,randrow); %距离赋值 end %在4个个体中选择最好的作为父体1 parent1 = min(teamDist); [~,parent1Y] = find(totaldist ==parent1,1,'first');%返回数组totaldist中个满足要求的元素的行和列下标 parent1Path = popRoute(parent1Y(1,1),:); %parent1Path是四个路径中距离最短的路径（是一个解） %找第二个父体 for i = 1:t randrow = randi(popSize);%从种群中随机选择一个个体 teamDist(i,1) = totaldist(1,randrow); %距离赋值 end %在4个个体中选择最好的作为父体2 parent2 = min(teamDist); [~,parent2Y] = find(totaldist ==parent2,1,'first');%返回数组totaldist中个满足要求的元素的行和列下标 parent2Path = popRoute(parent2Y(1,1),:); %parent2Path是四个路径中距离最短的路径（是一个解） %交叉 subPath = crossover(parent1Path,parent2Path,crossRate); %变异 subPath = mutate(subPath,mutationRate); offspring(k,:) = subPath(1,:); end popRoute = offspring;end%% 展示结果if showResult figure(3); plot(minLhistory,'b','LineWidth',2); xlabel('迭代次数'); ylabel('当前路径长度'); title('路径长度变化曲线图'); set(gca,'XLim',[0 IterNum+1],'YLim',[0 1.1*max(minLhistory)]);endtEnd = toc(tStart);fprintf('时间:%d 分 %f 秒.\', floor(tEnd/60), rem(tEnd,60));%打印时间end%% 交叉操作函数（顺序交叉）function subPath = crossover(parent1Path,parent2Path,crossRate)random = rand();%产生0~1的随机数if crossRate >= random %如果交叉概率大于该随机数，则尽行交叉操作 [~,length] = size(parent1Path); subPath = zeros(1,length); setsize = floor(length/2) -1; offset = randi(setsize);%%随机产生两个插入点 for i = offset:setsize+offset-1 subPath(1,i) = parent1Path(1,i);%把父体1的中间段基因赋给子代 end iterator = i+1; j = iterator; while any(subPath == 0) %一直循坏到子代基因全不为0 if j>length j =1; end if iterator > length iterator =1; end if ~any(subPath == parent2Path(1,j)) %把父代2中的基因转移到子代，且不能重复 subPath(1,iterator) = parent2Path(1,j); iterator = iterator+1; end j = j+1; endelse %如果随机数大于交叉概率,则不发生交叉操作 subPath = parent1Path;endend%% 变异操作函数function subPath = mutate(subPath,mutationRate)random = rand;%产生0~1的随机数if mutationRate>=random %变异概率大于随机数则发生变异 [~,n] = size(subPath); C = ceil(n*rand(1,2));%随机产生两个随机数 C = sort(C);%升序排列 subPath(1,[C(2),C(1)]) = subPath(1,[C(1),C(2)]);%将两个城市位置调转else subPath =subPath ;endend代码中的注释都比较的详尽，所以过多的话就不解释了，有啥不懂的，欢迎在评论上讨论，或者私信我，直接上结果图。
若有小对机器人任务分配算法较为兴趣的，可以在下面评论交流一波，纯属互相学习!
算法程序