第七章 遗传算法应用举例
遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架，它不依赖于问题具体的领域。随着对遗传算法技术的不断研究，人们对遗传算法的实际应用越来越重视，它已经广泛地应用于函数优化、组合优化、自动控制、机器人学、图象处理、人工生命、遗传编码、机器学习等科技领域。遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等多方面的应用取得了成功。本章通过一些例子，介绍如何利用第五章提供的遗传算法通用函数，编写MATLAB 程序，解决实际问题。
7.1 简单一元函数优化实例
利用遗传算法计算下面函数的最大值：
()sin(10) 2.0[1,2]f x x x x π=?+∈-，
选择二进制编码，种群中个体数目为40，每个种群的长度为20，使用代沟为0.9，最大遗传代数为25。
下面为一元函数优化问题的MA TLAB 代码。 figure(1);
fplot ('variable.*sin(10*pi*variable)+2.0',[-1,2]); %画出函数曲线
% 定义遗传算法参数
NIND= 40; % 个体数目(Number of individuals)
MAXGEN = 25; % 最大遗传代数(Maximum number of generations)
PRECI = 20; % 变量的二进制位数(Precision of variables)
GGAP = 0.9; % 代沟(Generation gap)
trace=zeros (2, MAXGEN); % 寻优结果的初始值
FieldD = [20;-1;2;1;0;1;1]; % 区域描述器(Build field descriptor) Chrom = crtbp(NIND, PRECI); % 初始种群
gen = 0; % 代计数器
variable=bs2rv(Chrom,FieldD); % 计算初始种群的十进制转换 ObjV = variable.*sin (10*pi*variable)+2.0; % 计算目标函数值
while gen < MAXGEN,
FitnV = ranking (-ObjV); % 分配适应度值(Assign fitness values) SelCh = select ('sus', Chrom, FitnV , GGAP); % 选择
SelCh = recombin ('xovsp',SelCh,0.7); % 重组
SelCh = mut(SelCh); % 变异
variable=bs2rv(SelCh,FieldD); % 子代个体的十进制转换
ObjVSel =variable.*sin(10*pi*variable)+2.0; % 计算子代的目标函数值
[Chrom ObjV]=reins(Chrom,SelCh,1,1,ObjV ,ObjVSel); % 重插入子代的新种群 gen = gen+1; % 代计数器增加
% 输出最优解及其序号，并在目标函数图象中标出，Y 为最优解，I 为种群的序号
[Y,I]=max(ObjV),hold on;
plot (variable (I),Y , 'bo');
trace (1,gen)=max (ObjV); %遗传算法性能跟踪
trace (2,gen)=sum (ObjV)/length (ObjV);
end
variable=bs2rv (Chrom,FieldD); %最优个体的十进制转换
hold on,grid;
plot (variable',ObjV','b*');
figure (2);
plot (trace (1,:)');
hold on;
plot (trace (2,:)','-.');grid;
legend ('解的变化','种群均值的变化')
使用基于适应度的重插入确保四个最适应的个体总是被连续传播到下一代。这样在每一代中有36（NIND*GGAP ）个新个体产生。
区域描述器FieldD 描述染色体的表示和解释，每个格雷码采用20位二进制，变量区间为
[-1，2]。
程序段Chrom = crtbp (NIND, PRECI)表示一个初始种群Chrom 被函数crtbp 创建，它是由NIND 个均匀分布长度为PRECI 的二进制串矩阵构成。
基于排序的适应度分配计算由程序段FitnV = ranking (-ObjV)实现。
对这个等级评定算法的缺省设置是选择等差为2和使用线性评估，给最适应个体的适应度值为2，最差个体的适应度值为0，这里的评定算法假设目标函数是最小化的，所以ObjV 乘了一个负号，使目标函数为最大化。适应度值结果被向量FitnV 返回。
选择层使用高级函数选择调用低级函数随机遍历抽样例程sus ，SelCh 包含来自原始染色体的GGAP *NIND 个个体，这些个体将使用高级函数recombin 进行重组，recombin 使个体通过SelCh 被选择再生产，并使用单点交叉例程xovsp ，使用交叉概率Px =0.7执行并叉。交叉后产生的子代被同一个矩阵SelCh 返回，实际使用的交叉例程通过支持使用不同函数名字串传递给recombin 而改变。
为了产生一组子代，变异使用变异函数mut 。子代再次由矩阵SelCh 返回，变异概率缺省值PM=0.7/Lind= 0.0017，这里Lind 是假定的个体长度。再次使用bs2rv ，将个体的二进制编码转换为十进制编码，计算子代的目标函数值ObjVSel 。
由于使用了代沟，所以子代的数量比当前种群数量要小，因此需要使用恢复函数reins 。这里Chrom 和 SelCh 是矩阵，包含原始种群和子代结果。这两个事件的第一个被使用单个种群和采用基于适应度的恢复，基于适应度的恢复用SelCh 中的个体代替Chrom 中最不适应的个体。新种群中的个体是由原始种群中的优良个体和子代中新产生的个体组成。原始种群中个体的目标函数值ObjV 随后又作为函数reins 的输入参数，子代中个体的目标函数值由ObjVSel 提供。Reins 返回具有插入子代的新种群Chrom 和该种群中个体的目标函数值ObjV 。
每次迭代后的最优解和解的均值存放在trace 中。这个遗传优化的结果包含在矩阵ObjV 中。决策变量的值为variable (I)。
画出迭代后个体的目标函数值分布图和遗传算法性能跟踪图。
遗传算法的运行结果如下：
（1）图7.1为目标函数()sin(10) 2.0[1,2]f x x x x π=?+∈-，的图象。
图7.1 目标函数图像
（2）图7.2为目标函数的图像和初始随机种群个体分布图。
图7.2 初始种群分布图
（3）经过1次遗传迭代后，寻优结果如图7.3所示。x=1.6357，f(x)=3.4729。
图7.3 一次遗传迭代后的结果
（4）经过10次遗传迭代后，寻优结果如图7.4所示。x= 1.8518，f(x)=3.8489。
图7.4 经过10次遗传迭代后的结果
（5）经过25次遗传迭代后，寻优结果如图7.5所示。x =1.8505，f (x )=3.8503。
图7.5 经过25次遗传迭代后的结果
（6）经过25次迭代后最优解的变化和种群均值的变化见图7.6。
图7.6 经过25次迭代后最优解的变化和种群均值的变化
7.2 多元单峰函数的优化实例
目标函数是De Jong 函数，是一个连续、凸起的单峰函数，它的M 文件objfun1包含在GA 工具箱软件中。
De Jong 函数的表达式为
求解
m i n ()51251
i f x x -≤≤， 这里n 是定义问题维数的一个值。这个例子中选取n =20。
由De Jong 函数的表达式可以看出，De Jong 函数是一个简单的平方和函数，只有一个极小点（0,0,…,0），理论最小值为f (0,0,…,0)=0。
程序的主要变量：个体的数量NIND 为40，最大遗传代数为MAXGEN=300，变量维数为NV AR=20，每个变量使用20位表示，即PRECI = 20，使用代沟GGAP=0.9。
下面为求解De Jong 函数最小值的MATLAB 代码。
% 定义遗传算法参数
NIND = 40; % 个体数目(Number of individuals)
MAXGEN =500; % 最大遗传代数(Maximum number of generations)
21()512512
==-≤≤∑， n
i i i f x x x
NV AR = 20; % 变量的维数
PRECI = 20; % 变量的二进制位数(Precision of variables)
GGAP = 0.9; % 代沟(Generation gap)
trace=zeros (MAXGEN,2);
% 建立区域描述器(Build field descriptor)
FieldD = [rep ([PRECI],[1,NV AR]);rep ([-512;512],[1,NV AR]);rep ([1;0;1;1],[1,NV AR])];
Chrom = crtbp (NIND, NV AR*PRECI); % 创建初始种群
gen = 0; % 代计数器
ObjV = objfun1(bs2rv (Chrom,FieldD)); % 计算初始种群个体的目标函数值
while gen < MAXGEN, % 迭代
FitnV = ranking (ObjV); % 分配适应度值(Assign fitness values)
SelCh = select ('sus', Chrom, FitnV, GGAP); % 选择
SelCh = recombin ('xovsp',SelCh,0.7); % 重组
SelCh = mut (SelCh); % 变异
ObjVSel = objfun1 (bs2rv (SelCh,FieldD)); %计算子代目标函数值
[Chrom ObjV]=reins (Chrom,SelCh,1,1,ObjV,ObjVSel); % 重插入
gen = gen+1; % 代计数器增加
% 输出最优解及其对应的20个自变量的十进制值，Y为最优解，I为种群的序号
trace (gen,1)=min (ObjV); % 遗传算法性能跟踪
trace (gen,2)=sum (ObjV)/length (ObjV);
end
plot (trace (:,1));hold on;
plot (trace (:,2),'-.');grid;
legend ('种群均值的变化','解的变化')
区域描述器的构建采用矩阵复制函数rep建立矩阵FieldD，描述染色体的表示和解释。
一个初始种群被函数crtbp创建，随后产生一个矩阵Chrom，它由NIND个均匀分布长度为NV AR*PRECI的二进制串构成。
使用函数objfun1重新计算目标函数，初始种群中的所有个体的目标函数值由下面程序段计算：
ObjV = objfun1(bs2rv (Chrom, FieldD));
函数bs2rv根据域描述器FieldD转换矩阵Chrom的二进制串为实值，返回一实值表现型的矩阵。这个bs2rv返回值矩阵通过直接作为目标函数objfun1的输入变量，目标函数结果被返回在矩阵ObjV中。
这个例子中基于排序的适应度分配计算由下面程序段实现：
FitnV = ranking (ObjV);
对这个等级评定算法的缺省设置是选择等差2，使用线性评估，给最适应个体的适应度值为2和最差个体的适应度值为0。适应度值结果被向量FitnV返回。
使用高级函数选择调用低级函数随机遍历抽样例程sus，程序段为：
SelCh = select (’sus’, Chrom, FitnV, GGAP);
后面的选择中，SelCh包含来自原始染色体的GGAP *NIND个个体，这些个体将使用高级函数recombin进行重组，程序段为：
SelCh = recombin ('xovsp', SelCh, 0.7);
函数recombin使个体通过SelCh被选择再生产，并使用单点交叉例程函数xovsp，使用交叉概率Px =0.7执行并叉。个体作为矩阵SelCh的输入被排序，以便使奇数位置的个体与它相邻的个体进行交叉，如果SelCh个体的数量是奇数个，则最后一个个体不进行交叉而返回。交叉后产生的子代被同一个矩阵SelCh返回，实际使用的交叉例程通过支持使用不同函数名字串
传递给recombin而改变。
为了产生一组子代，变异现在使用变异函数mut：
SelCh = mut (SelCh);
子代再次由矩阵SelCh返回，函数调用中变异概率没有被指定，这个缺省值PM=0.7/Lind= 0.0017，这里Lind是个体的长度。
子代的目标函数值ObjVSel由程序段计算：
ObjVSel = objfun1 (bs2rv (SelCh, FieldD));
因为使用了代沟，子代的数量比当前种群数量要小，完成使用恢复函数reins：
[Chrom,ObjV]=reins (Chrom, SelCh,1,1,ObjV,ObjVSel);
这里，Chrom 和SelCh是矩阵包含原始种群和子代结果。这两个事件的第一个被使用单个种群和采用基于适应度的恢复，基于适应度的恢复用SelCh中的个体代替Chrom 中最不适应的个体。原始种群目标函数值ObjV随后被要求作为reins的参数，另外新种群的目标函数值不用重新计算整个种群的目标函数而返回，子代的目标值ObjVSel被提供。Reins返回具有插入子代的新种群Chrom和这个种群的目标函数值ObjV。
这个遗传优化的结果包含在矩阵ObjV中，决策变量的值可能被包含在下面程序段中：Phen = bs2rv (Chrom, FieldD);
遗传算法的运行结果如下：
（1）图7.7为二维De Jong函数图形。
图7.7 二维De Jong函数图形
（2）初始种群中个体的目标函数值分布图如图7.8所示。
图7.8 初始种群中个体的目标函数值分布图
（3）经过20次遗传迭代后的结果如图7.9所示。此时min()
f x= 2.7412e+005。
图7.9 经过20次遗传迭代后的结果
（4）经过100次遗传迭代后的结果如图7.10所示。此时min()
f x= 6.9666e+003。
图7.10 经过100次遗传迭代后的结果
（5）经过250次遗传迭代后的结果如图7.11所示。此时min()
f x= 409.4516。
图7.11 经过250次遗传迭代后的结果
（6）经过500次遗传迭代后的结果如图7.12所示。此时min()
f x= 4.2550。
图7.12 经过500次遗传迭代后的结果
（7）经过250次迭代后种群目标函数均值的变化和最优解的变化如图7.13所示。
f x= 4.2550时20个变量的值见表7.1。
min()
图7.13 经过250次迭代后种群目标函数均值的变化和最优解的变化
表7.1 目标函数取最优解时20个变量的值
7.3 多元多峰函数的优化实例
Shubert 函数为：
55121211(,)cos[(1)]cos[(1)]1010(1,2)i i i f x x i i x i i i x i x i ==?=+?+?+?+???-≤≤=?
∑∑， 求
)(min x f 。
图7.14为Shubert 函数图像。
图7.14 Shubert 函数图
下面为 Shubert 函数寻优的MA TLAB 代码。 function z=Shubert (x,y) % Shubert 函数
z= ( (1*cos ( (1+1)*x+1))+ (2*cos ( (2+1)*x+2))+ (3*cos ( (3+1)*x+3))+…
(4*cos ( (4+1)*x+4))+ (5*cos ( (5+1)*x+5))).* ( (1*cos ( (1+1)*y+1))+…
(2*cos ( (2+1)*y+2))+ (3*cos ( (3+1)*y+3))+ (4*cos ( (4+1)*y+4))+ (5*cos ( (5+1)*y+5)));
[x1,x2]=meshgrid (-10:.1:10);
Figure(1);mesh (x1,x2,Shubert (x1,x2)); % 画出Shubert函数图像
% 定义遗传算法参数
NIND = 40; % 个体数目(Number of individuals)
MAXGEN =50; % 最大遗传代数(Maximum number of generations)
NV AR = 2; % 变量数目
PRECI = 25; % 变量的二进制位数(Precision of variables)
GGAP =0.9; % 代沟(Generation gap)
% 建立区域描述器(Build field descriptor)
FieldD = [rep ([PRECI],[1,NV AR]);rep ([-3;3],[1,NV AR]);rep ([1;0;1;1],[1,NV AR])]; Chrom = crtbp (NIND, NV AR*PRECI); % 创建初始种群
gen = 0;
trace=zeros (MAXGEN,2); % 遗传算法性能跟踪初始值
x=bs2rv (Chrom,FieldD); % 初始种群十进制转换
ObjV =Shubert (x (:,1),x (:,2)); % 计算初始种群的目标函数值
while gen < MAXGEN,
FitnV = ranking (ObjV); % 分配适应度值(Assign fitness values) SelCh = select ('sus', Chrom, FitnV, GGAP); % 选择
SelCh = recombin ('xovsp',SelCh,0.7); %重组
SelCh = mut (SelCh); % 变异
x=bs2rv (SelCh,FieldD); % 子代十进制转换
ObjVSel =Shubert (x (:,1),x (:,2)) ; % 重插入
[Chrom ObjV]=reins (Chrom,SelCh,1,1,ObjV,ObjVSel);
gen = gen+1;
[Y,I]=min (ObjVSel);
Y, bs2rv (Chrom (I,:),FieldD)) ; % 输出最优解及其对应的自变量值trace (gen,1)=min (ObjV);
trace (gen,2)=sum (ObjV)/length (ObjV); % 遗传算法性能跟踪
if (gen==50) % 迭代数为50时画出目标函数图figure (2);
plot (ObjV);hold on;
plot (ObjV,'b*');grid;
end
end
figure (3);clf;
plot (trace (:,1));hold on;
plot (trace (:,2),'-.');grid;
legend ('解的变化','种群均值的变化')
遗传算法的显示结果如下：
（1）初始种群的目标函数值分布如图7.15所示。
图7.15 初始种群的目标函数值
（2）经过一次迭代后的目标函数值如图7.16所示。此时=1x -1.3900，=2x -2.9601，)(min x f =-44.5224。
图7.16 经过一次迭代后的结果
（3）经过10次迭代后的目标函数值如图7.17所示。此时=1x -1.3811，=2x 0.8980，)(min x f =-186.0739。
图7.17 经过 10次迭代后的结果
（4）经过50次迭代后的目标函数值如图7.18所示。此时=1x -1.4342，=2x -0.8003，)(min x f = -186.7309。
图7.18 经过50次迭代后的结果
（5）经过50次迭代后，种群目标函数均值的变化和最优解的变化如图7.19所示。
图7.19 经过50次迭代后种群目标函数均值的变化和最优解的变化
7.4 收获系统最优控制
收获系统（Harvest ）是一个一阶的离散方程，表达式为：
(1)*()()1,2,,...(0)()x k a x k u k k N s t x x N +=-?=?=?
这里)0(x 是一个初始的状态条件，a 是一个刻度常量，+∈∈R k u R k x )(,)( 是状态和非常控制，N 是解决问题使用的步骤数。
目标函数为：
∑==N
k k u u f 1)()(max
这个问题的精确优化解答可由下式确定：
)
1()1)(0(max 12
--=-a a a x N N GA 工具箱提供一个M 文件实现这个函数objharv 。注意，这里是一个最大化问题，工具箱例程实现是最小化问题，这个目标函数objharv ，)(u f 乘 –1即产生为最小化问题。这个最初条件x (0)设为100，a 取为1.1。
这个问题的控制步骤N =20，因此使用的决策变量个数NV AR=20，作为每个控制输入U k 。决策变量被限制在RANG=[0，200]范围，限制最大的控制输入在任意步为200，这个区域描
述器FieldD描述决策变量可以使用矩阵复制函数rep构造。
这个GA的参数可用MA TLAB变量来指定。
除了传统GA参数例如代沟(GGAP) 和交叉概率(XOVR)外，还有大量与多种群GAS有关的其它参数被定义。这里INSR = 0.9，说明每一代中只有90%产生个体被复制到种群中，SUBPOP = 8，说明8个子种群使用迁移概率为MIGR =0.2或20%，每20代（MIGGEN= 20）在子种群与当前迁移之间。每个子种群包含20个个体，NIND = 20。
脚本文件使用的函数使用MATLAB串指定。用串SEL_F 、XOV_F、MUT_F、OBJ_F 指定分别代表：选择函数名、重组函数名、变异函数名、目标函数名。
由于使用离散重组函数recdis进行子代的培育，交叉概率没有使用，XOVR = 1。
初始种群的创建使用函数crtrp，代计数器gen设置为0。
在由FieldD指定的范围内使用一致性随机挑选个体决策变量组成SUBPOP *NIND个个体。矩阵Chrom包含了所有子种群并且子种群中所有个体的目标函数值能使用MA TLAB的feval命令直接计算。ObjV = feval (OBJ_F, Chrom);Feval执行函数计算获得第一个输入变量，这里是目标函数名objharv，包含在OBJ_F中，这个函数将被计算并用剩余的参数作为输入调用这个函数。这里函数调用是：
ObjV = objharv (Chrom);
由于使用实值编码，不需要将染色体转换为表现型表示。GA现在将进入代循环。
下面为收获系统最优控制的MA TLAB代码。
% 定义遗传算法参数
NV AR = 20; % 变量维数
RANGE = [0; 200]; % 变量范围
GGAP = 0.8; % 代沟(Generation gap)
XOVR = 1; % 交叉率
MUTR = 1/NV AR; % 变异率
MAXGEN = 500; % 最大遗传代数(Maximum number of generations)
INSR = 0.9; % 插入率
SUBPOP =8; % 子种群数
MIGR = 0.2; % 迁移率
MIGGEN = 20; % 在子种群与迁移之间20代
NIND = 20; % 个体数目(Number of individuals)
SEL_F = 'sus'; % 选择函数名
XOV_F ='recdis'; % 重组函数名
MUT_F ='mutbga'; % 变异函数名
OBJ_F ='objharv'; % 目标函数名
FieldDD = rep (RANGE,[1,NV AR]); % 译码矩阵
gen=0;
trace=zeros (MAXGEN,2); % 遗传算法性能跟踪
Chrom=crtrp (NIND,FieldDD); % 创建初始种群
ObjV = objharv (Chrom); % 计算目标函数值
while gen < MAXGEN, % 代循环
FitnV = ranking (ObjV,[2,1],SUBPOP); %分配适应度值(Assign fitness values)
SelCh = select (SEL_F, Chrom, FitnV, GGAP, SUBPOP); % 选择
SelCh=recombin (XOV_F, SelCh, XOVR, SUBPOP); % 重组
SelCh = mutate (MUT_F,SelCh,FieldDD,[MUTR],SUBPOP); % 变异
ObjVOff = feval (OBJ_F,SelCh); % 计算目标函数值
[Chrom, ObjV] = reins (Chrom, SelCh, SUBPOP,[1 INSR], ObjV, ObjVOff); % 替代
gen=gen+1;
[trace (gen,1),I]=min (ObjV);
trace (gen,2)=mean (ObjV);
% 在子种群之间迁移个体
if (rem (gen,MIGGEN) == 0)
[Chrom, ObjV] = migrate (Chrom, SUBPOP, [MIGR, 1, 1], ObjV);
end
end
[Y,I]=min (ObjV); % 输出最优解及其序号，Y为最优解，I为种群的序号
figure (1);plot (Chrom (I,:));
hold on;grid;
plot (Chrom (I,:),'bo')
figure (2);plot (-trace (:,1));
hold on;
plot (-trace (:,2),'-.'); % 遗传算法性能跟踪分布图
legend ('解的变化','种群均值的变化');xlabel ('迭代次数')
由于使用多子种群，待评定要求指定必须的选择压位差，这里我们用选择压位差为2。指定子种群的个数为SUBPOP。每个子种群的个体的目标值ObjV将独立排序，适应度值结果集将由向量FitnV返回。
在每个子种群中，个体将由高级选择函数select选择独立地培育子代：
SelCh = select (SEL_F, Chrom, FitnV, GGAP, SUBPOP);
Select为每个子种群调用低级选择函数SEL_F ='sus'，并建立包含用于重组的所有个体对的矩阵SelCh，代沟GGAP = 0.8，意思就是0.8* 20 = 16，GGAP*NIND个个体从每个子种群中选择，SelCh包含GGAP*NIND*SUBPOP = 128个个体。
高级重组函数recombin用于重组SelCh中每个子种群中的每对个体。
SelCh = recombin (XOV_F, SelCh, XOVR, SUBPOP);
重组函数XOV_F = 'recdis'对子种群中个体对执行离散重组。由于离散重组不需要指定常规的交叉概率，这里使用变量XOVR = 1.0仅仅是为了兼容。
子代现在将变异：
SelCh = mutate (MUT_F,SelCh,FieldD,MUTR,SUBPOP);
这里GA育种器变异函数MUT_F ='mutbga'使用高级变异例程mutate调用，使用变异概率MUTR = 1/NIND = 0.05。这个GA育种器变异函数需要域描述器FieldD，以使变异还会产生超出决策变量边界的结果。
所有子代的目标值ObjVOff现在可以再用feval计算。
ObjVOff = feval (OBJ_F, SelCh);
子代现在可以插入适当的子种群中。
[Chrom,ObjV]=reins (Chrom, SelCh,SUBPOP,[1,INSR],ObjV,ObjVOff);
使用基于适应度的插入，但对reins的第四个自变量的附加扩展参数指定了插入概率INSR = 0.9。这里的意思是指每个子种群的最小适应度的10%子代不会被插入。
多种群GA的个体在种群之间以相同间隔迁移。工具箱的迁移例程用于在子种群间根据相同的迁移策略交换个体，在这个例子中，每20代（MIGGEN = 20），在子种群间发生迁移。子种群间的迁移语句为：
if (rem (gen, MIGGEN) == 0)
[Chrom, ObjV] = migrate (Chrom, SUBPOP, [MIGR, 1, 1], ObjV);
end
在这里子种群中最适应的20%(MIGR = 0.2)个体被选择迁移。最邻近的子种群在它们之间
交换个体，均匀地重插入移民个体。返回矩阵Chrom和向量ObjV作为迁移结果反映子种群中个体的变化。
GA迭代循环直到gen = MAXGEN并随后终止。
GA搜索获得的结果被包含在矩阵ObjV中。最佳个体的目标值和索引号可用函数min搜索。例如：
[Y, I] = min (ObjV);
运行后得到：
Y = -73.2370, I =50。
注意：改变了目标函数的符号使形成最小化问题，这个结果相当于目标函数值为73.2370，给出的精确解答应为73.2376。因此这个GA优化解与精确解之间的误差在10-5以内。染色体值显示使用如下命令：
plot (Chrom (I,:));
遗传算法的显示结果如下：
（1）图7.20为初始随机种群个体分布图。
图7.20 初始种群的分布图
（2）经过50次迭代后，寻优结果如图7.21所示。此时max()=
f x9.1760。
图7.21 经过50次迭代后的优化解
（3）经过200次迭代后，寻优结果如图7.22所示。此时max()=
f x58.8087。
图7.22 经过200次迭代后的优化解
（4）经过1000次迭代后，寻优结果如图7.23所示。此时max ()=f x 68.0320。
图7.23 经过1000次迭代后的优化解
7.5 装载系统的最优问题
装载系统是一个二维的系统，表达式如下：
122212(1)()1,2,,.1(1)2*()()()+=??=?+=-+??
x k x k k N x k x k x k u k N
目标函数为： ∑=++-=N k k u N N x u x f 1
21)(*21)1(),( 理论最优解为：
∑-=+-+-=11232*21*61*331min N k k N N N
一个实现本目标函数的M 文件objpush 包含在GA 工具箱软件中。 下面为装载系统的最优问题的MATLAB 代码。
%定义遗传算法参数
GGAP = 0.8; % 代沟(Generation gap)
XOVR = 1; % 交叉率
NV AR = 20; % 变量维数
MUTR = 1/NV AR; % 变异率
MAXGEN = 200; % 最大遗传代数(Maximum number of generations)
INSR = 0.9; % 插入率
SUBPOP =12; % 子种群数
MIGR = 0.2; % 迁移率
MIGGEN = 20; % 每20代迁移个体
NIND =20; % 个体数目(Number of individuals)
RANGE=[0;10]; % 变量范围
SEL_F = 'sus'; % 选择函数名
XOV_F ='recdis'; % 重组函数名
MUT_F ='mutbga'; % 变异函数名
OBJ_F ='objpush'; % 目标函数名
FieldDD = rep (RANGE,[1,NV AR]);
trace=zeros (MAXGEN,2); % 遗传算法性能跟踪
Chrom=crtrp (SUBPOP*NIND,FieldDD); % 创建初始种群
gen = 0;
ObjV=feval (OBJ_F,Chrom);
while gen < MAXGEN, % 代循环
FitnV = ranking (ObjV,[2,0],SUBPOP); % 分配适应度值(Assign fitness values)
SelCh = select (SEL_F,Chrom,FitnV, GGAP,SUBPOP); % 选择
SelCh=recombin (XOV_F, SelCh,XOVR,SUBPOP); % 重组
SelCh = mutate (MUT_F,SelCh,FieldDD,[MUTR],SUBPOP); % 变异
ObjVOff=feval (OBJ_F,SelCh); % 计算子代目标函数值
[Chrom, ObjV] = reins (Chrom, SelCh, SUBPOP,[1 INSR], ObjV, ObjVOff); % 替代
gen=gen+1;
[trace (gen,1),I]=min (ObjV);
trace (gen,2)=mean (ObjV);
end
[Y,I]=min (ObjV); % 最优控制向量值及其序号
subplot (211); % 最优控制向量分布图
plot (Chrom (I,:));hold on;
plot (Chrom (I,:),'.');grid
subplot (212); % 遗传算法性能跟踪分布图
plot (trace (:,1));hold on;
plot (trace (:,2),'-');grid
legend ('解的变化','种群均值的变化')
遗传算法的显示结果如下：
（1）经过50次迭代后的优化解的目标函数值及性能跟踪如图7.24所示。此时min=f0.0369。
图7.24 经过50次迭代后的优化解的目标函数值及性能跟踪
（2）经过100次迭代后的优化解的目标函数值及性能跟踪如图7.25所示。此时min=f-0.1425。
图7.25 经过100次迭代后的优化解的目标函数值及性能跟踪
（3） 经过200次迭代后的优化解的目标函数值及性能跟踪如图7.26所示。此时min =f -0.1536。
图7.26 经过200次迭代后的优化解的目标函数值及性能跟踪
为了比较，计算出理论最优解：
2012231
132011min -0.15443620220k f k -=?-=-++=??∑。 经过200次迭代后的优化解-0.1536与理论最优解-0.1544的误差仅为0.0008。
7.6 离散二次线性系统最优控制问题
假设二阶线性系统是一维的，其表达式为：
(1)*()*(),
1,2,,.x k a x k b u k k N +=+=
目标函数定义为： ∑=+++=N
k k u r k x s n x q u x f 1222
])(*)(*[)1(*),(
求
x
min u
f
,(
)
参数设置为：
下面为离散二次线性系统最优控制的MA TLAB代码。
% 定义遗传算法参数
GGAP = 0.8; % 代沟(Generation gap)
XOVR = 1; % 交叉率
NV AR = 45; % 变量维数
MUTR = 1/NV AR; % 变异率
MAXGEN = 2000; % 最大遗传代数(Maximum number of generations)
INSR = 0.9; % 插入率
SUBPOP =12; % 子代数目
MIGR = 0.2; % 迁移率
MIGGEN = 20; % 每20代迁移个体
NIND =20; % 个体数目(Number of individuals)
SEL_F = 'sus'; % 选择函数名
XOV_F ='recdis'; % 重组函数名
MUT_F ='mutbga'; % 变异函数名
OBJ_F ='objlinq'; % 目标函数名
FieldDR=feval (OBJ_F,[ ],1);
Chrom=crtrp (SUBPOP*NIND,FieldDR); % 创建初始种群
gen = 0;
trace=zeros (MAXGEN,2); % 遗传算法性能跟踪
ObjV=feval (OBJ_F,Chrom); % 计算目标函数值
while gen < MAXGEN, % 代循环
trace (gen+1,1)=min (ObjV);
trace (gen+1,2)=mean (ObjV);
FitnV = ranking (ObjV,[2,0],SUBPOP); % 分配适应度值(Assign fitness values) SelCh = select (SEL_F,Chrom,FitnV, GGAP,SUBPOP); % 选择
SelCh=recombin (XOV_F, SelCh,XOVR,SUBPOP); % 重组
SelCh = mutate (MUT_F,SelCh,FieldDR,[MUTR],SUBPOP) ; % 变异
ObjVOff=feval (OBJ_F,SelCh); %计算目标函数值
[Chrom, ObjV] = reins (Chrom, SelCh, SUBPOP,[1 INSR], ObjV, ObjVOff); % 替代gen=gen+1;
end
[Y,I]=min (ObjV);
subplot (211);
plot (Chrom (I,:));
hold on;
plot (Chrom (I,:),'.');grid % 最优控制向量分布图
legend ('最优控制向量')
subplot (212); % 遗传算法性能跟踪分布图
plot (trace (:,1));
hold on;plot (trace (:,2),'-.');grid
legend ('解的变化','种群均值的变化'); xlabel ('迭代次数')
遗传算法的显示结果如下：
（1）经过100次迭代后的优化解的目标函数值及性能跟踪如图7.27所示。此时min=f26503。
图7.27 经过100次迭代后的优化解的目标函数值及性能跟踪
（2）经过1000次迭代后的优化解的目标函数值及性能跟踪如图7.28所示。此时min=f17259。
图7.28 经过1000次迭代后的优化解的目标函数值及性能跟踪
（3）经过2000次迭代后的优化解的目标函数值及性能跟踪如图7.29所示。此时min16337
=f。
图7.29 经过2000次迭代后的优化解的目标函数值及性能跟踪
7.7 目标分配问题
目标分配问题描述为：m 个地空导弹火力单元对n 批空袭目标进行目标分配。假设进行目标分配之前，各批目标的威胁程度与个火力单元对各批目标的射击有利程度已经经过评估和排序。第j 批目标的威胁程度评估值为j w ，第i 个火力单元对第j 批目标射击有利程度估计值为ij p ，令各火力单元对各批目标进行拦击的效益值为ij j ij p w c ?=，其中ij c 表示对某批目标进行拦击我方获益大小程度。目标分配的目的是满足目标分配的基本原则，追求总体效益最佳，即求1max()n ij j c
=∑。
染色体采用十进制编码，染色体的长度由按目标批次编号顺序排列的火力单元分配编号组成，表示一种可能的分配方案。
下面为目标分配的最优问题的MATLAB 代码。 function [eval]=targetalloc (chrom) % 目标函数
[m,n]=size (chrom);
% 射击有利程度估计值
p=[ .87 .52 .11 .78 .72 .69 .94 .72 .36 .28 .27 .74 .24 .78 .45;...
.87 .52 .11 .78 .72 .69 .94 .72 .36 .28 .27 .74 .24 .78 .45;...
.87 .52 .11 .78 .72 .69 .94 .72 .36 .28 .27 .74 .24 .78 .45;...
.87 .52 .11 .78 .72 .69 .94 .72 .36 .28 .27 .74 .24 .78 .45;...
.87 .52 .11 .78 .72 .69 .94 .72 .36 .28 .27 .74 .24 .78 .45;...
.87 .52 .11 .78 .72 .69 .94 .72 .36 .28 .27 .74 .24 .78 .45;...
.62 .87 .70 .22 .80 .42 .43 .90 .13 .95 .18 .19 .12 .61 .35;...
.48 .20 .42 .16 .43 .58 .69 .03 .34 .72 .15 .24 .29 .30 .75 ];
w=[.47 .97 .76 .62 .48 .77 .33 .74 .54 .65 .43 .35 .63 .66 .57]; % 威胁程度评估值 for i=1:m
for j=1:15
chrom (i,j)=p(chrom (i,j),j);
end;
end
eval=chrom*w';
% 定义遗传算法参数
NIND = 40; % 个体数目(Number of individuals)
MAXGEN =50; % 最大遗传代数(Maximum number of generations) GGAP = 0.9; % 代沟(Generation gap)
trace=zeros (MAXGEN,2); % 遗传算法性能跟踪初始值
BaseV= crtbase (15,8);
Chrom=crtbp (NIND, BaseV)+ones (NIND,15); %初始种群
gen = 0;
ObjV = taretalloc (Chrom); % 计算初始种群函数值
while gen < MAXGEN,
FitnV = ranking (-ObjV); % 分配适应度值(Assign fitness values)
SelCh = select ('sus', Chrom,FitnV , GGAP); % 选择
遗传算法入门到掌握 读完这个讲义，你将基本掌握遗传算法，要有耐心看完。 想了很久，应该用一个怎么样的例子带领大家走进遗传算法的神奇世界呢？遗传算法的有趣应用很多，诸如寻路问题，8数码问题，囚犯困境，动作控制，找圆心问题（这是一个国外网友的建议：在一个不规则的多边形中，寻找一个包含在该多边形内的最大圆圈的圆心。），TSP问题（在以后的章节里面将做详细介绍。），生产调度问题，人工生命模拟等。直到最后看到一个非常有趣的比喻，觉得由此引出的袋鼠跳问题（暂且这么叫它吧），既有趣直观又直达遗传算法的本质，确实非常适合作为初学者入门的例子。这一章将告诉读者，我们怎么让袋鼠跳到珠穆朗玛峰上去(如果它没有过早被冻坏的话)。 问题的提出与解决方案 让我们先来考虑考虑下面这个问题的解决办法。 已知一元函数： 图2-1 现在要求在既定的区间内找出函数的最大值。函数图像如图2-1所示。 极大值、最大值、局部最优解、全局最优解
在解决上面提出的问题之前我们有必要先澄清几个以后将常常会碰到的概念：极大值、最大值、局部最优解、全局最优解。学过高中数学的人都知道极大值在一个小邻域里面左边的函数值递增，右边的函数值递减，在图2.1里面的表现就是一个“山峰”。当然，在图上有很多个“山峰”，所以这个函数有很多个极大值。而对于一个函数来说，最大值就是在所有极大值当中，最大的那个。所以极大值具有局部性，而最大值则具有全局性。 因为遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。所以也可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。在这个多维曲面里面也有数不清的“山峰”，而这些最优解所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遗传算法不一定要找“最高的山峰”，如果问题的适应度评价越小越好的话，那么全局最优解就是函数的最小值，对应的，遗传算法所要找的就是“最深的谷底”）如果至今你还不太理解的话，那么你先往下看。本章的示例程序将会非常形象的表现出这个情景。 “袋鼠跳”问题 既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰（尽管袋鼠本身不见得愿意那么做）。所以求最大值的过程就转化成一个“袋鼠跳”的过程。下面介绍介绍“袋鼠跳”的几种方式。 爬山法、模拟退火和遗传算法 解决寻找最大值问题的几种常见的算法： 1. 爬山法（最速上升爬山法）： 从搜索空间中随机产生邻近的点，从中选择对应解最优的个体，替换原来的个体，不断重复上述过程。因为只对“邻近”的点作比较，所以目光比较“短浅”，常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题，通过一个简单的迭代找出全局最优解的机会非常渺茫。（在爬山法中，袋鼠最有希望到达最靠近它出发点的山顶，但不能保证该山顶是珠穆朗玛峰，或者是一个非常高的山峰。因为一路上它只顾上坡，没有下坡。） 2. 模拟退火： 这个方法来自金属热加工过程的启发。在金属热加工过程中，当金属的温度超过它的熔点（Melting Point）时，原子就会激烈地随机运动。与所有的其它的物理系统相类似，原子的这种运动趋向于寻找其能量的极小状态。在这个能量的变
摘要 随着科学技术和社会信息技术的不断提高，计算机科学的日渐成熟，其强大的功能已为人们深刻认识，它在人类社会的各个领域发挥着越来越重要的作用，给人们的生活带来了极大的便利，成为推动社会发展的首要技术动力。排课是学校教学管理中十分重要、又相当复杂的工作之一。解决好教学工作中的排课问题对整个教学计划的进行，有着十分重要的意义。首先对排课的已有算法作了相关的调查研究，决定采用遗传算法。通过设计实现基于遗传算法的自动排课系统，研究了遗传算法在排课系统中的应用。 关键词：遗传算法、自动排课、Java。
Abstract Along with science technical and community information technical increases continuously, calculator science is gradually mature, its mighty function has behaved deep cognition, and it has entered the human social each realm erupts to flick the more and more important function, bringing our life biggest of convenience. Curriculum arrangement is an important and complicated working in school,so solving the problem is of great importance for teaching programming.Investigated and studied the algorithm existed, determine that adoptgenetic algorithm. ThroughDesign Implementation theAuto CourseArrangementManagement System Base onGenetic Algorithm, researched the application of genetic algorithmin theCourseArrangementManagement System. Keywords: Genetic Algorithm Auto Course Arrangement ManagementJava.
基本遗传算法及应用举例 遗传算法(Genetic Algorithms)是一种借鉴生物界自然选择和自然遗传机制的随机、高度并行、自适应搜索算法。遗传算法是多学科相互结合与渗透的产物。目前它已发展成一种自组织、自适应的多学科技术。 针对各种不同类型的问题，借鉴自然界中生物遗传与进化的机理，学者们设计了不同的编码方法来表示问题的可行解，开发出了许多不同环境下的生物遗传特征。这样由不同的编码方法和不同的遗传操作方法就构成了各种不同的遗传算法。但这些遗传算法有共同的特点，即通过对生物的遗传和进化过程中的选择、交叉、变异机理的模仿来完成对最优解的自适应搜索过程。基于此共同点，人们总结出了最基本的遗传算法——基本遗传算法。基本遗传算法只使用选择、交叉、变异三种基本遗传操作。遗传操作的过程也比较简单、容易理解。同时，基本遗传算法也是其他一些遗传算法的基础与雏形。 1．1．1 编码方法 用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。 编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。每个个体的染色体中所包含的数字的个数L 称为染色体的长度或称为符号串的长度。一般染色体的长度L 为一固定的数，如 X=1010100 表示一个个体，该个体的染色体长度L=20。 二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[a ，b]，我们用长度为L 的二进制编码符号串来表示该参数，总共能产生L 2种不同的编码，若参数与编码的对应关系为 00000000000……00000000=0 →a 00000000000……00000001=1 →a+δ ? ? ? ……=L 2-1→b 则二进制编码的编码精度1 2--= L a b δ 假设某一个个体的编码是kl k k k a a a x 21=，则对应的解码公式为 )2(121 ∑=---+=L j j L kj L k a a b a x 例如，对于x ∈[0,1023],若用长度为10的二进制编码来表示该参数的话，则下述符号串：
实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下： 序号遗传学概念遗传算法概念数学概念 1 个体要处理的基本对象、结构也就是可行解 2 群体个体的集合被选定的一组可行解 3 染色体个体的表现形式可行解的编码 4 基因染色体中的元素编码中的元素 5 基因位某一基因在染色体中的位置元素在编码中的位置 6 适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应的适应函数值 7 种群被选定的一组染色体或个体根据入选概率定出的一组 可行解 8 选择从群体中选择优胜的个体， 淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解 9 交叉一组染色体上对应基因段的 交换根据交叉原则产生的一组新解 10 交叉概率染色体对应基因段交换的概 率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.90 11 变异染色体水平上基因变化编码的某些元素被改变
遗传算法经典学习Matlab代码 遗传算法实例: 也是自己找来的，原代码有少许错误，本人都已更正了，调试运行都通过了的。 对于初学者，尤其是还没有编程经验的非常有用的一个文件 遗传算法实例 % 下面举例说明遗传算法 % % 求下列函数的最大值 % % f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] % % 将 x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为 (10-0)/(2^10-1)≈0.01。 % % 将变量域 [0,10] 离散化为二值域 [0,1023], x=0+10*b/1023, 其 中 b 是 [0,1023] 中的一个二值数。 % % % %--------------------------------------------------------------------------------------------------------------% %--------------------------------------------------------------------------------------------------------------% % 编程 %----------------------------------------------- % 2.1初始化(编码) % initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)，
% 长度大小取决于变量的二进制编码的长度(在本例中取10位)。 %遗传算法子程序 %Name: initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand随机产生每个单元 为 {0,1} 行数为popsize，列数为chromlength的矩阵， % roud对矩阵的每个单元进行圆整。这样产生的初始种群。 % 2.2 计算目标函数值 % 2.2.1 将二进制数转化为十进制数(1) %遗传算法子程序 %Name: decodebinary.m %产生 [2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制function pop2=decodebinary(pop) [px,py]=size(pop); %求pop行和列数 for i=1:py pop1(:,i)=2.^(py-i).*pop(:,i); end pop2=sum(pop1,2); %求pop1的每行之和 % 2.2.2 将二进制编码转化为十进制数(2) % decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置
第七章 遗传算法应用举例 遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架，它不依赖于问题具体的领域。随着对遗传算法技术的不断研究，人们对遗传算法的实际应用越来越重视，它已经广泛地应用于函数优化、组合优化、自动控制、机器人学、图象处理、人工生命、遗传编码、机器学习等科技领域。遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等多方面的应用取得了成功。本章通过一些例子，介绍如何利用第五章提供的遗传算法通用函数，编写MATLAB 程序，解决实际问题。 7.1 简单一元函数优化实例 利用遗传算法计算下面函数的最大值： ()sin(10) 2.0[1,2]f x x x x π=?+∈-， 选择二进制编码，种群中个体数目为40，每个种群的长度为20，使用代沟为0.9，最大遗传代数为25。 下面为一元函数优化问题的MA TLAB 代码。 figure(1); fplot ('variable.*sin(10*pi*variable)+2.0',[-1,2]); %画出函数曲线 % 定义遗传算法参数 NIND= 40; % 个体数目(Number of individuals) MAXGEN = 25; % 最大遗传代数(Maximum number of generations) PRECI = 20; % 变量的二进制位数(Precision of variables) GGAP = 0.9; % 代沟(Generation gap) trace=zeros (2, MAXGEN); % 寻优结果的初始值 FieldD = [20;-1;2;1;0;1;1]; % 区域描述器(Build field descriptor) Chrom = crtbp(NIND, PRECI); % 初始种群 gen = 0; % 代计数器 variable=bs2rv(Chrom,FieldD); % 计算初始种群的十进制转换 ObjV = variable.*sin (10*pi*variable)+2.0; % 计算目标函数值 while gen < MAXGEN, FitnV = ranking (-ObjV); % 分配适应度值(Assign fitness values) SelCh = select ('sus', Chrom, FitnV , GGAP); % 选择 SelCh = recombin ('xovsp',SelCh,0.7); % 重组 SelCh = mut(SelCh); % 变异 variable=bs2rv(SelCh,FieldD); % 子代个体的十进制转换 ObjVSel =variable.*sin(10*pi*variable)+2.0; % 计算子代的目标函数值 [Chrom ObjV]=reins(Chrom,SelCh,1,1,ObjV ,ObjVSel); % 重插入子代的新种群 gen = gen+1; % 代计数器增加 % 输出最优解及其序号，并在目标函数图象中标出，Y 为最优解，I 为种群的序号 [Y,I]=max(ObjV),hold on; plot (variable (I),Y , 'bo'); trace (1,gen)=max (ObjV); %遗传算法性能跟踪
遗传算法的基本理论 一、起源： 早在20世纪50年代和60年代，就有少数人几个计算机科学家独立地进行了所谓的“人工进化系统”研究，其出发点是进化的思想可以发展成为许多工程问题的优化工具。早期的研究形成了遗传算法的雏形，如大多数系统都遵循“适者生存”的仿自然法则，有些系统采用了基于群体（population）的设计方案，并且加入了自然选择与变异操作，还有一些系统对生物染色体编码进行了抽象处理，应用二进制编码。由于缺乏一种通用的编码方案，人们只能依赖变异而非交叉来产生新的基因结构，早期的算法收敛甚微。20世纪60年代中期，美国Michigan大学的John Holland在A.S.Fraser和H.J.Bremermann等人工作的基础上提出了位串编码技术。这种编码既适用于变异操作，又适用于交叉（即杂交）操作。并且强调将交叉作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为的研究中，并于1975年出版了其开创性著作“Adaption in Natural and Artificial System”。以后，Holland等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传算法。遗传算法的通用编码技术和简单有效的遗传操作作为其广泛、成功地应用奠定了基础。Holland早期有关遗传算法的许多概念一直沿用至今，可见Holland对遗传算法的贡献之大。他认为遗传算法本质上是适应算法，应用最多的是系统最优化的研究。 二、发展： 年份贡献者内容 1962Holland程序漫游元胞计算机自适应系统框架 1968Holland模式定理的建立 1971Hollstein具有交配和选择规则的二维函数优化 1972Bosworth、Foo、Zeigler提出具有复杂变异、类似于遗传算法的基因操作1972Frantz位置非线性和倒位操作研究 1973Holland遗传算法中试验的最优配置和双臂强盗问题 1973Martin类似遗传真法的概率算法理论 1975De Jong用于5个测试函数的研究基本遗传算法基准参数 1975Holland 出版了开创性著作《Adaptation in Natural and Artificial System》 1981Bethke应用Walsh函数分析模式 1981Brindle研究遗传算法中的选择和支配问题 1983Pettit、Swigger遗传算法应用于非稳定问题的粗略研究1983Wetzel用遗传算法解决旅行商问题(TSP) 1984Mauldin基本遗传算法小用启发知识维持遗传多样性1985Baker试验基于排序的选择方法 1985Booker建议采用部分匹配计分、分享操作和交配限制法1985Goldberg、Lingle TSP问题个采用部分匹配交叉 1985Grefenstette、Fitzpattrick对含噪声的函数进行测试 1985Schaffer多种群遗传算法解决多目标优化问题1986Goldberg最优种群大小估计 1986Grefenstette元级遗传算法控制的遗传算法 1987Baker选择中随机误差的减少方法 1987Goldberg复制和交叉时最小欺骗问题(MDP) 1987Goldberg、Richardson借助分享函数的小生境和物种归纳法
Logistics Sci-Tech 2010.5 收稿日期：2010－02－07 作者简介：周兴建（1979-），男，湖北黄冈人，武汉科技学院经济管理学院，讲师，武汉理工大学交通学院博士研究生，研究方向：物流价值链、物流系统规划；刘元奇（1988-），男，甘肃天水人，武汉科技学院经济管理学院；李泉（1989-），男，湖北 武汉人，武汉科技学院经济管理学院。 文章编号：1002-3100(2010)05-0038-03 物流科技2010年第5期Logistics Sci-Tech No.5,2010 摘 要：应用遗传算法对邯运集团仓库库位进行优化。在充分考虑邯运集团仓库所存放的货物种类、货物数量、出入库频 率等因素的基础上进行库位预分区规划，建立了二次指派问题的数学模型。利用遗传算法对其求解，结合MATLAB 进行编程计算并得出最优划分方案。 关键词：遗传算法；预分区规划；库位优化中图分类号：F253.4 文献标识码：A Abstract:The paper optimize the storage position in warehouse of Hanyun Group based on genetic algorithm.With thinking of the factors such as goods categories,quantities and frequencies of I/O,etc,firstly,the storage district is planned.Then the model of quadratic assignment problems is build,and genetic algorithm is utilized to resolve the problem.The software MATLAB is used to program and figure out the best alternatives. Key words:genetic algorithm;district planning;storage position optimization 1 库位优化的提出 邯郸交通运输集团有限公司（简称“邯运集团”）是一家集多种业务为一体的大型综合性物流企业。邯运集团的主要业务板块有原料采购（天信运业及天昊、天诚、天恒等）、快递服务（飞马快运）、汽贸业务（天诚汽贸）及仓储配送（河北快运）等。其中，邯运集团的仓储配送业务由河北快运经营，现有仓库面积总共40000㎡，主要的业务范围为医药、日用百货、卷烟、陶瓷、化工产品的配送，其中以医药为主。邯运集团库存货物主要涉及两个方面：一个是大宗的供应商货物，如医药，化工产品等；另一方面主要是大规模的小件快递货物，如日用百货等[1]。经分析，邯运集团在仓储运作方面存在如下问题： （1）存储货物繁多而分拣速度低下。仓库每天到货近400箱，有近200多种规格，缺乏一套行之有效的仓储管理系统。（2）货架高度不当而货位分配混乱。现在采用的货架高度在2米以上，而且将整箱货物直接码垛在货架上，不严格按货位摆放。当需要往货架最上层码放货物需要借助梯子，增加操作难度且操作效率较低。货物在拣货区货架摆放是以件为单位的，分拣和搬运速度较慢。 （3）拣货货架设计不当而仓储效率低下。发货前装箱工作主要由人工协同完成，出库效率低，出错率难以控制。 （4）存储能力和分拣能力不能满足需求。根据邯运集团的业务发展现状及趋势，现有的仓库储存和分拣能力远远达不到集团公司对配送业务量的需求。 当前邯运集团的货位分配主要采用物理地址编码的方式，很少考虑货位分配对仓储管理员工作效率的影响。对其进行库位优化设计不仅直接影响到其库存量的大小、出入库的效率，还间接影响到邯运集团的整体经营效益。本文对邯运集团的仓库货位进行优化时，结合考虑仓库所存放的货物种类、货物数量、出入库频率等因素，对仓库货位进行规划，以提高仓储效率。 2库位预分区规划 在进行仓库货位规划时，作如下假设： （1）货物的存放种类已知； （2）货物每种类的单位时间内存放的数量己知； （3） 每一种货物的存取频率已知。 在仓库货位优化中一个重要的环节即预分区。所谓预分区，是指没有存放货物时的分区，分区时只考虑仓储作业人员的速基于遗传算法的库位优化问题 Optimization of Storage Position in Warehouse Based on Genetic Algorithm 周兴建1,2，刘元奇1，李泉1 ZHOU Xing-jian 1,2,LIU Yuan-qi 1,LI Quan 1 （1.武汉科技学院经济管理学院，湖北武汉430073；2.武汉理工大学交通学院，湖北武汉430063） (1.College of Economics &Management,Wuhan University of Science &Engineering,Wuhan 430073,China; 2.School of Transportation,Wuhan University of Technology,Wuhan 430063,China) !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 38
北京师范大学珠海分校 本科生毕业论文（设计）开题报告
理论和实践的意义及可行性论述 (包括文献综述) 理论和实践的意义：当前，现代物流是企业继续降低物资消耗、提高劳动生产 率后的第三利润源泉。但我国物流企业的运输成本普遍偏高。其中很重要一个 原因就是对配送车辆运输路线规划不科学。要想降低运输成本，离不开对配送 路线的优化和配送车辆的合理安排。对物流配送车辆行驶路径进行优化，可以降低物流成本，节约运输时间，是提高物流经济效益的有效手段。 可行性论述：配送路径优化问题是典型的优化组合问题，具有很高的计算复杂 性。但遗传算法解决作为一种有效的全局搜索方法具有隐并行性和较强的鲁棒性，在解决非线性的大规模复杂问题上具有很好的适应性，适合于对VPR问 题进行优化求解。标准遗传算法虽然未必每次都能找到最优解，但通过对标准 遗传算法进行改进，完全可以在有限时间内对较复杂的VPR问题计算出次优 解或可行解。因此，用遗传算法来解决物流车辆调度问题还是完全可行的。 文献综述： [1]朱剑英?非经典数学方法[M].武昌：华中科技大学出版社，2001 [2]李敏强，寇纪淞，林丹，李书全?遗传算法的基本理论与应用[M].北京：科 学技术出版社，2002 [3]孙丽丽?物流配送中车辆路径算法分析与研究[D].上海：上海海事大学，2007 [4]盖杉.基于遗传算法的物流配送调度系统 [D].长春：长春理工大学，2007 [5]高运良，基于免疫遗传算法的物流配送V RP 求解[D].武汉：武汉科技大学， 2007 论文撰写过程中拟采取的方法和手段 本论文主要采用遗传算法作为解决物流配送路径优化问题的主要算法。但由于标准遗传算法具有“早熟收敛”的缺陷，有可能使算法陷入局部最优解。论文还将尝试通过把其他算法和遗传算法相结合，来有效控制早熟现象的发生。为了快速得到任意两个配送点之间的最优路线。本论文还拟采用佛洛依德 算法构造配送路线的地理数据库的方式来对路线网络进行预处理。从而减少整 个算法的时间复杂度和空间复杂度。
2016年第17期 科技创新科技创新与应用 遗传算法的应用研究 赵夫群 （咸阳师范学院，陕西咸阳712000） 1概述 遗传算法（Genetic Algorithms，GA）一词源于人们对自然进化系统所进行的计算机仿生模拟研究，是以达尔文的“进化论”和孟德尔的“遗传学原理”为基础的，是最早开发出来的模拟遗传系统的算法模型。遗传算法最早是由Fraser提出来的，后来Holland对其进行了推广，故认为遗传算法的奠基人是Holland。 随着遗传算法的不断完善和成熟，其应用范围也在不断扩大，应用领域非常广泛，主要包括工业控制、网络通讯、故障诊断、路径规划、最优控制等。近几年，出现了很多改进的遗传算法，改进方法主要包括：应用不同的交叉和变异算子；引入特殊算子；改进选择和复制方法等。但是，万变不离其宗，都是基于自然界生物进化，提出的这些改进方法。 2遗传算法的原理 遗传算法是从某一个初始种群开始，首先计算个体的适应度，然后通过选择、交叉、变异等基本操作，产生新一代的种群，重复这个过程，直到得到满足条件的种群或达到迭代次数后终止。通过这个过程，后代种群会更加适应环境，而末代种群中的最优个体，在经过解码之后，就可以作为问题的近似最优解了。 2.1遗传算法的四个组成部分 遗传算法主要由四个部分组成[1]：参数编码和初始群体、适应度函数、遗传操作和控制参数。编码方法中，最常用的是二进制编码，该方法操作简单、便于用模式定理分析。适应度函数是由目标函数变换而成的，主要用于评价个体适应环境的能力，是选择操作的依据。遗传操作主要包括了选择、交叉、变异等三种基本操作。控制参数主要有：串长Z，群体大小size，交叉概率Pc，变异概率Pm等。目前对遗传算法的研究主要集中在参数的调整中，很多文献建议的参数取值范围一般是：size取20~200之间，Pc取0.5~1.0之间，Pm取0~0.05之间。 2.2遗传算法的基本操作步骤 遗传算法的基本操作步骤为： （1）首先，对种群进行初始化；（2）对种群里的每个个体计算其适应度值；（3）根据（2）计算的适应度，按照规则，选择进入下一代的个体；（4）根据交叉概率Pc，进行交叉操作；（5）以Pm为概率，进行变异操作；（6）判断是否满足停止条件，若没有，则转第（2）步，否则进入（7）；（7）得到适应度值最优的染色体，并将其作为问题的满意解或最优解输出。 3遗传算法的应用 遗传算法的应用领域非常广泛，下面主要就遗传算法在优化问题、生产调度、自动控制、机器学习、图像处理、人工生命和数据挖掘等方面的应用进行介绍。 3.1优化问题 优化问题包括函数优化和组合优化两种。很多情况下，组合优化的搜索空间受问题规模的制约，因此很难寻找满意解。但是，遗传算法对于组合优化中的NP完全问题非常有效。朱莹等[2]提出了一种结合启发式算法和遗传算法的混合遗传算法来解决杂货船装载的优化问题中。潘欣等[3]在化工多目标优化问题中应用了并行遗传算法，实验结果表明该方法效果良好。王大东等[4]将遗传算法应用到了清运车辆路径的优化问题求解中，而且仿真结果表明算法可行有效。 3.2生产调度 在复杂生产调度方面，遗传算法也发挥了很大的作用。韦勇福等[5]将遗传算法应用到了车间生产调度系统的开发中，并建立了最小化完工时间目标模型，成功开发了车间生产调度系统模块，并用实例和仿真验证了该方法的可行性。张美凤等[6]将遗传算法和模拟退火算法相结合，提出了解决车间调度问题的混合遗传算法，并给出了一种编码方法以及建立了相应的解码规则。 3.3自动控制 在自动控制领域中，遗传算法主要用于求解的大多也是与优化相关的问题。其应用主要分为为两类，即离线设计分析和在线自适应调节。GA可为传统的综合设计方法提供优化参数。 3.4机器学习 目前，遗传算法已经在机器学习领域得到了较为广泛的应用。邢晓敏等[7]提出了将遗传算子与Michigan方法和基于Pitt法的两个机器学习方法相结合的机器学习方法。蒋培等[8]提出了一种基于共同进化遗传算法的机器学习方法，该方法克服了学习系统过分依赖于问题的背景知识的缺陷，使得学习者逐步探索新的知识。 3.5图像处理 图像处理是一个重要的研究领域。在图像处理过程中产生的误差会影响图像的效果，因此我们要尽可能地减小误差。目前，遗传算法已经在图像增强、图像恢复、图像重建、图像分形压缩、图像分割、图像匹配等方面应用广泛，详见参考文献[9]。 4结束语 遗传算法作为一种模拟自然演化的学习过程，原理简单，应用广泛，已经在许多领域解决了很多问题。但是，它在数学基础方面相对不够完善，还有待进一步研究和探讨。目前，针对遗传算法的众多缺点，也相继出现了许多改进的算法，并取得了一定的成果。可以预期，未来伴随着生物技术和计算机技术的进一步发展，遗传算法会在操作技术等方面更加有效，其发展前景一片光明。 参考文献 [1]周明，孙树栋.遗传算法原理及应用[M].国防工业出版社，1999，6. [2]朱莹，向先波，杨运桃.基于混合遗传算法的杂货船装载优化问题[J].中国船舰研究，2015：10（6）：126-132. [3]潘欣，等.种群分布式并行遗传算法解化工多目标优化问题[J].化工进展，2015：34（5）：1236-1240. [4]王大东，刘竞遥，王洪军.遗传算法求解清运车辆路径优化问题[J].吉林师范大学学报（自然科学版），2015（3）：132-134. [5]韦勇福，曾盛绰.基于遗传算法的车间生产调度系统研究[J].装备制造技术，2014（11）：205-207. [6]黄巍，张美凤.基于混合遗传算法的车间生产调度问题研究[J].计算机仿真，2009，26（10）：307-310. [7]邢晓敏.基于遗传算法的机器学习方法赋值理论研究[J].软件导刊[J].2009，8（11）：80-81. [8]蒋培.基于共同进化遗传算法的机器学习[J].湖南师范大学自然科学学报，2004，27（3）：33-38. [9]田莹，苑玮琦.遗传算法在图像处理中的应用[J].中国图象图形学报，2007，12（3）：389-396. [10]周剑利，马壮，陈贵清.基于遗传算法的人工生命演示系统的研究与实现[J].制造业自动化，2009，31（9）：38-40. [11]刘晓莉，戎海武.基于遗传算法与神经网络混合算法的数据挖掘技术综述[J].软件导刊，2013，12（12）：129-130. 作者简介：赵夫群（1982，8-），女，汉族，籍贯：山东临沂，咸阳师范学院讲师，西北大学在读博士，工作单位：咸阳师范学院教育科学学院，研究方向：三维模型安全技术。 摘要：遗传算法是一种非常重要的搜索算法，特别是在解决优化问题上，效果非常好。文章首先介绍了遗传算法的四个组成部分，以及算法的基本操作步骤，接着探讨了遗传算法的几个主要应用领域，包括优化、生产调度、机器学习、图像处理、人工生命和数据挖掘等。目前遗传算法以及在很多方面的应用中取得了较大的成功，但是它在数学基础方面相对还不够完善，因而需要进一步研究和完善。 关键词：遗传算法；优化问题；数据挖掘 67 --
遗传算法的C语言程序案例 一、说明 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．举个例子，输入初始变量后，用y= (x1*x1)+(x2*x2)，其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 4．程序流程图
5．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual { char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 6．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个
最新发布的MA TLAB 7.0 Release 14已经包含了一个专门设计的遗传算法与直接搜索工具箱（Genetic Algorithm and Direct Search Toolbox，GADS）。使用遗传算法与直接搜索工具箱，可以扩展MATLAB及其优化工具箱在处理优化问题方面的能力，可以处理传统的优化技术难以解决的问题，包括那些难以定义或不便于数学建模的问题，可以解决目标函数较复杂的问题，比如目标函数不连续、或具有高度非线性、随机性以及目标函数没有导数的情况。 本章8.1节首先介绍这个遗传算法与直接搜索工具箱，其余各节分别介绍该工具箱中的遗传算法工具及其使用方法。 8.1 遗传算法与直接搜索工具箱概述 本节介绍MATLAB的GADS（遗传算法与直接搜索）工具箱的特点、图形用户界面及运行要求，解释如何编写待优化函数的M文件，且通过举例加以阐明。 8.1.1 工具箱的特点 GADS工具箱是一系列函数的集合，它们扩展了优化工具箱和MA TLAB数值计算环境的性能。遗传算法与直接搜索工具箱包含了要使用遗传算法和直接搜索算法来求解优化问题的一些例程。这些算法使我们能够求解那些标准优化工具箱范围之外的各种优化问题。所有工具箱函数都是MATLAB的M文件，这些文件由实现特定优化算法的MATLAB语句所写成。 使用语句 type function_name 就可以看到这些函数的MATLAB代码。我们也可以通过编写自己的M文件来实现来扩展遗传算法和直接搜索工具箱的性能，也可以将该工具箱与MATLAB的其他工具箱或Simulink结合使用，来求解优化问题。 工具箱函数可以通过图形界面或MA TLAB命令行来访问，它们是用MATLAB语言编写的，对用户开放，因此可以查看算法、修改源代码或生成用户函数。 遗传算法与直接搜索工具箱可以帮助我们求解那些不易用传统方法解决的问题，譬如表查找问题等。 遗传算法与直接搜索工具箱有一个精心设计的图形用户界面，可以帮助我们直观、方便、快速地求解最优化问题。 8.1.1.1 功能特点 遗传算法与直接搜索工具箱的功能特点如下： 图形用户界面和命令行函数可用来快速地描述问题、设置算法选项以及监控进程。 具有多个选项的遗传算法工具可用于问题创建、适应度计算、选择、交叉和变异。 直接搜索工具实现了一种模式搜索方法，其选项可用于定义网格尺寸、表决方法和搜索方法。 遗传算法与直接搜索工具箱函数可与MATLAB的优化工具箱或其他的MATLAB程序结合使用。 支持自动的M代码生成。 8.1.1.2 图形用户界面和命令行函数 遗传算法工具函数可以通过命令行和图形用户界面来使用遗传算法。直接搜索工具函数也可以通过命令行和图形用户界面来进行访问。图形用户界面可用来快速地定义问题、设置算法选项、对优化问题进行详细定义。 133
遗传算法及其在TSP问题中的应用 摘要：本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。其次，本文在深入分析和研究了遗传算法基本理论与方法的基础上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进，或者将遗传算法与其他方法相结合，以及在编程过程中对算法流程的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些注意事项。最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法（TSPD）、遗传算法在货物配送问题中的应用（ST－TSP）、多旅行商问题（MTSP）等。 引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP）也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机