遗传算法

遗传算法LN

关于遗传算法的人员安排问题，NP问题，
7 k7 o- B& h  b% M+ y2 u* m

遗传算法LN

如何利用工具箱求解

madio

问题：
+ _8 P/ z0 R3 @# g# f某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总电话费用尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分（因为通话的时间矩阵是对称的，没有必要写出下三角部分），n个城市两两之间通话费率表示在下面的矩阵的下三角部分（同样道理，因为通话的费率矩阵是对称的，没有必要写出上三角部分）. 试求解该二次指派问题。
$ ]- ]4 y. s& v# [. F0 5 3 7 9 3 9 2 9 0;
7 0 7 8 3 2 3 3 5 7;
# w  Y5 S/ E7 S4 ~6 c  o4 8 0 9 3 5 3 3 9 3;
& h% J( n# A6 J/ U# n/ O; D6 2 10 0 8 4 1 8 0 4;
5 g; k; r2 D) j8 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;
9 y9 n' G) C' B% A; e: a6 S6 8 2 3 8 8 6 0 5 5;
5 l2 \& q+ \' E6 u1 r6 3 6 2 8 3 7 8 0 5;
5 6 7 6 6 2 8 8 9 0;
- a2 [. e% M7 u; ]9 j( S
答案 ：
工人2指派给城市1，工人7指派给城市2，工人4指派给城市3，工人9指派给城市4，工人8指派给城市5，工人5指派给城市6，工人6指派给城市7，工人3指派给城市8，工人1指派给城市9，工人10指派给城市10时，可取得最小费用每月1142.00元。
matlab源程序：
  p: d8 ]9 I7 ]5 Q# d3 k+ @8 i%遗传算法
  |/ F: _4 @6 z2 q6 o! F, X- a%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
M=[0 5 3 7 9 3 9 2 9 0;
- {2 N5 e- g" `# y$ f: ?    7 0 7 8 3 2 3 3 5 7;
    4 8 0 9 3 5 3 3 9 3;
9 _5 ~$ ]% b8 f8 D# ?    6 2 10 0 8 4 1 8 0 4;
    8 6 4 6 0 8 8 7 5 9;
) C( l! B; i+ L+ |$ M    8 5 4 6 6 0 4 8 0 3;
  F. S: r2 X" j; a    8 6 7 9 4 3 0 7 9 5;
    6 8 2 3 8 8 6 0 5 5;
5 Y0 Q( }  p  C    6 3 6 2 8 3 7 8 0 5;
    5 6 7 6 6 2 8 8 9 0;];
  g8 f  |; ?& B4 Y: fM1=M;                   %员工间每月通话时间矩阵
for i=1:10
    for j=i+1:10
        M1(j,i)=M(i,j);
: j; R1 `' \/ X  |    end
& h; v! g7 K9 |- hend
# Z7 V* \# M) C. H, cM2=M;                %两地间通话费率矩阵
' w: L2 h" f8 E6 o$ c. Mfor i=1:10
! e( ?8 X. Y3 j, i' d- a    for j=i+1:10
        M2(i,j)=M(j,i);
    end
# }- w8 }+ t: B; Nend
# k5 S* o, ^9 R$ I9 H& U" M4 R* @%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
* ~: }0 r) }9 v+ _1 l0 t0 [; r%初始化种群
num=10;       %种群数量
code=10;       %染色体长
dai=100;        %遗传代数
3 H0 I+ R5 C1 r$ x3 Q! r& ginter=0.8;     %交叉率
byl=0.8;
: `& W1 j: y+ [9 I6 J' ^%A=randperm(num*code);
for i=1:num
    V(i,:)=randperm(10);
end
, w" h- r8 ~: h% O& j%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for gen=1:dai
- G# j4 z5 ?& n4 U* D' {- |5 u
3 m! v8 E3 q- K; L$ E; w, ~    %评估
) @- Y1 a. }/ s8 Y% S- [    [num1,lin]=size(V);
    eval=zeros(num1,1);
    for i=1:num1
) U- @* m8 a& G; F3 G) K% @7 l& {        for j=1:code-1
, X" U: G! `6 H: y            for k=j+1:code
! G) I2 D) k9 E: D4 h0 L* n                eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
            end
        end
    end
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
4 [: \* E8 p9 j1 K7 t, v    %选择
    [eval1,ind]=sort(eval);
9 E- Z1 I( Q) J, i    V1=V;
# w4 b  Q- y% Q! j  j3 `    V=zeros(num,code);
' K; I6 n! X6 D    for i=1:num
) i/ s$ D3 m0 q        V(i,:)=V1(ind(i),:);
* y1 X  r! v3 }! I6 t9 G( M    end
- v2 V: o# V4 Q. i/ [7 e# O    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% g0 Q; o7 `  H) b* x
% i$ p1 w$ H/ t+ }    %交叉
    V1=V;
    panduan=rand(fix(num),1);        %判断是否进行交叉
2 D; V% A5 H! K    for i=1:fix(num);
. D8 u% v6 ]/ [: ]" p        if panduan(i)<inter          %在交叉概率内进行交叉
            V2=zeros(1,code);         %记录交叉后的染色体
            h=randperm(num);                %随机取两个做交叉h(1)h(2)
) n- v8 }/ t  H& r4 ^* n& Z            a=zeros(code,1);                 %记录未使用的位置
& z; y, h6 f9 k6 u+ u  O            b=zeros(code,1);               %记录未使用的数字
' @& s( \+ k$ u1 C( O% d! u            %在双亲中随机选择基因
            for i=1:code
) o( i0 g% k7 l( f$ H; Z- E! k                h2=randperm(2);                %在双亲中随机选择
                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
            end

. @% F. l+ \: \& Z- T            %随机分配未使用数字和位置
0 ~3 A3 B% m& P1 t1 s1 _            h1=randperm(code);               %记录未使用的数字
; V. v- J. D; b: @            for i=1:code
1 h5 }- M* e4 F" Q3 U7 n3 C                for j=1:code
                    if b(i)==1&&h1(j)==i
: P+ K4 A, s: S  M3 B                        h1(j)=0;break
                    end
1 y+ c0 |* d, c  i9 t2 ]' \  }                end
0 O, M+ v6 W( j# f            end
" u! Z' f. M) d# O8 @         
/ U# j: ~( w4 R8 @/ b. Q            for i=1:code
                if V2(i)==0
                    for j=1:code
# y$ d1 g! s8 L8 w+ c                        if h1(j)~=0
2 ], {- |( l, l2 Y* x  n                            V2(i)=h1(j);h1(j)=0;break
                        end
                    end
                end
) E# {; {4 N; z& |: k2 f            end
            V=[V;V2];
        end
    end

5 ^+ R4 B/ [" W6 f7 Y    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %变异
    V1=V;
    [num1,lin]=size(V);
" m4 D3 x% `8 \' }& ]2 B    x3=rand(num1,1);
, ?2 S: H, O2 S$ a    for i=num1
4 y$ h# V- h! Q5 a% B        if x3(i)<byl              %变异率
0 M' n1 x) ], L0 Y) X5 @9 L            h2=randperm(code);
+ n) s; z7 {# \            V(i,h2(1))=V1(i,h2(2));
            V(i,h2(2))=V1(i,h2(1));
7 Y9 f) V1 F' a) X- c        end
    end
/ T% M" T) H* Q7 dend
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1 I4 I" x& J9 n+ e. J/ Y1 _' {
+ f* [$ a9 \  z! K%对最终种群进行评估
[num1,lin]=size(V);
! k3 b+ ~/ _  @: D- L  deval=zeros(num1,1);
for i=1:num1
    for j=1:code-1
        for k=j+1:code
2 x" ^& I( B, N            eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
/ K& C5 D6 y, H9 g9 h4 ~        end
    end
6 ~4 q2 Z/ R- h) y9 s8 F- K3 Kend

. s; w2 B7 H" q9 Z5 ]+ P+ }