遗传算法的实现及应用举例

第六节算法实现及应用一、算法实现遗传算法提供了一种求解复杂系统优化问题的通用框架。对于具体问题，可按下述步骤来构造：确定问题编码方案确定适配值函数设计遗传算子（选择、交叉、变异）确定算法参数确定算法终止条件生成初始种群SGA实现①个体适应度评价在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或0，不能是负数。为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值变换为个体的适应度。方法一：对于目标函数是求极大化，方法为：式中，为一个适当地相对比较小的数它可用下面几种方法之一来选取:预先指定的一个较小的数；进化到当前代为止的最小目标函数值；当前代或最近几代群体中的最小目标值。

②比例选择算子比例选择实际上是一种有退还随机选择，也叫做赌盘(RouletteWheel)选择，因为这种选择方式与赌博中的赌盘操作原理非常相似。比例选择算子的具体执行过程是：先计算出群体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操作（即0到1之间的随机数）来确定各个个体被选中的次数。③单点交叉算子单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执行过程如下：对群体中的个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。④基本位变异算子基本位变异算子的具体执行过程为：对个体的每一个基因座，依变异概率指定其为变异点；对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。简单演示问题：求（1）编码：编码长度为5（2）初始群体生成：群体大小设置为4，随机产生四个个体：编码：01101，11000，01000，10011

解码：1324819

适应度：16957664361（3）适应度函数：（4）轮盘赌选择：选择概率个体：01101，11000，01000，10011

适应度：16957664361

选择概率：0.140.490.060.31选择11000和01101交配产生下一代（5）交叉操作：发生交叉的概率取大交叉点位置的选取是随机的（单点交叉）

0110101100

1100011001（6）变异：发生变异的概率取小改变某个字节1100111101（7）新群体的产生：保留上一代最优个体，1个新个体取代旧个体

11101，11000，01000，10011（8）重复上述操作20次，或许就能够得到最优解！

应用实例：TSP问题回顾给定n个城市以及两两城市之间的距离，求解一条从某个城市出发、不重复地遍历所有其它城市并最终又回到起始城市的最短路径。数学描述给定图G=(V,E),V为顶点集,E为边集，确定一条长度最短的Hamilton回路TSP问题问题复杂度:指数增长的！(NP完全问题)12个城市，具有39916800条不同的路径。一条路径对应一个排列！交叉算子传统的交叉算子可能产生无效路径。交叉算子（1）基于位置的交叉把一个父代在向量上的被选元的位置强加到另一个父代。父代1：12345678910父代2：59246110738所选位置：****子代1：19236457810子代2：92345618107交叉算子（2）部分映射交叉利用父代所选段内元的对应定义子代。父代1：26438151079父代2：85110762439子代1：51437621089子代2：72610815439变异算子起双重作用：1、提供和保持群体的多样性；

2、搜索算子的作用。(1)基于位置的变异：随机选择两个元，然后把第二个元放在第一个元之前；(2)基于次序的变异：随机选择两个元，然后交换他们的位置；(3)打乱变异：随机选择一段，然后打乱这段内的次序。编码方案路径表达：对一个旅行最自然的表达一个旅行5—>1—>7—>8—>9—>4—>6—>2—>3的编码就是（517894623）编码空间和解空间一一对应，总量为n!个？其实一些解是相同的，因为（51789|4623）=（4623|51789）二者是同一个解(n-1)!/2应用实例1：TSP适应度函数就取为目标函数的倒数，即路径总长度的倒数初始种群随机生成40个终止条件2000次迭代参数设置自定......p1p2pir选择操作算子:轮盘式选择首先计算每个个体

i被选中的概率然后根据概率的大小将将圆盘分为n个扇形，每个扇形的大小为。选择时转动轮盘，参考点r落到扇形i则选择个体i

。交叉操作算子Davis提出OX算子：通过从一个亲体中挑选一个子序列旅行并保存另一个亲体的城市相对次序来构造后代例如：p1=（123|4567|89）p2=（452|1876|93）首先保持中间部分

o1=（XXX|4567|XX）

o2=（XXX|1876|XX）交叉操作算子然后移走p2中已在o1中的城市4、5、6和7后，得到2—1—8—9—3该序列顺次放在o1中：o1=（218|4567|93）类似地，可以得到另一个后代：o2=（234|1876|59）变异操作算子采用倒置变异：在染色体上随机地选择两点，将两点间的子串反转例如原个体：（123456789）随机选择两点：（12|3456|789）倒置后的个体：（12|6543|789）中国城市TSP的一个参考解应用实例2：函数优化函数优化编码方案采用二进制编码对子变量定义域根据计算精度进行离散化处理，然后根据离散化后待定解的个数选择合适长度的二进制字符串进行编码例如；[0，1]，计算精度0.001,则0，0.001,0.002,…,0.998,0.999,1.000，个数为1001则用长度为10的二进制字符串一次表征所有离散点0000000000，000000001，…，1111110001。适应度函数例如，f(x)=x2-

x5，取Cmax=2,即可得到满足要求的F(x)其它的就类似于TSP的求解了

已知函数

其中，用遗传算法求解y的最大值。

例1多元函数优化问题运行步骤运行步骤运行步骤运行步骤运行步骤运行步骤运行步骤

例2一元函数优化问题问题的提出

一元函数求最大值：问题的提出

用微分法求取

f(x)

的最大值：解有无穷多个：问题的提出

当i为奇数时xi对应局部极大值点，i为偶数时xi对应局部极小值。x19即为区间[-1,2]内的最大值点此时，函数最大值

f(x19)

比f(1.85)=3.85稍大。编码表现型：x

基因型：二进制编码（串长取决于求解精度）

串长与精度之间的关系：若要求求解精度到6位小数，区间长度为2-(-1)＝3，即需将区间分为3/0.000001=3×106等份。所以编码的二进制串长应为22位。产生初始种群

产生的方式：随机产生的结果：长度为22的二进制串产生的数量：种群的大小（规模），如30，50，…111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000……计算适应度

不同的问题有不同的适应度计算方法本例：直接用目标函数作为适应度函数①将某个体转化为[-1,2]区间的实数：

s=<1000101110110101000111>→x=0.637197②计算x的函数值（适应度）：

f(x)=xsin(10πx)+2.0=2.586345计算适应度

二进制与十进制之间的转换：

第一步，将一个二进制串（b21b20…b0）转化为10进制数：第二步，x’对应的区间[-1,2]内的实数：(0000000000000000000000)→-1(1111111111111111111111)→2遗传操作

选择：轮盘赌选择法；交叉：单点交叉；变异：小概率变异模拟结果

设置的参数：

种群大小50；交叉概率0.75；变异概率0.05；最大代数200。

得到的最佳个体：

smax=<1111001100111011111100>;

xmax=1.8506;

f(xmax)=3.8503;模拟结果

进化的过程：世代数自变量适应度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503主程序

%用遗传算法进行简单函数的优化clearbn=22;%个体串长度inn=50;%初始种群大小gnmax=200;%最大代数pc=0.75;%交叉概率pm=0.05;%变异概率Continue…

算法的设计与实现

主程序

%产生初始种群，0,1向量s=round(rand(inn,bn));%计算适应度,返回适应度f和累积概率p[f,p]=objf(s);Continue…主程序

gn=1;whilegn<gnmax+1forj=1:2:inn%选择操作

seln=sel(s,p);%交叉操作

scro=cro(s,seln,pc);

scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);%变异操作

smnew(j,:)=mut(scnew(j,:),pm);smnew(j+1,:)=mut(scnew(j+1,:),pm);endContinue…主程序

s=smnew;%产生了新的种群%计算新种群的适应度

[f,p]=objf(s);

%记录当前代最好和平均的适应度[fmax,nmax]=max(f);fmean=mean(f);ymax(gn)=fmax;ymean(gn)=fmean;Continue…主程序

%记录当前代的最佳个体x=n2to10(s(nmax,:));xx=-1.0+x*3/(power(2,bn)-1);

xmax(gn)=xx;

gn=gn+1endgn=gn-1;Continue…主程序

%绘制曲线subplot(2,1,1);plot(1:gn,[ymax;ymean]);title('历代适应度变化','fonts',10);legend('最大适应度','平均适应度');string1=['最终适应度',num2str(ymax(gn))];gtext(string1);subplot(2,1,2);plot(1:gn,xmax,'r-');legend('自变量');string2=['最终自变量',num2str(xmax(gn))];gtext(string2);End计算适应度和累计概率函数

%计算适应度函数function[f,p]=objf(s);r=size(s);%读取种群大小inn=r(1);%有inn个个体bn=r(2);%个体长度为bnContinue…计算适应度和累计概率函数

fori=1:innx=n2to10(s(i,:));%将二进制转换为十进制xx=-1.0+x*3/(power(2,bn)-1);%转化为[-1,2]区间的实数

f(i)=ft(xx);%计算函数值，即适应度endf=f‘;%行向量转列向量Continue…计算适应度和累计概率函数

%计算选择概率fsum=0;fori=1:inn

fsum=fsum+f(i)*f(i);endfori=1:inn

ps(i)=f(i)*f(i)/fsum;endContinue…计算适应度和累计概率函数

%计算累积概率p(1)=ps(1);fori=2:inn

p(i)=p(i-1)+ps(i);endp=p';Backtomain.m计算目标函数值函数

%目标函数functiony=ft(x);y=x.*sin(10*pi*x)+2;Backtoobjf.m函数n2to10()

Continue…functionx=n2to10(s)x=0;forj=1:22x=x+s(j)*2^(22-j);end

functionx=n2to10(s)x=s(1);forj=1:21x=x*2+s(j+1);end选择操作函数

%“选择”操作functionseln=sel(s,p);inn=size(p,1);%从种群中选择两个个体fori=1:2r=rand;%产生一个随机数

prand=p-r;j=1;whileprand(j)<0j=j+1;end

seln(i)=j;%选中个体的序号endBacktomain.m交叉操作函数

%“交叉”操作functionscro=cro(s,seln,pc);r=size(s);inn=r(1);bn=r(2);pcc=pro(pc);%根据交叉概率决定是否进行交叉操作，1则是，0则否Continue…交叉操作函数

ifpcc==1

chb=round(rand*(bn-2))+1;%在[1,bn-1]范围内随机产生一个交叉位scro(1,:)=[s(seln(1),1:chb)s(seln(2),chb+1:bn)];scro(2,:)=[s(seln(2),1:chb)s(seln(1),chb+1:bn)];elsescro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);endBacktomain.m变异操作函数

%“变异”操作functionsnnew=mut(snew,pm);r=size(snew);bn=r(2);snnew=snew;Continue…变异操作函数

pmm=pro(pm);%根据变异概率决定是否进行变异操作，1则是，0则否ifpmm==1

chb=round(rand*(bn-1))+1;%在[1,bn]范围内随机产生一个变异位

snnew(chb)=abs(snew(chb)-1);endBacktomain.m运行程序

运行程序

运行程序

运行程序

策略调整针对不同实际问题需要调整相应策略同一个实际问题不同的人也有不同的做法编码方案适应度函数设计选择算子交叉算子变异算子初始种群编码方案本质：如何表示解二进制：自变量高维、大范围连续、高精度的时候很难处理冗余问题，离散化后解的个数介于2(n-1)和2n之间D进制,D=3,8,16,…实数编码：无需编码和解码序列编码：例如TSP的路径表达树编码：非定长自适应编码-长度可调节适应度函数是进行自然选择的定量标准直接采用目标函数引入适应值调节线性变换乘幂变换指数变换自适应变换选择算子轮盘赌选择(roulettewheelselection)最基本、最常用的方式，又叫适应度比例选择算子最佳个体保存(elitistmodel)把适应度最高的个体保留到下一代，又叫精英保留排序模型(rank-basedmodel)按适应度函数大小排序，根据事先设定的概率表分配选择概率联赛选择模型(tournamentselectionmodel)随机选择几个进行比较，高的被选，又叫锦标赛模型选择算子期望值模型(expectedvaluemodel)排挤模型(crowdingmodel)浓度控制策略共享机制截断选择交叉算子简单交叉最基本、最常用的方式，双亲互换子串平坦交叉二者之间均匀随机产生算术交叉双亲的凸组合线性交叉1：1，3：1，1：3比较最好的两个留下交叉算子混合交叉离散交叉启发式交叉模拟二进制交叉单峰正态分布交叉单纯形交叉父体中心交叉几何交叉均匀交叉基于模糊联接的交叉变异算子随机变异区间内均匀随机取非一致变异某个区间内随机扰动边界变异取边界值多项式变异高斯变异Cauthy变异自适应变异Muhlenbein变异初始种群对计算结果和计算效率有影响全局性要求初始解尽量分散设计一些生成方法求解TSP的策略调整编码方案二进制编码：交叉和变异很难处理顺序表示：1985年

Grefenstette提出，序表示是指所有城市依次排列构成一个顺序表(orderlist),对于一条旅程,可以依旅行经过顺序处理每个城市,每个城市在顺序表中的顺序就是一个遗传因子的表示,每处理完一个城市,从顺序表中去掉该城市.处理完所有城市以后,将每个城市的遗传因子表示连接起来,就是一条旅程的基因表示.例如,顺序表C=(1,2,3,4,5,6,7,8,9),一条旅程为5-1-7-8-9-4-6-3-2.按照这种编码方法,这条旅程的编码为表l=(5155533321)编码方案路径表示：最自然、直接的表示方法布尔矩阵表示：将一个旅程定义为一个优先权布尔矩阵M,当且仅当城市i排在城市j之前时矩阵元素mij=1.这种方法用n×n矩阵M代表一条旅程,M具有如下三个性质:1)矩阵中1的数目为n(n-1)/2;2)mii=0,i=1,2,.,n;3)若mij=1,且mjk=1,那么mik=1.选择算子轮盘赌选择(roulettewheelselection),最佳个体保存(elitistmodel),期望值模型(expectedvaluemodel),排序模型(rank-basedmodel),联赛选择模型(tournamentselectionmodel)排挤模型(crowdingmodel)浓度控制策略上述机制混合交叉算子依赖于编码方式基于路径表示的顺序交叉基于路径表示的部分匹配交叉贪心交叉法：在一个父个体中选择第一个城市作为子个体的第一个城市,然后在两个父个体中进行比较并找到与已经选择的那个城市相邻且距离较近的城市作为下一个城市扩展到旅程中;如果与该城市相邻的两个城市有一个已经在旅程中,那么选择另外一个,如果两个都在旅程中,那么就选择其它没有被选择的城市.循环交叉边重组交叉变异算子全局意义点位变异：变异仅以一定的概率(通常很小)对串的某些位做值的变异;逆转变异：在串中,随机选择两点,再将这两点内的子串按反序插入到原来的位置中;对换变异：随机选择串中的两点,交换其值(码);插入变异：从串中随机选择1个码,将此码插入随机选择的插入点中间.变异算子贪心对换变异：从一个染色体中随机的选择两个城市(即两个码值),然后交换它们,得到新的染色体,以旅程长度为依据比较交换后的染色体与原来的染色体的大小,保留旅程长度值小的染色体.倒位变异算子：在个体编码串中随机选择两个城市,第一个城市的右城市与第二个城市之间的编码倒序排列,从而产生一个新个体。如，若有父个体P(14

5236),假设随机选择的城市是4,3,那么产生的新个体为Offspring(14

3256).遗传算法的前景性能分析并行遗传算法分类系统图像处理和模式识别优化与调度机器学习智能控制其它……人工生命自动程序设计应用

遗传算法的应用二、算法应用领域遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。

函数优化、组合优化、生产调度、自动控制、机器人学、图象处理、人工生命、遗传编程、机器学习等。函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。组合优化。遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。

TSP问题、背包问题、图划分问题生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。自动控制。遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。如：瓦斯管道控制、导弹控制、机器人控制等

机器人学。机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学自然成为遗传算法的一个重要应用领域。图象处理。图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。

如，模式识别、特征抽取人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。遗传编程。Koza发展了遗传编程的概念，他使用了以LISP语言所表示的编码方法，基于对一种树形结构所进行的遗传操作来自动生成计算机程序。机器学习。基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。规划生产规划、并行机任务分配等；设计通信网络设计、喷气发动机设计等；信号处理滤波器设计等；机器人路径规划等。

遗传算法的应用

函数优化

是遗传算法的经典应用领域;组合优化

实践证明，遗传算法对于组合优化中的NP完全问题非常有效;自动控制

如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等;机器人智能控制

遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等;组合图像处理和模式识别

目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用;

遗传算法的应用

人工生命

基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；遗传程序设计

Koza发展了遗传程序设计的慨念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序;

遗传算法的应用

遗传算法的应用

约束最优化问题（ConstrainedOptimizationProblems）的表述

1解决带约束的函数优化问题

解决途径将有约束问题转化为无约束问题（罚函数法，penaltyfunctionmethod），历史较长；改进无约束问题的方法，使之能用于有约束的情况（梯度投影算法），发展较晚。遗传算法解决有约束问题的关键是对约束条件的处理（直接按无约束问题处理是行不通的：随机生成的初始点中可能有大量不可行解；遗传算子作用于可行解后可能产生不可行解）。

遗传算法的应用

1解决带约束的函数优化问题

一般方法罚函数法

将罚函数包含到适应度评价中：关键是如何设计罚函数，需要谨慎地在过轻或过重惩罚之间找到平衡，针对不同问题设计罚函数。

遗传算法的应用

1解决带约束的函数优化问题

一般方法协同进化遗传算法（CoevolutionaryGeneticAlgorithm,1997）

以食物链关系、共生关系等为基础的生物进化现象称为协同进化；一个种群由问题的解组成，另一个种群由约束组成，两个种群协同进化，较好的解应满足更好的约束，较优的约束则被更多的解所违背。

遗传算法的应用

1解决带约束的函数优化问题

罚函数法评价函数的构造：

加法

乘法

遗传算法的应用

1解决带约束的函数优化问题

罚函数法罚函数分类：

定量惩罚——简单约束问题

变量惩罚——复杂约束问题，包含两个部分：可变惩罚率和违反约束的惩罚量。违反约束程度——随违反约束程度变得严重而增加惩罚压力，静态惩罚；进化迭代次数——随着进化过程的进展而增加惩罚压力，动态惩罚。

遗传算法的应用

1解决带约束的函数优化问题

罚函数法交叉运算：设父个体为x=[x1,x2,…,xn]和y=[y1,y2,…,yn]

简单交叉单点算术交叉整体算术交叉基于方向的交叉：x’=r(x-y)+x，r为(0,1)之间的随机数，并假设f(x)≥f(y)。

遗传算法的应用

1解决带约束的函数优化问题

罚函数法变异运算：设父个体为x=[x1,x2,…,xn]

均匀变异非均匀变异（动态变异）边界变异：x’=[x1,x2,…,xk’,…,xn]，xk’等概率地取用变异量的上界或下界，当最优解在可行域边界上或附近时，边界变异算子较为有效；基于方向的变异：x’=x+r•d，d为目标函数的近似梯度。

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

线性约束优化问题一般形式为：

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

线性约束优化问题：

目标函数可以是线性函数或非线性函数；

思路——消除可能的变量，消除等式约束设计罚函数设计特别的遗传操作

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法例：7×7运输规划问题将物品由7个起运站运到7个目的地；已知由i站运到j

地的单位运费是Cij，

ai表示i

站的供应量，

bj表示j

地的需求量，

xij表示从i

站到j

地的运量。（i,j=1,2,…,7）

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题

对于非线性目标函数的构造，可以选用以下几种测试函数：（1）函数A

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题

（2）函数B

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法例：7×7运输规划问题

（3）函数C

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题

（4）函数D

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题

（5）函数E

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题

（6）函数F

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题

目标函数为罚函数为其中，k=1，P=1/14，f为第t代群体的平均适应度，T为最大运行代数，dij为约束的违反度。

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法例：7×7运输规划问题对于约束，个体染色体表示为（v11,…,v77），其约束违反度定义为：

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题

费用参数表对于函数A，取S＝2，对于函数B、E和F，取S＝5。cij27282520202020200215062937710002021017546710004820501706098672523625460027100038269367982704742257710006710004703526100048253842350

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题

消除多余变量：可以消除13个变量，x11,x12,…,x17,x21,x31,x41,x51,x61,x71，其余36个变量设定为y1,y2,…,y36

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题

将原规划问题转化为：

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题

采用的参数：种群大小40，均匀变异概率0.08，边界变异概率0.03，非均匀变异概率0.07，简单交叉概率0.10，单一算术概率0.10，整体算术概率0.10，运行代数8000。

遗传算法的应用

1解决带约束的函数优化问题

遗传算法的应用

1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法

例：7×7运输规划问题结果比较：GENOCOP（约束优化的遗传算法）GAMS（拟牛顿法非线性最优化算法）函数ABCDEFGAMS96.001141.602535.29565.15208.2543527.54GENOCOP24.15205.602571.04480.16204.82119.61误差%297.52455.25-1.4117.701.6736291.22多目标优化问题

解的存在性怎样求解

遗传算法的应用

2

解决多目标优化问题

Pareto最优性理论

在一个有k个目标函数最小化的问题中，称决策向量x*∈F是Pareto最优的，当不存在另外一个决策向量x∈F同时满足

遗传算法的应用

2

解决多目标优化问题

Pareto最优性理论

多目标优化问题的解通常是多个满意解的集合，称为Pareto最优集，解集中的决策向量称为非劣的。

遗传算法的应用

2

解决多目标优化问题

传统方法

多目标加权法层次优化法目标规划法等特点：将多目标函数转化为单目标函数处理，只能得到特定条件下的某一Pareto解。

遗传算法的应用

2

解决多目标优化问题

多目标优化的遗传算法

优势：

并行地处理一组可能的解；不局限于Pareto前沿的形状和连续性，易于处理不连续的、凹形的Pareto前沿。目前基于Pareto的遗传算法占据主要地位。

遗传算法的应用

2

解决多目标优化问题

多目标优化的遗传算法

聚合函数法：把多个目标函数表示成一个目标函数作为遗传算法的适应函数（聚合）；无需改动遗传算法，但权值难以确定；

改进：自适应权值。

遗传算法的应用

2

解决多目标优化问题

多目标优化的遗传算法

向量评价遗传算法（非Pareto法）：

子种群的产生根据每一个目标函数分别进行选择。

遗传算法的应用

2

解决多目标优化问题

多目标优化的遗传算法

基于排序的多目标遗传算法：

根据“Pareto最优个体”的概念对所有个体进行排序，依据这个排列次序来进行进化过程中的选择运算，从而使得排在前面的Pareto最优个体将有更多的机会遗传到下一代群体。

遗传算法的应用

2

解决多目标优化问题

多目标优化的遗传算法小生境Pareto遗传算法：

为了保证寻优过程不收敛于可行域的某一局部，使种群向均匀分布于Pareto前沿面的方向进化，通过共享函数定义一小生境加以实现。

遗传算法的应用

2

解决多目标优化问题

TSPBenchmark问题

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450

遗传算法的应用

3

解决组合优化问题

TSPBenchmark问题

编码：直接采用解的表示形式,30位（30个城市）长，每位代表所经过的城市序号（无重复）；

适应度函数：个体所代表的路径距离的倒数；

选择：轮盘赌方法

遗传算法的应用

3

解决组合优化问题

TSPBenchmark问题

交叉：有序交叉法

1）随机选取两个交叉点；

2）两个父个体交换中间部分；

3）替换交换后重复的城市序号。X1:98|45671|320X2:87|14032|965X1’:98|14032|320X2’:87|45671|965X1’:98|14032|756X2’:83|45671|902

遗传算法的应用

3

解决组合优化问题

TSPBenchmark问题

变异：随机选择同一个个体的两个点进行交换；

初始参数：种群规模100

交叉概率0.8

变异概率0.8

终止代数2000

遗传算法的应用

3

解决组合优化问题

TSPBenchmark问题运行结果：

遗传算法的应用

3

解决组合优化问题

TSPBenchmark问题运行结果：

遗传算法的应用

3

解决组合优化问题

TSPBenchmark问题运行结果：

遗传算法的应用

3

解决组合优化问题

TSPBenchmark问题运行结果：

遗传算法的应用

3

解决组合优化问题

TSPBenchmark问题运行结果：

遗传算法的应用

3

解决组合优化问题

TSPBenchmark问题运行结果：

遗传算法的应用

3

解决组合优化问题

TSPBenchmark问题运行结果：

遗传算法的应用

3

解决组合优化问题

优化神经网络的权值神经网络建模：x1输出层隐藏层输入层x2yxn…………

遗传算法的应用

4

在过程建模中的应用

优化神经网络的权值

例：聚丙烯生产过程熔融指数的软测量模型输入变量：加氢量、釜压、升温时间、反应时间、搅拌电流；输出变量：熔融指数；样本数据：240组现场数据；

遗传算法的应用

4

在过程建模中的应用

优化神经网络