12 3 4 / 4 页下一页

查看: 27796|回复: 31

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

[复制链接]

字体大小: 正常放大

ilikenba

1万主题	49 听众	2万积分

TA的每日心情

	奋斗 2024-6-23 05:14

签到天数: 1043 天

[LV.10]以坛为家III

群组: 万里江山

群组: sas讨论小组

群组: 长盛证券理财有限公司

群组: C 语言讨论组

群组: Matlab讨论组

电梯直达

1^#

发表于 2005-4-27 15:36 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

<

>模拟退火算法
　　模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，
<

>内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis
<

>准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退
<

>火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始
<

>解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的
<

>当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling 
<

>Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
3.5.1 模拟退火算法的模型
　　模拟退火算法可以分解为解空间、目标函数和初始解三部分。
　模拟退火的基本思想:
　　(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L
　　(2) 对k=1，……，L做第(3)至第6步：
　　(3) 产生新解S′
　　(4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数
　　(5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.
　　(6) 如果满足终止条件则输出当前解作为最优解，结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法。
　　(7) T逐渐减少，且T->0，然后转第2步。
算法对应动态演示图：
模拟退火算法新解的产生和接受可分为如下四个步骤：
　　第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当
<

>前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法
<

>决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
　　第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。
<

>事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
　　第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若Δt′<0则接受S′作
<

>为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。
　　第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正
<

>目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的
<

>基础上继续下一轮试验。
　　模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在
<

>理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。 
<

>3.5.2 模拟退火算法的简单应用
　　作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem，简记为TSP)：设有n个城市，用数码1,…,n代表
<

>。城市i和城市j之间的距离为d(i，j) i, j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最
<

>短.。
　　求解TSP的模拟退火算法模型可描述如下：
　　解空间解空间S是遍访每个城市恰好一次的所有回路，是{1，……，n}的所有循环排列的集合，S中的成员记为(w1,w2 ,…
<

>…，wn)，并记wn+1= w1。初始解可选为(1，……，n)
　　目标函数此时的目标函数即为访问所有城市的路径总长度或称为代价函数： 
<

>　　我们要求此代价函数的最小值。
　　新解的产生随机产生1和n之间的两相异数k和m，若k<m，则将
　　(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
　　变为：
　　(w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn).
　　如果是k>m，则将
　　(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
　　变为：
　　(wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk).
　　上述变换方法可简单说成是“逆转中间或者逆转两端”。
　　也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。
　　代价函数差设将(w1, w2 ,……，wn)变换为(u1, u2 ,……，un), 则代价函数差为： 
<

>根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序：
Procedure TSPSA:
　begin
　　init-of-T; { T为初始温度}
　　S={1，……，n}; {S为初始值}
　　termination=false;
　　while termination=false
　　　begin
　　　　for i=1 to L do
　　　　　　begin
　　　　　　　　generate(S′form S); { 从当前回路S产生新回路S′}
　　　　　　　　Δt:=f(S′))-f(S);{f(S)为路径总长}
　　　　　　　　IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])
　　　　　　　　S=S′;
　　　　　　　　IF the-halt-condition-is-TRUE THEN
　　　　　　　　termination=true;
　　　　　　End;
　　　　T_lower;
　　　End;
　End
　　模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack 
<

>

roblem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。 
<

>3.5.3 模拟退火算法的参数控制问题
　　模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：
　　(1) 温度T的初始值设置问题。
　　温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但
<

>因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要
<

>依据实验结果进行若干次调整。
　　(2) 退火速度问题。
　　模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这
<

>需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
　　(3) 温度管理问题。
　　温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采
<

>用如下所示的降温方式： 
<

>T(t+1)＝k×T(t)
式中k为正的略小于1.00的常数，t为降温的次数 
<

>使用SA解决TSP问题的Matlab程序：
<DIV class=HtmlCode>
<

>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
% then use SA to slove this problem.
%
% TSP(LOC) solve the traveling salesman problem with cities'
% coordinates given by LOC, which is an M by 2 matrix and M is
% the number of cities.
%
% For example:
%
% loc = rand(50, 2);
% tsp(loc);
if nargin == 0,
% The following data is from the post by Jennifer Myers (<a href="mailtjmyers@nwu" target="_blank" >jmyers@nwu</A>.
edu)
edu)
% to comp.ai.neural-nets. It's obtained from the figure in
% Hopfield & Tank's 1985 paper in Biological Cybernetics
% (Vol 52, pp. 141-152).
loc = [0.3663, 0.9076; 0.7459, 0.8713; 0.4521, 0.8465;
0.7624, 0.7459; 0.7096, 0.7228; 0.0710, 0.7426;
0.4224, 0.7129; 0.5908, 0.6931; 0.3201, 0.6403;
0.5974, 0.6436; 0.3630, 0.5908; 0.6700, 0.5908;
0.6172, 0.5495; 0.6667, 0.5446; 0.1980, 0.4686;
0.3498, 0.4488; 0.2673, 0.4274; 0.9439, 0.4208;
0.8218, 0.3795; 0.3729, 0.2690; 0.6073, 0.2640;
0.4158, 0.2475; 0.5990, 0.2261; 0.3927, 0.1947;
0.5347, 0.1898; 0.3960, 0.1320; 0.6287, 0.0842;
0.5000, 0.0396; 0.9802, 0.0182; 0.6832, 0.8515];
end
NumCity = length(loc); % Number of cities
distance = zeros(NumCity); % Initialize a distance matrix
% Fill the distance matrix
for i = 1:NumCity,
for j = 1:NumCity,
distance(i, j) = norm(loc(i, - loc(j, );
distance(i, j) = norm(loc(i, - loc(j, );
end
end
% To generate energy (objective function) from path
%path = randperm(NumCity);
%energy = sum(distance((path-1)*NumCity + [path(2:NumCity) path(1)]));
% Find typical values of dE
count = 20;
all_dE = zeros(count, 1);
for i = 1:count
path = randperm(NumCity);
energy = sum(distance((path-1)*NumCity + [path(2:NumCity)
path(1)]));
new_path = path;
index = round(rand(2,1)*NumCity+.5);
inversion_index = (min(index):max(index));
new_path(inversion_index) = fliplr(path(inversion_index));
all_dE(i) = abs(energy - ...
sum(sum(diff(loc([new_path new_path(1)],)'.^2)));
end
dE = max(all_dE);
dE = 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)];
plot(loc(out(, 1), loc(out(, 2),'r.', 'Markersize', 20);
axis square; hold on
h = plot(loc(out(, 1), loc(out(, 2)); hold off
MaxTrialN = NumCity*100; % Max. # of trials at a
temperature
MaxAcceptN = NumCity*10; % Max. # of acceptances at a
temperature
StopTolerance = 0.005; % Stopping tolerance
TempRatio = 0.5; % Temperature decrease ratio
minE = inf; % Initial value for min. energy
maxE = -1; % Initial value for max. energy
% Major annealing loop
while (maxE - minE)/maxE > StopTolerance,
minE = inf;
minE = inf;
maxE = 0;
TrialN = 0; % Number of trial moves
AcceptN = 0; % Number of actual moves
while TrialN < MaxTrialN & AcceptN < MaxAcceptN,
new_path = path;
index = round(rand(2,1)*NumCity+.5);
inversion_index = (min(index):max(index));
new_path(inversion_index) =
fliplr(path(inversion_index));
new_energy = sum(distance( ...
(new_path-1)*NumCity+[new_path(2:NumCity)
new_path(1)]));
if rand < exp((energy - new_energy)/temp), %
accept
it!
energy = new_energy;
path = new_path;
minE = min(minE, energy);
maxE = max(maxE, energy);
AcceptN = AcceptN + 1;
end
TrialN = TrialN + 1;
end
end
% Update plot
out = [path path(1)];
set(h, 'xdata', loc(out(, 1), 'ydata', loc(out(, 2));
drawnow;
% Print information in command window
fprintf('temp. = %f\n', temp);
tmp = sprintf('%d ',path);
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
for i = 1:NumCity,
text(loc(path(i),1)+0.01, loc(path(i),2)+0.01, int2str(i), ...
'fontsize', 8);
end </DIV>
又一个相关的Matlab程序
<DIV class=HtmlCode>
function[X,P]=zkp(w,c,M,t0,tf)
[m,n]=size(w);
L=100*n;
t=t0;
clear m;
x=zeros(1,n)
xmax=x;
fmax=0;
while t>tf
for k=1

xr=change(x)
gx=g_0_1(w,x);
gxr=g_0_1(w,xr);
if gxr<=M
fr=f_0_1(xr,c);
f=f_0_1(x,c);
df=fr-f;
if df>0
x=xr;
if fr>fmax
fmax=fr;
xmax=xr;
end
else
p=rand;
if p<exp(df/t)
x=xr;
end
end
end
end
t=0.87*t
end
P=fmax;
X=xmax;
%下面的函数产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
clear m;
u=rand;
u=u*(n-2);
u=round(u);
if u<2
u=2;
end
if u>n-2
u=n-2;
end
v=rand;
v=v*(n-u+1);
v=round(v);
if v<1
v=1;
end
v=v+u;
if v>n
v=n;
end
pi_1(u)=pi0(v);
pi_1(u)=pi0(u);
if u>1
for k=1

u-1)
pi_1(k)=pi0(k);
end
end
if v>(u+1)
for k=1

v-u-1)
pi_1(u+k)=pi0(v-k);
end
end
if v<n
for k=(v+1):n
pi_1(k)=pi0(k);
end
end
d_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
d_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));
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
end
else
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
for k=(u+1):n
d_f=d_f-d(pi0(k),pi0(k-1));
end
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
end
end
pi_r=pi_1; </DIV>

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

ilikenba

1万主题	49 听众	2万积分

TA的每日心情

	奋斗 2024-6-23 05:14

签到天数: 1043 天

[LV.10]以坛为家III

群组: 万里江山

群组: sas讨论小组

群组: 长盛证券理财有限公司

群组: C 语言讨论组

群组: Matlab讨论组

2^#

发表于 2005-4-27 15:44 |只看该作者 |招呼Ta 关注Ta

遗传算法GA

<

>遗传算法：
<

>旅行商问题(traveling saleman problem,简称tsp)：
已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？
用图论的术语来说，假设有一个图 g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。
这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商问题(dij≠dji,,任意i,j=1,2,3，…,n)。
若对于城市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）
旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。
遗传算法：
初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。
适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)).
评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=alpha*(1-alpha).^(i-1) 。[随机规划与模糊规划]
选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。
step1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1,…pop-size.
step2、从区间(0,pop-size)中产生一个随机数r；
step3、若qi-1<r<qi,则选择第i个染色体；
step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。
grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如：
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。
交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从到pop-size重复以下过程：从[0，1]中产生一个随机数r，如果r<pc ，则选择vi作为一个父代。
将所选的父代两两组队，随机产生一个位置进行交叉，如：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1
交叉后为：
8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1
6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1
变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r<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
变异后：
8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1
反grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。
循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传操作，跳出。
<

>Matlab程序：
<DIV class=HtmlCode>
<

>function [bestpop,trace]=ga(d,termops,num,pc,cxops,pm,alpha)
%
%————————————————————————
%[bestpop,trace]=ga(d,termops,num,pc,cxops,pm,alpha)
%d:距离矩阵
%termops:种群代数
%num:每代染色体的个数
%pc:交叉概率
%cxops:由于本程序采用单点交叉，交叉点的设置在本程序中没有很好的解决，所以本文了采用定点，即第cxops，可以随机产生。
%pm:变异概率
%alpha:评价函数eval(vi)=alpha*(1-alpha).^(i-1).
%bestpop:返回的最优种群
%trace:进化轨迹
%------------------------------------------------
%####@@@##版权所有！欢迎广大网友改正，改进！##@@@####
%e-mail:tobysidney33@sohu.com
%####################################################
%
citynum=size(d,2);
n=nargin;
if n<2
disp('缺少变量！！')
disp('^_^开个玩笑^_^')
end
if n<2
termops=500;
num=50;
pc=0.25;
cxops=3;
pm=0.30;
alpha=0.10;
end
if n<3
num=50;
pc=0.25;
cxops=3;
pm=0.30;
alpha=0.10;
end
if n<4
pc=0.25;
cxops=3;
pm=0.30;
alpha=0.10;
end
if n<5
cxops=3;
pm=0.30;
alpha=0.10;
end
if n<6
pm=0.30;
alpha=0.10;
end
if n<7
alpha=0.10;
end
if isempty(cxops)
cxops=3;
end
<

>[t]=initializega(num,citynum);
for i=1:termops
[l]=f(d,t);
[x,y]=find(l==max(l));
trace(i)=-l(y(1));
bestpop=t(y(1),

;
[t]=select(t,l,alpha);
[g]=grefenstette(t);
[g1]=crossover(g,pc,cxops);
[g]=mutation(g1,pm); %均匀变异
[t]=congrefenstette(g);
end
<

>---------------------------------------------------------
function [t]=initializega(num,citynum)
for i=1:num
t(i,

=randperm(citynum);
end
-----------------------------------------------------------
function [l]=f(d,t)
[m,n]=size(t);
for k=1:m
for i=1:n-1
l(k,i)=d(t(k,i),t(k,i+1));
end
l(k,n)=d(t(k,n),t(k,1));
l(k)=-sum(l(k,

);
end
-----------------------------------------------------------
function [t]=select(t,l,alpha)
[m,n]=size(l);
t1=t;
[beforesort,aftersort1]=sort(l,2);%fsort from l to u
for i=1:n
aftersort(i)=aftersort1(n+1-i); %change
end
for k=1:n;
t(k,

=t1(aftersort(k),

;
l1(k)=l(aftersort(k));
end
t1=t;
l=l1;
for i=1:size(aftersort,2)
evalv(i)=alpha*(1-alpha).^(i-1);
end
m=size(t,1);
q=cumsum(evalv);
qmax=max(q);
for k=1:m
r=qmax*rand(1);
for j=1:m
if j==1&r<=q(1)
t(k,

=t1(1,

;
elseif j~=1&r>q(j-1)&r<=q(j)
t(k,

=t1(j,

;
end
end
end
--------------------------------------------------
function [g]=grefenstette(t)
[m,n]=size(t);
for k=1:m
t0=1:n;
for i=1:n
for j=1:length(t0)
if t(k,i)==t0(j)
g(k,i)=j;
t0(j)=[];
break
end
end
end
end
-------------------------------------------
function [g]=crossover(g,pc,cxops)
[m,n]=size(g);
ran=rand(1,m);
r=cxops;
[x,ru]=find(ran<pc);
if ru>=2
for k=1:2:length(ru)-1
g1(ru(k),

=[g(ru(k),[1:r]),g(ru(k+1),[(r+1):n])];
g(ru(k+1),

=[g(ru(k+1),[1:r]),g(ru(k),[(r+1):n])];
g(ru(k),

=g1(ru(k),

;
end
end
--------------------------------------------
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<pm);
for k=1:length(mu)
for i=1:length(r)
umax(i)=n+1-rr(i);
umin(i)=1;
g(mu(k),rr(i))=umin(i)+floor((umax(i)-umin(i))*r(i));
end
end
---------------------------------------------------
function [t]=congrefenstette(g)
[m,n]=size(g);
for k=1:m
t0=1:n;
for i=1:n
t(k,i)=t0(g(k,i));
t0(g(k,i))=[];
end
end
------------------------------------------------- </DIV>
<

>又一个Matlab程序，其中交叉算法采用的是由Goldberg和Lingle于1985年提出的PMX(部分匹配交叉)，淘汰保护指数alpha是我自己设计的，起到了加速优胜劣汰的作用。
<DIV class=HtmlCode>
<

>%TSP问题（又名：旅行商问题，货郎担问题）遗传算法通用matlab程序
%D是距离矩阵，n为种群个数,建议取为城市个数的1~2倍，
%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定
%m为适应值归一化淘汰加速指数 ,最好取为1,2,3,4 ,不宜太大
%alpha为淘汰保护指数,可取为0~1之间任意小数,取1时关闭保护功能,最好取为0.8~1.0
%R为最短路径,Rlength为路径长度
function [R,Rlength]=geneticTSP(D,n,C,m,alpha)
<

>[N,NN]=size(D);
farm=zeros(n,N);%用于存储种群
for i=1:n
farm(i,

=randperm(N);%随机生成初始种群
end
R=farm(1,

;%存储最优种群
len=zeros(n,1);%存储路径长度
fitness=zeros(n,1);%存储归一化适应值
counter=0;
<

>while counter<C
<

>for i=1:n
len(i,1)=myLength(D,farm(i,

);%计算路径长度
end
maxlen=max(len);
minlen=min(len);
fitness=fit(len,m,maxlen,minlen);%计算归一化适应值
rr=find(len==minlen);
R=farm(rr(1,1),

;%更新最短路径
<

>FARM=farm;%优胜劣汰，nn记录了复制的个数
nn=0;
for i=1:n
if fitness(i,1)>=alpha*rand
nn=nn+1;
FARM(nn,

=farm(i,

;
end
end
FARM=FARM(1:nn,

;
<

>[aa,bb]=size(FARM);%交叉和变异
while aa<n
if nn<=2
nnper=randperm(2);
else
nnper=randperm(nn);
end
A=FARM(nnper(1),

;
B=FARM(nnper(2),

;
[A,B]=intercross(A,B);
FARM=[FARM;A;B];
[aa,bb]=size(FARM);
end
if aa>n
FARM=FARM(1:n,

;%保持种群规模为n
end
<

>farm=FARM;
clear FARM
counter=counter+1
<

>end
<

>Rlength=myLength(D,R);
<

>function [a,b]=intercross(a,b)
L=length(a);
if L<=10%确定交叉宽度
W=1;
elseif ((L/10)-floor(L/10))>=rand&&L>10
W=ceil(L/10);
else
W=floor(L/10);
end
p=unidrnd(L-W+1);%随机选择交叉范围，从p到p+W
for 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));
[a(1,x),b(1,y)]=exchange(a(1,x),b(1,y));
end
function [x,y]=exchange(x,y)
temp=x;
x=y;
y=temp;
<

>% 计算路径的子程序
function len=myLength(D,p)
[N,NN]=size(D);
len=D(p(1,N),p(1,1));
for i=1

N-1)
len=len+D(p(1,i),p(1,i+1));
end
<

>%计算归一化适应值子程序
function fitness=fit(len,m,maxlen,minlen)
fitness=len;
for i=1:length(len)
fitness(i,1)=(1-((len(i,1)-minlen)/(maxlen-minlen+0.000001))).^m;
end </DIV>
<

>一个C++的程序：
<DIV class=HtmlCode>
<

>//c++的程序
#include<iostream.h>
#include<stdlib.h>
template<class T>
class Graph
{
 public:
Graph(int vertices=10)
{
 n=vertices;
 e=0;
}
~Graph(){}
virtual bool Add(int u,int v,const T& w)=0;
virtual bool Delete(int u,int v)=0;
virtual bool Exist(int u,int v)const=0;
int Vertices()const{return n;}
int Edges()const{return e;}
 protected:
int n;
int e;
};
template<class T>
class MGraph:public Graph<T>
{
 public:
MGraph(int Vertices=10,T noEdge=0);
~MGraph();
bool Add(int u,int v,const T& w);
bool Delete(int u,int v);
bool Exist(int u,int v)const;
void Floyd(T**& d,int**& path);
void print(int Vertices);
 private:
T NoEdge;
T** a;
};
template<class T>
MGraph<T>::MGraph(int Vertices,T noEdge)
{
 n=Vertices;
 NoEdge=noEdge;
 a=new T* [n];
 for(int i=0;i<n;i++){
a=new T[n];8 _6 {2 P! K( w6 x8 z
a=0;
( Z! O0 f- C- c for(int j=0;j<n;j++)if(i!=j)a[j]=NoEdge;
# }- Y$ x; G; z7 J }
# w, ]0 d b, U% k}7 r: l* s3 A G+ @; @
template<class T>+ h8 e) v' f* U$ f/ t
MGraph<T>::~MGraph()7 m# p6 p* m6 r1 `
{
- X1 ^% `( d- ` for(int i=0;i<n;i++)delete[]a;
# {( K$ F1 t4 ^0 @6 X8 K0 B delete[]a;
, _* Z8 L0 d" f( ?, d}- `8 G$ Q% A# S: E/ j3 D& e4 i; E5 Z
template<class T># D1 f# E$ e) w% u2 |# u( X
bool MGraph<T>::Exist(int u,int v)const
% k) b; ~' @" M! g4 x. p{0 `' P4 ?$ i! K7 E h9 g( P
 if(u<0||v<0||u>n-1||v>n-1||u==v||a[v]==NoEdge)return false;/ z* K i# Z- A% r2 O& H
 return true;! v7 J3 K0 F1 i; L5 d! E1 ]
}3 A0 x5 l; h; y
template<class T>
! m I$ R& D/ ?- F# w& S' Mbool MGraph<T>::Add(int u,int v,const T& w)
) W2 D2 o# F$ v5 p) w( l{
" v* [. |) R8 ], K5 X+ [/ L if(u<0||v<0||u>n-1||v>n-1||u==v||a[v]!=NoEdge){; `4 V- f1 z' K% E! @
cerr<<"BadInput!"<<endl;. ?6 ]! N6 ?1 t* U+ z
return false;
: k2 p0 X# l/ h# t2 M }
6 N0 |3 ?% G+ x% ]& i" r: B t a[v]=w;
5 z% G6 S4 U% E2 I7 U e++;. F) R, d: U& q8 M8 p* w b
 return true;$ X: A, k; a/ Q& K
}8 r& d8 ]3 ] o. f; x% v
template<class T>
4 _0 v& i1 B7 c9 g4 x, Zbool MGraph<T>:delete(int u,int v)
8 {! K6 |1 R/ _. r/ @{- v* c2 t: q8 `5 A0 ^, r
 if(u<0||v<0||u>n-1||v>n-1||u==v||a[v]==NoEdge){
2 A5 M! c3 R" s3 U2 G7 X, k+ c- k cerr<<"BadInput!"<<endl;8 t2 K/ T0 B( b/ Z8 ^( s
return false;2 x. y s& Z5 A' Q
 }
/ L' ]; i' L) ~4 \2 _ a[v]=NoEdge;9 l9 r2 Z8 \ L8 C
 e--;, M- N! ~2 V+ r
 return true;
. E% @$ y, D/ O8 b* o* k- P r}
0 [* d- S" j/ ?8 l8 Y" Ttemplate<class T>
- C+ b h( e$ yvoid MGraph<T>::Floyd(T**& d,int**& path)
9 e. @, o, v3 U& S{% |) K% |! d' G
 d=new T* [n];* e% B/ l0 r- }6 ^
 path=new int* [n];/ `( R) p. ?; P6 v' {
 for(int i=0;i<n;i++){. o, o S+ i! c% F- J
d=new T[n];
8 {. t6 T" j9 p, X path=new int[n];
9 v) k/ ?" a4 Z% T# ^ for(int j=0;j<n;j++){
, n: n$ ^ _6 r2 @1 ~, Y d[j]=a[j];$ e& c/ ^( @: i1 l9 G9 j: p
 if(i!=j&&a[j]<NoEdge)path[j]=i;# V# u3 _0 e3 m8 _+ b
 else path[j]=-1;
 I0 S9 q7 }/ _6 w) I }3 j" f/ M& } [( c4 y d3 B- L
 }
8 G8 t/ k& s" Q9 F6 Z6 m( ]! e& B for(int k=0;k<n;k++){2 s0 F' M2 h2 Y/ \$ t0 B$ ~
for(i=0;i<n;i++)& \6 t" ^7 y) O7 G) W, R
 for(int j=0;j<n;j++)5 r! a- v/ W5 v& C4 k
 if(d[k]+d[k][j]<d[j]){7 e+ O# O& l: K; s( D) o' \
 d[j]=d[k]+d[k][j];
; Q9 ^+ m7 L, J9 |4 ^5 ]/ U% T path[j]=path[k][j];
: |+ |9 @ B( H8 u }
# c4 X! ?0 B) d+ ^0 ]$ y7 b- `( { }, W0 V7 Z r8 P' J, g" ?$ i9 {5 _
}: s3 P; P S0 K0 z' }2 n
template<class T>
4 M$ i; n% B6 o' J/ D4 ?void MGraph<T>::print(int Vertices)
9 H# r7 z7 V$ C5 k% v4 _5 f{
: o; n$ D; z1 c6 h' {8 p3 z( K8 I for(int i=0;i<Vertices;i++)
6 n$ E$ ?. k( S' z, g. T for(int j=0;j<Vertices;j++)
% R5 z# l0 X' n7 g5 @& ]' x {
+ K' {$ ~$ s: g+ m- f 6 t6 @! Z: a* X3 `+ E% P2 x2 l6 @
 cout<<a[j]<<' ';if(j==Vertices-1)cout<<endl;" C w6 ]7 D% k
}# j4 _, z g0 ^9 g9 R0 z; K# r
}: _2 E& ]. R' c0 t: V6 X! H
#define noEdge 10000, I- _, @: I( ?: _) V& s2 Q
#include<iostream.h>8 v& t/ W, K1 A2 a# t! G& C2 G6 _
void main()1 o. A9 m- u: ~6 k+ T: R6 _- G
{
* \2 ?% ~! r$ P% A9 p: B cout<<"请输入该图的节点数："<<endl;
* P- v5 r5 X" n) Q+ I: C int vertices;
* [* m& h! }9 y cin>>vertices;6 d( c2 h3 A$ G0 O
 MGraph<float> b(vertices,noEdge);
( }* r, J, p; I3 M5 ?# n) P cout<<"请输入u,v,w:"<<endl;# W2 M# d. N% e) N; ?. B
 int u,v;0 J& Z5 ?; E5 ~, D f* k0 b
 float w; c! m* ?1 I3 [2 b2 u% J. _' r- c
 cin>>u>>v>>w;5 q) e I1 w3 H' `: f& @' t3 ^
 while(w!=noEdge){- K; q/ S. G$ c
//u=u-1;" n; K( t8 \$ Z: W& d
b.Add(u-1,v-1,w);
4 b0 c k) ^' u& r0 I6 Y7 f" R b.Add(v-1,u-1,w);
! I1 N! F; c7 }# w6 L, I cout<<"请输入u,v,w:"<<endl;
) E' W- Z! D2 j2 j0 b u; _ cin>>u>>v>>w;
/ Q2 u8 U1 w2 b* _; g" ^# ] }
! c+ l' D P6 J9 w0 e b.print(vertices);% T6 F9 E. I+ l
 int** Path;+ k% Q4 x+ l1 E, S6 L
 int**& path=Path;/ ]. l8 n/ G- Q3 ^9 m4 _
 float** D;: O( K- \9 ^" k
 float**& d=D;! t" |2 t( q" H/ |# n3 I4 j
 b.Floyd(d,path);8 i+ s3 [+ f" Y6 D( k& u' s# I
 for(int i=0;i<vertices;i++){
# @; ]+ Q, P* v! @& D& B) } for(int j=0;j<vertices;j++){2 p1 u; p$ ?6 W: j1 i
 cout<&ltath[j]<<' ';, j$ y( U2 v! P( j
 if(j==vertices-1)cout<<endl;( R" Z" s5 L2 D4 j
}
- e; W1 d5 S$ X }# P- T1 h8 j* Q7 B
 int *V;
( M& k3 o% _1 q2 b V=new int[vertices+1];" k, _; C. |) M5 [9 k* U7 t7 ?% T
 cout<<"请输入任意一个初始H-圈："<<endl;5 d6 Z _4 U3 [7 r
 for(int n=0;n<=vertices;n++){8 o4 [9 P% I( j" m" c

1 A4 F0 h4 j7 @# l$ ` cin>>V[n];* p! N+ d& |9 X! P- E: y
 }
: L4 G+ i' b2 Y# A- T for(n=0;n<55;n++){
, ~8 M' J- G2 ]' \+ v for(i=0;i<n-1;i++){
$ i$ R( |7 g. A% r% c9 V! ` for(int j=0;j<n-1;j++)
; X$ f1 [9 q- P% |$ @* Q! v3 h {# p/ W2 ^1 o1 b
 if(i+1>0&&j>i+1&&j<n-1){
' s, m7 H% d) i2 R9 e( b if(D[V][V[j]]+D[V[i+1]][V[j+1]]<D[V][V[i+1]]+D[V[j]][V[j+1]]){
* [# m& i8 u1 L* Q0 l, J int l;
2 c) `0 j$ L% P/ B2 _ l=V[i+1];V[i+1]=V[j];V[j]=l;
0 K/ [6 @3 i( ^1 R3 D4 c4 u }5 c( s4 L, x( ]6 n
 }/ g1 h' F7 ]2 g+ J3 ?+ s
}
4 F* t% U1 K1 [! e9 o5 a4 p }% |7 l+ u7 Y# J7 v* c9 S. b
 }9 X" V4 U# W7 W7 e$ h# L/ R
 float total=0;/ m: S. R# o9 T# f$ g/ ~* r& q
 cout<<"最小回路："<<endl;
6 ~1 B/ ^! e. I' d: P for(i=0;i<=vertices;i++){- K6 e% r4 b, j2 i2 f' t$ l
" k* ~/ ]9 m5 |7 c( o
cout<<V+1<<' ';
# H$ c8 ~: p. d }. p9 i& `6 [$ {+ ?9 ?0 c1 s$ l
 cout<<endl;# g2 @- [+ L6 E: M: r
 for(i=0;i<vertices;i++)
- ~ N( H8 H; I( C9 U: t/ F- } total+=D[V][V[i+1]];( j( d9 b2 p) Z& A6 x6 A) G
 cout<<"最短路径长度："<<endl;
5 k7 [5 v7 @; `, y- s* m cout<<total;' P/ ~& e; W) q+ P! m
} </DIV> {& F2 x3 u( g) M H1 `: F6 J
<>C语言程序：
2 J; g0 K9 W, Q) W% a" E& w<DIV class=HtmlCode>4 z. }/ w9 a0 k, X
<>#include<stdio.h>
3 T9 _. B* S) C, D9 t#include<stdlib.h>
, z4 `1 a: n& O6 B! ~8 T#include<math.h>
3 b( v3 `( W, D" a6 N, j. A e7 t' T#include<alloc.h>6 m N4 J+ P7 [5 h3 S
#include<conio.h>
$ E* l4 s1 K0 o8 s- t8 U+ L#include<float.h>2 a4 c2 Q" y# ]( J4 F3 N
#include<time.h>% k3 A8 N& E" y4 `$ ~- B
#include<graphics.h>" ]% n* _6 t# s, M2 X- u6 H7 y% c5 @
#include<bios.h>
3 P5 [8 w# U4 ^2 q<>#define maxpop 100, f) v& e' u! M2 r# w8 n2 y0 W! q+ A
#define maxstring 100
6 j/ l: @8 ]4 U0 Y/ O. o$ j<> h4 i: k6 t s
struct pp{unsigned char chrom[maxstring];% {- u1 M. S: R
float x,fitness;0 R4 n2 c. o6 U( {
unsigned int parent1,parent2,xsite;
. j( X" X. ]1 ^3 _$ w; M1 A };
 w5 ?3 q- y5 i9 g9 X# k6 X; Estruct pp *oldpop,*newpop,*p1;8 ~7 G3 A- k# g& U( y ^. O
unsigned int popsize,lchrom,gem,maxgen,co_min,jrand;! u* ^& J0 H4 A. K8 m, H
unsigned int nmutation,ncross,jcross,maxpp,minpp,maxxy;
) h$ B* ]. q& ]: @9 f) E$ ?' h3 c& }float pcross,pmutation,sumfitness,avg,max,min,seed,maxold,oldrand[maxstring];- W8 D" Y9 R. E# G( o U
unsigned char x[maxstring],y[maxstring];
! l8 w0 N, R6 D- g3 y3 bfloat *dd,ff,maxdd,refpd,fm[201]; \% R% b0 q- q: G; v# a5 Q4 ~" M* D
FILE *fp,*fp1;) |! @9 z" r# z
float objfunc(float);) X! u3 b+ i4 D; O
void statistics();: G$ h" @3 k* I
int select();
4 b- I( e. D tint flip(float);
- L7 x2 u! V' q, q& U* q: k* Tint crossover();
' q( j+ |" P+ ?: j, o# ]: uvoid generation();
2 L9 ]: j$ @5 R% A& y/ N( dvoid initialize();! z6 |7 X. X) u; ?8 t/ T
void report();
# u" r K! o9 S0 n9 p% lfloat decode();( w: V, ?9 {1 A C% Z; k; C) p, G
void crtinit();
' |. W1 H7 r8 ?# m: Nvoid inversion();2 { d% d' m) j: M4 J8 `
float random1();: l) m6 o, g. C
void randomize1();
8 Q3 [! J: D5 R' p2 c; _; |3 J% ]<>main()2 D1 [* ?# f+ P3 D
{unsigned int gen,k,j,tt;
9 }1 h$ x/ T+ R, |# A8 m, j4 Schar fname[10];( y& @0 }# z9 o) Q& Y( t
float ttt;
8 U+ V/ z, r% I$ }4 a4 _clrscr();
, P# P3 J6 s1 m+ K/ R: ~co_min=0;$ o3 G; L, D. e- j% r7 Z7 r
if((oldpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp)))==NULL)
 D! w! ~: [: `( E9 t+ a: i {printf("memory requst fail!\n");exit(0);}
; v; H+ ?, ^# v6 S7 q# f2 O/ uif((dd=(float *)farmalloc(maxstring*maxstring*sizeof(float)))==NULL)
& U7 C. B$ z% ?0 A {printf("memory requst fail!\n");exit(0);}
$ M3 j0 F; L' X& tif((newpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp)))==NULL)3 J! f1 U/ |; [% Y) z* Q+ d( I
 {printf("memory requst fail!\n");exit(0);}8 ^) V$ W& s; {- y
if((p1=(struct pp *)farmalloc(sizeof(struct pp)))==NULL)
: C2 {+ ]) I Q( s9 G+ T$ r {printf("memory requst fail!\n");exit(0);}
* C; p$ R( C z" f4 I/ \; Z- afor(k=0;k<maxpop;k++) oldpop[k].chrom[0]='\0';" u5 @; X# t$ L) J- k
for(k=0;k<maxpop;k++) newpop[k].chrom[0]='\0';3 c- b$ k( b- ` V$ X# t
printf("Enter Result Data Filename:"); X* \1 I/ P7 v4 X
gets(fname);
" v) ~3 j# t% P$ gif((fp=fopen(fname,"w+"))==NULL)0 ?+ f' F, Z5 G/ J7 {
 {printf("cannot open file\n");exit(0);}
; w( h }0 t9 W2 _$ {: q# E8 z5 S<>6 [; p8 b# {: |3 ?% F" |% K
gen=0;
- Y! [1 D9 h8 }randomize();( ~* o, }) ^& a0 L# g4 V( p% C/ s
initialize();+ K* A8 [8 H& R1 c# d0 Q+ Q9 E6 X( J; d
<>fputs("this is result of the TSP problem:",fp);' U* u1 I7 t5 H. B2 Q; g/ k
fprintf(fp,"city: %2d psize: %3d Ref.TSP_path: %f\n",lchrom,popsize,refpd);
$ L6 }/ s! D2 w' wfprintf(fp,"c: %f Pm: %f Seed: %f\n",pcross,pmutation,seed);
, D9 s( q, u5 @' W( Hfprintf(fp,"X site:\n");
" f+ z) {" P# ^4 p0 i& zfor(k=0;k<lchrom;k++)+ X% R& }. E6 h
{if((k%16)==0) fprintf(fp,"\n");
" K' R( T! |+ h s J fprintf(fp,"%5d",x[k]);/ [4 E5 V/ m. a- H, B
}
/ I$ m4 e9 D' }" I t4 y1 |* F. q5 @fprintf(fp,"\n Y site:\n");
% i, t+ u m! s8 S# I' c' rfor(k=0;k<lchrom;k++)2 m8 @2 G* e: E4 F- B/ ?% g
{if((k%16)==0) fprintf(fp,"\n");" O# |! Z9 H$ h2 q
fprintf(fp,"%5d",y[k]);
3 W+ l6 C6 T0 S R- Q2 q7 R }0 M6 F4 w8 U# q9 E5 e
fprintf(fp,"\n");
; ~- d+ T/ @# H) E( u
8 M0 D" [2 S8 v9 Y+ D2 ?crtinit();
8 K$ b, o- g/ X% f, |statistics(oldpop);
5 ]& ?/ X" n' c3 N7 Z! Areport(gen,oldpop);
; j. P% p! Y; Sgetch();
2 E0 c2 F2 k/ V0 zmaxold=min;
* C9 C, @6 x: l! ofm[0]=100.0*oldpop[maxpp].x/ff;( H* D3 c" d9 ?* q7 d4 A% ]/ P/ L
do {
6 ?9 m! `8 S- e! g6 p gen=gen+1;1 t* }- V+ P K, U2 x/ N' y0 u
generation();
 A+ r8 u8 K1 s5 B# ` statistics(oldpop);: r( O b3 Y) W! N
if(max>maxold)3 \" P6 W( V8 i" Z5 ^
 {maxold=max;! I2 v7 i5 m6 Z& K7 c
co_min=0;
: z. Z' E3 [; C7 |0 `" ^0 V; T }
/ U/ ~' R# F: {9 I/ D \ fm[gen%200]=100.0*oldpop[maxpp].x/ff;% C: l1 {. [- Z _* h
report(gen,oldpop);+ F6 F0 J3 \# A- k* N j$ v5 r
gotoxy(30,25);
, {, w3 Y- z% a4 o) | ttt=clock()/18.2;
& t( O5 b' z' `3 b( r9 X tt=ttt/60;
% M+ k* p' `! ]* M printf("Run Clock: %2d: %2d: %4.2f",tt/60,tt%60,ttt-tt*60.0); f3 R ?5 x. c9 A
printf("Min=%6.4f Nm:%d\n",min,co_min);9 i$ o! f& ` X) ^* F8 X6 Z
}while((gen<100)&&!bioskey(1));
0 s) [2 Y! o, h7 m- Gprintf("\n gen= %d",gen);8 f7 H# j4 e9 `1 k7 D# h) ?* P
do{8 v8 \; g( x2 {6 s
gen=gen+1;$ g/ Q& |7 }- d3 z0 T0 x
generation();
4 @: n* l, ?( s$ P6 b3 s* ^2 E4 K0 [0 X statistics(oldpop);
! y) x p1 r+ G# ~& A% @, M; p if(max>maxold)3 j' K! i5 z9 i. |, U
 {maxold=max;
! f0 p& ^; m: nco_min=0;
% T& S$ Q5 E. e- y& |7 m: a7 F* S, U }
* X2 ~. g* L% H0 f, J& ]! B# L fm[gen%200]=100.0*oldpop[maxpp].x/ff;
. M }1 T- X# o report(gen,oldpop);& n( \8 U0 K" [6 s+ ^' [( Q: h; E% ~ a
if((gen%100)==0)report(gen,oldpop);
! ?& W3 L9 _6 g: ^+ I& u gotoxy(30,25);
# [0 g1 P0 U1 z& V/ \, d ttt=clock()/18.2;) Z& ]; j5 O7 z- T W L
tt=ttt/60;1 O7 b0 w( P+ b f! e* [3 Q5 O
printf("Run Clock: %2d: %2d: %4.2f",tt/60,tt%60,ttt-tt*60.0);
1 W+ a( {3 |+ T8 x4 }9 n4 i, m printf("Min=%6.4f Nm:%d\n",min,co_min);
% L p' V7 t; C8 i$ [ }while((gen<maxgen)&&!bioskey(1));
. ]' x/ d7 W# Ngetch();
( U! P3 b" U: J; x ?for(k=0;k<lchrom;k++)
' Q* A. }, [9 S; @3 k {if((k%16)==0)fprintf(fp,"\n");: I1 p& V3 K$ v$ D; x
fprintf(fp,"%5d",oldpop[maxpp].chrom[k]);
' \6 e7 ` w. f7 J' }; d/ k2 f: n9 P }
1 j9 z" K: z# Q6 }1 F9 m e9 efprintf(fp,"\n");) s U2 Y6 t. @3 Q' M* T/ O, Z
fclose(fp);3 s/ R$ K; C5 T
farfree(dd);
/ h# }5 B6 Q2 r+ Y- U: R$ hfarfree(p1);6 e4 i5 ~ }- }2 J
farfree(oldpop);5 r1 F5 [- W% T5 L+ @$ ~+ N
farfree(newpop);
3 C( @7 E! c7 ?9 F, hrestorecrtmode();: t" `! u6 F! t6 {! l6 K/ P; b Y
exit(0);
+ A2 ^- w: \1 d2 A}; e4 V; G L: \, f( V
/*%%%%%%%%%%%%%%%%*/6 f" f) |: q" j% W& r3 \ a6 U
float objfunc(float x1)
/ A6 z. v! S; b! z{float y;
) ?* i9 U- t' e, m y=100.0*ff/x1;) X+ e* E0 e" ^' ?, {
 return y;
% _+ O; Z t# R# N: J/ a }
! g! [% r9 ? C% K/*&&&&&&&&&&&&&&&&&&&*/! a. }5 I+ o( P0 c1 R1 s( l
void statistics(pop)
+ \" X7 j" h, x3 x' `. Fstruct pp *pop;1 D* a6 D5 E1 |) d9 L+ `4 ?2 C( I
{int j;: }% ^6 ~; X4 Q" ]' S" N
sumfitness=pop[0].fitness;1 F' J" ~3 f$ K' A
min=pop[0].fitness;) u* b5 F0 @/ i6 X9 h
max=pop[0].fitness;9 q; s( v# [' j$ {
maxpp=0;
" G9 M& s- e- Y/ w7 nminpp=0;
6 ~" p( I4 I7 X8 M3 I2 Hfor(j=1;j<popsize;j++)
( G `. {" D% N+ i& r/ a$ Q* o {sumfitness=sumfitness+pop[j].fitness;
) L& s, ^0 n- z3 |/ n if(pop[j].fitness>max)
6 X4 y R6 k0 [, [% @. N) ]{max=pop[j].fitness;% Z* p7 Q- j0 L( T/ c3 J) Y
 maxpp=j;
9 E! {7 @( d; k) [; }: z- r0 a- }}
' u& H/ j+ W# F! x if(pop[j].fitness<min)
( J, h# r: w8 f1 ~{min=pop[j].fitness;4 f$ K, k6 r0 o7 \/ I
 minpp=j;
5 s% h% n5 L1 M. R}$ G) Q; L C3 [* a
}- w/ M% s4 e* ]$ o
avg=sumfitness/(float)popsize;9 Q1 r0 x9 k0 O* n2 U' N3 e; N' k
}
! Z/ ~* `$ _7 H! L% q- E: R H/*%%%%%%%%%%%%%%%%%%%%*/( E! f& K, L/ C! } D5 W) j5 k
void generation()
6 R7 @3 _* Q3 K/ p2 }{unsigned int k,j,j1,j2,i1,i2,mate1,mate2;5 k& n# m7 Z* U O2 L; I/ C0 {
float f1,f2;; p" F# Y5 A* ? z: o
j=0;4 N2 _3 z% ^5 l
do{% E) }( {6 P% A2 _
 mate1=select();
/ w% s5 [2 w9 l( l, ]2 j4 |6 F pp:mate2=select();/ a. B6 R8 B7 Y8 b" Z% ^2 R& D7 K
 if(mate1==mate2)goto pp;
7 ~4 G m! a9 W crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);: m/ J8 w, o- P, O0 X( H
 newpop[j].x=(float)decode(newpop[j].chrom);
: L X# }! y( A6 J$ w4 v+ {3 L newpop[j].fitness=objfunc(newpop[j].x);
: B3 F$ ?8 C) m' p5 @ newpop[j].parent1=mate1;9 i: T k; g* m
 newpop[j].parent2=mate2;
/ u* z, z$ I8 Y+ L* M0 R1 X; b$ L newpop[j].xsite=jcross;
/ O3 ]! I4 A8 o8 E% C& N2 F newpop[j+1].x=(float)decode(newpop[j+1].chrom);/ z2 V; P; H5 A4 w9 y$ _
 newpop[j+1].fitness=objfunc(newpop[j+1].x);
& I" C- O; J9 O) [/ l, Y' e: m newpop[j+1].parent1=mate1;* R$ V' u+ q# {) R) n" R$ E
 newpop[j+1].parent2=mate2;
* }3 V* F$ \$ i; d8 f4 c, Z newpop[j+1].xsite=jcross;- i/ j7 G$ d1 }8 u
 if(newpop[j].fitness>min)
: X& d2 H' ^5 ]% f2 u7 H& N{for(k=0;k<lchrom;k++)
, H+ |8 m9 r& M1 E% q- z1 o: ` oldpop[minpp].chrom[k]=newpop[j].chrom[k];
+ L2 t6 x; c& p1 _" A oldpop[minpp].x=newpop[j].x;2 k3 I' _6 r! s) _/ ~
 oldpop[minpp].fitness=newpop[j].fitness;4 B- i; q0 }6 f0 `4 d
 co_min++;- V0 z6 ]1 X0 z W; C
 return;; o6 \) a5 @+ M; d* {
}8 I {; z- T" z! }" L
 if(newpop[j+1].fitness>min)
( |8 \- \) ^8 ?! t6 ]. D l{for(k=0;k<lchrom;k++)
; D' S& X7 j6 @3 f oldpop[minpp].chrom[k]=newpop[j+1].chrom[k];0 M L( V8 g4 C) _
 oldpop[minpp].x=newpop[j+1].x;
, g, x0 W1 Y D& k) v oldpop[minpp].fitness=newpop[j+1].fitness;
. |0 S( Q/ r; G- p8 \: @ co_min++;" g# E: i! A9 V; F7 |
 return;# a. q$ `, l: x: `4 I# b3 l
}# o- P' Z2 U ~# T
 j=j+2;
; t/ e/ v# c+ _" t0 _) S }while(j<popsize);5 r' F% b5 H# g0 ]5 u; S* o) Y' E: u
}* Y; L: T: w% R" q' N9 Q
/*%%%%%%%%%%%%%%%%%*/6 Q- `. X. `4 ~7 G. V
void initdata()5 N4 F7 `; t. p5 s9 k( O* `
{unsigned int ch,j;# v4 I2 V3 `9 g8 X: u. _
clrscr();
: b& h4 y1 a# o" V& y$ Aprintf("-----------------------\n");8 C. @2 Q) w* i8 V
printf("A SGA\n");
& A0 s+ I/ {% H$ Y. }) Rprintf("------------------------\n");
& t) g/ B% c7 ? k/*pause();*/clrscr();
/ P% q; J* p' E- A& jprintf("*******SGA DATA ENTRY AND INITILIZATION *******\n");
) [4 i# F5 L. uprintf("\n");
) |+ G0 @" V3 _printf("input pop size");scanf("%d",&popsize);3 K. E4 W7 W5 |/ a
printf("input chrom length");scanf("%d",&lchrom);6 U- r4 ^3 R) h. y2 ~/ F
printf("input max generations");scanf("%d",&maxgen);
: D7 }' r% y2 z$ mprintf("input crossover probability");scanf("%f",&pcross);5 o9 Z( k* V- h
printf("input mutation prob");scanf("%f",&pmutation);
4 L0 v8 _6 n' j4 x Grandomize1();
+ J" L( Y$ U9 V! V7 |! m& k2 {& cclrscr();
# n; C! F8 N, w) W" d; Fnmutation=0; Y; M- O9 _3 G0 p$ ^) n
ncross=0;
, V7 M0 x0 g0 l, x8 O" ~4 {) m4 Z% v}
, t6 J0 j- {5 w0 y/*%%%%%%%%%%%%%%%%%%%%*/
: Y9 X9 ?$ O9 ivoid initreport()
) n' D, w( b. Y. R* J8 M7 _: `% e{int j,k;. K" [/ O' ] V/ d0 V) Q6 K
printf("pop size=%d\n",popsize);
: ]: Q4 C# Z- b2 Jprintf("chromosome length=%d\n",lchrom);) G# N) A4 u* n) K' J( C) T
printf("maxgen=%d\n",maxgen);6 \7 p( T0 X+ ?5 i7 \4 c$ k& L
printf("pmutation=%f\n",pmutation);+ v9 q4 r- J8 g0 ]
printf("pcross=%f\n",pcross);
( H6 |6 \; h+ _) I! G% C; zprintf("initial generation statistics\n");& o6 c( R1 D1 Q0 X) ?, h
printf("ini pop max fitness=%f\n",max);: U! ^% `/ j; M% X# M' o
printf("ini pop avr fitness=%f\n",avg);4 W0 r. ]9 } x
printf("ini pop min fitness=%f\n",min);3 k# S& q6 P3 w+ v% C- P5 {
printf("ini pop sum fit=%f\n",sumfitness);
( D2 m: l7 m3 F+ P! z3 I+ x}- P3 E7 M4 E6 s$ D9 L8 ^
( Y/ u4 A: i' s6 ]% Y7 W0 W
void initpop()
: ]' I5 i7 E; J2 Z: |" N0 J9 U{unsigned char j1;
. \5 i( E0 n# j0 {# |unsigned int k5,i1,i2,j,i,k,j2,j3,j4,p5[maxstring]; U6 o1 r# h6 N! _
float f1,f2; ]% ^" O1 \# f
j=0;
4 u h. [4 n: i7 N$ qfor(k=0;k<lchrom;k++)/ q# i3 u. O9 N, Y& y: h3 S
 oldpop[j].chrom[k]=k;
 B& s( B3 ]" F4 |9 z, P0 Lfor(k=0;k<lchrom;k++); o5 Z( d6 w; |+ d: Y
 p5[k]=oldpop[j].chrom[k];
& R) H( t r4 C7 c/ P0 jrandomize();
4 z! n5 D2 ]+ n) o9 j7 q8 zfor(;j<popsize;j++)
+ A# m& a7 q5 k {j2=random(lchrom);( M; `9 W, o4 |/ n
 for(k=0;k<j2+20;k++)
% i. U( b2 S& c5 L: I' U {j3=random(lchrom);
& C( b! w7 S% u; G j4=random(lchrom);4 ~9 I2 k3 A; j
j1=p5[j3];2 c* C: e" X9 [7 m
p5[j3]=p5[j4];: C* ?" X* _+ [+ K! f+ @' S- L9 y v- C
p5[j4]=j1;
8 a* i- Y, U) p& j$ Y C8 X }1 b; i. a9 e. w0 k$ Y$ W
 for(k=0;k<lchrom;k++)8 {& f- j7 o9 Z; q
 oldpop[j].chrom[k]=p5[k];; M$ M7 a% H: Z! V* O
 }
2 J% I) A% C! @5 s4 V- C/ w! u for(k=0;k<lchrom;k++)
3 m* T- j9 T+ |4 j! w; b for(j=0;j<lchrom;j++) Z+ e* {0 j8 k, Z7 m
 dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]);
6 ^ S1 G6 }8 @9 m; ?% W for(j=0;j<popsize;j++)% k7 ]/ r1 A. M% K& F! O9 I
{oldpop[j].x=(float)decode(oldpop[j].chrom);
5 z9 P) J3 k) ~5 _% R oldpop[j].fitness=objfunc(oldpop[j].x);
; G: A a8 h; Z1 H" x+ c oldpop[j].parent1=0;. E1 @2 H* J0 D5 H: j) Q
 oldpop[j].parent2=0;$ Z! S2 ^0 H: N
 oldpop[j].xsite=0;
( ] b" t+ ^7 R' ~0 m- W }. Z! T9 a& R! } A$ |# O) V" L
}
6 _/ N0 {( Q) N9 ^1 F- |* }" t. f/*&&&&&&&&&&&&&&&&&*/+ ?/ A7 c& S: c" N u0 [' u
void initialize()
3 C& l6 t" g' T h1 Q& x{int k,j,minx,miny,maxx,maxy;* H' K' O* B6 K |1 E) h
initdata();* p' t# l) ]. I* C
minx=0;2 F7 b6 P; R2 F) Q7 c
miny=0; m) M, s9 s$ J0 y& d5 Z
maxx=0;maxy=0;5 N5 z& g! {+ d- s
for(k=0;k<lchrom;k++)- R$ f+ K9 N2 R, ]
{x[k]=rand();5 u; e$ q# k; {' o* f+ Q7 S
if(x[k]>maxx)maxx=x[k];
* |3 Q" A/ @' S8 q, M2 w if(x[k]<minx)minx=x[k];2 A6 q5 r4 Y( O" \
y[k]=rand();
$ X+ |2 i4 Z& ?5 x! g0 f8 T* L7 k if(y[k]>maxy)maxy=y[k];
4 z4 b5 p8 S# m3 g: W3 o# i; q4 ~2 Q if(y[k]<miny)miny=y[k];
, E; g" m) a& D3 F5 Z! B }/ a/ t* F8 i: l" q. K8 d
if((maxx-minx)>(maxy-miny))0 T& ~4 I' c2 ^# Q$ ?! C" Q, e$ B
 {maxxy=maxx-minx;}9 F( B! y: u$ U- x+ q! v
else {maxxy=maxy-miny;}) Y% X4 s! ]: ~7 c1 a5 ~( F
maxdd=0.0;
5 B# T) {+ _7 E# p5 T* `) r8 Jfor(k=0;k<lchrom;k++)/ z! r8 P( R6 l) s# c( d
for(j=0;j<lchrom;j++)' \' _5 d8 u5 ^4 t j% V. R. f. I
 {dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]);! H" t& X h6 S9 K' z- V' {
 if(maxdd<dd[k*lchrom+j])maxdd=dd[k*lchrom+j];
* I4 _0 y2 I" |* x }. Y/ m$ j% X; D4 |
refpd=dd[lchrom-1];
2 R9 s& w5 `% K# o4 zfor(k=0;k<lchrom;k++)
& G- l9 J6 x/ \. p( O refpd=refpd+dd[k*lchrom+k+2];$ Y* o( H& I1 z# y! y
for(j=0;j<lchrom;j++)+ K' Z4 |( P1 I6 E+ W2 y! F- \8 v
dd[j*lchrom+j]=4.0*maxdd;
# }7 H1 H" u r, y- _/ M/ Kff=(0.765*maxxy*pow(lchrom,0.5));+ ~4 C3 x/ @3 J, @. q6 Q
minpp=0;
8 ~! m9 ^+ A% y( Smin=dd[lchrom-1];
/ t* f! \8 S2 dfor(j=0;j<lchrom-1;j++)
( g; E G! S/ W4 C {if(dd[lchrom*j+lchrom-1]<min)- J# T/ A1 w; d
{min=dd[lchrom*j+lchrom-1];
8 P, B) Q8 _3 T, {0 k; ] minpp=j;5 Z0 s9 u- W8 D/ d+ ]
}
( J( u# E, l- h3 B7 R' v! Y- K }
9 M5 i4 u- Q+ p5 h& ^% Uinitpop();
1 k1 j0 s" K% {& |0 gstatistics(oldpop);& h* l* j1 B3 P6 Y5 y
initreport();/ t! Z0 S& o" O5 |- ]
}
, G! k9 m" V) w" j. |4 S7 J! ?6 {/*&&&&&&&&&&&&&&&&&&*/
( R* E# D' U, S/ L* f! o' nvoid report(int l,struct pp *pop)' v3 G0 j+ |3 Z4 V* F, Q# _
{int k,ix,iy,jx,jy;, C9 B& x& C/ D* J( m
unsigned int tt;
7 p0 J5 c: ?$ u- C' l9 Zfloat ttt;/ m+ U% q- W2 y8 s) J/ x1 x
cleardevice();
" p+ n8 S( W1 wgotoxy(1,1);# S5 k3 x8 m8 B% {" h( w
printf("city:%4d para_size:%4d maxgen:%4d ref_tour:%f\n"
8 N/ x0 T0 T1 J1 u* f& E ,lchrom,popsize,maxgen,refpd);/ ], ~' B+ Q3 g* }( g# v
printf("ncross:%4d Nmutation:%4d Rungen:%4d AVG=%8.4f MIN=%8.4f\n\n"$ N8 w q, S1 r4 E
,ncross,nmutation,l,avg,min);: _4 k. I; f$ S! e, R- W, p% M
printf("Ref.cominpath:%6.4f Minpath length:%10.4f Ref_co_tour:%f\n"; e6 r) k' \1 e8 d. ] t& E$ \
,pop[maxpp].x/maxxy,pop[maxpp].x,ff);2 J" g/ Q3 d9 o( W1 h
printf("Co_minpath:%6.4f Maxfit:%10.8f"# V5 t4 V, F/ ^% p
,100.0*pop[maxpp].x/ff,pop[maxpp].fitness);9 z" \2 W' k$ O! G9 }/ }3 Z
ttt=clock()/18.2;$ R5 ?) s- _/ W$ j( A9 ] i' S1 l
tt=ttt/60;. p3 E& M. y3 N3 A+ {
printf("Run clock:%2d:%2d:%4d.2f\n",tt/60,tt%60,ttt-tt*60.0);- D6 N( I7 E$ D6 S, O
setcolor(1%15+1);
5 m4 A: n) k) a& lfor(k=0;k<lchrom-1;k++); [0 ?! f* w3 T' ?1 L8 G
{ix=x[pop[maxpp].chrom[k]];
# Y4 s! H1 \0 a0 [3 ]+ P2 _ iy=y[pop[maxpp].chrom[k]]+110; Y/ @ Q+ _# ]1 J: N9 R
 jx=x[pop[maxpp].chrom[k+1]];
* b" r3 L: o0 P) ~ jy=y[pop[maxpp].chrom[k+1]]+110;$ F( C) A9 W" N/ ?: G
 line(ix,iy,jx,jy);* k7 I; @" j8 i! q
 putpixel(ix,iy,RED);$ S1 m' s& f$ F
}
) R' O9 ^4 N. ~- I7 D/ Yix=x[pop[maxpp].chrom[0]];
8 I) K. w/ V/ ^2 X% b" Qiy=y[pop[maxpp].chrom[0]]+110;, g9 I4 [' P0 ]! D. J( b3 c4 e; E) n
jx=x[pop[maxpp].chrom[lchrom-1]];8 b( J$ U) x/ }/ ~: ]
jy=y[pop[maxpp].chrom[lchrom-1]]+110;
/ o9 l5 V3 t) x6 Fline(ix,iy,jx,jy);
2 x7 _* v. w2 ~8 zputpixel(jx,jy,RED);
/ f: H- c9 g) ? Q4 u6 J5 ^& Jsetcolor(11);
" r( S* U+ W: i4 Kouttextxy(ix,iy,"*"); i7 R, T0 v+ o# w1 L" y0 k# d6 w
setcolor(12);
' W, s R+ P) L( }2 nfor(k=0;k<1%200;k++)
- }9 T: E$ o9 r' G1 Y* p {ix=k+280;
5 S2 }1 B+ U8 `3 u. H iy=366-fm[k]/3;8 m7 \# i3 J& K6 N# k- A' ]
 jx=ix+1;
' n. p$ y/ J* a( Q V. Z, t' { jy=366-fm[k+1]/3;( a! h. H0 j' C$ U7 f5 ]
 line(ix,iy,jx,jy);9 O. L( C) M7 r0 a1 Z) ?: z' |
 putpixel(ix,iy,RED);6 {' H% s% u8 j. M
}, U3 R j6 N6 W7 R) @
printf("GEN:%3d",l);
# X+ v# A, G5 a9 fprintf("Minpath:%f Maxfit:%f",pop[maxpp].x,pop[maxpp].fitness);' G4 S, _+ ?! f' [+ l
printf("Clock:%2d:%2d:%4.2f\n",tt/60,tt%60,ttt-tt*60.0); D" g( H1 z M* e
}
3 t' b) C- d" u- U5 k& d7 C/*###############*/' O7 A+ t" D8 z* r" I
float decode(unsigned char *pp)0 [+ l0 q/ T8 e0 V9 i
{int j,k,l;' t4 C0 G; p7 v/ w
float tt;
" J4 J: {5 H; ?, j( `tt=dd[pp[0]*lchrom+pp[lchrom-1]];
$ _% O& P& G! g& b6 v& E6 _for(j=0;j<lchrom-1;j++)
0 b/ S, I& n) Q, x$ l: }. m {tt=tt+dd[pp[j]*lchrom+pp[j+1]];}
 ^0 v5 z4 V, P* Y2 v2 A4 ll=0;$ N4 G* J' ~5 t3 o
for(k=0;k<lchrom-1;k++)
4 S, v6 K0 b( h0 z2 u8 E4 V for(j=k+1;j<lchrom;j++)
1 g- y) @$ ]" t/ ]9 x+ ^9 w$ R) A {if(pp[j]==pp[k])l++;}7 x) o2 ?* \# g b2 A! z( A% f$ v
return tt+4*l*maxdd;
1 ~7 b# y( w) k- O}# R1 D2 T! T* w- a5 M$ [
/*%%%%%%%%%%%%%%%%%%*/
. t3 \5 i8 F, H& }2 _( Lvoid crtinit()4 n( z$ b; V, k; s2 J7 Z7 b
{int driver,mode;+ R. f6 {9 y2 v& U+ G( S" o1 b
struct palettetype p;
+ B; Y9 A) k1 \driver=DETECT;3 m! U5 D2 ]' z+ p/ M
mode=0;
1 h9 o& g+ `0 D5 J6 Q$ jinitgraph(&driver,&mode,"");. k5 V" i+ \; b; x6 ]6 |: m) Q5 h/ F' E
cleardevice();
" ~. w8 S) F8 q} |8 u8 }! B/ Y7 a+ V0 P. }
/*$$$$$$$$$$$$$$$$$$$$*/' j' P* |" i' h. X- h6 G
int select()
1 H; O2 w! Y1 j* \{double rand1,partsum;8 o- b' Z$ Z9 c( m7 I
float r1;2 z& K7 m6 O1 c) P# B$ d0 }0 q
int j;
) v; j' R9 z( X$ b S% }partsum=0.0;7 \, Z% W0 b7 }# _$ K! Y( S
j=0; d, l7 ?; O2 E! i
rand1=random1()*sumfitness;0 ]. \* d' p {1 @
do{
/ S0 l D' g( Q( E9 Z# Q. K; g1 Z8 w partsum=partsum+oldpop[j].fitness;
 `1 b5 a9 o! q7 ~( M- [ j=j+1;
 s; J: @& ^/ W: J2 C }while((partsum<rand1)&&(j<popsize));
1 x) q. h# R' u( }return j-1;
! T( m8 U% C/ B' n5 P3 V! V# j}# X8 Z0 A# S( {2 ]
/*$$$$$$$$$$$$$$$*/ I, b1 C$ |( D! w3 F/ a6 \
int crossover(unsigned char *parent1,unsigned char *parent2,int k5)7 g4 m- C; u/ n0 O/ ~2 B
{int k,j,mutate,i1,i2,j5;
2 R9 v9 r) x; x! t% dint j1,j2,j3,s0,s1,s2;
; Z% Q1 e. ]# {: @8 Runsigned char jj,ts1[maxstring],ts2[maxstring];
( C5 G; f, q9 o4 {float f1,f2;" f$ ]; P# h$ ?. H
s0=0;s1=0;s2=0;# f* z5 s4 _% ?8 ^( h
if(flip(pcross))
, r: j! j+ R% d! f1 M" y0 u. x {jcross=random(lchrom-1);2 u4 s' _- V0 O, ~9 @
j5=random(lchrom-1);
4 P7 N+ n" b+ m0 O( z& J2 { ncross=ncross+1;: v& e8 P& q# {; k2 w
if(jcross>j5){k=jcross;jcross=j5;j5=k;}3 |* e" p- E- Z8 h( W: U3 e
}
( g$ S4 }6 r$ N5 t else jcross=lchrom;: p! W% }& Y) s
if(jcross!=lchrom)
! Z+ D" m/ ]- l( t: d% G {s0=1;
! X0 I3 u) ~) a+ u6 x. X k=0;2 U/ _! d" r0 i4 ^, V
for(j=jcross;j<j5;j++)
5 K9 \. V/ F0 r+ |5 t$ J- g {ts1[k]=parent1[j];: V$ x7 o, w- \) _& T' t
 ts2[k]=parent2[j];) L6 m6 X! q# @. X# ?9 P& Y
 k++;3 v; G6 d" g6 |5 C3 V$ L: I; O' n
 }1 f4 z$ D" {8 j
j3=k;4 P5 z; o% g$ p/ k' E/ P2 F
for(j=0;j<lchrom;j++)4 [: T( H. G3 } m9 u
 {j2=0;" b, T& Z! O( X3 k0 U6 W9 V
while((parent2[j]!=ts1[j2])&&(j2<k)){j2++;}
8 {' Q' F2 D0 w( u8 y/ aif(j2==k)
- K( w) q! \; }/ x% ^9 ], v: X {ts1[j3]=parent2[j];
) y& N' N" \" Z8 l# e- {5 j j3++;
7 D+ K$ L/ t- W1 |, {3 d( Q }5 M- Q+ M3 W0 J
 }& ^7 t: w$ z$ d" f" v+ @+ C
 j3=k;
9 B/ G$ [$ Q# ]7 m; _4 U9 s for(j=0;j<lchrom;j++)
# r4 J6 C" O, i4 e, A# ^ {j2=0;" M$ @0 j0 o, m+ g$ W
while((parent1[j]!=ts2[j2])&&(j2<k)){j2++;}9 U2 V/ ^9 @4 U1 ]+ c( Q
if(j2==k)1 t( F$ N8 l [8 n3 |
 {ts2[j3]=parent1[j];% X! l; |/ o0 G3 G
 j3++;
0 K0 v9 l7 C; q/ o9 t/ f* n$ Y# C }
: V1 T1 I+ d3 ]+ Z }
& n0 \3 u5 v w for(j=0;j<lchrom;j++)
4 R$ k( \: n0 |. |3 u {newpop[k5].chrom[j]=ts1[j];( ]8 H: y( q2 N$ B+ `. W
newpop[k5+1].chrom[j]=ts2[j];
4 Q( p+ v3 @8 R2 u$ h# G) u }
0 T8 Y- H$ y# x# i }* Y$ U3 {" m, i5 D9 u5 @: t
else
" Z, _ D4 z: \; y' d5 f* _ {for(j=0;j<lchrom;j++)
- X+ Z. A1 D% v+ j; N {newpop[k5].chrom[j]=parent1[j];+ U: J: ]8 q* E
 newpop[k5+1].chrom[j]=parent2[j];2 [ V# n7 [; h( H0 Q. \
 }5 |* f' V+ [3 Z$ x# z. Z
mutate=flip(pmutation);. E+ ~. I y9 ?/ ^& Y% P4 X0 ]
if(mutate)
8 B. J( k' T7 k8 f4 J {s1=1;& ^! a" j$ e# T9 E0 Q
 nmutation=nmutation+1;
/ c6 H/ T+ m5 k- n( S9 V5 V for(j3=0;j3<200;j3++)( R; Q* a/ r2 Z2 A4 v5 q
 {j1=random(lchrom);
/ T# j% }, i# O |+ q9 m+ m j=random(lchrom);4 `! j$ Z" Z9 _- |/ V
jj=newpop[k5].chrom[j];( r( y( t1 Q/ p( E
newpop[k5].chrom[j]=newpop[k5].chrom[j1];! J7 e7 X! ^0 e: }- d* A1 d
newpop[k5].chrom[j1]=jj;
3 }9 o3 I% @- I7 } s' k }9 q+ u/ n3 m7 {7 U8 Y F& b
 }# v' B$ O8 X# z U `
mutate=flip(pmutation);
" c" Y' R- U0 d) w5 ] if(mutate)1 Y* C0 O+ @# ^
 {s2=1;
0 W& b6 p1 }' r1 _# i; F6 j0 l4 P6 } nmutation=nmutation+1;
 L! H2 X n& g# i for(j3=0;j3<100;j3++)
- h7 k, U; X0 g {j1=random(lchrom);
( x, x: S$ h) R- d+ A" z% R j=random(lchrom);/ n: k) ?" Y; Y5 k* B
jj=newpop[k5+1].chrom[j];% _5 n4 U! C0 h+ E( b
newpop[k5+1].chrom[j]=newpop[k5+1].chrom[j1];
1 v0 I$ ^. p8 h$ C0 ?+ c newpop[k5+1].chrom[j1]=jj;3 \: k- R; p! y% D
 }
5 W1 N7 h# Q1 J6 { }9 s9 v' c% g6 |
 }; ~4 v* F8 p2 a1 a- q
 j2=random(2*lchrom/3);1 Q" F1 Y: m; d! ?8 S) \
 for(j=j2;j<j2+lchrom/3-1;j++)
$ Y$ N2 ^6 }0 S) R+ g for(k=0;k<lchrom;k++)
: O- Z! J4 }5 t- M2 l3 z/ g% ] {if(k==j)continue;
- v6 J! y6 A/ ~! }$ \if(k>j){i2=k;i1=j;}; I$ T, a/ O! C9 i( m; |4 ~9 x, ]* A
 else{i1=k;i2=j;}
- x3 e4 ~+ ^% I4 B( n i5 yf1=dd[lchrom*newpop[k5].chrom[i1]+newpop[k5].chrom[i2]];8 V0 P; \: R5 s3 P1 K8 J
f1=f1+dd[lchrom*newpop[k5].chrom[(i1+1)%lchrom]+
4 O4 p/ v+ }4 r" h newpop[k5].chrom[(i2+1)%lchrom]];- Q( P. {" R0 \! ]4 v
f2=dd[lchrom*newpop[k5].chrom[i1]+
) B/ p) ] B$ a7 e% a newpop[k5].chrom[(i1+1)%lchrom]];+ k) B. b$ H1 A. ]' T
f2=f2+dd[lchrom*newpop[k5].chrom[i2]+% _# V5 E7 _9 B
 newpop[k5].chrom[(i2+1)%lchrom]];- p' s: I& ?- _7 p2 O) _
if(f1<f2){inversion(i1,i2,newpop[k5].chrom);}
; l: `6 ]8 b$ M! F# H }" |7 {- ] Z$ j
 j2=random(2*lchrom/3);
/ L( L0 @" w% s( x for(j=j2;j<j2+lchrom/3-1;j++)- Y( `/ I! O5 y& i3 C# E3 V
for(k=0;k<lchrom;k++)$ o" @2 a/ b; x$ T& b- \9 [
 {if(k==j)continue;5 e0 G0 L# {4 n
if(k>j){i2=k;i1=j;}) u7 m, m- ?$ N% B6 J
 else{i1=k;i2=j;}
; t2 |8 O/ Z/ V# ?9 [& sf1=dd[lchrom*newpop[k5+1].chrom[i1]+newpop[k5+1].chrom[i2]];
' f$ p) w7 k" t8 uf1=f1+dd[lchrom*newpop[k5+1].chrom[(i1+1)%lchrom]+3 v; d7 W7 n g/ `* i% M! c3 `
 newpop[k5+1].chrom[(i2+1)%lchrom]];( l t1 i3 }: B& C9 `, Y) G
f2=dd[lchrom*newpop[k5+1].chrom[i1]+- x3 y: p& h7 M" I8 ~- e* \/ w3 _- f
 newpop[k5+1].chrom[(i1+1)%lchrom]];
. Q- Y1 S; x% Sf2=f2+dd[lchrom*newpop[k5+1].chrom[i2]+/ w( r* H/ |; X+ `- g
 newpop[k5+1].chrom[(i2+1)%lchrom]];% O6 D+ ]0 {8 Y
if(f1<f2){inversion(i1,i2,newpop[k5+1].chrom);}9 \2 B' w( C" _ L
 }. W t, a5 Q7 R, m0 k5 p
 return 1;
8 c. e( Z U( O( ]}8 K- P+ C, N; X) @3 V0 ^! V' a
/*$$$$$$$$$$$$$$$*/
: B9 ^8 Z. w Mvoid inversion(unsigned int k,unsigned int j,unsigned char *ss)
# L5 K3 p2 v0 \' G2 p7 W! F{unsigned int l1,i;6 c' D* Q; ?; h9 o" b/ Y
unsigned char tt;
5 b1 q$ d4 @; B) Ul1=(j-k)/2;0 n8 S0 M+ F d8 p4 L, |
for(i=0;i<l1;i++)
* e7 D& `! w% i( @& G, i" v0 n {tt=ss[k+i+1]; T) l+ I0 g3 T5 M" `
ss[k+i+1]=ss[j-i];8 g5 P! ]8 X1 a, ^! |* a7 g
ss[j-i]=tt;7 a4 Q* {! _* p# z* L$ T" F
}
* D5 N% k; c- J4 F4 y# B7 K. Y}
2 w3 a7 j8 {1 _/ F$ F6 w b/*%%%%%%%%%%%%%%%*/
( w4 q5 t' G* Y, Z3 c) w) Kvoid randomize1()( |; }/ H8 m8 H" p$ S; e9 m0 q" i
{int i;6 q* G' q" X7 Y- k
randomize();5 o1 l0 I0 L! i
for(i=0;i<lchrom;i++)
; A6 @: I9 x3 ^: K4 \5 a oldrand=random(30001)/30000.0;
: W1 `4 z0 A$ \7 v" B3 ujrand=0;
: p6 F; I [/ O4 C8 i5 C}
! `: ^1 \6 O9 Z6 F( K4 D/*%%%%%%%%%%%*/
2 V% \5 I# _1 zfloat random1()6 ?+ a9 c4 n% I
{jrand=jrand+1;. V8 V( V8 N z, l. H- ^
if(jrand>=lchrom)
& \( J7 z" P# A `7 p f {jrand=0;8 \2 T/ F, E) X& j& j
randomize1();
( A) P& m7 {! S7 s, I4 T }
( x5 d' g1 D, ireturn oldrand[jrand];
$ V- _9 f% R4 Z1 z+ Y7 W, g4 y}
 e& J/ M8 ], ?) o8 I7 F# i/*%%%%%%%%%%*/
8 X, m# |5 J S- Rint flip(float probability)
4 C V, u3 x9 @9 e{float ppp;
+ Q0 H2 k9 W7 ^! f/ Oppp=random(20001)/20000.0;
: H' N/ j+ V; k% u! Wif(ppp<=probability)return 1; }' J8 a6 v7 T, e
return 0;5 b. J( U) x8 C* o, i4 t
}</DIV> K4 Z0 P; o9 _5 s

; O! |: \# J) D3 s) ?3 V改进后用来求解VRP问题的Delphi程序：- O7 L U2 ]. P' T5 u$ L4 Z. M* d
<DIV class=HtmlCode>! i6 I' F2 ^0 E
unit uEA;
4 f% X% t+ [/ T, ^; K9 X: H- ~interface
* B, n1 B5 Z x' O7 fuses6 o; E6 R6 b% y' b5 v
uUtilsEA, uIEA, uITSP, Classes, GaPara, windows, SysUtils, fEA_TSP;% E$ b8 R/ n# U
type2 |3 V% G+ f3 S! ]" \7 s. I3 T
TIndividual = class(TInterfacedObject, IIndividual)
8 m8 x5 b3 J/ z9 Z) ^5 x2 p, Dprivate$ a; V- B4 w8 h' x
// The internally stored fitness value
 E, M: c4 A3 B, z3 C& PfFitness: TFloat;3 L' z1 M2 D4 ?) z4 C2 y. S, t# d& B
fWeConstrain: integer;4 ]* U4 \) I. p% |
fBackConstrain: integer;5 s' P1 d2 c* P4 Q5 j
fTimeConstrain: integer;; c- W. j! J! u- e; r. ^" W2 F
procedure SetFitness(const Value: TFloat);# X" D" O+ u- ]# ^0 X% k
function GetFitness: TFloat;- F2 j6 Q* J4 w4 m" D
function GetWeConstrain: integer;
! @, r+ `1 U% k, h8 _+ xprocedure SetWeConstrain(const Value: integer);
5 z8 a$ b0 N$ ?9 ]& @( gprocedure SetBackConstrain(const Value: integer);
5 w% B H, W Mfunction GetBackConstrain: integer;7 @! ]) ? T* A0 u* G( c9 ?
function GetTimeConstrain: integer;
) K; @3 e; O# i5 V$ M% E: M8 O6 Y* Fprocedure SetTimeConstrain(const Value: integer);
( V% T! y6 l% Z' \( f( y' |5 qpublic+ y! @, D$ O5 v, U* {4 c
property Fitness : TFloat read GetFitness write SetFitness;9 D9 G) B$ z0 `, l% c- u% w
property WeConstrain :integer read GetWeConstrain write SetWeConstrain;
1 K" f9 a- t& C6 I4 R: ]property BackConstrain :integer read GetBackConstrain write SetBackConstrain;2 R# y/ m4 J* V5 H, A* G) d+ u
property TimeConstrain :integer read GetTimeConstrain write SetTimeConstrain;% L+ a! ^2 i* D( a- {; G7 C/ m/ m
end;! p1 ~3 S( I! O9 U4 S X% J
TTSPIndividual = class(TIndividual, ITSPIndividual)8 W/ u& T% O* y" w" {/ U$ G
private
- p+ \; a( ~3 W! _& @# e4 ]// The route we travel- n! l1 I" D' {, o6 Y4 @
fRouteArray : ArrayInt;
5 h' B6 J" P0 R+ E pfWeConstrain: integer;5 Y7 E/ H" c. Y* e! P
fBackConstrain: integer;
# ], {' { z4 T- j+ efTimeConstrain: integer;
" S& ?/ M! j& ~4 E9 Tfunction GetRouteArray(I: Integer): Integer;( r) S% {( `, m
procedure SetRouteArray(I: Integer; const Value: Integer);
 h& H8 c E! j# f3 Wprocedure SetSteps(const Value: Integer);. u# w2 a, N" L( ~/ T5 ]
function GetSteps: Integer;
- ^' [4 M; P) b9 Yfunction GetWeConstrain: integer;5 z# B- G4 W" i7 E1 S
procedure SetWeConstrain(const Value: integer);
9 z8 N7 V0 a, t# x' k Bprocedure SetBackConstrain(const Value: integer); N2 U' H9 P/ i3 f
procedure SetTimeConstrain(const Value: integer);
$ s2 q- W- Q, G$ vfunction GetBackConstrain: integer;5 ?9 \! d+ R* Y) @ [
function GetTimeConstrain: integer;
. v! {6 U) Z4 r# Z1 P1 P. Kpublic0 S- V' x, O* P
// Constructor, called with initial route size
" r) u1 ~5 ?! [# R% Vconstructor Create(Size : TInt); reintroduce;
+ C) D8 c: u! [2 {1 odestructor Destroy; override;% U( p8 s( K0 @) ]2 j
property RouteArray[I : Integer] : Integer read GetRouteArray write SetRouteArray; X+ y; d2 b2 `' m
// The number of steps on the route5 a7 J' N+ [% c5 T. Q4 x
property Steps : Integer read GetSteps write SetSteps;8 R2 t/ V6 B2 t7 R/ v
property Fitness : TFloat read GetFitness write SetFitness;
8 _( a% [1 q8 U; I" B* uproperty WeConstrain :integer read GetWeConstrain write SetWeConstrain;: t2 d4 A: u$ I7 B
property BackConstrain :integer read GetWeConstrain write SetBackConstrain;
4 d6 N! T2 j Zproperty TimeConstrain :integer read GetTimeConstrain write SetTimeConstrain;
" B' h, |* l1 K/ W6 qend;
! B9 M) h9 [0 Y7 ^* YTTSPCreator = class(TInterfacedObject, ITSPCreator)
0 n5 R6 c' ?; k/ `( j5 r4 jprivate
; O: r0 H" W3 |7 b, j% r// The Control component we are associated with7 u& `$ w, Y) N I
fController: ITSPController;
1 n1 E! U& s s' D; | {9 pfunction GetController: ITSPController;
9 S/ L, V8 u+ Z! y3 Mprocedure SetController(const Value: ITSPController);
* q0 i0 d9 E) _+ Fpublic; \/ Y$ n, T* Z- S. V& @- W' f- Y
// Function to create a random individual. E* \. r {# A* C
function CreateIndividual : IIndividual;
+ a; ] n. n# |# F% x, zfunction CreateFeasibleIndividual: IIndividual;& B1 A, v6 |0 t4 T4 D
property Controller : ITSPController read GetController write SetController;3 {+ _2 ]7 U) L' @
end;! e" }0 a2 U( P4 X$ l
TKillerPercentage = class(TInterfacedObject, IKillerPercentage)
* B2 R6 r( h9 j: k6 M% ?private6 ?! ?) [4 a2 R/ }0 `$ C
fPer: TFloat;: L4 w ?, b$ Y& p/ p1 |
procedure SetPercentage(const Value: TFloat);1 q9 b, m! Q0 m; L
function GetPercentage: TFloat;
9 X$ G: n" E0 y ^* r: U( Ppublic! m4 k) x5 h# a S
function Kill(Pop : IPopulation): Integer;4 D+ x2 ?: a9 i. t( i& u
// Percentage of population to be killed
! |! C8 X2 u6 oproperty Percentage: TFloat read GetPercentage write SetPercentage;
' W! ?8 o+ w& _& a! H. k9 ]) W9 Wend;
6 f9 \5 F" f+ T# I, M2 a- z& Y; k( |: fTParentSelectorTournament = class(TInterfacedObject, IParentSelector)
$ o. S1 ]: a6 V* Lpublic
; U1 f9 j) c( D$ r# e- Ifunction SelectParent(Population: IPopulation): IIndividual;/ h% G! {) |7 q% M
end;
" W& @3 S1 s; |- x7 Y/ wTTSPBreederCrossover = class(TInterfacedObject, IBreeder)+ h2 K" N4 q7 c9 \- w
public
. O+ d+ r5 S4 N7 A- J8 rfunction BreedOffspring(PSelector: IParentSelector; Pop: IPopulation): IIndividual;* t! n$ u0 L w2 c. a! m
end;
$ _# u. c( @: g5 hTTSPMutator = class(TInterfacedObject, ITSPMutator)
2 i4 ?' f9 A2 s3 j. Mprivate8 i. J4 G, V6 m9 X7 E
fTrans: TFloat;
. y! d7 w7 |4 I# gfInv: TFloat;
! z) {1 d" c: X6 ^procedure SetInv(const Value: TFloat);4 i7 S3 y" ?) _( h
procedure SetTrans(const Value: TFloat);
* Y8 L' z& ?0 F# \function GetInv: TFloat;
 ?7 R7 C+ \" M. C Ofunction GetTrans: TFloat;
: L6 R3 k( d, |, _+ \2 J( apublic
1 R# ~/ Y ^. t6 N0 e1 `+ I {9 Dprocedure Mutate(Individual: IIndividual);3 v. W8 y% y, \# i1 x, m6 i* j- v
published7 Z# C: Y# O% o- ?
// Probability of doing a transposition
 F+ ]0 h$ @4 I5 U: F) b. {/ h% D, Lproperty Transposition: TFloat read GetTrans write SetTrans;
+ h5 |4 |+ ?8 t P# Y$ f! a// Probability of doing an inversion- Y. i U& x8 N1 p7 w7 [, l
property Inversion: TFloat read GetInv write SetInv;% N: w3 C& I+ Q7 r
end;2 L7 m' p' n6 t
TTSPExaminer = class(TInterfacedObject, ITSPExaminer): [& ^! D2 `3 }+ |( R, L
private$ x- b# @7 {( I( f. ~' q
// The Control component we are associated with
3 e: S* F; v$ q+ s- G( sfController: ITSPController;; U2 T/ B/ M G
function GetController: ITSPController;- l) m% t$ p/ ~9 j' R. U7 Q
procedure SetController(const Value: ITSPController);4 W5 \( M" F8 ^3 E# A/ G2 `- x
public7 N, F. M2 \1 c7 p% S2 K4 k# q
// Returns the fitness of an individual as a real number where 0 => best/ G4 M$ q& K7 ?$ y" R
function GetFitness(Individual : IIndividual) : TFloat;. L+ h w& q! c: \9 j* q
property Controller : ITSPController read GetController write SetController;( e) [) |* r9 P0 P. ~) C
end;5 f0 C2 f0 }. P- d5 E. K5 \. r( Q
TPopulation = class(TInterfacedObject, IPopulation)& i! A+ _' V: `
private ) g1 p+ n8 l( M
// The population
. Y) M9 |) s8 i v' w! jfPop : TInterfaceList;, f* P6 _) Q+ E! |" d5 u
// Worker for breeding
( O: \. q5 D: H+ H5 h! C9 XfBreeder: IBreeder;) n6 y2 }6 _8 a. U! x
// Worker for killing
) ]( ]8 K' N. HfKiller: IKiller;& D9 r/ Z( M" s
// Worker for parent selection
4 {, l- Z/ f! L( S. R( w7 c6 P9 ^fParentSelector: IParentSelector;
) @6 U5 G/ q4 k3 j6 O// Worker for mutation- V* x7 T) [: E! r1 g
fMutator: IMutator;' L) |* v b |+ X$ x6 c9 H: ?* t
// Worker for initial creation p$ O& x# x- ? e) Z
fCreator: ICreator;+ o" A3 Z* Z9 F! u3 F3 D8 y9 q
// Worker for fitness calculation. ?9 W# Z8 u# R' p8 E/ K
fExaminer: IExaminer;( V; l/ Z3 u) f
// On Change event1 S, F7 M. V U+ t
FOnChange: TNotifyEvent;1 P" `( m) ]% ^7 X: z: w, R5 m: W
procedure Change;* q& `7 d* r2 N1 E
// Getters and Setters
$ x7 M: Y8 x( u! J; [function GetIndividual(I: Integer): IIndividual;
+ m: G4 s5 k1 U/ z: U8 @& `7 w' gfunction GetCount: Integer;
 S4 A5 p# Q, v7 }function GetBreeder: IBreeder;
. W! Q5 x/ k F# g: H) M4 \function GetCreator: ICreator;1 {8 {( U) n& g8 n, c
function GetExaminer: IExaminer;( D, o7 e, H' x
function GetKiller: IKiller;; P2 F2 M6 T9 |9 j, v
function GetMutator: IMutator;/ `0 n) h% j: W5 t. r U
function GetOnChange: TNotifyEvent;
8 {) F& ]0 z6 b! D3 Afunction GetParentSelector: IParentSelector;
" e, r8 J1 J% \4 Q% ?) Wprocedure SetBreeder(const Value: IBreeder);
# s# a8 ^9 O% w; t3 oprocedure SetCreator(const Value: ICreator);4 i6 Y3 ^8 D' F' i& X
procedure SetExaminer(const Value: IExaminer);
) Z4 p6 C* _9 g% Eprocedure SetKiller(const Value: IKiller);
8 z( r5 X2 w0 {# ^( z' hprocedure SetMutator(const Value: IMutator);
9 T! A' j/ }" `( ~2 \' i# X- T! V# _procedure SetOnChange(const Value: TNotifyEvent);
9 a6 J3 j m% ]- Eprocedure SetParentSelector(const Value: IParentSelector);; C4 ~8 K- V; e( D
// not interfaced
" B% t$ }! V9 D. d$ Rprocedure DanQuickSort(SortList: TInterfaceList; L, R: Integer; SCompare: TInterfaceCompare);4 Z) U& ~# I2 z
procedure Sort(Compare: TInterfaceCompare);
 c2 q5 s$ n2 T* W5 Wprotected% v- e" `. r" Q0 C- b, e
// Comparison function for Sort()$ ^5 p; x6 w d
function CompareIndividuals(I1, I2: IIndividual): Integer;
: X) ^" K, H1 l; u; V9 c- D& a" Z// Sort the population5 t' L5 @ F" N' [
procedure SortPopulation;
& W# A+ M$ r, |4 a0 zpublic: k+ |0 ?0 l7 r& F' Z
// The constructor
5 N+ F/ l4 k1 V/ W% l3 x! Xconstructor Create;
 K+ X$ P4 p# r5 M5 O// The destructor0 z9 p u1 A0 A" T9 {
destructor Destroy; override;
+ _4 x/ x/ {" H4 O, c5 {// Adds an individual to the population
6 o& ^( G/ A& U8 M/ Nprocedure Add(New : IIndividual);
- X2 `, t, T I6 c( ?$ j// Deletes an individual from the population
7 t( C" ? V$ F/ R! W$ Uprocedure Delete(I : Integer);6 ]* _% R& M: b: [6 O' V" M/ F
// Runs a single generation: H8 h9 m$ I1 f9 ~( S4 i3 P
procedure Generation;5 D/ D. T9 f7 I
// Initialise the population
) t" m* H: K/ s" `$ K. t" W( Lprocedure Initialise(Size : Integer);( z! J( i ^$ Y( l- i0 o) E( ~
// Clear ourselves out
" l n. C5 {4 e* gprocedure Clear;6 L# ?0 \3 f6 i3 g. H
// Get the fitness of an individual& a: B* o* Z5 V' [& K; E8 _% l
function FitnessOf(I : Integer) : TFloat;' s0 z. X" J; m/ f3 \8 p
// Access to the population members/ K6 Y9 M3 Q( D4 O
property Pop[I : Integer] : IIndividual read GetIndividual; default;) R Q: v" K: N
// The size of the population4 b, B T& B5 b$ h
property Count : Integer read GetCount;
8 Y! l# G% h1 T) Gproperty ParentSelector : IParentSelector read GetParentSelector write SetParentSelector;) [8 |2 r" E' @6 j6 \1 c
property Breeder : IBreeder read GetBreeder write SetBreeder;
# i" E8 D. T5 O5 g9 a. Qproperty Killer : IKiller read GetKiller write SetKiller;
1 ~+ `" H0 y) Z- D' G4 [# Q$ L0 H" Pproperty Mutator : IMutator read GetMutator write SetMutator;
& u) u* p9 x# Z2 m0 j4 Nproperty Creator : ICreator read GetCreator write SetCreator;, X1 {2 @/ C( J+ w c
property Examiner : IExaminer read GetExaminer write SetExaminer;
5 t2 x0 }1 p& w// An event
7 J1 J* F& ^5 r% N! M9 pproperty OnChange : TNotifyEvent read GetOnChange write SetOnChange;
$ ]- {6 |8 N* c: c. |end;
4 r6 |; m) l; g# E& O: lTTSPController = class(TInterfacedObject, ITSPController)
6 A5 g" y& g; @4 wprivate
4 e- o) i# {, [) s. i: ffXmin, fXmax, fYmin, fYmax: TFloat;( @+ [* y( `7 h! |0 z
{ The array of 'cities' }7 l g- j4 @9 ^" k7 L5 B7 d6 o
fCities : array of TPoint2D;' i0 K$ h; h& M5 _0 _! b
{ The array of 'vehicles' }" ^$ H4 Y5 f: S" s9 F' o9 S
fVehicles : array of TVehicle;9 K& g& g" M5 W6 G5 d5 J& B* n
{ The array of 'vehicle number' }% w1 n* F: S j9 Y
fNoVehicles : ArrayInt;/////////////////////
% ]* f5 ~% ]. Y. i{ The number of 'new cities' }) R! S& F. N( O+ A" q
fCityCount: Integer;, X1 h- o# _$ Y' Y9 @/ y
{ The number of 'old cities' }& M1 s7 C: i$ o7 f$ g
foldCityCount: Integer;
( g. T8 p! \2 W. y0 d. l{ The number of 'travelers' }* _! ]$ h( m' B7 M/ r$ e& R
fTravelCount:Integer; ///////////////////////- ^! r' J5 ^2 q# T
{ The number of 'depots' }
7 |; ^0 ]5 ^ b: J. O% |fDepotCount:Integer; ///////////////////////
. y5 \4 S' j6 S# Y{ Getters... }7 n% g* `! |, q4 Q$ \9 H
function GetCity(I: Integer): TPoint2D;
; T9 Q: ^% d1 Q. o# _function GetNoVehicle(I: Integer): TInt;
& c! b* l I% i k. J$ O2 O$ ifunction GetCityCount: Integer;
2 k$ n$ Z5 ^# R; x" |# g! rfunction GetOldCityCount: Integer;0 y1 F5 s9 \/ {# a, N8 S
function GetTravelCount:Integer;8 ]1 O* y j9 u; Y1 H5 }
function GetDepotCount:Integer;& A6 g' v) |0 ~ N3 \
function GetXmax: TFloat;4 ~1 f' ~2 j4 G$ h4 \ u& X# S
function GetXmin: TFloat;
' i, Q$ m5 |0 S5 y- cfunction GetYmax: TFloat;% w6 a# u. m3 H0 r& S8 V! p
function GetYmin: TFloat;
1 _% U$ X. y' Y6 O. f{ Setters... }
, k/ B \7 Z/ @7 K5 Wprocedure SetCityCount(const Value: Integer);- W3 B2 ?$ H! B' V0 k7 `5 [6 k
procedure SetOldCityCount(const Value: Integer);1 f' J" a1 y$ k
procedure SetTravelCount(const Value: Integer); /////////////0 i9 k+ I& M9 Y z
procedure SetDepotCount(const Value: Integer); ////////////// O6 g, ]! C: o* W: [- w% X/ n
procedure SetXmax(const Value: TFloat);
! F* n$ U$ l( Jprocedure SetXmin(const Value: TFloat);% R+ y: r/ M! k' u
procedure SetYmax(const Value: TFloat);0 x+ E9 u0 N5 W
procedure SetYmin(const Value: TFloat); l0 V1 j- d8 C9 h, P* d% ]5 I; ~
function TimeCostBetween(C1, C2: Integer): TFloat;
9 t6 Q+ ?3 R/ m+ S& W$ i$ ?- |2 H2 Sfunction GetTimeConstraint(Individual: IIndividual): TInt;% I2 V4 c( x* F, Q) s3 p8 a
function DateSpanToMin(d1, d2: TDateTime): integer;- a9 H' ^2 ^, R
function GetVehicleInfo(routeInt: Tint): integer;! u& Y1 v: R7 O2 k! g( w
procedure writeTimeArray;
! a. ~+ A$ r7 pprocedure writeCostArray;
. P7 s; o. V) y% Zpublic+ N2 E: V( A V! { \% ]9 w
{ The constructor }
& i+ u8 q! \: N. X6 Q) i& aconstructor Create;
* s3 g) Z! U8 e' A- C{ The destructor }7 M4 z' {- ?- f9 g* @
destructor Destroy; override;2 R8 U1 |* r8 x( M& d
{ Get the distance between two cities }% j6 j M$ P; @. ~" n" }$ K
function DistanceBetween(C1, C2 : Integer) : TFloat; 6 W0 V6 J- C3 R& Z8 C
{ Get the cost between two cities }9 V. K5 I8 {' @ m `
function CostBetween(C1, C2: Integer): TFloat;
. _! V2 f) C0 E Q4 V( _$ u0 a5 ifunction GetWeightConstraint( Individual: IIndividual): TInt;
% M1 I" H8 v$ Q2 e; g9 I: B# r6 u( F7 ^function GetBackConstraint( Individual: IIndividual): TInt;
5 {6 W' b3 T9 T: \{ Places the cities at random points }5 `! N" i; m" O
procedure RandomCities;+ T# B8 P. [" J" m
{ Area limits }; G0 v; d1 v. n6 K: `( E) N+ w
property Xmin: TFloat read GetXmin write SetXmin;! H6 b' Y& C! H, P8 `: p; i
property Xmax: TFloat read GetXmax write SetXmax;
2 m! o+ f: g& L; u/ N1 |property Ymin: TFloat read GetYmin write SetYmin;8 h0 S$ k# S! H9 ?2 V: \" d
property Ymax: TFloat read GetYmax write SetYmax;% u6 ^. ~2 X x" N
{ Properties... }
% X, ]% p+ K4 b# h9 K; uproperty CityCount : Integer read GetCityCount write SetCityCount;% {# W) F: c& h! a* ]2 | f
property OldCityCount : Integer read GetOldCityCount write SetOldCityCount;! {4 D8 I3 s% t; g% Z% o8 f
property TravelCount : Integer read GetTravelCount write SetTravelCount; ///////////
) V: f' j3 s2 M+ S; D& oproperty DepotCount : Integer read GetDepotCount write SetDepotCount; ///////////
' R* S$ c7 D8 u: I6 r{ Access to the cities array }0 S) [) ~3 n. w$ r# h9 l( V
property Cities[I : Integer] : TPoint2D read GetCity;" j. y' ?# o" e1 M% ?% B" s
property NoVehicles[I : Integer] : TInt read GetNoVehicle; ///////////////
" w$ A. z5 ]5 t- i+ uend;
' D+ }7 V0 L- A3 m$ h) ]implementation
& o, C7 o' F" w6 auses
7 j' s# ?2 o- i8 mMath;
$ Z0 w- J2 [* p) G- O, `" u" }2 [{ TIndividual }& m1 [! k+ _( p+ w. ]2 M* m7 @- R6 _
function TIndividual.GetFitness: TFloat;
1 d8 _" X, ~: }- @9 xbegin
. S$ k: X0 `0 `' ~+ Q- i' Mresult := fFitness;4 } _0 p. d- X6 L$ g" N
end;
; \& s4 T+ Q! c/ T8 Mfunction TIndividual.GetWeConstrain: integer;' J5 E- F# M" y" g
begin
# d& Q. v7 X# xresult := fWeConstrain;
 J6 Y2 [2 Y- p8 `end;; |$ B2 G; X+ U: N
function TIndividual.GetBackConstrain: integer;" g* A8 W( l9 r( n4 j% z
begin! N0 V5 N" A; h% Q
result := fBackConstrain;
, N% @; N% }1 l* jend;3 ~3 h4 }( L2 [. m
function TIndividual.GetTimeConstrain: integer;
0 k* \4 W, q5 D" Rbegin8 ~! ?8 p/ y" }
result := fTimeConstrain;
' K4 i. Q/ i; vend;
8 ^/ K# s6 I% k; }9 J9 v; r0 Tprocedure TIndividual.SetBackConstrain(const Value: integer);
7 Y: h0 j" r) V+ p N5 Pbegin
& d. L( k% [4 f, G9 S# e% I- ifBackConstrain := Value;
! ~* k k ?5 u% Dend;' N- e" }# H$ _) h
procedure TIndividual.SetFitness(const Value: TFloat);% d( B8 ~) n8 i2 e
begin
3 k) M3 F8 e" q: U) VfFitness := Value;
& ~2 r5 C* D+ X* F& B! T2 jend;
2 P J0 z9 _3 }0 m, c' I8 k kprocedure TIndividual.SetWeConstrain(const Value: integer);
/ Z% S) F W! h# {5 kbegin" q6 u; {: k& d% J
fWeConstrain := Value;- l9 G! _. _3 V6 E! x$ i `
end;
4 k: @- b, M) V& Gprocedure TIndividual.SetTimeConstrain(const Value: integer);
3 R- J; Y! B- o0 d9 q6 hbegin
! u$ }$ C; R" O# S% [fTimeConstrain := Value;9 b9 W, j. n. h% H' g
end;
" x! A! T8 @2 I6 F: U{ TTSPIndividual } X3 A3 l+ z. m) D- H' x
constructor TTSPIndividual.Create(Size: TInt);6 K, F8 c$ d2 l
begin
, E6 b: L* z! p' ?Inherited Create;
$ w; @( b4 B, v2 K: kSetLength(fRouteArray, Size);' Q# Z* ~3 I* Y6 j6 ~7 d' _
// fSteps := Size;9 G$ Y$ G2 D8 v) n
end;; I, X! h7 S) Y- y$ {9 B4 D
destructor TTSPIndividual.Destroy;, X9 J- x3 }4 |4 W* o! Z
begin: v: N) K6 }3 z7 S0 B( {2 t
SetLength(fRouteArray, 0);& S* }8 t! p# Z' p# K3 d
inherited;
: V' B# K7 V- U- @0 vend;
9 s* s0 t! I! i8 O) X( P) e! N5 Qfunction TTSPIndividual.GetRouteArray(I: Integer): Integer;( b* ?* V$ }& f, T; S, e9 i" A
begin3 h: q: U" ^+ y: N7 H
result := fRouteArray[I];
' C2 n/ w6 j) _$ S' T/ Y0 Bend;. X" g1 j* q4 [# S7 p- x9 Q: m: T
function TTSPIndividual.GetSteps: Integer;3 w+ r# D. _4 G. R2 @: T
begin7 _% c% f$ v/ K' I0 l. z7 b/ z
result := Length(fRouteArray);! k r' [0 v/ }8 I% E* l& B
end;
* m) J% ]' W/ c# H$ wprocedure TTSPIndividual.SetSteps(const Value: Integer);2 _# J; K4 \) [* I. N. ~, i8 a
begin
1 S+ G% Y+ i7 [SetLength(fRouteArray, Value);) M. A2 f" f4 l! w8 Q
end;
, I0 x% F4 _8 j/ [& u5 P5 j% _procedure TTSPIndividual.SetRouteArray(I: Integer; const Value: Integer);
' d$ N3 a" N0 b9 D6 [6 Q$ ?begin
0 [- D D" R* Q1 wfRouteArray[I] := Value;; [1 Y" ~2 X C' U% O% G% T
end;
8 D( X# L# ?3 mfunction TTSPIndividual.GetWeConstrain: integer;
) b4 x4 V$ Q o' m6 u4 ?& }begin
9 L8 D% E* ]1 h- R" nresult := fWeConstrain;6 g+ I% J! b5 s! B, m) Q
end;
* `8 r' d1 D! S2 nfunction TTSPIndividual.GetBackConstrain: integer;
' \# E/ q. b+ S7 |; |begin
5 u7 W+ Q3 M, F! L; {' y; L2 v# Gresult := fBackConstrain;
2 | h- e: W0 Xend;
: d4 C& s7 G0 N0 Z2 ^0 wfunction TTSPIndividual.GetTimeConstrain: integer;
# @' {5 U+ _ T& z" B4 `begin
+ |; w/ i; M! K- ^7 P8 vresult := fTimeConstrain;3 e2 `6 Y* R" c( d5 W1 L6 k3 a$ W- d
end;9 @9 a+ S; w: {* |+ y7 m1 }$ Z* B
procedure TTSPIndividual.SetWeConstrain(const Value: integer);
$ {$ e- W/ X; o) H' B6 [& Abegin
' h( _* r) h. x- E, h) A2 \. JfWeConstrain := Value;5 f8 V' _, O1 r% s8 T
end; n) N# N: p: ~+ D3 s! p9 C
procedure TTSPIndividual.SetBackConstrain(const Value: integer);
. I6 c8 x c' e9 kbegin' b3 K$ v) ^# n, r
fBackConstrain := Value;9 H6 d# @" d$ ?) Y
end;
8 ]& T- t$ W' h" Jprocedure TTSPIndividual.SetTimeConstrain(const Value: integer);0 y- r2 M1 }, p* u2 G
begin& t$ n- [' N3 o1 F) z0 z# E
fTimeConstrain := Value;
# ]4 r7 z8 E' H8 w2 x6 Nend;- p c( X" P" E# L# t+ ^9 V8 d
{ TTSPCreator }% R7 L3 B" {" g9 X3 \. }! W' m* s' C
function TTSPCreator.CreateIndividual: IIndividual;
) H6 f# T- C2 |( T+ h0 N. ?var9 f1 [: R. D' e% [7 s. y
New: ITSPIndividual;+ m: Y. ~* [% N5 N, R' M
i, j, Top, Temp : Integer;) y5 E: ?: A% q) y
//trav:integer;
* X) ^7 `1 `. B4 v9 k0 qbegin( p" |: A7 c/ X" l7 M7 s {
// Get the number of cities! T: a0 S' p" w+ |) q3 H
Top := fController.CityCount;
# I X. I7 l4 i; d// Create the new individual
2 F. H9 z2 b, w! r6 u9 KNew := TTSPIndividual.Create(Top);/ q& J0 s) }! T4 J& e$ B ~
// Initialise it with a sequential route' \: {* C1 a! d4 X# S! m/ V9 u
for i := 0 to Top - 1 do! b1 @. l9 O1 H0 Z n
New.RouteArray := i;7 c: P$ ~2 k$ F0 F* e+ A' x
// Shuffle the route
4 R+ q$ B( `" F' A+ \! m, `for i := Top - 1 downto 1 do" u1 h" x: i! f* K3 Q I1 |
begin
' k6 h& O: C) ~( \j := Random(i);) j7 s4 Z C: f; h/ y, O' _1 j
Temp := New.RouteArray[j];* r6 r5 r2 g4 l- Y( d/ f& x. b
New.RouteArray[j] := New.RouteArray;% {: B4 F5 _' s) W. t8 _2 O9 ~9 @
New.RouteArray := Temp;. z/ ~ ]0 n. Z# n/ T6 b( J$ P" [
end;0 X6 k; a/ p! i3 I
result := New;$ k+ S% I; V0 z* i
end;% N3 Q7 j" t( D$ _2 B
function TTSPCreator.CreateFeasibleIndividual: IIndividual;; i+ |8 W3 w! G/ @: E C. t
var
; j+ ]0 `* {" A# p/ d5 \* `) eNew: ITSPIndividual;5 P5 k! m& p: e. Z
i, j, Top, Temp : Tint;& S7 }' V2 D, V) b9 E% [' q
Msg:TMsg;
/ U7 r' L3 S6 u, @" U: x$ Pbegin- y" V/ N i" p' Q
// Get the number of cities
7 E& @8 R. H8 sTop := fController.CityCount;
" y$ B0 w, n$ E// Create the new individual
( P) E. O4 D& t7 f! t6 VNew := TTSPIndividual.Create(Top);- e9 R. V0 A; b$ a! O; |& y V0 J
// Initialise it with a sequential route/ I: e: k& D. h. [! M
repeat4 M3 M8 J m" ]" t: }8 Q% m2 h( M" w- b
begin//////////////////////////////////
$ X) K5 F" |% c$ Ifor i := 0 to Top - 1 do
( A1 N( @# Z; P: t- Y9 {New.RouteArray := i;
 V t/ s1 E# z// Shuffle the route
# ?* Z) g a8 U4 j5 e$ {7 @' mfor i := Top - 1 downto 1 do
( b4 b& k' x" ?" [5 U7 p. A4 S- ibegin
8 {. u9 k; ~6 F/ o/ aj := Random(i);5 \# T" ^: D$ k4 ]0 C5 t+ k: h
Temp := New.RouteArray[j];
" |8 p& i# m( H# t! ^New.RouteArray[j] := New.RouteArray;
; y3 s3 B5 a2 w$ eNew.RouteArray := Temp; ]$ ^* q4 h6 i( x* N1 q7 k9 D
end;; h/ r8 X+ U3 e1 K0 ]9 ?
//process message sequence//////////( Y8 F5 D4 `& y; y% `
while PeekMessage(Msg,0,0,0,1) do//// Q8 q" V( r5 \ z% P V. [2 o. F
begin ///2 P9 ~* B2 P3 }/ u
if Msg.Message<>18 then ///
: ~+ a$ `# P0 Sbegin ///$ O4 d$ \# G- G4 B
TranslateMessage(Msg); ///
/ P: m. {3 _$ j+ J3 [- zDispatchMessage(Msg); ///0 O. F- J, n" O. B+ B$ R
end; ///, Z5 G3 A' w" ~$ Q1 A/ l% N6 P" s
end; ///1 d/ f3 \# S/ h9 ]% F3 ]
////////////////////////////////////
& j. V% h2 {0 _- kend$ Z# m E0 k2 V0 O) n% m: v
until (fController.GetWeightConstraint(New)=0)and(fController.GetBackConstraint(New)=0);' D0 C. o0 g% m- E; t4 Y7 r, r
result := New;/ N. q v9 h% W, p6 X# g3 p D- f
end;9 b, x; e3 l" s$ n9 j
function TTSPCreator.GetController: ITSPController;( w, D! T- b4 n6 g4 ^
begin/ {6 Q1 N5 j* n
result := fController;# C$ i& r7 m: i, k1 D
end;
 p: G/ m% D/ p0 a2 Zprocedure TTSPCreator.SetController(const Value: ITSPController);6 I7 P" W% S2 W. k8 {
begin; Q8 {: @, d3 K l7 j* U/ F' } |
fController := Value;/ Y% Q* r/ L' H/ O6 Q
end;
( c8 g6 a8 M, R" B{ TKillerPercentage }2 x% `" P4 Y" W, |8 f- x# W
function TKillerPercentage.GetPercentage: TFloat;
/ K3 l- H G O$ E/ kbegin
& g6 y$ P8 _8 c, |result := fPer;
, n, T1 H# [3 |# v: g- Zend;
" i: B7 N. c# S* vfunction TKillerPercentage.Kill(Pop: IPopulation): Integer;# D5 t3 t+ ]' G1 i
var
- j2 b b) F9 O; B) g% b2 L( AKillCount, i : Integer;
2 r- p: a. }3 ^/ L4 \6 Nbegin3 v( F1 m! |' `* j! u
// Work out the number we have to kill6 G; ?" g [* a! L+ b: p! B
KillCount := Floor(Pop.Count * (fPer / 100));' ^' v. o+ z. ~; i
// Delete the worst individuals - assuming the population is sorted8 \* {7 ]3 n9 u* l
for i := 1 to KillCount do
; L. N, d7 j4 y; MPop.Delete(Pop.Count - 1);' N% A' v4 f5 \, u6 z0 i$ I7 m
// Return the number killed
2 F* p" {5 E! h; ?Result := KillCount;
" F, v4 k: |" Uend;
& c% A/ ~$ |5 m; z( Nprocedure TKillerPercentage.SetPercentage(const Value: TFloat);
0 c/ b$ E: r& ^! }" N; ^# W, Ebegin
0 K! b/ p6 p1 S7 h+ x- FfPer := Value;$ {* ^3 a$ A% c2 x& x: ?
end;: E6 k* x$ U6 w: S
{ TParentSelectorTournament }
* Q4 e4 ^$ I2 p! {! v8 D+ ~function TParentSelectorTournament.SelectParent(3 ~& E. S; t" R
Population: IPopulation): IIndividual;0 x9 ~& D7 p# d7 n3 Y
var
- y8 l I) L. A2 h0 Qi1, i2 : Integer;
4 Q. m5 C5 i! a6 c5 J! Kbegin
6 c' A/ h* p( R' ?, I0 Y// Select a random individual: I: u( `9 b' ^9 o
i1 := Random(Population.Count);4 R5 ?: C( G8 O$ k
// Select a *different* random individual
* u" {5 b$ o f g" u) Erepeat2 H' ~* b" O, D1 g8 s
i2 := Random(Population.Count);
. M9 o, u: V! Buntil i1 <> i2;. j; y7 H, W* u( r2 A$ p0 R% h6 [! j
// Hold the tournament and return the fittest of the two
! n$ J, S. K4 J# l0 M8 Bif Population.FitnessOf(i1) < Population.FitnessOf(i2) then1 R( @( I9 x, m. K% C- Q: U
Result := Population[i1]
' |% t! T, v# j6 o4 F | _else
0 w, r X8 Z. r+ Y, KResult := Population[i2];2 `& ?; ?+ W2 Y6 m( I
end;
% k" w2 q! J! r5 y{ TTSPBreederCrossover }
7 X2 W' O* ^! a* w! y4 ?) |& Sfunction TTSPBreederCrossover.BreedOffspring(PSelector: IParentSelector;
: ^# O) _) ?0 U. T# t, t$ cPop: IPopulation): IIndividual;
6 I" H* R: d* S; [! Evar
4 s8 |, |2 h1 e) O6 EChild, Mom, Dad, Parent1, Parent2 : ITSPIndividual;
3 q, F" n4 Y% wi, j, p : Integer;, m( n1 u( s" P8 q2 |% P
function AlreadyAssigned(City, x : Integer) : Boolean;
4 _$ }8 ~* q) Zvar n+ [' X/ s" M$ a. m' M) j! G: O
y : Integer;
0 R: W; L9 @1 N7 WFound : Boolean;# o- X1 B( T. L: V$ u: |; O8 F
begin
' x. d+ d; g1 s( F* W6 EFound := False; 3 B6 Y$ n4 s+ ^
for y := 0 to x - 1 do/ I" M# ]! u; V' D
begin
: ?5 s" n8 j% F& R# b& J- `" t2 cif Child.RouteArray[y] = City then 2 Q4 |3 A$ L' r. F1 R7 h" ?
begin 4 x% |4 H% o& t, Y
Found := True; 6 @7 |: r6 n* X0 v" \
Break; & R1 @% u! T- ?8 R0 n, g
end;
7 v9 s! G6 n) J/ h) s n iend; 2 i$ {& ?, E; o/ ~
Result := Found; 1 @0 f8 r+ Q+ l0 b2 `
end;
: j* @2 T4 h- o9 y! O9 e0 h- Kbegin " [6 s, v) n1 A% K4 U# e
// Select a some parents...
3 u7 v1 x7 @" q- e" V+ TMom := PSelector.SelectParent(Pop) as ITSPIndividual;, } s6 O6 i8 [0 I- A
Dad := PSelector.SelectParent(Pop) as ITSPIndividual;- ^0 H" w9 K; S8 b/ ]2 s
// Create a child
- f$ ? x8 [9 r& AChild := TTSPIndividual.Create(Mom.Steps);6 O8 H& x( J' C. Y8 ]
// Copy the route from parents to child
: s! ~* g3 u; v; Q; y: gfor i := 0 to Child.Steps - 1 do
% W4 E6 } V0 v0 \2 ibegin ' } g! [! d# a
// Choose a parent at random ' q+ ~4 @7 B \) V$ B7 P! j& @
p := Random(2);
) f" u+ i4 J t6 W! y2 `/ [if p = 0 then
2 n9 \ d/ W6 }$ J! sbegin 4 r! F( F& `1 o" X
Parent1 := Mom;
9 {5 {# H1 r T5 NParent2 := Dad;
6 G7 ^7 q7 V* V; Z2 i. g2 Cend else
% ]9 v, n0 j8 z6 Nbegin " h! s) R9 e% u) i2 A g+ @
Parent1 := Dad; - s% T, @4 Y8 Q
Parent2 := Mom;" [8 C7 J1 d7 w- {2 {
end; ' F* E g1 e# J$ n
if not AlreadyAssigned(Parent1.RouteArray, i) then ^% d' d: E& Z8 J3 n3 x0 ]
begin ) A+ H8 a3 K" L# B9 t9 l
// Use city from Parent 1 unless used already 1 m! [- T# N. V/ ~! U3 D) ^
Child.RouteArray := Parent1.RouteArray;
( G# P4 d$ m' ]% i1 dend else
2 G7 U5 p# d: |7 Fif not AlreadyAssigned(Parent2.RouteArray, i) then
$ f, i5 A# l$ ?* H. e$ }begin ) j1 r! Q# d( ]
// Otherwise use city from Parent 2 unless used already
 _, B$ Z+ R# }. a- t: I- l8 mChild.RouteArray := Parent2.RouteArray; 2 j) F B! F k( h, a; [
end else 7 X+ m+ i3 E) J. P8 }
begin
3 G+ |4 D4 e; B/ m- R4 k! u// If both assigned already then use a random city / X( y7 j, E! F- X/ c# d* b! L
repeat
$ d N% A7 O+ Q, `. ^/ Bj := Random(Child.Steps); 9 n) C. H6 L- K4 U1 o5 {* D# x ?
until not AlreadyAssigned(j, i);
/ {. j2 I; V6 W0 LChild.RouteArray := j; D4 d0 m) X9 V% _, l) c: P. j
end;
: ~8 ~$ x6 v: nend; - e( ?3 g S$ N' z: N% J
// Return the child
! W$ Q8 ~$ S0 r% y: g! t5 `Result := Child;- w# k& ?4 c% c2 @* C( A- {" f
end;
. n/ v# f2 R6 p- t) a4 L{ TTSPMutator }
4 @! D6 V1 W; b7 A& Sfunction TTSPMutator.GetInv: TFloat;: A, a1 ~* H9 X; b
begin
& }8 A% E( j/ f# K% iresult := fInv;
& n; G+ q* J3 Y$ O1 Rend;
1 A6 h) C7 \: _ `; Yfunction TTSPMutator.GetTrans: TFloat;
2 X* f, ?6 f; G3 _4 ebegin3 e8 U4 \* [% G/ g- R: \7 o
result := fTrans;( A. Y/ ?6 d* }1 r9 } P8 Q5 s
end;6 z, Z$ m8 Q$ j N$ N1 a8 i
procedure TTSPMutator.Mutate(Individual: IIndividual);
3 V+ B5 }6 I, @( F+ m% a! [var
5 N. U7 ?# x9 T( B% QP: Double;
9 l, ^9 n2 V9 ?3 z( I/ @i, j, t : Integer; Start, Finish : Integer;
" |, t0 ~& J& Pbegin
! n2 }8 R5 Y: \3 W( m. Jwith Individual as ITSPIndividual do
$ y: n. `# _6 [$ P* q* K( ~begin
5 g6 r% U9 O; B* a* k" T// Should we do an inversion? 3 k1 i! d, _1 r
P := Random * 100;
1 [: T/ D, z" S+ ?9 eif P < FTrans then & y* n& o6 K2 }3 e$ }9 u
begin
6 P- F6 m, r' f$ X& d// Do an inversion (i.e. swap two cities at random) 3 m- }+ N8 t% K8 ?+ ]+ [
// Choose first city
. b4 P# ?- q1 d# w/ I. Ti := Random(Steps);
$ E: T$ d' o- k- P/ ]5 g0 c// Choose a second city ( {4 p3 f; x7 ]: i: y+ Z! i3 O
repeat
8 {- T$ ~; r8 r; e7 Zj := Random(Steps); / q% i! E/ ]) E, s. e$ |. Q
until i <> j; 6 m! q6 L; K/ a; c7 u/ c
// Swap them over
) ]& B! B( r2 @% J) r' W, St := RouteArray;2 H) w) Z$ i/ |* C r/ V2 Y
RouteArray := RouteArray[j];$ n! [5 V9 [. B$ D+ \0 J
RouteArray[j] := t;
0 {2 _- T2 l1 O1 o' bend;
( R( a0 l" D, s// Should we do a transposition?
2 c# d* T. @& y$ g: P: y1 jP := Random * 100;# [' n$ _, v7 w' Q. B
if P < FInv then
7 a9 V g L' {. Sbegin
! m8 V0 M. K3 o! r// Do a transposition (i.e. reverse a sub-route)
, Y+ \. r# |' P8 u$ b4 y% \% W// Choose random start and finish points9 v6 S6 u$ T+ _8 K+ K4 [
Start := Random(Steps - 1);
6 D% z1 e8 }# ]4 UFinish := Start + Random(Steps - Start); e( R5 ~1 l" w8 @- w
// Reverse the sub-route9 x8 R4 o, Z/ C1 @' r
for i := 0 to Floor((Finish - Start) / 2) do! a$ z0 A9 b; W9 ^) \* D- F
begin
1 a) K+ L9 d" h4 Pt := RouteArray[Start + i];
% x7 K# C7 y# E1 K( o! k0 \. sRouteArray[Start + i] := RouteArray[Finish - i];5 _( W2 A9 \/ u+ u0 Z
RouteArray[Finish - i] := t;0 i: `! ?1 ~! i0 J
end;
2 q" J" r! \" n$ r `end;6 K5 F: z. |* u5 i- f& f* y q
end;- m; H. G& |' y, n2 H8 @
end;
0 {: a& f0 L/ |# X/ O7 xprocedure TTSPMutator.SetInv(const Value: TFloat);/ ~" r3 ~" S# d- M
begin& t7 x$ {, h- b* E! `7 j. {
fInv := Value; E) B! x s- ~6 r3 D1 K; P' X" W
end;) G! ^% o/ s/ p+ i: ]
procedure TTSPMutator.SetTrans(const Value: TFloat);1 o8 D' C) Q5 P5 E2 ^$ U
begin
, R' t Q, J, U2 ]0 FfTrans := Value;
" z, X5 E2 B1 u; [" T! b. Rend;+ Z" Z1 ]8 [$ u8 ?
{ TTSPExaminer }
% x# ?8 ~& |+ L* H& ?1 ]4 ^% F6 Qfunction TTSPExaminer.GetController: ITSPController;
0 w" n+ E/ Z; K! V- e- |. U4 s4 y! ebegin, r* ?+ v* O4 H( U2 G
result := fController;, u& c% |" }' E
end;, i2 |4 V2 @% ^# P
function TTSPExaminer.GetFitness(Individual: IIndividual): TFloat;
9 V! k8 Q$ o _* ^var' x: Y& {) `( I& F; z, q$ r: I
i , weightConstraint, backConstraint : TInt;$ {; K: i3 X: \2 Y _9 ~. N/ A6 W- g' v
Distance , penaltyW, penaltyB : TFloat;
- Y4 h" y; p2 ?* k8 C kIndi : ITSPIndividual;
1 h2 V8 n0 ? x( L+ g* {5 Ubegin
9 ]9 x6 A" y+ s/ T H6 `2 xIndi := Individual as ITSPIndividual;
$ Q' P, k; m: {' M5 NDistance := 0;" e7 h z" K% y! @+ ?
penaltyW:=FormGaPara.EditWeightConstrain.Value;
) }5 ]( _7 o6 bpenaltyB:=FormGaPara.EditBackConstrain.Value;
' z/ V) r# m3 u9 m# Jfor i := 0 to Indi.Steps - 2 do1 ?4 H7 u1 S& Z" ~- ^
begin* l0 I1 [$ T8 t7 x
Distance := Distance + fController.DistanceBetween(Indi.RouteArray, Indi.RouteArray[i + 1]);
 ]$ x, y7 x0 ]: ^* ?4 i2 Rend;
. M9 O) D9 t5 r( Q- L$ p% G: m5 NDistance := Distance + fController.DistanceBetween(Indi.RouteArray[Indi.Steps - 1], Indi.RouteArray[0]);, c1 p) J" m6 d1 X: L% ~3 Y0 M0 G/ `
WeightConstraint:=fController.GetWeightConstraint(Indi);
' v0 A$ {. ]+ d1 `6 H9 E. \, ~backConstraint:=fController.GetBackConstraint(Indi);
 C$ d7 q: }2 h- L0 A/ L" @1 b8 GIndi.WeConstrain:=WeightConstraint;' p& o: o4 [; t
Indi.BackConstrain:=backConstraint;' ]& Y, W0 d& P. y- Q! t: g
Result := Distance+penaltyW*weightconstraint+penaltyB*backConstraint;
1 }" t1 {* _# O: Bend;
6 t: {3 H( X; d3 _) r5 Rprocedure TTSPExaminer.SetController(const Value: ITSPController);( I( ]' a: e. r0 I9 Z: [1 c
begin7 O3 Q$ f: c8 V* }' t2 E
fController := Value;9 r; p# N ?3 a5 a3 H0 L
end;
/ }3 j6 z+ f* B0 l{ TPopulation }
: L9 u9 D* X5 ?/ c% y: \4 B Bconstructor TPopulation.Create;4 g* U2 [0 t' U; o; [) k
begin: Y8 p' x; e# B" V$ r
inherited;
 _$ X; A d$ ^fPop := TInterfaceList.Create;
4 M0 Z! u) m4 g0 r: Z. h+ wend;
9 V* \! C9 q0 r+ Tdestructor TPopulation.Destroy;$ F% f* m f% ~7 O1 j* i+ Q9 o2 J
begin
! O0 O1 s1 r+ ` HfPop.Free;5 ]' x8 O: n% N! u
inherited;
" P# I( e# ?* K! D% M: send;
! v8 S; A, f/ k) R8 Iprocedure TPopulation.Add(New: IIndividual);
. p$ E, W9 x/ H+ [" Ubegin
. N" V* K* k ^$ AfPop.Add(New);
4 [/ {* y. ]- ], c9 g/ v' E4 zend;
# B; s2 U! ` C6 B& U) Y* Eprocedure TPopulation.Clear;; u; J- l! R" S" i
begin! N4 a; w; P* M9 {% P/ k
fPop.Clear;, \* _% B y. N* D: g
end;
# }4 e0 U, i7 k1 f! t# {& M9 h4 {& tfunction TPopulation.CompareIndividuals(I1, I2: IIndividual): Integer;4 R: z1 W4 ]3 _8 b9 W. n$ k
var. m9 h' _/ H2 F$ L7 }) a8 g
A, B, D : TFloat;3 ^. F& t* y1 E3 N* \6 O# L2 S
begin
2 x; U5 P( N* ^, P! w0 g+ e# @4 j1 f// Get the difference between the two individuals (real number); S: ~- c# R- I0 j% n
A := I1.Fitness;' U' P6 { Z; p# A7 \- Y* g
B := I2.Fitness;
& j: O1 y4 U& w+ A& i$ ^$ UD := A - B;7 L3 M, i9 ?9 B, l( n
// Quickest way to convert that to an integer is...
0 G1 N% p; u! a2 e( Zif D > 0 then
4 u1 B2 f) O" R- L" O0 `Result := 1
# P, Z1 A. r$ w( r3 c+ Eelse if D < 0 then: Z5 q! T: @/ F& ~/ O& N1 l, ^
Result := -1
/ P7 w$ a! ^, w0 _else6 ~9 s# u% d. b6 b7 r% x: s$ \ c
Result := 0;
" O, b% T1 L1 b8 \4 _) `3 Zend;
+ }& k: s4 k& U+ [procedure TPopulation.Delete(I: Integer);
3 w6 S' O5 R' f. I* w1 }begin2 m! N0 z) ^: p# |; W8 a. f1 g3 J
fPop.Delete(I);
$ k- ?8 l( v2 k: V' eend;$ }# z2 T) ]$ v+ o! K# [
function TPopulation.FitnessOf(I: Integer): TFloat;: n4 q' k, z/ |7 g1 }- @
begin/ e& v+ Z' @2 a) `
result := Pop[I].Fitness;
! R( T8 o. B+ Q, Y2 B) v2 I6 [end;% g3 Q4 C. D0 L* J: ^0 O. z0 x
procedure TPopulation.Change;
9 g' R1 K L, Z* S* c9 dbegin
- X& s* [6 W4 Y6 M- G: o- F" vif Assigned(fOnChange) then- E% R/ F2 H. O) a+ m1 k
FOnChange(Self);! ~1 M0 X% }0 Y* w2 ?* ]" ?
end;
# l# A( Y3 {2 p3 W) Gprocedure TPopulation.Generation;, y3 I" ~& A/ U& m2 t
var
/ l1 H/ O/ I. \+ I# BReplace, i : Integer;4 I/ [, G9 a1 f( l; M' K# A& o
New : IIndividual;; q% F5 o( _. {1 {3 g2 p
begin
7 e. Q) g0 P7 c+ H8 H$ b! \; [// Kill some of the population! K; j& g [7 O
Replace := fKiller.Kill(Self);
' v! ?6 z1 \6 l, l4 I3 B+ hfor i := 1 to Replace do- f i( n' u$ @' h& z& o
begin
( R4 t: i5 c$ m3 _// Breed a new individual* V4 f1 H5 r! |, m
New := fBreeder.BreedOffspring(fParentSelector, Self);
3 H8 I* T7 Z* y. B0 X, g3 ]2 m// Perform some mutation on the individual, c0 W. o2 A! X/ u
FMutator.Mutate(New);. |7 q3 M+ }1 ~* T1 v9 v
// Get the fitness of the new individual
5 G" o6 Y1 u! t; VNew.Fitness := fExaminer.GetFitness(New);
8 k! O1 D2 {6 d! T; W9 W% `, w+ E8 ~// Add it to the population. p: P, C+ [8 }! M
Add(New);# h/ y$ h* m0 v) i2 y
end;9 T8 N: ?) X* i7 [" m- N+ X: U
// Sort the population into fitness order where first <==> best
, Q( p. v5 @5 l" c$ N3 C' MSortPopulation;
% o6 D0 d, E' LChange;
( X$ [7 \: {) ^end;) P! q; c0 d, i g
function TPopulation.GetBreeder: IBreeder;8 j1 n# B7 g( A
begin8 }9 V, x6 p, B$ c
result := fBreeder;% \4 I+ u9 c9 Y# i# U2 Q. m
end;- K: L' a) } l6 m0 J1 e
function TPopulation.GetCount: Integer;7 @- l. T5 h) l
begin
: }' {" g' Y! o7 T/ f3 j6 e3 j$ n3 vresult := fPop.Count;2 m, [& o- j% d$ N2 B4 T
end;
4 g$ ^/ r, U) S9 M3 Y' tfunction TPopulation.GetCreator: ICreator;
) A& h& X+ J. O& D5 Q$ Qbegin1 R/ k" j6 W7 Y7 R: W m4 ^8 Z
result := fCreator;
% u7 u* T: T% q% Z6 Lend;
; F& n6 A: Q1 ~# Cfunction TPopulation.GetExaminer: IExaminer;6 ?3 |+ q; y. w6 k q
begin/ v& G6 f% e% w; ]9 a L
result := fExaminer;
% ` v1 g. d0 V, qend;8 G# K, \7 c, L# o5 i8 H2 ~
function TPopulation.GetIndividual(I: Integer): IIndividual;9 I5 T* R" A4 G6 {- w- J+ t
begin& y1 D/ ]. V) W. i3 R7 m
result := (fPop[I] as IIndividual);$ F1 ~& C2 U' @% _, p% D/ ?' w! s
end;
2 j. a% p6 g( f+ N" r( Pfunction TPopulation.GetKiller: IKiller;; p" |8 y5 {( D. D' D( B7 |
begin
* {* A% O6 q: \4 @8 R) v. aresult := fKiller;- }( e6 |6 _6 ^; r" K q0 S
end;
& l* r5 o5 G; I, M$ ]function TPopulation.GetMutator: IMutator;
! B. `! @7 s- r# T7 n3 d, k# bbegin" F. Y; p0 d% ^# N+ n& m9 `2 V8 c
result := fMutator;. q" I- c: S Z" v% e
end;
/ k! `) |/ U% hfunction TPopulation.GetOnChange: TNotifyEvent;
3 K4 k& P" ?/ t( A) T- ybegin
- ~! L7 a3 v8 Z/ c, ^7 u- zresult := fOnChange;8 N" B! ?$ ` E0 G( U8 |; l% `
end;! w( l; @) K8 q
function TPopulation.GetParentSelector: IParentSelector;# _! T! P7 o2 F/ @3 u9 j4 t4 q
begin
: U) \7 C4 J' H" y+ y1 ~) uresult := fParentSelector;4 x7 T! \0 c; D
end;
0 w P: p$ E s: u N/ M: l5 D# Xprocedure TPopulation.Initialise(Size: Integer);" j9 ]% i! m. i- |& B5 L; \% Y) q
var
6 y' }& c" P( ? Ti,feasibleCount: Integer;, ^# L3 Q7 r& n
New: IIndividual;0 Q; c1 ~! b) x' I
begin; u3 H: O v9 A1 U# {. `0 v1 T
feasibleCount:=round(size*(FormGaPara.EditFeasible.Value)/100);
6 {4 ]( q8 U1 ?0 u) Q& t4 Y! D//feasibleCount:=1;
9 [1 u- o( ]2 L* O% z7 M' H// Clear out the old stuff
/ d: L9 Z; F) i5 a# o+ S3 y2 J- BClear;
! z1 D) u2 y# c1 O6 X* {// Set the capacity first to save about 12 nanoseconds ;o)7 }2 r/ z: i* l! G# f+ [4 u+ a
fPop.Capacity := Size;$ b6 w; m6 T' V Q
// Create the appropriate number of individuals4 O' j9 ^, E, Y" B8 |, l8 C! g7 k
for i := 1 to feasibleCount do; z' M9 z) a( k' I/ d" s9 B7 i
begin) V0 k* I( E0 u
// Create the individual/ K; A1 t. ^ {- G: k. A
New := fCreator.CreateFeasibleIndividual;
% z2 ^. F( M( p6 L" v// Get the fitness of the new individual
- ~" l- R( M5 U: P. aNew.Fitness := fExaminer.GetFitness(New);
, b" p0 i; D1 s5 l// Add to the population3 m) m! S8 \5 P: P- Q6 |% ~$ G
Add(New);
0 V1 H* [6 n, A. ?end;8 {5 s' z. T; p% ^# n: p
for i := feasibleCount+1 to Size do
. I9 m' p1 c9 z; x. Gbegin8 | ^, j8 K- l
// Create the individual
( s: g/ ~/ _; A7 jNew := fCreator.CreateIndividual; ////////+ D4 s; ~' ]5 x+ F7 V9 t0 Q
// Get the fitness of the new individual) {4 Z! y' ^$ {. E1 ?4 o5 S5 n
New.Fitness := fExaminer.GetFitness(New);
5 p$ S. e5 f w7 V// Add to the population. I" ?& \' h/ C$ e6 x
Add(New);6 K3 r% ~! P, L% N4 o; l
end;
4 }/ b' o5 n9 W5 I+ |: XSortPopulation;/ ]5 K7 l/ w; _4 H) A, f3 r" e
Change;, i9 ]9 E. l/ o/ ~& m
end;' J" F, B# E8 ?+ O3 o: y) F
procedure TPopulation.SetBreeder(const Value: IBreeder);
; u8 A! D& w- I J# n" i* @begin
- ?* L! m6 e N; B% {fBreeder := Value;
/ @: e3 H$ U3 N% [; Dend;
4 p# R5 _/ a7 ]& w: ?3 Oprocedure TPopulation.SetCreator(const Value: ICreator);. S6 I; }* v9 i7 h: l
begin
$ V. `" D! P8 e G: [fCreator := Value;9 J$ R3 V) Q% i/ E% J/ Z# H" S
end;3 d. U0 X2 F3 s5 K; x( T' `
procedure TPopulation.SetExaminer(const Value: IExaminer);9 d+ C, s+ d, ~% g4 E! v
begin# E- V- W- W5 M, U
fExaminer := Value;
$ Y; n0 Z4 P+ r( U; q* z9 S& eend;
2 C" N! n, K# ]% ]9 V) e; ^procedure TPopulation.SetKiller(const Value: IKiller);: B" H, G% h5 e
begin7 U. v/ d! A" p1 A
fKiller := Value;
) q6 }# S, C3 E5 L: z5 ?end;
- q/ X% ~" h, D; ^procedure TPopulation.SetMutator(const Value: IMutator);
) k; F; e. D, _" E: C4 ]- Sbegin( {% t( ?5 `2 }6 E. e
fMutator := Value;
5 U$ ^$ P' a. Iend;7 k4 X+ y. B g# f6 t4 z2 V
procedure TPopulation.SetOnChange(const Value: TNotifyEvent);
0 v/ S5 n1 v; `8 V7 z6 O jbegin7 b' y: c5 P, G
fOnChange := Value;
9 c1 b" r$ s9 v( k) ?8 L+ {end;) ?1 E+ M7 H. E2 K5 z
procedure TPopulation.SetParentSelector(const Value: IParentSelector);
( ]7 ~6 Z% s Y" t5 zbegin
2 E( t6 w5 k, n8 R3 xfParentSelector := Value;+ l6 c# g9 K. ?$ K# E3 }
end;8 f ?4 Q4 l8 e
procedure TPopulation.DanQuickSort(SortList: TInterfaceList; L, R: Integer;+ K8 b& Z7 b8 \0 S0 y
SCompare: TInterfaceCompare);' s' {9 _. J6 O9 H+ x! F
var
6 ~+ u: n1 P9 e* }, e; \I, J: Integer;& }/ d1 t" u- C8 w$ I& Y' V
P: IIndividual;
: r0 r Y1 h! Zbegin6 L/ J( V( a9 r) r, z( n% L/ [
repeat* _* k& {# l( y- {
I := L;
$ J4 S, R) X! {: B. L* N& g3 ^# mJ := R;
" n3 d. G& O% c) ?4 h G* u$ m. oP := SortList.Items[(L + R) div 2] as IIndividual;
2 i( w- l' B# k; d2 _! erepeat) B- y3 t- q# d0 s! P; U, ~. N0 S
while SCompare(SortList.Items[I] as IIndividual, P) < 0 do+ L& |6 `% N( V, v/ J
Inc(I);
3 j7 u6 C+ [' H9 n4 Mwhile SCompare(SortList.Items[J] as IIndividual, P) > 0 do
* t: ~1 a0 V2 A' `6 D# { uDec(J);
 O: {1 ~1 y& f/ v' Y5 u. _9 u7 }if I <= J then
1 Z$ L4 L. h9 w3 U& ]# ^: N" E, [begin; k, k$ P% ]! O4 S
SortList.Exchange(I, J);
) o4 m& G6 p/ O9 p( T! n# tInc(I);$ y( Y7 e8 K: f, H. H# a- `( C
Dec(J);! C: h' o/ f% R
end;$ _2 k5 J; p' v8 G# n6 L# X
until I > J;
+ t: m* N! c6 T5 ^* qif L < J then
$ b" `& }# Y) ^0 P, I: j; J7 MDanQuickSort(SortList, L, J, SCompare);
" Y9 k) S- J5 D& _0 e3 k( yL := I;
( q$ c6 `) [/ {, puntil I >= R;
4 y. \( _: _5 f; y0 v, {end;
) C$ v8 W( h" Oprocedure TPopulation.Sort(Compare: TInterfaceCompare);
0 R1 ?% b! F% o8 S1 |begin
* G' z. K3 p+ a& Jif Assigned(fPop) and (Count > 0) then
7 r L! j# K/ o1 UDanQuickSort(fPop, 0, Count - 1, Compare);
8 I2 e# ~' p9 B9 Pend;, ]) L$ f8 n3 Y9 j) Q" q
procedure TPopulation.SortPopulation;
# {. |5 n' {5 Dbegin
; S$ B/ m* Q) }4 j& OSort(self.CompareIndividuals);
# {/ P! t) u3 Send;5 z8 @$ x1 H, z5 a$ P+ H# n2 w8 F
{ TTSPController }/ q* @' k9 g D9 z4 C9 R
constructor TTSPController.Create;
, D% W9 k. K* L' F: j% Jbegin1 t; a. L3 A9 b1 h9 F5 _ G
inherited;
/ l3 T0 J% M+ h: k- k% Y8 z0 `" Pend;, G2 s7 n$ G* _3 v
destructor TTSPController.Destroy;
# u F d1 P- H$ R Gbegin; i5 D, T, h0 o! [+ i/ s
SetLength(FCities, 0);
" q6 B5 }9 x) h* Y0 iSetLength(FNoVehicles, 0);
. Y# \( h: E+ G1 p& f1 `SetLength(FVehicles, 0);
- Z0 @$ c Y- \ L4 [6 i( }inherited;- e3 ]. S) ~! G% A
end;
' c; C+ I7 p1 {2 y{ Standard euclidian distance between two 2D vectors... }
# [4 q# |) x. d+ w5 ~function TTSPController.DistanceBetween( C1, C2: Integer): TFloat;
; D7 {* `# {0 w9 p9 `& p6 V5 N/ ivar
& M0 D1 Z8 I9 E* wtemp:TFloat;
4 r7 {2 M% F% t5 k% q/ xi,j,intTemp,intTemp2:TInt; 5 l- ^- S7 n! Z" l
begin
! f5 W9 C5 A1 hintTemp:=0;: p" T6 e+ w, j- K6 P5 Q
temp:=FormGaPara.EditWrongConstrain.Value;8 K; `2 i, `% S, f
{if (Cities[C2].id>=1)and(Cities[C2].id<=fOldCityCount)and(Cities[C1].id<>0) then$ W' t9 Y$ X$ y: A1 o L
begin) _3 |- G! q$ }2 |8 U( l
fCities[C2].serviceDepot:= fCities[C1].serviceDepot; f% G* Q- H8 Z' S: W" g x
end; //}
' [' A9 i' H" ]//86 X: q2 `% q# v: D; u
if (Cities[C1].id>=1)and(Cities[C1].id<=fOldCityCount)and(Cities[C2].id>=1)and(Cities[C2].id<=fOldCityCount) then) H$ p. b0 j7 M- O1 `! q6 X; n) @
begin! ^- i; t/ [2 {% }! V) h) n J5 O
temp:=CostArray[C1,C2];% U% X4 w1 g& \
end;
0 n% ^$ ]" z- |# h//1 k; l, j- E8 r3 K" f) ?
if Cities[C1].id=0 then 6 N# H" [$ r2 o7 U+ y( q, v5 E1 h
begin
! t+ ? Z) ^6 S" l- P* T; v0 qfor i:=0 to fDepotCount-1 do
+ V6 t. s: I) @8 m" w3 Gbegin
' C6 Q: u7 a; Q$ q0 wintTemp:=intTemp+fNoVehicles;+ ?8 Z% |1 q- Y% P# X3 e& q* i
if Cities[C2].id =fOldCityCount + intTemp +1 then2 ]$ a% f6 M% r) c# q
temp:=0;
' q* H* G3 }' i& J0 Vend;( ~& K, x J6 D& I1 R' \: m
intTemp:=0;
, P0 R3 a/ m- r( h, send;+ i: ^7 ?) O% x# \5 u1 D
//28 Y) b0 \; @8 u! K# ?' X
if Cities[C2].id=0 then
 ]6 \% O0 l( u( ]' [begin
5 [: Y9 R3 y* r1 }for i:=1 to fDepotCount do; Q* l; v. N3 S. O0 Q: x, m
begin
' X! @7 `' i8 n# u& \intTemp:=intTemp+fNoVehicles;
4 Q; F+ i% t. ^if Cities[C1].id =fOldCityCount + intTemp then
6 c2 g+ j+ A# M# btemp:=0;4 B5 S n% J7 P2 @) z9 I( d
end;
6 N" s9 r! ^5 J9 [intTemp:=0;
( B9 K8 t( i2 q% }end;# t9 A; r2 i& A8 Y; a
//53 F7 i G G# E7 Z+ Z
for i:=0 to fDepotCount-1 do
) n( V' z. ^! r, G8 Ibegin
4 }+ z4 v3 t' J# y+ f' XintTemp:=intTemp+fNoVehicles;
- M& ~' ?, X: j) L2 o" p7 U9 J/ r{ if (Cities[C1].id=fOldCityCount + intTemp +1)and(Cities[C2].id=Cities[C1].id+1) then' z' Z3 j4 F0 [. Q. H9 C
temp:=10; /////////////////////////// }
; X: d$ O+ L8 h! O; z: Y! Mif (Cities[C1].id>=fOldCityCount + intTemp +1)and(Cities[C1].id<=fOldCityCount + intTemp+fNoVehicles[i+1]): ?& g% e3 L( W$ M
and(Cities[C2].id>=fOldCityCount + intTemp +1)and(Cities[C2].id<=fOldCityCount + intTemp+fNoVehicles[i+1])2 e2 I. v1 C9 x+ w7 z. h
then
8 \7 S5 s. ^$ l2 |" htemp:=0;//}* p! g, ]! A; e; o# A* d
end;
: X' v% `( m! F" `. x# Z% ]2 }intTemp:=0;" i9 i3 Q. W3 P1 K0 G- n7 ]& K$ B
//74 H; |# b# H& V. X
if (Cities[C1].id=Cities[C2].id)and(Cities[C1].id > fOldCityCount) then) D% g& s; F, z) i% p& s. Y# L: n8 n
begin
( W" @2 b) r0 c, q/ h% ntemp:=0; ?% E' y3 Y- o S
end;
( j! g7 }0 W, V; t; ^! z# ~- R, H- }//3
* j0 N1 ]: _9 t6 E6 k) ]if (Cities[C1].id > fOldCityCount)and(Cities[C2].id>=1)and(Cities[C2].id<=fOldCityCount) then
3 T3 b, z( N6 ?+ W0 j! }begin
- ?; Y6 s# v+ ^. C//temp := Sqrt(sqr(Cities[C1].X - Cities[C2].X)+sqr(Cities[C1].Y - Cities[C2].Y));5 F1 ~! z$ a2 f: t$ N, y
temp:=CostArray[C1,C2];
' D+ |' z& S- Mend;
7 B- Q9 x% n; F//4& I7 g- e; h S& ?% t7 y
if (Cities[C1].id<=fOldCityCount)and(Cities[C1].id>=1)and(Cities[C2].id > fOldCityCount) then
" T+ B; O/ Z: bbegin
$ F3 G3 P) ?5 g//if Cities[C1].serviceDepot=Cities[C2].serviceDepot then //back to the start point6 S% A# e# A( [1 J- o$ X8 X
temp:=CostArray[C1,C2];$ j/ u9 l$ P7 g( j, l; l# E8 \/ a
end;; b. C# j' ]/ ?8 b" L6 e
//6
+ E0 n0 `. i% b& \intTemp:=0;8 K4 A" A- k" M: _% \
for i:=1 to fDepotCount do 3 K& g! P+ x( g c! j9 m2 I/ ?
begin: o) Y% S T8 w' Q5 ~. k6 ]5 W
intTemp:=intTemp+fNoVehicles;# r- B4 i. k* Y _
if Cities[C1].id= fOldCityCount + intTemp then( N0 _2 x, r! w9 O
begin
, q" a& u$ l) \5 f8 ?9 eintTemp2:=0;
for j:=0 to fDepotCount-1 do; Q/ A5 Z! @. K& T( z' b
begin
: G! }' d Y* ^. `intTemp2:=intTemp2+fNoVehicles[j];& o7 [4 e" L& n S/ |
if Cities[C2].id=fOldCityCount + intTemp2 +1 then: w% U6 P- ^ i) [
if abs(Cities[C2].id-Cities[C1].id) <> fNoVehicles-1 then5 M5 t' W+ M/ ~% _
temp:=0;' f+ \' w* C5 h
end; //}
+ t; \) H: e! Q' P# iend;7 x$ ?& A3 ?- f `# P& o% m$ r1 I
end;( {6 b S- w' c x+ i+ i+ Q
intTemp:=0;
* {% i+ c; L8 A9 u5 Sresult:=temp;. [2 |' { {+ y |# X' I
end;8 x7 Q. u0 n) K2 ?% V5 s
function TTSPController.CostBetween(C1, C2: Integer): TFloat; //matrix cij
( x: i+ V1 e/ i( r& Q2 Kvar
5 k' O* t a0 ?& N9 ydistance:TFloat;
! M& @1 I; L T7 @0 Ibegin
7 L+ i2 t: F6 l; ~distance := Sqrt(sqr(Cities[C1].X - Cities[C2].X)+ sqr(Cities[C1].Y - Cities[C2].Y));1 a: j( y8 o6 B9 z$ k2 i
//result:=distance+TimeCostBetween(C1,C2); a. K! c. u1 \! e0 E
result:=distance;* c5 Y% ?$ Q- ]3 X
end;* g i; w& _& _4 J
function TTSPController.TimeCostBetween(C1, C2: Integer): TFloat;& o& a& P. b' H7 @* I1 Z5 l
var7 f! L$ Z% t# i
cost:TFloat;
9 x- W, c1 @* V5 I! Mi,j,penaltyW,penaltyD:TFloat;! }" B$ @. `% P1 C' U2 T
startTime:TDateTime;5 H" ?; z, R5 Z" T
begin8 y; w: |- g' J" T+ Q6 ]
startTime:=strToDateTime(FormGa.EditStartTime.Text);
5 `' |. W7 y. @: PpenaltyW:=FormGaPara.EditWaitConstrain.Value;
5 c" p* m' j* u4 T/ BpenaltyD:=FormGaPara.EditDelayConstrain.Value;4 j! a7 }) m) N* I) W8 R. X
if Cities[C2].id>fOldCityCount then
 p9 y1 r5 |" {6 zfCities[C2].totalTime:=07 m* ~- y0 @7 i/ C( B) J% @
else: k; \! z4 h2 q) s5 U( d" ?
fCities[C2].totalTime:=Cities[C1].totalTime+Cities[C1].serviceTime+timeArray[C1,C2];' e; }0 B* L% o& a; A" I T3 O; Q1 T
fCities[C2].waitTime:= max(0,DateSpanToMin(startTime,Cities[C2].early)-Cities[C2].totalTime);
$ d; B" N ~4 n2 _fCities[C2].delayTime:=max(0,Cities[C2].totalTime-DateSpanToMin(startTime,Cities[C2].late));
* G. l; O. W+ Gif Cities[C2].late<>0 then //consider time or not
; K7 F& }( G! ebegin% I4 b$ _0 a3 d, l8 e
if Cities[C2].early<>0 then //window or deadline
; i3 F- B0 q& W8 ?cost:=penaltyW*fCities[C2].waitTime +penaltyD*fCities[C2].delayTime
! j4 D+ _2 \& P) J5 ?else- z6 ?1 A6 E- _: Q+ t) ~
cost:=penaltyD*fCities[C2].delayTime;& s8 R0 p$ G3 o- e. p2 j% f7 S
end
) Q: s6 S2 @, A9 P) }0 helse
2 S1 y) T% }0 d0 x- o# zcost:=0;( h' e0 @. x2 f# ?8 H; R8 Z
result:=cost;; {& H/ p& I$ i' ]6 k
end;: t3 F9 d. B3 O6 T
function TTSPController.DateSpanToMin(d1,d2:TDateTime):integer;6 o. }7 G% D7 L1 K+ |8 m9 }
var
7 i& E: a5 y: H! ^4 z% w4 }* hspan:TDateTime;
( C1 r4 F6 |* w8 m- F EYear, Month, Day, Hour, Min, Sec, MSec: Word;
/ |8 \+ q% [+ p Vbegin4 g' p; G! J+ T# f
span:=abs(d2-d1);5 t. J2 U2 Z& H
DecodeDate(span, Year, Month, Day);8 Z- A% i$ e( j4 j8 [8 I
DecodeTime(span, Hour, Min, Sec, MSec);) r+ s0 M1 T4 |( s* X
result:=Min;
, @ c4 l; m9 z% H1 lend;
: @, N+ O$ Z" m( k% t//return the position in the vehicles array* c: l# m8 ~7 @1 A
function TTSPController.GetVehicleInfo( routeInt:Tint):integer;# K7 U0 d. L0 u0 T5 B% V4 F
begin$ o5 L5 x$ J, L2 Q: E, ^, e
result:=routeInt-fOldCityCount-1;
. o- m6 x& }+ aend;
. i. @! U" k+ P, Gfunction TTSPController.GetWeightConstraint( Individual: IIndividual): TInt;
7 A) j9 S% H; h+ C3 R. X7 s$ d* avar
! i1 C/ K+ z/ B+ X% H: WIndi: ITSPIndividual;0 I$ d$ i# n* Q; ^
totalCapacity,maxCapacity: TFloat;0 g- `. V9 F" z" W( c! x; Q
i,j:TInt;
9 r) b2 J: v/ Y5 l+ Z4 e( Z( otempArray:array of TInt; v+ f' E+ p$ N
tempResult:TInt;2 ~0 `1 d3 s' R/ H" @( h
begin Z9 L# [. a) V6 C" |2 K
Indi := Individual as ITSPIndividual;
+ S) C% E5 ]% r4 m O2 p0 bSetLength(tempArray, fCityCount+1);
9 I1 Y8 w* J+ wtempResult:=0;
; g: m+ S: N- s/////////////////////////////////////////////////////////
0 H0 B5 y+ P" b) c5 J8 r' x6 }for i:=0 to fCityCount-1 do& @5 w, L1 F2 l9 z$ [
begin
; k, M/ y4 k( G5 t" `) v- Q! {if Indi.RouteArray=fOldCityCount+1 then3 G0 N8 ^ x6 P" y7 `7 o: r. M' a
break;8 U& Q( _' e6 d( S
end;; y+ z3 H" l- U4 j% f% I) V
for j:=0 to fCityCount-i-1 do O- G# t2 ]" y
begin+ C$ r z/ @9 y8 n' c# i% O' F4 }
tempArray[j]:= Indi.RouteArray[i+j];6 m* H9 B$ q3 [" y/ J' J" L
end;
) U% c2 H$ Y( X/ h7 x' h5 W& q, U! mfor j:=fCityCount-i to fCityCount-1 do
3 Z/ l$ T. S$ D. Y$ E# |1 Qbegin3 E. R# H9 ~/ V! P( C- Q$ t, R1 X
tempArray[j]:= Indi.RouteArray[j-fCityCount+i];
0 ]2 @! C, O! ^0 N/ gend;# ^# z p- N$ N4 a/ L! _
tempArray[fCityCount]:= tempArray[0];3 Y- ]- B) i6 _ n9 g b9 R
//////////////////////////////////////////////////////////
" |/ P% R* f+ w3 U+ @//totalCapacity:=fCities[tempArray[0]].supply; //supply" k8 |. j: N, O
maxCapacity:=fVehicles[GetVehicleInfo(tempArray[0])].volume;
5 O; t8 b& t" N3 P: ]totalCapacity:=maxCapacity;+ e I/ A+ p+ x- K6 f- w
for i:=0 to fCityCount do
; Q2 O# P" F+ D$ b- Tbegin
: z6 K! A8 e& q4 M! D! [; \) f8 kif (FCities[tempArray].id<=fOldCityCount)and(FCities[tempArray].id>0) then) o6 N4 x4 g q5 K' ]
begin5 O$ b. {1 R% {% p, `0 S, N- R
totalCapacity:=totalCapacity+FCities[tempArray].supply-FCities[tempArray].demand;
, I0 W7 p! r2 f% C7 lif (totalCapacity>maxCapacity)or(totalCapacity<0) then
. ?% R0 z0 g( H( d) n5 zbegin
/ u% F: o1 V7 g7 [' `+ {tempResult:=tempResult+1;
$ T! m' g3 {' M//break;
: N: Z0 h4 T" b( k" C5 Eend;4 x. d0 j1 O2 q9 G6 Q5 A8 C' x
end;
7 O4 s6 i6 R, Q4 ?; p9 [& ~if FCities[tempArray].id>fOldCityCount then0 X) t0 D! D, v2 V
begin; T6 F" y; x+ J) a ]( h
//totalCapacity:=fCities[tempArray].supply; //supply
& ?1 [& z6 r, PmaxCapacity:=fVehicles[GetVehicleInfo(tempArray)].volume;
( _ L! T, _: B) Q0 Q4 L G: utotalCapacity:=maxCapacity; ( h* u+ \* }" G3 o/ ~
end;6 W# D3 W" n- W* O& Q: o! y4 i
end;
6 Q4 \* P g) c" x* rSetLength(tempArray,0);
9 |$ a! J! w; `0 t. p$ M; v3 Gresult:=tempResult;
- v( T7 H& }, F8 M- U. l( mend;% c. M- r' s, m1 g, d6 X4 R) e
function TTSPController.GetBackConstraint( Individual: IIndividual): TInt;
9 s3 f' }7 M' |+ ?var
% o u* S. b" G3 HIndi: ITSPIndividual;: |- k7 I$ F2 a
i,j:TInt;
 J' }; L6 h& z \1 AtempArray:array of TInt;
4 c, |" z% @/ g: M3 GtempResult:TInt;
8 C* M. u4 B( L* i' ~9 Vbegin" G3 r& B: T9 P( w+ e9 _3 F
Indi := Individual as ITSPIndividual;
, C' p# g, E& d* X" e4 n6 T, pSetLength(tempArray, fCityCount+1);9 m0 x+ _5 \* [# V1 ^; H U
tempResult:=0;
+ v# Z0 d6 j: d! R rfor i:=0 to fCityCount-1 do9 V; q6 A6 T9 l$ E! K
begin
. {' q0 B6 [% w( V P2 ]/ D& zif Indi.RouteArray=fOldCityCount+1 then: L. p$ C* m3 o7 B9 n$ S
break;4 X3 H* _, r7 ?! A& X4 y X
end;
0 [& r! t# y! L& Ffor j:=0 to fCityCount-i-1 do
( j3 z. K D' h% l& |begin4 \& j x$ ?3 ~: }. X
tempArray[j]:= Indi.RouteArray[i+j];
4 R+ v+ b* w9 e7 ?0 @& Z( n9 qend;
! ]4 k+ h4 U* d6 U" X' D( {for j:=fCityCount-i to fCityCount-1 do) u5 S3 p, A: \1 d7 [
begin& i' S. C ]5 Z, q: s
tempArray[j]:= Indi.RouteArray[j-fCityCount+i];
0 J4 t+ \* x3 Y- e5 h; x1 iend;2 y; A: P+ l. c `. ~
tempArray[fCityCount]:=tempArray[0];
& H7 e- [4 c3 }2 p: w1 Y2 a{tempArray[0]:=11;tempArray[1]:=5;tempArray[2]:=8;tempArray[3]:=7;
7 ^7 M# C6 q. s+ P- h ]tempArray[4]:=9;tempArray[5]:=6;tempArray[6]:=12;tempArray[7]:=10;, h- t# N( q. _/ L* W% j+ P( @$ a$ S
tempArray[8]:=2;tempArray[9]:=4;tempArray[10]:=3;tempArray[11]:=1;
# [& ]9 ]! x \3 l: wtempArray[12]:=0;tempArray[13]:=11;tempArray[14]:=3;tempArray[15]:=1;9 _$ g6 f, [$ p8 C% q2 E
tempArray[16]:=4;tempArray[17]:=11;//10,2,2}
3 g. Q$ }# {: ifor i:=0 to fCityCount-1 do. M8 g4 P/ J7 a2 \2 ~
begin
! r# ]! @! [, y# ?: Wif (Cities[tempArray[i+1]].id<=fOldCityCount) then6 R' X0 z. C& K9 y, m9 m/ P
begin) U% R. U. k; O- ~4 G
fCities[tempArray[i+1]].serviceDepot:= fCities[tempArray].serviceDepot;
9 i! F9 L% W( @; Y" T/ c' _" Zend;
! m$ Z I/ Z" Bif (Cities[tempArray].id<=fOldCityCount)and(Cities[tempArray].id>=1)and(Cities[tempArray[i+1]].id > fOldCityCount) then- D" g: ^# Z6 [ \4 [
begin$ G7 {7 U& W. u( q! z
if Cities[tempArray].serviceDepot<>Cities[tempArray[i+1]].serviceDepot then //back to the start point
. ?0 }9 ~$ J; N0 M. a, {begin% N. u# l6 j$ ?' P
tempResult:=tempResult+1;: k; S. u& ~- C6 O2 v- i& R
// break;
+ b5 y; F( ^8 Z4 U, Wend;1 z# m' ~/ ]9 g7 n* i B$ C) p8 b
end;7 [) a# F/ m1 I- u4 n: F3 P
end;
% x6 g6 y% t, N# oSetLength(tempArray,0);
- B- u# Q: Y1 J& H, R/ A0 W6 }result:=tempResult;
" F" w3 |5 E6 x: Wend; 
6 u6 c8 t/ O- |8 q9 A# M$ Pfunction TTSPController.GetTimeConstraint( Individual: IIndividual): TInt;4 H# Z0 F4 h/ D" b
var
; r4 F$ f* b& T) u2 i$ ?Indi: ITSPIndividual;
9 `: h9 t2 M1 w- _- e& P0 @' ai,j:TInt;
) \2 t7 Q4 z2 U% ^ ktotalTimeCost:TFloat;4 I/ B7 p3 E' v* e% E6 `
tempArray:array of TInt;
7 Z9 b% v7 b8 Z7 JtempResult:TInt;: o0 `6 n1 F: k) ^% r
begin, ^) W: u( ^0 Z+ L+ Q0 E0 W% w
Indi := Individual as ITSPIndividual;
$ R* p5 e' N0 tSetLength(tempArray, fCityCount+1);
1 @0 s+ w- g/ xtempResult:=0;. {" y1 ]3 F+ ^% `, u$ w
for i:=0 to fCityCount-1 do
 y$ C9 [7 H1 G! Nbegin' Y9 _: z( N6 \# J3 ~" d
if Indi.RouteArray=fOldCityCount+1 then' C( W' |$ `+ F, f" b" A
break;
8 ?0 M' H* i* r, }3 Wend;
" q# d' ?, y% v, p# Tfor j:=0 to fCityCount-i-1 do
 T$ @1 F4 K2 s2 F P% @ nbegin
" i: H# z: f. V6 @) Z w1 j% QtempArray[j]:= Indi.RouteArray[i+j];) L9 p, Z0 f" R. s* b6 F
end;
3 e! ~4 s7 ^8 [for j:=fCityCount-i to fCityCount-1 do
) v/ w1 Q* P9 v# z cbegin) W: z: M1 B% Z) H9 ]- \' P- w0 d
tempArray[j]:= Indi.RouteArray[j-fCityCount+i];
& P8 q! ~4 q) G/ F) Tend;
# U+ Z0 j @0 E; q8 [' FtempArray[fCityCount]:=tempArray[0];& z, b$ r- j+ k. ]
totalTimeCost:=0;
, l6 {2 c" P* b0 ]5 _for i:=0 to fCityCount-1 do0 J% T& E9 _- D7 J7 ^
begin
1 W8 K: ^+ H! r# l' _: etotalTimeCost:=totalTimeCost+timeCostBetween(tempArray,tempArray[i+1]);
' X6 {! ]6 G' G8 h2 c$ s" s( kend;
0 v/ h6 L+ q. X2 W6 [if totalTimeCost<>0 then tempResult:=1;+ }* r) R# v7 X- g S0 |' f7 a: x
SetLength(tempArray,0);
) [+ w1 R9 v* H6 Z" v& Vend;
0 R$ D {% n; ~0 y. dfunction TTSPController.GetCity(I: Integer): TPoint2D;7 _# L) e1 r; B# S
begin
+ z! B# D' i. X0 vresult := fCities[I];
7 m. Q% ?; l G4 B7 `end;4 a3 I8 F g& s0 l8 X, S f
function TTSPController.GetNoVehicle(I: Integer): TInt;* y9 _# X, m/ H
begin: g- i d% e0 Q
result := fNoVehicles[I];( o/ j% |; z; s4 O4 h" K
end;
& h% y- Y' M; d' c' x; X5 bfunction TTSPController.GetCityCount: Integer;
/ q8 z7 T0 `2 E9 O2 c sbegin& J9 t2 e. i. d' U
result := fCityCount; U* `- z- F) Z$ J4 H; g
end;
: _" I, ?9 _+ A0 Ffunction TTSPController.GetOldCityCount: Integer;! _% [, o; n7 [0 ^ }9 n
begin
% T" N8 X4 [! ?+ s# s4 a) uresult := fOldCityCount;
& H V4 u1 P8 a+ r1 |7 v1 Yend;6 @7 Y4 c) @/ A' F
function TTSPController.GetTravelCount: Integer;
% e, H% Q7 `' Tbegin
result := fTravelCount; D( L! d. k6 T4 f' ?1 {
end;
7 m( m/ @6 B/ B+ g- t# _function TTSPController.GetDepotCount: Integer;6 m% Z- f, T/ f. ^- I
begin
4 v8 }4 P7 u0 Iresult := fDepotCount;
2 z6 D2 e& ?- Y0 ]3 U+ R4 uend;# u5 f) L1 K7 M' S
function TTSPController.GetXmax: TFloat;" }4 w3 z: {3 K3 {0 d; i2 }, d
begin% D) z* r* |* C% g. Q# I9 A: S, q% A
result := fXmax;
' b2 A5 B. h$ a1 h# yend;
% H4 }: F1 I. Lfunction TTSPController.GetXmin: TFloat;
6 M$ x2 i2 C" @5 qbegin
: O' |$ L* K: c' r& ^, @/ _result := fXmin;5 N& R; w- |) T0 I
end;
& z7 j8 Z) W0 Y o8 a6 w2 ^* [8 f* ?function TTSPController.GetYmax: TFloat;( x! U2 x' X! o) Z
begin
 O) w+ B! v& W; d: z0 Uresult := fYmax;
4 w4 |- N. o6 bend;
0 w' F4 ?! s3 y5 Hfunction TTSPController.GetYmin: TFloat;
) t* ^) U4 d2 ?% P3 B9 Ubegin
3 }$ l" X3 x% G1 q% s* |7 Tresult := fYmin;& ?% f: u R r
end;
/ ~ K$ w* F- y! g" z6 y' wprocedure TTSPController.RandomCities; //from database
3 M2 V$ \" p3 G6 Q5 m7 u' b" _$ ?var( O9 S3 m- Y% E2 K/ F D2 A: |
i,j,k,m,intTemp,totalVehicleCount: Integer;
4 J# r8 e: W1 }tempVehicle:TVehicle;
5 u+ U2 w8 l1 r, q: [' [begin$ x& I) w' f$ g2 O
//////////////////////////////////////////////////////////) [* |7 D( Y3 b6 C
fNoVehicles[0]:=0; : i+ r# G: d& w
totalVehicleCount:=0;- b7 U% ]: g) G$ l# |, S& ~ W" z
for i:=1 to fDepotCount do //from depots database
% ]+ \1 Z+ t/ wbegin
6 M5 V6 e6 X4 o0 `/ g: cfNoVehicles:=fTravelCount +1;
2 d8 Q4 \/ t- n8 D$ _) QtotalVehicleCount:=totalVehicleCount+ fNoVehicles; //real and virtual vehicles
8 I# x6 p5 c& J2 yend;
5 M) a( U, O# M% }! }) qSetLength(fVehicles,totalVehicleCount);
1 }/ c! o2 Z& v! U. R% C7 yintTemp:=0;
) a- U$ `$ y, ?. ?for i:=1 to fDepotCount do
, U' B, B: d% }6 H2 o) G* m3 \begin
; J7 r8 H( k+ z$ o' z3 H% qfor j:=intTemp to intTemp+fNoVehicles-2 do, T$ X% _3 D/ O9 K
begin- ?+ e! g, M% R0 u# U0 j' o
fVehicles[j].index:=j+1;/ N9 S9 z* s7 t" o% L5 v" ], P
fVehicles[j].id:='real vehicle';" B) z* i& h7 F1 ?' E: ?$ W
fVehicles[j].volume:=50; @0 @ i/ e! J* b: w9 w
end;, k! _, l* X1 B! B1 l
with fVehicles[intTemp+fNoVehicles-1] do
8 M$ S" B0 G! }( F3 q% tbegin
0 g5 c5 a% c5 _index:=intTemp+fNoVehicles;; X+ g# D: b( j3 r' T7 q% L
id:='virtual vehicle';
' b7 L5 ~& g Ivolume:=0;1 H ^9 v2 `# |# |
end;, d9 m8 m3 c% k
intTemp:=intTemp+ fNoVehicles;
0 n& }& w0 U2 jend;
 r8 t2 b5 \, c///////////////////////////////////////////////////////////
% y- @6 X3 f. A& ]- b# v jintTemp:=0;
; I, r1 A9 u! b% f0 D, o$ t% rfor i:=1 to fDepotCount do //depot 1--value6 ?0 b0 c- [0 d$ w2 q7 i- s8 {
begin5 n3 V7 I+ ]) D, `0 f
intTemp:=intTemp + fNoVehicles;
5 t+ ^4 {5 C1 q' T; Bend;9 D% r# s! R' E% @# Q
for i := 0 to FOldCityCount do //from database" O$ V# C3 J! Y' `6 r) D
begin
& b9 E8 A6 o! V' \- eFCities.id:= i;
6 Q; F& J1 Y6 tFCities.X := Xmin+0.5+(Xmax-Xmin-1.0)*Random;
/ _9 W) @* v: c: l7 DFCities.Y := Ymin+0.5+(Ymax-Ymin-1.0)*Random;
. j Q3 y- }( L1 d6 uFCities.early:=0;
9 b8 L* ~% ], E: v9 JFCities.late:=0; //TDateTime& j0 S, H5 c. C) \
FCities.serviceTime:=0;2 y+ y$ n) e {8 P
FCities.totalTime:=0;( t& Z; G9 ?: m! w. P& g
FCities.waitTime:=0;
3 O6 |5 p( ]4 K& _* qFCities.delayTime:=0;& B0 A/ B1 U0 q9 T' X
end;
, C, {& x5 o( K) n/ Z: e; O% ]for i:=FOldCityCount+1 to FCityCount-1 do7 {* C: x' C- C+ A2 m
begin
5 [9 A$ y$ s* n8 O' l; Y' G9 ~2 BFCities.id:= i;
. h) F) M0 i1 g) Gif fDepotCount=1 then) ?6 O* u. @# F w( [+ R
begin5 x# G0 b+ W7 m
FCities.X := Xmin+0.5+(Xmax-Xmin-1.0)*RandomRange(2,4)/5;5 E7 y* B7 W: m! W
FCities.Y := Ymin+0.5+(Ymax-Ymin-1.0)*RandomRange(2,4)/5;/ [# Y9 b2 s7 m4 K2 N0 M
end) D( E3 h& F: Z/ J9 f, {
else
! n- l+ [0 Z K7 ^ i2 E) O% Ibegin
7 b, J: H; [ e- [/ u( _8 GFCities.X := Xmin+0.5+(Xmax-Xmin-1.0)*Random;7 }1 ^2 c% M7 A
FCities.Y := Ymin+0.5+(Ymax-Ymin-1.0)*Random;0 u6 i) B) A& }. v3 S1 Y+ T) P
end;) i% p) j2 k$ {: |. j) d
FCities.early:=0;
( Y6 Y2 H% \2 V( LFCities.late:=0; //TDateTime
! s {* t; }" J" q h: `# M) \FCities.serviceTime:=0;: K+ x. @ ~" b
FCities.totalTime:=0;
) h4 e5 J4 a6 I9 {6 F4 h2 HFCities.waitTime:=0;
7 W J0 ^4 Q( }% y: ^" z1 N* C& IFCities.delayTime:=0;
, y: b1 {+ l# r1 lend;
for i := 0 to FOldCityCount do; a# D2 R# v5 B- e/ s5 p
begin
; o. W4 H) ]* W& EFCities.serviceDepot:=i;
& l; Z8 M9 T- Q t: h+ fend;
6 k( d2 @( ^9 t, z! ]8 f9 Tm:=FOldCityCount+1;
5 ?, y4 U5 }9 m1 g7 Y$ kfor k:=1 to fDepotCount do7 M2 ?6 X% q: X* V0 m) g
begin! d, w( Y8 i3 l2 k B
for j:=0 to fNoVehicles[k]-1 do
5 P: H/ J# r/ R$ |1 P3 Ebegin
$ ?" z# H, P; D! G pFCities[m].serviceDepot:= fOldCityCount+k;
. s, W# x5 ?& Em:=m+1;+ Y1 t3 Y7 f8 v& S# C$ L* p8 E
end;
$ A8 Q* i# I, P4 N+ oend;
4 T' m3 @* h& H$ \3 q' i//supply and demand //////////////////////////from database
. g! |4 H" A" mFCities[0].demand:=0;
8 Z8 u5 ~- E# @% d- z0 F0 w. [FCities[0].supply:=0;
: T3 K7 K( K7 w& A7 ]) k6 _for i:=1 to FOldCityCount do, N4 ~% W9 F( B) M1 r% M) q
begin( R0 s# p8 V4 e; i' a3 T/ j2 M0 ~
FCities.demand:=10;
$ o9 x, A7 x. n8 kFCities.supply:=0;
( N; L' X/ F8 Gend;
; r7 ^% |) ~2 L8 cfor i:=FOldCityCount+1 to FCityCount-1 do
begin
9 f0 _2 m( M; r4 M1 pFCities.demand:=0;/ I6 Z) a/ d+ F2 t
FCities.supply:=50;
0 k* ?- p3 ^. q j8 T+ Iend;
- l2 g6 I; T; l////////////////////////////////////////////////////////////
' R9 M% f& L, n" KintTemp:=0;& \: I5 L4 ?1 B9 |
for i:=0 to fDepotCount-1 do) R; }/ Y1 J6 x5 C: M, U$ x
begin
! d, d5 S6 O8 [8 T2 bintTemp:=intTemp+fNoVehicles;
# Z, S5 }, O! ] tfor j:=2 to fNoVehicles[i+1] do& n" A4 |$ b1 ^) f; C
begin
' ^, N, E; p) v; f+ D" Z7 k5 X9 nFCities[fOldCityCount + intTemp +j].X :=FCities[fOldCityCount + intTemp +1].X;+ l) n4 {0 A) F
FCities[fOldCityCount + intTemp +j].Y :=FCities[fOldCityCount + intTemp +1].Y;7 S, y! {: @; A# A2 m) y9 L
end; Q1 `" e6 v1 z4 @4 _4 e- ?
end;2 z0 U# [: }+ }. F/ N- Z6 J" ]
writeTimeArray;
0 I! Q* V$ J2 N$ j' lwriteCostArray; ; _1 W. A& h8 u! L0 _( ^8 q9 z
end;
5 h5 K2 y2 b6 L- c8 }1 Kprocedure TTSPController.writeTimeArray; //database* u/ j6 M; r; Q T: U* C r, D
var
" I7 W0 Z! m, @: k8 Q0 L8 d- {i,j:integer;
- B& P3 [ z- M# |- _, ^4 I+ sbegin
1 g5 I* b( ~6 \4 h7 Y. cSetLength(timeArray,fCityCount,fCityCount);
6 s1 n& D; Z9 Ffor i:=0 to fCityCount-1 do
7 b) J" S0 J+ Q0 ?5 _4 @! Ybegin
/ o/ i G6 b$ P+ {; F8 Jfor j:=0 to fCityCount-1 do
; D! D `0 `7 Ibegin
7 }4 s! m; l' V4 V0 Qif i=j then timeArray[i,j]:=0
% W! x3 ]" W' W; nelse timeArray[i,j]:=10;
2 R3 t7 v5 p$ y, J$ b- Cend;
" e! ~/ K5 N7 A6 e7 X- U; U. Qend;
/ Y/ |& n- |" P$ R8 h. L6 R* }end;
1 `% z* i; o# T z$ Jprocedure TTSPController.writeCostArray; //database& w% M# I/ }/ |1 x9 s5 t7 r/ ?
var' I2 V& X4 O X) l& [
i,j:integer;
8 v& o2 A- J: z) G6 Bbegin, X/ U; L+ B- Y
SetLength(costArray,fCityCount,fCityCount);
5 \5 ?1 k% V! u$ Z. i( I2 I, M, nfor i:=0 to fCityCount-1 do! V# r7 b5 d" M1 D3 G! _
begin
- A* t: z0 }* xfor j:=0 to fCityCount-1 do) y# h* X3 ~& y$ Z
begin. w+ E2 [1 h( R5 c/ k. W1 _. C+ [/ n9 Y
if i=j then costArray[i,j]:=0- S; T. r* _) I9 L
else costArray[i,j]:=costBetween(i,j);% A" @- p$ R c e- k5 v1 L9 ]
end;
2 {, P# K6 k* j1 N/ Lend;& @% C" m' \$ y# Y0 c9 W
end;
& j+ F; ?$ [# k3 G8 s6 E6 X+ Mprocedure TTSPController.SetCityCount(const Value: Integer);8 K! y1 z+ Z- o0 {. G* a! q! U- k
begin
; b$ K8 i. _* H2 Z! t6 X" ISetLength(fCities, Value);
) w( N }: b" p3 y+ D! ~2 ?$ r7 HfCityCount := Value;
0 f% ^5 |% s' F+ JRandomCities;
) U* K+ U% `* p9 `! ~) yend;- [: g, t5 h( ~- T8 \. K
procedure TTSPController.SetOldCityCount(const Value: Integer);# [5 O( J' t$ c3 l& u
begin
 u1 O% g' R" Z! u) H; o( ?fOldCityCount := Value;% T( x" j4 K4 I# K3 u4 S' r$ N5 T1 y
end;, N+ z, K; S! \7 P- s+ e
procedure TTSPController.SetTravelCount(const Value: Integer); ///////////8 g1 C$ f5 H& z( f
begin4 p: S* _: X; q P- @& [
fTravelCount := Value;
6 G& ]; R' |) C* d% Oend;% A5 Z w( Q9 G+ P" G( @
procedure TTSPController.SetDepotCount(const Value: Integer); ///////////( g9 }* N3 o" d5 B+ [
begin5 E0 Z4 v. S; r5 V. ]/ d0 q
SetLength(fNoVehicles, Value+1); ///////////////+ [" M7 _) w6 o/ E: \' @) Q% c
fDepotCount := Value;
) l9 b. K; u' b% W9 n6 s" cend;- k% d+ O0 Y$ e/ }4 |$ \
procedure TTSPController.SetXmax(const Value: TFloat);
8 ^, |; V% t4 B- ]6 S# Hbegin
4 O2 C2 S8 g$ u4 g$ efXmax := Value;
2 N" k% w: b3 E6 |2 Nend;
 F9 t4 |( m7 `2 M: Aprocedure TTSPController.SetXmin(const Value: TFloat);/ z/ g! F% |7 |
begin) v- {8 C$ B7 h- ?
fXmin := Value;3 u* B& [4 y1 [0 q+ n
end;0 }7 X0 g5 C$ I# d% f3 k D8 [
procedure TTSPController.SetYmax(const Value: TFloat);& p9 H- A. M1 `- O
begin
6 v) c1 g: f* w2 pfYmax := Value;2 q1 Z4 {# [+ B
end;
: ?1 B% Z& X7 q9 Iprocedure TTSPController.SetYmin(const Value: TFloat);
! r/ B: Z; d) gbegin# g- R, T: ~, S
fYmin := Value;" M2 z C" b' O: H2 { Z; H# `
end;
; [9 T ^" Y* I6 ?9 Z* x. _/ n/ iend.
/ g3 @# K4 V& ^; b/ A% s i</DIV>
& G+ [9 c: B6 \- s' |8 r
[此贴子已经被作者于2005-4-27 15:51:02编辑过]

我也说一句

发表

使用道具举报

ilikenba

1万主题	49 听众	2万积分

TA的每日心情

	奋斗 2024-6-23 05:14

签到天数: 1043 天

[LV.10]以坛为家III

群组: 万里江山

群组: sas讨论小组

群组: 长盛证券理财有限公司

群组: C 语言讨论组

群组: Matlab讨论组

3^#

发表于 2005-4-27 15:48 |只看该作者 |招呼Ta 关注Ta

进化算法

<

>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++模板和工具中。进化算法可以各种各样--遗传算法、遗传编程、进化计算等等，但是它们的核心都共享一些特点：种群通过几代来繁殖和成熟，基于某种适当性量度来产生未来的代。
<

>这是进化算法解决TSP问题的源代码：

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

45.23 KB, 下载次数: 72, 下载积分: 体力 -2 点

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

我也说一句

发表

使用道具举报

ilikenba

1万主题	49 听众	2万积分

TA的每日心情

	奋斗 2024-6-23 05:14

签到天数: 1043 天

[LV.10]以坛为家III

群组: 万里江山

群组: sas讨论小组

群组: 长盛证券理财有限公司

群组: C 语言讨论组

群组: Matlab讨论组

4^#

发表于 2005-4-27 16:05 |只看该作者 |招呼Ta 关注Ta

蚂蚁算法

<

>该算法是由意大利学者M.Dorigo、V.Maniez-zo、A.Colorini等人首先提出的,称之为蚁群系统(antcolonysystem), 该模型已成功应用于求旅行商问题(ＴＳＰ),二次指派问题,排序问题等ＮＰ-困难的组合最优化问题,结果可与模拟退火,遗传算法等通用的启发式算法相媲美.蚁群算法和局部搜索算法相结合(称为混合蚁群算法)应用于解二次指派问题和排序问题,得到的结果可以与专用算法相媲美].受其影响,蚁群系统模型逐渐引起了其它研究者的注意,D.Costa和A.Hertz.
<

>在M.Dorigo等人研究成果的基础上,提出了一种求解分配类型问题(assignmenttypeproblem)的一般模型,并用来研究图着色问题.G.Bilchev、I.C.Parmee研究了求解连续空间优化问题的蚁群系统模型.。
<

>蚁群算法是模仿蚂蚁工作方式的一种新的启发式算法.生物学研究表明一群互相协作的蚂蚁能够找到食物源和巢之间的最短路径,而单只蚂蚁则不能.蚂蚁间相互协作的方法是它们在所经过的路上留下一定数量的信息素(迹),该迹能被其它蚂蚁检测出来,一条路上的迹越多,其它蚂蚁将以越高的概率跟随此路径,从而该路径上的迹会被加强.
<

>蚂蚁算法伪码
Begin
初始化:
t← 0
iteration← 0 (iteration为迭代步数)
将 m个蚂蚁随机置于 n个顶点上 ;
Loop:
将所有蚂蚁的初始出发点置于当前解集中 ;
for i← 0 to n-1 do
for k← 1 to m do
按概率选择顶点 j;
移动蚂蚁 k至顶点 j;
将顶点j置于蚂蚁k的当前解集
<

>end for
t←t＋1
end for
计算各蚂蚁的 L个目标函数值
更新当前的理想解
计算各个解的满意度 
<

>置 t← t+1
重置所有 ← 0
iteration← iteration+1
若 iteration<预定的迭代次数
则 goto Loop
输出目前的最满意解
End
<

>下面是蚂蚁算法解决TSP问题的C++程序：
<DIV class=HtmlCode>
<

>/* >->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->
AntColonySystemTSP.cc, Heiko Stamer 
<

>Ant Colony System (ACS) for the Traveling Salesman Problem (TSP) 
<

>[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 
<

>[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 
<

><a href="http://stinfwww.informatik.uni-leipzig.de/~mai97ixb" target="_blank" >http://stinfwww.informatik.uni-leipzig.de/~mai97ixb</A>
>->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->-> 
<

>Copyright (C) 2001 - until_the_end_of_the_ants 
<

>This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version. 
<

>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. 
<

>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. */ 
<

>#include
#include
#include
#include
#include
#include 
<

>#define N 70 
<

>double C[N][2] = { {64 , 96} , {80 , 39} , {69 , 23} , {72 , 42} , {48 , 67} , {58 ,
43} , {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} ,
{62 , 1} , {28 , 43} , {76 , 73} , {67 , 88} , {93 , 54} , {6 , 8} , {87 , 18} ,
{30 , 9} , {77 , 13} , {78 , 94} , {55 , 3} , {82 , 88} , {73 , 28} , {20 , 55}
, {27 , 43} , {95 , 86} , {67 , 99} , {48 , 83} , {75 , 81} , {8 , 19} , {20 ,
18} , {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}
, {17 , 22} , {5 , 45} , {79 , 70} , {9 , 100} , {17 , 82} , {74 , 67} , {10 ,
68} , {48 , 19} , {83 , 86} , {84 , 94} }; 
<

>typedef int Tour[N][2];
typedef double doubleMatrix[N][N]; 
<

>doubleMatrix D; 
<

>double dist(int i, int j)
{
return sqrt(pow((C[0]-C[j][0]), 2.0) + pow((C[1]-C[j][1]), 2.0)); * r# g2 x& C7 S3 M- o
} ) B( J3 g; z! k E, d2 Y
<>void calc_dist() 0 u, s. q; P3 w) k
{
; `4 K/ _/ a1 [( @for (int i = 0; i < N; i++) * u7 |9 c) U6 }4 o/ v7 z
for (int j = 0; j < N; j++) - r, F4 k3 ^* n: z5 x
D[j] = dist(i, j); # ^- d x3 ^6 K( s
} 0 u1 n; Q3 _/ Z, e/ a
<>double max_dist()
$ W ~ p( V f6 {! b8 E5 D3 p, D{ " X* `) y% y$ L* i; Q( D1 y+ R
double max_dist = 0.0;
) Z' V/ L5 N# U* kfor (int i = 0; i < N; i++)
 n6 ^- n& o' u/ A6 [' Nfor (int j = 0; j < N; j++)
8 r/ w4 I; C) G( v4 Nif (dist(i, j) > max_dist)
( J4 }! n" D. k$ Y; @max_dist = dist(i, j);
2 Y+ K7 b p) `5 s$ treturn max_dist; 4 g B3 i9 `6 D7 t$ m6 g
} + U, p$ H# u, K5 L
<>double calc_length(Tour tour)
# n \9 i9 ~0 s* I! N: l% d{ ) m9 y& T7 ~6 _/ _6 N. O
double l = 0.0;
+ Y' \) r7 A% qfor (int n = 0; n < N; n++)
8 h0 a. `0 n* ^+ `4 @& \* a{ ' e4 i4 ~3 t1 d9 Y
int i = tour[n][0]; ! \+ ^: D) r* f7 t* t2 c
int j = tour[n][1]; ; P9 X- \0 g4 B5 o; ~7 p
l += D[j]; % Z+ H7 w- Z' h' B
}
+ j, f/ |% G! J9 R1 b; Qreturn (l);
% Q2 t8 L/ Z) I} 8 b8 A, g& ~$ Q$ a5 {9 u; h' h' e
<>void print_tour(Tour tour)
2 {) K1 }% g" \3 X{
2 q; C$ \1 D0 d5 q. O% C* g% ?2 Gfor (int n = 0; n < N; n++)
4 T- B/ _2 k) m5 U0 Aprintf("( %d , %d ) ", tour[n][0], tour[n][1]);
; o2 w+ Y! m) O; A! \printf("\n");
/ n" L- b+ D! X$ |; ^: }} ! i. h+ f# a5 S: o2 b
<>int sum_sequence(int array[], int count)
- J# V# j; N2 N8 c8 Q" o" k{ * L3 R Z" u7 M% f' l: k& L3 J
int sum = 0;
" S Z. i1 ~) zfor (int i = 0; i < count; i++)
7 @) y( r% O7 |2 Q# Psum += array;
& c4 H( x1 j* [return (sum); ; c" j" S: }3 [& ~% }
} - `7 q3 `- @' d3 a" Y: a! m
<>/******************************************************************************/ $ Y/ z0 x1 L9 B/ u8 \
<>class Ant
+ X0 P, r% r( b: @" z8 `{
6 r) l" P/ Z. \9 X) q1 Lprotected: ' U6 ^& B- h5 D/ A* T# }
int START_CITY, CURRENT_CITY;
: y4 j9 x" h% W: C" p# Mint ALLOWED[N];
- j8 V$ x% k6 x) k2 {Tour CURRENT_TOUR;
0 v0 y; R& F9 C6 t+ S: t/ y1 nint CURRENT_TOUR_INDEX; " |6 v; `; c/ Z3 W8 m7 V3 q' O# @
public:
4 U5 ?; f. i$ w% l6 {9 D7 Qinline Ant(int start_city)
4 m* E$ l. c& ^% B# u! k0 L+ s{
- Q8 L$ u! s2 G' w) S* vSTART_CITY = start_city; 5 H% V( b7 i9 A c, @: @. H# o0 p& M
} 6 W7 J: Q+ ]8 Y {. F8 O
inline void moveTo(int to_city)
; l8 o; }8 m6 F{ ! V8 J) K& m( J' s/ G z4 z
ALLOWED[to_city] = 0;
" @% Q3 I% D/ F6 U; kCURRENT_TOUR[CURRENT_TOUR_INDEX][0] = CURRENT_CITY;
" I7 Z0 l* e) Y% h5 o4 ?CURRENT_TOUR[CURRENT_TOUR_INDEX][1] = to_city; 0 Q" p& c# V$ x2 d, f6 w
CURRENT_TOUR_INDEX++; 4 z) H6 z& w; z( x: w$ M! l4 d
CURRENT_CITY = to_city; ! F4 Y5 a$ k( k# K( M
} 3 a/ x, U' r. |, j' C
}; 3 E2 y( m, g$ i
<>class NNAnt : Ant
9 w0 r$ f. Y/ t# o* q, v{ # k0 P, Z! m# f+ i$ e9 ~
public:
9 F, }# l% Z: {. s9 c8 binline NNAnt(int start_city): Ant(start_city) { }; : b+ u8 ~& x0 b6 ~. B9 [; k' F
inline int choose() 4 E: w7 b2 X: R% P
{
# D: h: |) g- Ydouble best_length = (double)N * max_dist(); + k9 N2 B& ~0 ?2 b& ~! |7 @$ ~6 w
int best_choose = -1; ' F+ J6 m4 U+ y5 _: |( T+ o! x0 @
for (int j = 0; j < N; j++) 1 H' P9 P( ~& u4 C* }) i( u
{ ) H- D" c7 f8 h5 D7 \( H' o: [
if ((ALLOWED[j] == 1) && (D[CURRENT_CITY][j] < best_length))
 B# j& p+ M; G( |{ % c* c( }9 S0 A! t7 V2 b6 C
best_choose = j; + }1 r1 ^. t) P; w6 l7 ?% ^: s
best_length = D[CURRENT_CITY][j]; * O$ q5 `4 Y; W% d! S* L) j
}
6 G5 V/ T2 b" c) C}
! W" H; T$ Q4 b, O1 f u* zreturn best_choose;
# o# m3 U$ B' d5 ?}
+ E0 k2 e6 H# q3 g6 p" iinline Tour *search()
8 {2 x [1 }8 B1 f{ & Z+ A6 H% k C: T6 J6 c& k
CURRENT_CITY = START_CITY; 4 Q1 T4 ~5 _2 J+ M
CURRENT_TOUR_INDEX = 0;
7 h m: n/ y& w. P- v' z3 \for (int i = 0; i < N; i++) 6 a3 A/ }& d( x, ~+ n
ALLOWED = 1;
 G+ {* h0 E- T& r) LALLOWED[CURRENT_CITY] = 0; + Y8 w- e7 B) q( ^( C q3 v9 n8 I
while (sum_sequence(ALLOWED, N) > 0)
4 a A; `2 Z9 Y2 ? `( ?% V; ^moveTo(choose());
' J. T* J5 b) O: jALLOWED[START_CITY] = 1;
) L5 t2 t" c9 H5 B d* T3 G3 DmoveTo(START_CITY);
% a2 H4 _8 ^9 b' v2 K+ ?# N+ R6 dreturn &CURRENT_TOUR;
8 ?- k7 b- `, z/ S- e- k9 Y} 5 v5 x+ z- v3 e7 A4 T
}; 
5 J/ p* r) h$ ?$ Z. f2 o( s( qclass AntColonySystem;
3 K* W4 w$ G5 s7 ~( Q8 Z( x. |class ACSAnt : Ant
9 e& C, y2 l5 W$ o& o! U8 Z! y{
1 C/ f$ t& z/ j: p( ]! o7 h& dprivate: 2 Q# G& x0 ?2 D, N/ [) P; u
AntColonySystem *ACS; + U" [9 H6 d* [# e8 F1 q+ J
public:
3 d6 _0 p, \: ~. a3 U, |ACSAnt(AntColonySystem *acs, int start_city): Ant(start_city) " E8 s% h3 p/ Z6 c% E/ D# N
{ `( X( l! @+ R% u, }- k4 Y6 M( H' d5 Y+ @
ACS = acs; 1 k( m% o8 X. m# C6 a# d
} , a' [9 T0 O( o( U/ ^2 }5 D
inline int choose();
; H3 I# e }/ k' Yinline Tour *search(); & o# r7 u; y) V7 l
}; v5 L- C* G( N" T+ S T% h8 O @4 h
class AntColonySystem
* v+ |+ @9 \3 n2 e% r: U{ / h7 I5 W. w/ I1 W" W' }' W
private: & P1 `: T$ e T9 o1 S
double ALPHA, BETA, RHO, TAU0;
 I) c* g, K2 S d w% }3 |- q- xdoubleMatrix TAU, dTAU; $ f% {! s4 k# Q, `+ }* S1 x! w. N
static const int M = 420; . S6 q& a% ]5 B) G; s# @ t) ^
ACSAnt *ANTS[M]; 
3 L; k6 _/ \. a) i, D+ {9 Y1 s+ ]public:
6 D+ ]- b5 @& H5 R3 Pdouble Q0; ) ?$ t1 }$ J3 g' h! l7 y) k
AntColonySystem(double alpha, double beta, double rho, double q0);
' R# |. A8 ?$ Einline double calc_tau0(); 3 f6 i! ]* Q9 D2 |
inline void init_tau_by_value(double value);
( J- U0 S* L% B$ yinline void init_tau_by_matrix(doubleMatrix matrix); 2 q' E& z! m ~7 s5 m6 X5 g) A
inline void init_uniform(); 9 `+ M/ L* o( y3 R# |
inline void init_random();
) \& D0 z& K7 v$ E* y- p8 N# sinline void init_randomMOAPC();
2 C. A" h, z0 Finline double ETA(int i, int j);
+ v2 w# ]1 o" a; ]9 dinline double transition(int i, int j);
- [1 w; `, c% [: Qinline double sum_transition(int i, int allowed[]); 0 c! @7 ^; y, z% d& ^
inline void local_update_rule(int i, int j); $ `! p7 `! m% O5 H9 F& I* f
inline void clear_global_update(); ) \: S5 A; S: [
inline void add_global_update(Tour tour, double length);
: d3 ~9 A. ]* P$ ?. o" Kinline void global_update_rule();
2 d6 _7 i* K. x: m# ainline doubleMatrix *get_tau(); 2 j4 G9 j4 r" [% ?
inline Tour *search(int T); ) I3 U" O/ x8 {# X! ^
}; * }! ~2 y# m, u2 t) V
inline int ACSAnt::choose() ; q6 b1 d& c8 |, R
{
: Y. j1 M% J" K: jdouble q = rand() / (double)RAND_MAX; 
" r$ Q- S# e7 d0 a" {if (q <= ACS->Q0) - k9 F6 |9 t' d& W
{
0 [( l: S/ Q, s8 u2 {& d3 Edouble best_value = -1.0; * S0 D& Y% n4 f
int best_choose = -1; 4 L& B( d, E/ X. f4 N8 H
for (int j = 0; j < N; j++) 8 o' c$ K, o( b& G* R
{ 2 @8 P$ k( \* M: ^( y, s3 K& t
if ((ALLOWED[j] == 1) &&
, x& d" S, l# Y$ J/ b( t(ACS->transition(CURRENT_CITY, j) > best_value))
5 y* a" i5 g; ]. |{
2 j5 S- y9 v" ~( v0 abest_choose = j;
; U% J' k% a- q. Mbest_value = ACS->transition(CURRENT_CITY, j);
4 [ P* o! Y2 |7 Z. [" m" F7 q" K- P}
8 `! V6 ^' H. V) d} ) [7 B- y+ Q9 V: h8 g; N5 g% z7 y0 k
return best_choose;
: `# q9 O) l, l2 P} 
# X' i9 U/ g, e6 Jdouble sum = ACS->sum_transition(CURRENT_CITY, ALLOWED);
) R& }5 I. t% s9 X: B+ G2 ]double p = rand() / (double)RAND_MAX; # [: J, B- g0 ?. F, |, R; N
double p_j = 0.0; 
8 P4 u* k1 r+ y" a4 d' _ U3 ]for (int j = 0; j < N; j++) % F! A% @0 ~3 A1 v0 Q( H
{
 d% m( i" x% a! u- hif (ALLOWED[j] == 1) p_j += ACS->transition(CURRENT_CITY, j) / sum; $ o, M9 Q2 I. m7 S2 k G- {) ]/ F
if ((p < p_j) && (ALLOWED[j] == 1)) $ S: S4 }4 _' b
return j; + W- ^) [9 A$ @
} " P. `4 z" A% ^( r: V
return -1; 9 o. l' [! H9 g3 [& }! r4 c' g
} 0 F( F4 L9 ^, [3 B& ]+ q
inline Tour *ACSAnt::search() 1 L; p* p4 m! G) x% p
{ 0 `3 h5 W/ g+ l3 @5 w# X
CURRENT_CITY = START_CITY;
7 N2 C: ^5 a; g. c; S! r" KCURRENT_TOUR_INDEX = 0;
. ]/ m+ {. x# L: d. ~; e' hfor (int i = 0; i < N; i++) 0 `" `! V4 [+ R) b& M( E
ALLOWED = 1; " r" h9 K: @4 I& y
ALLOWED[CURRENT_CITY] = 0; 7 U7 s- F) U" L
while (sum_sequence(ALLOWED, N) > 0)
/ b! U7 {: t4 {8 M6 F; N9 @{
 b/ u& ~1 \; b$ M* R: dint LAST_CITY = CURRENT_CITY;
' U3 L, M$ a; i+ o- pmoveTo(choose()); " r/ l7 A) w5 ~5 \+ D
ACS->local_update_rule(LAST_CITY, CURRENT_CITY); % X0 I9 p6 C' a; x
} , O& B: G. C% {. b! B
ALLOWED[START_CITY] = 1; 0 C: g9 ^' g# t/ j/ L4 G
ACS->local_update_rule(CURRENT_CITY, START_CITY); / o. @$ @5 \( K' v9 F
moveTo(START_CITY); & V- ?) d% C! d+ @6 w4 t8 v
return &CURRENT_TOUR;
, {; R5 S# W2 A/ q& _} 4 \( P7 w9 x# S, z5 O/ n% ?
/******************************************************************************/ & T2 [5 a- a2 |$ F* e; {4 h) B
AntColonySystem::AntColonySystem(double alpha, double beta, double rho, double q0)
, D* _& T g7 P6 I) r& K{
! ^" D1 M1 C8 \$ d# L) ]ALPHA = alpha;
1 X0 K1 S5 W( K; I9 \: PBETA = beta; 6 H% T0 q2 b9 X' M2 c, O
RHO = rho; 1 J4 `% G& n: j9 Q: c9 j& u
Q0 = q0; ( ^( f4 s1 s/ z, s, k6 L, Y
} 
1 e, b1 I" B0 O2 `# [* `$ m) ~+ p1 u, qinline double AntColonySystem::calc_tau0() # l: |0 F4 ~$ ~) h8 D C& J
{ $ Y3 ]- w) x5 \% f
double best_length = (double)N * max_dist(); 
; H1 t& R8 [; c4 Z, S3 Vfor (int n = 0; n < N; n++)
5 N- T l# z9 Y{
9 w, Q2 o. h) ^, N- {NNAnt *nnANT = new NNAnt(n);
2 s, ]) g. ]! |3 c! n* f, v. `Tour tour;
& X2 G9 k' F" e. J( e2 Ctour = *(nnANT->search()); ; I$ j. R/ B8 c! b. ]5 c
double tour_length = calc_length(tour);
4 P$ Z: N; _' d0 e6 a8 A- k2 D: wif (tour_length < best_length)
9 Z7 h+ G3 x5 ^* Tbest_length = tour_length; ) n; |/ @* Y( H+ R& v6 ?4 N/ h j
delete nnANT; " N' [' P: q. Y9 j
} ; J# J g/ J' s$ w/ u# P
return 1.0 / ((double)N * best_length);
* p) l) d- a5 u% u1 \, s4 I} ; U5 \, g9 I, {- y7 _( o
inline void AntColonySystem::init_tau_by_value(double value) - e3 t. L8 `4 f( l- J L
{ . j4 Q2 z+ K! h8 h: c, z+ J
TAU0 = value;
3 T- D# g! o( T( b8 _+ O& Q) xfor (int i = 0; i < N; i++) # I- l% i% n ?6 S2 k
for (int j = 0; j < N; j++)
# b& v, s! F- s- r& I1 @! l) ]TAU[j] = TAU0;
* m M+ c2 h+ w5 V( @} 9 e; w, E A) z- r/ S8 B
inline void AntColonySystem::init_tau_by_matrix(doubleMatrix matrix)
# B8 n; n8 c% h2 o# u{
( L" c# k6 k, k0 |/ f5 hfor (int i = 0; i < N; i++) ! Y& l; x8 Z0 D% @8 E0 S7 ~1 h
for (int j = 0; j < N; j++) 8 H! ~+ o) x# Y2 x+ P
TAU[j] = matrix[j]; ; W$ r% a8 s2 D2 m: C5 n! ]
} 3 ?" L" b, c7 |( b$ t
inline void AntColonySystem::init_uniform() 6 s( j w1 z |6 B* I K
{ & C |0 D% z# g' S+ Y
// uniformly distributed & C- T" m1 r, U' o- q* c- x
for (int k = 0; k < M; k++)
 \* u* C% d, cANTS[k] = new ACSAnt(this, (k % N)); 1 ~" x+ f" X2 \9 f1 _
} 
( i s) G" O( T1 [. H2 C0 r7 Xinline void AntColonySystem::init_random() 4 P/ u5 ^ ]& _ [2 _' W! D
{
* h5 a& d3 R4 b& O8 ` a// randomly distributed
0 E K, F3 s4 x' Efor (int k = 0; k < M; k++)
0 Y" s& Z: X2 |. h; a' }8 f# i0 u4 }ANTS[k] = new ACSAnt(this, (int)((double)N * (rand() / (double)RAND_MAX))); + Q0 D* p- x1 G+ H$ h5 q
} 
/ G' ?/ c# h0 h4 H$ Z" Hinline void AntColonySystem::init_randomMOAPC() ; N2 J& _/ n% s$ [9 x, A
{
; Y1 c7 Y3 W% L# Z4 d2 ?// randomly distributed with MOAPC (most one ant per city) % t/ b& A; r; e. o/ s4 k
bool MOAPCarray[N]; ; w$ @1 {- H% v. Q3 ~9 P
assert(M <= N); 
2 Y# K4 @, Q& Q* `+ zfor (int n = 0; n < N; n++) * z- ?9 d$ l0 ]; f" f! J
MOAPCarray[n] = false; - p* X; B5 F2 c3 _8 @
for (int k = 0; k < M; k++)
% Q& F& M9 Y% v$ r+ D2 D{
* Q0 }( e2 o9 _* d; fint c;
0 d- ^: @& l" Y3 x. odo
) f/ m+ V4 Y. @{
+ Y. v7 o ~# P2 I' Xc = (int)((double)N * (rand() / (double)RAND_MAX)); ; @8 c2 B* u! S$ T3 g
} 0 y; T% N; y" Q
while (MOAPCarray[c]); + I0 \2 w. t1 Z" E7 Q1 Z
MOAPCarray[c] = true;
! g3 l# D- V7 L' O1 K5 M, ZANTS[k] = new ACSAnt(this, c);
$ f" s0 J6 O& o, y; |. L/ T s}
 `; t" U/ b# V; I% {8 c' Q+ m} 2 T- F! \7 Y4 f! X% }+ L7 L/ z4 U
inline double AntColonySystem::ETA(int i, int j) ' R# J; g i' `4 w1 L+ P; Q# `
{
5 Z/ F; x+ T5 X' lreturn ( 1.0 / D[j] );
6 S* n1 e0 |* p& w* I# W} 
- ]' Y. m! Z. g5 pinline double AntColonySystem::transition(int i, int j)
$ {/ L$ S, C1 Y" J% N$ K/ H7 M{
+ W4 k! ^- g! V- v2 m) Gif (i != j)
; y. s, e: p! B# B. yreturn ( TAU[j] * pow( ETA(i, j), BETA ) ); % [ M1 R* K. _/ W8 F" L4 n' V
else
2 S5 @* T/ a sreturn(0.0); : X4 ]6 t, d3 p* f1 u7 \
} 
' g3 Q- [5 ]$ I6 A8 N" binline double AntColonySystem::sum_transition(int i, int allowed[]) 3 p- l' `$ j% L0 v
{ - u5 [+ [8 D& b2 i% q+ A
double sum = 0.0;
) z& {; I: `, }3 Ofor (int j = 0; j < N; j++) * `& e+ l% F" ^$ C, r& y
sum += ((double)allowed[j] * transition(i, j)); " @$ g0 _7 i) {) |" J
return (sum); 8 A5 E6 |' N/ e8 @+ H6 |
} 
" V' b/ } \( Zinline void AntColonySystem::local_update_rule(int i, int j) * O3 v3 m5 |) `+ r/ P6 B+ G
{ , T$ i9 H2 |! T, P0 e! D
TAU[j] = (1.0 - RHO) * TAU[j] + RHO * TAU0;
$ P# ?3 |, ^4 j. K; A5 f8 C. X% Y// symmetric TSP
% c G! _) U7 r' L& q& uTAU[j] = TAU[j];
% q( H; E" X% d} * S% d% u3 q; H2 v2 E: U
inline void AntColonySystem::clear_global_update()
" T! ^4 s1 x" A7 g6 r{
0 p8 s7 r& F( efor (int i = 0; i < N; i++)
; `( U/ G' u4 H5 t+ C9 ofor (int j = 0; j < N; j++)
& D0 e \! H$ \$ {$ h7 idTAU[j] = 0.0;
; S& a: J( z6 x X$ L' u} 
5 H' @6 D0 C9 C4 x* {3 A8 R) F/ d/ }! T- m; |7 E( ]
inline void AntColonySystem::add_global_update(Tour tour, double length) - r$ \' m% K, ]7 q6 s% r
{
( Z7 l/ U4 O* y! Y# Yfor (int n = 0; n < N; n++)
& B2 a. y- |! U, Z/ X) V# Z{
/ k" P) I' S9 q+ Wint i = tour[n][0];
1 o8 [. w/ M' i6 G. ]! I3 Q/ Vint j = tour[n][1];
/ e4 @2 G7 u7 V2 {, L$ ?$ EdTAU[j] += (1.0 / length); 5 T5 M2 U% H6 g7 c
// symmetric TSP
' Z" W2 F% f4 C1 m" x! V! ndTAU[j] += (1.0 / length);
( r9 x' t# _; P8 M} ! X# X* ^" O5 [* c
} 4 q$ j1 V& \( q
inline void AntColonySystem::global_update_rule()
# G# S" q5 K" ^& z{
9 u; q- A# S8 f5 {for (int i = 0; i < N; i++) 7 z5 l# u* L7 W
for (int j = 0; j < N; j++)
 |, a( Q. K$ O0 [TAU[j] = (1.0 - ALPHA) * TAU[j] + ALPHA * dTAU[j];
8 L) e& m% O( V} - d2 a: F$ O6 }! j$ \: e
inline doubleMatrix *AntColonySystem::get_tau() ( r! K( e9 r$ A M0 q3 N( s
{ ; p0 d2 }/ c& a1 o
return &TAU; % C1 _4 X3 V& Z# ^( d1 `1 c
} 
% j7 G* C" ]# \inline Tour *AntColonySystem::search(int T)
+ V& z6 {% \2 Y& R# E{ ; T- F9 n8 G2 v# ?; ~# \0 [
Tour best_tour, tour; % Y) A* |; A4 i$ N# D3 X* ?
double best_length = (double)N * max_dist(), tour_length; , h. i/ C9 N# Q6 ~% L' @
clear_global_update(); 3 E% L3 @+ d y0 O7 m
// do T iterations of ACS algorithm 0 _0 u7 l$ P4 l! {* Q
int t;
( L$ F6 O1 {4 ufor (t = 0; t < T; t++) + S/ A0 G: s% K+ h4 i J% X- k
{
4 D$ X. _. v4 A# w# G7 M( k1 Nfor (int k = 0; k < M; k++) 8 _, y7 Y: `, Y2 e, e+ c
{
1 K( N8 |& _2 p: F( Rtour = *(ANTS[k]->search());
5 S6 p' k/ s+ j' k; ^7 f3 Ztour_length = calc_length(tour); 1 V0 E/ z, O1 k( g
if (tour_length < best_length)
! R, ]# R0 b, O{
% W* N7 c; k F# [$ `best_tour = tour; 7 \$ i& ~+ M' i3 a* ]
best_length = tour_length; ' m; K4 n* ^1 w2 ] G
clear_global_update();
6 @+ O& b/ R! s ~add_global_update(tour, tour_length);
0 Q7 x5 Z% @9 N& {8 z0 D% n//printf("[%d / %d]: %lf \n", t, T, tour_length); 8 N7 b1 N# v$ o
}
/ \( k5 ]" E- E9 X9 P% S} * z9 H3 M/ A$ @' w f& Z+ o
global_update_rule(); 9 s2 D/ l1 E" v# ~8 `0 B- q; }7 l/ l
} - M# k2 s4 v$ V# y% x
//printf("[%d/%d] best tour (length = %f):\n", t, T, best_length);
: u, ^* h N3 B" x: V$ M, S) Q//print_tour(best_tour);
5 S. P0 V8 H" a% C//printf("[%d/%d] iterations done\n", t, T);
) Z8 m9 M, {# |printf("%f\n", best_length);
3 N3 D1 L( ]/ s: W0 Jreturn (&best_tour); - F, m+ I% X/ r- N2 @: p
} @# ], j M- u
int main(int argc, char* argv[]) ( m( m. x# g) X( b
{ # T2 {7 Z7 p) g5 E5 h7 b: \
// PRNG initalisieren . C2 V) ~7 W6 y! ?# F' {
time_t timer; & R7 M( ?8 T* m5 l/ s2 p
time(&timer);
+ O0 l4 b- s4 Upid_t pid = getpid() + getppid();
1 L) \9 I6 D. @4 k8 ~unsigned long seed = (timer * pid); ) m. a* W8 ^* [
if (seed == 0)
2 w# |8 V: X' S$ ?{
. o5 o7 I& ^7 `8 [; V) ptime(&timer); - }. ]! y; x( i6 I( r4 ~5 W) A2 b' g
seed = 7 * timer * pid;
* X v! a5 W- [+ V0 Cif (seed == 0) seed = pid; else seed = seed % 56000; 8 R* I: @- n( V% r3 U* B9 z4 v- i
} else seed = seed % 56000;
5 s% H: b7 A# ]' \ Z8 s% {srand((unsigned int)seed); 
 d9 G/ _* M. w7 S; m9 F' i- [5 H// EUC2D
9 u' S$ _) V# f9 F3 Lcalc_dist(); ) D7 T* b7 d# F7 ] L
// Ant Colony System
2 q6 x) B1 c; l4 u& h7 y6 aAntColonySystem *acs = new AntColonySystem(0.1, 2.0, 0.1, 0.9); , [, F! d0 r3 z
double tau0 = acs->calc_tau0(); ' V9 y* V+ a# G2 R
acs->init_tau_by_value(tau0); 9 {% e' X; l: J5 R$ L# _! K
acs->init_uniform();
# s( `+ f5 k9 C+ b5 ^* A& j! ~acs->search(1000); + W/ D6 g2 J/ Y, @3 X
return(0);
: U: \. H3 k; o" H/ E+ w1 X9 i5 Y8 M. t} </DIV>- x3 k. m" d% V: B( x) p( ?7 z

, q( a( O) `1 x+ y0 s& {蚂蚁算法的一些文献：; s0 d8 @' H4 N) w2 O- ?
 5 D: j9 C0 T+ C! S