遗传算法

遗传算法LN

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

遗传算法LN

如何利用工具箱求解

madio

问题：
某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总电话费用尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分（因为通话的时间矩阵是对称的，没有必要写出下三角部分），n个城市两两之间通话费率表示在下面的矩阵的下三角部分（同样道理，因为通话的费率矩阵是对称的，没有必要写出上三角部分）. 试求解该二次指派问题。
  [6 H  H2 X, {0 5 3 7 9 3 9 2 9 0;
* R  d# Y' U& T8 c7 0 7 8 3 2 3 3 5 7;
4 8 0 9 3 5 3 3 9 3;
6 w2 P- E; N) `1 _/ ?6 2 10 0 8 4 1 8 0 4;
3 S) B! p* m1 x8 Z9 X* T  z" [2 M8 6 4 6 0 8 8 7 5 9;
1 {0 V- x" \7 d. P# [8 5 4 6 6 0 4 8 0 3;
* w* C# u/ _% A2 m1 y& N8 6 7 9 4 3 0 7 9 5;
2 O/ V' ]+ g- ~1 w6 8 2 3 8 8 6 0 5 5;
. v7 G4 A% D  t0 z% P7 S) l3 z& v6 3 6 2 8 3 7 8 0 5;
$ c6 o5 h4 L% E$ y6 c& c5 M2 g3 p5 6 7 6 6 2 8 8 9 0;
: E: N) _1 D3 _' h" C8 W& Y) A# Z
答案 ：
工人2指派给城市1，工人7指派给城市2，工人4指派给城市3，工人9指派给城市4，工人8指派给城市5，工人5指派给城市6，工人6指派给城市7，工人3指派给城市8，工人1指派给城市9，工人10指派给城市10时，可取得最小费用每月1142.00元。
matlab源程序：
) k/ `# w7 H  q! b! B3 Q%遗传算法
3 g0 Q5 S/ b. c0 k1 s+ X% |# T; u%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/ U& a0 u' M: E; ^$ bM=[0 5 3 7 9 3 9 2 9 0;
$ R& H" ~$ W$ H( ^7 V& o* F, u    7 0 7 8 3 2 3 3 5 7;
- E. g) C5 b: e4 p. w8 @& x    4 8 0 9 3 5 3 3 9 3;
/ {, p1 \0 ]3 K$ x" I& ?5 t    6 2 10 0 8 4 1 8 0 4;
; O$ P2 ]( k1 k7 z# Z' B6 c; p    8 6 4 6 0 8 8 7 5 9;
9 z0 S, W4 l5 O3 F' a8 W6 U    8 5 4 6 6 0 4 8 0 3;
+ ~& Y; T4 c3 T5 v* [7 }7 ~) h; a    8 6 7 9 4 3 0 7 9 5;
$ v% c. f1 L2 a- D7 }    6 8 2 3 8 8 6 0 5 5;
1 L# f) X; ~2 N    6 3 6 2 8 3 7 8 0 5;
" ?9 a* f: ?9 ^! |    5 6 7 6 6 2 8 8 9 0;];
% u1 E+ H; i8 w; k0 GM1=M;                   %员工间每月通话时间矩阵
for i=1:10
. l; ~, D+ U  T9 I# v9 H    for j=i+1:10
& a$ Q; I/ V, L1 z, y6 G        M1(j,i)=M(i,j);
" h; J* ]$ Y4 B- O* m% W  f! P+ c8 A    end
end
M2=M;                %两地间通话费率矩阵
4 A7 Y$ a" I3 J8 b- nfor i=1:10
. z# Q2 H* B2 \3 Y$ w: o' p    for j=i+1:10
$ i) ]1 n* p' `) h5 B        M2(i,j)=M(j,i);
    end
5 ^# l6 \' }: o: K0 Eend
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
; q& ], ~; [6 @% h%初始化种群
num=10;       %种群数量
7 W$ v8 w1 [- k+ Gcode=10;       %染色体长
dai=100;        %遗传代数
inter=0.8;     %交叉率
/ f7 u: N& k7 `3 h5 H( ^9 j6 Wbyl=0.8;
) S. X$ p- Z, V$ i9 {' c%A=randperm(num*code);
0 O" f$ P3 J1 y- tfor i=1:num
1 T6 g- r# g5 K) s/ c    V(i,:)=randperm(10);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
- q  F( E7 l4 z7 w) n1 [% ufor gen=1:dai

( T  V, N0 {: J) v1 C  }* k. x    %评估
    [num1,lin]=size(V);
" e1 M! T; l" L. S7 z% W) b0 s    eval=zeros(num1,1);
    for i=1:num1
5 Z- @7 m2 q+ `/ V% l, M        for j=1:code-1
            for k=j+1:code
                eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
- i7 \, t4 R. Y6 Q            end
        end
    end
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
$ p2 B" T0 g* O. S  _    %选择
4 A- e6 l0 E- d  l9 }    [eval1,ind]=sort(eval);
    V1=V;
% d+ H3 n$ H' i9 i- A6 \" V/ J    V=zeros(num,code);
& v; |9 R- |2 @! n/ [# t7 {    for i=1:num
        V(i,:)=V1(ind(i),:);
    end
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    %交叉
4 R7 D7 C9 m9 k: T, v1 ^5 x    V1=V;
. |8 L( o! p; A/ O3 p, V    panduan=rand(fix(num),1);        %判断是否进行交叉
) _' S6 P1 @, l    for i=1:fix(num);
        if panduan(i)<inter          %在交叉概率内进行交叉
) u% z" t$ G/ l8 i" l) `            V2=zeros(1,code);         %记录交叉后的染色体
            h=randperm(num);                %随机取两个做交叉h(1)h(2)
" G) o4 |+ _4 Y# c+ y$ W            a=zeros(code,1);                 %记录未使用的位置
            b=zeros(code,1);               %记录未使用的数字
            %在双亲中随机选择基因
) J4 A4 Y% p+ x# `) R( P            for i=1:code
                h2=randperm(2);                %在双亲中随机选择
/ d4 b* a( a: d6 d" W& q) N                if b(V1(h(h2(1)),i))==0
/ Q# d4 j" s0 M: W1 m9 U% d+ I                    V2(i)=V1(h(h2(1)),i);   b(V1(h(h2(1)),i))=1; a(i)=1;
                end
            end
4 j+ X) W5 R+ T+ W
            %随机分配未使用数字和位置
: l5 c& H$ _2 u  L            h1=randperm(code);               %记录未使用的数字
& \7 @7 \# ~* t7 l4 O            for i=1:code
                for j=1:code
/ W9 N) n  v8 Y$ e                    if b(i)==1&&h1(j)==i
                        h1(j)=0;break
                    end
                end
2 H7 w8 s. g. T/ n" t$ M5 P. l8 X            end
, i  A, U" T$ \' L7 g         
( z5 ]- ]+ @4 I1 E            for i=1:code
5 h( I( m. D2 Z* U% \9 y- p                if V2(i)==0
' R) [; X2 o; b* u" @                    for j=1:code
4 |8 u9 V" N% z. A                        if h1(j)~=0
                            V2(i)=h1(j);h1(j)=0;break
                        end
                    end
                end
2 C$ f. M2 _& w8 m& Q! S  y1 I            end
            V=[V;V2];
7 C6 c7 i. D. N. M        end
    end

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %变异
    V1=V;
$ ~, a$ R! w# i$ N    [num1,lin]=size(V);
5 ]* y7 ^7 ?$ ^9 y' q    x3=rand(num1,1);
3 X- ]' U, t5 O/ a% o    for i=num1
1 H3 a6 A3 p" }        if x3(i)<byl              %变异率
            h2=randperm(code);
6 q0 _3 w8 ?5 W; k            V(i,h2(1))=V1(i,h2(2));
            V(i,h2(2))=V1(i,h2(1));
        end
8 H5 B/ g6 U3 Z9 h2 f    end
end
7 k9 |+ r  R5 S1 H; A, f, n- \%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

! ~! B: N3 g9 W6 W; r) {4 ~2 ]3 s%对最终种群进行评估
! Y! d9 x5 z2 b5 b5 k& |$ `[num1,lin]=size(V);
: X7 y% }2 A5 I" E& x. k# Xeval=zeros(num1,1);
for i=1:num1
6 l8 ]: B4 s7 m    for j=1:code-1
6 X1 p7 @) W/ x+ M( d9 R        for k=j+1:code
! h2 k  s; U7 @; {" W* z            eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
. f. T$ t, Q/ D  Z2 \        end
    end
: p6 I9 l% k1 D5 S9 q) wend
1 X7 e3 Q. \- f: T2 T
+ B# y5 I/ y. N5 g" g7 y- A) D) h