遗传算法

遗传算法LN

关于遗传算法的人员安排问题，NP问题，
) R. e6 ^/ `9 o4 f; Y

遗传算法LN

如何利用工具箱求解
+ ]0 o0 O* k  V

madio

问题：
1 r% i1 A1 T1 Y' w% Q某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总电话费用尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分（因为通话的时间矩阵是对称的，没有必要写出下三角部分），n个城市两两之间通话费率表示在下面的矩阵的下三角部分（同样道理，因为通话的费率矩阵是对称的，没有必要写出上三角部分）. 试求解该二次指派问题。
0 5 3 7 9 3 9 2 9 0;
8 F% f% w! e$ p: G5 p& t) i7 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;
: a4 n, }6 x* V. h! @- _" J/ t8 6 4 6 0 8 8 7 5 9;
& U# J' ^. `8 _: x; u. U8 5 4 6 6 0 4 8 0 3;
$ k- L0 M- |0 y8 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;

答案 ：
工人2指派给城市1，工人7指派给城市2，工人4指派给城市3，工人9指派给城市4，工人8指派给城市5，工人5指派给城市6，工人6指派给城市7，工人3指派给城市8，工人1指派给城市9，工人10指派给城市10时，可取得最小费用每月1142.00元。
) ]( b: E! O4 Y0 {matlab源程序：
%遗传算法
' U$ I' I; T* F6 u% R" I% Y3 c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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;
) w. z* t/ k$ S. ^- f    6 2 10 0 8 4 1 8 0 4;
    8 6 4 6 0 8 8 7 5 9;
7 E2 z" s2 w0 z6 u( X    8 5 4 6 6 0 4 8 0 3;
  y, S! i' n& @& B- X3 ^    8 6 7 9 4 3 0 7 9 5;
    6 8 2 3 8 8 6 0 5 5;
2 o1 i& t/ g5 _* U$ q, B    6 3 6 2 8 3 7 8 0 5;
4 [5 [. P. \" s% j6 N; t4 Q5 a    5 6 7 6 6 2 8 8 9 0;];
" z6 o$ v2 Y3 L; oM1=M;                   %员工间每月通话时间矩阵
for i=1:10
6 ?6 W3 U5 C5 |" w, R, a    for j=i+1:10
, W0 B( Y0 @, u- r& T        M1(j,i)=M(i,j);
    end
end
M2=M;                %两地间通话费率矩阵
for i=1:10
    for j=i+1:10
$ u5 ?7 w# u- p8 P. _        M2(i,j)=M(j,i);
    end
) u0 ^, Q* m) y7 r7 z5 Rend
. W' i' T1 p  x, D% c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ O2 F/ T# _# `4 Z% K$ U; }# |%初始化种群
num=10;       %种群数量
' q* T. }7 d! D1 q5 `# acode=10;       %染色体长
& M" o" R+ g0 [  adai=100;        %遗传代数
6 [! ~4 j! e( o! R" g( sinter=0.8;     %交叉率
4 j' [! R& S# b/ ?& u1 xbyl=0.8;
%A=randperm(num*code);
' I( E$ s- q% R' F* l5 {4 W, vfor i=1:num
) K  ?+ L9 @! O6 n% s    V(i,:)=randperm(10);
end
& [' ^, J( @; v" |6 I5 B  w# H%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3 ?5 b& L: M# Z: m2 q- T2 i: a8 nfor gen=1:dai

7 c3 F) [( ^. ^! c, a2 ^+ W- ~    %评估
    [num1,lin]=size(V);
. L% H% Z1 U4 Y" G3 R' T, L    eval=zeros(num1,1);
1 L$ ]' W, j( M6 b# P- I; I% t    for i=1:num1
        for j=1:code-1
# d1 M' @. d3 @6 s            for k=j+1:code
1 i* z9 F# Z  E+ `2 i, q' `                eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
            end
1 ?6 `2 O$ s6 {% W; {8 T        end
    end
( J/ c; R7 L6 s/ T+ C    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %选择
8 N) K6 L- O- v' a    [eval1,ind]=sort(eval);
    V1=V;
/ [2 B, C" n9 a7 Y) g+ J4 m    V=zeros(num,code);
    for i=1:num
* c. e( ]: y; A/ [# \8 S6 _: [6 k        V(i,:)=V1(ind(i),:);
    end
2 c! [& y2 _" |3 o  ]5 `( b5 z1 Z( U    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
& I) Z, ~, n4 s% N% f
    %交叉
    V1=V;
( @8 D, J! j3 Q1 I) c    panduan=rand(fix(num),1);        %判断是否进行交叉
    for i=1:fix(num);
        if panduan(i)<inter          %在交叉概率内进行交叉
            V2=zeros(1,code);         %记录交叉后的染色体
$ Q6 Q1 f1 F5 F            h=randperm(num);                %随机取两个做交叉h(1)h(2)
$ E. |) \% V6 c3 V8 q            a=zeros(code,1);                 %记录未使用的位置
            b=zeros(code,1);               %记录未使用的数字
: ?; ~7 F2 E2 u7 Z: M8 x7 y( u            %在双亲中随机选择基因
5 o! a5 D# }, r9 Q% U# f( f            for i=1:code
& R& y# W* E; A                h2=randperm(2);                %在双亲中随机选择
' A3 o7 c- n- M9 o2 T) l                if b(V1(h(h2(1)),i))==0
5 J/ b; s+ a/ v* w- w                    V2(i)=V1(h(h2(1)),i);   b(V1(h(h2(1)),i))=1; a(i)=1;
5 }* }% [  b1 H) c                end
1 L& v, d3 l9 [" t1 k" w            end

            %随机分配未使用数字和位置
7 Z3 y5 S8 U) y( u; o  g5 x            h1=randperm(code);               %记录未使用的数字
            for i=1:code
                for j=1:code
8 V# ^, F6 A$ N8 N8 i* {9 h                    if b(i)==1&&h1(j)==i
                        h1(j)=0;break
3 |  v8 Q0 n4 ]+ d) A                    end
                end
- a6 L; ?' n# }4 |            end
         
            for i=1:code
                if V2(i)==0
                    for j=1:code
                        if h1(j)~=0
                            V2(i)=h1(j);h1(j)=0;break
                        end
                    end
3 Q$ p* ~& X, K( I4 `3 \                end
+ o8 M/ t) L! g& T( P8 J            end
            V=[V;V2];
* \& A) \* B1 m, {  T9 I: Z1 p        end
' z, S& A" q, l! ], c6 y/ Z% X    end

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %变异
    V1=V;
    [num1,lin]=size(V);
. m8 X- y1 q2 e7 r( r9 U1 X8 D    x3=rand(num1,1);
    for i=num1
        if x3(i)<byl              %变异率
            h2=randperm(code);
            V(i,h2(1))=V1(i,h2(2));
. x/ b1 O9 t& c            V(i,h2(2))=V1(i,h2(1));
6 O% F  l1 |5 v" i6 p        end
. Y9 O( p6 @( L    end
# G4 \# P0 S! l4 Kend
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
7 A- `2 p5 J# @
% [6 J& G/ [4 |/ l* _6 y%对最终种群进行评估
[num1,lin]=size(V);
eval=zeros(num1,1);
for i=1:num1
) L, p* }* a1 Q0 @    for j=1:code-1
5 S' R& p$ m, }* s" X9 w0 ~; s# C. G        for k=j+1:code
. ?4 x! L; F! M% W! D! r. t            eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
        end
    end
; _- _1 Z* h1 F* \% s; [/ ~# vend
; q, `) |# W) _
$ J% e  ^$ o* h% ~5 S& ?