遗传算法简单学习案例

这是一个很简单的遗传算法案例。解决旅行商问题。

clc,clear, close all

sj0=load('data12_1.txt');

x=sj0(:,1:2:8); x=x(:);

y=sj0(:,2:2:8); y=y(:);

sj=[x y]; d1=[70,40]; 

xy=[d1;sj;d1]; sj=xy*pi/180;  %单位化成弧度

d=zeros(102); %距离矩阵d的初始值

for i=1:101

  for j=i+1:102

      d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*...

          cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)));

  end

end

d=d+d'; w=50; g=100; %w为种群的个数，g为进化的代数

for k=1:w  %通过改良圈算法选取初始种群

    c=randperm(100); %产生1，...，100的一个全排列  

    c1=[1,c+1,102]; %生成初始解

    for t=1:102 %该层循环是修改圈 

        flag=0; %修改圈退出标志

    for m=1:100

      for n=m+2:101

        if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<...

                d(c1(m),c1(m+1))+d(c1(n),c1(n+1))

           c1(m+1:n)=c1(n:-1:m+1);  flag=1; %修改圈

        end

      end

    end

   if flag==0

      J(k,c1)=1:102; break %记录下较好的解并退出当前层循环

   end

   end

end

J(:,1)=0; J=J/102; %把整数序列转换成[0,1]区间上的实数，即转换成染色体编码

for k=1:g  %该层循环进行遗传算法的操作 

    A=J; %交配产生子代A的初始染色体

    c=randperm(w); %产生下面交叉操作的染色体对 

    for i=1:2:w  

        F=2+floor(100*rand(1)); %产生交叉操作的地址

        temp=A(c(i),[F:102]); %中间变量的保存值

        A(c(i),[F:102])=A(c(i+1),[F:102]); %交叉操作

        A(c(i+1),F:102)=temp;  

    end

    by=[];  %为了防止下面产生空地址，这里先初始化

while ~length(by)

    by=find(rand(1,w)<0.1); %产生变异操作的地址

end

B=A(by,:); %产生变异操作的初始染色体

for j=1:length(by)

   bw=sort(2+floor(100*rand(1,3)));  %产生变异操作的3个地址

   B(j,:)=B(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]); %交换位置

end

   G=[J;A;B]; %父代和子代种群合在一起

   [SG,ind1]=sort(G,2); %把染色体翻译成1，...,102的序列ind1

   num=size(G,1); long=zeros(1,num); %路径长度的初始值

   for j=1:num

       for i=1:101

           long(j)=long(j)+d(ind1(j,i),ind1(j,i+1)); %计算每条路径长度

       end

   end

     [slong,ind2]=sort(long); %对路径长度按照从小到大排序

     J=G(ind2(1:w),:); %精选前w个较短的路径对应的染色体

end

path=ind1(ind2(1),:), flong=slong(1)  %解的路径及路径长度

xx=xy(path,1);yy=xy(path,2);

plot(xx,yy,'-o') %画出路径

1取值，以及确定旅行商问题

2在原始数据中进化找合适的解集J（其中对d进行比较和修正）

（适应度函数直接作为条件语句进行描述）

3在J中进行交配操作（交叉），得到交配子代A

4在A中进行变异操作（交换rand位置），得到变异子代B

5合成解集G=(J:A:B)，在G中寻找路径最短的值。

6画出路径。

备注：

染色体编码出现在交配过程中，直接J=J/102

因为适应度函数比较简单，所以就没有专门描述适应度函数。

下一步应该对适应度函数的表达进行学习。

data12_1：

53.7121   15.3046 51.1758    0.0322 46.3253   28.2753 30.3313    6.9348

56.5432   21.4188 10.8198   16.2529 22.7891   23.1045 10.1584   12.4819

20.1050   15.4562 1.9451    0.2057 26.4951   22.1221 31.4847    8.9640

26.2418   18.1760 44.0356   13.5401 28.9836   25.9879 38.4722   20.1731

28.2694   29.0011 32.1910    5.8699 36.4863   29.7284 0.9718   28.1477

8.9586   24.6635 16.5618   23.6143 10.5597   15.1178 50.2111   10.2944

8.1519    9.5325 22.1075   18.5569 0.1215   18.8726 48.2077   16.8889

31.9499   17.6309 0.7732    0.4656 47.4134   23.7783 41.8671    3.5667

43.5474    3.9061 53.3524   26.7256 30.8165   13.4595 27.7133    5.0706

23.9222    7.6306 51.9612   22.8511 12.7938   15.7307 4.9568    8.3669

21.5051   24.0909 15.2548   27.2111 6.2070    5.1442 49.2430   16.7044

17.1168   20.0354 34.1688   22.7571 9.4402    3.9200 11.5812   14.5677

52.1181    0.4088 9.5559   11.4219 24.4509    6.5634 26.7213   28.5667

37.5848   16.8474 35.6619    9.9333 24.4654    3.1644 0.7775    6.9576

14.4703   13.6368 19.8660   15.1224 3.1616    4.2428 18.5245   14.3598

58.6849   27.1485 39.5168   16.9371 56.5089   13.7090 52.5211   15.7957

38.4300    8.4648 51.8181   23.0159 8.9983   23.6440 50.1156   23.7816

13.7909    1.9510 34.0574   23.3960 23.0624    8.4319 19.9857    5.7902

40.8801   14.2978 58.8289   14.5229 18.6635    6.7436 52.8423   27.2880

39.9494   29.5114 47.5099   24.0664 10.1121   27.2662 28.7812   27.6659

8.0831   27.6705 9.1556   14.1304 53.7989    0.2199 33.6490    0.3980

1.3496   16.8359 49.9816    6.0828 19.3635   17.6622 36.9545   23.0265

15.7320   19.5697 11.5118   17.3884 44.0398   16.2635 39.7139   28.4203

6.9909   23.1804 38.3392   19.9950 24.6543   19.6057 36.9980   24.3992

4.1591    3.1853 40.1400   20.3030 23.9876    9.4030 41.1084   27.7149

本文为我原创本文禁止转载或摘编