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

ilikenba

<>模拟退火算法
1 \$ h# w7 x  L" K. T$ M/ h　　模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，</P>
  {# l, l! y, K+ I. U, F<>内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis</P>
/ n: A8 G7 `$ z<>准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退</P>
<>火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始</P>
) g5 R. {& t+ Y6 `" Q<>解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的</P>
<>当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling </P>
  }$ t8 j3 p/ Y! i<>Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
3.5.1 模拟退火算法的模型
　　模拟退火算法可以分解为解空间、目标函数和初始解三部分。
- p8 N% L* I8 B! @& K/ \3 W2 j　模拟退火的基本思想:
　　(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L
　　(2) 对k=1，……，L做第(3)至第6步：
　　(3) 产生新解S′
& W2 ]" K, i* H" j0 ]# [& Q　　(4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数
# E2 |/ Z$ m7 {" q　　(5) 若Δt′&lt;0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.
　　(6) 如果满足终止条件则输出当前解作为最优解，结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法。
　　(7) T逐渐减少，且T-&gt;0，然后转第2步。
; H$ k! b& Z! x算法对应动态演示图：
1 n4 j& K8 X1 l# Q, s/ S模拟退火算法新解的产生和接受可分为如下四个步骤：
8 b! c& w6 ~) F+ l- a9 {4 l　　第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当</P>
8 ~8 r# T. t5 o7 Y0 K- L<>前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法</P>
9 A: l+ J- d( C; T7 Z" S& `" P<>决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
& B0 T' G7 p" ~9 r# H" |　　第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。</P>
<>事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
　　第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若Δt′&lt;0则接受S′作</P>
<>为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。
4 \/ e- Q' l2 n9 ~$ V" z　　第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正</P>
: T4 J, ?- X  |% w% @<>目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的</P>
<>基础上继续下一轮试验。
; u% p# `; r" o; @　　模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在</P>
<>理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。 </P>
<>3.5.2 模拟退火算法的简单应用
, ]/ r( V" V, X1 B6 [7 C( Q　　作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem，简记为TSP)：设有n个城市，用数码1,…,n代表</P>
<>。城市i和城市j之间的距离为d(i，j) i, j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最</P>
<>短.。
　　求解TSP的模拟退火算法模型可描述如下：
! U: S4 m; `9 {9 k, R: W　　解空间 解空间S是遍访每个城市恰好一次的所有回路，是{1，……，n}的所有循环排列的集合，S中的成员记为(w1,w2 ,…</P>
<>…，wn)，并记wn+1= w1。初始解可选为(1，……，n)
7 g. C. r, W5 J; }$ K; C* Y　　目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数： </P>
<>　　我们要求此代价函数的最小值。
$ s# u" V3 `5 }- V　　新解的产生 随机产生1和n之间的两相异数k和m，若k&lt;m，则将
　　(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
　　变为：
　　(w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn).
　　如果是k&gt;m，则将
  J: e9 q0 a& R; @* B+ z" @　　(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
# F& w: z9 T) r" t1 @& v8 ]　　变为：
　　(wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk).
　　上述变换方法可简单说成是“逆转中间或者逆转两端”。
# M' W+ J- r5 H# ~　　也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。
　　代价函数差 设将(w1, w2 ,……，wn)变换为(u1, u2 ,……，un), 则代价函数差为： </P>
) j7 e) y/ q8 a* n# v2 Q<>根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序：
1 J+ P* h6 u8 v: J$ A# PProcedure TSPSA:
　begin
- K) @$ ?6 C/ e4 Q/ P, d　　init-of-T; { T为初始温度}
. k( c  F- H/ Z+ w, R; b　　S={1，……，n}; {S为初始值}
, [: }; ^- l" I/ n4 w+ N　　termination=false;
" |. R* F! V9 L+ k　　while termination=false
1 i+ T& P- _, k9 s& K　　　begin
, f) v& U6 e' g; x5 `) P$ u　　　　for i=1 to L do
' k8 Y  ]1 l0 j1 S7 l0 M　　　　　　begin
　　　　　　　　generate(S′form S); { 从当前回路S产生新回路S′}
　　　　　　　　Δt:=f(S′))-f(S);{f(S)为路径总长}
" b. O( w  @! Z- [: |. e$ U& }$ x　　　　　　　　IF(Δt&lt;0) OR (EXP(-Δt/T)&gt;Random-of-[0,1])
　　　　　　　　S=S′;
% `. F2 |4 c" ]4 c' p6 t! D# W　　　　　　　　IF the-halt-condition-is-TRUE THEN
; Y3 R5 v% C' j# A. V　　　　　　　　termination=true;
　　　　　　End;
　　　　T_lower;
# S  ~, Y! X- h　　　End;
9 t+ C. B0 t9 b9 E# p　End
　　模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack </P>
+ R- C; @0 i3 P" a  T<>roblem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。 </P>
' o( i- v' e1 O- h$ |# k<>3.5.3 模拟退火算法的参数控制问题
" a3 ]) z2 C; \% t, _8 d　　模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：
7 k+ J" [4 f3 L, T; [1 c/ i' ]　　(1) 温度T的初始值设置问题。
　　温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但</P>
<>因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要</P>
1 l9 k/ }1 P: W$ y) \<>依据实验结果进行若干次调整。
　　(2) 退火速度问题。
# n3 F* c% B2 R. f4 p( A　　模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这</P>
8 u: c0 W, O) o4 E! j<>需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
　　(3) 温度管理问题。
　　温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采</P>
8 N/ b( I& a$ T1 m9 W9 d<>用如下所示的降温方式： </P>
9 m( X0 y8 c! m1 p( F<>T(t+1)＝k×T(t)
8 o' Q8 q, z2 \; w6 K5 h式中k为正的略小于1.00的常数，t为降温的次数 </P>
2 S! @# M6 R7 ]& h# X- w% A<>使用SA解决TSP问题的Matlab程序：</P>
4 R! m1 J4 ?6 S+ j<DIV class=HtmlCode>
) z( x% T& M( ^6 _* y<>function out = tsp(loc)
% TSP Traveling salesman problem (TSP) using SA (simulated annealing).
% TSP by itself will generate 20 cities within a unit cube and
# k) L' g% O# v  H2 O7 X% then use SA to slove this problem.
%
2 \6 @/ a" a7 \% TSP(LOC) solve the traveling salesman problem with cities'
" s9 H: X% R) A: t* I2 @6 O, ^  O  ]% coordinates given by LOC, which is an M by 2 matrix and M is
% the number of cities.
%
% For example:
%
4 S( Z. ]* I2 j% {% loc = rand(50, 2);
% tsp(loc);
) U8 [) p7 k& @4 y* Gif nargin == 0,
% The following data is from the post by Jennifer Myers (<a href="mailtjmyers@nwu" target="_blank" >jmyers@nwu</A>.
% `3 J! C$ B8 G( C% xedu)
6 I" P" w1 ]. E' j, hedu)
8 D' ^. a1 ^( e4 S+ k% to comp.ai.neural-nets. It's obtained from the figure in
6 y/ a5 Z1 x5 m% s, t% Hopfield &amp; Tank's 1985 paper in Biological Cybernetics
% (Vol 52, pp. 141-152).
+ S5 r3 n( o3 K& a! Xloc = [0.3663, 0.9076; 0.7459, 0.8713; 0.4521, 0.8465;
0.7624, 0.7459; 0.7096, 0.7228; 0.0710, 0.7426;
! |3 o+ c; M$ h% R6 X! m8 t9 I0.4224, 0.7129; 0.5908, 0.6931; 0.3201, 0.6403;
0.5974, 0.6436; 0.3630, 0.5908; 0.6700, 0.5908;
; \4 ]7 i6 `7 |! K, G: A0 V0.6172, 0.5495; 0.6667, 0.5446; 0.1980, 0.4686;
0.3498, 0.4488; 0.2673, 0.4274; 0.9439, 0.4208;
  M8 r  V: x- y5 s. A4 K0.8218, 0.3795; 0.3729, 0.2690; 0.6073, 0.2640;
% A' t& ~0 ]/ t6 S& ]9 i0.4158, 0.2475; 0.5990, 0.2261; 0.3927, 0.1947;
0.5347, 0.1898; 0.3960, 0.1320; 0.6287, 0.0842;
5 E5 B  v# V4 ?; l% B8 h# y: Y# |8 V0 F0.5000, 0.0396; 0.9802, 0.0182; 0.6832, 0.8515];
( a# a- m" F) c) r4 Hend
) @( {! r  `0 \! d( R' M, }: O$ wNumCity = length(loc); % Number of cities
distance = zeros(NumCity); % Initialize a distance matrix
% Fill the distance matrix
for i = 1:NumCity,
, m0 T; Y* |- r; y6 O! ?# T* afor j = 1:NumCity,
" S: ]- [3 ?/ ydistance(i, j) = norm(loc(i, - loc(j, );
distance(i, j) = norm(loc(i, - loc(j, );
, u! z8 H" E4 `( X6 {; q7 mend
- Q4 Z- J! d5 B8 [2 l) Wend
: u1 }) g; ^* u" n$ z% To generate energy (objective function) from path
%path = randperm(NumCity);
%energy = sum(distance((path-1)*NumCity + [path(2:NumCity) path(1)]));
  L6 c* W& x( n, ~9 R0 g; ?, B* K) ~' E% Find typical values of dE
- r. u9 r6 ]' \8 E) d3 f$ Ncount = 20;
3 i; G) [' }$ lall_dE = zeros(count, 1);
$ ]$ e# U9 f: Z; V3 Lfor i = 1:count
path = randperm(NumCity);
energy = sum(distance((path-1)*NumCity + [path(2:NumCity)
path(1)]));
* c* t3 O- M/ ~" jnew_path = path;
) N- l: Z" Z6 Zindex = round(rand(2,1)*NumCity+.5);
inversion_index = (min(index):max(index));
* M: v2 ^4 A, I- ?new_path(inversion_index) = fliplr(path(inversion_index));
" `' \/ T( o2 E8 k& g0 h  vall_dE(i) = abs(energy - ...
sum(sum(diff(loc([new_path new_path(1)],)'.^2)));
end
dE = max(all_dE);
% Z. C9 A1 }; H, H6 ddE = max(all_dE);
temp = 10*dE; % Choose the temperature to be large enough
fprintf('Initial energy = %f\n\n',energy);
% Initial plots
out = [path path(1)];
4 u1 `: x, c( f4 jplot(loc(out(, 1), loc(out(, 2),'r.', 'Markersize', 20);
" @# G9 x% R' m" C3 |# Naxis square; hold on
h = plot(loc(out(, 1), loc(out(, 2)); hold off
5 }0 x9 m( Z0 N4 X  V+ dMaxTrialN = NumCity*100; % Max. # of trials at a
7 S! b+ @1 o% J8 ^0 m* W; z* t1 ptemperature
MaxAcceptN = NumCity*10; % Max. # of acceptances at a
' n# s/ a$ U7 M- Ctemperature
StopTolerance = 0.005; % Stopping tolerance
; d1 w* G6 R1 D' D8 [) @% l) ZTempRatio = 0.5; % Temperature decrease ratio
) \' r' h' Z, `* ~3 D$ n: SminE = inf; % Initial value for min. energy
maxE = -1; % Initial value for max. energy
% Major annealing loop
while (maxE - minE)/maxE &gt; StopTolerance,
minE = inf;
minE = inf;
maxE = 0;
: Y  K* O6 {' g' P( I9 GTrialN = 0; % Number of trial moves
AcceptN = 0; % Number of actual moves
+ L/ t' x/ @& `  U9 zwhile TrialN &lt; MaxTrialN &amp; AcceptN &lt; MaxAcceptN,
) t6 m/ Y$ u4 m. rnew_path = path;
index = round(rand(2,1)*NumCity+.5);
inversion_index = (min(index):max(index));
6 X; ~, t7 E* W8 C8 tnew_path(inversion_index) =
fliplr(path(inversion_index));
new_energy = sum(distance( ...
(new_path-1)*NumCity+[new_path(2:NumCity)
' u( a' w- j% P+ C# Knew_path(1)]));
# {5 F. D! w$ F+ v/ K) i  ^; Oif rand &lt; exp((energy - new_energy)/temp), %
; x" h( E) @# N- i4 U3 g' \accept
$ K7 u; l8 h6 W) G1 o( Z: Y  z* Tit!
energy = new_energy;
/ H  s3 v  I3 `path = new_path;
8 j4 _# `' k, t- I6 @. [minE = min(minE, energy);
4 h) H4 X! k( {8 ~0 [  f& R2 k. h, {maxE = max(maxE, energy);
4 @: x$ O8 ~8 n* b, c, qAcceptN = AcceptN + 1;
6 K5 ^; k9 M; [end
TrialN = TrialN + 1;
& j( X1 [* u$ F7 x/ _( Pend
$ U4 B9 a6 X( C$ l6 w) H) Z0 Oend
' q( e9 a) E/ D1 A: ^7 G  y% Update plot
out = [path path(1)];
0 X) N% ^- n- z7 D/ F* n1 Pset(h, 'xdata', loc(out(, 1), 'ydata', loc(out(, 2));
" M5 s! I  C$ j0 G$ X; D( Wdrawnow;
% Print information in command window
fprintf('temp. = %f\n', temp);
tmp = sprintf('%d ',path);
" ?' d/ v% ~; s1 M3 @fprintf('path = %s\n', tmp);
fprintf('energy = %f\n', energy);
fprintf('[minE maxE] = [%f %f]\n', minE, maxE);
fprintf('[AcceptN TrialN] = [%d %d]\n\n', AcceptN, TrialN);
% Lower the temperature
temp = temp*TempRatio;
end
% Print sequential numbers in the graphic window
6 I9 z& q3 O+ v1 b( B/ ~for i = 1:NumCity,
0 n2 @% U$ u0 O) o8 D. ltext(loc(path(i),1)+0.01, loc(path(i),2)+0.01, int2str(i), ...
'fontsize', 8);
end </P></DIV>
' i9 Y4 f- `0 g# @$ y, b<P>又一个相关的Matlab程序</P>
* L4 U% H% v- }7 ~  o) b<DIV class=HtmlCode>
<P>function[X,P]=zkp(w,c,M,t0,tf)
[m,n]=size(w);
L=100*n;
t=t0;
+ y2 H) D1 a/ i7 Jclear m;
1 u1 L+ F" A& n9 ?3 gx=zeros(1,n)
xmax=x;
  f2 \1 m% T7 }. Y$ b5 Zfmax=0;
' b: M! p# h% D8 g# r  o6 cwhile t&gt;tf
for k=1
xr=change(x)
gx=g_0_1(w,x);
gxr=g_0_1(w,xr);
if gxr&lt;=M
# o- a$ \: L4 }: b% bfr=f_0_1(xr,c);
0 X& D+ I& v; l+ Jf=f_0_1(x,c);
  {; I% n/ K' Q% S0 Z. ?, Fdf=fr-f;
if df&gt;0
x=xr;
if fr&gt;fmax
fmax=fr;
xmax=xr;
; E! |' q/ Z$ gend
4 L1 x4 X8 g. ]/ W/ ]else
p=rand;
if p&lt;exp(df/t)
7 N  |+ g1 u) s0 W! M7 H1 }) Fx=xr;
8 ?. n* d/ ~8 v3 g! Xend
& c9 t2 M; w/ M: ^) V+ J! iend
end
end
t=0.87*t
end
* A) o  R- z. f! M% EP=fmax;
+ }) \) o) O) J1 p6 lX=xmax;
%下面的函数产生新解
* U/ H/ r$ I/ Q) r0 `7 I" U  jfunction [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
1 `8 |6 I3 v) u6 Y/ j6 Iclear m;
u=rand;
u=u*(n-2);
u=round(u);
if u&lt;2
u=2;
( x7 Z/ E& x4 m% D" i6 tend
if u&gt;n-2
u=n-2;
end
v=rand;
v=v*(n-u+1);
v=round(v);
# M3 J0 [0 V. P" K0 M5 I' ]% vif v&lt;1
v=1;
end
v=v+u;
if v&gt;n
+ q$ z- F8 i/ [" _: Gv=n;
; `, z8 j0 W9 v: X  rend
pi_1(u)=pi0(v);
pi_1(u)=pi0(u);
if u&gt;1
for k=1u-1)
pi_1(k)=pi0(k);
end
end
. N1 H0 w- ]$ H5 Z" T6 s8 Dif v&gt;(u+1)
# [( J$ P) E; Y! {. S# |( b) a( |for k=1v-u-1)
% _4 b5 W- D  w  l, f* F" ?- I- Epi_1(u+k)=pi0(v-k);
end
end
) U( E. f% @9 ]$ ?0 @  n, M, uif v&lt;n
* P  J! V0 f- T* I) {for k=(v+1):n
' W! J) O7 r$ T  P( e9 Hpi_1(k)=pi0(k);
1 C& q! E3 L. c# oend
8 _  U9 a# ~4 L. a! \" Yend
d_f=0;
if v&lt;n
) {% d% u% k5 w2 l5 Wd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
. {) g/ c/ i! m& ud_f=d_f+d(pi0(k),pi0(k-1))-d(pi0(v),pi0(v+1));
end
d_f=d_f-d(pi0(u-1),pi0(u));
3 s4 o" w& g: E# j# g* [for k=(u+1):n
& X9 B# O4 ~& d/ ?! }  i* Gd_f=d_f-d(pi0(k-1),pi0(k));
end
  s8 v; u4 m9 B' P# M* ~else
& X; T" B* ?1 T( N9 Dd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
6 d9 B! j5 Y, Efor k=(u+1):n
" n) _: R+ A6 b* h# ]d_f=d_f-d(pi0(k),pi0(k-1));
end
1 ]! D; B' z; c, }- r; w5 e+ S7 Gfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
& [* E6 ]% c; aend
; w6 x# b4 }( e: B/ r. kend
pi_r=pi_1; </P></DIV>

ilikenba

<>遗传算法：</P>
<>旅行商问题(traveling saleman problem,简称tsp)：
. K5 E+ c- j- [$ p# D' g已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？
5 N& k. N4 L3 N0 b" i+ G1 H$ l( z+ h用图论的术语来说，假设有一个图 g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。
. |7 ~2 F6 \" x* P; H4 y5 I9 V& u这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商问题(dij≠dji,,任意i,j=1,2,3，…,n)。
若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中ti∈v(i=1,2,3,…,n)，且记tn+1= t1，则旅行商问题的数学模型为：
min l=σd(t(i),t(i+1)) （i=1,…,n）
7 O" l8 G% O5 U" S6 ~" Q) N旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。
, o! g1 u' E# s) ^* p7 B遗传算法：
初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。
8 M! L# Q2 J1 c( \+ a) P  J/ i适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)).
% F/ r) I+ b( Y& Z0 ~评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=alpha*(1-alpha).^(i-1) 。[随机规划与模糊规划]
选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。
5 ], }- D, u5 P3 O( s# wstep1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1,…pop-size.
" p+ U' s# k% A" q7 w9 Gstep2、从区间(0,pop-size)中产生一个随机数r；
step3、若qi-1&lt;r&lt;qi,则选择第i个染色体 ；
- X, C. j/ j' @' n( l, X4 Y6 \step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。
8 |) {* ^1 v" [- D5 ^* X% Q$ ygrefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如：
- a* }" i' J  `7 l5 `8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1
对应：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。
6 a  L; w: j: d& ~2 S交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从 到pop-size重复以下过程：从[0，1]中产生一个随机数r，如果r&lt;pc ，则选择vi作为一个父代。
9 j7 r; w% A( X& O( E" Y将所选的父代两两组队，随机产生一个位置进行交叉，如：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
+ M8 d8 L' l& s6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1
( E2 |& Y- F6 D4 m3 _! p$ @0 M5 Z4 \交叉后为：
& Y8 w9 o& q4 B* I5 B( D8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1
8 v  X- I# ]! a6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1
* s/ H  w; ?- a  X% x& t变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在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
变异后：
# {7 p1 G( T& `8 j2 i. S8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1
0 g! N4 ?$ G) s4 q( X反grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。
3 B& Q& h& K$ a循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传操作，跳出。</P>
<>Matlab程序：</P>
) w& @" M/ x  S<DIV class=HtmlCode>
6 h3 I  N7 n* Y8 G! ~8 z<>function [bestpop,trace]=ga(d,termops,num,pc,cxops,pm,alpha)
6 T0 E- Z9 ^1 Q  o5 n%
! U* J5 o& v' y%————————————————————————
1 M( \+ w5 j% S%[bestpop,trace]=ga(d,termops,num,pc,cxops,pm,alpha)
%d:距离矩阵
9 _/ f! D! E+ w, P3 p; |# R%termops:种群代数
%num:每代染色体的个数
  g5 o$ t/ }% W0 V/ W%pc:交叉概率
) z4 z3 y* E) H1 \# O% t& h%cxops:由于本程序采用单点交叉，交叉点的设置在本程序中没有很好的解决，所以本文了采用定点，即第cxops，可以随机产生。
%pm:变异概率
2 F" i$ {$ P1 H, J%alpha:评价函数eval(vi)=alpha*(1-alpha).^(i-1).
2 G* N( l% K" s; ^0 ?%bestpop:返回的最优种群
# s3 \% ]. k$ c* D- w3 @%trace:进化轨迹
) c8 o; m1 U$ J: G) ?5 s, z5 p/ R%------------------------------------------------
%####@@@##版权所有！欢迎广大网友改正，改进！##@@@####
; m) y. A, }" I1 y# @9 K& T; q%e-mail:tobysidney33@sohu.com
1 P7 }* c5 v: ^# b( ]) k%####################################################
+ Z' J4 y1 z& r" ~; v; o%
% b% R7 {8 \) o( v( Ccitynum=size(d,2);
* Q$ D( I2 A2 n' k5 }# A3 wn=nargin;
  o. w5 \* v- a+ fif n&lt;2
" ~7 m  K# ?8 y. h2 ]disp('缺少变量！！')
disp('^_^开个玩笑^_^')
end
if n&lt;2
termops=500;
* C1 I4 k" ~7 w! Vnum=50;
pc=0.25;
  A4 M1 d2 d2 Z6 x/ a3 }* Fcxops=3;
pm=0.30;
3 C2 l: h* U9 o, v+ n: f% E; m, m) valpha=0.10;
& Y1 s! m3 }( Y3 K: n6 ]2 Qend
' U0 y) A7 Y3 W0 `* nif n&lt;3
- {0 {7 L' L9 u% Z( c, g% Nnum=50;
; V: f/ M) p# V& J+ }. _% opc=0.25;
% d. _: H, h  h4 c& B# mcxops=3;
pm=0.30;
alpha=0.10;
/ Y9 `1 H+ q1 U$ H3 E# J! @end
- G% G! R" B. D- s3 Rif n&lt;4
pc=0.25;
  W5 _1 e( w5 l$ X: wcxops=3;
7 X7 d$ z1 p- m6 Upm=0.30;
% q: H* i' I+ U/ s+ Yalpha=0.10;
1 B3 p$ u, w0 p) Aend
% n9 u8 e5 v4 E7 @4 f, h1 Dif n&lt;5
cxops=3;
  f* U9 ?- E" M+ ?$ ~pm=0.30;
alpha=0.10;
end
if n&lt;6
, N$ d9 R2 |7 f  ypm=0.30;
+ P- u# C5 U# o0 w7 qalpha=0.10;
$ N- z3 a, p( b4 U& _end
if n&lt;7
alpha=0.10;
6 [) N- r2 v. k5 _7 Qend
if isempty(cxops)
cxops=3;
8 p0 V: w$ t+ ]end</P>
& _9 T# V" D0 t! s& _( Z4 M<>[t]=initializega(num,citynum);
  J0 [3 I; P, r. x( `for i=1:termops
[l]=f(d,t);
[x,y]=find(l==max(l));
trace(i)=-l(y(1));
1 c' T! v4 F: B6 ?! Z' vbestpop=t(y(1),;
[t]=select(t,l,alpha);
[g]=grefenstette(t);
4 a# @5 N! y; H0 t[g1]=crossover(g,pc,cxops);
9 h/ k4 o+ X3 K, t[g]=mutation(g1,pm); %均匀变异
4 @# N' _& ], k[t]=congrefenstette(g);
end</P>
( T9 T+ u( z# [* B2 H<>---------------------------------------------------------
function [t]=initializega(num,citynum)
6 ^: A) R- C. Y2 ~" A( n" L/ yfor i=1:num
6 u2 h5 e5 C' q: O! gt(i,=randperm(citynum);
end
- q# l, L  F9 l+ X( h. ]-----------------------------------------------------------
& M# T) m4 y! gfunction [l]=f(d,t)
[m,n]=size(t);
6 o4 c5 h9 }8 O$ L& @* {for k=1:m
) r2 @- W/ ]& n* F+ j1 Hfor i=1:n-1
4 X' E8 r( J; l5 H9 o$ S% R' |l(k,i)=d(t(k,i),t(k,i+1));
end
l(k,n)=d(t(k,n),t(k,1));
) x( ^) l5 U( Q* a  z1 |l(k)=-sum(l(k,);
' l" D/ M6 y. A9 Y. y2 M& Gend
: d# A1 m3 L) b' S" Y5 O1 \-----------------------------------------------------------
/ X- c& E- n( h" J$ L0 Ofunction [t]=select(t,l,alpha)
2 _: e. D  I# y: d) Z% [[m,n]=size(l);
t1=t;
[beforesort,aftersort1]=sort(l,2);%fsort from l to u
8 O7 b: u" F/ q- E' r+ i- Mfor i=1:n
aftersort(i)=aftersort1(n+1-i); %change
end
for k=1:n;
t(k,=t1(aftersort(k),;
* P+ e4 r7 J  I5 z+ K4 g  Tl1(k)=l(aftersort(k));
end
( M9 g) r1 p! G  S) ^3 \t1=t;
l=l1;
, b& v2 @# S2 X6 Afor i=1:size(aftersort,2)
evalv(i)=alpha*(1-alpha).^(i-1);
/ b: C3 j1 i5 v+ p! g: kend
+ R1 K5 z1 L9 |0 Qm=size(t,1);
+ G( ^+ }3 b6 i& k6 Sq=cumsum(evalv);
qmax=max(q);
for k=1:m
+ p! L- ^( X$ C; }8 x, \) br=qmax*rand(1);
for j=1:m
if j==1&amp;r&lt;=q(1)
# l  A( U' o6 I2 j" n7 Kt(k,=t1(1,;
elseif j~=1&amp;r&gt;q(j-1)&amp;r&lt;=q(j)
% H( @) P5 C7 u) X; {t(k,=t1(j,;
9 ]+ e# ~8 ]2 h1 wend
9 ]  ~9 a7 k  F) m% q* aend
8 C' o+ Y6 R' a5 z, Uend
--------------------------------------------------
function [g]=grefenstette(t)
) m' E6 V1 r3 @  N7 f3 P( i[m,n]=size(t);
5 R  O1 ]1 e  G- d2 B- yfor k=1:m
; T' R' E$ R5 `; K. X  G) Nt0=1:n;
for i=1:n
for j=1:length(t0)
if t(k,i)==t0(j)
: O) b0 }. [* ~g(k,i)=j;
# O) r8 h1 G& w% \" F/ R1 jt0(j)=[];
break
$ q; q; M% P1 d' K4 pend
& K& ~: x2 R) \end
end
end
) D4 @7 [/ g! i- U% W8 ~-------------------------------------------
function [g]=crossover(g,pc,cxops)
' H8 ~1 s6 w' ^! r" t1 G[m,n]=size(g);
ran=rand(1,m);
r=cxops;
[x,ru]=find(ran&lt;pc);
+ X# N# ^3 F- U& M& T, Rif ru&gt;=2
for k=1:2:length(ru)-1
" t6 z2 @. p4 M' Ug1(ru(k),=[g(ru(k),[1:r]),g(ru(k+1),[(r+1):n])];
& I. c7 Y* R& l- d& }+ z# N) ng(ru(k+1),=[g(ru(k+1),[1:r]),g(ru(k),[(r+1):n])];
g(ru(k),=g1(ru(k),;
end
end
' x- q  s) r" U4 V--------------------------------------------
function [g]=mutation(g,pm) %均匀变异
[m,n]=size(g);
ran=rand(1,m);
r=rand(1,3); %dai gai jin
rr=floor(n*rand(1,3)+1);
[x,mu]=find(ran&lt;pm);
4 H* o) ~$ a, Qfor k=1:length(mu)
for i=1:length(r)
umax(i)=n+1-rr(i);
, h& H  D* A/ m8 Sumin(i)=1;
g(mu(k),rr(i))=umin(i)+floor((umax(i)-umin(i))*r(i));
end
end
---------------------------------------------------
6 O/ l4 }+ [. hfunction [t]=congrefenstette(g)
[m,n]=size(g);
for k=1:m
t0=1:n;
6 U4 m6 ?) q- }" g2 Q. W3 sfor i=1:n
t(k,i)=t0(g(k,i));
+ F7 J4 v5 F3 V6 n9 y4 }# M) kt0(g(k,i))=[];
% E" `2 f* G! U% pend
, z( T5 L/ X) a# [& D6 cend
5 _! U: F+ T- m4 g------------------------------------------------- </P></DIV>
; O) ?) `  I( O5 X2 C7 a6 z2 n" u<>又一个Matlab程序，其中交叉算法采用的是由Goldberg和Lingle于1985年提出的PMX(部分匹配交叉)，淘汰保护指数alpha是我自己设计的，起到了加速优胜劣汰的作用。</P>
6 f- c% W+ E. Q) D1 T<DIV class=HtmlCode>
: }4 ?. y& K1 X$ D- t<>%TSP问题（又名：旅行商问题，货郎担问题）遗传算法通用matlab程序
6 V' k: R  N. i%D是距离矩阵，n为种群个数,建议取为城市个数的1~2倍，
; d  g0 S7 W4 q; r9 p9 j%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定
%m为适应值归一化淘汰加速指数 ,最好取为1,2,3,4 ,不宜太大
" E6 q1 x$ X) g& z! \/ K) C) w%alpha为淘汰保护指数,可取为0~1之间任意小数,取1时关闭保护功能,最好取为0.8~1.0
/ d) Z* a6 h( c: I2 e, a$ E%R为最短路径,Rlength为路径长度
function [R,Rlength]=geneticTSP(D,n,C,m,alpha)</P>
. Q# t! m8 y4 T2 \  E! j! o<>[N,NN]=size(D);
' t8 H2 t, s! N+ E1 I, zfarm=zeros(n,N);%用于存储种群
for i=1:n
farm(i,=randperm(N);%随机生成初始种群
6 x1 g6 ]- G7 P" {7 D3 Iend
2 ]4 h- e3 v- @7 QR=farm(1,;%存储最优种群
  R) u$ ^% g4 N1 j8 F* P) Ilen=zeros(n,1);%存储路径长度
fitness=zeros(n,1);%存储归一化适应值
/ `0 M4 ?2 S2 pcounter=0;</P>
<>while counter&lt;C</P>
9 j* K  p' u5 ~* |- f2 t) o<>for i=1:n
9 _- ]# J3 y3 klen(i,1)=myLength(D,farm(i,);%计算路径长度
0 C/ V( F& S1 Q1 {$ F, wend
1 P! v, d8 e$ e0 ]/ Ymaxlen=max(len);
' M( j% ]# \$ p- r, x7 Nminlen=min(len);
fitness=fit(len,m,maxlen,minlen);%计算归一化适应值
rr=find(len==minlen);
6 B4 P1 @  Z: K: dR=farm(rr(1,1),;%更新最短路径</P>
<>FARM=farm;%优胜劣汰，nn记录了复制的个数
# R/ [/ {' t2 c- q2 ]4 {nn=0;
for i=1:n
if fitness(i,1)&gt;=alpha*rand
nn=nn+1;
2 U# @) a* `, P, OFARM(nn,=farm(i,;
$ T9 A% g! n) Y5 k4 a, T/ Q* ?6 Hend
' h( f$ [( w; ^end
FARM=FARM(1:nn,;</P>
<>[aa,bb]=size(FARM);%交叉和变异
while aa&lt;n
7 X6 c! _- N" r) u; m! v; Fif nn&lt;=2
; K* X" H5 P* u; Jnnper=randperm(2);
else
nnper=randperm(nn);
: F5 R- o# V, r7 F( `end
A=FARM(nnper(1),;
. A. Q  b  d& r0 MB=FARM(nnper(2),;
[A,B]=intercross(A,B);
FARM=[FARM;A;B];
: k& g5 j1 H1 b8 j  z[aa,bb]=size(FARM);
& i/ W" r0 _5 P! I' L# l/ eend
5 W3 r, A3 l1 |- vif aa&gt;n
FARM=FARM(1:n,;%保持种群规模为n
end</P>
, X+ s! E' x; v* U<>farm=FARM;
8 `) l( S" y. w& Z1 ]clear FARM
counter=counter+1</P>
<>end</P>
/ X' J5 z; j# Z, T<>Rlength=myLength(D,R);</P>
; l) n" j# Q+ t2 I: D2 M2 n! c- f8 U<>function [a,b]=intercross(a,b)
4 K) f& U6 b8 g9 B! c9 G4 mL=length(a);
if L&lt;=10%确定交叉宽度
W=1;
& d) N7 d, k* B6 ?) ]. \/ C7 oelseif ((L/10)-floor(L/10))&gt;=rand&amp;&amp;L&gt;10
W=ceil(L/10);
else
% R. ~( b; z1 t4 W: O: P! eW=floor(L/10);
* l2 @" Q* x9 e& \. Send
$ |0 r( L4 C# i# T- sp=unidrnd(L-W+1);%随机选择交叉范围，从p到p+W
2 v% S" r, I. G# m4 h. v! Jfor i=1:W%交叉
x=find(a==b(1,p+i-1));
y=find(b==a(1,p+i-1));
[a(1,p+i-1),b(1,p+i-1)]=exchange(a(1,p+i-1),b(1,p+i-1));
7 |" E5 S3 B& B[a(1,x),b(1,y)]=exchange(a(1,x),b(1,y));
/ Q! G2 F+ d' o/ \end
function [x,y]=exchange(x,y)
temp=x;
x=y;
1 W' k) q  u1 g) ]) r/ zy=temp;</P>
<>% 计算路径的子程序
& r6 F9 {; h% U! mfunction len=myLength(D,p)
& \5 P5 H+ V# ^; z+ O[N,NN]=size(D);
len=D(p(1,N),p(1,1));
. y* ]/ f4 A! f) H, W5 {for i=1N-1)
len=len+D(p(1,i),p(1,i+1));
, }# u$ R% w2 f5 p2 N- {- g* i0 r& wend</P>
<>%计算归一化适应值子程序
function fitness=fit(len,m,maxlen,minlen)
fitness=len;
for i=1:length(len)
/ {4 G, S; S' h* Wfitness(i,1)=(1-((len(i,1)-minlen)/(maxlen-minlen+0.000001))).^m;
end </P></DIV>
$ T6 c5 c  u, W# {4 B<>一个C++的程序：</P>
  ?3 |5 m6 e9 L/ Q$ n# d<DIV class=HtmlCode>
4 [+ S+ l2 u6 W2 u8 s' B2 S, g<>//c++的程序
#include&lt;iostream.h&gt;
/ p0 i2 o( U6 w; \( F#include&lt;stdlib.h&gt;
template&lt;class T&gt;
9 C$ C$ t' F) X4 Kclass Graph
{
6 _5 I/ `6 ]  b2 e2 d1 A) D  public:
1 ^( h9 }  |) h( M% C  i    Graph(int vertices=10)
' u4 ~9 m2 o7 I2 T. ~    {
# |8 \1 E$ {& e8 q% D      n=vertices;
      e=0;
/ g) K7 `9 E; {* F! e6 ^    }
    ~Graph(){}
: U' o3 b6 ]0 {; `0 _& a    virtual bool Add(int u,int v,const T&amp; w)=0;
    virtual bool Delete(int u,int v)=0;
. M6 F  g0 m+ o% K" T    virtual bool Exist(int u,int v)const=0;
8 C1 i; @* Q4 h. Y6 a    int Vertices()const{return n;}
/ G' L( t( b, c( }& ?$ E, G. R    int Edges()const{return e;}
  protected:
    int n;
    int e;
};
0 Y5 L% v- F6 y9 R: |+ C! {' b4 N4 }template&lt;class T&gt;
7 N6 `! r5 G+ A" n; eclass MGraph:public Graph&lt;T&gt;
{
  public:
! \- P* Y; L! o    MGraph(int Vertices=10,T noEdge=0);
    ~MGraph();
    bool Add(int u,int v,const T&amp; w);
9 @# J* O4 O1 ^2 L# Z    bool Delete(int u,int v);
1 i" b  K0 c5 y' s    bool Exist(int u,int v)const;
# S9 I/ _4 K- W! i" p' N    void Floyd(T**&amp; d,int**&amp; path);
( p3 f' x' W# }; w0 V: m6 k) P    void print(int Vertices);
  private:
+ _- p  w1 e+ a% y$ I4 x    T NoEdge;
    T** a;
& o2 [( c- H/ R  B9 W- D};
' B: j! l$ G/ w4 |template&lt;class T&gt;
MGraph&lt;T&gt;::MGraph(int Vertices,T noEdge)
{
) m  Q$ t) ~1 w  n=Vertices;
% r* w2 J8 `# {; S  NoEdge=noEdge;
  a=new T* [n];
  for(int i=0;i&lt;n;i++){
/ d6 _; I& F5 @) H    a=new T[n];
: k( {/ a" p( R; }2 y9 p# t    a=0;
4 y* n0 G8 _7 P$ y& W6 S9 s6 U    for(int j=0;j&lt;n;j++)if(i!=j)a[j]=NoEdge;
5 c3 }* r$ i) X6 p8 c  }
}
# \- o0 x; o% }) Wtemplate&lt;class T&gt;
MGraph&lt;T&gt;::~MGraph()
/ |2 a4 [' j; l# f" @% \0 ]{
- g" b, d* W1 F( q$ c: q  for(int i=0;i&lt;n;i++)delete[]a;
* ^6 o9 P. K# x* g: d  delete[]a;
}
template&lt;class T&gt;
bool MGraph&lt;T&gt;::Exist(int u,int v)const
{
7 L( M$ r4 o% z( W  if(u&lt;0||v&lt;0||u&gt;n-1||v&gt;n-1||u==v||a[v]==NoEdge)return false;
. V1 [4 }, n" B" u: Y+ N  return true;
}
template&lt;class T&gt;
/ `0 A2 Z- x. {; Ebool MGraph&lt;T&gt;::Add(int u,int v,const T&amp; w)
{
. u& x8 ^7 e+ E# r3 f3 B  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;
, m1 k8 J0 |; N. i' |: _    return false;
# ]3 K2 E7 W/ d  }
  a[v]=w;
1 B# m  e; V' q# I8 F' e; E$ B  O  e++;
  return true;
}
9 l& {) K& k# R% K/ Xtemplate&lt;class T&gt;
bool MGraph&lt;T&gt;:delete(int u,int v)
+ N# g4 }% ]% A9 Z4 k+ s8 O{
6 ]  L6 d* H) b- {4 g  if(u&lt;0||v&lt;0||u&gt;n-1||v&gt;n-1||u==v||a[v]==NoEdge){
* G* c5 u( ]6 U8 B7 r) o    cerr&lt;&lt;"BadInput!"&lt;&lt;endl;
0 O/ y/ X9 ]3 \  j    return false;
  }
  a[v]=NoEdge;
  e--;
* v, d7 u& I7 a7 w8 e! A% w  return true;
}
template&lt;class T&gt;
! T5 t6 R7 A" ]  S' h! J$ Qvoid MGraph&lt;T&gt;::Floyd(T**&amp; d,int**&amp; path)
# [0 L! ~) I$ m{
  d=new T* [n];
  path=new int* [n];
2 {* L& o) p4 {  for(int i=0;i&lt;n;i++){
    d=new T[n];
+ Z+ b0 a8 R6 G- `8 _) V    path=new int[n];
1 ^# l: C" m0 E5 K$ Y    for(int j=0;j&lt;n;j++){
& d* |! h2 N! N% k2 \      d[j]=a[j];
      if(i!=j&amp;&amp;a[j]&lt;NoEdge)path[j]=i;
" d: ^2 _' k0 D9 N, ~9 N% g      else path[j]=-1;
    }
; c. Y$ j5 j! P/ n, \' h* s3 w/ ^  }
6 o+ D. x& g. J3 Z% i6 O# h; {7 F: o5 B  for(int k=0;k&lt;n;k++){
    for(i=0;i&lt;n;i++)
      for(int j=0;j&lt;n;j++)
0 ]- ?6 {! C6 s! s# x% g3 I# v( F        if(d[k]+d[k][j]&lt;d[j]){
          d[j]=d[k]+d[k][j];
          path[j]=path[k][j];
        }
        }
( s% y8 A5 n2 X# o2 s/ Y. y}
, c+ x+ H( H8 Z) u0 x' h5 i5 ctemplate&lt;class T&gt;
void MGraph&lt;T&gt;::print(int Vertices)
{
/ h8 ]2 n/ t% m( W  for(int i=0;i&lt;Vertices;i++)
5 D- G. h7 h3 y" v$ w/ G* i& L+ r: h    for(int j=0;j&lt;Vertices;j++)
# n% S2 d+ [# B; J/ F( r2 b% B    {
      
      cout&lt;&lt;a[j]&lt;&lt;' ';if(j==Vertices-1)cout&lt;&lt;endl;
    }
}
7 q6 p+ b6 ^% }- a/ r#define noEdge 10000
* B0 W3 N2 X) M9 v1 a#include&lt;iostream.h&gt;
void main()
{
  cout&lt;&lt;"请输入该图的节点数："&lt;&lt;endl;
4 m' q4 [6 \- n$ ]  int vertices;
7 O& ~. ~+ R9 B$ }7 V  cin&gt;&gt;vertices;
; n- W8 a% p+ h' i( k  MGraph&lt;float&gt; b(vertices,noEdge);
  cout&lt;&lt;"请输入u,v,w:"&lt;&lt;endl;
  int u,v;
! O/ v; V6 l: z% Z6 B( S: c  float w;
4 Q- Z6 f' b3 P* u  cin&gt;&gt;u&gt;&gt;v&gt;&gt;w;
% {) r+ H, q, w- I( O: y  while(w!=noEdge){
( h% J/ U- y, A. F& P    //u=u-1;
    b.Add(u-1,v-1,w);
7 z0 b. ^+ g1 h    b.Add(v-1,u-1,w);
    cout&lt;&lt;"请输入u,v,w:"&lt;&lt;endl;
    cin&gt;&gt;u&gt;&gt;v&gt;&gt;w;
# |; p' c1 _4 ]) W) o& J; V  }
% P( \: c8 r3 |  b.print(vertices);
$ C: E- g/ f6 z6 |- r$ ~1 z  int** Path;
  int**&amp; path=Path;
  float** D;
  float**&amp; d=D;
2 u: i/ q3 P' l  b.Floyd(d,path);
  for(int i=0;i&lt;vertices;i++){
* K5 A! P' O, a8 u( |+ |    for(int j=0;j&lt;vertices;j++){
% d. y$ a5 h3 ]( e. G      cout&lt;&ltath[j]&lt;&lt;' ';
, ~# V' _9 j' L) u9 F" A9 i5 k+ p      if(j==vertices-1)cout&lt;&lt;endl;
# y# a3 p4 m! L& r0 }    }
1 O/ b% L* P+ J9 e  }
3 @% v! }. x  Y  int *V;
7 x( f2 T0 d: C/ n3 d  V=new int[vertices+1];
# U+ }9 L. n7 X2 M: B  cout&lt;&lt;"请输入任意一个初始H-圈："&lt;&lt;endl;
! b, P+ N& C0 W7 Q  for(int n=0;n&lt;=vertices;n++){
   
    cin&gt;&gt;V[n];
  }
  for(n=0;n&lt;55;n++){
    for(i=0;i&lt;n-1;i++){
    for(int j=0;j&lt;n-1;j++)
2 }/ C; k+ U+ S9 {: g6 I" W& C1 B6 Q    {
      if(i+1&gt;0&amp;&amp;j&gt;i+1&amp;&amp;j&lt;n-1){
8 i5 V/ T% R/ v2 ?! M* }4 i& f        if(D[V][V[j]]+D[V[i+1]][V[j+1]]&lt;D[V][V[i+1]]+D[V[j]][V[j+1]]){
6 ~* y0 |0 g' _, |* y- N# V          int l;
/ \3 h8 n2 C& b6 _* ~% {          l=V[i+1];V[i+1]=V[j];V[j]=l;
, u- b# e/ k, T" |6 t7 B& A        }
( O( V1 B  a- K2 ]! V      }
    }
  }
! s. `5 J4 v  N- W  }
$ Y7 l/ o* m$ U* \" c1 N  float total=0;
' J. J! c& Y8 i, q  cout&lt;&lt;"最小回路："&lt;&lt;endl;
: L7 u5 y: \( R) |% x  for(i=0;i&lt;=vertices;i++){
2 c/ i% \3 p& v% O5 Q  \# z5 q   
    cout&lt;&lt;V+1&lt;&lt;' ';
8 z9 d2 p  v7 ^& @. Y  }
  cout&lt;&lt;endl;
  for(i=0;i&lt;vertices;i++)
  total+=D[V][V[i+1]];
6 y9 o8 L$ N1 T+ n( X8 `  cout&lt;&lt;"最短路径长度："&lt;&lt;endl;
  cout&lt;&lt;total;
} </P></DIV>
5 v9 F, u  J* \7 }" ~6 @<>C语言程序：</P>
0 H5 O. G, r8 d1 z3 x, C+ s<DIV class=HtmlCode>
; O5 W6 d3 r$ C6 W9 G<>#include&lt;stdio.h&gt;
5 w- ?" Z/ O0 j9 o3 X% _#include&lt;stdlib.h&gt;
#include&lt;math.h&gt;
6 y+ d8 I, w" q( t( W#include&lt;alloc.h&gt;
0 Z# G6 A: ^9 F' i#include&lt;conio.h&gt;
#include&lt;float.h&gt;
2 x2 @' q* O1 L: z6 O1 P5 g#include&lt;time.h&gt;
#include&lt;graphics.h&gt;
#include&lt;bios.h&gt;</P>
! S- i* w0 \7 Q6 w9 m<>#define   maxpop  100
#define   maxstring  100</P>
<>
; M4 G7 n5 X1 ~$ t5 @( _# Ystruct  pp{unsigned char chrom[maxstring];
    float x,fitness;
    unsigned int parent1,parent2,xsite;
: n/ J7 H% ^8 O! ?& C   };
" T' o5 w' \$ Tstruct pp *oldpop,*newpop,*p1;
unsigned int popsize,lchrom,gem,maxgen,co_min,jrand;
unsigned int nmutation,ncross,jcross,maxpp,minpp,maxxy;
float 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;
: w5 n7 T$ m* P0 D* k+ h/ lfloat objfunc(float);
( p) H) M- L0 M6 ?5 J( uvoid statistics();
9 X' [: M1 F! {int select();
int flip(float);
int crossover();
void generation();
void initialize();
void report();
' b8 g3 V7 S. g0 W2 p1 Mfloat decode();
void crtinit();
1 o. R7 [1 q3 m8 }% f8 c' D+ C8 j& ?void inversion();
2 A& S7 o+ E% u! lfloat random1();
void randomize1();</P>
3 V- y3 R( `- Y<>main()
$ K8 s8 y6 k) N, g{unsigned int gen,k,j,tt;
) |$ _; j0 E( K, i4 fchar fname[10];
7 m2 S5 L4 P6 b$ M$ @/ v  ]float ttt;
clrscr();
co_min=0;
+ M, L# d3 u: X1 Gif((oldpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp)))==NULL)
     {printf("memory requst fail!\n");exit(0);}
" q5 B6 D; F4 s+ N+ Z" e' `/ Wif((dd=(float *)farmalloc(maxstring*maxstring*sizeof(float)))==NULL)
, m' s3 T8 ^+ g: m     {printf("memory requst fail!\n");exit(0);}
if((newpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp)))==NULL)
     {printf("memory requst fail!\n");exit(0);}
if((p1=(struct pp *)farmalloc(sizeof(struct pp)))==NULL)
6 S; ^1 i# [  B7 }% ]" k     {printf("memory requst fail!\n");exit(0);}
for(k=0;k&lt;maxpop;k++) oldpop[k].chrom[0]='\0';
* a$ ?" s4 s# X: j7 K. tfor(k=0;k&lt;maxpop;k++) newpop[k].chrom[0]='\0';
. F& {3 n8 B3 G) r% qprintf("Enter Result Data Filename:");
! @& S% A6 A5 xgets(fname);
3 v8 p4 R7 ~8 z# z& _if((fp=fopen(fname,"w+"))==NULL)
  {printf("cannot open file\n");exit(0);}</P>
<>
; v! D0 j0 F5 Hgen=0;
randomize();
initialize();</P>
7 @+ `2 d7 J' a- V5 h<>fputs("this is result of the TSP problem:",fp);
$ c' U9 k- h1 k" N, o/ A/ |2 s7 [4 Ifprintf(fp,"city: %2d psize: %3d Ref.TSP_path: %f\n",lchrom,popsize,refpd);
) i8 f( _/ o9 ]9 j" O4 hfprintf(fp,"c: %f Pm: %f Seed: %f\n",pcross,pmutation,seed);
8 _6 m! [& R* nfprintf(fp,"X site:\n");
for(k=0;k&lt;lchrom;k++)
$ V6 @( D, X5 E" a0 H   {if((k%16)==0) fprintf(fp,"\n");
    fprintf(fp,"%5d",x[k]);
   }
2 Q7 F: B% Z( ~2 D) R4 y+ t0 ffprintf(fp,"\n Y site:\n");
for(k=0;k&lt;lchrom;k++)
   {if((k%16)==0) fprintf(fp,"\n");
    fprintf(fp,"%5d",y[k]);
# q; u+ r1 y; t5 @   }
fprintf(fp,"\n");</P>
<P>
2 ]* k- ?6 T9 H; bcrtinit();
statistics(oldpop);
report(gen,oldpop);
% O* b7 }' T8 o. \, l+ rgetch();
maxold=min;
fm[0]=100.0*oldpop[maxpp].x/ff;
do {
% }/ H" B/ x* Q$ D" Q  m" k" S    gen=gen+1;
( |) x! [" v$ C  @" Q, P    generation();
    statistics(oldpop);
# {4 }9 C( S- g3 O& U- j  i, x    if(max&gt;maxold)
$ {% ?' W; j6 T$ S       {maxold=max;
; H) {, k  F  D( Cco_min=0;
       }
    fm[gen%200]=100.0*oldpop[maxpp].x/ff;
% Z% H. d* v7 F- I0 p( J, e    report(gen,oldpop);
" x3 w, F" j# `* f" v    gotoxy(30,25);
# Y$ t& k& B+ v; q2 A3 y# f    ttt=clock()/18.2;
    tt=ttt/60;
+ Q4 ~* c+ q4 n9 K. P3 r% y! F    printf("Run Clock: %2d: %2d: %4.2f",tt/60,tt%60,ttt-tt*60.0);
% j  w3 ^  E+ A" ?% R    printf("Min=%6.4f Nm:%d\n",min,co_min);
$ t/ c5 O% ~/ U$ Y: z4 n   }while((gen&lt;100)&amp;&amp;!bioskey(1));
printf("\n gen= %d",gen);
do{
0 m% s& H' \! y# T    gen=gen+1;
    generation();
    statistics(oldpop);
3 S2 E3 j# I) H1 c3 z0 s    if(max&gt;maxold)
       {maxold=max;
co_min=0;
9 \4 `5 r) |& t       }
    fm[gen%200]=100.0*oldpop[maxpp].x/ff;
6 @# b) L7 ?3 o- l( D$ R    report(gen,oldpop);
    if((gen%100)==0)report(gen,oldpop);
3 }* E6 b- P5 M8 U; C    gotoxy(30,25);
# a/ P3 {" d) g    ttt=clock()/18.2;
# P' t; h. b: r# v, c    tt=ttt/60;
4 f$ j. I( P, j+ I- p8 o    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);
- R/ X) ]' h3 m6 }7 `   }while((gen&lt;maxgen)&amp;&amp;!bioskey(1));</P>
<P>getch();
for(k=0;k&lt;lchrom;k++)
: x9 A, k( {9 p# R8 \; F! f7 R  {if((k%16)==0)fprintf(fp,"\n");
+ A5 |: \) u( T   fprintf(fp,"%5d",oldpop[maxpp].chrom[k]);
  }
fprintf(fp,"\n");</P>
7 Z1 O; P7 A1 t' c<P>fclose(fp);
" v+ a8 p0 W9 j7 B7 T7 ]5 p4 efarfree(dd);
farfree(p1);
farfree(oldpop);
farfree(newpop);
restorecrtmode();
exit(0);
4 O# G; r) o5 q* Z  ~# `}</P>
) W. b) F; J, z8 l' n# s* c' \4 ?<P>/*%%%%%%%%%%%%%%%%*/</P>
<P>float  objfunc(float x1)
{float y;
  y=100.0*ff/x1;
  return y;
  }</P>
" p0 m2 C. T/ V+ J<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)
9 h3 ^' S6 P# s0 I8 k* m9 Astruct pp *pop;
/ W! r3 C) h& j{int j;
sumfitness=pop[0].fitness;
min=pop[0].fitness;
max=pop[0].fitness;
maxpp=0;
minpp=0;
for(j=1;j&lt;popsize;j++)
    {sumfitness=sumfitness+pop[j].fitness;
     if(pop[j].fitness&gt;max)
{max=pop[j].fitness;
8 D( q* {3 L+ B2 e; a% }( ^  maxpp=j;
7 p4 t  v6 T( n) w}
     if(pop[j].fitness&lt;min)
2 V" s6 F! O6 w; j+ Q2 y, G{min=pop[j].fitness;
8 ~; Z+ Q7 r  q, x0 a0 h$ k+ S0 x  minpp=j;
. {$ Q1 w9 Q9 ?; j}
    }</P>
<P>avg=sumfitness/(float)popsize;
}</P>
8 Q* D/ ]7 s4 z3 m' P$ M2 ^<P>/*%%%%%%%%%%%%%%%%%%%%*/</P>
<P>void generation()
{unsigned int k,j,j1,j2,i1,i2,mate1,mate2;
% K' q: J6 R5 t* Q+ S) T$ S3 S. l. [float f1,f2;
7 P; @: }" Z! m. Hj=0;
0 s3 W/ N# m3 O/ d/ q/ M- s* `0 T6 Ddo{
     mate1=select();
     pp:mate2=select();
     if(mate1==mate2)goto pp;
     crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
5 }, m6 ^6 H% }( q' e9 ]     newpop[j].x=(float)decode(newpop[j].chrom);
* P( z  a: R5 e* C* ^2 \     newpop[j].fitness=objfunc(newpop[j].x);
: N! [1 S0 \" r7 T/ k     newpop[j].parent1=mate1;
7 G+ N, e8 I: W6 r' ?     newpop[j].parent2=mate2;
     newpop[j].xsite=jcross;
# C: C  y) F2 a     newpop[j+1].x=(float)decode(newpop[j+1].chrom);
4 O- C' T6 y0 u0 C7 Q9 p+ f% k     newpop[j+1].fitness=objfunc(newpop[j+1].x);
! w; n; O" B6 C' S+ d) O1 U     newpop[j+1].parent1=mate1;
9 `4 E4 u6 h, s     newpop[j+1].parent2=mate2;
     newpop[j+1].xsite=jcross;
     if(newpop[j].fitness&gt;min)
{for(k=0;k&lt;lchrom;k++)
      oldpop[minpp].chrom[k]=newpop[j].chrom[k];
2 n/ }' ?7 l) c1 C4 F: i8 N! H4 R  oldpop[minpp].x=newpop[j].x;
9 m9 ], |. j4 _4 O1 T4 h" }$ X  oldpop[minpp].fitness=newpop[j].fitness;
  co_min++;
# u0 `$ }! _8 x# Y8 s! N  return;
}</P>
- W1 ~9 b5 x5 i2 Q  H& l* C3 E<P>     if(newpop[j+1].fitness&gt;min)
( c, e" E, g1 L/ X* v5 x4 ^{for(k=0;k&lt;lchrom;k++)
      oldpop[minpp].chrom[k]=newpop[j+1].chrom[k];
  oldpop[minpp].x=newpop[j+1].x;
  oldpop[minpp].fitness=newpop[j+1].fitness;
  co_min++;
  return;
}
      j=j+2;
( j! J( p9 o9 R, J3 V( k     }while(j&lt;popsize);
}</P>
7 k* _0 V4 R% G; f' `6 e+ g+ l<P>/*%%%%%%%%%%%%%%%%%*/</P>
7 Q4 A7 D& Y$ y0 D$ ~* v' s<P>void initdata()
8 Z/ L3 J- y2 K0 \{unsigned int ch,j;
clrscr();
, _3 J1 G8 y0 P7 |: W' U! g% zprintf("-----------------------\n");
printf("A SGA\n");
printf("------------------------\n");
/*pause();*/clrscr();
printf("*******SGA DATA ENTRY AND INITILIZATION *******\n");
7 N1 n& U6 r6 R: \printf("\n");
4 o& W; z( R* I$ r: Q: A: w& Q( q3 Qprintf("input pop size");scanf("%d",&amp;popsize);
printf("input chrom length");scanf("%d",&amp;lchrom);
$ d$ C* [- q+ g+ S9 W% e- }* Oprintf("input max generations");scanf("%d",&amp;maxgen);
printf("input crossover probability");scanf("%f",&amp;pcross);
printf("input mutation prob");scanf("%f",&amp;pmutation);
randomize1();
clrscr();
nmutation=0;
- R; R$ u1 a* p' D; q, w+ |ncross=0;
7 D& P; c' q8 C& C) x% t4 q  N" Q}</P>
4 `: E6 N4 C* |% X! Z9 y<P>/*%%%%%%%%%%%%%%%%%%%%*/</P>
<P>void initreport()
{int j,k;
printf("pop size=%d\n",popsize);
6 W# k5 ]3 n9 u0 @! kprintf("chromosome length=%d\n",lchrom);
/ t- w/ X; |: x  v3 u) Oprintf("maxgen=%d\n",maxgen);
* l5 w" I. Q$ f1 ]printf("pmutation=%f\n",pmutation);
0 M1 Z& A/ O% s7 A6 Hprintf("pcross=%f\n",pcross);
printf("initial generation statistics\n");
printf("ini pop max fitness=%f\n",max);
2 _8 D# j$ U& v, D, z0 Jprintf("ini pop avr fitness=%f\n",avg);
, e4 d2 e' ?6 J- O  h1 v' w5 Tprintf("ini pop min fitness=%f\n",min);
- `6 R4 C. Y6 M2 T' Oprintf("ini pop sum fit=%f\n",sumfitness);
}</P>
<P>
void initpop()
{unsigned char j1;
) Z6 [% r& t) u5 C- Iunsigned int k5,i1,i2,j,i,k,j2,j3,j4,p5[maxstring];
. C. y( {7 M7 C4 i) P5 I* ufloat f1,f2;
9 q' }& @& V3 ?0 b  ^: m3 K# L% `j=0;
  x$ a* A) K( S- \for(k=0;k&lt;lchrom;k++)
     oldpop[j].chrom[k]=k;
1 h) f/ J) x0 [+ z( t- Gfor(k=0;k&lt;lchrom;k++)
     p5[k]=oldpop[j].chrom[k];
randomize();
for(;j&lt;popsize;j++)
     {j2=random(lchrom);
      for(k=0;k&lt;j2+20;k++)
9 h) x( ^  I2 l; o  {j3=random(lchrom);
* z0 I# I0 D9 Z  r! v0 U) W& x6 {   j4=random(lchrom);
   j1=p5[j3];
   p5[j3]=p5[j4];
  h6 W+ C2 B. p' G  i& Y! p   p5[j4]=j1;
. F; n+ }2 I6 w( \  }
: t, ~- E; t/ J, B: L' K2 {& q       for(k=0;k&lt;lchrom;k++)
  oldpop[j].chrom[k]=p5[k];
% y( e) C4 u! p. E& H     }
  L1 S, d; L- Y9 `* F  w  for(k=0;k&lt;lchrom;k++)
    for(j=0;j&lt;lchrom;j++)
       dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]);
  for(j=0;j&lt;popsize;j++)
+ s. Z. @( l! j    {oldpop[j].x=(float)decode(oldpop[j].chrom);
     oldpop[j].fitness=objfunc(oldpop[j].x);
     oldpop[j].parent1=0;
# ^% _6 l# l5 M8 {4 |  L     oldpop[j].parent2=0;
% e  V" ]: g' F; v- D     oldpop[j].xsite=0;
$ U6 o& ~+ V5 U# s    }
% T7 s) D5 |! ?; d6 u1 |}</P>
<P>/*&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;*/
void initialize()
! y9 `, X) ?3 y! }9 C3 O{int k,j,minx,miny,maxx,maxy;
initdata();
$ w- c5 O4 u1 e- @- H8 \minx=0;
* Q# H4 h. M" Y; {. v1 hminy=0;
7 D2 B; d& |8 g: Kmaxx=0;maxy=0;
- V1 C% N& B' C. ?. N4 zfor(k=0;k&lt;lchrom;k++)
   {x[k]=rand();
- h) A) E- x4 v" q  [' P# k    if(x[k]&gt;maxx)maxx=x[k];
    if(x[k]&lt;minx)minx=x[k];
    y[k]=rand();
0 U6 }9 Z; h7 Z* i. h# l) }- P5 k    if(y[k]&gt;maxy)maxy=y[k];
    if(y[k]&lt;miny)miny=y[k];
$ y  L+ m( ~! Z9 w7 ]8 j# R& F   }
if((maxx-minx)&gt;(maxy-miny))
     {maxxy=maxx-minx;}
% \9 S( m: z' T  x    else {maxxy=maxy-miny;}
  S$ C5 ~9 f4 U+ p8 p6 P2 c9 q; j# ?maxdd=0.0;
5 b( b2 @" G4 |7 |3 Gfor(k=0;k&lt;lchrom;k++)
   for(j=0;j&lt;lchrom;j++)
     {dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]);
2 b; J& q. c! n; n% D      if(maxdd&lt;dd[k*lchrom+j])maxdd=dd[k*lchrom+j];
     }
. X% S) Z7 i1 R% e* M  \refpd=dd[lchrom-1];
# Q2 K5 w4 z* t  hfor(k=0;k&lt;lchrom;k++)
0 f7 g7 F% Z  ~( a+ R, H; a! l   refpd=refpd+dd[k*lchrom+k+2];
for(j=0;j&lt;lchrom;j++)
# M! O6 a" L' I! o- ^   dd[j*lchrom+j]=4.0*maxdd;
ff=(0.765*maxxy*pow(lchrom,0.5));
minpp=0;
min=dd[lchrom-1];
0 j/ L) {9 l8 e+ V! \for(j=0;j&lt;lchrom-1;j++)
6 O) o; h5 n7 z3 B6 v   {if(dd[lchrom*j+lchrom-1]&lt;min)
% j  |" z% J4 y8 R+ o! U{min=dd[lchrom*j+lchrom-1];
  minpp=j;
}
    }
initpop();
' ~4 s( u* O  r% m" kstatistics(oldpop);
initreport();
) e9 t. N3 o. q}</P>
<P>/*&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;*/</P>
% W" ]  F; q6 d" d; p2 m0 t3 t<P>void report(int l,struct pp *pop)
{int k,ix,iy,jx,jy;
unsigned int tt;
float ttt;
  l  d  G8 m" k9 [# Dcleardevice();
4 N; {! r' N" C0 agotoxy(1,1);
printf("city:%4d  para_size:%4d  maxgen:%4d  ref_tour:%f\n"
  O8 v' [' c8 D9 V0 b3 q   ,lchrom,popsize,maxgen,refpd);
printf("ncross:%4d  Nmutation:%4d Rungen:%4d AVG=%8.4f MIN=%8.4f\n\n"
% l" @. S6 @2 T4 j   ,ncross,nmutation,l,avg,min);
printf("Ref.cominpath:%6.4f Minpath length:%10.4f Ref_co_tour:%f\n"
3 L- J& s3 z8 Q) t   ,pop[maxpp].x/maxxy,pop[maxpp].x,ff);
printf("Co_minpath:%6.4f Maxfit:%10.8f"
9 r) g1 N6 |% Z$ r   ,100.0*pop[maxpp].x/ff,pop[maxpp].fitness);
/ z* I3 n" D5 M! w* h. ]' ettt=clock()/18.2;
- r& m& y! a& H1 w. {+ S+ rtt=ttt/60;
printf("Run clock:%2d:%2d:%4d.2f\n",tt/60,tt%60,ttt-tt*60.0);
setcolor(1%15+1);
9 R; `% A9 k1 L  b% g: F- ]$ qfor(k=0;k&lt;lchrom-1;k++)
" \+ z# `2 [0 p$ l  A" E    {ix=x[pop[maxpp].chrom[k]];
     iy=y[pop[maxpp].chrom[k]]+110;
     jx=x[pop[maxpp].chrom[k+1]];
% b! x  f3 c3 z     jy=y[pop[maxpp].chrom[k+1]]+110;
     line(ix,iy,jx,jy);
+ I) [, E2 R- J8 w' h1 h% Y     putpixel(ix,iy,RED);
& _) N8 N* J2 [$ ?2 I+ U    }
ix=x[pop[maxpp].chrom[0]];
iy=y[pop[maxpp].chrom[0]]+110;
jx=x[pop[maxpp].chrom[lchrom-1]];
& O9 U2 C; b2 p$ ~  P& ojy=y[pop[maxpp].chrom[lchrom-1]]+110;
; ^( }& q: Y7 A; Cline(ix,iy,jx,jy);
putpixel(jx,jy,RED);
5 W! U/ D6 Y1 W: Tsetcolor(11);
outtextxy(ix,iy,"*");
1 |& T8 M6 \8 i9 a# k* G: Wsetcolor(12);
for(k=0;k&lt;1%200;k++)
* w6 n- ?, U1 ^* D+ X    {ix=k+280;
     iy=366-fm[k]/3;
6 G; h% |# X  r5 I* x4 L/ v+ ?7 q) u     jx=ix+1;
     jy=366-fm[k+1]/3;
3 D3 E, M  f( d% p& E1 l9 D     line(ix,iy,jx,jy);
     putpixel(ix,iy,RED);
7 B% Z( k& u- Q& l    }
$ a; h- s& u1 t1 q. Xprintf("GEN:%3d",l);
printf("Minpath:%f Maxfit:%f",pop[maxpp].x,pop[maxpp].fitness);
printf("Clock:%2d:%2d:%4.2f\n",tt/60,tt%60,ttt-tt*60.0);
& F" k' s3 k2 c8 {}</P>
<P>/*###############*/</P>
<P>float decode(unsigned char *pp)
+ x. t4 H7 ^: ~7 C5 o{int j,k,l;
5 N; W6 z% U& e) m  c, {, ]float tt;
2 q' `# L! P9 ?tt=dd[pp[0]*lchrom+pp[lchrom-1]];
0 Y  h: A8 b% `; i/ g. Q' E' ?; kfor(j=0;j&lt;lchrom-1;j++)
    {tt=tt+dd[pp[j]*lchrom+pp[j+1]];}
" I3 W+ m$ y, o$ Kl=0;
for(k=0;k&lt;lchrom-1;k++)
   for(j=k+1;j&lt;lchrom;j++)
  S2 S! v0 ^" ]& S% j: K2 p; J      {if(pp[j]==pp[k])l++;}
return tt+4*l*maxdd;
}</P>
<P>/*%%%%%%%%%%%%%%%%%%*/
void crtinit()
{int driver,mode;
struct palettetype p;
driver=DETECT;
mode=0;
initgraph(&amp;driver,&amp;mode,"");
( m. m* `7 ~& z; N3 N1 }$ bcleardevice();
}</P>
) F7 ?1 C- f7 z  c1 a2 a<P>/*$$$$$$$$$$$$$$$$$$$$*/
int select()
{double rand1,partsum;
. ?3 I8 i( R8 @) \& j6 l0 Dfloat r1;
" [8 L2 I3 J5 Qint j;
partsum=0.0;
7 B0 ^/ e2 }9 Pj=0;
rand1=random1()*sumfitness;
do{
     partsum=partsum+oldpop[j].fitness;
     j=j+1;
   }while((partsum&lt;rand1)&amp;&amp;(j&lt;popsize));
return j-1;
}</P>
<P>/*$$$$$$$$$$$$$$$*/
int crossover(unsigned char *parent1,unsigned char *parent2,int k5)
6 `8 Y, ^8 g. \  a{int k,j,mutate,i1,i2,j5;
int j1,j2,j3,s0,s1,s2;
4 q& k; y3 T4 @2 qunsigned char jj,ts1[maxstring],ts2[maxstring];
/ Z# o- D5 p) l, N, jfloat f1,f2;
s0=0;s1=0;s2=0;
if(flip(pcross))
   {jcross=random(lchrom-1);
    j5=random(lchrom-1);
- O! _$ i+ \' O- ^( ?9 e- Q    ncross=ncross+1;
    if(jcross&gt;j5){k=jcross;jcross=j5;j5=k;}
! V: P/ n; e" {8 P) [/ c8 b, ?   }
   else jcross=lchrom;
  c, b# b  A- x' B) W; M" V9 C" v6 m8 nif(jcross!=lchrom)
   {s0=1;
    k=0;
    for(j=jcross;j&lt;j5;j++)
      {ts1[k]=parent1[j];
       ts2[k]=parent2[j];
4 D' c+ n8 g! s9 H& \) ]       k++;
      }
6 g; t& W4 D* N( b    j3=k;
    for(j=0;j&lt;lchrom;j++)
5 f( @' V$ w% e' q6 ~6 j       {j2=0;
while((parent2[j]!=ts1[j2])&amp;&amp;(j2&lt;k)){j2++;}
if(j2==k)
. ]8 R6 D* c$ V$ c( C# Y! t* |2 b      {ts1[j3]=parent2[j];
       j3++;
      }
       }
. |# E  q4 N7 C! v* M7 i4 R1 w     j3=k;
6 `. y! B) i6 |4 q8 g; I; ]     for(j=0;j&lt;lchrom;j++)
* \6 N  C- _5 x9 ^3 K/ A$ F) n       {j2=0;
" ]+ W# A" o! P1 f' h5 K! ]while((parent1[j]!=ts2[j2])&amp;&amp;(j2&lt;k)){j2++;}
if(j2==k)
; \9 |6 d4 J# A$ t       {ts2[j3]=parent1[j];
, E' g- E1 p( w. d        j3++;
       }
       }
     for(j=0;j&lt;lchrom;j++)
  O3 n6 E6 q9 X# k- e8 B       {newpop[k5].chrom[j]=ts1[j];
3 c7 F8 q6 r& g; O1 `% s' enewpop[k5+1].chrom[j]=ts2[j];
4 N! C7 t/ `) c7 j       }
) ^/ f1 |, W$ Z   }
& i" l' b) e- g  }else
* L, U; R* t* J( p( _8 T; W   {for(j=0;j&lt;lchrom;j++)
9 t) E1 O! `. B0 l$ J      {newpop[k5].chrom[j]=parent1[j];
7 c" d* I( U* q4 i3 W% R! O       newpop[k5+1].chrom[j]=parent2[j];
      }
$ d/ g, x% o, [, s) J    mutate=flip(pmutation);
    if(mutate)
      {s1=1;
8 D. R4 F  ^# D       nmutation=nmutation+1;
& W* ]: i* g  R9 ~7 a' Q       for(j3=0;j3&lt;200;j3++)
9 Q3 o; c' ^/ `  {j1=random(lchrom);
2 k, q3 \2 @% \- W5 b: U' @   j=random(lchrom);
/ R7 j2 J8 P1 Q8 ^7 o   jj=newpop[k5].chrom[j];
   newpop[k5].chrom[j]=newpop[k5].chrom[j1];
   newpop[k5].chrom[j1]=jj;
- B  G+ g5 n2 f1 i  }
: z/ S0 \* |% Q  h, a       }
    mutate=flip(pmutation);
6 K- H! t2 u# r    if(mutate)
4 r/ r- P- y9 j9 g      {s2=1;
       nmutation=nmutation+1;
% B6 N3 p1 S9 [5 ?       for(j3=0;j3&lt;100;j3++)
1 E- L9 j  P( h7 _% }  {j1=random(lchrom);
6 U; ~; ]# q8 l4 w6 o   j=random(lchrom);
3 \9 S; e# J# m% w! n8 n& _$ @   jj=newpop[k5+1].chrom[j];
! Q% G7 C! ], o   newpop[k5+1].chrom[j]=newpop[k5+1].chrom[j1];
   newpop[k5+1].chrom[j1]=jj;
  }
       }
/ ?5 U1 G% x! c' F  }
  j2=random(2*lchrom/3);
  for(j=j2;j&lt;j2+lchrom/3-1;j++)
. p, m& q' e; r2 x8 G; A- h' N' v    for(k=0;k&lt;lchrom;k++)
       {if(k==j)continue;
7 v& q( {1 ~; s/ `if(k&gt;j){i2=k;i1=j;}
9 C, ~8 A" _- H6 O/ a      else{i1=k;i2=j;}
f1=dd[lchrom*newpop[k5].chrom[i1]+newpop[k5].chrom[i2]];
f1=f1+dd[lchrom*newpop[k5].chrom[(i1+1)%lchrom]+
  p. N. t+ r$ M; d     newpop[k5].chrom[(i2+1)%lchrom]];
f2=dd[lchrom*newpop[k5].chrom[i1]+
( h$ L2 P. ^8 l% @     newpop[k5].chrom[(i1+1)%lchrom]];
6 [! h6 y; }) `; H+ of2=f2+dd[lchrom*newpop[k5].chrom[i2]+
: v. k2 `9 y. `) h* M     newpop[k5].chrom[(i2+1)%lchrom]];
if(f1&lt;f2){inversion(i1,i2,newpop[k5].chrom);}
       }
  j2=random(2*lchrom/3);
$ O  \3 C' U8 C$ T  for(j=j2;j&lt;j2+lchrom/3-1;j++)
  }+ ^# N3 b2 f" ?5 H" G    for(k=0;k&lt;lchrom;k++)
7 M; \5 _4 \8 P- b       {if(k==j)continue;
if(k&gt;j){i2=k;i1=j;}
      else{i1=k;i2=j;}
f1=dd[lchrom*newpop[k5+1].chrom[i1]+newpop[k5+1].chrom[i2]];
7 d& h( y8 S1 M+ n: Vf1=f1+dd[lchrom*newpop[k5+1].chrom[(i1+1)%lchrom]+
     newpop[k5+1].chrom[(i2+1)%lchrom]];
f2=dd[lchrom*newpop[k5+1].chrom[i1]+
0 F7 q( u+ g8 ~! O0 c# N" d     newpop[k5+1].chrom[(i1+1)%lchrom]];
! I- q! M5 `) g2 g: c' ~f2=f2+dd[lchrom*newpop[k5+1].chrom[i2]+
- r* O5 @3 m, [! U     newpop[k5+1].chrom[(i2+1)%lchrom]];
if(f1&lt;f2){inversion(i1,i2,newpop[k5+1].chrom);}
       }
  return 1;
' W; _# Y: V7 R' p" p) n5 Y' B}</P>
7 O4 D5 f, y7 a5 [6 u<P>/*$$$$$$$$$$$$$$$*/</P>
<P>void inversion(unsigned int k,unsigned int j,unsigned char *ss)
; C! e$ I$ k1 L{unsigned int l1,i;
unsigned char tt;
3 b; I$ a3 z- `  _7 j3 U9 g2 {. |l1=(j-k)/2;
# i! ~) d: O, K5 O' Bfor(i=0;i&lt;l1;i++)
2 K) \$ ]' W, P( O# D$ w   {tt=ss[k+i+1];
    ss[k+i+1]=ss[j-i];
    ss[j-i]=tt;
   }
}</P>
<P>/*%%%%%%%%%%%%%%%*/</P>
<P>void randomize1()
7 k& X( E0 O: D+ B5 O( C{int i;
randomize();
2 @: s7 `! z: y4 u  S7 k; T& h; Cfor(i=0;i&lt;lchrom;i++)
   oldrand=random(30001)/30000.0;
# a& Y' n/ b' [jrand=0;
0 r) p3 Q# z0 W- [( m" w}</P>
<P>/*%%%%%%%%%%%*/</P>
<P>float random1()
7 l' r. E! l) `5 B{jrand=jrand+1;
' W1 p" k3 o, ^. ^if(jrand&gt;=lchrom)
   {jrand=0;
    randomize1();
9 w' ?9 t# n% W, H   }
6 b% E- R; D# P7 ~, Q; treturn oldrand[jrand];
}</P>
<P>/*%%%%%%%%%%*/</P>
' U, {& p- W0 `) Z. b<P>int flip(float probability)
. ]; @! U! q4 w* c# ]$ ?1 Z{float ppp;
( s" X, W! E. @2 }0 r6 {# ^0 e2 dppp=random(20001)/20000.0;
if(ppp&lt;=probability)return 1;
, A3 w2 W" F% ?4 B* `& Creturn 0;
/ r4 r. V$ S4 @% j  ?5 F# x}</P></DIV>

<P>改进后用来求解VRP问题的Delphi程序：</P>
<DIV class=HtmlCode>
<P>unit uEA;</P>
<P>interface</P>
5 d3 k) F& b, D8 S/ ?1 a<P>uses
+ Q/ ~! v/ h& n; P7 Q+ Z; MuUtilsEA, uIEA, uITSP, Classes, GaPara, windows, SysUtils, fEA_TSP;</P>
<P>type
& L) k3 k2 r" qTIndividual = class(TInterfacedObject, IIndividual)
' q% b, c( o! B! B9 r. j4 {2 Fprivate
// The internally stored fitness value
fFitness: TFloat;
fWeConstrain: integer;
# F* v' s2 R% Z: U. d1 q/ pfBackConstrain: integer;
: {1 L% t( o7 yfTimeConstrain: integer;
; Z8 Z3 _; }: X, W  {0 Xprocedure SetFitness(const Value: TFloat);
6 d  _+ N  p+ P5 z# A; M5 m9 X! ]2 lfunction GetFitness: TFloat;
function GetWeConstrain: integer;
0 I* o  {  d0 Gprocedure SetWeConstrain(const Value: integer);
- V  v$ u4 _5 o# Y% qprocedure SetBackConstrain(const Value: integer);
( c5 S! x8 W6 L4 h: lfunction GetBackConstrain: integer;
function GetTimeConstrain: integer;
- v( \  t1 ^  n, r# k$ wprocedure SetTimeConstrain(const Value: integer);
; E* I% D/ y& ~6 l6 q8 v! lpublic
' i1 ?/ E+ ?& `& iproperty Fitness : TFloat read GetFitness write SetFitness;
property WeConstrain :integer read GetWeConstrain write SetWeConstrain;
property BackConstrain :integer read GetBackConstrain write SetBackConstrain;
* Z/ E6 n/ |! }- \7 ?property TimeConstrain :integer read GetTimeConstrain write SetTimeConstrain;
end;</P>
1 q8 U5 M$ e3 P1 Q+ Y6 g& \' I& k<P>TTSPIndividual = class(TIndividual, ITSPIndividual)
private
: `* i. d- D/ N$ ~$ k8 V// The route we travel
fRouteArray : ArrayInt;
fWeConstrain: integer;
fBackConstrain: integer;
fTimeConstrain: integer;
1 R+ s0 |& ~/ c4 B# Bfunction GetRouteArray(I: Integer): Integer;
procedure SetRouteArray(I: Integer; const Value: Integer);
  r! i1 ?( l; @1 U# qprocedure SetSteps(const Value: Integer);
4 b2 s' f$ `# m( S! Bfunction GetSteps: Integer;
( ]* n# S/ h3 Q- z( c  vfunction GetWeConstrain: integer;
, ]) y; D* ^( C; H( t! ^$ ^procedure SetWeConstrain(const Value: integer);
procedure SetBackConstrain(const Value: integer);
; _* X  z9 j( ?. x, L' K& T9 i& fprocedure SetTimeConstrain(const Value: integer);
function GetBackConstrain: integer;
4 c( }% A3 E! [+ H8 ifunction GetTimeConstrain: integer;
7 B! |4 [! S2 jpublic
# t; t: T, Q: U// Constructor, called with initial route size
0 E6 m7 o8 Q$ Z+ ~constructor Create(Size : TInt); reintroduce;
destructor Destroy; override;
property RouteArray[I : Integer] : Integer read GetRouteArray write SetRouteArray;
& G( W0 }5 _5 m% M: P0 R3 z' D// The number of steps on the route
property Steps : Integer read GetSteps write SetSteps;
6 m/ @4 j8 z0 [+ |! j. H3 Eproperty Fitness : TFloat read GetFitness write SetFitness;
property WeConstrain :integer read GetWeConstrain write SetWeConstrain;
property BackConstrain :integer read GetWeConstrain write SetBackConstrain;
2 ?4 C" c0 b1 {' Iproperty TimeConstrain :integer read GetTimeConstrain write SetTimeConstrain;
end;</P>
+ K+ l" N$ I' ?( B<P>TTSPCreator = class(TInterfacedObject, ITSPCreator)
2 u' |3 P) {9 B5 mprivate
// The Control component we are associated with
# @- K+ c! U* r) I, l4 CfController: ITSPController;
% i& d' r0 H4 t* _1 Vfunction GetController: ITSPController;
procedure SetController(const Value: ITSPController);
  p- v0 z0 _: i2 T) l0 |public
// Function to create a random individual
function CreateIndividual : IIndividual;
function CreateFeasibleIndividual: IIndividual;
, |' A+ v; w( K# O- w+ j- U+ q/ @property Controller : ITSPController read GetController write SetController;
end;</P>
<P>TKillerPercentage = class(TInterfacedObject, IKillerPercentage)
* \4 l# @$ B4 V: ^- l7 J6 T- dprivate
, o% I+ @1 X3 A" ~fPer: TFloat;
procedure SetPercentage(const Value: TFloat);
function GetPercentage: TFloat;
5 x! j! j" \3 h7 K7 [' Epublic
function Kill(Pop : IPopulation): Integer;
+ F) v; z0 T2 F$ ]// Percentage of population to be killed
property Percentage: TFloat read GetPercentage write SetPercentage;
  Q/ s* T0 ]0 P7 c" w4 J8 \  Dend;</P>
# C+ [# A" m: y& o1 {; q<P>TParentSelectorTournament = class(TInterfacedObject, IParentSelector)
public
/ u0 P( y$ e& T. `  Kfunction SelectParent(Population: IPopulation): IIndividual;
) w# e2 N9 q7 I" N6 |- @end;</P>
<P>TTSPBreederCrossover = class(TInterfacedObject, IBreeder)
/ e# Q4 F1 i% I. u8 i' M9 z1 Q8 ppublic
function BreedOffspring(PSelector: IParentSelector; Pop: IPopulation): IIndividual;
end;</P>
' e5 |. F) t) P) o. {: @' `<P>TTSPMutator = class(TInterfacedObject, ITSPMutator)
private
8 S5 p6 R% s; k; J* P3 a# Z+ _fTrans: TFloat;
fInv: TFloat;
procedure SetInv(const Value: TFloat);
6 `5 t5 d$ g, z" L, W7 _/ P$ z$ rprocedure SetTrans(const Value: TFloat);
. N: ]& @2 m0 u; S# y% \, C& Xfunction GetInv: TFloat;
function GetTrans: TFloat;
public
. W! Y+ G  Z' I( q% Cprocedure Mutate(Individual: IIndividual);
published
// Probability of doing a transposition
property Transposition: TFloat read GetTrans write SetTrans;
# Q" D+ h1 N8 v1 _" }. a( b// Probability of doing an inversion
property Inversion: TFloat read GetInv write SetInv;
' {& D5 V9 `9 @0 Kend;</P>
& y: y' e2 y! J+ g" C6 L! I! p<P>TTSPExaminer = class(TInterfacedObject, ITSPExaminer)
$ b# g( P# Q: l" P; d1 ]private
// The Control component we are associated with
/ w. I* `) b  |! Z- ?$ Z  ifController: ITSPController;
function GetController: ITSPController;
procedure SetController(const Value: ITSPController);
: _7 j7 x/ C- J8 s$ ^public
// Returns the fitness of an individual as a real number where 0 =&gt; best
% n# w' E! b8 Rfunction GetFitness(Individual : IIndividual) : TFloat;
, O& }* m4 ?/ s+ Dproperty Controller : ITSPController read GetController write SetController;
' k6 P. ^) }' L' v2 B) d" d: b: iend;</P>
6 n- v' P0 o. I3 V<P>TPopulation = class(TInterfacedObject, IPopulation)
private
. G+ }% o' D1 q' r0 \// The population
: f+ C6 r; X! s: y3 ZfPop : TInterfaceList;
4 d( M6 F. P. j// Worker for breeding
fBreeder: IBreeder;
// Worker for killing
fKiller: IKiller;
// Worker for parent selection
4 C( G2 i' p6 BfParentSelector: IParentSelector;
! [( J3 Z( f6 D# T# q* M// Worker for mutation
fMutator: IMutator;
// Worker for initial creation
% w; n; h. V* x& b! SfCreator: ICreator;
1 \4 q' g3 Y! b% O4 z1 n// Worker for fitness calculation
fExaminer: IExaminer;
0 f. b, H' q2 U9 l# H// On Change event
3 z% B6 o+ S4 rFOnChange: TNotifyEvent;
procedure Change;
// Getters and Setters
2 C- u+ P. Y. {1 ?function GetIndividual(I: Integer): IIndividual;
: e" s4 F( |* b9 n$ ^+ W" D: sfunction GetCount: Integer;
function GetBreeder: IBreeder;
function GetCreator: ICreator;
  d  I4 @" |  c/ g5 `1 Kfunction GetExaminer: IExaminer;
function GetKiller: IKiller;
function GetMutator: IMutator;
3 h# ]6 K: @' H9 S0 A3 R. Jfunction GetOnChange: TNotifyEvent;
7 |! w4 p+ f/ d2 n0 Tfunction GetParentSelector: IParentSelector;
5 e! W6 R7 A/ L8 e( oprocedure SetBreeder(const Value: IBreeder);
procedure SetCreator(const Value: ICreator);
procedure SetExaminer(const Value: IExaminer);
7 d' c/ D, t- ~procedure SetKiller(const Value: IKiller);
& f! |4 \# N: k; A& p) v) mprocedure SetMutator(const Value: IMutator);
procedure SetOnChange(const Value: TNotifyEvent);
5 i! A" `- W  F+ `procedure SetParentSelector(const Value: IParentSelector);
// not interfaced
. ?9 Y3 h2 F3 x/ |/ u( sprocedure DanQuickSort(SortList: TInterfaceList; L, R: Integer; SCompare: TInterfaceCompare);
0 G$ W9 t. W/ w( K! r, Tprocedure Sort(Compare: TInterfaceCompare);
' U4 a7 E( ^% l, b  r. R3 xprotected
( t6 }9 W3 w" E% P2 D// Comparison function for Sort()
function CompareIndividuals(I1, I2: IIndividual): Integer;
// Sort the population
# N" [- k( v" ^1 z" p0 lprocedure SortPopulation;
public
// The constructor
' Z5 w& b, y5 Cconstructor Create;
! z2 {6 l1 c7 G// The destructor
3 F% f# w" ]  [2 s& [% Sdestructor Destroy; override;
// Adds an individual to the population
procedure Add(New : IIndividual);
' T  T7 a$ g9 _// Deletes an individual from the population
3 J% G2 u6 M- a$ _) E4 Lprocedure Delete(I : Integer);
// Runs a single generation
: }- H" N4 p4 O2 U  n9 Fprocedure Generation;
// Initialise the population
" A$ I3 a, Z4 Mprocedure Initialise(Size : Integer);
# ?0 b. D2 v) [3 U% E( y// Clear ourselves out
procedure Clear;
// Get the fitness of an individual
$ H: C+ `9 z% ]5 Y5 S6 k, _function FitnessOf(I : Integer) : TFloat;
# F3 B; E1 u5 e7 o// Access to the population members
property Pop[I : Integer] : IIndividual read GetIndividual; default;
// The size of the population
; A& ^/ X: R0 N9 uproperty Count : Integer read GetCount;
! `- ]; T7 N, q& ^9 L+ d0 dproperty ParentSelector : IParentSelector read GetParentSelector write SetParentSelector;
1 G' O  c( o( v/ ]5 Z, Mproperty Breeder : IBreeder read GetBreeder write SetBreeder;
property Killer : IKiller read GetKiller write SetKiller;
property Mutator : IMutator read GetMutator write SetMutator;
property Creator : ICreator read GetCreator write SetCreator;
) K1 e; p! b5 `# m7 [* E: Oproperty Examiner : IExaminer read GetExaminer write SetExaminer;
// An event
property OnChange : TNotifyEvent read GetOnChange write SetOnChange;
' v1 A$ j5 e9 o/ S4 h1 I$ o. aend;</P>
<P>TTSPController = class(TInterfacedObject, ITSPController)
; s7 N0 c8 I& O, B  h" w, [' ~private
& n7 ?) B9 g7 G4 \% [* ^* v5 `fXmin, fXmax, fYmin, fYmax: TFloat;
& t! h  G. o' p  b( t& B! N; ?{ The array of 'cities' }
fCities : array of TPoint2D;
{ The array of 'vehicles' }
. \0 f- y& y: j2 w3 |fVehicles : array of TVehicle;
4 d7 z! S$ S/ ?5 U" s{ The array of 'vehicle number' }
5 E' K7 l  o3 R* wfNoVehicles : ArrayInt;/////////////////////
% P5 m0 F. _+ `9 _) M% U% c1 u{ The number of 'new cities' }
fCityCount: Integer;
{ The number of 'old cities' }
& ?2 ^& R, z# E7 d) efoldCityCount: Integer;
% ^6 `" M% S' [8 {" e0 W2 ]{ The number of 'travelers' }
. b  O  w5 P/ x9 I' efTravelCount:Integer; ///////////////////////
{ The number of 'depots' }
- O2 ^8 d- e5 C' a, X8 q$ LfDepotCount:Integer; ///////////////////////
{ Getters... }
* ^8 _7 j; s( y" t& Q' Kfunction GetCity(I: Integer): TPoint2D;
function GetNoVehicle(I: Integer): TInt;
function GetCityCount: Integer;
5 B4 u+ ~4 d( qfunction GetOldCityCount: Integer;
function GetTravelCount:Integer;
2 {+ U4 w- A# V  x: [function GetDepotCount:Integer;
function GetXmax: TFloat;
. k) a& p: C: q+ v3 r! d6 O/ jfunction GetXmin: TFloat;
$ p3 t$ z' B/ v/ z% I* l) |function GetYmax: TFloat;
function GetYmin: TFloat;
{ Setters... }
procedure SetCityCount(const Value: Integer);
procedure SetOldCityCount(const Value: Integer);
procedure SetTravelCount(const Value: Integer); /////////////
procedure SetDepotCount(const Value: Integer); /////////////
procedure SetXmax(const Value: TFloat);
, p! ]: d4 n! |4 j3 Z. |; f0 |" o$ Aprocedure SetXmin(const Value: TFloat);
/ U) v8 x: k$ Z9 d: _procedure SetYmax(const Value: TFloat);
procedure SetYmin(const Value: TFloat);
$ N8 b+ a7 Z* V0 Y# z/ e& efunction TimeCostBetween(C1, C2: Integer): TFloat;
function GetTimeConstraint(Individual: IIndividual): TInt;
- J9 T5 \( q0 Ffunction DateSpanToMin(d1, d2: TDateTime): integer;
function GetVehicleInfo(routeInt: Tint): integer;
procedure writeTimeArray;
procedure writeCostArray;
4 I5 f. L, v' Apublic
7 M9 X( c. l( _, M$ V1 ]! u& G{ The constructor }
# h. }  p) z& Yconstructor Create;
{ The destructor }
5 F" A/ X7 B0 u) J, B3 v; r1 I5 Ddestructor Destroy; override;
/ f1 u" c5 u5 ^' ~* {% w- ?; k2 Z{ Get the distance between two cities }
function DistanceBetween(C1, C2 : Integer) : TFloat;
+ m, H: T. e( H: {- B! l- N{ Get the cost between two cities }
2 ~7 C9 T; D5 ?5 g. y: @% Efunction CostBetween(C1, C2: Integer): TFloat;</P>
) V3 D2 V. U7 @! ^* P<P>function GetWeightConstraint( Individual: IIndividual): TInt;</P>
7 W& P( l8 G5 H3 i, `9 p<P>function GetBackConstraint( Individual: IIndividual): TInt;
{ Places the cities at random points }
procedure RandomCities;
! @* I, v4 A4 s" q/ [{ Area limits }
7 [% P( ~/ d% Wproperty Xmin: TFloat read GetXmin write SetXmin;
property Xmax: TFloat read GetXmax write SetXmax;
/ d) `; n5 q: C0 j* A  K1 ?6 mproperty Ymin: TFloat read GetYmin write SetYmin;
property Ymax: TFloat read GetYmax write SetYmax;
/ i# C- w9 e* L- H5 R6 s; }{ Properties... }
- C" w/ i) a& `property CityCount : Integer read GetCityCount write SetCityCount;
property OldCityCount : Integer read GetOldCityCount write SetOldCityCount;
3 d1 o! s) R7 mproperty TravelCount : Integer read GetTravelCount write SetTravelCount; ///////////
3 g% }" Y1 I' F; jproperty DepotCount : Integer read GetDepotCount write SetDepotCount; ///////////
9 e; }" @! K+ R; f0 n{ Access to the cities array }
property Cities[I : Integer] : TPoint2D read GetCity;
property NoVehicles[I : Integer] : TInt read GetNoVehicle; ///////////////
1 O8 l" R$ n  P; j, e. Rend;</P>
0 a3 T  O" _: |* h, `<P>implementation</P>
( e+ i; Y. y0 Q& ^5 `' Q<P>uses
Math;</P>
<P>{ TIndividual }</P>
9 B. b2 H+ l6 l<P>function TIndividual.GetFitness: TFloat;
9 H' q1 j" O0 m9 b, X2 hbegin
* g7 G( s; q0 Q; Cresult := fFitness;
end;</P>
! {6 L, w% T2 ]4 a. u<P>function TIndividual.GetWeConstrain: integer;
begin
result := fWeConstrain;
end;</P>
<P>function TIndividual.GetBackConstrain: integer;
begin
6 ^9 X3 I+ }9 |% r- oresult := fBackConstrain;
! ?/ U; R  |0 P4 ^. Dend;</P>
<P>function TIndividual.GetTimeConstrain: integer;
begin
0 O* }$ ~# L# C* q0 T/ W8 C, iresult := fTimeConstrain;
2 v9 j# p( C8 P. |- H) O. N8 k# nend;</P>
<P>procedure TIndividual.SetBackConstrain(const Value: integer);
+ l5 Y2 v% o; _, [8 U% Dbegin
fBackConstrain := Value;
end;</P>
<P>procedure TIndividual.SetFitness(const Value: TFloat);
( _3 }; J# w; \' r; ]begin
fFitness := Value;
8 h$ h1 A! {& A6 ~' x- ]$ j2 A9 Jend;</P>
<P>procedure TIndividual.SetWeConstrain(const Value: integer);
begin
fWeConstrain := Value;
* n5 |$ Q! k3 e/ s5 o) z! qend;</P>
<P>procedure TIndividual.SetTimeConstrain(const Value: integer);
1 v9 B5 ]5 |  Ubegin
fTimeConstrain := Value;
end;</P>
4 ~# z# @8 P, R( b* T% J3 ]7 r<P>{ TTSPIndividual }</P>
/ {0 S. w" u% |3 P+ Y<P>constructor TTSPIndividual.Create(Size: TInt);
begin
  R$ w' @' s6 W4 yInherited Create;
+ c# ^, A: H- t* |3 ?% Z2 BSetLength(fRouteArray, Size);
// fSteps := Size;
; M5 E3 B! E/ g* H2 Send;</P>
<P>destructor TTSPIndividual.Destroy;
begin
SetLength(fRouteArray, 0);
$ ^! f- b, |$ |. [inherited;
end;</P>
<P>function TTSPIndividual.GetRouteArray(I: Integer): Integer;
6 k: I# g) M' H+ ~, k* I- u0 M, nbegin
( y9 b3 S3 p7 \% ]2 D  H+ xresult := fRouteArray[I];
6 X) ~! N6 Z' A" j5 x0 X; v! jend;</P>
<P>function TTSPIndividual.GetSteps: Integer;
; |% u4 F& Q+ T' Ibegin
result := Length(fRouteArray);
9 a0 L! _2 W( D' Kend;</P>
& W9 e+ z# ^, Q! ~- _5 K<P>procedure TTSPIndividual.SetSteps(const Value: Integer);
begin
SetLength(fRouteArray, Value);
: _1 F0 Z  q2 G; dend;</P>
<P>procedure TTSPIndividual.SetRouteArray(I: Integer; const Value: Integer);
begin
fRouteArray[I] := Value;
2 @1 I4 i  ?+ X) Y9 Qend;</P>
<P>function TTSPIndividual.GetWeConstrain: integer;
9 a; J9 ?# }/ \0 Y" P  N" j( d/ vbegin
result := fWeConstrain;
: R5 `8 X8 I4 \end;</P>
+ k7 Z$ ?% a1 S<P>function TTSPIndividual.GetBackConstrain: integer;
7 |5 C9 C5 f2 X8 ]  Bbegin
, ^* b  c  o1 J: t7 R3 Zresult := fBackConstrain;
end;</P>
$ r4 u# z* e8 A, u<P>function TTSPIndividual.GetTimeConstrain: integer;
  C/ |" T4 _/ q, P# Lbegin
result := fTimeConstrain;
) a. Q( J5 u1 U$ l: wend;</P>
<P>procedure TTSPIndividual.SetWeConstrain(const Value: integer);
begin
fWeConstrain := Value;
8 h$ K" B5 |" J3 i! jend;</P>
1 p- n7 C7 K4 l$ \' v4 u6 c* s( r<P>procedure TTSPIndividual.SetBackConstrain(const Value: integer);
+ W+ r$ j( R7 A2 Rbegin
3 H6 r3 E9 K4 [9 k) UfBackConstrain := Value;
end;</P>
2 R* Y8 o& E0 R2 @8 R: j<P>procedure TTSPIndividual.SetTimeConstrain(const Value: integer);
, l2 ]9 q/ N. T1 F5 Qbegin
, ^  g6 R1 g* P- X* [fTimeConstrain := Value;
' L) S2 v& ?- ?/ U( Zend;</P>
( f. @" U: s0 |( o5 I<P>{ TTSPCreator }</P>
: m1 l& m0 ?) a5 E$ r- Z<P>function TTSPCreator.CreateIndividual: IIndividual;
: Z& Y5 c7 K# M- Y+ s# fvar
7 P( o! Y" c+ v0 I, Y" L7 F0 dNew: ITSPIndividual;
( m5 q8 C# c( ?i, j, Top, Temp : Integer;
1 T# w3 E5 w9 p& }; w" o/ t//trav:integer;
begin
& ]# y4 d. y: O8 a1 ]: B4 {1 O// Get the number of cities
# o, f$ d! D9 h" a4 HTop := fController.CityCount;
/ c1 J! B- G4 O$ b// Create the new individual
New := TTSPIndividual.Create(Top);
5 U+ i' ^+ h5 p! b& l$ x// Initialise it with a sequential route
for i := 0 to Top - 1 do
  e( d. ~$ b" J" S9 Z- _# |New.RouteArray := i;
// Shuffle the route
) E8 _# e! G( w9 |6 h7 }for i := Top - 1 downto 1 do
begin
9 V8 m3 W1 l' V! R+ y$ w# `j := Random(i);
9 Z& C/ c7 c7 kTemp := New.RouteArray[j];
New.RouteArray[j] := New.RouteArray;
New.RouteArray := Temp;
% {+ s/ [' U0 c+ o& i3 v$ U9 Send;
result := New;
9 Y; j3 B! o( B  xend;</P>
<P>function TTSPCreator.CreateFeasibleIndividual: IIndividual;
0 ?2 z9 l8 X: L" g5 E, P2 z0 Ivar
; p6 j+ w0 H( Z9 P" g! ONew: ITSPIndividual;
2 E6 v* u1 V* X' g1 ]i, j, Top, Temp : Tint;
Msg:TMsg;
begin
// Get the number of cities
Top := fController.CityCount;
9 K! n" Y4 p  H6 P' F4 M// Create the new individual
New := TTSPIndividual.Create(Top);
// Initialise it with a sequential route
repeat
6 B$ F  i6 w7 g, Q- Z# Ubegin//////////////////////////////////
for i := 0 to Top - 1 do
New.RouteArray := i;
: T7 B2 L" _3 I3 p. O5 R! f! C// Shuffle the route
for i := Top - 1 downto 1 do
begin
j := Random(i);
1 G( }! D% k+ E- l% f( V) |Temp := New.RouteArray[j];
New.RouteArray[j] := New.RouteArray;
) e$ h+ C$ b& q8 GNew.RouteArray := Temp;
end;
//process message sequence//////////
while PeekMessage(Msg,0,0,0,1) do///
begin ///
if Msg.Message&lt;&gt;18 then ///
begin ///
TranslateMessage(Msg); ///
6 n( v& p# v7 M0 N0 r. u0 r% ADispatchMessage(Msg); ///
4 U. ~5 ]3 @# p  ?4 \6 ~end; ///
1 Y& ~- v$ p  \9 X4 |/ rend; ///
////////////////////////////////////
end
until (fController.GetWeightConstraint(New)=0)and(fController.GetBackConstraint(New)=0);</P>
<P>result := New;
end;</P>
<P>function TTSPCreator.GetController: ITSPController;
begin
result := fController;
end;</P>
<P>procedure TTSPCreator.SetController(const Value: ITSPController);
begin
fController := Value;
end;</P>
9 ^2 R, S4 A. }* ^! Y3 r<P>{ TKillerPercentage }</P>
<P>function TKillerPercentage.GetPercentage: TFloat;
begin
  l# T! Q- J" ?+ r; Lresult := fPer;
end;</P>
<P>function TKillerPercentage.Kill(Pop: IPopulation): Integer;
var
KillCount, i : Integer;
begin
% }% P  }7 i" c' c// Work out the number we have to kill
KillCount := Floor(Pop.Count * (fPer / 100));
" l$ L  l1 \* ?. P// Delete the worst individuals - assuming the population is sorted
for i := 1 to KillCount do
7 z% @+ b2 h6 B) i% c$ oPop.Delete(Pop.Count - 1);
// Return the number killed
Result := KillCount;
end;</P>
0 S  W* Y6 X" ^& q% y8 y* w<P>procedure TKillerPercentage.SetPercentage(const Value: TFloat);
begin
fPer := Value;
* ~1 ~1 _, Q1 K. f0 V* Zend;</P>
, O$ ?& M1 |  P  a8 F<P>{ TParentSelectorTournament }</P>
<P>function TParentSelectorTournament.SelectParent(
( U) _7 F& x% GPopulation: IPopulation): IIndividual;
) W9 q: T9 {5 jvar
i1, i2 : Integer;
3 M: W. x7 A1 }# ~3 y! ~0 T2 Qbegin
' x# A3 S! d# V% V1 Y) V// Select a random individual
i1 := Random(Population.Count);
2 M, Z3 @' s1 I* |+ ^5 U; v" z// Select a *different* random individual
' M, J7 ^3 Q+ C( x  ~repeat
i2 := Random(Population.Count);
until i1 &lt;&gt; i2;
// Hold the tournament and return the fittest of the two
2 |% a3 l4 s/ }* B0 M0 zif Population.FitnessOf(i1) &lt; Population.FitnessOf(i2) then
, q- J; f- _& Q2 h0 M! w8 s/ S0 V; RResult := Population[i1]
else
% V7 l' v" H; k! Y4 X$ BResult := Population[i2];
' ~" G! \5 I8 R- z6 R+ rend;</P>
) t' G9 U" M8 R9 w  M" }9 q2 ~. }3 ?<P>{ TTSPBreederCrossover }</P>
<P>function TTSPBreederCrossover.BreedOffspring(PSelector: IParentSelector;
: |+ Z7 P" ]0 B7 i  |- ~3 iPop: IPopulation): IIndividual;
4 x3 ]( g' |& Pvar
# Q) i- B4 w$ C  x/ W6 e. E9 ?Child, Mom, Dad, Parent1, Parent2 : ITSPIndividual;
i, j, p : Integer;</P>
0 v' H% e; V/ v/ j; O<P>function AlreadyAssigned(City, x : Integer) : Boolean;
# v* M  a! C$ W8 s  c4 Fvar
% ~# S% \, J. H) T" h2 py : Integer;
Found : Boolean;
begin
Found := False;
+ E: b; P: u5 }- {7 afor y := 0 to x - 1 do
begin
if Child.RouteArray[y] = City then
% N9 r) l" P1 D  ^% ubegin
Found := True;
* R* I: x4 M& C8 \% d5 pBreak;
6 j& p2 T2 G# }6 Aend;
" o1 q8 c+ o8 M6 s7 cend;
  f5 ^. G* V% GResult := Found;
2 g9 t4 T) K$ g9 [* r/ Dend;</P>
% L3 B+ f- f# C2 y<P>begin
1 r; o$ y$ g. r6 J& S$ A// Select a some parents...
Mom := PSelector.SelectParent(Pop) as ITSPIndividual;
# _3 Z0 P- h9 k. p# ?: o) P! j  hDad := PSelector.SelectParent(Pop) as ITSPIndividual;
& C& R; |7 R6 y( t5 q5 ~. R+ W  g// Create a child
. D- ?( d' E, G2 x' e2 L" a) z: gChild := TTSPIndividual.Create(Mom.Steps);
// Copy the route from parents to child
for i := 0 to Child.Steps - 1 do
- w: \6 {" _- k' Ebegin
& M; l* `! Y2 H  c" E$ y" ]// Choose a parent at random
p := Random(2);
1 |0 F. P/ ]8 E( ^if p = 0 then
begin
! \6 Y$ E- C( ], U$ o% s5 BParent1 := Mom;
1 G  t+ A* m& D/ D: S9 AParent2 := Dad;
9 X( Q" W) `( v2 zend else
begin
Parent1 := Dad;
6 X1 j' @1 h6 R9 l9 l8 p$ s, l+ YParent2 := Mom;
end;
, v/ k; y7 c7 m5 C5 Z) S; Wif not AlreadyAssigned(Parent1.RouteArray, i) then
begin
// Use city from Parent 1 unless used already
& F7 Q( \! E* h* \0 yChild.RouteArray := Parent1.RouteArray;
end else
" d- X, Q% D% e5 D$ Qif not AlreadyAssigned(Parent2.RouteArray, i) then
+ y1 J! v& e) O5 Mbegin
( ^, H: s2 K0 q2 u$ q// Otherwise use city from Parent 2 unless used already
- Z8 ]. _9 U% }' s# ^& dChild.RouteArray := Parent2.RouteArray;
end else
/ \- }1 Q. t( r5 Pbegin
// If both assigned already then use a random city
- ]+ R; c: p& L% E, m. f" [: Qrepeat
" i/ {1 d6 {; t9 [' r$ Jj := Random(Child.Steps);
until not AlreadyAssigned(j, i);
$ B' e7 Z1 I  G2 b& |& iChild.RouteArray := j;
end;
end;
// Return the child
Result := Child;
( Z9 L) r6 m$ }/ Y6 P  Wend;</P>
- e; @1 V1 D" ]0 ?! O* m) b<P>{ TTSPMutator }</P>
<P>function TTSPMutator.GetInv: TFloat;
6 s' V: |& `1 {" U; Ibegin
. w" d0 q# w  k- H. H8 vresult := fInv;
end;</P>
<P>function TTSPMutator.GetTrans: TFloat;
begin
result := fTrans;
+ U( X% j# ?$ X+ r1 tend;</P>
<P>procedure TTSPMutator.Mutate(Individual: IIndividual);
var
  A) I7 S( S4 m: g8 [% [4 zP: Double;
i, j, t : Integer; Start, Finish : Integer;
begin
" T+ B1 L1 h# Wwith Individual as ITSPIndividual do
begin
// Should we do an inversion?
* ~5 J& ^9 T0 k2 x3 g  Z7 e) q7 pP := Random * 100;
if P &lt; FTrans then
5 U9 J6 G+ |/ n) tbegin
( h# `) c( g' H/ R' I8 G) {+ x// Do an inversion (i.e. swap two cities at random)
6 _0 x& x- R$ `6 o& c5 D5 o// Choose first city
! A3 G$ B4 u& O/ Q8 p* k5 `i := Random(Steps);
& D1 \" j& q% Y7 ?( R' Z& M2 X2 @// Choose a second city
repeat
j := Random(Steps);
until i &lt;&gt; j;
1 B: g2 c5 c2 A" ]: p$ |2 C// Swap them over
: v- p1 y- I, z9 g  _1 G1 yt := RouteArray;
% M0 r6 Y  c0 j0 J( |; v2 v0 A" ]RouteArray := RouteArray[j];
RouteArray[j] := t;
end;
8 n0 k3 L$ e' H' ]: b2 \" L// Should we do a transposition?
1 J$ s- {, X( v6 ?$ L4 [1 s  z0 TP := Random * 100;
8 B) o/ S; S1 ?" F% Wif P &lt; FInv then
- J$ u. ?6 }2 z. x8 qbegin
; j4 P6 O  H  U% a7 b// Do a transposition (i.e. reverse a sub-route)
4 X- Z, O% V% I8 g2 y8 G0 a// Choose random start and finish points
Start := Random(Steps - 1);
Finish := Start + Random(Steps - Start);
: W" k: u& i+ p// Reverse the sub-route
for i := 0 to Floor((Finish - Start) / 2) do
begin
t := RouteArray[Start + i];
RouteArray[Start + i] := RouteArray[Finish - i];
% N4 Q2 {3 E: X4 S- qRouteArray[Finish - i] := t;
end;
9 d  M/ ]" B8 j/ w7 n- K  b4 y) fend;
end;
5 x% V/ `9 }" @$ Y3 cend;</P>
& |: `* Z5 q& z$ @: M3 D. Y<P>procedure TTSPMutator.SetInv(const Value: TFloat);
begin
; _' S& n) k0 N+ TfInv := Value;
end;</P>
) Q, a( t9 b+ b  f" u% }<P>procedure TTSPMutator.SetTrans(const Value: TFloat);
begin
fTrans := Value;
end;</P>
<P>{ TTSPExaminer }</P>
<P>function TTSPExaminer.GetController: ITSPController;
1 f- `+ y* c0 Z/ |4 I9 T/ `begin
result := fController;
" q3 F8 e- Y8 T" y# o' m9 {! Fend;</P>
<P>function TTSPExaminer.GetFitness(Individual: IIndividual): TFloat;
var
i , weightConstraint, backConstraint : TInt;
Distance , penaltyW, penaltyB : TFloat;
7 ~9 X) k( X# x5 C) @3 Z3 \Indi : ITSPIndividual;
# F4 |- @( d0 Y7 o3 Q; p) xbegin
( u8 o* S+ t0 p: b3 ^  u' JIndi := Individual as ITSPIndividual;
4 e+ {& q& w. m# ^5 ]* oDistance := 0;
" S) q) c; Q7 A; l9 C& y, tpenaltyW:=FormGaPara.EditWeightConstrain.Value;
penaltyB:=FormGaPara.EditBackConstrain.Value;
for i := 0 to Indi.Steps - 2 do
begin
Distance := Distance + fController.DistanceBetween(Indi.RouteArray, Indi.RouteArray[i + 1]);
  H! M2 z$ g; V" U$ Z3 f" }end;
Distance := Distance + fController.DistanceBetween(Indi.RouteArray[Indi.Steps - 1], Indi.RouteArray[0]);
8 ~7 o" o; @* Q% o8 V! c; U7 UWeightConstraint:=fController.GetWeightConstraint(Indi);
backConstraint:=fController.GetBackConstraint(Indi);
5 V, K$ l" @/ s8 L9 q4 ~Indi.WeConstrain:=WeightConstraint;
( q8 P# d; _& R$ j+ \# ]' m; `Indi.BackConstrain:=backConstraint;
Result := Distance+penaltyW*weightconstraint+penaltyB*backConstraint;
end;</P>
& U9 W" v( x$ {7 y5 D% o7 M# Q<P>procedure TTSPExaminer.SetController(const Value: ITSPController);
0 n# A! K. W/ W  v* y) xbegin
, j4 r1 [  S. W1 K+ yfController := Value;
  M# u) f# X: `# Y, w, fend;</P>
<P>{ TPopulation }</P>
<P>constructor TPopulation.Create;
" L) ?& E# ^& F9 n' {begin
inherited;
' p! `& N" S- z. J* o8 v( w2 TfPop := TInterfaceList.Create;
' _6 e* C" Z  p  ~4 gend;</P>
  G; _4 g8 `- V4 @' D) Z  M: p<P>destructor TPopulation.Destroy;
' S  V+ w2 T6 dbegin
fPop.Free;
inherited;
  }  O) A: z" x8 I, M* @end;</P>
8 D' d: x0 O1 u8 `4 ~' u( D8 e<P>procedure TPopulation.Add(New: IIndividual);
0 X' q9 M2 D- C$ g" ubegin
fPop.Add(New);
end;</P>
<P>procedure TPopulation.Clear;
begin
) x: _7 J, m8 Y  `* G, DfPop.Clear;
- J2 u! Y/ \$ C7 X: \end;</P>
<P>function TPopulation.CompareIndividuals(I1, I2: IIndividual): Integer;
7 O" X7 ?7 v2 {" R3 O8 \2 v! dvar
A, B, D : TFloat;
( `9 D7 Q. r$ Gbegin
// Get the difference between the two individuals (real number)
4 c1 o3 ^* W& MA := I1.Fitness;
B := I2.Fitness;</P>
9 a% T2 {8 f7 x( `+ v<P>D := A - B;</P>
/ z. ~8 r/ F) w* w! ~<P>// Quickest way to convert that to an integer is...
if D &gt; 0 then
Result := 1
else if D &lt; 0 then
: l" l2 g' Q* i. b, b3 {Result := -1
else
Result := 0;
6 h# y. q; K' ?' Z5 ]# Vend;</P>
! }  z) n* O6 B# }<P>procedure TPopulation.Delete(I: Integer);
: L0 u# p7 U1 {# B3 \3 Rbegin
( V) K4 S/ J; g! N( IfPop.Delete(I);
- {) c- E- _3 \- j% g3 K; Uend;</P>
<P>function TPopulation.FitnessOf(I: Integer): TFloat;
* N0 }0 C1 A# o) Z% vbegin
result := Pop[I].Fitness;
end;</P>
<P>procedure TPopulation.Change;
  j. L" i" t& [' W( }  d- `begin
if Assigned(fOnChange) then
# z- O; Y  X& p. l( gFOnChange(Self);
end;</P>
- |  m8 f" Z4 W8 X8 H<P>procedure TPopulation.Generation;
. [# {6 B+ _9 _7 A3 I  d4 L# b2 Uvar
1 P# @/ L4 s" t- ?. n0 d; AReplace, i : Integer;
New : IIndividual;
0 f9 ^* y9 G/ f8 ]* abegin
: Z# s, D9 c' X" D$ b// Kill some of the population
Replace := fKiller.Kill(Self);</P>
<P>for i := 1 to Replace do
7 c' }" |5 ~7 N; V1 e/ nbegin
2 D4 I; M1 P) H$ h% c4 P// Breed a new individual
- o! ?' \. d& V/ hNew := fBreeder.BreedOffspring(fParentSelector, Self);
// Perform some mutation on the individual
. [) G3 e9 I6 G/ {- D- p! D& q; a! D2 ?FMutator.Mutate(New);
// Get the fitness of the new individual
2 z3 f+ [" c  E. n" INew.Fitness := fExaminer.GetFitness(New);
// Add it to the population
Add(New);
end;
& f  \- \* h! d, N, ^9 B// Sort the population into fitness order where first &lt;==&gt; best
4 Q, F9 Q' B" s3 vSortPopulation;</P>
& f( i5 q+ t" L  k; j, i% P<P>Change;
, f& w3 X$ u) K( d6 Mend;</P>
- I" I0 i$ O$ _2 I$ X<P>function TPopulation.GetBreeder: IBreeder;
begin
" Y0 P, _& Z& {# aresult := fBreeder;
. t7 j0 s# q" B- t, z  z9 bend;</P>
<P>function TPopulation.GetCount: Integer;
begin
# h9 X- y+ i  z: Z1 }. X+ sresult := fPop.Count;
end;</P>
6 H) h7 ]" Y1 n4 L9 |9 _1 h<P>function TPopulation.GetCreator: ICreator;
8 e3 B+ G  R: j( A0 b1 S# J  dbegin
result := fCreator;
end;</P>
5 g- ^% {( M! P0 z9 f! D! N<P>function TPopulation.GetExaminer: IExaminer;
begin
result := fExaminer;
$ _% Y& d4 d9 R9 d/ i- lend;</P>
: N/ U( N+ x, H1 q( Y4 P- b<P>function TPopulation.GetIndividual(I: Integer): IIndividual;
7 l. [6 z- M( ?0 jbegin
1 K; U& Z7 M) E5 `: Y; I$ l* sresult := (fPop[I] as IIndividual);
8 T+ M$ G: u/ I/ P0 uend;</P>
7 c' u% G7 J- V8 s% i, \  o<P>function TPopulation.GetKiller: IKiller;
begin
result := fKiller;
" V7 P  D0 R4 Send;</P>
! [, d# s" ?/ e% I<P>function TPopulation.GetMutator: IMutator;
5 N2 F. y1 z( u: `3 r. Nbegin
( W3 k! |% g( f% d0 hresult := fMutator;
$ m- H! E3 M' u- A! ]: rend;</P>
<P>function TPopulation.GetOnChange: TNotifyEvent;
3 n1 b) R+ O9 b4 Q9 ]) mbegin
2 O, }0 X& a4 ]( Jresult := fOnChange;
) n: R- w- Q0 C9 v* Mend;</P>
<P>function TPopulation.GetParentSelector: IParentSelector;
9 e7 t' K7 ^/ @$ Obegin
' D  o# s: k: M* w. l$ W; ^- G- u$ iresult := fParentSelector;
end;</P>
<P>procedure TPopulation.Initialise(Size: Integer);
var
* l" @, V" ?4 r0 p6 P! `# N( ri,feasibleCount: Integer;
New: IIndividual;
2 Q; }4 S- J7 Zbegin
1 y" A* B. s. \- U2 L  GfeasibleCount:=round(size*(FormGaPara.EditFeasible.Value)/100);
//feasibleCount:=1;
// Clear out the old stuff
5 L! N- X4 P' h5 cClear;
1 Z* U# P5 ?9 C4 I// Set the capacity first to save about 12 nanoseconds ;o)
6 t/ k/ V1 b' e$ d/ {1 LfPop.Capacity := Size;
& R3 d2 x0 @# T9 k3 e2 Y5 {// Create the appropriate number of individuals
for i := 1 to feasibleCount do
begin
4 W. B7 z9 b$ J7 x// Create the individual
1 L* M$ r6 O+ G, lNew := fCreator.CreateFeasibleIndividual;
// Get the fitness of the new individual
New.Fitness := fExaminer.GetFitness(New);
4 ]8 o" A; h" l/ r// Add to the population
1 k  k$ D2 d5 W* N. yAdd(New);
end;
- P, F6 V3 H4 d% Q/ n8 Qfor i := feasibleCount+1 to Size do
$ C4 t  L; `/ sbegin
2 o4 x8 N' g" h) v, d1 P( o. X// Create the individual
New := fCreator.CreateIndividual; ////////
2 e8 ?- Z+ D4 o) t# X// Get the fitness of the new individual
New.Fitness := fExaminer.GetFitness(New);
( q7 r' u8 ~+ Q( }// Add to the population
Add(New);
end;
( h/ g% |& \% S+ w0 RSortPopulation;
Change;
3 m& m0 |" F2 g3 J1 xend;</P>
<P>procedure TPopulation.SetBreeder(const Value: IBreeder);
; Y4 N$ b* j) z4 }5 x( p4 K% Mbegin
fBreeder := Value;
5 }8 T6 q3 e5 q% K: Pend;</P>
- a4 N2 {- ?/ x<P>procedure TPopulation.SetCreator(const Value: ICreator);
$ \& N- Q% w- e3 {begin
fCreator := Value;
end;</P>
<P>procedure TPopulation.SetExaminer(const Value: IExaminer);
begin
# E# k$ B* E! N  n- o( N. `4 U$ {+ ZfExaminer := Value;
9 A- e0 T. _$ k! ]$ T7 lend;</P>
' u: |: o7 g7 z& g<P>procedure TPopulation.SetKiller(const Value: IKiller);
begin
fKiller := Value;
end;</P>
3 u1 [4 Z1 n4 V! ~- x% ]. ?) a' |<P>procedure TPopulation.SetMutator(const Value: IMutator);
% g7 n1 b5 S* o& ~5 ubegin
# f; {& M( B( T; u6 B* p; DfMutator := Value;
end;</P>
<P>procedure TPopulation.SetOnChange(const Value: TNotifyEvent);
3 m; ]6 ^9 T& n8 Sbegin
fOnChange := Value;
end;</P>
" V% b% u- C/ U7 @. C<P>procedure TPopulation.SetParentSelector(const Value: IParentSelector);
begin
& I6 Y5 D# v* y+ x3 M- NfParentSelector := Value;
' Y6 J. L- M9 t; o) jend;</P>
, j4 P+ ^. O) ?# T4 B) u<P>procedure TPopulation.DanQuickSort(SortList: TInterfaceList; L, R: Integer;
4 `+ W0 [/ h; F+ a7 T2 ?SCompare: TInterfaceCompare);
var
, e% Y# _% _3 o6 i2 Y! i7 g- ~I, J: Integer;
6 r+ ~' n: i: ^$ b3 G0 i0 L" t1 SP: IIndividual;
begin
repeat
5 H+ r, i8 R# G7 O- |/ vI := L;
" ]1 }# @5 p" r) S/ i% }+ G: f# \J := R;
P := SortList.Items[(L + R) div 2] as IIndividual;
repeat
while SCompare(SortList.Items[I] as IIndividual, P) &lt; 0 do
Inc(I);
) }  [" `- `4 \! uwhile SCompare(SortList.Items[J] as IIndividual, P) &gt; 0 do
Dec(J);
7 ~2 s. ^9 i$ s9 q$ `" ]if I &lt;= J then
! m* @/ i4 B* A  R7 C5 u) kbegin
1 Q7 R& r5 J8 p7 t) \: @% v5 `SortList.Exchange(I, J);
: P+ @0 D/ \) Y& QInc(I);
* U* e8 D/ P' }8 B4 ZDec(J);
end;
until I &gt; J;
% [4 p  [+ X# G- w0 L' nif L &lt; J then
% Z+ b2 [2 h$ Q  HDanQuickSort(SortList, L, J, SCompare);
# B0 [9 \9 \  c9 eL := I;
4 h- {6 k; R( Tuntil I &gt;= R;
" x! ?" _; J+ h5 K& j+ \" s  M" xend;</P>
/ u- N5 R* t- \% b% e& ^<P>procedure TPopulation.Sort(Compare: TInterfaceCompare);
  K! Q- q  S' c0 O1 X9 Ibegin
( }# A1 ^- B) x4 t0 [6 _if Assigned(fPop) and (Count &gt; 0) then
" P  `8 ~$ ?- cDanQuickSort(fPop, 0, Count - 1, Compare);
end;</P>
/ z: U+ S, B8 R% {2 r<P>procedure TPopulation.SortPopulation;
  n! u: d8 F6 i% o. x2 w% b. ]begin
! n1 x- i# M- d, Y- v* |% G. cSort(self.CompareIndividuals);
end;</P>
1 m1 x8 Q2 ?$ e, V# n9 d8 A' \<P>{ TTSPController }</P>
3 H% h) @7 P  C2 u<P>constructor TTSPController.Create;
begin
inherited;
end;</P>
" C! [7 p4 {+ j( v- u<P>destructor TTSPController.Destroy;
3 w  }% S  [% F$ [' mbegin
SetLength(FCities, 0);
2 }/ o7 l6 |- I5 Z' F1 `5 k& CSetLength(FNoVehicles, 0);
SetLength(FVehicles, 0);
inherited;
end;</P>
<P>{ Standard euclidian distance between two 2D vectors... }
function TTSPController.DistanceBetween( C1, C2: Integer): TFloat;
var
temp:TFloat;
i,j,intTemp,intTemp2:TInt;
( @% i1 x) V- M3 N/ Hbegin
. ~+ T' R/ e* }% G9 XintTemp:=0;
temp:=FormGaPara.EditWrongConstrain.Value;</P>
: E6 S4 U" h. I$ T<P>{if (Cities[C2].id&gt;=1)and(Cities[C2].id&lt;=fOldCityCount)and(Cities[C1].id&lt;&gt;0) then
5 {& {* G. Y2 Z8 Sbegin
fCities[C2].serviceDepot:= fCities[C1].serviceDepot;
  B& t; F8 k- U# I4 S3 g. b3 E0 Nend; //}
//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];
end;
//1
if Cities[C1].id=0 then
begin
3 z0 Z6 ]# {# `8 f5 c; ^/ Lfor i:=0 to fDepotCount-1 do
begin
3 M9 Q, S/ J" T) r, E+ MintTemp:=intTemp+fNoVehicles;
% I6 T! l( i* v; ~if Cities[C2].id =fOldCityCount + intTemp +1 then
* h- ~1 E' p$ Y  [temp:=0;
end;
intTemp:=0;
* }* o+ P1 }4 ?end;
//2
$ a0 |, V* i- M" ]5 Zif Cities[C2].id=0 then
0 G+ T1 q2 V1 P" Gbegin
* _8 k' C( v& ]: x# gfor i:=1 to fDepotCount do
7 c, P+ I3 v4 K& h5 k" F: [begin
intTemp:=intTemp+fNoVehicles;
if Cities[C1].id =fOldCityCount + intTemp then
temp:=0;
+ i0 G: f# }' v% W- u9 C) G2 Gend;
. Y# J" e, Q1 T. Q! t& ]9 kintTemp:=0;
end;
) o+ |$ x5 g5 Q//5
1 A% V7 ^' Y/ {0 Pfor i:=0 to fDepotCount-1 do
begin
intTemp:=intTemp+fNoVehicles;
* v3 h& E% _* @{ if (Cities[C1].id=fOldCityCount + intTemp +1)and(Cities[C2].id=Cities[C1].id+1) then
. h8 R3 M  S+ ]; z+ ]) j# Ptemp:=10; /////////////////////////// }
4 _. I& x7 c# Q1 q  @0 u2 sif (Cities[C1].id&gt;=fOldCityCount + intTemp +1)and(Cities[C1].id&lt;=fOldCityCount + intTemp+fNoVehicles[i+1])
/ E. r: G- i5 j) a# M1 ~and(Cities[C2].id&gt;=fOldCityCount + intTemp +1)and(Cities[C2].id&lt;=fOldCityCount + intTemp+fNoVehicles[i+1])
7 P& Q" g9 }: R5 G+ o+ Y" tthen
0 A: ?' \7 q- e8 u4 ztemp:=0;//}
6 |3 i' y7 T7 Tend;
. K8 v* D. {* o9 V; B; p% |intTemp:=0;
% K' `9 X; r+ k/ q+ k8 G7 z+ V//7
if (Cities[C1].id=Cities[C2].id)and(Cities[C1].id &gt; fOldCityCount) then
) Q$ t# `2 r! {9 Ybegin
temp:=0;
end;
7 ]1 i. Q! c8 N* W//3
9 x$ I) L) U/ v6 \3 d2 H+ kif (Cities[C1].id &gt; fOldCityCount)and(Cities[C2].id&gt;=1)and(Cities[C2].id&lt;=fOldCityCount) then
+ i' {. n" |$ ^  B- D  R* }begin
//temp := Sqrt(sqr(Cities[C1].X - Cities[C2].X)+sqr(Cities[C1].Y - Cities[C2].Y));
temp:=CostArray[C1,C2];
- f! f* }+ c, y3 o/ jend;
- j. B3 w; E7 P" |4 K: S//4
if (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];
$ m/ [3 U& K( \end;
//6
intTemp:=0;
' |+ \7 D/ |7 x$ Q& ]  R0 yfor i:=1 to fDepotCount do
begin
intTemp:=intTemp+fNoVehicles;
if Cities[C1].id= fOldCityCount + intTemp then
begin
intTemp2:=0;
$ {% z3 D/ B8 E8 }for j:=0 to fDepotCount-1 do
begin
1 R6 C; r$ |1 M( l/ LintTemp2:=intTemp2+fNoVehicles[j];
  `1 P1 m# y8 ?( N* hif Cities[C2].id=fOldCityCount + intTemp2 +1 then
if abs(Cities[C2].id-Cities[C1].id) &lt;&gt; fNoVehicles-1 then
) U: Z7 I. s. i- Ytemp:=0;
7 B+ A* l& J  F2 r5 x% Dend; //}</P>
9 X& |0 @. J# H) [7 e  O<P>end;
. H8 ^# o* e4 K8 H6 w2 m' C3 j% xend;
$ `* g% O. ~) o( D/ nintTemp:=0;
- H6 F3 d; y5 z6 R) v/ Presult:=temp;
' B5 C2 `' y! T& Y. Jend;</P>
1 y; R  X6 s0 E- Z<P>function TTSPController.CostBetween(C1, C2: Integer): TFloat; //matrix cij
var
distance:TFloat;
( r* [- Q4 S, V: ?; e4 ubegin
distance := Sqrt(sqr(Cities[C1].X - Cities[C2].X)+ sqr(Cities[C1].Y - Cities[C2].Y));
4 V6 e& P: [$ b: c9 A% e//result:=distance+TimeCostBetween(C1,C2);
( n& b* |# V; m  X2 l! zresult:=distance;
end;</P>
<P>function TTSPController.TimeCostBetween(C1, C2: Integer): TFloat;
7 R% _) V3 ~8 N2 i+ F# uvar
cost:TFloat;
i,j,penaltyW,penaltyD:TFloat;
! \) F3 S4 A1 H0 f/ u- xstartTime:TDateTime;
/ C, Z0 ]1 R" |begin
9 c9 Q8 T& e. e9 vstartTime:=strToDateTime(FormGa.EditStartTime.Text);
/ h, j! v- M; E" Y+ openaltyW:=FormGaPara.EditWaitConstrain.Value;
penaltyD:=FormGaPara.EditDelayConstrain.Value;
if Cities[C2].id&gt;fOldCityCount then
fCities[C2].totalTime:=0
else
3 `* `5 I% K3 N0 j- h2 efCities[C2].totalTime:=Cities[C1].totalTime+Cities[C1].serviceTime+timeArray[C1,C2];</P>
, y9 c8 w0 g0 d" o! c# p<P>fCities[C2].waitTime:= max(0,DateSpanToMin(startTime,Cities[C2].early)-Cities[C2].totalTime);
fCities[C2].delayTime:=max(0,Cities[C2].totalTime-DateSpanToMin(startTime,Cities[C2].late));</P>
( v% c( \. q  R' a<P>if Cities[C2].late&lt;&gt;0 then //consider time or not
begin
2 I+ a: O% i' Y! `! qif Cities[C2].early&lt;&gt;0 then //window or deadline
cost:=penaltyW*fCities[C2].waitTime +penaltyD*fCities[C2].delayTime
( L1 S+ d9 @/ {5 \- Yelse
' n$ b, |2 b" p6 S- `cost:=penaltyD*fCities[C2].delayTime;
! c" \* G9 ~4 h( N& Kend
else
. c( R6 G, |# b8 W0 @cost:=0;
result:=cost;
/ `  t9 a) n" ^7 h: F5 ^end;</P>
<P>function TTSPController.DateSpanToMin(d1,d2:TDateTime):integer;
var
* o# b- J5 W( W- ~' _span:TDateTime;
: H3 C) _: K8 W; |Year, Month, Day, Hour, Min, Sec, MSec: Word;
: ~* @7 A) s/ xbegin
6 @0 v* ]" ^! }/ O1 c% pspan:=abs(d2-d1);
DecodeDate(span, Year, Month, Day);
DecodeTime(span, Hour, Min, Sec, MSec);
result:=Min;
end;</P>
* @# ?& `  L; L4 I% n  Z3 c<P>//return the position in the vehicles array
* k5 D4 E: Z. Kfunction TTSPController.GetVehicleInfo( routeInt:Tint):integer;
. n# ]  r+ c+ X+ S( ]; J! X1 q" Ibegin
' j$ I; J" i# r/ E8 t7 Nresult:=routeInt-fOldCityCount-1;
9 ~2 c. N# i: g+ aend;</P>
<P>function TTSPController.GetWeightConstraint( Individual: IIndividual): TInt;
" \8 d5 c% q6 g& \9 Jvar
0 P) q$ E6 y6 t; u& X& ^- YIndi: ITSPIndividual;
+ k& m- ], n! FtotalCapacity,maxCapacity: TFloat;
# E& y1 a9 j/ Q2 ?i,j:TInt;
tempArray:array of TInt;
tempResult:TInt;
  F/ o3 T7 {$ G. Bbegin
9 @6 |( i! k' V* I" O: nIndi := Individual as ITSPIndividual;
9 c4 [5 L3 @7 ~. J5 iSetLength(tempArray, fCityCount+1);
tempResult:=0;
: w' P7 n/ v4 y, B. i! k/////////////////////////////////////////////////////////
& y  Y0 p' {# \9 Jfor i:=0 to fCityCount-1 do
begin
if Indi.RouteArray=fOldCityCount+1 then
- B/ X9 a) H* k( @3 j$ w' o, dbreak;
end;
7 }, Y; v9 f6 i0 F: ifor j:=0 to fCityCount-i-1 do
: i. f& d2 J' R& R* Gbegin
" d6 v. m( u( G; i2 E" n: x" q# P7 DtempArray[j]:= Indi.RouteArray[i+j];
( R+ `( x7 y6 Qend;
3 ]+ H; L; T" B( R7 l$ kfor j:=fCityCount-i to fCityCount-1 do
1 U/ R3 B' U2 X' O8 ^begin
tempArray[j]:= Indi.RouteArray[j-fCityCount+i];
! C$ F; n7 ?# Oend;
tempArray[fCityCount]:= tempArray[0];
, r! x8 G4 b# y3 f//////////////////////////////////////////////////////////
//totalCapacity:=fCities[tempArray[0]].supply; //supply
maxCapacity:=fVehicles[GetVehicleInfo(tempArray[0])].volume;
totalCapacity:=maxCapacity;
" |  |$ F1 F" |4 Z8 C- k0 m0 mfor i:=0 to fCityCount do
% H* V2 I, ?/ P0 |$ r2 c0 ybegin
if (FCities[tempArray].id&lt;=fOldCityCount)and(FCities[tempArray].id&gt;0) then
5 {7 B' d8 `% sbegin
totalCapacity:=totalCapacity+FCities[tempArray].supply-FCities[tempArray].demand;
if (totalCapacity&gt;maxCapacity)or(totalCapacity&lt;0) then
begin
; p+ I% ]2 J, etempResult:=tempResult+1;
# M+ Q2 J9 _+ }7 O//break;
end;
* K) k  i' n+ ^3 Bend;
6 n) H3 U; @" @& ~6 Z5 P" e" Yif FCities[tempArray].id&gt;fOldCityCount then
begin
3 Y. f% t" b( l) z* x$ f5 f//totalCapacity:=fCities[tempArray].supply; //supply
maxCapacity:=fVehicles[GetVehicleInfo(tempArray)].volume;
2 P& G) t, }. j  x8 z9 ntotalCapacity:=maxCapacity;
end;
end;
2 R0 Y% E  o8 ~9 OSetLength(tempArray,0);
3 x, _6 c* W0 q/ [/ S# wresult:=tempResult;
, V) e4 v  ?8 `5 g1 `' Z5 wend;</P>
<P>function TTSPController.GetBackConstraint( Individual: IIndividual): TInt;
( J/ z  C. R/ `( m1 Hvar
Indi: ITSPIndividual;
i,j:TInt;
; {2 a+ t% [4 _5 |: C! @$ Y5 ^tempArray:array of TInt;
tempResult:TInt;
, B+ M$ J0 _  [4 \+ g; lbegin
Indi := Individual as ITSPIndividual;
$ a$ l& W+ t3 R- J( jSetLength(tempArray, fCityCount+1);
6 H9 n2 Q3 f6 i, p, X6 J. k! f% YtempResult:=0;
0 F% V/ v$ W+ lfor i:=0 to fCityCount-1 do
7 [# O0 b9 R, v' ^begin
! d" i" q7 A1 y* Lif Indi.RouteArray=fOldCityCount+1 then
break;
6 g2 H, v" }0 x2 ]  _5 eend;
for j:=0 to fCityCount-i-1 do
begin
9 {0 c% q, X) j$ z$ e7 _tempArray[j]:= Indi.RouteArray[i+j];
end;
2 i0 g! y  [' n4 @$ \for j:=fCityCount-i to fCityCount-1 do
begin
3 D; Z5 z' c6 g5 z- c3 H6 i9 B+ ltempArray[j]:= Indi.RouteArray[j-fCityCount+i];
6 j! A" _4 w6 E6 {% c) R$ oend;
( t$ E. F* S/ S* h  h- OtempArray[fCityCount]:=tempArray[0];
* t5 C! r+ A% k5 }/ b{tempArray[0]:=11;tempArray[1]:=5;tempArray[2]:=8;tempArray[3]:=7;
tempArray[4]:=9;tempArray[5]:=6;tempArray[6]:=12;tempArray[7]:=10;
5 b& D) U' ~5 X( k# W+ z" ~tempArray[8]:=2;tempArray[9]:=4;tempArray[10]:=3;tempArray[11]:=1;
9 g1 ^) t" W6 g4 J7 X/ btempArray[12]:=0;tempArray[13]:=11;tempArray[14]:=3;tempArray[15]:=1;
$ D& j4 H2 e( E! Q" `, ]& rtempArray[16]:=4;tempArray[17]:=11;//10,2,2}
5 P( p  r5 u6 c1 Hfor i:=0 to fCityCount-1 do
  r& o& G8 s- w: g* G* C/ o: n$ Gbegin
8 b8 T* v6 H+ p9 xif (Cities[tempArray[i+1]].id&lt;=fOldCityCount) then
begin
fCities[tempArray[i+1]].serviceDepot:= fCities[tempArray].serviceDepot;
end;
if (Cities[tempArray].id&lt;=fOldCityCount)and(Cities[tempArray].id&gt;=1)and(Cities[tempArray[i+1]].id &gt; fOldCityCount) then
1 |8 [" @" b. _5 Kbegin
if Cities[tempArray].serviceDepot&lt;&gt;Cities[tempArray[i+1]].serviceDepot then //back to the start point
begin
2 ~/ f/ G+ ^; u4 [4 DtempResult:=tempResult+1;
// break;
1 q( h- ~( @- q4 X  {( t4 S; zend;
- v$ \) Y2 _6 p: t% r' t8 |end;
end;
: R% a: e) }5 Z- v0 }& }SetLength(tempArray,0);
0 y& O- p& W1 R. r& n3 {# Tresult:=tempResult;
end; </P>
2 P+ [1 ]: b' {$ p% _; s<P>function TTSPController.GetTimeConstraint( Individual: IIndividual): TInt;
var
7 x7 V* G, K: j: W; LIndi: ITSPIndividual;
+ R% @# ^. g% e/ _i,j:TInt;
/ ?, X' Q; {# f, y, a( L/ jtotalTimeCost:TFloat;
0 B0 g& d$ B4 o; mtempArray:array of TInt;
9 K- a( a, ^3 |- RtempResult:TInt;
begin
4 G, ]% n4 ?/ f. kIndi := Individual as ITSPIndividual;
/ Q% d( [0 t, J; J8 Z7 C' ~SetLength(tempArray, fCityCount+1);
5 n; D, F7 T' \9 xtempResult:=0;
1 y( b* g- [( b) }' ?- R/ {for i:=0 to fCityCount-1 do
begin
4 \% Y" W2 O) M: N3 y, oif Indi.RouteArray=fOldCityCount+1 then
break;
4 X) w3 T/ m& r0 a0 \: u% W. nend;
for j:=0 to fCityCount-i-1 do
  O/ V* h% F$ Z! w4 Qbegin
tempArray[j]:= Indi.RouteArray[i+j];
end;
for j:=fCityCount-i to fCityCount-1 do
( X6 r6 F9 C) ^  t: }9 Tbegin
tempArray[j]:= Indi.RouteArray[j-fCityCount+i];
/ g3 n( V5 U, j0 F) e" k6 M% xend;
4 d- L) Q( J) A$ f; N, NtempArray[fCityCount]:=tempArray[0];</P>
<P>totalTimeCost:=0;
  s. L5 Y# @5 Xfor i:=0 to fCityCount-1 do
' s9 y6 B( |9 x3 @; x3 `$ Ibegin
totalTimeCost:=totalTimeCost+timeCostBetween(tempArray,tempArray[i+1]);
end;
if totalTimeCost&lt;&gt;0 then tempResult:=1;
SetLength(tempArray,0);
end;</P>
<P>function TTSPController.GetCity(I: Integer): TPoint2D;
begin
  h" I5 ?( q/ Y; oresult := fCities[I];
end;</P>
4 V% Z4 n. b, u. N+ L3 R. C( h3 ^<P>function TTSPController.GetNoVehicle(I: Integer): TInt;
( K( n; X1 L" k0 I+ v3 S: ~. E6 P+ ^begin
result := fNoVehicles[I];
2 P, A! \$ u0 H7 u5 C5 Wend;</P>
<P>function TTSPController.GetCityCount: Integer;
begin
  Y& c# G# Y2 a4 ^/ w0 Z; Kresult := fCityCount;
end;</P>
7 R+ p  d4 L! V+ F, ]<P>function TTSPController.GetOldCityCount: Integer;
9 ^% N( l) x& c8 ?" o: g. j1 Dbegin
result := fOldCityCount;
: i( U, b: K  A' A3 iend;</P>
  X" ^* n3 k5 g% V<P>function TTSPController.GetTravelCount: Integer;
begin
result := fTravelCount;
end;</P>
' v# x" Y* F3 g" Z$ {% X' {<P>function TTSPController.GetDepotCount: Integer;
  }1 O  c! B9 l4 lbegin
result := fDepotCount;
end;</P>
. E! I, d& }( w6 p1 ^9 n4 ]6 v<P>function TTSPController.GetXmax: TFloat;
begin
result := fXmax;
end;</P>
9 e$ B- [$ ?, x; `( [  b<P>function TTSPController.GetXmin: TFloat;
begin
3 v" k4 L& s7 g7 V  u1 H4 n4 A. Presult := fXmin;
end;</P>
* z6 ~4 k5 B# }; {) ^7 T5 _<P>function TTSPController.GetYmax: TFloat;
& e2 f# o" b" o9 [1 nbegin
5 e; r" M2 v6 a" v8 ^' cresult := fYmax;
) O$ C$ T" G! h6 M; M$ |end;</P>
<P>function TTSPController.GetYmin: TFloat;
begin
result := fYmin;
3 i& `! T# l* C: p. pend;</P>
<P>procedure TTSPController.RandomCities; //from database
& N0 |4 S3 m$ c- n* wvar
i,j,k,m,intTemp,totalVehicleCount: Integer;
8 \7 |  g  l3 u, EtempVehicle:TVehicle;
- S/ W' F( [, w+ E4 i- p( }0 sbegin
$ E5 O' M+ ~# i) _: u  d/ X5 F5 d//////////////////////////////////////////////////////////
fNoVehicles[0]:=0;
totalVehicleCount:=0;
) e" z9 i& ?* m% e7 c; Rfor i:=1 to fDepotCount do //from depots database
begin
fNoVehicles:=fTravelCount +1;
& Z7 A) j- Y. s  V3 h: h( {2 QtotalVehicleCount:=totalVehicleCount+ fNoVehicles; //real and virtual vehicles
end;
: `6 m2 _- l& x; Z6 C. [, q2 BSetLength(fVehicles,totalVehicleCount);
intTemp:=0;
! b3 S9 v9 G* k3 i  T7 F0 yfor i:=1 to fDepotCount do
( k& A4 n) F$ l+ Abegin
for j:=intTemp to intTemp+fNoVehicles-2 do
5 m, B$ s/ }$ o0 T( _' L4 M% Z1 _begin
7 `1 e! S' ]& z2 [" \fVehicles[j].index:=j+1;
fVehicles[j].id:='real vehicle';
fVehicles[j].volume:=50;
( P; z- i2 L3 @  {- w9 Fend;
/ j# t+ J$ P) E* ywith fVehicles[intTemp+fNoVehicles-1] do
begin
index:=intTemp+fNoVehicles;
( f/ r/ C4 a+ D! Wid:='virtual vehicle';
1 m8 J8 K6 `8 z" x0 d0 Nvolume:=0;
  R% {* ^" I! X, h. G( t9 D# w% V2 send;
: H' H3 d0 u8 UintTemp:=intTemp+ fNoVehicles;
# N+ r9 z0 z' O* b, J( H# nend;</P>
2 W% \9 H2 Q- y<P>///////////////////////////////////////////////////////////
intTemp:=0;
' v5 t5 e% v! k1 n7 O* qfor i:=1 to fDepotCount do //depot 1--value
& `; \4 [) t% u- Y$ F; Dbegin
$ n! }$ e  {# P+ i5 k' {- @! kintTemp:=intTemp + fNoVehicles;
end;</P>
<P>for i := 0 to FOldCityCount do //from database
6 O* U9 C7 A) u3 v, j8 J3 |begin
, j; z$ v) L# V0 v% G2 CFCities.id:= i;
9 c( [% n" F6 |; NFCities.X := Xmin+0.5+(Xmax-Xmin-1.0)*Random;
+ \/ Q8 x; w  |  f* M( l) v" ]! x8 I8 pFCities.Y := Ymin+0.5+(Ymax-Ymin-1.0)*Random;
FCities.early:=0;
5 _7 m; @2 D: M+ d) O' Y7 N2 nFCities.late:=0; //TDateTime
FCities.serviceTime:=0;
FCities.totalTime:=0;
FCities.waitTime:=0;
' T& h7 Y# Y2 w5 I+ L6 rFCities.delayTime:=0;
end;
for i:=FOldCityCount+1 to FCityCount-1 do
) T* }, t- ^5 |, ]" E' zbegin
FCities.id:= i;
9 j  X# {1 y9 F7 m" O4 F: Z' \if fDepotCount=1 then
. W8 r; S) v2 _4 p6 S! Vbegin
FCities.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;
  a, ~2 p* T7 h/ B' ^# {# A, @( D0 g7 Dend
else
begin
FCities.X := Xmin+0.5+(Xmax-Xmin-1.0)*Random;
FCities.Y := Ymin+0.5+(Ymax-Ymin-1.0)*Random;
# |% B1 e! D) G  `/ Jend;
FCities.early:=0;
FCities.late:=0; //TDateTime
/ e% S) \) ]; @# \" |3 H: G: VFCities.serviceTime:=0;
FCities.totalTime:=0;
FCities.waitTime:=0;
% \1 L: n! w$ H) j; Y, O4 H6 R& H' N2 UFCities.delayTime:=0;
end;</P>
<P>for i := 0 to FOldCityCount do
! R+ Z2 R2 N9 U+ P; q+ g7 h3 w0 }: dbegin
, a4 {$ s0 H* y& [* ?% r! RFCities.serviceDepot:=i;
; a+ x. R7 Q) Y* a% ?end;</P>
<P>m:=FOldCityCount+1;
for k:=1 to fDepotCount do
8 I1 F8 c: v# A6 E: r  Cbegin
/ l7 A4 X& _, ?) R5 h  ^2 w! Pfor j:=0 to fNoVehicles[k]-1 do
begin
FCities[m].serviceDepot:= fOldCityCount+k;
. I8 e/ Z7 u/ ^) lm:=m+1;
* j( s( S) `! U/ O2 fend;
end;</P>
<P>//supply and demand //////////////////////////from database
) y8 |0 D! j5 }. d/ X, xFCities[0].demand:=0;
FCities[0].supply:=0;
  l+ _7 f; K& G8 K3 p1 c- m1 e: rfor i:=1 to FOldCityCount do
! B4 y! g1 v( m% Mbegin
FCities.demand:=10;
FCities.supply:=0;
1 [" G6 }4 v' ?1 nend;
for i:=FOldCityCount+1 to FCityCount-1 do
begin
3 |6 s+ `- F; i! K2 Q8 QFCities.demand:=0;
% w$ X& q2 X8 M: _$ F- wFCities.supply:=50;
% v4 e' Q2 L) H1 k9 D6 {end;
////////////////////////////////////////////////////////////</P>
<P>intTemp:=0;
for i:=0 to fDepotCount-1 do
" S9 u- w9 O5 H, Vbegin
intTemp:=intTemp+fNoVehicles;
for j:=2 to fNoVehicles[i+1] do
begin
FCities[fOldCityCount + intTemp +j].X :=FCities[fOldCityCount + intTemp +1].X;
) V( a# \" n! [. p' pFCities[fOldCityCount + intTemp +j].Y :=FCities[fOldCityCount + intTemp +1].Y;
end;
end;
* w: q  w2 s0 s( H! g( VwriteTimeArray;
5 V& |: x& V2 F! Z: A: @# ]writeCostArray;
end;</P>
<P>procedure TTSPController.writeTimeArray; //database
3 Q5 n$ [4 h, }3 {var
i,j:integer;
begin
. H  e, x. J, d9 z% d2 x, \3 Y1 mSetLength(timeArray,fCityCount,fCityCount);
# @0 n4 A8 U* ]6 ^) ufor i:=0 to fCityCount-1 do
0 M9 R6 }/ h2 e* W; ]6 _begin
for j:=0 to fCityCount-1 do
- b3 E' Y! ~2 ?7 R, l( }  \% kbegin
if i=j then timeArray[i,j]:=0
else timeArray[i,j]:=10;
end;
3 O" v2 t" A( n! wend;
$ E9 M  l' ?0 @end;</P>
4 T0 G2 H" [$ X& |* _2 S7 T; N7 P7 ]<P>procedure TTSPController.writeCostArray; //database
var
, ~1 h1 }. D+ ~* \i,j:integer;
begin
6 ]- H+ @6 v, q$ s: C3 vSetLength(costArray,fCityCount,fCityCount);
& D! e+ u  W( [for i:=0 to fCityCount-1 do
/ z1 X. ?, s5 F; L! j% @begin
  T0 F+ b. O7 s: i' B* D1 R1 ]# Rfor j:=0 to fCityCount-1 do
, h9 {, z5 z( z0 @+ W7 o4 Lbegin
) `% ^9 j, |  H, z# }$ \. `if i=j then costArray[i,j]:=0
# F1 u, P2 M$ |3 |else costArray[i,j]:=costBetween(i,j);
end;
end;
end;</P>
7 a1 d2 F1 U3 U  a4 C( p0 x3 l<P>procedure TTSPController.SetCityCount(const Value: Integer);
begin
+ q3 e8 f' F* y6 p# K. uSetLength(fCities, Value);
fCityCount := Value;</P>
. ]2 k: u+ i5 ^2 N6 y<P>RandomCities;
% C3 {' ?! K3 A5 h0 V0 g% a! H7 H) Z3 Iend;</P>
) V4 \; o0 k* T" G: `$ E<P>procedure TTSPController.SetOldCityCount(const Value: Integer);
begin
fOldCityCount := Value;
  p4 y2 M- b$ m" L" l/ J, g" D$ Gend;</P>
<P>procedure TTSPController.SetTravelCount(const Value: Integer); ///////////
2 T8 Q# A; X# C6 M6 {- o, Gbegin
fTravelCount := Value;
/ X5 c) r" `" _end;</P>
<P>procedure TTSPController.SetDepotCount(const Value: Integer); ///////////
begin
SetLength(fNoVehicles, Value+1); ///////////////
fDepotCount := Value;
; g3 J  h; O( H5 uend;</P>
' W$ K; F2 r3 i; T' X3 G3 D<P>procedure TTSPController.SetXmax(const Value: TFloat);
( [# ^: \7 z* Jbegin
fXmax := Value;
: D0 l- ?: J' I( o1 Mend;</P>
* U5 a" I7 R1 I0 M) {<P>procedure TTSPController.SetXmin(const Value: TFloat);
1 l- w& a! _( _5 sbegin
fXmin := Value;
end;</P>
<P>procedure TTSPController.SetYmax(const Value: TFloat);
5 V7 U# Z) P1 I5 l+ q: rbegin
( P( x2 `8 d  s- c5 XfYmax := Value;
1 e  r: J  L( b% C, bend;</P>
<P>procedure TTSPController.SetYmin(const Value: TFloat);
3 G; K6 U2 l  D$ {$ m  \begin
fYmin := Value;
end;</P>
<P>end.
' b1 L/ [& [5 R% O</P></DIV>
  Y# R) Y9 Z6 p0 a7 ^; M) p$ E! o

[此贴子已经被作者于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>
3 Z' l0 o. E' G: c<>这是进化算法解决TSP问题的源代码：</P>

ilikenba

<>该算法是由意大利学者M.Dorigo、V.Maniez-zo、A.Colorini等人首先提出的,称之为蚁群系统(antcolonysystem), 该模型已成功应用于求旅行商问题(ＴＳＰ),二次指派问题,排序问题等ＮＰ-困难的组合最优化问题,结果可与模拟退火,遗传算法等通用的启发式算法相媲美.蚁群算法和局部搜索算法相结合(称为混合蚁群算法)应用于解二次指派问题和排序问题,得到的结果可以与专用算法相媲美].受其影响,蚁群系统模型逐渐引起了其它研究者的注意,D.Costa和A.Hertz.</P>
<>在M.Dorigo等人研究成果的基础上,提出了一种求解分配类型问题(assignmenttypeproblem)的一般模型,并用来研究图着色问题.G.Bilchev、I.C.Parmee研究了求解连续空间优化问题的蚁群系统模型.。</P>
<>蚁群算法是模仿蚂蚁工作方式的一种新的启发式算法.生物学研究表明一群互相协作的蚂蚁能够找到食物源和巢之间的最短路径,而单只蚂蚁则不能.蚂蚁间相互协作的方法是它们在所经过的路上留下一定数量的信息素(迹),该迹能被其它蚂蚁检测出来,一条路上的迹越多,其它蚂蚁将以越高的概率跟随此路径,从而该路径上的迹会被加强.</P>
6 s- q0 q( |' F8 L; J4 ^" P<>蚂蚁算法伪码
' s6 I9 `. [/ q# q. g. L2 bBegin
初始化:
( q: f; P7 U6 T' F  O3 Vt← 0
iteration← 0 (iteration为迭代步数)
将 m个蚂蚁随机置于 n个顶点上 ;
: V  O, A( q3 y2 [# C4 LLoop:
# _8 `! r2 h& M' z2 A将所有蚂蚁的初始出发点置于当前解集中 ;
6 @, g7 u  k" A/ R2 ^. P: ]: ofor i← 0 to n-1 do
for k← 1 to m do
  j" K3 h; h( T" w9 |按概率 选择顶点 j;
移动蚂蚁 k至顶点 j;
7 O6 W  p: E! t' {) q" `将顶点j置于蚂蚁k的当前解集</P>
: S2 S& R" t5 k<>end for
t←t＋1
end for
* u2 \2 r; c% O5 }8 r计算各蚂蚁的 L个目标函数值
- }( P% ]7 {' P' ]) M- S; h更新当前的理想解
1 M! R: Z6 ^4 I* @2 u计算各个解的满意度 </P>
4 @5 V8 h% o. P<>置 t← t+1
重置所有 ← 0
iteration← iteration+1
若 iteration&lt;预定的迭代次数
则 goto Loop
/ G' F9 U. X0 [, @0 r" Z输出目前的最满意解
* d( _1 t( b* j3 b5 _End</P>
<>下面是蚂蚁算法解决TSP问题的C++程序：</P>
' m6 T& A2 q4 `4 D2 [" d<DIV class=HtmlCode>
. X! H  K; q# V# f  `<>/* &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>
<>Ant Colony System (ACS) for the Traveling Salesman Problem (TSP) </P>
; c0 U' |+ }0 D- H6 E- B8 t<>[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>
, D) D( U# {* i/ E- B( B$ P1 H/ i<>[Ant Colony System: A Cooperative Learning Approach to the TSP]
by M. Dorigo and L. M. Gambardella
IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, 1997 </P>
9 v4 ^0 n' R$ }; `, J- V; {# q<><a href="http://stinfwww.informatik.uni-leipzig.de/~mai97ixb" target="_blank" >http://stinfwww.informatik.uni-leipzig.de/~mai97ixb</A>
" |3 I# m" f5 D$ _/ ^5 m&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>
<>Copyright (C) 2001 - until_the_end_of_the_ants </P>
2 n0 \; ~$ x; ^<>This program is free software; you can redistribute it and/or modify
7 n# y9 M5 w6 b" n0 Eit under the terms of the GNU General Public License as published by
) Y% I; i  ]6 K5 K; b* Jthe Free Software Foundation; either version 2 of the License, or
, }( y! K% Y- [  }/ x(at your option) any later version. </P>
<>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>
3 v) Q6 L4 X8 E<>You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ </P>
) }: T1 ]( M6 O5 j% u+ @<>#include
#include
* I- Z. \# t# ^#include
6 K% L3 m0 h+ N3 i/ t) a# P1 P#include
#include
#include </P>
<>#define N 70 </P>
$ Q0 h5 [9 l3 H, @<>double C[N][2] = { {64 , 96} , {80 , 39} , {69 , 23} , {72 , 42} , {48 , 67} , {58 ,
" N! A/ L$ ?+ p" x  ~" A9 O43} , {81 , 34} , {79 , 17} , {30 , 23} , {42 , 67} , {7 , 76} , {29 , 51} , {78
, 92} , {64 , 8} , {95 , 57} , {57 , 91} , {40 , 35} , {68 , 40} , {92 , 34} ,
5 z4 R( v" I: e7 ^* r$ b4 i{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}
' I! i3 `* L9 a& Q# S# I, {27 , 43} , {95 , 86} , {67 , 99} , {48 , 83} , {75 , 81} , {8 , 19} , {20 ,
$ p  y* F8 l  G, d  m18} , {54 , 38} , {63 , 36} , {44 , 33} , {52 , 18} , {12 , 13} , {25 , 5} , {58
, 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}
5 g' V) s3 G) d9 F, {17 , 22} , {5 , 45} , {79 , 70} , {9 , 100} , {17 , 82} , {74 , 67} , {10 ,
68} , {48 , 19} , {83 , 86} , {84 , 94} }; </P>
) ]% Z( m, r; V5 Y+ T7 K<>typedef int Tour[N][2];
& c( }0 C  q- h* I' M7 Q& h0 stypedef double doubleMatrix[N][N]; </P>
2 p3 M5 i$ _$ C2 w- q( n- ?# ^<>doubleMatrix D; </P>
6 l/ C/ v, R2 w<>double dist(int i, int j)
( s- B0 Y4 Y+ z- |, y3 G{
return sqrt(pow((C[0]-C[j][0]), 2.0) + pow((C[1]-C[j][1]), 2.0));
} </P>
$ B1 Z, U2 n6 C/ ?& r: l/ m<>void calc_dist()
2 h; b& F0 p; D{
% h5 K0 y9 z% g  c; Ofor (int i = 0; i &lt; N; i++)
2 L2 K! G6 [5 V5 e/ @8 O9 E# dfor (int j = 0; j &lt; N; j++)
D[j] = dist(i, j);
& j* c! E& ?& Y4 V} </P>
: D7 Y4 [# y# Q" ^! H<>double max_dist()
! g1 |( O) H, |, u  S{
double max_dist = 0.0;
for (int i = 0; i &lt; N; i++)
for (int j = 0; j &lt; N; j++)
% ]) [. B6 t! Y4 G3 _* X# M- j1 Fif (dist(i, j) &gt; max_dist)
max_dist = dist(i, j);
4 ]+ o& j6 }) D8 \0 T7 e+ v3 Yreturn max_dist;
} </P>
<>double calc_length(Tour tour)
, |& h: M/ \) {& {! D) L- l/ h{
2 X0 ?7 A! k, M6 r- sdouble l = 0.0;
( l& L# W# Z% V0 _& _0 K* X1 M8 K. Afor (int n = 0; n &lt; N; n++)
1 |* Z- u) m/ ]' B& J{
3 X* R: r& ~* ?- L. L; b( M$ U6 Hint i = tour[n][0];
int j = tour[n][1];
l += D[j];
}
return (l);
} </P>
<>void print_tour(Tour tour)
5 g9 W3 U4 G0 @+ ?# C1 W& E$ F& a{
for (int n = 0; n &lt; N; n++)
printf("( %d , %d ) ", tour[n][0], tour[n][1]);
printf("\n");
8 l/ H+ e7 x9 i) p! }* i* P5 ]} </P>
<>int sum_sequence(int array[], int count)
{
int sum = 0;
for (int i = 0; i &lt; count; i++)
1 g6 L: @4 h) `; X( C! psum += array;
+ \# v! z! Q. s, W3 Q6 Zreturn (sum);
} </P>
<>/******************************************************************************/ </P>
( H! C* v( i" |# D: Q8 y6 u+ Z<>class Ant
{
protected:
int START_CITY, CURRENT_CITY;
: p7 Q" T$ r* [& Y+ b4 mint ALLOWED[N];
7 Q3 T( N( @5 |' f6 L8 |Tour CURRENT_TOUR;
int CURRENT_TOUR_INDEX;
public:
inline Ant(int start_city)
{
START_CITY = start_city;
6 m2 Z: c0 |* p$ @5 y}
inline void moveTo(int to_city)
{
ALLOWED[to_city] = 0;
CURRENT_TOUR[CURRENT_TOUR_INDEX][0] = CURRENT_CITY;
5 I2 h1 X5 V6 u8 \. @, B( {# X9 f2 f- G0 BCURRENT_TOUR[CURRENT_TOUR_INDEX][1] = to_city;
CURRENT_TOUR_INDEX++;
CURRENT_CITY = to_city;
2 v6 H. F) j# v5 N1 F* Z/ z}
( i0 H, ^2 B: E* t8 C- Q- L, K}; </P>
0 i9 y3 F* a1 |! ]# ?1 ]+ g) v% u<>class NNAnt : Ant
' u0 O( @7 f3 i3 Y/ x, t1 d{
. I% R. @6 i% A' [0 r2 M8 Fpublic:
inline NNAnt(int start_city): Ant(start_city) { };
inline int choose()
) b& X! D. Y' o{
double best_length = (double)N * max_dist();
int best_choose = -1; </P>
4 x  x& X% r. V0 K5 j$ f<P>for (int j = 0; j &lt; N; j++)
{
) E% |( K# g! z2 j7 tif ((ALLOWED[j] == 1) &amp;&amp; (D[CURRENT_CITY][j] &lt; best_length))
{
best_choose = j;
& l7 Y# z0 y- @! v) L, o( r& p8 Gbest_length = D[CURRENT_CITY][j];
}
}
  u: p6 Z* N$ l1 C9 Creturn best_choose;
' j# @3 t* Q8 R}
3 Y/ h! D. `1 x, q0 |2 F8 V4 rinline Tour *search()
9 l" V- d5 T- n7 T! W. k) v  ?{
CURRENT_CITY = START_CITY;
CURRENT_TOUR_INDEX = 0;
! `* T/ m' P% ~* e5 \9 ]. t8 xfor (int i = 0; i &lt; N; i++)
ALLOWED = 1;
ALLOWED[CURRENT_CITY] = 0;
while (sum_sequence(ALLOWED, N) &gt; 0)
2 {4 F0 S3 o+ TmoveTo(choose());
8 o( e4 Y7 ]+ q) d" HALLOWED[START_CITY] = 1;
moveTo(START_CITY);
return &amp;CURRENT_TOUR;
}
/ \& k3 F7 C2 b+ H  M5 P& \}; </P>
6 t4 b" f% [6 o; B7 F* r8 {<P>class AntColonySystem;
( G  S" W9 U0 Z, v7 a0 iclass ACSAnt : Ant
{
private:
/ ~* s" l& Z1 hAntColonySystem *ACS;
2 Q  F' i! @  |7 X6 b& |public:
1 D+ U& F/ F. i/ j6 R; }& m$ S  _ACSAnt(AntColonySystem *acs, int start_city): Ant(start_city)
+ T, T5 `# D+ u( B9 U{
ACS = acs;
* s' U6 `9 P% X* b9 q* P0 |}
7 v$ O6 U7 g  a# W2 z0 ^6 qinline int choose();
inline Tour *search();
}; </P>
! s- X$ `0 m, A5 F<P>class AntColonySystem
( R* [- X* d  d- l3 B/ v! X, X{
9 w1 {! x: d8 ~. Y8 \/ m7 Sprivate:
9 Z( Y# {5 s) V+ W& ^5 xdouble ALPHA, BETA, RHO, TAU0;
& V6 }, x- h7 f- l, j! pdoubleMatrix TAU, dTAU;
4 q; K# O/ x3 g! A7 S, n& qstatic const int M = 420;
9 ]1 v$ u6 ~+ BACSAnt *ANTS[M]; </P>
<P>public:
2 K8 q3 m, n+ E1 |5 n/ A3 Hdouble Q0;
AntColonySystem(double alpha, double beta, double rho, double q0);
6 P0 n& u$ p! J  z- F2 Z8 ?9 p( i, sinline double calc_tau0();
' B$ Q, c5 {7 l+ k' ^' }6 winline void init_tau_by_value(double value);
4 c! K4 j+ U* ?0 e7 dinline void init_tau_by_matrix(doubleMatrix matrix);
  U* }& _: P" U" Z+ E, k$ s: c6 Winline void init_uniform();
inline void init_random();
inline void init_randomMOAPC();
inline double ETA(int i, int j);
inline double transition(int i, int j);
) ]/ T$ p0 B* n  i3 ^6 _4 vinline double sum_transition(int i, int allowed[]);
inline void local_update_rule(int i, int j);
inline void clear_global_update();
inline void add_global_update(Tour tour, double length);
inline void global_update_rule();
7 m; R+ j4 t& iinline doubleMatrix *get_tau();
6 e: h2 Z" t$ K' A/ R& {7 Q( v. rinline Tour *search(int T);
}; </P>
+ o. L2 f% f7 Q" K- l" p) T* C<P>inline int ACSAnt::choose()
5 [" P% }6 B$ m& Z$ |{
double q = rand() / (double)RAND_MAX; </P>
4 Y* ~5 G% o& p  B1 E3 b4 p<P>if (q &lt;= ACS-&gt;Q0)
6 d* W' I& v' z{
; N: V- x0 [  {8 i8 adouble best_value = -1.0;
int best_choose = -1;
, D/ D7 i/ F0 f3 c: }for (int j = 0; j &lt; N; j++)
6 T" w4 |7 U! y7 m( ?{
3 W' g9 D) J8 {! u, {) A) `2 fif ((ALLOWED[j] == 1) &amp;&amp;
# |( \; O. E2 k  R; P  q(ACS-&gt;transition(CURRENT_CITY, j) &gt; best_value))
{
# j' Y# w7 `$ A& d1 M8 k) k2 jbest_choose = j;
- R4 O  p( ^7 o5 G& lbest_value = ACS-&gt;transition(CURRENT_CITY, j);
1 x* A. I2 s4 x; d: A}
}
return best_choose;
4 L# N5 ~1 G& k) w# ^4 A! @" J( H} </P>
<P>double sum = ACS-&gt;sum_transition(CURRENT_CITY, ALLOWED);
double p = rand() / (double)RAND_MAX;
: K6 t5 `- g- ]double p_j = 0.0; </P>
2 a  H( ]6 R: j! [2 i<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))
return j;
}
return -1;
2 B7 @8 d3 x' N9 X, F) R} </P>
<P>inline Tour *ACSAnt::search()
  v$ @: {8 O7 x7 X# X{
* p6 U6 [7 a9 ]  ACURRENT_CITY = START_CITY;
CURRENT_TOUR_INDEX = 0;
! ^" ?6 r) i5 H5 @9 {for (int i = 0; i &lt; N; i++)
ALLOWED = 1;
ALLOWED[CURRENT_CITY] = 0;
( Q2 B$ Z) u( m( U5 _while (sum_sequence(ALLOWED, N) &gt; 0)
{
int LAST_CITY = CURRENT_CITY;
moveTo(choose());
- Y  [5 d3 W- \7 pACS-&gt;local_update_rule(LAST_CITY, CURRENT_CITY);
}
ALLOWED[START_CITY] = 1;
ACS-&gt;local_update_rule(CURRENT_CITY, START_CITY);
moveTo(START_CITY);
& i( L; g8 ~, b4 S+ x+ Lreturn &amp;CURRENT_TOUR;
$ a" U5 [% L1 b6 J} </P>
# j1 _7 s2 e& L! ?+ {# G6 ~<P>/******************************************************************************/ </P>
  F7 M5 A. v% g$ a  P* b4 j<P>AntColonySystem::AntColonySystem(double alpha, double beta, double rho, double q0)
{
ALPHA = alpha;
; B+ B8 Y" n+ B4 X7 f/ S- l  g' @BETA = beta;
# E5 o& Y2 W6 V5 }" [RHO = rho;
- y% k7 |2 K2 Q$ cQ0 = q0;
} </P>
<P>inline double AntColonySystem::calc_tau0()
8 Q. Y2 S2 I8 [) I4 {3 t' K& c{
& j! R1 B5 r( D! w; R) gdouble best_length = (double)N * max_dist(); </P>
<P>for (int n = 0; n &lt; N; n++)
{
NNAnt *nnANT = new NNAnt(n);
7 u5 {1 g" m9 A# ]6 x" R( S# kTour tour;
6 C5 _8 M# m) jtour = *(nnANT-&gt;search());
double tour_length = calc_length(tour);
2 |; f& K8 y# U+ }) wif (tour_length &lt; best_length)
best_length = tour_length;
delete nnANT;
6 r  U& K  u7 b$ c" r' S$ X}
return 1.0 / ((double)N * best_length);
} </P>
9 k! q/ u5 V9 \/ X2 k: a6 X3 K<P>inline void AntColonySystem::init_tau_by_value(double value)
  L2 I7 g7 p" Q, @9 E7 U- G9 |- y{
TAU0 = value;
for (int i = 0; i &lt; N; i++)
/ E* H9 J7 @# J( Hfor (int j = 0; j &lt; N; j++)
, ]7 @1 C; |  }% c) c* S  [& STAU[j] = TAU0;
' r, F0 J! K3 P9 w+ |7 p} </P>
; l/ v5 i7 ~  I* L<P>inline void AntColonySystem::init_tau_by_matrix(doubleMatrix matrix)
# d' t. S* k$ @. z) f{
' Z& C6 l" K3 ?7 D6 |, T0 ^& S6 ffor (int i = 0; i &lt; N; i++)
for (int j = 0; j &lt; N; j++)
TAU[j] = matrix[j];
* }* u2 c' D+ G3 ~6 f: }: Z1 h} </P>
<P>inline void AntColonySystem::init_uniform()
- v* n4 }9 b5 u0 {# P/ s{
// uniformly distributed
' k! ]! F" w6 ^for (int k = 0; k &lt; M; k++)
ANTS[k] = new ACSAnt(this, (k % N));
} </P>
& H3 Z- H! d6 `<P>inline void AntColonySystem::init_random()
( G  {+ ~+ f0 T7 [& K{
/ b  l! h5 Q1 q# E- a// randomly distributed
for (int k = 0; k &lt; M; k++)
3 y6 C& E) w! L6 u. `, ]7 K' R  FANTS[k] = new ACSAnt(this, (int)((double)N * (rand() / (double)RAND_MAX)));
} </P>
8 g4 _( |" m2 _. U% \( l<P>inline void AntColonySystem::init_randomMOAPC()
{
/ y) ^4 |  h' q; T; j; P* w8 [// randomly distributed with MOAPC (most one ant per city)
' |) C, B3 g: ~6 z9 W+ zbool MOAPCarray[N];
$ \) [! }. g- qassert(M &lt;= N); </P>
<P>for (int n = 0; n &lt; N; n++)
' g  w( M" F  nMOAPCarray[n] = false; </P>
  U8 I0 e+ z5 G1 m; f# s( P" l<P>for (int k = 0; k &lt; M; k++)
& [3 P, y( n' ~8 I{
int c;
4 B  G/ d( v" N& i% f- S1 ?* h, ydo
5 @4 ~- J4 m# J! q& @( u{
9 n  M& f! B3 R( |: s8 oc = (int)((double)N * (rand() / (double)RAND_MAX));
}
while (MOAPCarray[c]); </P>
<P>MOAPCarray[c] = true;
" N  K2 G; l1 \( MANTS[k] = new ACSAnt(this, c);
}
% U3 N0 S; q; k$ k+ G; u. \9 P} </P>
<P>inline double AntColonySystem::ETA(int i, int j)
4 q0 A! ~# g. B2 M- g{
return ( 1.0 / D[j] );
} </P>
<P>inline double AntColonySystem::transition(int i, int j)
- w3 q# {' _, C* V- n; z0 r( V{
if (i != j)
return ( TAU[j] * pow( ETA(i, j), BETA ) );
# h8 J: ]# {3 v7 X) d; R( c* ~& yelse
) M6 W* {7 P! W& Y5 G8 V4 [return(0.0);
} </P>
<P>inline double AntColonySystem::sum_transition(int i, int allowed[])
( N5 }: `) ?1 n2 U{
' r0 v# w7 {& x5 F4 r% vdouble sum = 0.0;
for (int j = 0; j &lt; N; j++)
( m& e+ Y: c& _+ L& q. d! d  Gsum += ((double)allowed[j] * transition(i, j));
return (sum);
5 S& a/ ?% O* T} </P>
4 S- k: q% Q2 r+ C<P>inline void AntColonySystem::local_update_rule(int i, int j)
6 Q$ o% I1 D/ k{
TAU[j] = (1.0 - RHO) * TAU[j] + RHO * TAU0;
// symmetric TSP
, N1 R  a" x/ k5 {) pTAU[j] = TAU[j];
. N; p! {* w% J' ^# \6 h: ]. {6 L} </P>
<P>inline void AntColonySystem::clear_global_update()
$ u0 i  W5 T0 M/ w  N- W. m{
  D% H$ \" r/ [( `' m# S0 Zfor (int i = 0; i &lt; N; i++)
7 q' Z! X$ W4 efor (int j = 0; j &lt; N; j++)
dTAU[j] = 0.0;
& Y! v0 O2 r* W0 \+ [4 p} </P>
<P>
inline void AntColonySystem::add_global_update(Tour tour, double length)
{
for (int n = 0; n &lt; N; n++)
" _/ V0 k" Z6 _{
int i = tour[n][0];
int j = tour[n][1];
6 N8 M8 w4 f' D, r- qdTAU[j] += (1.0 / length);
/ E% R4 x2 Y  ]9 N* ^// symmetric TSP
dTAU[j] += (1.0 / length);
6 y: q) `9 L0 |7 Z5 I2 j}
+ \% Q: H% y; J* y& y) j} </P>
1 t, p1 t5 ]0 k/ E<P>inline void AntColonySystem::global_update_rule()
8 f, K# x  {+ {0 z. J6 c{
, {' G# g+ x3 C0 Z2 a- O1 ?for (int i = 0; i &lt; N; i++)
% C# l, f0 P- F; P( J2 W$ E- Ifor (int j = 0; j &lt; N; j++)
/ T3 X; m9 g- [; @2 n) ZTAU[j] = (1.0 - ALPHA) * TAU[j] + ALPHA * dTAU[j];
} </P>
<P>inline doubleMatrix *AntColonySystem::get_tau()
$ I% J# e6 k) m, C* C) o1 z: H& N{
9 D3 a: e9 A  V( `return &amp;TAU;
. E" l* ^% D7 r! g} </P>
<P>inline Tour *AntColonySystem::search(int T)
{
9 j2 `. J8 ?: kTour best_tour, tour;
9 T( N) n3 G4 e' {7 Udouble best_length = (double)N * max_dist(), tour_length;
9 w' t$ h' m0 r- e8 i6 b* ]% mclear_global_update(); </P>
4 Z. @2 T# o7 Q, Q& o) J<P>// do T iterations of ACS algorithm
& P" @$ C% A  @8 ?, b* Zint t;
7 S4 r+ c* M# J" hfor (t = 0; t &lt; T; t++)
{
for (int k = 0; k &lt; M; k++)
* q* {  T% A& U& P+ A{
& v. M$ f' }0 j4 Rtour = *(ANTS[k]-&gt;search());
tour_length = calc_length(tour);
. P# J4 P1 o1 N, Z9 W: rif (tour_length &lt; best_length)
{
best_tour = tour;
- S  a: N5 |% o: V1 R5 p2 qbest_length = tour_length;
clear_global_update();
add_global_update(tour, tour_length);
& f& u/ p1 M; C0 g+ W9 W//printf("[%d / %d]: %lf \n", t, T, tour_length);
  p5 ^& M, d$ j5 Q" [}
}
$ O; J: |+ o! V  Xglobal_update_rule();
2 B. ~  M, |0 V" u% Z4 {} </P>
2 d; F& {0 B; u# v4 [- @<P>//printf("[%d/%d] best tour (length = %f):\n", t, T, best_length);
+ J5 G; N' l* }//print_tour(best_tour);
3 w& F% F4 J) k7 [$ }( t//printf("[%d/%d] iterations done\n", t, T);
% L  M! I. q( j6 J' Y. I1 ]- Wprintf("%f\n", best_length);
- ?- I3 ^% }5 `9 y; v) {. j! }return (&amp;best_tour);
} </P>
<P>int main(int argc, char* argv[])
{
// PRNG initalisieren
# a( A5 m" c5 M. etime_t timer;
time(&amp;timer);
# A  t' \( @; fpid_t pid = getpid() + getppid();
unsigned long seed = (timer * pid);
  Y' x1 s' Z6 iif (seed == 0)
2 Z" g# G& z' z7 y9 W- m0 b{
7 g; K' t. F" V, |8 x& otime(&amp;timer);
; [7 G: e7 x, B; v9 `$ K2 d7 l* Dseed = 7 * timer * pid;
! o0 T/ u7 H+ ~/ v* S$ zif (seed == 0) seed = pid; else seed = seed % 56000;
} else seed = seed % 56000;
$ [" ~1 D: ?8 J7 l9 \6 h4 k' esrand((unsigned int)seed); </P>
<P>// EUC2D
* s' F( Q. ^  E8 ^$ H3 {calc_dist(); </P>
<P>// Ant Colony System
* |1 ^1 {! G* `3 k) J7 bAntColonySystem *acs = new AntColonySystem(0.1, 2.0, 0.1, 0.9);
  K/ h2 ]  [! u9 Z$ C' Edouble tau0 = acs-&gt;calc_tau0();
acs-&gt;init_tau_by_value(tau0);
+ J8 e3 u3 m; facs-&gt;init_uniform();
acs-&gt;search(1000); </P>
<P>return(0);
} </P></DIV>
) M( q$ r+ T% s
<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>