MATLAB遗传算法：代码实现与优化

 参加国赛到现在有两年了， 想起原来我参加国赛的时候没日没夜的写论文的事现在仍然觉得机动。初学代码的时候对MATLAB一点都不知道，举步维艰，到了现在也算是能对MATLAB编程进行一些浅薄的理解，就现在把遗传算法的代码贴出来供大家学习使用吧。

遗传算法（Genetic Algorithm，GA）是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法 则，它最初由美国Michigan大学的J. Holland教授于1967年提出。 • 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一 定数目的个体(individual)组成。因此，第一步需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照 适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度 （fitness）大小选择个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉和变异，产生出代表新 的解集的种群。这个过程将导致种群像自然进化一样，后生代种群比前代更加适应于环境，末代种群中的最优个体经过解 码（decoding），可以作为问题近似最优解。 • 遗传算法有三个基本操作：选择（Selection）、交叉（Crossover）和变异（Mutation）。 • （1）选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁衍子孙。根据各个个体的 适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代种群中。选择的依据是适应性强的 个体为下一代贡献一个或多个后代的概率大。 • （2）交叉。通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。将群体中的各个个体随机搭配成对，对每 一个个体，以交叉概率交换它们之间的部分染色体。 • （3）变异。对种群中的每一个个体，以变异概率改变某一个或多个基因座上的基因值为其他的等位基因。同生物界中一样， 变异发生的概率很低，变异为新个体的产生提供了机会。 以多个城市的巡回送信问题为背景进行编程如下：

主程序：

clc

clear

close all

pop=1000;%每一代种群数量

citynum=20;%城市数量

maxit=1000;%运算到最后代数

city=zeros(citynum,2);%城市坐标

city(:,1)=rand(citynum,1).*1000;%随机生成的城市横坐标

city(:,2)=rand(citynum,1).*1000;%随机生成的城市纵坐标

locd=zeros(citynum,2);

pathlength=zeros(1,5);

x=city(:,1);

y=city(:,2);

subplot(2,2,1)

plot(x,y,'*r');

xlabel('城市横坐标');

ylabel('城市纵坐标');

hold off

parent=zeros(pop,citynum+1);

offspring=zeros(pop,citynum+1);

% 初始化种群

for i=1:pop

    parent(i,1:citynum)=randperm(citynum);

    parent(i,citynum+1)=fit(parent(i,1:citynum),city);

end

%进行迭代进化

for it=1:maxit

    parent=sortrows(parent,citynum+1);

    pathlength(1,it)=parent(1,citynum+1);

    for i=1:pop

        if i<=10

            offspring(i,:)=parent(i,:);

        else

            offspring(i,1:citynum)=change1(randperm(citynum));

            offspring(i,citynum+1)=fit(offspring(i,1:citynum),city);

        end

    end

    parent=offspring;

end

parent=sortrows(parent,citynum+1);

bst=parent(1,:);

for j=1:citynum

    locd(j,:)=city(bst(1,j),:);

end

locd(citynum+1,:)=locd(1,:);

subplot(2,2,2)

suptitle(strcat({num2str(citynum)},{ '个城市的路径规划'}));

plot(locd(:,1),locd(:,2),'-ro');

xlabel('城市横坐标（citys_x_label)');

ylabel('城市纵坐标');

subplot(2,2,[3,4])

plot(pathlength)

xlabel('迭代次数');

ylabel('最短路径长度');

disp(parent(1,:));

% msgbox(parent(1,:));

变异子程序：

function off= change1(off)

if rand<0.6

    n=size(off,2);

    n1=randi([1,n]);

    n2=randi([1,n1]);

    k=off(1,n1);

    off(1,n1)=off(1,n2);

    off(1,n2)=k;

end

路程设置为适应度，计算适应度子程序：

function t = fit(p,location)

num=size(p,2);

t=0;

for k=1:num-1

    x=location(p(1,k),1);

    y=location(p(1,k),2);

    x1=location(p(1,k+1),1);

    y1=location(p(1,k+1),2);

    t=t+sqrt((x-x1)^2+(y-y1)^2);

end

t=t+sqrt((location(p(1,1),1)-location(p(1,num),1))^2+(location(p(1,1),2)-location(p(1,num),2))^2);

end