[分享]从网上找到的一些解决TSP问题的算法及源代码

ilikenba

<>模拟退火算法
　　模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，</P>
<>内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis</P>
8 X+ X* G7 f+ j+ X<>准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退</P>
4 H$ G- ^' |- w& A+ i* d<>火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始</P>
<>解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的</P>
<>当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling </P>
5 c8 j8 ]1 B9 l$ s<>Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
3.5.1 模拟退火算法的模型
8 w7 ^1 B( c. n　　模拟退火算法可以分解为解空间、目标函数和初始解三部分。
　模拟退火的基本思想:
; |2 f, v& A) _3 C　　(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L
　　(2) 对k=1，……，L做第(3)至第6步：
  h0 H8 e7 C0 j: p! M6 u/ ~　　(3) 产生新解S′
　　(4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数
　　(5) 若Δt′&lt;0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.
2 y4 B$ I& S& f) [8 Y* x　　(6) 如果满足终止条件则输出当前解作为最优解，结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法。
8 Y! J' c" @. U* H% c9 o　　(7) T逐渐减少，且T-&gt;0，然后转第2步。
! Y1 K* p  U' X" X" g算法对应动态演示图：
模拟退火算法新解的产生和接受可分为如下四个步骤：
　　第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当</P>
- N7 i) q4 b$ ~, [; d- U<>前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法</P>
" g# u. E4 X* A9 p7 u% A<>决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
, q/ M5 U2 G2 I9 v8 p　　第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。</P>
. k) [+ z4 H, p: u4 c<>事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
　　第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若Δt′&lt;0则接受S′作</P>
/ j, d8 m  J/ z9 L<>为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。
　　第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正</P>
$ O) ], O) g& ?1 Z0 @' d<>目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的</P>
1 H. P: J( v2 X+ r/ A4 \. L4 u( r<>基础上继续下一轮试验。
. E& u5 F! r; X% r& h6 F: J　　模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在</P>
' k" _$ @: @+ |- M<>理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。 </P>
2 ^3 \. C* h- W3 L$ v3 s3 z<>3.5.2 模拟退火算法的简单应用
　　作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem，简记为TSP)：设有n个城市，用数码1,…,n代表</P>
<>。城市i和城市j之间的距离为d(i，j) i, j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最</P>
<>短.。
　　求解TSP的模拟退火算法模型可描述如下：
2 V' a$ Q8 Z# _, r' r　　解空间 解空间S是遍访每个城市恰好一次的所有回路，是{1，……，n}的所有循环排列的集合，S中的成员记为(w1,w2 ,…</P>
9 s5 v4 L2 c4 w& D<>…，wn)，并记wn+1= w1。初始解可选为(1，……，n)
" Q, n0 X1 D& ]8 L* q6 l0 m　　目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数： </P>
' D5 E4 Z7 j+ G2 p6 K4 w3 b<>　　我们要求此代价函数的最小值。
　　新解的产生 随机产生1和n之间的两相异数k和m，若k&lt;m，则将
　　(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
; N7 T" ^; ?$ U3 Z: Q　　变为：
　　(w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn).
　　如果是k&gt;m，则将
/ K4 V0 l: J1 I. [: M　　(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
　　变为：
# \. ]) z+ s6 q$ O$ P* X　　(wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk).
　　上述变换方法可简单说成是“逆转中间或者逆转两端”。
　　也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。
　　代价函数差 设将(w1, w2 ,……，wn)变换为(u1, u2 ,……，un), 则代价函数差为： </P>
<>根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序：
) R7 D/ @# a, f9 _) t  wProcedure TSPSA:
　begin
* m' M5 s' |$ u: A& l　　init-of-T; { T为初始温度}
, p% a) [  h% ^% F　　S={1，……，n}; {S为初始值}
　　termination=false;
　　while termination=false
　　　begin
% k; V6 \. M$ [$ O4 S) f　　　　for i=1 to L do
　　　　　　begin
' M3 |  Q5 Q! O; i3 i) v　　　　　　　　generate(S′form S); { 从当前回路S产生新回路S′}
4 _; s/ K0 J0 C& d$ ^7 J+ }　　　　　　　　Δt:=f(S′))-f(S);{f(S)为路径总长}
$ p' E- z# \) U# o　　　　　　　　IF(Δt&lt;0) OR (EXP(-Δt/T)&gt;Random-of-[0,1])
* g3 c" ~" `: N' ^　　　　　　　　S=S′;
' I) E& t# l5 V: w. T1 P: ^: H  x; g　　　　　　　　IF the-halt-condition-is-TRUE THEN
' i% Q" \& x& t" j8 N% j' u* B; p　　　　　　　　termination=true;
" C4 J, C( V9 z+ @8 D: \! U- n　　　　　　End;
, p) B' _3 W/ K　　　　T_lower;
　　　End;
* f# j& [; n8 c  n/ w　End
3 A( D  k+ M8 H　　模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack </P>
<>roblem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。 </P>
% Z" K+ Y8 C4 v$ E6 H: j* q1 ^; ?6 z2 \) |3 c<>3.5.3 模拟退火算法的参数控制问题
/ F. m# N, [1 u8 B$ k3 f4 M3 U) }　　模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：
# A: }% |  S: b　　(1) 温度T的初始值设置问题。
　　温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但</P>
<>因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要</P>
<>依据实验结果进行若干次调整。
7 Y6 v2 t1 d; u5 H/ W" E3 P/ x　　(2) 退火速度问题。
% K, D& g/ |" p6 c　　模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这</P>
<>需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
+ e. R! C# K5 J! o& Q  B0 B3 t+ ~5 x　　(3) 温度管理问题。
　　温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采</P>
<>用如下所示的降温方式： </P>
. G- W- ]+ `5 e, o+ T2 _0 A<>T(t+1)＝k×T(t)
% I5 h) R7 h5 `! Y" ?7 P) M式中k为正的略小于1.00的常数，t为降温的次数 </P>
& {9 Z' m% x: _; r3 h  P$ h; d<>使用SA解决TSP问题的Matlab程序：</P>
<DIV class=HtmlCode>
4 _* o' t- c: p! m% k% \1 g/ b" A<>function out = tsp(loc)
/ h2 x! x* a$ I% {: e' l" x# p% TSP Traveling salesman problem (TSP) using SA (simulated annealing).
! R: U, E0 n4 P$ C" r5 g% TSP by itself will generate 20 cities within a unit cube and
0 G+ c. D& E$ w! p; n/ p9 ^7 a% then use SA to slove this problem.
%
$ q! C6 c: ]" r3 J; B- \% TSP(LOC) solve the traveling salesman problem with cities'
% coordinates given by LOC, which is an M by 2 matrix and M is
% the number of cities.
%
% For example:
0 a% B; Y7 k$ @( I+ i%
% loc = rand(50, 2);
% tsp(loc);
+ x6 P5 F9 J+ d; B; K# Yif nargin == 0,
' `) y: A/ g. o- Y  i$ p6 U% E% The following data is from the post by Jennifer Myers (<a href="mailtjmyers@nwu" target="_blank" >jmyers@nwu</A>.
edu)
4 G' p9 K0 B. b* G' q' zedu)
% to comp.ai.neural-nets. It's obtained from the figure in
% Hopfield &amp; Tank's 1985 paper in Biological Cybernetics
% (Vol 52, pp. 141-152).
loc = [0.3663, 0.9076; 0.7459, 0.8713; 0.4521, 0.8465;
; W! ~( _; E$ s. W) N0.7624, 0.7459; 0.7096, 0.7228; 0.0710, 0.7426;
+ E6 `* J- g) b1 U6 y: K0.4224, 0.7129; 0.5908, 0.6931; 0.3201, 0.6403;
, i4 B/ M9 r( V8 `8 o4 E8 v0.5974, 0.6436; 0.3630, 0.5908; 0.6700, 0.5908;
0.6172, 0.5495; 0.6667, 0.5446; 0.1980, 0.4686;
9 n+ v9 U- i7 x7 @( B! f7 {- J" p0.3498, 0.4488; 0.2673, 0.4274; 0.9439, 0.4208;
0.8218, 0.3795; 0.3729, 0.2690; 0.6073, 0.2640;
- m0 b8 Q& h. f! d3 i2 w9 f0.4158, 0.2475; 0.5990, 0.2261; 0.3927, 0.1947;
% w1 }& i! A3 u. F7 q. s% Z0.5347, 0.1898; 0.3960, 0.1320; 0.6287, 0.0842;
0.5000, 0.0396; 0.9802, 0.0182; 0.6832, 0.8515];
end
NumCity = length(loc); % Number of cities
& V5 g. ?$ p- p( U5 ?/ odistance = zeros(NumCity); % Initialize a distance matrix
# Z) J# L7 v9 c  |& C% Fill the distance matrix
4 F0 u4 l0 m% @+ i$ ~for i = 1:NumCity,
2 o! r" T: Z. t1 ?1 jfor j = 1:NumCity,
distance(i, j) = norm(loc(i, - loc(j, );
' F* c$ x! {$ E& E, z8 w3 E  m6 c2 gdistance(i, j) = norm(loc(i, - loc(j, );
end
1 O2 R# y5 z& w5 s/ \: kend
% To generate energy (objective function) from path
%path = randperm(NumCity);
$ e7 }' ]8 ~3 }1 a, j) g" f9 |4 p%energy = sum(distance((path-1)*NumCity + [path(2:NumCity) path(1)]));
$ C5 v% O; _9 B8 {' Z% @% Find typical values of dE
count = 20;
all_dE = zeros(count, 1);
* j& F# |& h" f) G/ c% Vfor i = 1:count
$ V: U" L. U8 n+ H+ ?4 epath = randperm(NumCity);
energy = sum(distance((path-1)*NumCity + [path(2:NumCity)
path(1)]));
new_path = path;
index = round(rand(2,1)*NumCity+.5);
: M2 E$ `# `1 S* einversion_index = (min(index):max(index));
new_path(inversion_index) = fliplr(path(inversion_index));
( Q' c' e8 ~& U! I/ r/ Xall_dE(i) = abs(energy - ...
9 b) V4 o. H( Q+ _sum(sum(diff(loc([new_path new_path(1)],)'.^2)));
end
dE = max(all_dE);
, T  n9 x! P- p1 C5 V+ h* O! adE = max(all_dE);
temp = 10*dE; % Choose the temperature to be large enough
/ k, N8 u4 u$ e3 X; i* Z, b4 A& ]fprintf('Initial energy = %f\n\n',energy);
8 H) J3 t- `" R* S0 i1 p% Initial plots
out = [path path(1)];
3 y8 q. y  R2 G- X$ g, `plot(loc(out(, 1), loc(out(, 2),'r.', 'Markersize', 20);
axis square; hold on
  Y5 P( F- S% R( mh = plot(loc(out(, 1), loc(out(, 2)); hold off
MaxTrialN = NumCity*100; % Max. # of trials at a
temperature
MaxAcceptN = NumCity*10; % Max. # of acceptances at a
3 ?7 H% S! |7 @0 b; btemperature
StopTolerance = 0.005; % Stopping tolerance
4 r+ y8 U6 Q! ~; ETempRatio = 0.5; % Temperature decrease ratio
minE = inf; % Initial value for min. energy
- d: B5 j7 m- i; CmaxE = -1; % Initial value for max. energy
8 c: @1 Z: E8 s) s/ W1 }  V7 x, x% Major annealing loop
2 b; Y" ?) u& \: Xwhile (maxE - minE)/maxE &gt; StopTolerance,
minE = inf;
minE = inf;
9 ~7 [: T# h+ YmaxE = 0;
TrialN = 0; % Number of trial moves
% c, N7 a& h; a/ D2 L) mAcceptN = 0; % Number of actual moves
5 M8 Y3 m  o: c" _while TrialN &lt; MaxTrialN &amp; AcceptN &lt; MaxAcceptN,
+ f: I; {7 I9 S3 ?7 K- ~$ {1 m5 q3 M/ enew_path = path;
# f  T. U0 C. c! I* e1 I* n* bindex = round(rand(2,1)*NumCity+.5);
8 T* t1 v% r1 Z  J0 e: q5 v/ \+ j0 `( Ainversion_index = (min(index):max(index));
1 B: `7 p( {: K3 z2 u. P5 H- Onew_path(inversion_index) =
fliplr(path(inversion_index));
1 i4 ^, i* J5 O0 w# rnew_energy = sum(distance( ...
(new_path-1)*NumCity+[new_path(2:NumCity)
new_path(1)]));
% p' m- T& V8 A6 k2 B% sif rand &lt; exp((energy - new_energy)/temp), %
- `, S: O" s- O4 |accept
it!
- V% I0 P8 Y- N( Eenergy = new_energy;
( A& k' e% N0 C6 k( v6 npath = new_path;
) @; _( K. E% K) o8 l) O, }minE = min(minE, energy);
maxE = max(maxE, energy);
3 ^- X/ v! b# [AcceptN = AcceptN + 1;
end
TrialN = TrialN + 1;
; x2 _0 g* `* {$ pend
2 V& X; [' ~4 }! q  U4 \' eend
8 T* Y, {) G3 y2 y* F" y. H0 w% Update plot
- I; v# r4 i* s  H: t3 [9 Gout = [path path(1)];
7 ^( V% D8 m0 d/ W" {7 f8 lset(h, 'xdata', loc(out(, 1), 'ydata', loc(out(, 2));
drawnow;
% Print information in command window
4 i1 I( w5 ], a8 T2 |& |- bfprintf('temp. = %f\n', temp);
tmp = sprintf('%d ',path);
fprintf('path = %s\n', tmp);
fprintf('energy = %f\n', energy);
" C( o7 q8 m) a7 K2 S( r; cfprintf('[minE maxE] = [%f %f]\n', minE, maxE);
% S9 Q; o- _. F! y2 r# I& Efprintf('[AcceptN TrialN] = [%d %d]\n\n', AcceptN, TrialN);
9 I4 @+ Z) v$ F( M; h" A/ w% Lower the temperature
temp = temp*TempRatio;
end
% Print sequential numbers in the graphic window
- N' u2 \8 t) q# e9 C# ~7 ofor i = 1:NumCity,
$ n* j7 O( W* d. ^7 Qtext(loc(path(i),1)+0.01, loc(path(i),2)+0.01, int2str(i), ...
'fontsize', 8);
1 T5 x; {! \5 vend </P></DIV>
<P>又一个相关的Matlab程序</P>
<DIV class=HtmlCode>
<P>function[X,P]=zkp(w,c,M,t0,tf)
) Q5 A3 U6 u% Q[m,n]=size(w);
& m  {0 C$ y+ w8 l5 I9 vL=100*n;
t=t0;
clear m;
: t$ o/ f3 v6 U: ~0 I, w6 E  ux=zeros(1,n)
, ]' x8 y9 z% bxmax=x;
fmax=0;
while t&gt;tf
for k=1
0 D. M1 a: Q  y4 z/ [xr=change(x)
3 d& v: E% ^0 V3 m& Ugx=g_0_1(w,x);
  Q, l' X& y9 D( Q/ egxr=g_0_1(w,xr);
, Y# E' u* F" nif gxr&lt;=M
( W  b4 `) v- Y+ U) u/ I8 ~fr=f_0_1(xr,c);
f=f_0_1(x,c);
& }, K5 R: W$ R2 Q3 R/ G4 tdf=fr-f;
if df&gt;0
  c) w: I% l2 wx=xr;
if fr&gt;fmax
fmax=fr;
+ G% W# e6 R6 x& Bxmax=xr;
2 M; b( ?' w, ]& ^  p& Xend
9 T! u6 r* j+ Z" c, M) @/ aelse
p=rand;
if p&lt;exp(df/t)
x=xr;
end
/ k3 Y4 R6 d8 \+ K; Q6 X4 w& q4 i  dend
end
. T4 ?- Y9 |1 L8 ]# nend
( U( T* K: Z6 _" E& d) H' lt=0.87*t
0 r1 }4 _( C3 Z  ~end
P=fmax;
X=xmax;
%下面的函数产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
7 |6 m( S3 }2 N" P, n& Gclear m;
u=rand;
0 C4 ~* L5 Y! E0 m5 [9 J2 hu=u*(n-2);
u=round(u);
if u&lt;2
# ?: s) e! f) [. z2 s7 Au=2;
end
if u&gt;n-2
2 r! g' ~( h5 a$ ^: t. Su=n-2;
8 ^7 H7 \; d# M' T+ [1 Eend
v=rand;
v=v*(n-u+1);
- ?- O( I) R0 X  F& y* ]& nv=round(v);
& T$ D4 x1 e9 l3 m! qif v&lt;1
v=1;
end
v=v+u;
if v&gt;n
3 m+ l: P9 O/ l4 I# `" X3 C  q( O2 Fv=n;
+ f4 J9 w( M$ Z* ]. h+ b6 ?( Q9 hend
7 T! j9 k9 W( X( z, bpi_1(u)=pi0(v);
6 u9 T' g  O! L& k  X2 M- Mpi_1(u)=pi0(u);
$ U7 Z1 b1 F$ |4 p6 p# @9 `+ hif u&gt;1
for k=1u-1)
pi_1(k)=pi0(k);
end
( S8 q! V) K. |& _( C# F" P) ^! Vend
/ E7 I) r9 I: K$ I& L/ p8 Oif v&gt;(u+1)
( n5 m( [2 Z4 ?5 e0 mfor k=1v-u-1)
0 K" m! K! C, a; E, P  r$ Rpi_1(u+k)=pi0(v-k);
end
* M+ q6 b* B0 A( v) |% f( q8 Kend
* P" d; i6 Z; N2 j/ G2 M- ]+ Cif v&lt;n
: F& O9 F& q' e1 Wfor k=(v+1):n
pi_1(k)=pi0(k);
end
end
4 S5 A. \, v1 h; ~4 Jd_f=0;
if v&lt;n
& T1 J! X* b8 M  d. z: U6 P) B2 n5 Ad_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
1 J7 A2 _# I. l) a5 b, H8 H7 Vfor k=(u+1):n
' X! @0 M% A: hd_f=d_f+d(pi0(k),pi0(k-1))-d(pi0(v),pi0(v+1));
5 T: V" [6 P+ B1 |+ Aend
7 T* h% ]$ T9 k. `5 Pd_f=d_f-d(pi0(u-1),pi0(u));
for k=(u+1):n
6 z, k9 @, O( O" Ad_f=d_f-d(pi0(k-1),pi0(k));
end
1 x, m& v  X; M) h  y) d5 xelse
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
for k=(u+1):n
$ U5 t: i  L; ]5 t7 E3 T+ xd_f=d_f-d(pi0(k),pi0(k-1));
' ^0 l1 ?' {+ I8 J; t5 o4 Wend
3 T% s/ [' O0 Y3 Z6 ^0 ]: ffor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
! O' ^: Z7 c# {end
end
pi_r=pi_1; </P></DIV>

ilikenba

<>遗传算法：</P>
$ H5 ]+ F' }. _: X<>旅行商问题(traveling saleman problem,简称tsp)：
已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？
, j  J$ d5 C9 {7 M/ ?用图论的术语来说，假设有一个图 g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。
这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商问题(dij≠dji,,任意i,j=1,2,3，…,n)。
4 T! N5 z1 Z/ \7 c若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中ti∈v(i=1,2,3,…,n)，且记tn+1= t1，则旅行商问题的数学模型为：
* y; |7 Z' J  B8 f: ?6 emin l=σd(t(i),t(i+1)) （i=1,…,n）
: i0 e  r( c$ G0 V$ n1 r3 ]6 ~旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。
遗传算法：
初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。
适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)).
评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=alpha*(1-alpha).^(i-1) 。[随机规划与模糊规划]
选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。
step1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1,…pop-size.
step2、从区间(0,pop-size)中产生一个随机数r；
: \$ V0 Z% K) ~& X8 wstep3、若qi-1&lt;r&lt;qi,则选择第i个染色体 ；
3 O' a* ?7 ?0 \9 p) @step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。
4 p- y, i3 h1 V4 S$ Z' _% mgrefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如：
8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1
对应：
& D3 G* x% o* |7 t8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。
6 [. z. ]8 {1 p: w8 G交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从 到pop-size重复以下过程：从[0，1]中产生一个随机数r，如果r&lt;pc ，则选择vi作为一个父代。
4 }3 ?3 l# ?+ m& {5 f$ ]8 A# G将所选的父代两两组队，随机产生一个位置进行交叉，如：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
5 L; k. x' o0 s6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1
交叉后为：
8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1
6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1
5 k2 I+ ?1 h6 J8 w  I) }3 y变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r&lt;pm 的标准下选择多个染色体vi作为父代。对每一个选择的父代，随机选择多个位置，使其在每位置按均匀变异（该变异点xk的取值范围为[ukmin,ukmax],产生一个[0，1]中随机数r，该点变异为x'k=ukmin+r(ukmax-ukmin)）操作。如：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
3 n, a1 ?8 {1 F5 h0 h变异后：
; C# ?# l3 S3 [6 I) |/ C# l8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1
  o$ d$ F6 z6 {( l, Y2 H. y反grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。
循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传操作，跳出。</P>
9 j9 m5 g% j, v# L<>Matlab程序：</P>
: E' y9 g  \5 ^+ U+ z$ Q<DIV class=HtmlCode>
<>function [bestpop,trace]=ga(d,termops,num,pc,cxops,pm,alpha)
%
) z. f3 m7 d; X%————————————————————————
%[bestpop,trace]=ga(d,termops,num,pc,cxops,pm,alpha)
%d:距离矩阵
$ C. C2 {) u6 D2 d9 S%termops:种群代数
; o8 [( }8 \% {%num:每代染色体的个数
0 L  W: b* w$ _9 V: m- [%pc:交叉概率
/ t# o9 `" g. l2 H" _; e%cxops:由于本程序采用单点交叉，交叉点的设置在本程序中没有很好的解决，所以本文了采用定点，即第cxops，可以随机产生。
%pm:变异概率
%alpha:评价函数eval(vi)=alpha*(1-alpha).^(i-1).
%bestpop:返回的最优种群
, F0 S7 V! x2 A& N: c. @%trace:进化轨迹
2 V% w* v' @  c( _- i%------------------------------------------------
%####@@@##版权所有！欢迎广大网友改正，改进！##@@@####
%e-mail:tobysidney33@sohu.com
1 H* d( J+ k2 Q3 X%####################################################
%
& a! [$ g& P  G9 @citynum=size(d,2);
n=nargin;
if n&lt;2
disp('缺少变量！！')
7 R* `1 x' N$ u$ I% vdisp('^_^开个玩笑^_^')
# {6 V9 u$ p) R5 {8 Q; l" hend
4 T% F- \+ [( K* x3 ]$ F3 Z, i+ Iif n&lt;2
  I8 X+ h9 w& vtermops=500;
6 B" x: v# L. T* d! Anum=50;
% J, F. l. H, z& V  G) \% U: }pc=0.25;
cxops=3;
, h7 F7 ~) [$ \& U. Npm=0.30;
alpha=0.10;
end
. S1 I- X; V! }" Wif n&lt;3
) g! X* c- c- Snum=50;
pc=0.25;
) r* o/ ~2 J' K* Y/ x- J4 jcxops=3;
pm=0.30;
, a, D& x9 I5 D4 M9 @3 K! \alpha=0.10;
end
if n&lt;4
! D6 v9 D4 s( _7 [pc=0.25;
cxops=3;
, B8 O! _) y( y6 K# apm=0.30;
2 Q& o% P7 X- v4 X! l6 I6 Aalpha=0.10;
end
5 ~- }  {% A' s. mif n&lt;5
cxops=3;
/ ?+ T4 V4 C2 Z- cpm=0.30;
' w" H7 o5 {  |+ Y0 zalpha=0.10;
end
if n&lt;6
. B! Q$ N* `1 ]pm=0.30;
alpha=0.10;
end
2 o+ e  C# a) ?* P. s+ t4 |if n&lt;7
alpha=0.10;
" |! ^9 N/ t$ D4 I+ z/ Wend
if isempty(cxops)
cxops=3;
( d$ y/ _5 I3 H- o# _! B# V6 v' F0 u4 vend</P>
<>[t]=initializega(num,citynum);
for i=1:termops
[l]=f(d,t);
[x,y]=find(l==max(l));
0 p) \4 L5 L( {/ Btrace(i)=-l(y(1));
bestpop=t(y(1),;
[t]=select(t,l,alpha);
[g]=grefenstette(t);
# ^# u0 n' I3 p1 o" m$ _[g1]=crossover(g,pc,cxops);
. I: ~, J; j  Y& b$ ]& |8 L" c# O[g]=mutation(g1,pm); %均匀变异
[t]=congrefenstette(g);
end</P>
<>---------------------------------------------------------
3 I0 ?  I2 c4 c. }7 X8 tfunction [t]=initializega(num,citynum)
for i=1:num
( }" T1 \/ q' @2 \t(i,=randperm(citynum);
end
& E/ j& E7 b5 D/ T. V% S6 o-----------------------------------------------------------
function [l]=f(d,t)
[m,n]=size(t);
* F  f+ ]8 O  a8 j# u! Dfor k=1:m
for i=1:n-1
- ~7 D! U6 b0 k  h0 cl(k,i)=d(t(k,i),t(k,i+1));
end
* ~; M- g9 [1 ]l(k,n)=d(t(k,n),t(k,1));
l(k)=-sum(l(k,);
end
-----------------------------------------------------------
% ?$ H5 V* p$ G- I4 X$ @! O, Sfunction [t]=select(t,l,alpha)
[m,n]=size(l);
2 y, C" S1 [1 ft1=t;
[beforesort,aftersort1]=sort(l,2);%fsort from l to u
* z* ~6 U# w) o# }) Zfor i=1:n
aftersort(i)=aftersort1(n+1-i); %change
end
for k=1:n;
t(k,=t1(aftersort(k),;
) b/ D, l: r. a" _7 n! gl1(k)=l(aftersort(k));
- K1 A' @6 }, j% V+ ~) }% uend
: \/ [9 ~8 H3 Ft1=t;
l=l1;
for i=1:size(aftersort,2)
evalv(i)=alpha*(1-alpha).^(i-1);
+ c8 }# {1 X7 j. C+ {+ Dend
+ ]$ w2 J6 N3 m2 [5 |m=size(t,1);
" b6 t7 x0 Z& Y6 }) pq=cumsum(evalv);
+ u- L: Q6 e: Z5 o- }8 Bqmax=max(q);
for k=1:m
r=qmax*rand(1);
for j=1:m
if j==1&amp;r&lt;=q(1)
' A1 Q6 U* U# G  |t(k,=t1(1,;
elseif j~=1&amp;r&gt;q(j-1)&amp;r&lt;=q(j)
t(k,=t1(j,;
) M  X; h- f7 }* L2 k6 P6 ^end
end
4 b) A! N+ _8 G3 z, o% \# g/ yend
( P& u) O2 D/ b) Q--------------------------------------------------
function [g]=grefenstette(t)
& k. ]) \8 v5 K' z: ~[m,n]=size(t);
for k=1:m
t0=1:n;
8 j: E8 u3 Y4 Y% S. `for i=1:n
for j=1:length(t0)
/ L: A; P4 P* A$ @- e1 Q: Mif t(k,i)==t0(j)
8 v8 r9 l' h0 f' X* D# Og(k,i)=j;
t0(j)=[];
' Z$ g* b: k# h! dbreak
+ o4 s$ H) R9 o* I, a; o" dend
end
. b+ `5 A- r9 Kend
2 b$ @& R" M9 Lend
-------------------------------------------
function [g]=crossover(g,pc,cxops)
, F$ R5 [9 X$ A: l- R[m,n]=size(g);
ran=rand(1,m);
( g* X! m9 J! T3 Ur=cxops;
5 M6 ?5 o" {1 Q0 ], ~[x,ru]=find(ran&lt;pc);
if ru&gt;=2
for k=1:2:length(ru)-1
  D9 f) h7 L. _1 f% Kg1(ru(k),=[g(ru(k),[1:r]),g(ru(k+1),[(r+1):n])];
8 V. t: b! I$ Jg(ru(k+1),=[g(ru(k+1),[1:r]),g(ru(k),[(r+1):n])];
g(ru(k),=g1(ru(k),;
end
end
$ M0 t% l" D, m1 w; o4 U--------------------------------------------
function [g]=mutation(g,pm) %均匀变异
& J3 H# n3 r% t! ^: |: X[m,n]=size(g);
ran=rand(1,m);
+ @, q9 B- N; s3 G1 G7 y. t% W4 \- hr=rand(1,3); %dai gai jin
rr=floor(n*rand(1,3)+1);
, v; E& m! g' p% g% O[x,mu]=find(ran&lt;pm);
for k=1:length(mu)
for i=1:length(r)
; q, S0 {& x* @0 G2 @! U: bumax(i)=n+1-rr(i);
0 k& K) S* v9 B2 b+ a1 C$ S+ U8 Rumin(i)=1;
g(mu(k),rr(i))=umin(i)+floor((umax(i)-umin(i))*r(i));
end
; e" x/ z# p5 W& W  ^: G$ |! g& Nend
---------------------------------------------------
function [t]=congrefenstette(g)
[m,n]=size(g);
for k=1:m
t0=1:n;
2 w& h( E: `8 U" C- x# cfor i=1:n
t(k,i)=t0(g(k,i));
$ L; K  g( ]% f/ I( ^8 bt0(g(k,i))=[];
end
, [- B6 }: y3 s/ ~/ q! r& T/ gend
------------------------------------------------- </P></DIV>
; o: D/ K: s& ?<>又一个Matlab程序，其中交叉算法采用的是由Goldberg和Lingle于1985年提出的PMX(部分匹配交叉)，淘汰保护指数alpha是我自己设计的，起到了加速优胜劣汰的作用。</P>
9 d0 {& _3 I, w<DIV class=HtmlCode>
% P5 _9 U4 c, u; ?6 n, T  l<>%TSP问题（又名：旅行商问题，货郎担问题）遗传算法通用matlab程序
%D是距离矩阵，n为种群个数,建议取为城市个数的1~2倍，
%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定
%m为适应值归一化淘汰加速指数 ,最好取为1,2,3,4 ,不宜太大
; P) B/ f' [4 n8 {$ W%alpha为淘汰保护指数,可取为0~1之间任意小数,取1时关闭保护功能,最好取为0.8~1.0
, S" e( f- x' R( ?2 Y) J%R为最短路径,Rlength为路径长度
% L' \% F' R* m) Z5 V" _) h* x/ [function [R,Rlength]=geneticTSP(D,n,C,m,alpha)</P>
<>[N,NN]=size(D);
& n& s: C& q2 O1 pfarm=zeros(n,N);%用于存储种群
for i=1:n
farm(i,=randperm(N);%随机生成初始种群
end
R=farm(1,;%存储最优种群
len=zeros(n,1);%存储路径长度
& k$ V0 \8 m* I0 F* P9 b* Afitness=zeros(n,1);%存储归一化适应值
counter=0;</P>
<>while counter&lt;C</P>
' y' k9 |# Y8 L* @$ B<>for i=1:n
3 t* e2 T" l/ D3 flen(i,1)=myLength(D,farm(i,);%计算路径长度
/ t9 K0 Z# V# x$ d0 ~- R8 Mend
maxlen=max(len);
minlen=min(len);
) @/ S9 n* |7 B( {, f- dfitness=fit(len,m,maxlen,minlen);%计算归一化适应值
rr=find(len==minlen);
& v* B4 i' C4 I9 U! ^3 zR=farm(rr(1,1),;%更新最短路径</P>
* a* u* [$ g) B<>FARM=farm;%优胜劣汰，nn记录了复制的个数
* z. g# T& ?$ z# z* ^- g" _, F4 d3 rnn=0;
3 \4 E" ~6 D# Q& j6 a6 g' h# [& `for i=1:n
if fitness(i,1)&gt;=alpha*rand
/ K5 m: x# d: T0 H2 G9 F' f% }; o/ Rnn=nn+1;
* B0 R0 F5 |. P- NFARM(nn,=farm(i,;
end
end
3 g6 v& O  X4 e# J4 G6 E5 k  l3 m6 nFARM=FARM(1:nn,;</P>
& o* a/ M4 @$ j3 w<>[aa,bb]=size(FARM);%交叉和变异
: q/ L8 q( J3 u- M- h7 e: y6 Lwhile aa&lt;n
1 Y* B- ~. C  J$ ?4 G: ?if nn&lt;=2
nnper=randperm(2);
* k) v* N/ W# V) q! J! telse
nnper=randperm(nn);
end
: Z2 a  f0 B( hA=FARM(nnper(1),;
7 M4 W1 F/ \  v2 h. @) M) G+ {B=FARM(nnper(2),;
* }* q) z# y1 P$ H' c  ^[A,B]=intercross(A,B);
FARM=[FARM;A;B];
% H7 t0 l5 V1 a0 \[aa,bb]=size(FARM);
end
* G3 u# K( w# }" |$ w! t+ Nif aa&gt;n
- X/ E5 t9 |" }2 S: b: Q$ wFARM=FARM(1:n,;%保持种群规模为n
end</P>
" m7 ^+ f. ~( u/ r  U$ k0 i<>farm=FARM;
clear FARM
counter=counter+1</P>
/ }+ R, @; o& {" |<>end</P>
<>Rlength=myLength(D,R);</P>
<>function [a,b]=intercross(a,b)
L=length(a);
if L&lt;=10%确定交叉宽度
1 j% j; J5 E+ y& P/ f6 [W=1;
elseif ((L/10)-floor(L/10))&gt;=rand&amp;&amp;L&gt;10
) c& V7 I  K) s  d. JW=ceil(L/10);
' G. N  E' _9 Pelse
( Z6 m2 Q& p7 \( ~# {- u+ SW=floor(L/10);
4 a; `+ d6 x8 d! D1 Dend
: _3 f2 M) w2 Z3 R& Y7 ]p=unidrnd(L-W+1);%随机选择交叉范围，从p到p+W
  K3 G& m; ^5 y1 T, lfor i=1:W%交叉
% ?. G, n0 {+ Z6 r0 Y) b! B* x5 wx=find(a==b(1,p+i-1));
! e6 A2 t6 g/ @' n, R- ~9 yy=find(b==a(1,p+i-1));
+ @( j( U/ A4 D[a(1,p+i-1),b(1,p+i-1)]=exchange(a(1,p+i-1),b(1,p+i-1));
[a(1,x),b(1,y)]=exchange(a(1,x),b(1,y));
6 l& c% Y) ]9 K; [0 w! F0 Z0 Aend
function [x,y]=exchange(x,y)
temp=x;
8 V7 B# }; N; ~& s  [" G+ ]4 ~" i( Kx=y;
- U- U8 L; K0 V& jy=temp;</P>
<>% 计算路径的子程序
) u" F; d$ L7 B  vfunction len=myLength(D,p)
[N,NN]=size(D);
- Z6 g- U' s( G) s" x! Plen=D(p(1,N),p(1,1));
7 N0 X5 r( B% ?for i=1N-1)
len=len+D(p(1,i),p(1,i+1));
end</P>
<>%计算归一化适应值子程序
$ ~) D3 S+ \' W7 W* c  N8 ^function fitness=fit(len,m,maxlen,minlen)
fitness=len;
for i=1:length(len)
fitness(i,1)=(1-((len(i,1)-minlen)/(maxlen-minlen+0.000001))).^m;
& o. l0 z, ^$ Fend </P></DIV>
4 Y* E. k* A; g1 k6 ?<>一个C++的程序：</P>
8 U7 }. W$ y' j5 x* h<DIV class=HtmlCode>
5 ^/ g8 i# \- W<>//c++的程序
#include&lt;iostream.h&gt;
5 k1 L. t1 J& J( B$ j#include&lt;stdlib.h&gt;
template&lt;class T&gt;
class Graph
. E( V& x- y4 x5 S3 f5 o8 m- f{
* J# z7 N  n( n! `. O  B" _  public:
    Graph(int vertices=10)
    {
: I3 @! b7 Q7 g' H) i+ X      n=vertices;
. b8 N3 O; o4 ]6 G9 h% U  p      e=0;
8 V- H' ~9 d1 x! T    }
% c6 h6 p, n& f6 U    ~Graph(){}
    virtual bool Add(int u,int v,const T&amp; w)=0;
    virtual bool Delete(int u,int v)=0;
    virtual bool Exist(int u,int v)const=0;
5 [( v" @% ?1 _% A    int Vertices()const{return n;}
: D" ]/ l0 Q) e( u; a    int Edges()const{return e;}
  protected:
    int n;
1 |5 v+ R, Z8 X2 A, O2 ^    int e;
};
template&lt;class T&gt;
class MGraph:public Graph&lt;T&gt;
{
  public:
, Z8 B% f5 V1 O) `& x+ V) |    MGraph(int Vertices=10,T noEdge=0);
# C" [" G0 E9 L    ~MGraph();
    bool Add(int u,int v,const T&amp; w);
7 `1 B' W4 Q" y  b    bool Delete(int u,int v);
. F: U# I" A8 G# F/ i- c    bool Exist(int u,int v)const;
    void Floyd(T**&amp; d,int**&amp; path);
    void print(int Vertices);
+ a) i+ g5 y6 f  S- g2 g  private:
    T NoEdge;
) I9 N7 e! Q5 i$ [8 T! F    T** a;
};
1 Q' R8 I& d% q( ^! btemplate&lt;class T&gt;
$ s, ]5 Q$ o" f$ b- YMGraph&lt;T&gt;::MGraph(int Vertices,T noEdge)
: r6 B  u) b$ J( ?; X- ]5 r7 t{
  n=Vertices;
! r; s8 D2 o( M+ `) n' u) U  NoEdge=noEdge;
  a=new T* [n];
# z" U# m- b+ @) n/ v0 Z  for(int i=0;i&lt;n;i++){
$ w" d4 B" v- Y! h7 a  T8 |2 A: w+ X    a=new T[n];
    a=0;
' z$ J$ K, ?1 I# _' Z    for(int j=0;j&lt;n;j++)if(i!=j)a[j]=NoEdge;
+ g! _; g+ J7 M/ X- Y/ `9 S: s  }
8 s- `) R3 ]# e7 y: n& u}
$ n2 \* ~& u0 J3 D+ [/ rtemplate&lt;class T&gt;
MGraph&lt;T&gt;::~MGraph()
{
- J1 h& x+ r: e  for(int i=0;i&lt;n;i++)delete[]a;
  delete[]a;
}
: X2 X& y' b! A  D0 m0 H  V  ttemplate&lt;class T&gt;
5 D+ V/ h1 V. Nbool MGraph&lt;T&gt;::Exist(int u,int v)const
" \% v8 l; n% ^1 l, o{
: p* b. D1 J. l  if(u&lt;0||v&lt;0||u&gt;n-1||v&gt;n-1||u==v||a[v]==NoEdge)return false;
  return true;
}
; q7 s0 v3 L7 E/ A0 s5 \" ktemplate&lt;class T&gt;
: G% J" Q5 n6 Z, j- U3 Fbool MGraph&lt;T&gt;::Add(int u,int v,const T&amp; w)
  K: V- S- ~. p0 ?% k) B{
  if(u&lt;0||v&lt;0||u&gt;n-1||v&gt;n-1||u==v||a[v]!=NoEdge){
2 [$ @" o7 B: v$ h    cerr&lt;&lt;"BadInput!"&lt;&lt;endl;
    return false;
- ]# L8 K7 C. @! J  }
' ~. G# {7 d0 P$ A. q  E( Q( e$ P  a[v]=w;
6 o$ n% }% Z- |: h8 i* u: G  e++;
4 [% X3 C# _7 R+ c! _  \" \* c: \5 z  return true;
/ v. e( e- y1 Q$ G7 ~  ~; C9 ^' s# l}
template&lt;class T&gt;
bool MGraph&lt;T&gt;:delete(int u,int v)
1 v! z! b7 W$ z. F5 \4 E{
8 F9 a! p" }2 z2 u; a1 X  if(u&lt;0||v&lt;0||u&gt;n-1||v&gt;n-1||u==v||a[v]==NoEdge){
    cerr&lt;&lt;"BadInput!"&lt;&lt;endl;
4 a$ f4 |) ?8 R$ j6 x    return false;
  }
  a[v]=NoEdge;
  e--;
  return true;
}
template&lt;class T&gt;
void MGraph&lt;T&gt;::Floyd(T**&amp; d,int**&amp; path)
, J% z/ X4 _9 N& w; h" u7 M) h9 ]{
, V4 A9 B  J. O3 T% S  d=new T* [n];
. r; ~+ i7 @. Y# a; `  path=new int* [n];
  for(int i=0;i&lt;n;i++){
' I9 B6 B% P& ~5 ~) d% W/ [    d=new T[n];
  z, ]) J1 n- A+ f! \6 D$ T4 ?8 e    path=new int[n];
7 ~9 r# g# m& `: w6 T    for(int j=0;j&lt;n;j++){
      d[j]=a[j];
      if(i!=j&amp;&amp;a[j]&lt;NoEdge)path[j]=i;
& T7 r) l- E3 |      else path[j]=-1;
- @# a& e( I: X6 z* f* Z    }
  }
  for(int k=0;k&lt;n;k++){
4 N& i9 j7 _; ]# W5 Y% f% y' F" Y    for(i=0;i&lt;n;i++)
      for(int j=0;j&lt;n;j++)
: C+ F! {& s7 T1 F6 m        if(d[k]+d[k][j]&lt;d[j]){
          d[j]=d[k]+d[k][j];
          path[j]=path[k][j];
        }
        }
}
template&lt;class T&gt;
7 R* K) ~# F7 s+ E2 S$ @, {) B5 jvoid MGraph&lt;T&gt;::print(int Vertices)
{
) L+ L3 f1 Z' ^* Y" D  for(int i=0;i&lt;Vertices;i++)
) B9 L5 s# @# X$ p4 T    for(int j=0;j&lt;Vertices;j++)
( N% e8 c" f/ I    {
0 x2 M% P3 z* `0 i- X" i/ L1 N% @      
      cout&lt;&lt;a[j]&lt;&lt;' ';if(j==Vertices-1)cout&lt;&lt;endl;
7 Z9 N" s( s1 O1 y8 Y# [    }
}
#define noEdge 10000
#include&lt;iostream.h&gt;
void main()
3 P  c% P6 P$ `. [{
  cout&lt;&lt;"请输入该图的节点数："&lt;&lt;endl;
, Y& X3 ?+ z, b0 Q; Z  int vertices;
  cin&gt;&gt;vertices;
  MGraph&lt;float&gt; b(vertices,noEdge);
0 b( a: [- }+ Z; Q1 j1 a7 G  cout&lt;&lt;"请输入u,v,w:"&lt;&lt;endl;
1 D: f  B5 u2 H5 R& m' k  int u,v;
  float w;
) |, u( Z2 Q0 ^- C3 \+ g  cin&gt;&gt;u&gt;&gt;v&gt;&gt;w;
  while(w!=noEdge){
: j+ ~; ?+ N2 Q    //u=u-1;
    b.Add(u-1,v-1,w);
    b.Add(v-1,u-1,w);
5 C& X) h, ~* G* R    cout&lt;&lt;"请输入u,v,w:"&lt;&lt;endl;
- _$ l7 M8 F$ X7 m    cin&gt;&gt;u&gt;&gt;v&gt;&gt;w;
, H! o" p9 s3 a  V( L, C  }
1 m+ @+ V3 B9 s2 ~  b.print(vertices);
' k% _6 J; J  b8 a. M2 `. S  int** Path;
5 w& v1 q# D3 s4 X0 @  int**&amp; path=Path;
; a* o0 U# _  {) T$ x  float** D;
  float**&amp; d=D;
4 K! u+ Q6 z0 @1 U2 M- C7 H  b.Floyd(d,path);
  for(int i=0;i&lt;vertices;i++){
    for(int j=0;j&lt;vertices;j++){
      cout&lt;&ltath[j]&lt;&lt;' ';
! f. ^# O, x7 U/ ^+ o- i      if(j==vertices-1)cout&lt;&lt;endl;
+ I; K4 o# t: e, G; K0 c4 {7 f    }
, n  Y0 j, e3 R0 T: `% w  }
( Y  C3 F  d0 q# e  int *V;
4 i4 ~3 ?  h9 ^$ r1 Q  V=new int[vertices+1];
9 S& z* g# \. i5 I+ T# E1 j  cout&lt;&lt;"请输入任意一个初始H-圈："&lt;&lt;endl;
  for(int n=0;n&lt;=vertices;n++){
   
    cin&gt;&gt;V[n];
  }
  for(n=0;n&lt;55;n++){
  b  m3 B+ s: [3 s5 q  l    for(i=0;i&lt;n-1;i++){
/ M" ^0 I- y7 C5 l    for(int j=0;j&lt;n-1;j++)
    {
3 z" B* ]3 L* ]8 }1 R      if(i+1&gt;0&amp;&amp;j&gt;i+1&amp;&amp;j&lt;n-1){
1 D: D0 o0 q0 \# g$ A        if(D[V][V[j]]+D[V[i+1]][V[j+1]]&lt;D[V][V[i+1]]+D[V[j]][V[j+1]]){
          int l;
          l=V[i+1];V[i+1]=V[j];V[j]=l;
$ D- m0 o; N3 l5 R+ L# O        }
( q& V# G, t$ G& i% g( `. s      }
    }
: B) q- a- T. L- y/ Z  }
  }
  float total=0;
* t, L, i7 d% M5 O  cout&lt;&lt;"最小回路："&lt;&lt;endl;
/ E6 F2 ^  J7 d  for(i=0;i&lt;=vertices;i++){
   
0 X# U+ e1 @3 u- W  U7 C    cout&lt;&lt;V+1&lt;&lt;' ';
  }
  cout&lt;&lt;endl;
  for(i=0;i&lt;vertices;i++)
  total+=D[V][V[i+1]];
1 ~1 \4 X* @2 P$ [" V& S  cout&lt;&lt;"最短路径长度："&lt;&lt;endl;
6 ]4 w& O# s3 k& y6 q, q: k! x  cout&lt;&lt;total;
8 S/ t7 P7 h8 h2 C5 E9 s} </P></DIV>
<>C语言程序：</P>
<DIV class=HtmlCode>
4 l9 _5 d4 e( |1 L6 V& n<>#include&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;
5 ^4 {. q$ O, K7 N: k#include&lt;math.h&gt;
/ t; [' p$ @" f. j0 c/ R#include&lt;alloc.h&gt;
8 R/ c  W8 ^; ~' w  k#include&lt;conio.h&gt;
' C1 J2 p% z5 R#include&lt;float.h&gt;
#include&lt;time.h&gt;
#include&lt;graphics.h&gt;
$ [( L+ v3 p/ M# S; k) F#include&lt;bios.h&gt;</P>
<>#define   maxpop  100
#define   maxstring  100</P>
<>
7 j: q* ~0 n) y3 r& a: T, M& vstruct  pp{unsigned char chrom[maxstring];
3 i* ?1 o) F- @2 J/ }9 n6 }8 f    float x,fitness;
% e5 j5 N% y2 s4 [  g7 X    unsigned int parent1,parent2,xsite;
. {) o" Q" z1 L9 x" P   };
struct pp *oldpop,*newpop,*p1;
( N6 O' S3 h8 x6 l6 j5 Q$ L6 F/ qunsigned int popsize,lchrom,gem,maxgen,co_min,jrand;
unsigned int nmutation,ncross,jcross,maxpp,minpp,maxxy;
' V5 u( e( x) X$ e$ p" Z) nfloat pcross,pmutation,sumfitness,avg,max,min,seed,maxold,oldrand[maxstring];
unsigned char x[maxstring],y[maxstring];
float *dd,ff,maxdd,refpd,fm[201];
FILE *fp,*fp1;
/ B. _7 H3 _4 `$ wfloat objfunc(float);
2 a1 O5 Q! j0 f* K& F3 B2 evoid statistics();
5 q" C, A/ l# O. F) ]int select();
int flip(float);
int crossover();
9 L$ H' L$ i% c/ I  D# Hvoid generation();
  I2 p# A1 F% O4 `void initialize();
5 y, m6 l" f1 O0 |: W+ fvoid report();
' Q% ~. D9 t# C2 m+ a% d' i  w& Jfloat decode();
void crtinit();
; M! D# N6 @1 G) lvoid inversion();
  ]  e5 I" U& E: K) Xfloat random1();
5 r  c8 q* E! }, ~/ |1 B% Xvoid randomize1();</P>
6 Y4 T! j( t4 ]; O; U* M& [<>main()
{unsigned int gen,k,j,tt;
3 V& C) x# c# }# {5 y$ nchar fname[10];
float ttt;
/ B5 J+ ^, R9 K# fclrscr();
6 ~" p  ?$ C/ R! |& Ico_min=0;
if((oldpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp)))==NULL)
     {printf("memory requst fail!\n");exit(0);}
if((dd=(float *)farmalloc(maxstring*maxstring*sizeof(float)))==NULL)
     {printf("memory requst fail!\n");exit(0);}
if((newpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp)))==NULL)
! t* P1 p2 `- Q' C3 D$ E     {printf("memory requst fail!\n");exit(0);}
5 Y7 L9 ]% r7 cif((p1=(struct pp *)farmalloc(sizeof(struct pp)))==NULL)
+ b! D. K6 F. m! z" o) P     {printf("memory requst fail!\n");exit(0);}
for(k=0;k&lt;maxpop;k++) oldpop[k].chrom[0]='\0';
$ O* ]: K- y2 o1 Y/ S: d0 rfor(k=0;k&lt;maxpop;k++) newpop[k].chrom[0]='\0';
printf("Enter Result Data Filename:");
! C& V3 {8 Y3 j8 lgets(fname);
if((fp=fopen(fname,"w+"))==NULL)
+ Q. O" }; y8 o+ f  {printf("cannot open file\n");exit(0);}</P>
" U; @# A( ^; d$ v; s<>
gen=0;
randomize();
, J$ B/ n% ]# `5 G( V: r5 ainitialize();</P>
. }# E8 g0 O2 f3 j$ K0 e<>fputs("this is result of the TSP problem:",fp);
) Y& _% |$ d  W! z* I1 Qfprintf(fp,"city: %2d psize: %3d Ref.TSP_path: %f\n",lchrom,popsize,refpd);
! S* J1 s! Z& d' K1 cfprintf(fp,"c: %f Pm: %f Seed: %f\n",pcross,pmutation,seed);
fprintf(fp,"X site:\n");
for(k=0;k&lt;lchrom;k++)
   {if((k%16)==0) fprintf(fp,"\n");
    fprintf(fp,"%5d",x[k]);
  W0 i+ L) L! ~" A   }
. w' p2 C; }! J' _fprintf(fp,"\n Y site:\n");
for(k=0;k&lt;lchrom;k++)
   {if((k%16)==0) fprintf(fp,"\n");
    fprintf(fp,"%5d",y[k]);
$ }' @$ ^- _; r+ A   }
fprintf(fp,"\n");</P>
1 n+ k( {: X- O9 a, L<P>
& U# b! M9 ~- I/ k3 g- Hcrtinit();
( x* l* B: B, W4 M' g4 g0 p+ y3 hstatistics(oldpop);
+ K, f* d) J" h4 z/ Breport(gen,oldpop);
0 x+ N; [% m  Z1 N/ w; m- I- ogetch();
maxold=min;
fm[0]=100.0*oldpop[maxpp].x/ff;
+ p; L* Z& E6 ]( Z, J8 n6 Mdo {
7 j8 \+ K. v4 I9 p    gen=gen+1;
  A7 K& s; V( `. H7 @6 L9 I    generation();
5 S3 j, O& {" u    statistics(oldpop);
# X' f. \( Z7 ]! Z    if(max&gt;maxold)
; s0 P, e( m/ K$ [4 L1 l( Z! ^       {maxold=max;
2 k$ j3 @2 b1 y1 g0 P/ q9 V- }- Uco_min=0;
! ]: i; s; o% T8 G       }
2 ^1 f" [5 T9 v" e/ |5 r    fm[gen%200]=100.0*oldpop[maxpp].x/ff;
1 Q. r; c: J+ U: g( ~& C7 w5 J    report(gen,oldpop);
    gotoxy(30,25);
: J4 {( [( A" b3 a    ttt=clock()/18.2;
    tt=ttt/60;
/ h- ]2 h4 g& `( I; x    printf("Run Clock: %2d: %2d: %4.2f",tt/60,tt%60,ttt-tt*60.0);
    printf("Min=%6.4f Nm:%d\n",min,co_min);
6 h  n) J0 C' z9 e2 R3 f5 ^2 k, l0 r   }while((gen&lt;100)&amp;&amp;!bioskey(1));
printf("\n gen= %d",gen);
. z+ t; T7 r5 \" }7 \; ]( i: ddo{
    gen=gen+1;
$ V& H0 ?& e; B    generation();
$ ?# w- Y7 W, Z6 \1 G    statistics(oldpop);
    if(max&gt;maxold)
5 x5 Q2 a' G& T       {maxold=max;
co_min=0;
* P+ U8 h& i0 z2 j8 U! X       }
6 @1 V$ O& c# ?3 T. B" L    fm[gen%200]=100.0*oldpop[maxpp].x/ff;
    report(gen,oldpop);
5 {, l4 i6 W3 v    if((gen%100)==0)report(gen,oldpop);
    gotoxy(30,25);
    ttt=clock()/18.2;
    tt=ttt/60;
    printf("Run Clock: %2d: %2d: %4.2f",tt/60,tt%60,ttt-tt*60.0);
    printf("Min=%6.4f Nm:%d\n",min,co_min);
   }while((gen&lt;maxgen)&amp;&amp;!bioskey(1));</P>
" `7 G% x6 Q- G4 M- d<P>getch();
# w$ ^/ A# S9 H$ Dfor(k=0;k&lt;lchrom;k++)
  {if((k%16)==0)fprintf(fp,"\n");
   fprintf(fp,"%5d",oldpop[maxpp].chrom[k]);
  }
: c) \$ A0 S( |. _# I! G/ f1 wfprintf(fp,"\n");</P>
/ O& o- H0 f( b4 t7 G% s' B<P>fclose(fp);
5 U0 P: K0 P, B2 ]0 {0 q1 Tfarfree(dd);
farfree(p1);
' c; F! v! }; l! [( {4 a) rfarfree(oldpop);
( o$ M- q; W# k1 i- y: C) X! Bfarfree(newpop);
restorecrtmode();
8 v* n6 s+ ~; oexit(0);
- c4 Z) t( c  L( K% c+ [, i- h}</P>
) ~( ~3 I1 X4 I! q$ j. q<P>/*%%%%%%%%%%%%%%%%*/</P>
<P>float  objfunc(float x1)
3 J, w! ^% h0 w! e5 Y0 T{float y;
0 M: H9 p4 W2 N) m  H: N/ y  y=100.0*ff/x1;
  return y;
  }</P>
<P>/*&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;*/</P>
<P>void statistics(pop)
struct pp *pop;
{int j;
sumfitness=pop[0].fitness;
min=pop[0].fitness;
max=pop[0].fitness;
maxpp=0;
minpp=0;
5 @; \. y5 q7 i, h9 Zfor(j=1;j&lt;popsize;j++)
    {sumfitness=sumfitness+pop[j].fitness;
2 M! p. n, d  A6 u, d3 ?/ i     if(pop[j].fitness&gt;max)
( G$ x1 j2 ~2 o! O5 Q( e. l( [{max=pop[j].fitness;
  maxpp=j;
}
     if(pop[j].fitness&lt;min)
& z, S* `2 q! c. b6 X- V9 ~{min=pop[j].fitness;
  minpp=j;
0 H) Y, C9 Q+ I8 j}
    }</P>
<P>avg=sumfitness/(float)popsize;
9 G# S5 J9 V" j4 X+ s8 \# H}</P>
' z. i& V0 z3 J4 Y; _7 P$ W) ]3 X, c<P>/*%%%%%%%%%%%%%%%%%%%%*/</P>
6 h& ]' C: {* v. N' I3 r3 f+ S& L0 J<P>void generation()
6 V" s: q8 V& S, Z/ N( w9 x, f' B{unsigned int k,j,j1,j2,i1,i2,mate1,mate2;
' E, z7 V! m, L0 jfloat f1,f2;
9 N; f1 c, ]0 [* [j=0;
do{
     mate1=select();
4 i1 w) Z* r* A0 L7 T     pp:mate2=select();
     if(mate1==mate2)goto pp;
     crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
     newpop[j].x=(float)decode(newpop[j].chrom);
     newpop[j].fitness=objfunc(newpop[j].x);
2 r8 ]7 Y& y5 T5 z     newpop[j].parent1=mate1;
     newpop[j].parent2=mate2;
5 f' y! z5 X: r; ]     newpop[j].xsite=jcross;
     newpop[j+1].x=(float)decode(newpop[j+1].chrom);
$ v8 s9 L! R6 B4 o  Y1 C: L     newpop[j+1].fitness=objfunc(newpop[j+1].x);
; t( t* i, m9 l$ r$ s     newpop[j+1].parent1=mate1;
$ d0 ?/ M: `4 N% T5 q8 W( L8 H* \     newpop[j+1].parent2=mate2;
     newpop[j+1].xsite=jcross;
  P# s. x5 E* t     if(newpop[j].fitness&gt;min)
{for(k=0;k&lt;lchrom;k++)
      oldpop[minpp].chrom[k]=newpop[j].chrom[k];
/ v& M- R3 i+ x7 I  oldpop[minpp].x=newpop[j].x;
  oldpop[minpp].fitness=newpop[j].fitness;
- Y) n" x7 S! |# Y( ^( B  co_min++;
0 t5 j/ @4 p! g' f$ }" ~8 N% |  return;
}</P>
6 p; v  _  Y1 `1 ]( a& V, U<P>     if(newpop[j+1].fitness&gt;min)
{for(k=0;k&lt;lchrom;k++)
6 _3 M- F* V: z: Z9 u      oldpop[minpp].chrom[k]=newpop[j+1].chrom[k];
* I' \) J$ a: X/ F* k" K) `7 a9 H  oldpop[minpp].x=newpop[j+1].x;
7 o: H6 d. E0 J% M  oldpop[minpp].fitness=newpop[j+1].fitness;
; w2 e5 ^/ C( N2 u- N+ q, Q- t& e8 m  co_min++;
" r# {; d6 o' r/ P: X: @  return;
}
$ m  y  ?: q8 B* q      j=j+2;
     }while(j&lt;popsize);
}</P>
7 f) d3 M8 f8 s  ^1 L; Y<P>/*%%%%%%%%%%%%%%%%%*/</P>
/ y/ E  g% C5 c8 z& ^+ `, f; D<P>void initdata()
{unsigned int ch,j;
' ^1 b7 d' ?) w7 S( _* ?2 q! {clrscr();
printf("-----------------------\n");
printf("A SGA\n");
printf("------------------------\n");
/*pause();*/clrscr();
printf("*******SGA DATA ENTRY AND INITILIZATION *******\n");
printf("\n");
2 Z  e( i, `2 K# aprintf("input pop size");scanf("%d",&amp;popsize);
  s5 C" w7 d8 i9 w  d# M" m, o% @printf("input chrom length");scanf("%d",&amp;lchrom);
printf("input max generations");scanf("%d",&amp;maxgen);
+ x* g, u3 c. L: U8 J: |printf("input crossover probability");scanf("%f",&amp;pcross);
- ?6 [! y- R! q9 Gprintf("input mutation prob");scanf("%f",&amp;pmutation);
& S3 m. R8 `! Y0 z: \randomize1();
* O$ q' a+ y* t3 J( U- Wclrscr();
' {, W5 Z3 d5 C$ m& T& Qnmutation=0;
1 p$ `" e" V* i) kncross=0;
}</P>
<P>/*%%%%%%%%%%%%%%%%%%%%*/</P>
<P>void initreport()
6 C9 o; M+ L& h) O{int j,k;
printf("pop size=%d\n",popsize);
) }+ Z& g; {4 Q. b' V2 lprintf("chromosome length=%d\n",lchrom);
6 y2 E" h+ Z3 h; x6 V: x4 Cprintf("maxgen=%d\n",maxgen);
: v" _* _; t/ v& d0 ~printf("pmutation=%f\n",pmutation);
1 A. i. R, @/ s9 H7 O( |printf("pcross=%f\n",pcross);
printf("initial generation statistics\n");
printf("ini pop max fitness=%f\n",max);
; M4 i0 V  b/ L5 vprintf("ini pop avr fitness=%f\n",avg);
printf("ini pop min fitness=%f\n",min);
. g+ s  G, ?0 W$ kprintf("ini pop sum fit=%f\n",sumfitness);
}</P>
; R5 V# f5 n! m7 Q; E2 o! I<P>
( b, f- ?1 {$ D/ y$ hvoid initpop()
% l+ l+ ?3 u% p{unsigned char j1;
unsigned int k5,i1,i2,j,i,k,j2,j3,j4,p5[maxstring];
& o7 z# o# o( }3 E7 H. w! d4 Kfloat f1,f2;
j=0;
for(k=0;k&lt;lchrom;k++)
7 i: b7 Z0 w/ [4 U9 I  n     oldpop[j].chrom[k]=k;
for(k=0;k&lt;lchrom;k++)
     p5[k]=oldpop[j].chrom[k];
- S& U% q" z6 c) l9 prandomize();
for(;j&lt;popsize;j++)
' i6 ]* X7 [# u5 U     {j2=random(lchrom);
  o9 S2 {3 O+ @" D$ {. W      for(k=0;k&lt;j2+20;k++)
- u# w& A& {9 v' t9 }; D3 E; f  {j3=random(lchrom);
; f8 ^% {" i; Y' M   j4=random(lchrom);
: ^6 b- Q4 v: R2 A   j1=p5[j3];
   p5[j3]=p5[j4];
   p5[j4]=j1;
' F* k7 E) s- G% D! A5 n  }
       for(k=0;k&lt;lchrom;k++)
9 Z  x9 ]/ b/ G  oldpop[j].chrom[k]=p5[k];
7 j: W, i& w. u* C. V4 r( ^     }
" k4 k' t9 v6 p: s( i. l  n  for(k=0;k&lt;lchrom;k++)
1 ?4 P/ ]  H; c5 l  Q3 a    for(j=0;j&lt;lchrom;j++)
" K4 J* E! H2 U8 x       dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]);
9 T4 {# U4 D: |  for(j=0;j&lt;popsize;j++)
( P( O/ s! z. r# s) X    {oldpop[j].x=(float)decode(oldpop[j].chrom);
     oldpop[j].fitness=objfunc(oldpop[j].x);
     oldpop[j].parent1=0;
     oldpop[j].parent2=0;
     oldpop[j].xsite=0;
    }
}</P>
  h' c; o" Z; j$ {" I, }<P>/*&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;*/
void initialize()
{int k,j,minx,miny,maxx,maxy;
initdata();
7 U% ^' T& p4 C5 S. A$ Pminx=0;
miny=0;
maxx=0;maxy=0;
for(k=0;k&lt;lchrom;k++)
   {x[k]=rand();
8 `  J  Y; q; @, |; o    if(x[k]&gt;maxx)maxx=x[k];
. L# v! |2 Y7 Q  q, V( v# Z    if(x[k]&lt;minx)minx=x[k];
3 y3 I; i! w2 ~, E* {    y[k]=rand();
    if(y[k]&gt;maxy)maxy=y[k];
    if(y[k]&lt;miny)miny=y[k];
+ `  k4 F  C- x  N   }
( q% f7 x, l+ q- Xif((maxx-minx)&gt;(maxy-miny))
     {maxxy=maxx-minx;}
. g& `7 t7 D$ H! E    else {maxxy=maxy-miny;}
$ W9 @9 I  m( V* S8 v' ]6 @maxdd=0.0;
for(k=0;k&lt;lchrom;k++)
   for(j=0;j&lt;lchrom;j++)
& s: x# o# g4 l' R2 y$ `2 U5 |7 d     {dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]);
; ~  n, i9 e9 K, b& ^      if(maxdd&lt;dd[k*lchrom+j])maxdd=dd[k*lchrom+j];
5 W( s# D' c4 E0 N     }
refpd=dd[lchrom-1];
for(k=0;k&lt;lchrom;k++)
, ^1 h: [$ U, L9 J7 R* O& p: T   refpd=refpd+dd[k*lchrom+k+2];
for(j=0;j&lt;lchrom;j++)
; R! ~4 F0 w9 r* r# i   dd[j*lchrom+j]=4.0*maxdd;
+ G' t- N5 W5 v1 e, rff=(0.765*maxxy*pow(lchrom,0.5));
0 W# S3 W9 p8 l( v9 G( rminpp=0;
min=dd[lchrom-1];
for(j=0;j&lt;lchrom-1;j++)
6 O) i, c$ v3 S4 i1 \   {if(dd[lchrom*j+lchrom-1]&lt;min)
{min=dd[lchrom*j+lchrom-1];
  minpp=j;
}
    }
initpop();
" D& o  d! h3 L+ O) U8 t3 `  zstatistics(oldpop);
initreport();
' p1 x" t& o8 ~- \- M. d* X! L}</P>
<P>/*&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;*/</P>
<P>void report(int l,struct pp *pop)
{int k,ix,iy,jx,jy;
- y! \, O$ p/ o" X5 e$ Iunsigned int tt;
float ttt;
cleardevice();
9 P5 f: a* x) i- Zgotoxy(1,1);
printf("city:%4d  para_size:%4d  maxgen:%4d  ref_tour:%f\n"
1 b& H. O  I. q6 q& Z1 K- [  m) `   ,lchrom,popsize,maxgen,refpd);
printf("ncross:%4d  Nmutation:%4d Rungen:%4d AVG=%8.4f MIN=%8.4f\n\n"
5 E5 A9 \6 f9 \   ,ncross,nmutation,l,avg,min);
printf("Ref.cominpath:%6.4f Minpath length:%10.4f Ref_co_tour:%f\n"
+ l4 ^. B; Q% L4 _  s5 \$ s   ,pop[maxpp].x/maxxy,pop[maxpp].x,ff);
- `: \, V. H, ^. jprintf("Co_minpath:%6.4f Maxfit:%10.8f"
   ,100.0*pop[maxpp].x/ff,pop[maxpp].fitness);
. x, b$ g2 ?: Fttt=clock()/18.2;
tt=ttt/60;
4 m3 t3 N  ]% i; tprintf("Run clock:%2d:%2d:%4d.2f\n",tt/60,tt%60,ttt-tt*60.0);
setcolor(1%15+1);
for(k=0;k&lt;lchrom-1;k++)
    {ix=x[pop[maxpp].chrom[k]];
# y/ f% J9 t( i7 R2 H# n# Y     iy=y[pop[maxpp].chrom[k]]+110;
+ I$ Q% l" a( r7 a8 }     jx=x[pop[maxpp].chrom[k+1]];
     jy=y[pop[maxpp].chrom[k+1]]+110;
     line(ix,iy,jx,jy);
3 I9 D5 I2 \& U3 D  r. b     putpixel(ix,iy,RED);
" [0 K; e" e  E- v5 Q( l0 c    }
+ y' ^4 |8 N$ B* V2 P+ {. oix=x[pop[maxpp].chrom[0]];
1 }: c# s$ u1 U6 e# D' q! K& x2 Viy=y[pop[maxpp].chrom[0]]+110;
, f. u9 w, E0 Gjx=x[pop[maxpp].chrom[lchrom-1]];
1 G! I, H9 ^$ j1 s$ E% ?jy=y[pop[maxpp].chrom[lchrom-1]]+110;
line(ix,iy,jx,jy);
+ n7 h4 j( e1 {putpixel(jx,jy,RED);
% U( \7 s9 ?% u% M& G* ksetcolor(11);
outtextxy(ix,iy,"*");
2 ?) ]3 M; t- p6 Tsetcolor(12);
for(k=0;k&lt;1%200;k++)
    {ix=k+280;
     iy=366-fm[k]/3;
# Z8 L+ }4 N) P     jx=ix+1;
' q* a: V7 P+ F* g& w     jy=366-fm[k+1]/3;
0 b. I! I. p8 r; i/ F3 Y     line(ix,iy,jx,jy);
     putpixel(ix,iy,RED);
8 U) s$ |0 ?1 z, }/ T# t5 ^0 ~    }
# t; S4 R  Q' {, D+ w0 iprintf("GEN:%3d",l);
5 Y7 E2 L1 \8 x+ ^& K' Sprintf("Minpath:%f Maxfit:%f",pop[maxpp].x,pop[maxpp].fitness);
2 t9 K1 _( M8 K* q3 _printf("Clock:%2d:%2d:%4.2f\n",tt/60,tt%60,ttt-tt*60.0);
}</P>
<P>/*###############*/</P>
<P>float decode(unsigned char *pp)
* ^7 j& j# t0 d# z/ @: v: N0 ]{int j,k,l;
# k9 h3 ]2 X- z- w. J* D, m$ Efloat tt;
tt=dd[pp[0]*lchrom+pp[lchrom-1]];
5 N' G" W8 V1 B/ w2 Q" L( ~/ }for(j=0;j&lt;lchrom-1;j++)
    {tt=tt+dd[pp[j]*lchrom+pp[j+1]];}
l=0;
for(k=0;k&lt;lchrom-1;k++)
   for(j=k+1;j&lt;lchrom;j++)
! C$ q( e- Q1 `' r  ^9 L1 W      {if(pp[j]==pp[k])l++;}
* w6 f) R6 H! x1 D& treturn tt+4*l*maxdd;
}</P>
<P>/*%%%%%%%%%%%%%%%%%%*/
& h$ j; a4 ?# }; k1 c# W: Q) L6 Lvoid crtinit()
{int driver,mode;
struct palettetype p;
+ o$ y6 Q' o  Y1 z+ D6 q! odriver=DETECT;
mode=0;
initgraph(&amp;driver,&amp;mode,"");
9 o- B; S+ L- C7 [cleardevice();
! G) ?3 J* c4 y' \: K}</P>
<P>/*$$$$$$$$$$$$$$$$$$$$*/
6 i8 ?1 z, ~. E* kint select()
4 o/ q+ ]6 a$ q1 t4 {0 G# {{double rand1,partsum;
float r1;
int j;
+ R9 |0 W6 g2 o* qpartsum=0.0;
* }9 x  h0 L( k! _j=0;
rand1=random1()*sumfitness;
$ c! J: F0 w- c% Zdo{
, O8 g* X- t# n* `! ?7 f/ w     partsum=partsum+oldpop[j].fitness;
7 P$ q& P  C) H, S1 `9 r1 D     j=j+1;
7 j9 ~+ p  Y! s$ O( {, c+ j1 w   }while((partsum&lt;rand1)&amp;&amp;(j&lt;popsize));
return j-1;
}</P>
: G1 \/ C. u, e! Y<P>/*$$$$$$$$$$$$$$$*/
4 D+ L) b% d0 eint crossover(unsigned char *parent1,unsigned char *parent2,int k5)
' k0 w/ n5 u' N, m3 q3 N{int k,j,mutate,i1,i2,j5;
; m+ n' j" p* O  jint j1,j2,j3,s0,s1,s2;
unsigned char jj,ts1[maxstring],ts2[maxstring];
float f1,f2;
$ K6 c  Q" l; ]5 ~, w/ }s0=0;s1=0;s2=0;
if(flip(pcross))
3 A. {, ^! U$ Z% `   {jcross=random(lchrom-1);
6 P2 |# T9 \$ S    j5=random(lchrom-1);
    ncross=ncross+1;
4 [* c' R' q1 Z/ _% \+ \; [    if(jcross&gt;j5){k=jcross;jcross=j5;j5=k;}
- N# O8 p# d6 }$ }   }
( w) u  s  |( @7 b   else jcross=lchrom;
if(jcross!=lchrom)
, u4 N% d( ?5 K- F; _8 k# `   {s0=1;
9 A7 @; T2 p% K    k=0;
    for(j=jcross;j&lt;j5;j++)
# C. V& {+ o% t( v1 n# f      {ts1[k]=parent1[j];
4 z- `' e8 b3 v) ^4 y  `2 g       ts2[k]=parent2[j];
       k++;
; N! c% J, w/ B; i( `; M- J5 h      }
    j3=k;
: T2 h9 v. v& ~! a* \3 |7 N    for(j=0;j&lt;lchrom;j++)
       {j2=0;
" L  d( c7 s- M1 Q/ W3 P! Qwhile((parent2[j]!=ts1[j2])&amp;&amp;(j2&lt;k)){j2++;}
- [7 `' c8 i# |if(j2==k)
      {ts1[j3]=parent2[j];
       j3++;
      }
       }
     j3=k;
: C) v- p; B) p+ y' q) o     for(j=0;j&lt;lchrom;j++)
( n* U  g4 |9 q8 a1 I4 H       {j2=0;
while((parent1[j]!=ts2[j2])&amp;&amp;(j2&lt;k)){j2++;}
if(j2==k)
; u! i) b: _3 s- k/ P0 v9 o! m9 u       {ts2[j3]=parent1[j];
        j3++;
7 j4 M1 E* R/ Q2 Q, j       }
       }
     for(j=0;j&lt;lchrom;j++)
       {newpop[k5].chrom[j]=ts1[j];
newpop[k5+1].chrom[j]=ts2[j];
0 T& j8 w& F1 I9 U0 C' L       }
   }
7 d- H) o% T3 ]* P5 melse
& Q* d, Y, w# |% d. ?; b$ e   {for(j=0;j&lt;lchrom;j++)
      {newpop[k5].chrom[j]=parent1[j];
       newpop[k5+1].chrom[j]=parent2[j];
+ X  ~" b  X, Q0 ^      }
    mutate=flip(pmutation);
    if(mutate)
      {s1=1;
3 p) g) v# z0 w. U       nmutation=nmutation+1;
       for(j3=0;j3&lt;200;j3++)
  {j1=random(lchrom);
   j=random(lchrom);
   jj=newpop[k5].chrom[j];
0 \3 a. N; d- ]* G) Y+ a* H   newpop[k5].chrom[j]=newpop[k5].chrom[j1];
$ v% K: _1 V5 ~$ `   newpop[k5].chrom[j1]=jj;
  }
       }
; L% q& A' K$ _. m$ V+ B( ~    mutate=flip(pmutation);
    if(mutate)
      {s2=1;
; n" ?5 T; |2 u4 g% Q6 |       nmutation=nmutation+1;
       for(j3=0;j3&lt;100;j3++)
- L9 [! [8 `  ]' J) [  {j1=random(lchrom);
   j=random(lchrom);
   jj=newpop[k5+1].chrom[j];
# R& }$ M5 Z0 Y1 g) A   newpop[k5+1].chrom[j]=newpop[k5+1].chrom[j1];
  A1 r- x, Q2 w9 x7 j( D. y   newpop[k5+1].chrom[j1]=jj;
  }
  O4 y  l" D+ L; B/ \$ C       }
  }
; w6 [% Z0 K5 T" @- Z1 |3 h  j2=random(2*lchrom/3);
  for(j=j2;j&lt;j2+lchrom/3-1;j++)
    for(k=0;k&lt;lchrom;k++)
       {if(k==j)continue;
if(k&gt;j){i2=k;i1=j;}
      else{i1=k;i2=j;}
) f+ y- Y$ e5 v7 E' M4 `( Af1=dd[lchrom*newpop[k5].chrom[i1]+newpop[k5].chrom[i2]];
f1=f1+dd[lchrom*newpop[k5].chrom[(i1+1)%lchrom]+
* x4 h5 t9 G6 f8 ], z     newpop[k5].chrom[(i2+1)%lchrom]];
; _  a9 T& G. I( T# Nf2=dd[lchrom*newpop[k5].chrom[i1]+
; ]0 Q; v4 z' v/ Y( n) K, |. i     newpop[k5].chrom[(i1+1)%lchrom]];
f2=f2+dd[lchrom*newpop[k5].chrom[i2]+
     newpop[k5].chrom[(i2+1)%lchrom]];
# K& C3 G' I  c: \1 s; [8 ?if(f1&lt;f2){inversion(i1,i2,newpop[k5].chrom);}
       }
  j2=random(2*lchrom/3);
# R) v0 }! X+ V8 o  for(j=j2;j&lt;j2+lchrom/3-1;j++)
: ]7 B/ K8 R/ ~* W+ I9 B' g    for(k=0;k&lt;lchrom;k++)
# l' ?4 ^7 m; G0 q' P/ ^! ^3 r       {if(k==j)continue;
% A, H! L% ]: u  Kif(k&gt;j){i2=k;i1=j;}
% c5 G) Z: p( b& l7 P. d) v2 o      else{i1=k;i2=j;}
f1=dd[lchrom*newpop[k5+1].chrom[i1]+newpop[k5+1].chrom[i2]];
f1=f1+dd[lchrom*newpop[k5+1].chrom[(i1+1)%lchrom]+
* T9 b( L8 |  N6 [     newpop[k5+1].chrom[(i2+1)%lchrom]];
f2=dd[lchrom*newpop[k5+1].chrom[i1]+
     newpop[k5+1].chrom[(i1+1)%lchrom]];
f2=f2+dd[lchrom*newpop[k5+1].chrom[i2]+
7 }: Y7 J7 L: b' Y     newpop[k5+1].chrom[(i2+1)%lchrom]];
if(f1&lt;f2){inversion(i1,i2,newpop[k5+1].chrom);}
/ `: A6 m1 \! E       }
# V# C( u& p3 b9 d  return 1;
}</P>
<P>/*$$$$$$$$$$$$$$$*/</P>
<P>void inversion(unsigned int k,unsigned int j,unsigned char *ss)
5 e7 N6 h8 s2 r* D$ u3 l, c, J. n# r{unsigned int l1,i;
unsigned char tt;
l1=(j-k)/2;
for(i=0;i&lt;l1;i++)
   {tt=ss[k+i+1];
    ss[k+i+1]=ss[j-i];
0 q" E0 N0 X$ {, ~1 r# W- B7 O5 {" p    ss[j-i]=tt;
   }
}</P>
/ B: R4 D) B1 o. t+ o<P>/*%%%%%%%%%%%%%%%*/</P>
/ U! u$ L: Q8 `7 G<P>void randomize1()
{int i;
randomize();
for(i=0;i&lt;lchrom;i++)
   oldrand=random(30001)/30000.0;
jrand=0;
$ c! z/ l! G/ f8 N0 E8 l) M}</P>
<P>/*%%%%%%%%%%%*/</P>
<P>float random1()
{jrand=jrand+1;
if(jrand&gt;=lchrom)
   {jrand=0;
8 q# |0 N# |5 Y8 X( [) H) y    randomize1();
. g/ E4 s* ]: F% p0 ?+ z' P- t   }
3 Q" X7 u8 i" o! V% vreturn oldrand[jrand];
}</P>
' s$ A/ N# [2 j<P>/*%%%%%%%%%%*/</P>
<P>int flip(float probability)
{float ppp;
ppp=random(20001)/20000.0;
9 D& \% o/ N/ B2 V, H/ gif(ppp&lt;=probability)return 1;
return 0;
! B) I6 ^, h* i( A2 r3 ~8 [}</P></DIV>
  E6 E- I5 g2 C9 K9 x
<P>改进后用来求解VRP问题的Delphi程序：</P>
, m1 y) T8 R. w  R5 s<DIV class=HtmlCode>
$ Q' u; U1 x' R% d<P>unit uEA;</P>
<P>interface</P>
4 ^! x! b! d! A* g! }<P>uses
5 F5 w4 [: K3 F! S% E9 juUtilsEA, uIEA, uITSP, Classes, GaPara, windows, SysUtils, fEA_TSP;</P>
5 m' M9 E6 h. M! y  f<P>type
% {8 N) ]# g& d; E3 y+ y6 \TIndividual = class(TInterfacedObject, IIndividual)
private
// The internally stored fitness value
fFitness: TFloat;
8 ~  @# r) }; Z9 _. kfWeConstrain: integer;
fBackConstrain: integer;
fTimeConstrain: integer;
+ i- g+ R/ q* l" t, P% Hprocedure SetFitness(const Value: TFloat);
5 S2 d1 i. ~; M' T6 f: W3 Kfunction GetFitness: TFloat;
- X1 ~; s7 ~' U8 jfunction GetWeConstrain: integer;
procedure SetWeConstrain(const Value: integer);
procedure SetBackConstrain(const Value: integer);
function GetBackConstrain: integer;
/ {9 F$ I6 h+ H' p: ~, jfunction GetTimeConstrain: integer;
: [. X" o1 S5 k* |8 t8 V3 D6 v9 eprocedure SetTimeConstrain(const Value: integer);
public
4 U8 V4 Q% E, Wproperty Fitness : TFloat read GetFitness write SetFitness;
* L3 m- W9 M1 P* a9 T! C0 m# Wproperty WeConstrain :integer read GetWeConstrain write SetWeConstrain;
4 L$ Y. A$ a6 Q& Q4 lproperty BackConstrain :integer read GetBackConstrain write SetBackConstrain;
6 U9 b2 u. d9 X6 u, T) Rproperty TimeConstrain :integer read GetTimeConstrain write SetTimeConstrain;
) K1 B1 g+ C0 m6 c: Y8 zend;</P>
2 n8 v  H. F3 @7 d& C3 l' J; `<P>TTSPIndividual = class(TIndividual, ITSPIndividual)
private
// The route we travel
fRouteArray : ArrayInt;
* T" g+ g# p& r% H5 C# NfWeConstrain: integer;
+ V6 z$ z! G3 f* zfBackConstrain: integer;
* M# Y, z, Q' Z! TfTimeConstrain: integer;
; b/ `2 ]) b9 `function GetRouteArray(I: Integer): Integer;
procedure SetRouteArray(I: Integer; const Value: Integer);
$ d$ |' M5 ?) ?8 V  g8 k, j8 oprocedure SetSteps(const Value: Integer);
function GetSteps: Integer;
: k# I. y1 N/ z" W6 jfunction GetWeConstrain: integer;
) M! O: j# M7 W% R- yprocedure SetWeConstrain(const Value: integer);
5 K) b& `5 u. f! S8 S0 e& [procedure SetBackConstrain(const Value: integer);
9 T1 W# B4 J# R+ C3 {7 t: z0 Gprocedure SetTimeConstrain(const Value: integer);
function GetBackConstrain: integer;
function GetTimeConstrain: integer;
public
" \8 P3 Y9 N. I' E( @" k// Constructor, called with initial route size
constructor Create(Size : TInt); reintroduce;
destructor Destroy; override;
property RouteArray[I : Integer] : Integer read GetRouteArray write SetRouteArray;
// The number of steps on the route
  c$ R+ D) M( P9 `- t" M3 s& Kproperty Steps : Integer read GetSteps write SetSteps;
property Fitness : TFloat read GetFitness write SetFitness;
9 Y, Z- ^8 S' k' P/ ^property WeConstrain :integer read GetWeConstrain write SetWeConstrain;
property BackConstrain :integer read GetWeConstrain write SetBackConstrain;
property TimeConstrain :integer read GetTimeConstrain write SetTimeConstrain;
- M9 v: O7 C6 G3 B  W" {end;</P>
% Z0 Y6 f' ]) S- l: _9 W<P>TTSPCreator = class(TInterfacedObject, ITSPCreator)
private
" M0 @8 _. ?( k$ v9 b// The Control component we are associated with
) u, Y/ M7 ~: n$ ?$ DfController: ITSPController;
! L$ w2 Y- J$ C2 M$ g* r+ `function GetController: ITSPController;
procedure SetController(const Value: ITSPController);
/ v- F3 [2 c, ^( M; `$ s% n, R, f% Qpublic
& z( z8 L! Y  \# t" b1 O, K// Function to create a random individual
function CreateIndividual : IIndividual;
function CreateFeasibleIndividual: IIndividual;
property Controller : ITSPController read GetController write SetController;
& G2 ~6 m9 Y' o1 i- Send;</P>
<P>TKillerPercentage = class(TInterfacedObject, IKillerPercentage)
" n8 Q3 s& E4 F9 g% Y5 Uprivate
" g6 \' w- T" @$ k/ t/ C/ |fPer: TFloat;
8 q$ E; C$ I# m4 r4 _" |procedure SetPercentage(const Value: TFloat);
function GetPercentage: TFloat;
public
function Kill(Pop : IPopulation): Integer;
// Percentage of population to be killed
property Percentage: TFloat read GetPercentage write SetPercentage;
end;</P>
<P>TParentSelectorTournament = class(TInterfacedObject, IParentSelector)
public
# }  @9 z! t1 l$ m6 {2 z) Rfunction SelectParent(Population: IPopulation): IIndividual;
end;</P>
+ n5 [; k- M4 V5 V5 ~<P>TTSPBreederCrossover = class(TInterfacedObject, IBreeder)
2 j  R- y  S* |, q4 X8 xpublic
" V: L4 h+ ~& ^: H  Jfunction BreedOffspring(PSelector: IParentSelector; Pop: IPopulation): IIndividual;
end;</P>
/ T% B$ I$ V# Q! [<P>TTSPMutator = class(TInterfacedObject, ITSPMutator)
/ c2 r7 \5 V. l( _! pprivate
fTrans: TFloat;
fInv: TFloat;
procedure SetInv(const Value: TFloat);
: f# ]- I, v( m+ H2 S) d% B( \- v) Wprocedure SetTrans(const Value: TFloat);
5 w- h) B% b5 B. O; Dfunction GetInv: TFloat;
function GetTrans: TFloat;
6 H0 b" L( h' f  [- X* @public
$ r0 B7 _/ J$ r4 y$ D' zprocedure Mutate(Individual: IIndividual);
published
. A4 O6 q! p$ c% H( M7 h$ ~// Probability of doing a transposition
property Transposition: TFloat read GetTrans write SetTrans;
// Probability of doing an inversion
property Inversion: TFloat read GetInv write SetInv;
end;</P>
- U4 t: F4 t4 U$ ~6 I& `6 q<P>TTSPExaminer = class(TInterfacedObject, ITSPExaminer)
private
// The Control component we are associated with
# {# D0 ?% I( [$ BfController: ITSPController;
3 ~- d/ d, w1 s9 E# W9 p- Wfunction GetController: ITSPController;
# G4 a; c+ c0 W0 n8 b+ yprocedure SetController(const Value: ITSPController);
" ~- j; d, K- b+ wpublic
* Z+ H/ O( ~3 A" F+ J2 S7 ]4 A// Returns the fitness of an individual as a real number where 0 =&gt; best
function GetFitness(Individual : IIndividual) : TFloat;
3 K& ~8 \' ^, P# K5 ~- k/ jproperty Controller : ITSPController read GetController write SetController;
7 @# e& r; L" F# A7 b3 C/ @end;</P>
<P>TPopulation = class(TInterfacedObject, IPopulation)
$ d, J  D  V% }- H. w3 Nprivate
// The population
fPop : TInterfaceList;
( \$ t+ R( M# ^$ Y0 c' u. W// Worker for breeding
! B) G. e- X% Y& |. i" ]3 J6 bfBreeder: IBreeder;
// Worker for killing
fKiller: IKiller;
. i: ^3 k* _% y/ c// Worker for parent selection
fParentSelector: IParentSelector;
// Worker for mutation
( ~/ `. B3 D- v5 ^fMutator: IMutator;
; ?1 Z  a! j& I$ v  _4 R( i// Worker for initial creation
+ ]5 X: D: ^# L# c1 n% o2 s' MfCreator: ICreator;
) Y$ h3 M) k& O+ [) k7 H) @% U// Worker for fitness calculation
/ t( S* N( I+ S8 D( P% m. ^; ~8 d3 ffExaminer: IExaminer;
// On Change event
% E! ^' ?) b0 g1 J2 E; hFOnChange: TNotifyEvent;
' W4 X$ |! E) k) `procedure Change;
. e6 v% x" b* Z1 p, s// Getters and Setters
function GetIndividual(I: Integer): IIndividual;
& P& |. H8 B& M7 c# x( Dfunction GetCount: Integer;
function GetBreeder: IBreeder;
$ R7 n' M) n2 y; B5 sfunction GetCreator: ICreator;
function GetExaminer: IExaminer;
& C! X3 d+ i/ @; x% Hfunction GetKiller: IKiller;
function GetMutator: IMutator;
4 i. `" @2 T7 u& |! j+ }function GetOnChange: TNotifyEvent;
function GetParentSelector: IParentSelector;
procedure SetBreeder(const Value: IBreeder);
. `6 A2 ~6 d  G0 x0 `procedure SetCreator(const Value: ICreator);
% C! s4 {: A" x2 f2 oprocedure SetExaminer(const Value: IExaminer);
procedure SetKiller(const Value: IKiller);
' \3 j/ K- p7 _3 Cprocedure SetMutator(const Value: IMutator);
procedure SetOnChange(const Value: TNotifyEvent);
# [# |; p* e1 f! Gprocedure SetParentSelector(const Value: IParentSelector);
// not interfaced
4 t" @  o- X! T" {3 `: K( q, L+ Sprocedure DanQuickSort(SortList: TInterfaceList; L, R: Integer; SCompare: TInterfaceCompare);
7 y+ ]$ x' M0 \1 z9 [8 gprocedure Sort(Compare: TInterfaceCompare);
protected
// Comparison function for Sort()
. s3 c" E1 o$ p0 I: tfunction CompareIndividuals(I1, I2: IIndividual): Integer;
// Sort the population
/ n* H8 U" f& f( cprocedure SortPopulation;
public
) o& j# ?. J; h6 q0 U. c: |// The constructor
. t  f& c# f$ |$ e/ {constructor Create;
// The destructor
; M  q; U) N/ ~( ?. I! s, ?destructor Destroy; override;
// Adds an individual to the population
& w' c# ^+ x* s5 Aprocedure Add(New : IIndividual);
& x# e2 R: Z. p4 V  P// Deletes an individual from the population
procedure Delete(I : Integer);
// Runs a single generation
" t, i+ `) Y* D% s& k- `procedure Generation;
// Initialise the population
procedure Initialise(Size : Integer);
) w9 H+ N1 ^  t# H" @: f+ R// Clear ourselves out
procedure Clear;
// Get the fitness of an individual
- s- ?" _% `+ w" h; Ifunction FitnessOf(I : Integer) : TFloat;
* m. U- k" n' g) C// Access to the population members
property Pop[I : Integer] : IIndividual read GetIndividual; default;
" b7 }8 @% g2 g' g$ O7 A// The size of the population
property Count : Integer read GetCount;
property ParentSelector : IParentSelector read GetParentSelector write SetParentSelector;
. D1 q3 s7 u* ~: R! W% I) n; dproperty Breeder : IBreeder read GetBreeder write SetBreeder;
property Killer : IKiller read GetKiller write SetKiller;
property Mutator : IMutator read GetMutator write SetMutator;
% v7 F! ^$ o, w1 e  O# Mproperty Creator : ICreator read GetCreator write SetCreator;
7 I; E6 d, k2 n5 Iproperty Examiner : IExaminer read GetExaminer write SetExaminer;
7 J' ?. u  P9 O1 U8 N; B// An event
property OnChange : TNotifyEvent read GetOnChange write SetOnChange;
end;</P>
<P>TTSPController = class(TInterfacedObject, ITSPController)
private
fXmin, fXmax, fYmin, fYmax: TFloat;
& x, j. J! H# c+ r/ D4 S{ The array of 'cities' }
fCities : array of TPoint2D;
- `; U/ @) N6 @3 U, ?4 }) v{ The array of 'vehicles' }
fVehicles : array of TVehicle;
{ The array of 'vehicle number' }
0 ~* D4 r$ M0 c. b9 H4 r/ @2 AfNoVehicles : ArrayInt;/////////////////////
. }1 A  ~6 U4 v' r{ The number of 'new cities' }
fCityCount: Integer;
{ The number of 'old cities' }
" }3 E; f* d; M- \, i  e/ kfoldCityCount: Integer;
6 Q2 R, ^$ `' Z$ P$ W2 l{ The number of 'travelers' }
5 Z& w. \' C' |: BfTravelCount:Integer; ///////////////////////
1 `( u; v6 b7 q7 O) w  l& c{ The number of 'depots' }
fDepotCount:Integer; ///////////////////////
/ b0 e. \/ @' a" J7 f6 {. c{ Getters... }
7 ~5 O9 ~# M0 M7 k( Q1 \* Yfunction GetCity(I: Integer): TPoint2D;
4 z# C) n+ A# ]+ Z4 ?function GetNoVehicle(I: Integer): TInt;
- w" {* y) Z% ?" Xfunction GetCityCount: Integer;
function GetOldCityCount: Integer;
7 x% j# v* X0 d, z  Q7 bfunction GetTravelCount:Integer;
function GetDepotCount:Integer;
, X* Q+ w# j2 o2 L2 q9 ~function GetXmax: TFloat;
) ^, q2 O6 H/ d( K5 N) W/ X2 G, `( Mfunction GetXmin: TFloat;
function GetYmax: TFloat;
+ n/ Q' Z1 M; J3 i7 Dfunction GetYmin: TFloat;
{ Setters... }
+ K& h. T- c4 M, Bprocedure SetCityCount(const Value: Integer);
  y: K, c% v* ^& o, g8 T5 `& U7 {procedure SetOldCityCount(const Value: Integer);
* o, u1 |. t3 T. o$ ]7 O) L, }; y8 Lprocedure SetTravelCount(const Value: Integer); /////////////
procedure SetDepotCount(const Value: Integer); /////////////
procedure SetXmax(const Value: TFloat);
procedure SetXmin(const Value: TFloat);
procedure SetYmax(const Value: TFloat);
& R9 R- x9 w  ^% v4 jprocedure SetYmin(const Value: TFloat);
function TimeCostBetween(C1, C2: Integer): TFloat;
function GetTimeConstraint(Individual: IIndividual): TInt;
function DateSpanToMin(d1, d2: TDateTime): integer;
! `  Q# s1 @- r0 H4 B6 Sfunction GetVehicleInfo(routeInt: Tint): integer;
procedure writeTimeArray;
/ B$ G9 @0 o$ h2 v5 F+ ]1 `procedure writeCostArray;
* Y; P1 S8 X! Z* xpublic
{ The constructor }
constructor Create;
; ]' |+ H( U; p7 N4 [{ The destructor }
* n3 p* i7 m& x7 G6 t) ]$ f& ?) jdestructor Destroy; override;
{ Get the distance between two cities }
function DistanceBetween(C1, C2 : Integer) : TFloat;
; m3 ~% @& ~/ ]7 v; f{ Get the cost between two cities }
function CostBetween(C1, C2: Integer): TFloat;</P>
: \& A) v$ @" k" U  k: W; Y<P>function GetWeightConstraint( Individual: IIndividual): TInt;</P>
<P>function GetBackConstraint( Individual: IIndividual): TInt;
- @4 f7 Z9 W! V( G3 d; j# E{ Places the cities at random points }
procedure RandomCities;
{ Area limits }
property Xmin: TFloat read GetXmin write SetXmin;
  j% s2 I7 s3 {property Xmax: TFloat read GetXmax write SetXmax;
& J- C1 l+ K  Q! V2 r8 Aproperty Ymin: TFloat read GetYmin write SetYmin;
property Ymax: TFloat read GetYmax write SetYmax;
$ t  F  v7 f2 Y0 i1 _  |{ Properties... }
property CityCount : Integer read GetCityCount write SetCityCount;
8 q* v9 ?& |5 E$ I6 W" wproperty OldCityCount : Integer read GetOldCityCount write SetOldCityCount;
property TravelCount : Integer read GetTravelCount write SetTravelCount; ///////////
; ]: c+ b! `8 y$ Oproperty DepotCount : Integer read GetDepotCount write SetDepotCount; ///////////
  p) G$ p0 _. q2 D6 a, o) e{ Access to the cities array }
6 I' A& {' n) N. u& `property Cities[I : Integer] : TPoint2D read GetCity;
( k- _4 ^4 F& }$ `6 b; \property NoVehicles[I : Integer] : TInt read GetNoVehicle; ///////////////
end;</P>
3 a6 A( N9 [& v  q- M5 @) c<P>implementation</P>
<P>uses
! \1 w! W; l5 b0 D% P0 V3 GMath;</P>
' ]9 D) e6 l$ h/ ~" N<P>{ TIndividual }</P>
4 M2 z+ N6 E/ F# b. u" U% i/ W<P>function TIndividual.GetFitness: TFloat;
begin
result := fFitness;
3 e  D( T7 Z0 _  u# N% Eend;</P>
<P>function TIndividual.GetWeConstrain: integer;
begin
" R; O' L3 M. o- Z8 zresult := fWeConstrain;
end;</P>
<P>function TIndividual.GetBackConstrain: integer;
begin
result := fBackConstrain;
end;</P>
' n3 ]1 u: q* ~$ E! l1 S<P>function TIndividual.GetTimeConstrain: integer;
begin
result := fTimeConstrain;
end;</P>
+ D4 y( u$ A9 u: d- t4 Y% U  W<P>procedure TIndividual.SetBackConstrain(const Value: integer);
begin
3 ]7 m' S6 A0 T# nfBackConstrain := Value;
" `  {) N) R$ j$ dend;</P>
<P>procedure TIndividual.SetFitness(const Value: TFloat);
begin
fFitness := Value;
end;</P>
4 Z' k( r; U3 K+ o! f9 g$ j<P>procedure TIndividual.SetWeConstrain(const Value: integer);
0 O6 R: Y# T5 a! J- h6 sbegin
fWeConstrain := Value;
. \7 Y4 U: p0 Y+ ]/ j. J- bend;</P>
<P>procedure TIndividual.SetTimeConstrain(const Value: integer);
, c2 E1 Y, ]% P8 K' mbegin
fTimeConstrain := Value;
end;</P>
<P>{ TTSPIndividual }</P>
( h" }% T5 i* Z; b5 X3 e<P>constructor TTSPIndividual.Create(Size: TInt);
+ c/ Y! ]! j) a5 g+ Rbegin
2 s- B% e  _( t# U) P; M) n; cInherited Create;
SetLength(fRouteArray, Size);
// fSteps := Size;
( {- f* Q4 r" mend;</P>
<P>destructor TTSPIndividual.Destroy;
( q$ l( S  ]1 X+ w! K( Cbegin
' G- Q7 [# O9 @4 v' M+ L5 {5 iSetLength(fRouteArray, 0);
inherited;
# R. @" V7 R! [; e4 [: _5 b4 Gend;</P>
<P>function TTSPIndividual.GetRouteArray(I: Integer): Integer;
begin
  `5 c4 V& @+ `$ `" X% C* rresult := fRouteArray[I];
end;</P>
! {" `* X1 h- S. W<P>function TTSPIndividual.GetSteps: Integer;
begin
result := Length(fRouteArray);
" R% {9 u3 n8 i5 o/ a# O6 D' }end;</P>
<P>procedure TTSPIndividual.SetSteps(const Value: Integer);
! g% k9 ]3 g: f6 X+ |. qbegin
SetLength(fRouteArray, Value);
0 _% |2 ]: Z  b9 t- }" e& Tend;</P>
<P>procedure TTSPIndividual.SetRouteArray(I: Integer; const Value: Integer);
begin
fRouteArray[I] := Value;
end;</P>
* n2 Y6 T, f# [9 e0 B) G& N<P>function TTSPIndividual.GetWeConstrain: integer;
begin
result := fWeConstrain;
end;</P>
* t! g2 a: S7 n; P" y<P>function TTSPIndividual.GetBackConstrain: integer;
begin
result := fBackConstrain;
5 r9 U6 E# O* x9 ]end;</P>
<P>function TTSPIndividual.GetTimeConstrain: integer;
begin
result := fTimeConstrain;
1 U0 W/ t0 @( I, {+ c! |$ Oend;</P>
  R( {! L8 `# @: o5 p' ?4 a" z<P>procedure TTSPIndividual.SetWeConstrain(const Value: integer);
, l' [! I4 Y/ n# fbegin
- s- Z- }. E  M, jfWeConstrain := Value;
4 A' x/ Z; P4 hend;</P>
9 S- K0 H$ m( E6 U7 U0 m<P>procedure TTSPIndividual.SetBackConstrain(const Value: integer);
begin
, l& v+ U( R6 UfBackConstrain := Value;
end;</P>
& J3 `( M1 E  M# c<P>procedure TTSPIndividual.SetTimeConstrain(const Value: integer);
begin
fTimeConstrain := Value;
) A- B1 z+ z; o5 F8 }' [end;</P>
; {) _5 y1 ]6 ]+ p<P>{ TTSPCreator }</P>
9 B6 q! ~* `5 E+ a+ G# w$ J0 l6 ~<P>function TTSPCreator.CreateIndividual: IIndividual;
var
New: ITSPIndividual;
i, j, Top, Temp : Integer;
7 F) Z$ P! ]5 M. @//trav:integer;
0 @! R) z9 t% ^2 o. A5 bbegin
# }- w* R( w- f2 M4 @5 y" H3 x// Get the number of cities
: y) ~' B# d' _3 @6 E5 t( fTop := fController.CityCount;
0 v2 l) n$ c9 _2 D( g// Create the new individual
- \/ i1 x$ P3 v- y( f4 Y& WNew := TTSPIndividual.Create(Top);
// Initialise it with a sequential route
; N: S; G  ~6 }0 l% ffor i := 0 to Top - 1 do
# _1 ~8 d( u5 }New.RouteArray := i;
// Shuffle the route
for i := Top - 1 downto 1 do
begin
j := Random(i);
" _* J/ }8 x, L3 r2 g4 l; x2 s$ i- WTemp := New.RouteArray[j];
  {: Q1 o* p' ~% i. ~  T6 lNew.RouteArray[j] := New.RouteArray;
New.RouteArray := Temp;
end;
/ {6 l! H0 d: Bresult := New;
end;</P>
<P>function TTSPCreator.CreateFeasibleIndividual: IIndividual;
var
New: ITSPIndividual;
i, j, Top, Temp : Tint;
Msg:TMsg;
8 E; G5 \4 l+ \" ?begin
// Get the number of cities
Top := fController.CityCount;
" x- Z/ b7 W% L1 U0 Y// Create the new individual
New := TTSPIndividual.Create(Top);
2 u: w6 F6 h" O" R& V0 l" y// Initialise it with a sequential route
6 `& T5 E3 G  t+ arepeat
. y( v+ S' U( w5 R, g9 \/ ybegin//////////////////////////////////
' P6 e8 X4 g# G  G( Wfor i := 0 to Top - 1 do
New.RouteArray := i;
// Shuffle the route
: W- ~5 n1 A( jfor i := Top - 1 downto 1 do
begin
j := Random(i);
  F. H0 O% H1 \% V% MTemp := New.RouteArray[j];
New.RouteArray[j] := New.RouteArray;
# R' D+ @$ a* N3 w9 c* \New.RouteArray := Temp;
# g) @2 P: g  c$ Y! H# C2 Kend;
+ e% T: p* U, l' S" T//process message sequence//////////
- U# W3 J. q6 d/ ~while PeekMessage(Msg,0,0,0,1) do///
begin ///
( h7 ^" w0 ]9 S5 qif Msg.Message&lt;&gt;18 then ///
$ b% g8 T3 }: K7 s  `begin ///
+ ^& N! q$ f( `; B% zTranslateMessage(Msg); ///
) Z* Q- W3 Q( z/ |; i0 H$ XDispatchMessage(Msg); ///
end; ///
: c# h9 _- z+ K* R4 G9 O8 K' p; kend; ///
# Y9 N$ i. C% m$ u) Y$ L////////////////////////////////////
1 u9 E  E% d: \end
until (fController.GetWeightConstraint(New)=0)and(fController.GetBackConstraint(New)=0);</P>
; P, L* E7 W4 q0 g<P>result := New;
; |  T3 m7 F9 }7 `1 Yend;</P>
: j7 p- C, m4 _5 I# J4 W, H9 ^<P>function TTSPCreator.GetController: ITSPController;
begin
result := fController;
end;</P>
<P>procedure TTSPCreator.SetController(const Value: ITSPController);
, |$ r+ ^1 k0 ^! hbegin
% t- @$ }4 [4 {# H7 kfController := Value;
  z# v: o# X: |% Zend;</P>
/ v( N' l7 H4 D1 y0 S4 v<P>{ TKillerPercentage }</P>
: p) m3 D4 b1 {3 |  }- \" I/ W% s<P>function TKillerPercentage.GetPercentage: TFloat;
' _6 t1 R( o. I6 Z9 h6 Nbegin
) V, C+ |. n, [* f5 Oresult := fPer;
* g" f& }. f" E8 |$ y* P1 [end;</P>
<P>function TKillerPercentage.Kill(Pop: IPopulation): Integer;
var
; }  }( q2 l1 u  @! y- y9 }) @- Q! SKillCount, i : Integer;
7 g7 [8 c; q4 K4 @1 jbegin
// Work out the number we have to kill
KillCount := Floor(Pop.Count * (fPer / 100));
// Delete the worst individuals - assuming the population is sorted
: r( D7 A! u5 h! b: cfor i := 1 to KillCount do
& D" t0 g& H: K5 O( a& t" a3 jPop.Delete(Pop.Count - 1);
// Return the number killed
Result := KillCount;
end;</P>
3 o  h. O' a- O8 s$ y% F$ R, {<P>procedure TKillerPercentage.SetPercentage(const Value: TFloat);
3 y7 U! Y% [: k( w# e2 l$ N  E0 ubegin
3 H) h3 V" o3 d" Y# k- h* L" ]fPer := Value;
end;</P>
<P>{ TParentSelectorTournament }</P>
. g- r0 v! j8 f- j1 W<P>function TParentSelectorTournament.SelectParent(
Population: IPopulation): IIndividual;
$ J& ]* D& X- o8 {: w, Dvar
i1, i2 : Integer;
7 ]1 [+ V" J7 O8 Y! J" `0 dbegin
+ i$ V' ?5 F% \2 n$ ?// Select a random individual
1 |7 j; C' p1 O$ J+ P0 b0 U* m8 `i1 := Random(Population.Count);
$ A" j( V8 U$ w4 k5 z% i// Select a *different* random individual
repeat
1 T  G3 W1 h) L# U+ K( p  w9 D5 {i2 := Random(Population.Count);
until i1 &lt;&gt; i2;
8 x9 Y! L; K6 w! E5 I// Hold the tournament and return the fittest of the two
if Population.FitnessOf(i1) &lt; Population.FitnessOf(i2) then
Result := Population[i1]
else
Result := Population[i2];
0 }! P% F9 b% ~# i) eend;</P>
" ^8 o- k& b: s2 F<P>{ TTSPBreederCrossover }</P>
& V' ?8 q- y  E8 R8 c( q9 Z- t3 |<P>function TTSPBreederCrossover.BreedOffspring(PSelector: IParentSelector;
8 c# p& [5 G0 y$ T5 `Pop: IPopulation): IIndividual;
/ p$ X& E2 @7 c2 Yvar
( @+ [9 I- b+ {. Z! aChild, Mom, Dad, Parent1, Parent2 : ITSPIndividual;
i, j, p : Integer;</P>
<P>function AlreadyAssigned(City, x : Integer) : Boolean;
var
y : Integer;
Found : Boolean;
begin
Found := False;
8 t2 t% ?) S# k$ ]for y := 0 to x - 1 do
, h( Y3 z: Y2 i- a' vbegin
if Child.RouteArray[y] = City then
+ }# u0 V7 O  Y2 ^8 Fbegin
" [5 m% v* p9 SFound := True;
3 N3 d  V5 b5 m- v0 ~  [  b, N( UBreak;
: }) P4 G* ^; }( i* bend;
end;
Result := Found;
end;</P>
<P>begin
// Select a some parents...
3 X' k4 w6 `0 t" @) QMom := PSelector.SelectParent(Pop) as ITSPIndividual;
3 R) [" E0 }  T3 O( fDad := PSelector.SelectParent(Pop) as ITSPIndividual;
// Create a child
0 {3 k" h) q+ R3 V' l5 nChild := TTSPIndividual.Create(Mom.Steps);
// Copy the route from parents to child
for i := 0 to Child.Steps - 1 do
begin
// Choose a parent at random
: e! T8 T& V& m9 e# qp := Random(2);
  m' U, ^/ ]) Y( l  Cif p = 0 then
begin
Parent1 := Mom;
/ {/ h" A, R# MParent2 := Dad;
end else
% q% i# c5 z# x5 Bbegin
Parent1 := Dad;
7 n! N  Y$ h( T$ C" p, ~Parent2 := Mom;
9 \& J7 J, j; y  j7 X6 ^8 ^% Gend;
if not AlreadyAssigned(Parent1.RouteArray, i) then
* z6 ]8 `8 u5 o  q4 rbegin
// Use city from Parent 1 unless used already
6 L( O  P% V7 Z0 ~9 i# b) [Child.RouteArray := Parent1.RouteArray;
/ H! l) H% w! A$ h: hend else
" J0 b: O- z5 _- ^0 Zif not AlreadyAssigned(Parent2.RouteArray, i) then
begin
. _: G( g5 k" M$ ]// Otherwise use city from Parent 2 unless used already
- V* L( d; l* {0 U- U6 JChild.RouteArray := Parent2.RouteArray;
end else
9 Z: i0 t1 c, S! z' zbegin
// If both assigned already then use a random city
, L( n6 g* U0 o" T) s7 V. ^* erepeat
j := Random(Child.Steps);
until not AlreadyAssigned(j, i);
' s4 l  [# \) _& @6 M5 HChild.RouteArray := j;
end;
3 Y2 [6 q9 q. Z9 \, i; X4 Qend;
// Return the child
Result := Child;
end;</P>
<P>{ TTSPMutator }</P>
3 G5 Q3 d/ v, i2 E<P>function TTSPMutator.GetInv: TFloat;
! g2 D: m8 {% z! C- s" ?8 Bbegin
result := fInv;
- y3 b, y( D0 P- nend;</P>
8 A) e" s4 Q( A9 [6 T! Z$ T- ?; y<P>function TTSPMutator.GetTrans: TFloat;
  H. t0 e5 B% h, ~# i9 d( Tbegin
result := fTrans;
end;</P>
<P>procedure TTSPMutator.Mutate(Individual: IIndividual);
var
P: Double;
i, j, t : Integer; Start, Finish : Integer;
begin
, ]: |% @5 D4 x& D) X* O+ ^with Individual as ITSPIndividual do
begin
" R0 E* \5 r# a! e- K// Should we do an inversion?
+ t  f+ l1 G0 \  b" QP := Random * 100;
if P &lt; FTrans then
1 S5 ^. f( y9 T3 rbegin
& }6 B: N, o3 F5 O/ Q// Do an inversion (i.e. swap two cities at random)
8 C; O4 I- j7 W3 _* t" _// Choose first city
0 \! O, W. N# @  vi := Random(Steps);
// Choose a second city
/ a# {: R5 G8 |0 _/ Nrepeat
& ~( z' Y2 g5 f+ Q9 lj := Random(Steps);
until i &lt;&gt; j;
// Swap them over
* `0 k' W8 Q& c. ]t := RouteArray;
' C- l( [1 Q4 M9 o/ KRouteArray := RouteArray[j];
RouteArray[j] := t;
3 D( G4 T( y! i% Z" q* c8 F; Wend;
& w+ s. g& I" J5 w+ R// Should we do a transposition?
  M6 ~9 J: e$ w$ E8 A# mP := Random * 100;
if P &lt; FInv then
3 E' U! I$ k/ U4 S% e$ ]# {1 fbegin
- E: X+ A9 p& R/ M  {. j- O// Do a transposition (i.e. reverse a sub-route)
// Choose random start and finish points
Start := Random(Steps - 1);
$ `" l& r& ^/ B) l) sFinish := Start + Random(Steps - Start);
// Reverse the sub-route
9 ]/ @7 o2 ~! C6 Q4 Q6 afor i := 0 to Floor((Finish - Start) / 2) do
begin
t := RouteArray[Start + i];
RouteArray[Start + i] := RouteArray[Finish - i];
RouteArray[Finish - i] := t;
% w) b- `2 W9 O2 @. `) p5 P* b' hend;
end;
end;
end;</P>
& g9 J8 R4 Y( Q. b* @' {<P>procedure TTSPMutator.SetInv(const Value: TFloat);
, u* ~  v. W2 Z- o1 Jbegin
fInv := Value;
end;</P>
<P>procedure TTSPMutator.SetTrans(const Value: TFloat);
begin
fTrans := Value;
" m. M& r# H0 V# pend;</P>
<P>{ TTSPExaminer }</P>
<P>function TTSPExaminer.GetController: ITSPController;
begin
) S( p! ]3 J1 Uresult := fController;
end;</P>
) W8 X7 u% r4 I) I& U8 d" R<P>function TTSPExaminer.GetFitness(Individual: IIndividual): TFloat;
0 M; p8 I: S& v7 Ivar
% ~, H& Z- R- K5 K) J: j# z, O* I: Ti , weightConstraint, backConstraint : TInt;
Distance , penaltyW, penaltyB : TFloat;
: ~! b1 y, \9 w8 D7 ~Indi : ITSPIndividual;
, l; s6 l( V, C( N" ]6 |0 _; Cbegin
  Y: S: g0 E  z4 VIndi := Individual as ITSPIndividual;
Distance := 0;
penaltyW:=FormGaPara.EditWeightConstrain.Value;
# @# ~+ j' b! l& wpenaltyB:=FormGaPara.EditBackConstrain.Value;
for i := 0 to Indi.Steps - 2 do
begin
Distance := Distance + fController.DistanceBetween(Indi.RouteArray, Indi.RouteArray[i + 1]);
end;
Distance := Distance + fController.DistanceBetween(Indi.RouteArray[Indi.Steps - 1], Indi.RouteArray[0]);
3 Q3 E! q* X1 EWeightConstraint:=fController.GetWeightConstraint(Indi);
backConstraint:=fController.GetBackConstraint(Indi);
Indi.WeConstrain:=WeightConstraint;
Indi.BackConstrain:=backConstraint;
Result := Distance+penaltyW*weightconstraint+penaltyB*backConstraint;
& W( S$ k$ J8 I- [end;</P>
<P>procedure TTSPExaminer.SetController(const Value: ITSPController);
begin
fController := Value;
end;</P>
<P>{ TPopulation }</P>
, w( ?+ G; F4 x, k$ K+ H<P>constructor TPopulation.Create;
$ v- C: ?; y% ?# Lbegin
inherited;
fPop := TInterfaceList.Create;
% N  Q4 a( o: j1 [3 {& V( ~end;</P>
<P>destructor TPopulation.Destroy;
4 R- y! d1 T& o9 T+ q- H/ wbegin
fPop.Free;
inherited;
, B% J' Q9 b; H6 H( t* Lend;</P>
<P>procedure TPopulation.Add(New: IIndividual);
begin
. Y" f1 u/ B' f" S3 p, NfPop.Add(New);
# ^: ]' I) W) u$ o# {end;</P>
* d+ ~- t9 U1 u! {: s0 j<P>procedure TPopulation.Clear;
1 n5 _7 I7 o/ y& G* c, g8 Fbegin
/ f% D; g/ d4 g* ~; S( kfPop.Clear;
: e" M. X* J0 aend;</P>
7 ?, f5 ]. t* j6 `<P>function TPopulation.CompareIndividuals(I1, I2: IIndividual): Integer;
var
8 L/ }9 J/ E4 L, v$ ~: kA, B, D : TFloat;
begin
// Get the difference between the two individuals (real number)
* r( B; Z3 \+ p; VA := I1.Fitness;
9 I7 z  |* X% B3 D0 C/ u* gB := I2.Fitness;</P>
( P' |! ]. c) ^<P>D := A - B;</P>
<P>// Quickest way to convert that to an integer is...
if D &gt; 0 then
Result := 1
1 z* q' Y* z# F# Z/ @) J6 Lelse if D &lt; 0 then
Result := -1
else
3 y6 W2 j% n9 C% O. V% M0 mResult := 0;
end;</P>
<P>procedure TPopulation.Delete(I: Integer);
; |: c6 k" j) Zbegin
fPop.Delete(I);
end;</P>
: Y+ n7 h1 t, t) ]<P>function TPopulation.FitnessOf(I: Integer): TFloat;
begin
result := Pop[I].Fitness;
end;</P>
<P>procedure TPopulation.Change;
& f2 X' I1 x- J9 o3 D; }) o; tbegin
3 T: p$ c3 q' K( }% rif Assigned(fOnChange) then
FOnChange(Self);
4 m% ?: E' ]5 j  Jend;</P>
<P>procedure TPopulation.Generation;
# G/ a* O2 L) m' I- C  svar
% g8 l6 E' J" x% I/ ~3 J5 @% G! DReplace, i : Integer;
+ y! a$ Q, w; ~  \3 }- t$ dNew : IIndividual;
7 W+ p" B6 \, }; r1 A! s! Ybegin
// Kill some of the population
Replace := fKiller.Kill(Self);</P>
) x# ^0 c# G$ X! `: d* B( x: C( b<P>for i := 1 to Replace do
+ C6 F5 n9 S" ?. ~% V+ z3 [- X% |begin
% f6 Q7 J/ j, a) ?/ N1 K// Breed a new individual
+ S  R/ ]7 F0 |( F( M3 sNew := fBreeder.BreedOffspring(fParentSelector, Self);
// Perform some mutation on the individual
FMutator.Mutate(New);
// Get the fitness of the new individual
New.Fitness := fExaminer.GetFitness(New);
! P/ \% D1 I# j3 [# e: H, _' ?, O' |// Add it to the population
Add(New);
end;
// Sort the population into fitness order where first &lt;==&gt; best
SortPopulation;</P>
- T/ Q+ F( _: [; x' C9 @<P>Change;
end;</P>
<P>function TPopulation.GetBreeder: IBreeder;
begin
result := fBreeder;
8 I0 R* x7 Y, iend;</P>
4 W( a) B+ _% I: ^$ X<P>function TPopulation.GetCount: Integer;
begin
# Y# Q, @  f9 W: r. rresult := fPop.Count;
end;</P>
" H4 E/ \8 Y: T# X3 D! X$ x<P>function TPopulation.GetCreator: ICreator;
begin
8 o! H1 @$ L, l3 j; @+ _result := fCreator;
3 x. [/ B" q6 l* Kend;</P>
+ v- H8 n' Q; D5 x<P>function TPopulation.GetExaminer: IExaminer;
begin
result := fExaminer;
end;</P>
) r: p- n  }# W% M- n( ]( k3 a<P>function TPopulation.GetIndividual(I: Integer): IIndividual;
begin
result := (fPop[I] as IIndividual);
/ x0 X& T. `5 J0 Uend;</P>
) Y* Q" S2 v3 Z  E3 f) H1 z<P>function TPopulation.GetKiller: IKiller;
+ q0 g' L& ?* {+ e, ?begin
, S9 N( J& ]6 j- l* Hresult := fKiller;
2 N) {1 c9 N5 z0 A; Rend;</P>
% Z) |2 g. f7 C( V9 _, G<P>function TPopulation.GetMutator: IMutator;
3 Q& V  a0 d* O9 r2 f" `2 Rbegin
result := fMutator;
- j# B2 Q( l' E5 R* {end;</P>
( Y$ L) e; E- |2 y7 H4 a<P>function TPopulation.GetOnChange: TNotifyEvent;
begin
- j/ Q) F% F: \" E8 lresult := fOnChange;
end;</P>
" f- O9 f0 \. u6 g2 b4 ^2 W<P>function TPopulation.GetParentSelector: IParentSelector;
begin
result := fParentSelector;
/ ~4 ^. y# c0 |9 Tend;</P>
/ O. x  W. `$ t+ a2 z% _<P>procedure TPopulation.Initialise(Size: Integer);
/ p% }& A* P( l% M9 n0 Lvar
i,feasibleCount: Integer;
3 F1 H# S) Z0 TNew: IIndividual;
+ n1 @7 p; b* t; |5 |begin
& f8 D& E) `  C, }5 s& Q, d6 XfeasibleCount:=round(size*(FormGaPara.EditFeasible.Value)/100);
6 M: ?& t- @4 v2 P//feasibleCount:=1;
/ L; W1 w% J, ?6 u' |// Clear out the old stuff
; ^" u0 k$ v4 Q* ~2 I2 QClear;
& i3 r8 z) o5 n2 h% _9 _0 j0 ?% N// Set the capacity first to save about 12 nanoseconds ;o)
fPop.Capacity := Size;
$ N( W+ h' i) Y2 ^// Create the appropriate number of individuals
; s5 k! L! C- I( v# O  Cfor i := 1 to feasibleCount do
/ w6 |1 ^( C. Z, obegin
6 Z# H" V6 H- o// Create the individual
- {% g" G+ ^6 r# ?& l2 S5 c$ wNew := fCreator.CreateFeasibleIndividual;
0 _  [( d) F1 V* `4 Q2 E5 Y// Get the fitness of the new individual
: z) O  K" \5 ZNew.Fitness := fExaminer.GetFitness(New);
// Add to the population
( k: c) u9 y( A: t, [: WAdd(New);
. g$ i3 k$ S! B, s* |end;
for i := feasibleCount+1 to Size do
begin
// Create the individual
New := fCreator.CreateIndividual; ////////
9 L; F2 s1 ~6 q* X, M4 m$ K7 d. A( }3 P// Get the fitness of the new individual
New.Fitness := fExaminer.GetFitness(New);
// Add to the population
Add(New);
* N, r9 O. E$ W: f/ Kend;
4 e2 B3 ^* ~) O9 q6 SSortPopulation;
Change;
end;</P>
<P>procedure TPopulation.SetBreeder(const Value: IBreeder);
begin
fBreeder := Value;
end;</P>
% A0 O; c% x9 b8 G; ^- b- ^5 B<P>procedure TPopulation.SetCreator(const Value: ICreator);
5 V5 B. ~# h5 x; d4 c2 n# B8 d0 Cbegin
fCreator := Value;
end;</P>
<P>procedure TPopulation.SetExaminer(const Value: IExaminer);
! B2 R& x! Q2 `6 ]8 ?1 v' f2 t; Ebegin
fExaminer := Value;
end;</P>
<P>procedure TPopulation.SetKiller(const Value: IKiller);
begin
fKiller := Value;
end;</P>
<P>procedure TPopulation.SetMutator(const Value: IMutator);
4 w; K: G- Z- l; }" Y- v. lbegin
$ K2 {3 k& Q5 T0 N- KfMutator := Value;
end;</P>
<P>procedure TPopulation.SetOnChange(const Value: TNotifyEvent);
4 S! _2 B/ b# Ibegin
fOnChange := Value;
end;</P>
<P>procedure TPopulation.SetParentSelector(const Value: IParentSelector);
begin
! |. w. m5 B. h! YfParentSelector := Value;
0 h+ |0 R" ~' Z1 J5 u5 ]( dend;</P>
<P>procedure TPopulation.DanQuickSort(SortList: TInterfaceList; L, R: Integer;
SCompare: TInterfaceCompare);
var
* l: o( L8 Y" ]I, J: Integer;
. P, J: X$ U! \: H0 j# rP: IIndividual;
# \  }5 d" ^! Bbegin
# u2 _& K8 M: }& l9 [' Qrepeat
! j5 p/ P/ v) @( ]0 b6 B. LI := L;
, }1 }" c! B6 L* o* \J := R;
( I. b* p+ O- [* DP := SortList.Items[(L + R) div 2] as IIndividual;
repeat
0 ^9 U) l( d2 }1 l+ E1 X) x$ {while SCompare(SortList.Items[I] as IIndividual, P) &lt; 0 do
: k4 A$ B& I/ ?9 J( t( O9 u7 |Inc(I);
while SCompare(SortList.Items[J] as IIndividual, P) &gt; 0 do
- C# O8 v/ Q- {8 V6 i5 R  kDec(J);
if I &lt;= J then
begin
SortList.Exchange(I, J);
# L# Q: g8 w, D! r& i/ z/ v3 jInc(I);
Dec(J);
end;
until I &gt; J;
5 [+ ?( P: S: `: d! v5 ?7 p! h$ Wif L &lt; J then
1 C' x8 b8 Y) u: g$ WDanQuickSort(SortList, L, J, SCompare);
L := I;
4 ^0 }8 E' h4 v6 tuntil I &gt;= R;
end;</P>
7 A6 [& g( [/ M7 u/ a. m<P>procedure TPopulation.Sort(Compare: TInterfaceCompare);
' }+ O; J- l5 _+ R/ mbegin
if Assigned(fPop) and (Count &gt; 0) then
DanQuickSort(fPop, 0, Count - 1, Compare);
end;</P>
<P>procedure TPopulation.SortPopulation;
' l  Y) ?3 r5 P% y# @3 n4 ^begin
' x8 w' N) B! b0 T& ISort(self.CompareIndividuals);
; L, s" A, K* x: bend;</P>
' p* A8 _! g- d; q1 D$ }<P>{ TTSPController }</P>
<P>constructor TTSPController.Create;
begin
inherited;
2 G0 S6 x6 B! }$ N* O8 i; u8 w  D- Bend;</P>
<P>destructor TTSPController.Destroy;
begin
/ ^6 `  [. s& gSetLength(FCities, 0);
SetLength(FNoVehicles, 0);
SetLength(FVehicles, 0);
inherited;
4 i. P- r9 v! ?0 C: E8 R( ]0 a$ [end;</P>
% c# W& L4 o, U) X1 x<P>{ Standard euclidian distance between two 2D vectors... }
function TTSPController.DistanceBetween( C1, C2: Integer): TFloat;
var
6 d2 U2 g. Q& t' Ntemp:TFloat;
5 v" W/ L1 s0 M1 l; Fi,j,intTemp,intTemp2:TInt;
' d% ~$ U! K3 k0 f8 V  Mbegin
intTemp:=0;
temp:=FormGaPara.EditWrongConstrain.Value;</P>
7 u' s. [* s9 H<P>{if (Cities[C2].id&gt;=1)and(Cities[C2].id&lt;=fOldCityCount)and(Cities[C1].id&lt;&gt;0) then
: g( U" o9 A; N* j; p8 pbegin
6 e2 s; s; t: j& Q& GfCities[C2].serviceDepot:= fCities[C1].serviceDepot;
end; //}
//8
if (Cities[C1].id&gt;=1)and(Cities[C1].id&lt;=fOldCityCount)and(Cities[C2].id&gt;=1)and(Cities[C2].id&lt;=fOldCityCount) then
begin
temp:=CostArray[C1,C2];
" @( p# @$ v# Hend;
! Z% n6 a2 R, r" v* {//1
if Cities[C1].id=0 then
2 n) h, J+ Q* a6 G8 Y0 r' ~begin
for i:=0 to fDepotCount-1 do
begin
intTemp:=intTemp+fNoVehicles;
if Cities[C2].id =fOldCityCount + intTemp +1 then
3 y8 p/ d5 b( T% F! ytemp:=0;
1 [5 d+ M% u9 \end;
0 y+ r% O' H7 u  h) uintTemp:=0;
end;
//2
4 r  G8 ]% Y' Hif Cities[C2].id=0 then
% ?. a' E; Y( o/ B3 I5 I% Lbegin
for i:=1 to fDepotCount do
% P" v# R5 v0 dbegin
intTemp:=intTemp+fNoVehicles;
if Cities[C1].id =fOldCityCount + intTemp then
temp:=0;
end;
intTemp:=0;
end;
//5
2 F, _$ Q1 C; x$ pfor i:=0 to fDepotCount-1 do
) f* M/ o# s% E2 I2 O$ g9 K, J' Kbegin
intTemp:=intTemp+fNoVehicles;
/ o5 z9 v8 M  C) `& N) y4 d# P{ if (Cities[C1].id=fOldCityCount + intTemp +1)and(Cities[C2].id=Cities[C1].id+1) then
! G. s* V. Z& p: u! c; l0 B7 V: }temp:=10; /////////////////////////// }
if (Cities[C1].id&gt;=fOldCityCount + intTemp +1)and(Cities[C1].id&lt;=fOldCityCount + intTemp+fNoVehicles[i+1])
  y2 B& O: U4 B; Land(Cities[C2].id&gt;=fOldCityCount + intTemp +1)and(Cities[C2].id&lt;=fOldCityCount + intTemp+fNoVehicles[i+1])
* Z5 U4 _8 p: j" I& Lthen
temp:=0;//}
$ }- j" V* f' ^1 l' \2 o: F9 Nend;
7 _6 j6 [* ~0 P$ x: k. ointTemp:=0;
//7
; Q2 |, v  L, M1 t# r( \if (Cities[C1].id=Cities[C2].id)and(Cities[C1].id &gt; fOldCityCount) then
! T) M7 d3 @3 {" J/ s2 obegin
temp:=0;
end;
//3
7 X' T5 Q& K0 F: b" v  Gif (Cities[C1].id &gt; fOldCityCount)and(Cities[C2].id&gt;=1)and(Cities[C2].id&lt;=fOldCityCount) then
/ M" J, [0 Y% a3 }: C4 l9 fbegin
6 c& x! M( a9 b5 V//temp := Sqrt(sqr(Cities[C1].X - Cities[C2].X)+sqr(Cities[C1].Y - Cities[C2].Y));
temp:=CostArray[C1,C2];
7 w; m' J8 |, k, f1 p4 P$ oend;
//4
; c  ]8 I+ q2 `6 I' ]- `  g! Z. nif (Cities[C1].id&lt;=fOldCityCount)and(Cities[C1].id&gt;=1)and(Cities[C2].id &gt; fOldCityCount) then
begin
//if Cities[C1].serviceDepot=Cities[C2].serviceDepot then //back to the start point
temp:=CostArray[C1,C2];
3 h2 F0 B4 F8 l1 n6 H0 Pend;
//6
! H5 L1 K2 o9 r6 UintTemp:=0;
9 ~2 r) {; ^5 P- u5 F; [for i:=1 to fDepotCount do
* o4 f. w! F  V: }8 |3 Vbegin
intTemp:=intTemp+fNoVehicles;
6 o- e2 }6 e, r1 `1 \" Z! W! Q. fif Cities[C1].id= fOldCityCount + intTemp then
* b# m" `4 ^6 |/ Lbegin
intTemp2:=0;
for j:=0 to fDepotCount-1 do
begin
intTemp2:=intTemp2+fNoVehicles[j];
9 q# j: ]1 r  a2 r5 ~if Cities[C2].id=fOldCityCount + intTemp2 +1 then
0 R. |, d9 R6 C* {+ _if abs(Cities[C2].id-Cities[C1].id) &lt;&gt; fNoVehicles-1 then
2 {7 `8 W& k1 l( ?: F+ htemp:=0;
end; //}</P>
+ q2 z" F+ S1 O% K<P>end;
end;
intTemp:=0;
6 u' K5 |+ i  k. Z/ V: D+ P8 }8 |result:=temp;
end;</P>
, l4 k4 W# u3 N" S<P>function TTSPController.CostBetween(C1, C2: Integer): TFloat; //matrix cij
/ l; |5 B  Y1 T$ o3 c9 Tvar
distance:TFloat;
+ @. u- G3 k8 s, p; Mbegin
distance := Sqrt(sqr(Cities[C1].X - Cities[C2].X)+ sqr(Cities[C1].Y - Cities[C2].Y));
% y0 P( j0 G0 w# f/ V5 J//result:=distance+TimeCostBetween(C1,C2);
result:=distance;
( d& Q4 R& {# P* l2 m7 Iend;</P>
0 s5 r1 Q+ T/ ^7 v<P>function TTSPController.TimeCostBetween(C1, C2: Integer): TFloat;
1 y3 g) E2 t% k! uvar
cost:TFloat;
i,j,penaltyW,penaltyD:TFloat;
startTime:TDateTime;
begin
startTime:=strToDateTime(FormGa.EditStartTime.Text);
2 J6 ?; \7 x/ c( t. }penaltyW:=FormGaPara.EditWaitConstrain.Value;
9 T% t" E' o9 w, w8 V- m4 TpenaltyD:=FormGaPara.EditDelayConstrain.Value;
9 H8 N: K) [' X3 R8 Bif Cities[C2].id&gt;fOldCityCount then
  W7 w5 c) ?' B' VfCities[C2].totalTime:=0
# J, m- y! T! a) Eelse
1 d: n* `' M: l9 B8 V& ]1 t) N* ffCities[C2].totalTime:=Cities[C1].totalTime+Cities[C1].serviceTime+timeArray[C1,C2];</P>
* q# c8 i2 |4 g0 [( M) ~5 }7 Z<P>fCities[C2].waitTime:= max(0,DateSpanToMin(startTime,Cities[C2].early)-Cities[C2].totalTime);
7 Y  W0 L$ W4 w$ xfCities[C2].delayTime:=max(0,Cities[C2].totalTime-DateSpanToMin(startTime,Cities[C2].late));</P>
<P>if Cities[C2].late&lt;&gt;0 then //consider time or not
begin
if Cities[C2].early&lt;&gt;0 then //window or deadline
cost:=penaltyW*fCities[C2].waitTime +penaltyD*fCities[C2].delayTime
' d+ t  M1 i$ j" R: L9 [9 r$ g: r3 `else
cost:=penaltyD*fCities[C2].delayTime;
9 U& E( s" O( i0 |# B2 ~end
/ Y$ T$ e0 T1 [6 ]/ melse
cost:=0;
result:=cost;
end;</P>
<P>function TTSPController.DateSpanToMin(d1,d2:TDateTime):integer;
$ J* }) m0 R5 W2 w9 mvar
span:TDateTime;
3 r# e6 L( w7 v- U5 H% DYear, Month, Day, Hour, Min, Sec, MSec: Word;
$ K. \  {. m' T8 d3 ]9 A  U$ {begin
* x/ Y6 K4 m) L0 A% |$ Xspan:=abs(d2-d1);
DecodeDate(span, Year, Month, Day);
" G3 J$ o  o/ `  [DecodeTime(span, Hour, Min, Sec, MSec);
result:=Min;
end;</P>
8 z- H! k4 Y( k7 e- N+ q<P>//return the position in the vehicles array
function TTSPController.GetVehicleInfo( routeInt:Tint):integer;
' ?0 i5 w  n3 }$ w+ \begin
result:=routeInt-fOldCityCount-1;
* Q7 ?0 D1 Z3 g- s( x. F' |end;</P>
<P>function TTSPController.GetWeightConstraint( Individual: IIndividual): TInt;
/ u* \, [6 s* w& K; S% Vvar
9 |& w; J* }& J9 ^- NIndi: ITSPIndividual;
, i" k* K- D# MtotalCapacity,maxCapacity: TFloat;
( L2 x3 Y3 z7 R* z8 [6 ji,j:TInt;
) t  Q/ w7 i3 \5 ]tempArray:array of TInt;
tempResult:TInt;
begin
3 U/ [9 [: V8 f# h1 W. C" C: MIndi := Individual as ITSPIndividual;
8 S0 b3 a" |" S1 _2 t* n7 h9 \SetLength(tempArray, fCityCount+1);
. B$ i8 n6 Z  JtempResult:=0;
# P1 E/ Q3 ~( B; V9 K4 ~: i/////////////////////////////////////////////////////////
9 S, N% Z, @: ]9 L: T7 Tfor i:=0 to fCityCount-1 do
begin
/ w$ H6 R  X, }if Indi.RouteArray=fOldCityCount+1 then
9 L- g9 U( `3 U/ L% ybreak;
end;
for j:=0 to fCityCount-i-1 do
begin
tempArray[j]:= Indi.RouteArray[i+j];
3 G2 F& s. X8 ~' k* k7 uend;
9 t1 k8 B( u5 E. x$ V0 Ifor j:=fCityCount-i to fCityCount-1 do
- y* [1 g# r; s) K" Ibegin
tempArray[j]:= Indi.RouteArray[j-fCityCount+i];
end;
tempArray[fCityCount]:= tempArray[0];
8 _3 l4 e* ~% I2 A$ _5 \//////////////////////////////////////////////////////////
+ L# o. Q2 n2 k+ [3 u//totalCapacity:=fCities[tempArray[0]].supply; //supply
0 U3 z1 S- E# E7 D1 BmaxCapacity:=fVehicles[GetVehicleInfo(tempArray[0])].volume;
totalCapacity:=maxCapacity;
for i:=0 to fCityCount do
begin
  P+ I$ V( e. i; C6 wif (FCities[tempArray].id&lt;=fOldCityCount)and(FCities[tempArray].id&gt;0) then
begin
* Q" I8 ^* m( k! P' C/ t( l  |totalCapacity:=totalCapacity+FCities[tempArray].supply-FCities[tempArray].demand;
' Q1 q2 |  T; a; `& d$ k9 l& mif (totalCapacity&gt;maxCapacity)or(totalCapacity&lt;0) then
% K1 {. V3 j' N7 i$ O) abegin
tempResult:=tempResult+1;
//break;
end;
9 ^/ {- m) I! B5 j' n% j/ q1 oend;
if FCities[tempArray].id&gt;fOldCityCount then
9 h% ?& u0 O/ [0 Zbegin
//totalCapacity:=fCities[tempArray].supply; //supply
maxCapacity:=fVehicles[GetVehicleInfo(tempArray)].volume;
8 J% }7 O: T! w5 L% {totalCapacity:=maxCapacity;
$ t+ [4 k6 M: y( v2 ^% A% F7 t; k' hend;
end;
SetLength(tempArray,0);
result:=tempResult;
end;</P>
* k1 i# M& U( G9 M<P>function TTSPController.GetBackConstraint( Individual: IIndividual): TInt;
var
! D% V$ s5 l7 v9 l. KIndi: ITSPIndividual;
i,j:TInt;
tempArray:array of TInt;
tempResult:TInt;
, r+ B( n! ]; s: K5 h3 n) A* S7 i2 Ubegin
7 d( O1 a- Y& X1 s7 U& i& n- lIndi := Individual as ITSPIndividual;
# j* F  q0 w) B6 `/ OSetLength(tempArray, fCityCount+1);
' H3 a5 A, K8 [* W. O1 u% C( l2 DtempResult:=0;
for i:=0 to fCityCount-1 do
begin
5 `/ Z9 }: D" lif Indi.RouteArray=fOldCityCount+1 then
break;
3 }% Z+ v7 M3 h; e1 x4 cend;
- m( V# K$ B* Q4 mfor j:=0 to fCityCount-i-1 do
9 |& u3 Y6 V1 U' Rbegin
tempArray[j]:= Indi.RouteArray[i+j];
end;
4 V- W" B' `  q4 x& Y0 H. lfor j:=fCityCount-i to fCityCount-1 do
begin
: W. r' Z" O1 H, t  VtempArray[j]:= Indi.RouteArray[j-fCityCount+i];
end;
2 U+ e7 }3 k8 {# K2 ^2 ftempArray[fCityCount]:=tempArray[0];
{tempArray[0]:=11;tempArray[1]:=5;tempArray[2]:=8;tempArray[3]:=7;
tempArray[4]:=9;tempArray[5]:=6;tempArray[6]:=12;tempArray[7]:=10;
; p1 W* k* G# s7 btempArray[8]:=2;tempArray[9]:=4;tempArray[10]:=3;tempArray[11]:=1;
tempArray[12]:=0;tempArray[13]:=11;tempArray[14]:=3;tempArray[15]:=1;
9 M6 b  q) C$ Z0 f; ~) A/ ntempArray[16]:=4;tempArray[17]:=11;//10,2,2}
6 J8 D9 o3 x) l2 J6 f, o" D/ Ffor i:=0 to fCityCount-1 do
begin
9 ]( Y, ~( {% b& H9 p2 u, ]0 vif (Cities[tempArray[i+1]].id&lt;=fOldCityCount) then
( I* o: ]$ M! Y8 I1 j# Kbegin
fCities[tempArray[i+1]].serviceDepot:= fCities[tempArray].serviceDepot;
7 x% A! L3 r" S$ H6 n; hend;
if (Cities[tempArray].id&lt;=fOldCityCount)and(Cities[tempArray].id&gt;=1)and(Cities[tempArray[i+1]].id &gt; fOldCityCount) then
begin
if Cities[tempArray].serviceDepot&lt;&gt;Cities[tempArray[i+1]].serviceDepot then //back to the start point
begin
1 R/ Q4 S, Z0 h, GtempResult:=tempResult+1;
! G3 x. G; z/ {8 r" T// break;
! O2 ~+ u% y- P: m  c/ Oend;
1 h- e: ?6 _6 T; D& k3 rend;
end;
3 O/ @: M0 j( y$ I) r& fSetLength(tempArray,0);
result:=tempResult;
end; </P>
0 H- f0 f5 c+ O$ \! L<P>function TTSPController.GetTimeConstraint( Individual: IIndividual): TInt;
) g6 |( I8 B& |; \$ h+ Wvar
Indi: ITSPIndividual;
i,j:TInt;
totalTimeCost:TFloat;
8 \' c6 M  B' T' btempArray:array of TInt;
3 `" _- a2 c: y, y5 JtempResult:TInt;
begin
" {3 g% F5 B4 F* @+ V+ lIndi := Individual as ITSPIndividual;
SetLength(tempArray, fCityCount+1);
tempResult:=0;
; k4 l; e0 W. L3 mfor i:=0 to fCityCount-1 do
begin
& d# E5 x+ ^5 X7 O# Rif Indi.RouteArray=fOldCityCount+1 then
break;
end;
0 d9 ~9 g' K3 g1 }for j:=0 to fCityCount-i-1 do
! p/ ^7 O3 w+ ^begin
tempArray[j]:= Indi.RouteArray[i+j];
; {  g3 k$ Z; iend;
for j:=fCityCount-i to fCityCount-1 do
begin
9 A' j+ b/ O" I( I! [tempArray[j]:= Indi.RouteArray[j-fCityCount+i];
- A3 r( o0 c! l  k6 \- P  I  Kend;
& B& |: }6 D! w# Y3 jtempArray[fCityCount]:=tempArray[0];</P>
<P>totalTimeCost:=0;
for i:=0 to fCityCount-1 do
begin
7 S) e+ y. X% b" r) L& w+ xtotalTimeCost:=totalTimeCost+timeCostBetween(tempArray,tempArray[i+1]);
5 }; b2 v% e$ x( e( K: }" h& Gend;
if totalTimeCost&lt;&gt;0 then tempResult:=1;
. q: P4 W, e2 s9 d" tSetLength(tempArray,0);
8 C, g- w' B! @* D& g5 G) ?& pend;</P>
+ }! y) ]6 v6 o/ y+ P9 D, T6 p6 d<P>function TTSPController.GetCity(I: Integer): TPoint2D;
. e) S! C" k7 u7 E7 `' @4 V! Ebegin
4 Y7 V* P9 e0 |' Jresult := fCities[I];
end;</P>
8 g. Z( T9 ]# F$ `  a: I8 v8 {<P>function TTSPController.GetNoVehicle(I: Integer): TInt;
+ @+ w. @' J  H5 n4 M0 @begin
result := fNoVehicles[I];
end;</P>
" o8 T5 F1 V/ G- P% y3 A<P>function TTSPController.GetCityCount: Integer;
/ k8 x" g' [# d7 `. m( B' G, Ibegin
% ~) X2 x) l- ~6 Q; @result := fCityCount;
end;</P>
+ g% W5 t& E# R<P>function TTSPController.GetOldCityCount: Integer;
) x7 _* [* I" l+ mbegin
result := fOldCityCount;
7 o2 \8 {* C) |1 P8 D  Mend;</P>
<P>function TTSPController.GetTravelCount: Integer;
& `5 d: m  ~1 P& l5 }# ?begin
! F; L7 \0 ?/ U% l+ g; ^/ ~result := fTravelCount;
end;</P>
5 I1 I$ Q5 y/ u6 w7 j5 A<P>function TTSPController.GetDepotCount: Integer;
0 @! h$ D9 Y5 Fbegin
result := fDepotCount;
5 N/ [: z7 `: h, ]1 Z' ]/ send;</P>
<P>function TTSPController.GetXmax: TFloat;
begin
result := fXmax;
5 A+ V4 D0 ?7 rend;</P>
0 O6 }# J: C0 K2 A( p* U<P>function TTSPController.GetXmin: TFloat;
begin
result := fXmin;
9 f6 ~8 m7 [# {" ?  q/ @# V1 m1 |0 }end;</P>
, Z. w3 X* c" G3 L<P>function TTSPController.GetYmax: TFloat;
3 s- e8 Z; e; x1 g* Z$ Q' Vbegin
; K. H7 Z3 `9 ^5 v" ?result := fYmax;
* z: ^9 r* G, o% kend;</P>
<P>function TTSPController.GetYmin: TFloat;
- h2 p) z' D0 \! ^begin
3 p/ o1 ~0 W: O1 V/ D! i1 uresult := fYmin;
end;</P>
<P>procedure TTSPController.RandomCities; //from database
var
$ f) X) ~4 s' N) |; ^: s+ ri,j,k,m,intTemp,totalVehicleCount: Integer;
tempVehicle:TVehicle;
begin
//////////////////////////////////////////////////////////
fNoVehicles[0]:=0;
totalVehicleCount:=0;
for i:=1 to fDepotCount do //from depots database
4 G- {5 Q2 v( xbegin
' R2 q* f  H, R6 d1 ?fNoVehicles:=fTravelCount +1;
; J! F2 P/ O! L( Z8 l# c9 Y; AtotalVehicleCount:=totalVehicleCount+ fNoVehicles; //real and virtual vehicles
+ t2 G. m( k; Oend;
SetLength(fVehicles,totalVehicleCount);
intTemp:=0;
: Q- I5 k/ e- K/ Vfor i:=1 to fDepotCount do
) B5 o1 c! N& M9 Ubegin
2 s/ N8 M$ G# V% b7 q2 x6 `: {  m% Z* qfor j:=intTemp to intTemp+fNoVehicles-2 do
/ ~0 J% }2 }& B7 b# sbegin
, d2 b2 i2 [! U& xfVehicles[j].index:=j+1;
fVehicles[j].id:='real vehicle';
fVehicles[j].volume:=50;
end;
2 z, `' b0 i: g1 [4 ?0 Uwith fVehicles[intTemp+fNoVehicles-1] do
0 h( x9 s; o- Y% b% p5 a# Lbegin
index:=intTemp+fNoVehicles;
3 U- M' Y1 p8 B5 E) X( q6 U2 fid:='virtual vehicle';
# m" b4 f" @8 Dvolume:=0;
* O4 z& `4 h1 g, U6 nend;
intTemp:=intTemp+ fNoVehicles;
+ }* W2 p( [: n! e4 }3 m. V  Dend;</P>
<P>///////////////////////////////////////////////////////////
9 S- L" z" T" l4 B& l7 Z& qintTemp:=0;
4 c$ }, o+ V- \# `; k( x9 kfor i:=1 to fDepotCount do //depot 1--value
/ _& r, b' s) q. pbegin
# z6 w: _; B3 ZintTemp:=intTemp + fNoVehicles;
1 F) w; w. n! Xend;</P>
& x1 L9 V0 r. g7 y; x% H<P>for i := 0 to FOldCityCount do //from database
$ k# S! ~4 E% k( w7 O( I2 \; a+ R. ^begin
7 y5 a& O9 B" ]6 G2 r! BFCities.id:= i;
5 b7 e: z! K" ^! V7 XFCities.X := Xmin+0.5+(Xmax-Xmin-1.0)*Random;
* l; a% x0 b3 D" ~2 vFCities.Y := Ymin+0.5+(Ymax-Ymin-1.0)*Random;
FCities.early:=0;
" o6 ?2 U$ a6 D# g0 J+ l) CFCities.late:=0; //TDateTime
  s  Y/ V, ]$ P0 C+ C, uFCities.serviceTime:=0;
FCities.totalTime:=0;
FCities.waitTime:=0;
9 t# S% K! k' Z, R8 F! ZFCities.delayTime:=0;
9 M( G9 W  m/ r( ^2 Z. zend;
& h! D7 G( W8 \3 Xfor i:=FOldCityCount+1 to FCityCount-1 do
! ?% l% B0 v8 e2 e$ P5 @- C4 zbegin
' j9 P' C9 V# Y% f! B7 {FCities.id:= i;
if fDepotCount=1 then
% g+ u4 U( _! e0 u, m2 t; Gbegin
! C2 V( ~9 w/ f; r9 iFCities.X := Xmin+0.5+(Xmax-Xmin-1.0)*RandomRange(2,4)/5;
FCities.Y := Ymin+0.5+(Ymax-Ymin-1.0)*RandomRange(2,4)/5;
# Z$ r7 z7 i$ X* }end
9 z) a9 X4 q5 Qelse
begin
$ K0 U, N9 _5 hFCities.X := Xmin+0.5+(Xmax-Xmin-1.0)*Random;
FCities.Y := Ymin+0.5+(Ymax-Ymin-1.0)*Random;
end;
; A" p7 G! V) ?* s! A, RFCities.early:=0;
FCities.late:=0; //TDateTime
FCities.serviceTime:=0;
FCities.totalTime:=0;
, R$ q% ~1 P& Z% }& u* |4 KFCities.waitTime:=0;
1 ]. i8 a" }. r2 Q3 }4 V1 sFCities.delayTime:=0;
  I- D# p& _( i+ F3 T+ mend;</P>
<P>for i := 0 to FOldCityCount do
- w/ z2 p4 s/ ]+ obegin
; P0 ^1 v: ?% R, LFCities.serviceDepot:=i;
! N% Y# ^4 R$ l7 e. q) S; eend;</P>
<P>m:=FOldCityCount+1;
for k:=1 to fDepotCount do
4 W* @& ^! Q# V% Lbegin
for j:=0 to fNoVehicles[k]-1 do
! f4 s4 \+ _8 v: b8 bbegin
" n: n9 w! m1 d5 LFCities[m].serviceDepot:= fOldCityCount+k;
m:=m+1;
; J) T" d2 I6 r( Pend;
end;</P>
<P>//supply and demand //////////////////////////from database
FCities[0].demand:=0;
FCities[0].supply:=0;
for i:=1 to FOldCityCount do
begin
FCities.demand:=10;
FCities.supply:=0;
end;
5 h$ y+ R4 V; ]! L- T9 }& c9 hfor i:=FOldCityCount+1 to FCityCount-1 do
begin
) N$ H7 J, v# ]; H: p' J5 Q1 wFCities.demand:=0;
FCities.supply:=50;
end;
////////////////////////////////////////////////////////////</P>
" V" H. \4 Z2 |<P>intTemp:=0;
for i:=0 to fDepotCount-1 do
/ ?# R6 T: [& }begin
, a' C/ T$ x6 _intTemp:=intTemp+fNoVehicles;
) D+ X  W, `) z4 b# T& n3 P( ofor j:=2 to fNoVehicles[i+1] do
begin
9 o/ M9 s5 ~; x- |& b6 @! d2 mFCities[fOldCityCount + intTemp +j].X :=FCities[fOldCityCount + intTemp +1].X;
* P; g* F8 F2 ~8 K. aFCities[fOldCityCount + intTemp +j].Y :=FCities[fOldCityCount + intTemp +1].Y;
7 V' D/ Q2 H' o! k2 k9 j/ t" qend;
end;
0 M0 R1 J. G6 m- E/ n& QwriteTimeArray;
writeCostArray;
& }8 n; D& m, |# c* rend;</P>
<P>procedure TTSPController.writeTimeArray; //database
var
i,j:integer;
begin
SetLength(timeArray,fCityCount,fCityCount);
for i:=0 to fCityCount-1 do
- l4 X9 N$ Q  m/ l: b4 x2 Kbegin
for j:=0 to fCityCount-1 do
, W, f; `7 Z! J" F5 L7 c2 y" Obegin
( h$ E4 \2 P1 A/ i" W* z% Jif i=j then timeArray[i,j]:=0
. r# o4 [+ V9 B8 C5 T2 t9 [else timeArray[i,j]:=10;
( ?. k% y5 H6 t5 E& N4 Y# bend;
4 k" o1 p8 A6 Z  kend;
% t2 ^( L- M& {+ N. {( U! Fend;</P>
7 J( u; B- ~/ o- U2 A<P>procedure TTSPController.writeCostArray; //database
2 E! w4 @. ]6 D& \5 S6 b' G' wvar
i,j:integer;
% N0 h3 w0 N6 _9 x+ a" J& Sbegin
  x$ }" \7 x: R7 C5 b2 oSetLength(costArray,fCityCount,fCityCount);
2 T" y' b+ N+ b8 f2 F# o$ Sfor i:=0 to fCityCount-1 do
begin
for j:=0 to fCityCount-1 do
: J/ N5 K2 L( q( v* n9 x9 P5 i. }begin
if i=j then costArray[i,j]:=0
4 q' q6 n5 \1 a4 G" F3 p! Telse costArray[i,j]:=costBetween(i,j);
# f' s# c* ~' f) Uend;
end;
end;</P>
  t7 ^7 o0 Q" v: g6 ~: a  i<P>procedure TTSPController.SetCityCount(const Value: Integer);
begin
! x+ ^0 Z( O) u$ p; q7 [) u5 |SetLength(fCities, Value);
fCityCount := Value;</P>
<P>RandomCities;
; z  S9 M6 b" hend;</P>
<P>procedure TTSPController.SetOldCityCount(const Value: Integer);
begin
fOldCityCount := Value;
end;</P>
1 D) F8 D( M2 ]! t) J4 g* l<P>procedure TTSPController.SetTravelCount(const Value: Integer); ///////////
begin
9 z, L- [0 Z& p' T$ N3 q  f/ a3 |fTravelCount := Value;
end;</P>
+ E0 `6 u' z( F4 ]6 E- }. z<P>procedure TTSPController.SetDepotCount(const Value: Integer); ///////////
# B* \  ^4 V' V7 w$ Hbegin
$ q; X: i! f; \* I" ]7 aSetLength(fNoVehicles, Value+1); ///////////////
fDepotCount := Value;
8 K) a- X' \. {( s8 e/ h$ _, @4 zend;</P>
<P>procedure TTSPController.SetXmax(const Value: TFloat);
3 z$ c# J+ r& Kbegin
) u* F- ~* q( s5 L0 Q% ffXmax := Value;
end;</P>
<P>procedure TTSPController.SetXmin(const Value: TFloat);
begin
fXmin := Value;
7 B) P8 V3 l, Tend;</P>
' F& L) B" R5 n* x  x! [1 [0 S9 x<P>procedure TTSPController.SetYmax(const Value: TFloat);
4 p  N6 S' s# y% }begin
fYmax := Value;
end;</P>
- [, u6 v8 S# `8 A, F+ I, D<P>procedure TTSPController.SetYmin(const Value: TFloat);
begin
+ a: O( u0 H* b+ d7 UfYmin := Value;
, @3 @* w  H% `, i- Iend;</P>
9 s" }* c) n8 M* d  J4 T<P>end.
+ ?# ]6 a! I5 P/ l2 I$ I</P></DIV>
1 m+ J" W. @2 i( I

[此贴子已经被作者于2005-4-27 15:51:02编辑过]

ilikenba

<>Evocosm encapsulates the fundamental principles of evolutionary algorithms in an extensible set of standard C++ templates and tools. Evolutionary algorithms come in a variety of shapes and flavors -- genetic algorithms, genetic programming, evolutionary computing -- but at their core, they all share certain characteristics: populations that reproduce and mutate through a series of generations, producing future generations based on some measure of fitness.
Evocosm将进化算法的基本原则封装在一套可扩展的标准C++模板和工具中。进化算法可以各种各样--遗传算法、遗传编程、进化计算等等，但是它们的核心都共享一些特点：种群通过几代来繁殖和成熟，基于某种适当性量度来产生未来的代。</P>
5 r4 }/ @4 ?4 a7 z# d<>这是进化算法解决TSP问题的源代码：</P>

ilikenba

<>该算法是由意大利学者M.Dorigo、V.Maniez-zo、A.Colorini等人首先提出的,称之为蚁群系统(antcolonysystem), 该模型已成功应用于求旅行商问题(ＴＳＰ),二次指派问题,排序问题等ＮＰ-困难的组合最优化问题,结果可与模拟退火,遗传算法等通用的启发式算法相媲美.蚁群算法和局部搜索算法相结合(称为混合蚁群算法)应用于解二次指派问题和排序问题,得到的结果可以与专用算法相媲美].受其影响,蚁群系统模型逐渐引起了其它研究者的注意,D.Costa和A.Hertz.</P>
3 ]) W* H. B& G5 M6 c; O& Y<>在M.Dorigo等人研究成果的基础上,提出了一种求解分配类型问题(assignmenttypeproblem)的一般模型,并用来研究图着色问题.G.Bilchev、I.C.Parmee研究了求解连续空间优化问题的蚁群系统模型.。</P>
<>蚁群算法是模仿蚂蚁工作方式的一种新的启发式算法.生物学研究表明一群互相协作的蚂蚁能够找到食物源和巢之间的最短路径,而单只蚂蚁则不能.蚂蚁间相互协作的方法是它们在所经过的路上留下一定数量的信息素(迹),该迹能被其它蚂蚁检测出来,一条路上的迹越多,其它蚂蚁将以越高的概率跟随此路径,从而该路径上的迹会被加强.</P>
<>蚂蚁算法伪码
" w% t+ ^- q) |Begin
初始化:
) M4 E, F1 F' V. ]3 O$ Ft← 0
iteration← 0 (iteration为迭代步数)
* e0 `, ~/ Z8 X" h! v将 m个蚂蚁随机置于 n个顶点上 ;
, `: \& U& H2 LLoop:
将所有蚂蚁的初始出发点置于当前解集中 ;
for i← 0 to n-1 do
+ a' e  H* v) D, i8 Tfor k← 1 to m do
按概率 选择顶点 j;
! U7 W, p/ t, \4 u& i移动蚂蚁 k至顶点 j;
将顶点j置于蚂蚁k的当前解集</P>
<>end for
+ N; G( q+ o1 w! R" W3 \( L# W* f/ Pt←t＋1
end for
6 z5 i9 _8 l7 p( B8 F) K. ^计算各蚂蚁的 L个目标函数值
更新当前的理想解
" Y' |0 _3 l1 q( z, b& ]7 w计算各个解的满意度 </P>
<>置 t← t+1
' F3 k; C% M; ]6 t8 F; z" l重置所有 ← 0
iteration← iteration+1
  Y+ c; z8 N5 f- N5 j7 l若 iteration&lt;预定的迭代次数
则 goto Loop
输出目前的最满意解
7 Z! O2 X* c% z1 b' x6 iEnd</P>
& f2 {0 f) C/ B<>下面是蚂蚁算法解决TSP问题的C++程序：</P>
<DIV class=HtmlCode>
<>/* &gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;
AntColonySystemTSP.cc, Heiko Stamer </P>
3 V( j* d2 B+ }<>Ant Colony System (ACS) for the Traveling Salesman Problem (TSP) </P>
( Z; G; t1 Z0 Z. o+ F% O% X6 F<>[The Ant System: Optimization by a colony of cooperating agents]
by M. Dorigo, V. Maniezzo, A. Colorni
IEEE Transactions on Systems, Man and Cybernetics - Part B, Vol.26-1 1996 </P>
<>[Ant Colony System: A Cooperative Learning Approach to the TSP]
by M. Dorigo and L. M. Gambardella
5 K( w' U7 A! I3 s& f1 D* F& Z  `+ C& DIEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, 1997 </P>
<><a href="http://stinfwww.informatik.uni-leipzig.de/~mai97ixb" target="_blank" >http://stinfwww.informatik.uni-leipzig.de/~mai97ixb</A>
/ V4 |. @( w$ Z$ d* [&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt; </P>
* S  V& R( c/ [  g8 N<>Copyright (C) 2001 - until_the_end_of_the_ants </P>
+ Y3 O1 Z5 |$ `0 G% h<>This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
9 F/ \0 E% H4 c  l& \4 B(at your option) any later version. </P>
5 U+ B- _! [' G: e3 r# ], a8 d<>This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details. </P>
<>You should have received a copy of the GNU General Public License
) B0 e/ B; k3 X+ F" s6 s8 Oalong with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ </P>
<>#include
- e; B5 C$ [6 X, N#include
' c/ Q4 Y7 I6 Q+ ?2 k#include
#include
! a+ n. o1 N2 e( h- {#include
#include </P>
<>#define N 70 </P>
<>double C[N][2] = { {64 , 96} , {80 , 39} , {69 , 23} , {72 , 42} , {48 , 67} , {58 ,
0 ]( Y# t! s* l& F: G$ F' T43} , {81 , 34} , {79 , 17} , {30 , 23} , {42 , 67} , {7 , 76} , {29 , 51} , {78
- j$ C; A; O/ W: v, ]; W, 92} , {64 , 8} , {95 , 57} , {57 , 91} , {40 , 35} , {68 , 40} , {92 , 34} ,
' j- n6 j7 _# U1 X% h{62 , 1} , {28 , 43} , {76 , 73} , {67 , 88} , {93 , 54} , {6 , 8} , {87 , 18} ,
{30 , 9} , {77 , 13} , {78 , 94} , {55 , 3} , {82 , 88} , {73 , 28} , {20 , 55}
, {27 , 43} , {95 , 86} , {67 , 99} , {48 , 83} , {75 , 81} , {8 , 19} , {20 ,
) j: ^6 ]0 ?0 _2 `  U+ i$ L5 I18} , {54 , 38} , {63 , 36} , {44 , 33} , {52 , 18} , {12 , 13} , {25 , 5} , {58
7 Y9 ?- ~" P8 q% K, 85} , {5 , 67} , {90 , 9} , {41 , 76} , {25 , 76} , {37 , 64} , {56 , 63} ,
{10 , 55} , {98 , 7} , {16 , 74} , {89 , 60} , {48 , 82} , {81 , 76} , {29 , 60}
" S$ V: g' F4 I( i0 }/ N/ K6 A) Q, {17 , 22} , {5 , 45} , {79 , 70} , {9 , 100} , {17 , 82} , {74 , 67} , {10 ,
) O! U" V. S1 R9 n6 z% K& |68} , {48 , 19} , {83 , 86} , {84 , 94} }; </P>
: g' c3 k0 N6 c6 h# i  ]<>typedef int Tour[N][2];
typedef double doubleMatrix[N][N]; </P>
/ Y# F+ j" J" U3 d<>doubleMatrix D; </P>
+ g& k& x- w9 V$ f$ Z' Y% @<>double dist(int i, int j)
% b/ ^& c9 G  b1 t( J0 ~3 Q{
( y+ L( [" {* l- Dreturn sqrt(pow((C[0]-C[j][0]), 2.0) + pow((C[1]-C[j][1]), 2.0));
! A: V; s8 F% G5 l9 X! q} </P>
<>void calc_dist()
{
for (int i = 0; i &lt; N; i++)
for (int j = 0; j &lt; N; j++)
* n8 \7 o. T$ M6 l1 zD[j] = dist(i, j);
} </P>
& Q8 H/ `3 S$ q8 D<>double max_dist()
2 C7 {  s6 r4 Y  }# y: B{
8 S1 Y0 N- r, }' @double max_dist = 0.0;
% F) W# a& `+ |' q9 J! s$ O6 Tfor (int i = 0; i &lt; N; i++)
for (int j = 0; j &lt; N; j++)
5 ]0 C0 {6 L! T+ o. jif (dist(i, j) &gt; max_dist)
max_dist = dist(i, j);
return max_dist;
' A3 L) Z8 j2 F) j" B, G} </P>
<>double calc_length(Tour tour)
8 x1 L  O/ H+ u; H+ ]! y) h6 g{
double l = 0.0;
for (int n = 0; n &lt; N; n++)
  M5 O/ y/ g1 T$ B( o, g{
8 W" V# @( q& g1 z  v  c2 tint i = tour[n][0];
0 b7 f/ X5 z% q( v0 r' ^* E' }int j = tour[n][1];
: O' X! u( o- K9 ]9 L+ Z4 `" Fl += D[j];
3 M- G  _1 g! m) P& t+ c}
return (l);
& ?6 {" a  ], Y5 Z} </P>
8 `! E; ~, i: b9 G# `" W9 @. V<>void print_tour(Tour tour)
* U+ P( y* h$ w6 V% s" V5 s* w{
, [- R- Q& o% Q7 K! c( r: ]for (int n = 0; n &lt; N; n++)
printf("( %d , %d ) ", tour[n][0], tour[n][1]);
printf("\n");
} </P>
<>int sum_sequence(int array[], int count)
{
int sum = 0;
for (int i = 0; i &lt; count; i++)
sum += array;
" |# o4 k5 ]& W' h! o' d) Y. i  Breturn (sum);
} </P>
% k9 v5 @$ t' Y/ w4 c<>/******************************************************************************/ </P>
3 {$ u0 s1 V, Z( B<>class Ant
{
3 l+ }9 c& T2 O. I' o  G3 l! [protected:
int START_CITY, CURRENT_CITY;
int ALLOWED[N];
2 P$ s) t; Y1 j- C+ n6 {6 H+ ^Tour CURRENT_TOUR;
. z  u% R: b5 `4 ?: d# wint CURRENT_TOUR_INDEX;
public:
, B5 B3 a: }/ Hinline Ant(int start_city)
" }$ d7 p' C" Y" Z3 W{
START_CITY = start_city;
}
8 t, ?3 j) z4 tinline void moveTo(int to_city)
& p! q$ S% ]; R9 @{
% S' @/ s+ |# m7 c! QALLOWED[to_city] = 0;
- j; q4 T* y' G5 ?0 dCURRENT_TOUR[CURRENT_TOUR_INDEX][0] = CURRENT_CITY;
, R/ a  s* a6 I0 I& ACURRENT_TOUR[CURRENT_TOUR_INDEX][1] = to_city;
CURRENT_TOUR_INDEX++;
CURRENT_CITY = to_city;
}
}; </P>
<>class NNAnt : Ant
9 m: _! f6 F6 M) k* A6 ?{
4 r4 a3 Q2 \$ W1 ~  @5 t0 {- npublic:
inline NNAnt(int start_city): Ant(start_city) { };
+ e9 Z$ Q( D8 p, X# Minline int choose()
{
double best_length = (double)N * max_dist();
$ w% w6 B& `8 h5 E5 D* iint best_choose = -1; </P>
# r" w/ P- @2 I+ Y& Y; P<P>for (int j = 0; j &lt; N; j++)
  N3 y2 @! f6 h8 z{
" J( L7 ~+ u$ Oif ((ALLOWED[j] == 1) &amp;&amp; (D[CURRENT_CITY][j] &lt; best_length))
{
best_choose = j;
( e. s% a( w" |3 z! Xbest_length = D[CURRENT_CITY][j];
}
}
return best_choose;
}
2 l1 c4 H' Y) b1 J" N2 hinline Tour *search()
4 Y, @5 B- i! f{
CURRENT_CITY = START_CITY;
# K3 f$ ~% a' x  B0 _CURRENT_TOUR_INDEX = 0;
for (int i = 0; i &lt; N; i++)
ALLOWED = 1;
ALLOWED[CURRENT_CITY] = 0;
: H# `4 ?" k  M5 |) Fwhile (sum_sequence(ALLOWED, N) &gt; 0)
moveTo(choose());
ALLOWED[START_CITY] = 1;
) @1 L: k# z2 b2 `* L; VmoveTo(START_CITY);
return &amp;CURRENT_TOUR;
}
}; </P>
<P>class AntColonySystem;
& t# h! v) n/ T4 E( e9 Iclass ACSAnt : Ant
2 b/ Z; y! @( r1 a9 H{
+ A# ^9 K2 X. I1 V) y! t# eprivate:
7 _' F  W- u( k* f% ~) }3 S" nAntColonySystem *ACS;
public:
0 M' {/ y4 p+ R- `$ |ACSAnt(AntColonySystem *acs, int start_city): Ant(start_city)
/ u4 B% L- F+ }8 Q{
ACS = acs;
0 J/ K: N2 \. C0 F% X}
; ]3 X  k; L5 I- W3 H4 _inline int choose();
inline Tour *search();
}; </P>
<P>class AntColonySystem
{
# C% E% m5 ?9 mprivate:
& F. X1 L4 m1 e5 _$ adouble ALPHA, BETA, RHO, TAU0;
doubleMatrix TAU, dTAU;
static const int M = 420;
ACSAnt *ANTS[M]; </P>
& N0 s$ [; g3 P) |* N7 z* ?<P>public:
- \1 }% A% ?$ V3 ~" K/ A  ]double Q0;
3 A) x6 _4 `, c! b6 P8 ZAntColonySystem(double alpha, double beta, double rho, double q0);
inline double calc_tau0();
5 Q  B0 J8 Z. Y  ^- l% Yinline void init_tau_by_value(double value);
6 L! O! J; Y  o2 S" q' K5 K) Q% [) @inline void init_tau_by_matrix(doubleMatrix matrix);
2 o$ D3 Z) J. M% [inline void init_uniform();
inline void init_random();
inline void init_randomMOAPC();
inline double ETA(int i, int j);
: W# D5 O# @- b' _. O' h3 ginline double transition(int i, int j);
# f7 ~" V) f5 P, P* ?4 b4 [inline double sum_transition(int i, int allowed[]);
2 T& H3 B9 R- M4 D, e; xinline void local_update_rule(int i, int j);
inline void clear_global_update();
  x; o" z0 u: `( E9 j# T4 t1 F2 \! ~inline void add_global_update(Tour tour, double length);
) E, f% d" P2 N9 c8 f1 B5 i5 Rinline void global_update_rule();
, C& T' h' F' N; d7 M+ Q8 R5 Xinline doubleMatrix *get_tau();
( l1 r# U: q1 ?inline Tour *search(int T);
9 s3 U: b) Y8 [; w5 U}; </P>
$ q* w( v2 q! h6 p<P>inline int ACSAnt::choose()
{
; b4 [4 T( v6 _% [/ xdouble q = rand() / (double)RAND_MAX; </P>
<P>if (q &lt;= ACS-&gt;Q0)
) [* p: ]' g9 @# b& [  @{
double best_value = -1.0;
int best_choose = -1;
: o+ V0 u- R, ?, Q( U. \) afor (int j = 0; j &lt; N; j++)
{
0 I; d: g% ~. {6 G$ e* {if ((ALLOWED[j] == 1) &amp;&amp;
! H6 K  Y2 U7 L  {! n(ACS-&gt;transition(CURRENT_CITY, j) &gt; best_value))
/ X( u  R+ k+ y8 ?7 h% X# D7 C9 O{
- I$ P- |5 N9 e# Jbest_choose = j;
best_value = ACS-&gt;transition(CURRENT_CITY, j);
}
}
$ L) b1 p9 ]& E% ereturn best_choose;
} </P>
<P>double sum = ACS-&gt;sum_transition(CURRENT_CITY, ALLOWED);
* ^. ~: \& s' [$ m' z3 h7 V3 ndouble p = rand() / (double)RAND_MAX;
. X) o) N4 y9 ^1 rdouble p_j = 0.0; </P>
2 Y% t5 u; j9 F! n: X4 K& [. f<P>for (int j = 0; j &lt; N; j++)
{
if (ALLOWED[j] == 1) p_j += ACS-&gt;transition(CURRENT_CITY, j) / sum;
if ((p &lt; p_j) &amp;&amp; (ALLOWED[j] == 1))
. q, X( k& T3 k! Sreturn j;
}
return -1;
& D# g& @1 l; q( f} </P>
' E  ^. k8 ~$ S, \<P>inline Tour *ACSAnt::search()
{
CURRENT_CITY = START_CITY;
. e' M  D8 a) l4 d2 s. d0 DCURRENT_TOUR_INDEX = 0;
5 k+ K/ B! X: X3 V1 ~  q5 }for (int i = 0; i &lt; N; i++)
7 l4 ~! r7 ~9 LALLOWED = 1;
+ q0 {; C7 @& U5 [9 u! I/ m0 ~6 OALLOWED[CURRENT_CITY] = 0;
while (sum_sequence(ALLOWED, N) &gt; 0)
{
( n7 b: u& S, {- |; h( }int LAST_CITY = CURRENT_CITY;
moveTo(choose());
ACS-&gt;local_update_rule(LAST_CITY, CURRENT_CITY);
}
ALLOWED[START_CITY] = 1;
- Y1 R, M' c* r% ^' f( g4 bACS-&gt;local_update_rule(CURRENT_CITY, START_CITY);
. ?& _+ H; Q4 \" n4 MmoveTo(START_CITY);
! w5 Q2 {+ @) H4 Ureturn &amp;CURRENT_TOUR;
: ^. o, x* ~, S5 c! E} </P>
<P>/******************************************************************************/ </P>
" y# V4 X3 H) H; \/ o. @<P>AntColonySystem::AntColonySystem(double alpha, double beta, double rho, double q0)
{
ALPHA = alpha;
& h1 V1 w; D9 u% U, ^) E' M& ~- mBETA = beta;
RHO = rho;
Q0 = q0;
- x, f7 J" N; e3 f} </P>
+ e# o9 w! e9 m  A<P>inline double AntColonySystem::calc_tau0()
3 T" N) t+ E8 P2 T, q/ L{
double best_length = (double)N * max_dist(); </P>
% A- ?1 j; J6 x7 M<P>for (int n = 0; n &lt; N; n++)
; y# j. q7 B- u; ^+ C- j{
NNAnt *nnANT = new NNAnt(n);
6 h' i8 b5 I2 Z; eTour tour;
tour = *(nnANT-&gt;search());
" y) G2 x9 m" j5 ~8 J: z* U- o1 s$ fdouble tour_length = calc_length(tour);
if (tour_length &lt; best_length)
best_length = tour_length;
delete nnANT;
}
; i$ y9 X6 n1 R9 b3 zreturn 1.0 / ((double)N * best_length);
} </P>
<P>inline void AntColonySystem::init_tau_by_value(double value)
6 d# X5 n9 v# i2 s/ c  L/ I, ?# |2 O{
TAU0 = value;
for (int i = 0; i &lt; N; i++)
  i* j7 e5 m9 R$ I, y0 |for (int j = 0; j &lt; N; j++)
TAU[j] = TAU0;
3 k/ d2 W! U! E2 Y. `} </P>
( C; `3 g" A% _3 f8 v" P<P>inline void AntColonySystem::init_tau_by_matrix(doubleMatrix matrix)
5 d+ F0 B% K# K, d' @2 r; d0 y{
5 i9 Q; ?' ?/ x% o* b6 s# j( k( Ufor (int i = 0; i &lt; N; i++)
for (int j = 0; j &lt; N; j++)
TAU[j] = matrix[j];
} </P>
<P>inline void AntColonySystem::init_uniform()
{
// uniformly distributed
5 s/ R. f  _/ I  E/ L1 c; Ifor (int k = 0; k &lt; M; k++)
ANTS[k] = new ACSAnt(this, (k % N));
} </P>
<P>inline void AntColonySystem::init_random()
{
// randomly distributed
& W7 c9 n  U9 S0 Ufor (int k = 0; k &lt; M; k++)
7 q5 f$ L) \2 E- fANTS[k] = new ACSAnt(this, (int)((double)N * (rand() / (double)RAND_MAX)));
9 f  {* P& K/ ~% Z3 q! u} </P>
7 }0 @0 V( r- v/ k4 R* z. n" `<P>inline void AntColonySystem::init_randomMOAPC()
{
# D5 O% k( H% y7 z// randomly distributed with MOAPC (most one ant per city)
: t  y8 F5 a/ D; k+ ?bool MOAPCarray[N];
/ b" J1 j+ _+ n" s+ g& Lassert(M &lt;= N); </P>
& d9 Y) @- T! M3 s<P>for (int n = 0; n &lt; N; n++)
MOAPCarray[n] = false; </P>
, h/ l- j' G8 U/ S<P>for (int k = 0; k &lt; M; k++)
{
5 |9 V0 m8 W4 i% V' ]: cint c;
do
8 i1 X- ?; v2 H5 |' x% b{
c = (int)((double)N * (rand() / (double)RAND_MAX));
8 d% l: x8 [9 x: Z+ l}
) T6 A9 O& ]# r- b5 _4 Gwhile (MOAPCarray[c]); </P>
<P>MOAPCarray[c] = true;
ANTS[k] = new ACSAnt(this, c);
}
* z- T' M! j& B9 h/ B} </P>
<P>inline double AntColonySystem::ETA(int i, int j)
{
2 d- x: W) I' X7 z4 Yreturn ( 1.0 / D[j] );
  L* v, C6 J$ @' r) K} </P>
<P>inline double AntColonySystem::transition(int i, int j)
{
if (i != j)
return ( TAU[j] * pow( ETA(i, j), BETA ) );
" L; R; J7 q* \7 I1 s8 `else
( P# Y9 f9 z% G+ O. z% k: |return(0.0);
3 S$ V, ?. d! w8 W, x} </P>
<P>inline double AntColonySystem::sum_transition(int i, int allowed[])
{
, S3 W1 x  D  x# I2 I3 z9 ddouble sum = 0.0;
+ ^8 w) A; {0 E- hfor (int j = 0; j &lt; N; j++)
sum += ((double)allowed[j] * transition(i, j));
" C( x/ G: {2 O& w0 ]1 Xreturn (sum);
9 J( l; g; R5 t. K$ x7 [} </P>
7 Z6 S1 Y) a6 g/ N8 p% a# g4 i<P>inline void AntColonySystem::local_update_rule(int i, int j)
0 n7 M' m6 q4 R* h2 P{
TAU[j] = (1.0 - RHO) * TAU[j] + RHO * TAU0;
// symmetric TSP
0 P; c& ]' S/ x, U* J7 \8 y4 ^TAU[j] = TAU[j];
, r) f! A5 e  X% m% `% p+ y; S- z} </P>
<P>inline void AntColonySystem::clear_global_update()
. D% w+ v. D* g" u: Q{
for (int i = 0; i &lt; N; i++)
for (int j = 0; j &lt; N; j++)
dTAU[j] = 0.0;
} </P>
<P>
  W2 U2 n. O1 b; L# hinline void AntColonySystem::add_global_update(Tour tour, double length)
{
7 i+ Y$ Q6 ]9 P- }4 X# pfor (int n = 0; n &lt; N; n++)
{
0 @' C& ?2 C" {4 j. W# mint i = tour[n][0];
int j = tour[n][1];
8 |. U3 X: x4 b+ W5 RdTAU[j] += (1.0 / length);
8 g8 W7 D, L, c$ Q// symmetric TSP
" d4 }4 m3 d7 Y$ hdTAU[j] += (1.0 / length);
$ X5 {3 @) u4 P7 }}
/ j4 c/ [+ s$ h6 N} </P>
* @- p: ]2 k( W& d<P>inline void AntColonySystem::global_update_rule()
! T, m' }4 _* J( ]- b{
# |1 T7 v6 b2 i) Ufor (int i = 0; i &lt; N; i++)
for (int j = 0; j &lt; N; j++)
" V; S# N1 \: H& Q. U* v% i# y" z$ kTAU[j] = (1.0 - ALPHA) * TAU[j] + ALPHA * dTAU[j];
6 G; S9 h2 w4 y' I, [$ B} </P>
: }7 ]" z5 O" B<P>inline doubleMatrix *AntColonySystem::get_tau()
{
return &amp;TAU;
} </P>
<P>inline Tour *AntColonySystem::search(int T)
{
Tour best_tour, tour;
double best_length = (double)N * max_dist(), tour_length;
6 _6 O0 E6 s& a1 Uclear_global_update(); </P>
/ N4 X+ v; E& t3 i7 _<P>// do T iterations of ACS algorithm
' `8 e  T* I/ b$ Rint t;
) \+ z5 G( W& R' S" g8 c2 Ufor (t = 0; t &lt; T; t++)
{
% L3 G, {: m+ f0 y' R3 j+ Rfor (int k = 0; k &lt; M; k++)
* {4 Z- m: s) K2 m  V$ d( Y1 _( o6 L{
! R) g) q+ ~. z# r& ntour = *(ANTS[k]-&gt;search());
  x+ \/ ]2 m$ w- u! _tour_length = calc_length(tour);
) }9 B  O; f! d  tif (tour_length &lt; best_length)
{
best_tour = tour;
best_length = tour_length;
clear_global_update();
( {9 N) s" R5 b) N* ^; M; Wadd_global_update(tour, tour_length);
+ V$ l* Y+ _/ J( j- s) w//printf("[%d / %d]: %lf \n", t, T, tour_length);
}
" v1 g: n9 a1 w; [0 s+ `}
global_update_rule();
; o8 O( E- R! }% y% x7 V) `; ], B# R$ S} </P>
& d, @7 u' F4 h. U  v2 A<P>//printf("[%d/%d] best tour (length = %f):\n", t, T, best_length);
//print_tour(best_tour);
//printf("[%d/%d] iterations done\n", t, T);
printf("%f\n", best_length);
return (&amp;best_tour);
} </P>
<P>int main(int argc, char* argv[])
{
// PRNG initalisieren
  U9 {) c3 _9 \- b  B3 btime_t timer;
; w9 d9 \8 F" f- D* I+ W* Itime(&amp;timer);
pid_t pid = getpid() + getppid();
unsigned long seed = (timer * pid);
if (seed == 0)
{
time(&amp;timer);
seed = 7 * timer * pid;
( m7 n6 X- }! ^; L9 |, }% Kif (seed == 0) seed = pid; else seed = seed % 56000;
& y" @" ^4 I8 X3 ?} else seed = seed % 56000;
srand((unsigned int)seed); </P>
$ v; p  A+ U! ]: R) I<P>// EUC2D
& H# a/ h0 [% E$ W- Ccalc_dist(); </P>
* n  w1 ^6 t3 s$ L0 q' s' r0 w/ {: G<P>// Ant Colony System
. i0 F2 N5 z& cAntColonySystem *acs = new AntColonySystem(0.1, 2.0, 0.1, 0.9);
double tau0 = acs-&gt;calc_tau0();
1 s% C/ O/ U$ G" `) [3 aacs-&gt;init_tau_by_value(tau0);
' ^: u. f& b. V' [4 ^acs-&gt;init_uniform();
acs-&gt;search(1000); </P>
<P>return(0);
% S- W. W7 \$ [# T4 M0 e& k} </P></DIV>

0 J5 g$ }" W6 ^% ?7 ~8 x& c% O<P>蚂蚁算法的一些文献：</P>
<P>
</P>

helen

感谢共享!!,不过这样传上来看着不是很方便.不过还是非常感谢共享你的资源!!

高巡

多谢楼主,对我帮助很大.

xiaoyueryfq

谢谢楼主！！！

zhouming09

<font size="5">谢谢楼主！！！谢谢楼主！！！</font>

zhouming09

<div>好</div>

zhouming09

<a href="http://www.madio.net/bbs/dispbbs.asp?BoardID=107&amp;ID=4088&amp;replyID=32632&amp;skin=1"><font color="#000000" size="+0">多谢楼主,对我帮助很大.</font></a>