遗传算法

遗传算法LN

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

遗传算法LN

如何利用工具箱求解
& O2 b) z" A' g+ h9 U( m0 u3 t

madio

问题：
1 ~* }, G- q9 |0 W9 [3 g某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总电话费用尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分（因为通话的时间矩阵是对称的，没有必要写出下三角部分），n个城市两两之间通话费率表示在下面的矩阵的下三角部分（同样道理，因为通话的费率矩阵是对称的，没有必要写出上三角部分）. 试求解该二次指派问题。
! Z2 T7 m& ~! O0 C0 5 3 7 9 3 9 2 9 0;
0 Q. E3 g* U+ w' @# r$ E8 G! \. k% h7 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;
0 q9 T$ |- b# C4 Y8 6 4 6 0 8 8 7 5 9;
: H- B/ _+ G5 N* Y8 5 4 6 6 0 4 8 0 3;
: v& I2 T& g9 Q, C/ n2 V8 6 7 9 4 3 0 7 9 5;
6 8 2 3 8 8 6 0 5 5;
4 z7 L, a2 j" s% h/ M/ [6 3 6 2 8 3 7 8 0 5;
5 6 7 6 6 2 8 8 9 0;

答案 ：
工人2指派给城市1，工人7指派给城市2，工人4指派给城市3，工人9指派给城市4，工人8指派给城市5，工人5指派给城市6，工人6指派给城市7，工人3指派给城市8，工人1指派给城市9，工人10指派给城市10时，可取得最小费用每月1142.00元。
5 I; ]1 Y$ @2 y4 p. @; rmatlab源程序：
: R; _# Y8 s4 N% t%遗传算法
* A3 K+ \5 i& u! v" ~2 m" \& J2 T6 U%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
M=[0 5 3 7 9 3 9 2 9 0;
6 {+ J' ]6 y) l* ?* z4 C    7 0 7 8 3 2 3 3 5 7;
    4 8 0 9 3 5 3 3 9 3;
3 B+ [# f# U6 Z    6 2 10 0 8 4 1 8 0 4;
    8 6 4 6 0 8 8 7 5 9;
9 A. |; C, {' j( O" U    8 5 4 6 6 0 4 8 0 3;
( ]9 S8 B& J& T% n: H& h1 u$ }    8 6 7 9 4 3 0 7 9 5;
$ @3 U4 R  F% r3 H+ i+ y    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;];
9 F7 L3 O) `! iM1=M;                   %员工间每月通话时间矩阵
7 b1 j2 ?5 Z6 l* Kfor i=1:10
. W. @% m( e7 F5 ]3 o* v% t) h    for j=i+1:10
        M1(j,i)=M(i,j);
    end
end
& j7 N( n5 w! [( oM2=M;                %两地间通话费率矩阵
- J4 k0 l2 H% q, I( q8 \. [for i=1:10
    for j=i+1:10
* N/ s( F, \. g  K- M, C: t& v9 q" m        M2(i,j)=M(j,i);
) y% T$ P  t/ ?* r2 A; ]: J    end
end
" k+ V+ a5 m8 \7 Y+ D& Q/ E" ]/ H%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
! O0 G  B1 ~, S) ~%初始化种群
0 q6 `' y. q1 anum=10;       %种群数量
% O" p9 d) D* t! X0 K7 d, T8 ?$ fcode=10;       %染色体长
4 o; m% G! T  ~# A4 ~dai=100;        %遗传代数
inter=0.8;     %交叉率
: P5 @; ]: ]6 C7 E( _byl=0.8;
; P* n" a9 x  R6 S0 t0 c- I%A=randperm(num*code);
for i=1:num
6 \7 L! N$ i) t' t, o    V(i,:)=randperm(10);
end
9 T! J0 Z1 O" `: N- u%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for gen=1:dai

# w! J4 ^" I7 t) V    %评估
' s& _* A! }3 A+ Q/ s- x' q    [num1,lin]=size(V);
- Y, ], R2 O1 `9 |, b    eval=zeros(num1,1);
  u# F/ w9 }/ w5 Z3 j    for i=1:num1
5 b! a6 e2 }  X! a  n: g1 b, U        for j=1:code-1
8 |0 M1 S  o5 j' M: j- S            for k=j+1:code
+ P- }9 ~! P6 h, ~                eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
+ ?4 T1 T8 u6 t* v. h% p! f- K            end
& q: x" G1 x, p6 r; f1 r        end
    end
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
, O4 z# Q: N0 Q( Q    %选择
: C5 f3 D) G" B, g5 v  B    [eval1,ind]=sort(eval);
    V1=V;
    V=zeros(num,code);
    for i=1:num
        V(i,:)=V1(ind(i),:);
    end
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    %交叉
' ~: m- g5 B1 \    V1=V;
% b& c, A. Q. G- u1 k    panduan=rand(fix(num),1);        %判断是否进行交叉
    for i=1:fix(num);
' w; C. {: _+ I& E        if panduan(i)<inter          %在交叉概率内进行交叉
            V2=zeros(1,code);         %记录交叉后的染色体
) @7 h3 N9 ?& V! f' A            h=randperm(num);                %随机取两个做交叉h(1)h(2)
& h( g) a3 U- A3 h, V1 s' b5 _) `            a=zeros(code,1);                 %记录未使用的位置
            b=zeros(code,1);               %记录未使用的数字
            %在双亲中随机选择基因
            for i=1:code
                h2=randperm(2);                %在双亲中随机选择
8 s5 U! H( x/ `/ H1 u9 ]" S* U) B% r                if b(V1(h(h2(1)),i))==0
9 `$ T4 y' D* z                    V2(i)=V1(h(h2(1)),i);   b(V1(h(h2(1)),i))=1; a(i)=1;
3 b2 L& p) ?& U! Q) J0 v' w                end
7 Y1 w# `) M; Y. }5 H6 }, y% X            end

            %随机分配未使用数字和位置
            h1=randperm(code);               %记录未使用的数字
            for i=1:code
                for j=1:code
                    if b(i)==1&&h1(j)==i
                        h1(j)=0;break
                    end
                end
* l( E7 k& x# z# U$ o            end
6 O; z- ?7 G2 m4 H# p: e0 V         
            for i=1:code
4 Q! Y# q) q- L2 _/ k9 g6 T                if V2(i)==0
( F0 [3 g8 v" y7 P& x! b                    for j=1:code
: H5 I2 P0 X+ z$ p2 [6 c1 g1 c                        if h1(j)~=0
. s0 ?6 y3 d$ e9 w& V7 a                            V2(i)=h1(j);h1(j)=0;break
                        end
                    end
                end
" r! \5 _- T: x. I: p* p            end
            V=[V;V2];
0 U7 X: j5 H' U* h: s" {. p        end
    end
# x7 V5 T1 |4 [0 d+ ]- e3 w
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %变异
( {' y: V: i8 _2 ~    V1=V;
    [num1,lin]=size(V);
* z/ I, Y- }& C    x3=rand(num1,1);
    for i=num1
        if x3(i)<byl              %变异率
1 S! z6 q% X7 }  J3 o            h2=randperm(code);
            V(i,h2(1))=V1(i,h2(2));
6 h; n7 a/ L# v' W            V(i,h2(2))=V1(i,h2(1));
  G% _+ z5 b, h8 F        end
4 c7 J% t5 b6 N$ u% U$ P    end
end
- `; ?' f8 X# E, [0 a7 _%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
( g/ F* i. D5 j1 d7 a% ~8 k" r3 @7 t
%对最终种群进行评估
/ X. k! E  k0 v+ K% ^[num1,lin]=size(V);
1 P7 V: U$ i" p! e% Q& Ueval=zeros(num1,1);
for i=1:num1
    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
7 [7 A% x3 Q- y% U2 Z7 c9 lend
$ h/ T' l: P3 k* A8 j
6 F: z' r: x5 K0 U+ _  G1 M