yichuan.m

遗传算法在tsp中的应用

% 遗传算法在TSP中的应用
function [s,q]=yichuan(D,n)       % D为距离矩阵，难为TSP中的城市个数
tic
fprintf('注意：种群中个体数、遗传代数越多，需要运行的时间越长,但是结果越好！\n');
m=input('请输入种群大小,最好为偶数m=');  
p=input('请输入遗传代数p=');
% 产生初始种群
for i=1:m
    e=1:n;
    for j=1:n
        t=unidrnd(length(e));
        q(i,j)=e(t);
        e(t)=[];
    end
end
s=len(q,D,n,m); % 计算路程长度
for i=1:p
    q=newq(s,q,m);% 产生新种群
    q=change(q,m,n); % 交叉
    q=vf(q,n,m);   % 变异
    s=len(q,D,n,m); % 计算路程长度
end
[s0,b]=min(s);
fprintf('中总路程为s=%4.2f\n',s0);
fprintf('站点顺序为\n');
fprintf('%d  ',q(b,:));
toc


% 计算路程即目标函数
function s=len(q,D,n,m)
for i=1:m
    s(i)=0;
    for j=1:n-1
        s(i)=s(i)+D(q(i,j),q(i,j+1));
    end
end


%  选择目标函数小的个体，产生新种群
function q=newq(s,q,m)
t=0.20;  % 淘汰比例
% 降序排列
for i=1:m-1
    for j=i:m
        if s(i)<s(j)
            k=s(j);
            s(j)=s(i);
            s(i)=k;
            
            Q=q(j,:);
            q(j,:)=q(i,:);
            q(i,:)=Q;
        end
    end
end
f=fix(m*t);  % 淘汰个数
% 将目标函数值大的前f个个体用目标函数值小的后f个个体
for i=1:f
    q(i,:)=q(m-f+i,:);
end
% 打乱顺序
for i=1:2*m
    N1=unidrnd(m);
    N2=unidrnd(m);
    Q=q(N1,:);
    q(N1,:)=q(N2,:);
    q(N2,:)=Q;
end



%  两两交叉操作
function q=change(q,m,n)
while 1
    N1=unidrnd(n-1);
    N2=unidrnd(n-1);
    if N2>N1+1 
        break;
    end
end

%  采用部分匹配交叉，且一对一对交叉
for i=1:2:m-1
    % 中间部分交换
    Q=q(i,N1+1:N2);
    q(i,N1+1:N2)=q(i+1,N1+1:N2);
    q(i+1,N1+1:N2)=Q;
    % 选出可以保留的部分
    t1=1;t2=1;
    for j=1:n        
        if (q(i,j)~=q(i,N1+1:N2))
            e1(t1)=j;
            t1=t1+1;
        end
        if (j>N1&j<=N2)
            e1(t1)=j;
            t1=t1+1;
        end
       if (q(i+1,j)~=q(i+1,N1+1:N2))
           e2(t2)=j;
           t2=t2+1;
       end
       if (j>N1&j<=N2)
           e2(t2)=j;
           t2=t2+1;
       end
    end
    % 替换重复部分
    for j=1:n
        if j~=e1
            for k=N1+1:N2
                if q(i+1,k)~=q(i,e1)
                    q(i,j)=q(i+1,k);
                    e1(t1)=j;
                    t1=t1+1;
                    break;
                end
            end
        end
        if j~=e2
           for k=N1+1:N2
                if q(i,k)~=q(i+1,e2)
                    q(i+1,j)=q(i,k);
                    e2(t2)=j;
                    t2=t2+1;
                    break;
                end
            end 
        end
    end
    for j=1:n
        if j~=e1
            for k=1:n
                if k~=q(i,e1)
                    q(i,j)=k;
                    e1(t1)=j;
                    t1=t1+1;
                    break;
                end
            end
        end
        if j~=e2
            for k=1:n
                if k~=q(i+1,e2)
                    q(i+1,j)=k;
                    e2(t2)=j;
                    t2=t2+1;
                    break;
                end
            end
        end 
    end
    clear e1 e2
end


%  变异
function q=vf(q,n,m)
F=0.01 ; %以1%的概率变异
N1=unidrnd(m);   % 种群中第N1个个体可能变异
N2=1+unidrnd(n-1); % 编码中第N2个号可能变异
k=1+unidrnd(n-1);  % q(n1,n2)变为k
p0=unifrnd(0,1);   % 随机产生变异概率
if p0<F
    for i=1:n
        if q(N1,i)==k
            q(N1,i)=q(N1,N2);
            break;
        end
    end
    q(N1,N2)=k;
end