遗传算法

遗传算法LN

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

遗传算法LN

如何利用工具箱求解
2 l7 G+ k2 z1 _( i8 Y; ^

madio

问题：
某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总电话费用尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分（因为通话的时间矩阵是对称的，没有必要写出下三角部分），n个城市两两之间通话费率表示在下面的矩阵的下三角部分（同样道理，因为通话的费率矩阵是对称的，没有必要写出上三角部分）. 试求解该二次指派问题。
! e5 g  x( _7 H3 y, Q( L+ c0 5 3 7 9 3 9 2 9 0;
7 0 7 8 3 2 3 3 5 7;
/ D$ r4 s: q; ]0 v& P$ \: |' K4 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;
) `) E# c5 x) L$ G8 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 t6 r' ?* v" F5 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元。
matlab源程序：
%遗传算法
5 a. ~3 ^9 Y: T# r6 \4 \9 ?: s%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
M=[0 5 3 7 9 3 9 2 9 0;
9 T* f, p4 E! [7 ?# c3 N" \+ p% t    7 0 7 8 3 2 3 3 5 7;
    4 8 0 9 3 5 3 3 9 3;
, _7 [% \3 F2 O3 J2 q- |    6 2 10 0 8 4 1 8 0 4;
' i" U0 p% ^. R: h    8 6 4 6 0 8 8 7 5 9;
/ Y+ _" R- J. V  {4 `; e: F    8 5 4 6 6 0 4 8 0 3;
    8 6 7 9 4 3 0 7 9 5;
# f' k: N/ s! }+ K    6 8 2 3 8 8 6 0 5 5;
: A' v4 P9 j; }6 j+ k    6 3 6 2 8 3 7 8 0 5;
+ Q0 W, F8 S0 P9 l2 [/ k    5 6 7 6 6 2 8 8 9 0;];
M1=M;                   %员工间每月通话时间矩阵
for i=1:10
) J$ A( Q4 F: y& O2 [1 r" s    for j=i+1:10
4 L) l' ]( b$ M9 B" f7 t, E) e        M1(j,i)=M(i,j);
    end
  h2 j. p, ^' r" u# Nend
M2=M;                %两地间通话费率矩阵
$ T' ~3 m" o& ~/ X% vfor i=1:10
    for j=i+1:10
. h1 Y" D/ v7 h        M2(i,j)=M(j,i);
8 z  D( K6 Y8 w5 E& b' d3 X    end
3 n0 F2 g; C# [0 u1 g- mend
+ Z! j1 B% A' I8 g) H+ K6 w%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
0 d. O9 O, v1 y2 k2 z%初始化种群
% L* ]! ?5 \; Z9 m- W6 Gnum=10;       %种群数量
% g$ o4 T9 t( V  z# kcode=10;       %染色体长
dai=100;        %遗传代数
inter=0.8;     %交叉率
! m0 @0 |( C& o: l! R3 gbyl=0.8;
$ Z! f. V8 S5 P, T* U4 B%A=randperm(num*code);
for i=1:num
    V(i,:)=randperm(10);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for gen=1:dai
4 l! s& `5 S1 M2 E, U5 ^) ^) H
    %评估
& O( ?- Q% V* Y# C7 m8 _" ]    [num1,lin]=size(V);
    eval=zeros(num1,1);
3 g; U- L) w  i, N' I" t) j- b    for i=1:num1
- K& {0 ~7 ~6 [        for j=1:code-1
2 P1 p/ f# M' e; |            for k=j+1:code
5 |, Q9 P8 ]( [6 M+ j                eval(i)=M1(V(i,j),V(i,k))*M2(j,k)+eval(i);
            end
8 _' o% Q$ }2 {) V3 J( ~        end
% [% o. K5 [; v3 j0 o! n. \    end
% N: \/ v$ r; B3 V6 E    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %选择
; Q( u2 [1 G$ n    [eval1,ind]=sort(eval);
    V1=V;
    V=zeros(num,code);
, G8 G/ W1 q6 c: Q% w/ C- {8 c) M8 e2 o    for i=1:num
        V(i,:)=V1(ind(i),:);
    end
9 h# ]& C/ G' W    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
: U0 F+ Y3 q2 U3 i$ h
( c3 e2 ~, V& G8 B, \3 Q, l* e    %交叉
    V1=V;
    panduan=rand(fix(num),1);        %判断是否进行交叉
    for i=1:fix(num);
        if panduan(i)<inter          %在交叉概率内进行交叉
            V2=zeros(1,code);         %记录交叉后的染色体
            h=randperm(num);                %随机取两个做交叉h(1)h(2)
( Q( z5 Z; N3 b3 a$ b            a=zeros(code,1);                 %记录未使用的位置
            b=zeros(code,1);               %记录未使用的数字
            %在双亲中随机选择基因
& L% n! O) l( U& V            for i=1:code
                h2=randperm(2);                %在双亲中随机选择
                if b(V1(h(h2(1)),i))==0
9 u2 C& b; q7 `$ V* j/ f                    V2(i)=V1(h(h2(1)),i);   b(V1(h(h2(1)),i))=1; a(i)=1;
2 [' C7 p) p! A  h  b                end
# h$ D) M8 l6 }- Y$ s            end
% |& r! X3 M* @1 Y
3 M- I, `# s2 V1 q' V            %随机分配未使用数字和位置
            h1=randperm(code);               %记录未使用的数字
9 A/ i7 E3 G; d0 x, p0 E            for i=1:code
& v: B. a5 l* ~- {                for j=1:code
                    if b(i)==1&&h1(j)==i
* O& r  L" G: f. R0 h1 X                        h1(j)=0;break
                    end
* G0 R' u3 k" x: C: t                end
            end
2 i4 V9 f" I0 k         
9 V& K, u5 p5 F$ @4 B0 k- `            for i=1:code
% @0 f$ m+ d+ b                if V2(i)==0
, n, e. Y/ }. g; {" W                    for j=1:code
                        if h1(j)~=0
8 B$ j2 n: J  _9 K                            V2(i)=h1(j);h1(j)=0;break
! m: ~/ e, n5 w7 P; t$ J) y6 Y& A4 f                        end
0 P4 d! z5 Y" {                    end
6 R8 K3 `0 z/ c# O% l0 q                end
            end
            V=[V;V2];
        end
    end
: y5 F1 s) X2 `+ V* O- I# B0 r
6 o& R% G" L( |# m0 w    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
. e5 s# X8 b2 ^- h' R9 r* }9 G: G    %变异
( Q$ v8 N6 F9 b0 ?    V1=V;
    [num1,lin]=size(V);
! T% ^4 B! Q' ?5 T    x3=rand(num1,1);
    for i=num1
1 V5 C9 x) M' S. H) b, U- O# E1 d$ C        if x3(i)<byl              %变异率
, w! ?6 g4 U) C- \6 v( W2 t- M3 W            h2=randperm(code);
" I: [$ ^3 _, Z- J. V            V(i,h2(1))=V1(i,h2(2));
            V(i,h2(2))=V1(i,h2(1));
" F2 e0 s5 s! K4 v        end
    end
) g/ J3 f5 f" }4 n$ r. I" N3 h$ Fend
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%对最终种群进行评估
. j# i3 i- A. i- Q  R( |[num1,lin]=size(V);
eval=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
end

. E7 ?/ c# I' j