遗传算法

遗传算法LN

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

遗传算法LN

如何利用工具箱求解
2 d  v# i: y+ r( I: c

madio

问题：
; s5 W, i1 o$ S& U- o某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总电话费用尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分（因为通话的时间矩阵是对称的，没有必要写出下三角部分），n个城市两两之间通话费率表示在下面的矩阵的下三角部分（同样道理，因为通话的费率矩阵是对称的，没有必要写出上三角部分）. 试求解该二次指派问题。
* a( L* E& N8 X/ @0 5 3 7 9 3 9 2 9 0;
2 h9 y* V/ B$ B/ j7 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;
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;
( H' n, [. L& V: Z) j3 D8 T
: B; ^$ n6 h8 x* D" [) h答案 ：
; N/ T8 q5 G% r- A$ V2 C工人2指派给城市1，工人7指派给城市2，工人4指派给城市3，工人9指派给城市4，工人8指派给城市5，工人5指派给城市6，工人6指派给城市7，工人3指派给城市8，工人1指派给城市9，工人10指派给城市10时，可取得最小费用每月1142.00元。
1 i6 x, U, a: ?/ J* Mmatlab源程序：
%遗传算法
: P: z* r- h9 v" R9 u6 M2 `+ E& v%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
7 [" i4 _" I2 Q% n% oM=[0 5 3 7 9 3 9 2 9 0;
5 O" m! s# a7 y! t6 I6 l    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;
% O: e& Z% a% A2 p$ `8 y    8 6 4 6 0 8 8 7 5 9;
, a3 G# V0 s9 H  V! c" Q    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;
8 \2 N: }; h  j/ D: P    5 6 7 6 6 2 8 8 9 0;];
% g2 D8 Z* Y" H  }8 d1 N8 mM1=M;                   %员工间每月通话时间矩阵
for i=1:10
4 O1 X1 m, S  F- v: @    for j=i+1:10
        M1(j,i)=M(i,j);
    end
end
7 K8 F1 L! [8 [' s4 F5 UM2=M;                %两地间通话费率矩阵
4 Q+ Y# J9 Y, ]( sfor i=1:10
    for j=i+1:10
6 h. ^1 N/ {: |* d8 c5 H& H        M2(i,j)=M(j,i);
: a8 c5 X$ T' k) ^. W$ X2 M    end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%初始化种群
num=10;       %种群数量
code=10;       %染色体长
dai=100;        %遗传代数
$ D( m; R) k. @4 ~inter=0.8;     %交叉率
- F8 k2 h( b2 `byl=0.8;
%A=randperm(num*code);
+ ~% t' t2 J+ W* B' p# C8 nfor i=1:num
- G- m  V. q9 M  X& n+ \9 w% ?7 J) e    V(i,:)=randperm(10);
6 V8 ?/ u  @3 B( T5 |9 ?end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
! _2 n0 T5 S7 w2 k9 [! Jfor gen=1:dai

5 Z7 c( q) x1 W1 A$ ?' l" l6 G    %评估
    [num1,lin]=size(V);
$ E+ m5 J7 d+ B" T& S    eval=zeros(num1,1);
" x0 E9 H6 g3 T0 \( N    for i=1:num1
/ V* p9 z# \5 w: ~4 I# o: W9 ~; t: a        for j=1:code-1
4 ~. O& b( O, }5 k, `- }            for k=j+1:code
                eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
. l$ a3 q4 Q4 O3 h' Z0 [. v6 E# R            end
        end
/ B3 x2 u4 X) w; y$ J$ T0 C2 k    end
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %选择
    [eval1,ind]=sort(eval);
    V1=V;
4 [: @% B' ?+ W* `2 M, R+ k4 R6 \    V=zeros(num,code);
    for i=1:num
        V(i,:)=V1(ind(i),:);
    end
6 Q) f3 r5 P( i4 k1 j% o    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
. h, d! a/ m) b( _; G4 O
$ D; ~: I: {5 \( B    %交叉
    V1=V;
    panduan=rand(fix(num),1);        %判断是否进行交叉
    for i=1:fix(num);
7 ~9 O. `- n3 ^        if panduan(i)<inter          %在交叉概率内进行交叉
            V2=zeros(1,code);         %记录交叉后的染色体
5 ^8 d% g1 ], A            h=randperm(num);                %随机取两个做交叉h(1)h(2)
" q1 w+ F6 G$ s$ s! Z            a=zeros(code,1);                 %记录未使用的位置
% q! {2 Q  ^0 ^/ Y' ^: d            b=zeros(code,1);               %记录未使用的数字
            %在双亲中随机选择基因
            for i=1:code
                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;
  X% K/ D3 q1 ^/ s) ~                end
4 L- r# i8 S4 X' y, a5 u/ K            end

5 n5 |. o9 U& o, C9 |            %随机分配未使用数字和位置
            h1=randperm(code);               %记录未使用的数字
6 I9 n! w3 A0 `* h" k* `            for i=1:code
* Y5 l1 a, }9 g                for j=1:code
                    if b(i)==1&&h1(j)==i
: t5 z, \" {- G+ I                        h1(j)=0;break
$ K3 f+ L5 B7 a8 D                    end
                end
- ^( m- U6 @8 F- M- L- U            end
         
; m0 j. N, f9 n- P; j0 u# g            for i=1:code
                if V2(i)==0
9 ]! i! U: L: j& ^* }- ~( y- t; C                    for j=1:code
                        if h1(j)~=0
, Q+ j/ |! ]3 Z+ |9 [( h                            V2(i)=h1(j);h1(j)=0;break
6 P* B+ U; m# V0 _. e                        end
1 q5 R% i! l1 t! n1 P! q! M, z                    end
$ a* w0 f1 ^. i( L9 h: o                end
            end
8 p# e9 M+ A0 @; F( f3 S, g            V=[V;V2];
) c% W2 J, S: [' k5 W# {3 K, r        end
    end

7 I7 h3 t+ ?0 y1 d- o    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
# s; L  L5 i* S- D# b7 Q    %变异
    V1=V;
    [num1,lin]=size(V);
2 p9 ^) {$ h: ~- p    x3=rand(num1,1);
    for i=num1
        if x3(i)<byl              %变异率
0 N+ U1 i6 q0 t" H+ m& |. i            h2=randperm(code);
            V(i,h2(1))=V1(i,h2(2));
            V(i,h2(2))=V1(i,h2(1));
5 @) `- M7 V7 o% O6 f        end
    end
end
& T/ q, Z0 V4 u8 F, O$ g%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6 w$ }5 {% P; U5 ^" ~9 X# c% a
%对最终种群进行评估
0 W) H2 u- K4 d5 W[num1,lin]=size(V);
5 h; b0 }& d1 I8 o5 z0 C" H) teval=zeros(num1,1);
for i=1:num1
0 e6 M2 e  m) D    for j=1:code-1
9 o/ Z  b3 u9 f* @        for k=j+1:code
            eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
        end
    end
# E4 g$ I5 p9 j+ E5 bend
+ i4 ~' i; x) L; Z; C; W) Y$ b, s
5 i% Y& q# @3 O) S5 Z3 p, _