遗传算法

遗传算法LN

关于遗传算法的人员安排问题，NP问题，

遗传算法LN

如何利用工具箱求解

madio

问题：
1 d( ?1 [, q4 A4 [某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总电话费用尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分（因为通话的时间矩阵是对称的，没有必要写出下三角部分），n个城市两两之间通话费率表示在下面的矩阵的下三角部分（同样道理，因为通话的费率矩阵是对称的，没有必要写出上三角部分）. 试求解该二次指派问题。
! u" }* U5 H, x( J2 u3 g0 T0 5 3 7 9 3 9 2 9 0;
7 0 7 8 3 2 3 3 5 7;
4 8 0 9 3 5 3 3 9 3;
! m2 E) k3 @8 k* _9 C+ x- K5 E) T6 2 10 0 8 4 1 8 0 4;
8 6 4 6 0 8 8 7 5 9;
8 5 4 6 6 0 4 8 0 3;
8 6 7 9 4 3 0 7 9 5;
6 8 2 3 8 8 6 0 5 5;
6 3 6 2 8 3 7 8 0 5;
4 D1 [" y$ o& f1 }. A9 N7 G+ x5 P5 6 7 6 6 2 8 8 9 0;
3 u, Q& m7 |1 ?% @- x
答案 ：
工人2指派给城市1，工人7指派给城市2，工人4指派给城市3，工人9指派给城市4，工人8指派给城市5，工人5指派给城市6，工人6指派给城市7，工人3指派给城市8，工人1指派给城市9，工人10指派给城市10时，可取得最小费用每月1142.00元。
$ `1 l0 h7 l$ x6 o5 P1 Kmatlab源程序：
%遗传算法
7 p* I& Q1 P& h4 c! j%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
9 v! r$ e6 `: q' fM=[0 5 3 7 9 3 9 2 9 0;
    7 0 7 8 3 2 3 3 5 7;
    4 8 0 9 3 5 3 3 9 3;
    6 2 10 0 8 4 1 8 0 4;
    8 6 4 6 0 8 8 7 5 9;
    8 5 4 6 6 0 4 8 0 3;
- q$ n, j: S4 S% U4 w    8 6 7 9 4 3 0 7 9 5;
    6 8 2 3 8 8 6 0 5 5;
    6 3 6 2 8 3 7 8 0 5;
    5 6 7 6 6 2 8 8 9 0;];
M1=M;                   %员工间每月通话时间矩阵
% A3 ~  Y6 P7 jfor i=1:10
    for j=i+1:10
        M1(j,i)=M(i,j);
9 p7 l9 k8 ~: ?/ ]( u$ p: B6 f    end
end
4 M* f0 z! N' ^# g; [& j% z7 _M2=M;                %两地间通话费率矩阵
for i=1:10
1 p9 i" [" L( ]8 k( C+ ^& `    for j=i+1:10
        M2(i,j)=M(j,i);
    end
end
5 l; b) a4 S: E. @%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%初始化种群
num=10;       %种群数量
; H" c9 c6 }! e/ N! S) [- L! ~code=10;       %染色体长
dai=100;        %遗传代数
inter=0.8;     %交叉率
byl=0.8;
%A=randperm(num*code);
for i=1:num
* u7 J0 i3 s% y/ S, |; g    V(i,:)=randperm(10);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for gen=1:dai

    %评估
" B2 G0 Y" |! P7 [& C    [num1,lin]=size(V);
    eval=zeros(num1,1);
    for i=1:num1
+ F+ F- X% t) D* z& `' B7 L% e- h        for j=1:code-1
            for k=j+1:code
                eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
            end
        end
    end
0 ]2 r4 Y: O* W    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/ b5 h0 e9 t& r! Z    %选择
9 \- {3 z- e& P3 f    [eval1,ind]=sort(eval);
    V1=V;
    V=zeros(num,code);
+ }7 V$ a" U+ ?3 r+ v    for i=1:num
        V(i,:)=V1(ind(i),:);
  |. t9 t( L! y0 S1 d6 j$ k    end
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$ {4 j4 c! F5 A+ f- p% h    %交叉
8 ]3 M% _' \, s& N    V1=V;
    panduan=rand(fix(num),1);        %判断是否进行交叉
    for i=1:fix(num);
        if panduan(i)<inter          %在交叉概率内进行交叉
7 c$ @# ]7 P7 d1 y            V2=zeros(1,code);         %记录交叉后的染色体
            h=randperm(num);                %随机取两个做交叉h(1)h(2)
+ z: I3 }' z2 h' D' `3 x  R* e            a=zeros(code,1);                 %记录未使用的位置
- B; |9 q5 b2 D5 g0 S  G            b=zeros(code,1);               %记录未使用的数字
            %在双亲中随机选择基因
8 M" t3 o1 y1 t6 U1 {            for i=1:code
( f- N" I$ [& Q                h2=randperm(2);                %在双亲中随机选择
) T  b. @9 ~# ?4 x                if b(V1(h(h2(1)),i))==0
                    V2(i)=V1(h(h2(1)),i);   b(V1(h(h2(1)),i))=1; a(i)=1;
                end
$ @. h1 {, K( M1 U" P2 w, M            end

3 y2 C. R% X+ l            %随机分配未使用数字和位置
; [7 ]2 u0 W- W% F( g' X- y            h1=randperm(code);               %记录未使用的数字
2 D; y  L1 R. \% B& n# B, c            for i=1:code
) G* u( t4 L# ~" c! O9 d                for j=1:code
9 i$ P" g  `: Y, `                    if b(i)==1&&h1(j)==i
                        h1(j)=0;break
6 z" Y* L3 `+ q, X3 a/ x                    end
- L; o5 b. u0 h) C. K* j                end
            end
         
            for i=1:code
5 E+ }# }& K! h* q$ w                if V2(i)==0
                    for j=1:code
                        if h1(j)~=0
                            V2(i)=h1(j);h1(j)=0;break
                        end
                    end
                end
            end
            V=[V;V2];
        end
    end

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6 n/ T  z3 B  ?    %变异
9 x; _4 D8 k! _! j6 K    V1=V;
    [num1,lin]=size(V);
    x3=rand(num1,1);
    for i=num1
        if x3(i)<byl              %变异率
* O* g% A+ P8 a, K. \+ F            h2=randperm(code);
% a, s" |9 n5 Y, V1 B            V(i,h2(1))=V1(i,h2(2));
            V(i,h2(2))=V1(i,h2(1));
        end
    end
/ ?- {( C# f# v$ M) J* \6 yend
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%对最终种群进行评估
/ ~( r, ~% E! R2 _[num1,lin]=size(V);
eval=zeros(num1,1);
* f6 g0 I: j& E& dfor i=1:num1
8 K2 @  D) v0 b* Z# L' b    for j=1:code-1
- o* W6 n) k( M2 {        for k=j+1:code
            eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
  k0 s" E, c" S* e        end
    end
4 u" M5 J) V7 z7 {/ R2 e3 Y, Xend
1 O, E3 C5 R! m; u