遗传算法

遗传算法LN

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

遗传算法LN

如何利用工具箱求解

madio

问题：
& H6 x9 t2 z$ ?某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总电话费用尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分（因为通话的时间矩阵是对称的，没有必要写出下三角部分），n个城市两两之间通话费率表示在下面的矩阵的下三角部分（同样道理，因为通话的费率矩阵是对称的，没有必要写出上三角部分）. 试求解该二次指派问题。
" T: ?( b$ U# @* v( e! \0 5 3 7 9 3 9 2 9 0;
; n/ a$ Y! D9 f- A/ X7 0 7 8 3 2 3 3 5 7;
. Z4 V7 E: [6 J& Z# [4 r4 8 0 9 3 5 3 3 9 3;
) v6 `9 M. k/ W2 @+ X! m2 d6 2 10 0 8 4 1 8 0 4;
8 6 4 6 0 8 8 7 5 9;
3 X& O2 B9 \, }7 O8 5 4 6 6 0 4 8 0 3;
* m+ h5 k) ^) P* O8 F& P8 6 7 9 4 3 0 7 9 5;
& r8 q# x1 R) M2 {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;

答案 ：
+ F4 k5 S! q; n8 ]9 ?5 F工人2指派给城市1，工人7指派给城市2，工人4指派给城市3，工人9指派给城市4，工人8指派给城市5，工人5指派给城市6，工人6指派给城市7，工人3指派给城市8，工人1指派给城市9，工人10指派给城市10时，可取得最小费用每月1142.00元。
7 i  {% ~) q6 ]4 H+ hmatlab源程序：
%遗传算法
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
M=[0 5 3 7 9 3 9 2 9 0;
    7 0 7 8 3 2 3 3 5 7;
/ l: ^. f4 T/ F- P+ ^: F# m) I+ e    4 8 0 9 3 5 3 3 9 3;
    6 2 10 0 8 4 1 8 0 4;
3 R3 q6 W* c' Y$ J1 V    8 6 4 6 0 8 8 7 5 9;
# {$ v( U- M5 o2 D4 F" A, \    8 5 4 6 6 0 4 8 0 3;
    8 6 7 9 4 3 0 7 9 5;
/ S) k9 U, ^5 {* `2 A    6 8 2 3 8 8 6 0 5 5;
    6 3 6 2 8 3 7 8 0 5;
2 K  X" I% Y: Q2 y4 X  c    5 6 7 6 6 2 8 8 9 0;];
M1=M;                   %员工间每月通话时间矩阵
! ~. H5 K8 l* a# J+ `for i=1:10
    for j=i+1:10
        M1(j,i)=M(i,j);
6 \+ _1 Y7 o! A    end
9 m+ I! t6 ~0 @" e4 |end
  Z9 m+ J: E& \! m0 KM2=M;                %两地间通话费率矩阵
% I6 {# A( K# T3 f- B4 [for i=1:10
  |7 F: F6 N& ~& \    for j=i+1:10
9 B6 y- U: z1 N4 j: d        M2(i,j)=M(j,i);
- y. U* k* Q4 W8 x  M4 e    end
end
. _1 E5 f" i1 ?2 D0 `$ p%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
5 ?6 ^% G0 s8 }2 f5 n9 K%初始化种群
! w* p0 a, b4 O9 J6 c& T/ ]num=10;       %种群数量
9 r2 k: M6 C2 Y2 Rcode=10;       %染色体长
) M" r6 X2 K' G$ T$ q, o& ^) X$ Tdai=100;        %遗传代数
# x7 T. j! Q3 B) y% sinter=0.8;     %交叉率
- b5 C' j: a0 s- r3 w5 X# }, L* @; d  wbyl=0.8;
0 c6 [+ e$ \% C% o9 E2 |2 z6 |$ W$ r%A=randperm(num*code);
# O# P2 q( [/ A3 w7 `" A" ifor i=1:num
    V(i,:)=randperm(10);
end
* U! z0 }2 O, N9 I( h%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/ t. k, r  x/ l: vfor gen=1:dai
+ G$ a6 ^) }0 m) I, I' }
' g8 I. p2 ^6 u. ]    %评估
+ P" g7 B& s/ v9 t/ C1 h+ G9 b! w    [num1,lin]=size(V);
    eval=zeros(num1,1);
    for i=1:num1
        for j=1:code-1
/ J9 q7 w/ t0 p1 A" R8 h            for k=j+1:code
                eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
$ d. M' L% ]& F- B1 D            end
        end
9 H/ g1 J/ }1 D* R1 }4 G: {* n* i    end
. t* C8 w  Z2 V' g    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %选择
    [eval1,ind]=sort(eval);
    V1=V;
5 S, j3 a/ t; k  N/ v& J) e+ }    V=zeros(num,code);
$ T% B# ~  d; q0 L    for i=1:num
6 ~/ Z2 l% b  M        V(i,:)=V1(ind(i),:);
* f% Q( D# r8 Z1 U# p/ I6 T" j    end
! X' w1 P/ H: ^2 @6 C3 Z% |    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    %交叉
    V1=V;
    panduan=rand(fix(num),1);        %判断是否进行交叉
& a0 H- M. }6 s4 W) Y! C* n    for i=1:fix(num);
+ E2 v+ `/ b9 b4 Z; L' l        if panduan(i)<inter          %在交叉概率内进行交叉
* v0 {) t- C/ k1 ~8 G0 I            V2=zeros(1,code);         %记录交叉后的染色体
) \  E" \1 _5 q: D: A. U2 e5 |            h=randperm(num);                %随机取两个做交叉h(1)h(2)
            a=zeros(code,1);                 %记录未使用的位置
            b=zeros(code,1);               %记录未使用的数字
            %在双亲中随机选择基因
            for i=1:code
5 }9 S" c6 I+ ]  ~9 ^2 Y                h2=randperm(2);                %在双亲中随机选择
                if b(V1(h(h2(1)),i))==0
  {- c1 e0 M  O                    V2(i)=V1(h(h2(1)),i);   b(V1(h(h2(1)),i))=1; a(i)=1;
/ c2 Z# n/ u* j- ?1 j6 B                end
$ H3 S% k0 {; K8 _+ @& E            end

, s- U8 V) B3 G8 ?            %随机分配未使用数字和位置
            h1=randperm(code);               %记录未使用的数字
            for i=1:code
                for j=1:code
$ Z' n. r, J6 ]; |+ u: T                    if b(i)==1&&h1(j)==i
7 B( {/ ?, v9 p                        h1(j)=0;break
                    end
0 M2 Q( @; i* b4 s4 d+ _8 Q. I+ D                end
0 w9 G5 Z/ u; S' c: L            end
         
            for i=1:code
2 y0 d2 O( c" E) {3 d                if V2(i)==0
) k' _, ]) ]: T5 W( n! c  }' f. C                    for j=1:code
7 j( c! L; X/ f" N. T( @* w                        if h1(j)~=0
                            V2(i)=h1(j);h1(j)=0;break
0 x: C- r8 I8 q, j- }                        end
6 v5 n0 L' {* T( S* ]3 Y                    end
                end
            end
7 i+ ^+ O/ [( x( ~' u! E            V=[V;V2];
        end
+ t) Q7 ^8 D+ k+ ~, U! R# K7 _- b/ O    end

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ M4 c) m( R9 A    %变异
    V1=V;
- U! z8 r# ?; S  n7 s" i    [num1,lin]=size(V);
    x3=rand(num1,1);
    for i=num1
: v8 @& Y; @0 Y( X' j: q1 V* |        if x3(i)<byl              %变异率
            h2=randperm(code);
            V(i,h2(1))=V1(i,h2(2));
            V(i,h2(2))=V1(i,h2(1));
2 s: _* l  E7 A0 x        end
" e5 H* J. e/ I& g6 n    end
end
' j2 m  V' F% j7 f%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
) x4 X. g+ x9 H* }( S# \0 y
" m8 }. C) b6 H%对最终种群进行评估
. i7 t6 |5 G1 r. c[num1,lin]=size(V);
7 X- @" B0 Q, k% }5 V, q! eeval=zeros(num1,1);
5 ]4 k- G4 j1 u3 Qfor i=1:num1
8 S. E5 L/ ]. W3 q1 J    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
5 [5 G% R# B' n( _; aend
# T9 q; V! \  f9 P
. [; W0 K, y( U' K% \, x$ s7 y* F