遗传算法

遗传算法LN

关于遗传算法的人员安排问题，NP问题，
9 U7 E$ e+ l# {5 D4 A; X2 [

遗传算法LN

如何利用工具箱求解

madio

问题：
! W) a. K( w2 a3 [0 [" x1 j/ [某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总电话费用尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分（因为通话的时间矩阵是对称的，没有必要写出下三角部分），n个城市两两之间通话费率表示在下面的矩阵的下三角部分（同样道理，因为通话的费率矩阵是对称的，没有必要写出上三角部分）. 试求解该二次指派问题。
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;
8 6 7 9 4 3 0 7 9 5;
$ ?. m5 `/ P3 i9 H" k3 X6 8 2 3 8 8 6 0 5 5;
9 c6 p  u; J% l, U; e6 3 6 2 8 3 7 8 0 5;
1 b! v1 K9 Z+ m, L4 i5 G5 6 7 6 6 2 8 8 9 0;
) Z4 P  B5 z1 k, n! S3 \, N" z! ~2 V$ e
答案 ：
( w% Q4 m! c- f. E  ~& c工人2指派给城市1，工人7指派给城市2，工人4指派给城市3，工人9指派给城市4，工人8指派给城市5，工人5指派给城市6，工人6指派给城市7，工人3指派给城市8，工人1指派给城市9，工人10指派给城市10时，可取得最小费用每月1142.00元。
, j+ K+ V, _" D  `2 c- gmatlab源程序：
. R3 o9 F2 v- E! Y+ S%遗传算法
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
M=[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;
7 z4 p$ i8 J, r. A2 B, g& a    6 2 10 0 8 4 1 8 0 4;
    8 6 4 6 0 8 8 7 5 9;
: p9 s3 r; j# s6 L0 x3 N, d( z    8 5 4 6 6 0 4 8 0 3;
) G+ D0 `5 e! u5 S: S    8 6 7 9 4 3 0 7 9 5;
  N$ I+ e5 T+ a: n( p- J8 ]$ V    6 8 2 3 8 8 6 0 5 5;
    6 3 6 2 8 3 7 8 0 5;
4 |0 Z# o( _; _; f. P: Q% l( n    5 6 7 6 6 2 8 8 9 0;];
M1=M;                   %员工间每月通话时间矩阵
: [" E6 P# I1 Q8 F; ?, bfor i=1:10
- U: M5 x% R# J: D    for j=i+1:10
        M1(j,i)=M(i,j);
2 Z& R7 U2 @2 f- X    end
% s5 u& P8 }, A( p+ i2 _. eend
M2=M;                %两地间通话费率矩阵
for i=1:10
) T+ g2 A* |" P' N$ G2 f9 |    for j=i+1:10
        M2(i,j)=M(j,i);
    end
/ n( n" @# }' k8 @end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8 w3 K9 B% O6 v6 Z/ [$ p. s%初始化种群
num=10;       %种群数量
+ ]5 v* |: ]1 a* y: r4 Jcode=10;       %染色体长
6 B$ D. Y! G3 y$ vdai=100;        %遗传代数
inter=0.8;     %交叉率
byl=0.8;
%A=randperm(num*code);
for i=1:num
$ @; Q; Y6 F: G' y# S4 U6 r    V(i,:)=randperm(10);
, W1 `+ P  b& A5 o7 r% eend
5 ~& Q$ Q8 o" s; o9 W8 D%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for gen=1:dai
: B# [( L. N* l0 L8 X1 Y2 z
    %评估
) _, h6 }: H8 \1 }9 c    [num1,lin]=size(V);
    eval=zeros(num1,1);
    for i=1:num1
3 v# B* e4 @. ^0 i4 _$ K8 u        for j=1:code-1
" U0 K! J$ b) h' O5 d% V            for k=j+1:code
4 v9 O( n9 T9 U% {  u+ t/ d                eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
( F$ w9 U9 R8 W0 P            end
# A: y( P% g' G: _        end
    end
% U6 O6 L: N7 [    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %选择
/ u; e+ I2 n  X1 Z1 t% I    [eval1,ind]=sort(eval);
    V1=V;
    V=zeros(num,code);
' }8 r0 Q4 Z& ]6 g0 O    for i=1:num
        V(i,:)=V1(ind(i),:);
    end
* q4 K+ |+ F2 {- [8 _1 P    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

! R  _2 K! ]2 _1 e3 i' i4 S) X    %交叉
) N, _9 e. t8 E0 [    V1=V;
; i, p9 @0 Y: ~9 [5 h    panduan=rand(fix(num),1);        %判断是否进行交叉
    for i=1:fix(num);
        if panduan(i)<inter          %在交叉概率内进行交叉
) g/ G8 T% m8 O2 p6 q& W            V2=zeros(1,code);         %记录交叉后的染色体
9 q: [: I1 U8 c$ `5 T            h=randperm(num);                %随机取两个做交叉h(1)h(2)
            a=zeros(code,1);                 %记录未使用的位置
            b=zeros(code,1);               %记录未使用的数字
2 ^' ?6 ^! r( j* o6 t            %在双亲中随机选择基因
. b/ d7 J  n- [. S            for i=1:code
                h2=randperm(2);                %在双亲中随机选择
) Y6 Y3 X( v0 i) L                if b(V1(h(h2(1)),i))==0
2 O& q) }1 ]. p  i) M4 i2 g4 q                    V2(i)=V1(h(h2(1)),i);   b(V1(h(h2(1)),i))=1; a(i)=1;
                end
) [& C  y) t4 J' n            end
1 {) s( h% \4 ^/ [3 R
1 [% D  U; o) M            %随机分配未使用数字和位置
            h1=randperm(code);               %记录未使用的数字
' h5 ~* L. t# Q/ f  }+ H. a            for i=1:code
                for j=1:code
                    if b(i)==1&&h1(j)==i
4 N' C4 s# Y( k  C9 w                        h1(j)=0;break
1 F' u1 w" T, K$ b5 A3 J5 F8 i                    end
                end
; M1 \' O* b% ^4 }$ q            end
         
            for i=1:code
7 w, ]8 L9 T1 O; V" e  I7 ^& J2 T+ j                if V2(i)==0
4 N' u" Q- G# f) l/ D8 ~2 f  n' ]9 D                    for j=1:code
                        if h1(j)~=0
0 S* d! T+ }+ X1 x- D                            V2(i)=h1(j);h1(j)=0;break
: R7 ?( ~1 p; Z' {% T                        end
5 d9 Y; C; {8 C, j1 O                    end
: l' Z( j! g+ o' R, {: w) A                end
            end
7 s) y9 V- q0 V/ s$ F            V=[V;V2];
        end
8 L3 J' r7 S. x4 |" s    end
, T! m# X0 P! K( z
/ b3 l) Z. b* Q( K- ^) |6 Q# u# r    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  W* h3 u1 g* j5 E7 D5 p# H    %变异
    V1=V;
) K; ^8 |* B1 N+ D  W6 V    [num1,lin]=size(V);
- H# \; K9 W# Q2 L3 p/ _3 e    x3=rand(num1,1);
7 ?/ p3 p3 H0 W, @    for i=num1
5 ~: ?6 \) z5 s9 }4 r        if x3(i)<byl              %变异率
* o9 p/ u% I4 o5 N# p! w* a) ^% T, Y+ a            h2=randperm(code);
            V(i,h2(1))=V1(i,h2(2));
3 J* S; A: _9 n5 y; P7 _: f            V(i,h2(2))=V1(i,h2(1));
        end
    end
end
4 S" A% o0 }) r% Z%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/ ^  o! R! l' V, ?" q; H
) G" i8 \: }0 x& j) q%对最终种群进行评估
) d/ u9 @' _; r3 R' M5 [[num1,lin]=size(V);
eval=zeros(num1,1);
1 }- \/ E5 }( c. m. Gfor i=1:num1
    for j=1:code-1
. P( b$ n+ `7 b" e0 u& x        for k=j+1:code
            eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
        end
4 v' }8 P' x) W1 d7 b, c# r    end
& ]' v( |: F+ \$ D/ `end
& u/ r1 I" I: O( s5 g: o
. y" s. {2 E# J  C/ |) Y" R; D