遗传算法

遗传算法LN

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

遗传算法LN

如何利用工具箱求解
! ^* D7 x- m& Y% c  O4 w+ K

madio

问题：
某公司指派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;
; S: e& N1 j* {9 t6 2 10 0 8 4 1 8 0 4;
4 u6 N3 v& X+ ], }% n8 6 4 6 0 8 8 7 5 9;
+ ?. ^2 `0 d8 F3 }6 i& t8 5 4 6 6 0 4 8 0 3;
" d8 x1 O: }1 _' p- ~# y6 r  r8 6 7 9 4 3 0 7 9 5;
6 8 2 3 8 8 6 0 5 5;
5 }9 ^+ i) A% `' }6 3 6 2 8 3 7 8 0 5;
+ K2 O5 m( J$ ?0 v5 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元。
3 c4 n+ W2 R  |3 Y+ H! l1 Omatlab源程序：
%遗传算法
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
! O) L( }  ^/ F6 m8 j# B& h" rM=[0 5 3 7 9 3 9 2 9 0;
    7 0 7 8 3 2 3 3 5 7;
, ]1 l: `1 t) a, l    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;
  h# _% g) n; \( s" {7 b4 t  u    8 5 4 6 6 0 4 8 0 3;
" Z% r" ]6 Z! d* l8 V8 ^( A% ]( {* ^    8 6 7 9 4 3 0 7 9 5;
: e8 F' j% a/ S6 \* |/ n  _    6 8 2 3 8 8 6 0 5 5;
4 k' T, p  A% T) S    6 3 6 2 8 3 7 8 0 5;
+ D6 ~; Z/ Y: }( c, f( p7 u  s    5 6 7 6 6 2 8 8 9 0;];
M1=M;                   %员工间每月通话时间矩阵
" e7 o& c8 t4 r5 O! j( D4 w: dfor i=1:10
    for j=i+1:10
        M1(j,i)=M(i,j);
. e$ [9 g" U/ f& }7 }- r6 c    end
3 K( s) S3 k2 t: Y7 N- Oend
M2=M;                %两地间通话费率矩阵
) c& I8 l. p4 ]for i=1:10
    for j=i+1:10
        M2(i,j)=M(j,i);
4 b6 {6 X0 e$ X) c    end
end
! ]6 K% k# i) }# k- k! a%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2 G) I, a2 C6 @! S( C( J' e%初始化种群
6 h$ ~# h9 A* x5 Jnum=10;       %种群数量
! I, M& `3 C8 X% g7 r% N% ~" s+ Zcode=10;       %染色体长
& G( u& A" B) I. H6 X- Jdai=100;        %遗传代数
inter=0.8;     %交叉率
byl=0.8;
* r5 w4 J2 i6 r  P5 y/ d, Y%A=randperm(num*code);
* i( p2 B; J# s- n2 |0 efor i=1:num
    V(i,:)=randperm(10);
0 j, j( E" Y! Y+ b1 Yend
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for gen=1:dai

    %评估
: i, u( j" G9 q% _& ~* R    [num1,lin]=size(V);
/ p6 G/ N- r; n: b- n$ E" Y1 _: |    eval=zeros(num1,1);
    for i=1:num1
7 x8 S+ M/ W' I/ U7 O, n        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
    end
1 A# m. q& c8 X$ j. k4 M2 g% P5 N  U    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% A9 ~4 K) ~" S* S    %选择
    [eval1,ind]=sort(eval);
) B$ G6 C& u$ g6 K4 X    V1=V;
8 f' q2 O/ Q9 L, \$ a/ ~+ _    V=zeros(num,code);
9 g1 N, D! m% Z  y    for i=1:num
' g% d  L  [; ~        V(i,:)=V1(ind(i),:);
    end
5 p& ~( |$ ]4 W. u9 N& O    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
( h4 K* p8 X- z4 p( Y$ k
    %交叉
) W4 W. y; n, l* ~. u! V5 C    V1=V;
' `% w# T0 b# ~# D4 c    panduan=rand(fix(num),1);        %判断是否进行交叉
+ ?4 g: ?# e, i5 I4 ^. Q    for i=1:fix(num);
        if panduan(i)<inter          %在交叉概率内进行交叉
            V2=zeros(1,code);         %记录交叉后的染色体
            h=randperm(num);                %随机取两个做交叉h(1)h(2)
( r) k8 R  N( m( g* m            a=zeros(code,1);                 %记录未使用的位置
, V7 B- C* Y# T4 ~            b=zeros(code,1);               %记录未使用的数字
8 M, i; @3 A3 G! K3 O6 O* V; E            %在双亲中随机选择基因
$ G% R( C2 V) L            for i=1:code
                h2=randperm(2);                %在双亲中随机选择
% F0 e- ?. x( n7 o9 d                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
/ x7 a" [5 z/ ~3 e% i! U: g5 W            end
7 S+ z8 H  G1 I* L
6 _9 p1 t5 \# z) c  h" K            %随机分配未使用数字和位置
! o9 g2 Q# _: `9 @4 x) g            h1=randperm(code);               %记录未使用的数字
            for i=1:code
                for j=1:code
/ j& D# |/ D/ N5 m2 n                    if b(i)==1&&h1(j)==i
                        h1(j)=0;break
                    end
, ^/ D2 h* A9 D+ |) @' Y) `                end
            end
         
0 `3 f, \+ Y$ I$ f! E6 l. t            for i=1:code
                if V2(i)==0
- D8 |9 p; Z# ]: f3 u2 S                    for j=1:code
                        if h1(j)~=0
                            V2(i)=h1(j);h1(j)=0;break
! m6 ~9 s& L# l' d4 x1 I$ c                        end
& X& c9 e; y; T% L& S; x                    end
                end
1 d8 O# H& {( O. v) G- }            end
7 [0 a$ M1 q0 W+ {8 {! J            V=[V;V2];
        end
5 P4 `. a6 i* W    end

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/ }) [& ^) V$ p/ ]2 O    %变异
1 Q6 s7 [& e. F; p4 M    V1=V;
# J$ q) a% B% Z, [1 c    [num1,lin]=size(V);
0 u9 w5 s' Q* y6 F( H1 G1 R    x3=rand(num1,1);
    for i=num1
        if x3(i)<byl              %变异率
' a/ a) Z7 m* E0 N! D            h2=randperm(code);
            V(i,h2(1))=V1(i,h2(2));
5 W: I: n- j. `$ H            V(i,h2(2))=V1(i,h2(1));
        end
  t* E- k, v5 V. q  Q    end
end
) K8 ?' h% M! R5 Z3 V: c& C7 `% y%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/ V) s- z1 e5 G
) A, K1 {" K, P& b* Q# {%对最终种群进行评估
[num1,lin]=size(V);
  u6 t: V7 ~, n" {. q6 [' p% Feval=zeros(num1,1);
for i=1:num1
    for j=1:code-1
  |& m, U( a0 x        for k=j+1:code
9 `5 [* F; G9 g, S4 V: h$ N# i0 t            eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
/ `+ Z) P& e! B; q        end
8 a" e+ y7 V! F9 x$ m9 ^' k' h    end
: l, F. c( V/ nend
# i' `7 t0 n% e
2 f+ O9 k+ ^4 I+ J' `% l