没错，“遗传交配”也能做成算法。想一下，我们人类的进化史，大海就是我们的家呀！从海洋生物进化到陆地生物，由简单生物进化到复杂生物……，不禁想起了生物的高考考点。基因、染色体、交配、变异……这些都造成了生物的进化。也许就是从达尔文的进化论衍生出了一种寻优的算法——遗传算法(Genetic Algorithm，简称GA)，这算法是我目前感觉最容易理解的算法了哦。
1、遗传算法简介
遗传算法是由美国教授John holland于1975年左右提出的，它是借鉴了生物界自然选择和自然遗传机制的一种随机搜索算法，有一种“适者生存”、“优胜劣汰”的蓬勃之气。遗传算法常用来解决传统搜索算法难以解决的复杂和非线性的寻优问题。
2、遗传算法核心概念
先来补一下生物书简单的知识：
个体：这个概念很简单，就是我自己一个人，一个人称为个体，在遗传算法中的个体，也就是指拥有完整一套染色体的解。
群体：我们人类作为一个群体，群体之间可以相互交配，那么在理想情况下，不同群体之间是不可能发生交配的，即不同群体之间的进化过程是不不干扰的。
基因：染色体中的一个单位，也可以称为一个特征分量。
染色体：在生物中是可以简单理解为只有在发生交配的时候，染色体才会发生变化，也就是只有在交配的时候，群体的染色体类型才会更加地多样化，群体才能进化。在遗传算法中，则解释为根据问题的类型而编码形成的一个向量或字符串。
编码方式：有二进制编码、浮点数编码、十进制编码、有序串编码、结构式编码等。像TSP问题的话，是与参访的城市顺序有关的，则称为有序串编码。
适应度：适应度是由适应度函数计算出来的，它的值的大小表示对应个体适应环境的程度。其值越大则表示它越优秀。
选择：从当前群体中按照一定概率(选择概率)选出优良的个体，使它们有机会作为父代繁殖下一代子孙。个体适应度越大，其被选择作为父代的概率也就越大，优秀的基因肯定会被遗传下去的噻！接下来，介绍三种选择方法吧！
（1）轮盘赌方法:按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例，然后随机产生一个0~1的数，选择轮盘内第一个比随机数大的个体，如下图所示，第一个随机数为0.81，选择了6号个体，第二个随机数为0.32，选择了2号个体。
（2）锦标赛方法：从群体中随机选择若干个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止
（3）最佳个体保存方法群体中适应度最高的个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。
变异：类似于生物学中的基因突变，执行变异操作的概率称为变异算子，以下介绍6种遗传算法中的变异方法。
(1) 位点变异：群体中的个体码串，随机挑选一个或多个基因，并对这些基因的基因值以变异概率作变动。
(2)逆转变异：在个体码串中随机选择两点（逆转点），然后将两点之间的基因值以逆向排序插入到原位置中。
(3)插入变异：在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间。
(4)互换变异：随机选取染色体的两个基因进行简单互换。
(5)移动变异：随机选取一个基因，向左或者向右移动一个随机位数。
(6)自适应变异：类似于位点变异，但变异概率随群体中个体的多样性程度而自适应调整。
交叉：指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉操作是遗传算法产生新个体的关键步骤，执行交叉操作的概率称为交叉算子。主要交叉方法如下：
(1)单点交叉：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。
(2)两点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换。
(3)均匀交叉：按照均匀概率抽取一些位，每一位是否被选取都是随机的，并且独立于其他位。然后将两个个体被抽取位互换组成两个新个体。
(4)顺序交叉：在两个父代染色体中随机选择起始和结束位置，将父代染色体1该区域内的基因复制到子代1相同位置上，再在父代染色体2上将子代1中缺少的基因按照顺序填入。
3、遗传算法流程
(1)初始化GA参数，随机生成初始种群；
(2)计算种群中每一个个体的适应度值；
(3)进行选择、交叉、变异操作，产生新种群；
(4)是否满足终止条件，若是，则终止，否则跳转到(2)；
(5)输出最优解；
4、实例及其matlab代码
为了更加具体地解释遗传算法，又来同样一招，就是利用它来解决TSP问题。一个人从一个城市出发，遍历完给定的所有城市，并尽可能使整体的旅行距离最短。城市的坐标分布图如下所示。
function TSP_gaout = TSPGA(xy,dmat,popSize,IterNum,showProg,showResult)
%利用遗传算法解决TSP问题
tStart = tic; % 算法计时器
nargs = 6;
for i = nargin: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
end
end
%对输入参数进行检查
[N,~] = size(xy);%城市个数、维数
[nr,nc] = size(dmat);%距离矩阵的行数和列数
if N~=nr || N~=nc
error('城市坐标或距离矩阵输入有误')
end
showProg = 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)]);
end
tEnd = toc(tStart);
fprintf('时间:%d 分 %f 秒.n', 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;
end
else %如果随机数大于交叉概率,则不发生交叉操作
subPath = parent1Path;
end
end
%% 变异操作函数
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 ;
end
end
代码中的注释都比较的详尽，所以过多的话就不解释了，有啥不懂的，欢迎在评论上讨论，或者私信我，直接上结果图。
若有小伙伴对机器人任务分配算法较为兴趣的，可以在下面评论交流一波，纯属互相学习!
最新评论