遗传算法3优秀课件

第四章遗传算法（续）

智能优化计算

2013年教学重点理解改进的遗传算法掌握遗传算法解决简单优化问题掌握遗传算解决简单的STP问题教学难点遗传算解决简单的STP问题4.1遗传算法简介

4.1.1遗传算法的产生与发展

4.1.2生物进化理论和遗传学的基本知识

4.1.3遗传算法的思路与特点

4.1.4遗传算法的基本操作

4.1.5遗传算法的应用4.2基本遗传算法

4.2.1简单函数优化的实例

4.2.2遗传基因型

4.2.3适应度函数及其尺度变换

4.2.4遗传操作——选择

4.2.5遗传操作——交叉/基因重组

4.2.6遗传操作——变异

4.2.7算法的设计与实现

4.2.8模式定理智能优化计算数学与统计学院

2013年4.3遗传算法的改进

智能优化计算数学与统计学院

2013年改进的途径改变遗传算法的组成成分；采用混合遗传算法；采用动态自适应技术；采用非标准的遗传操作算子；采用并行遗传算法等。

4.3遗传算法的改进

智能优化计算数学与统计学院

2013年改进思路1991年Eshelman提出的一种改进遗传算法；C：跨世代精英选择（Crossgenerationalelitistselection）策略；H：异物种重组（Heterogeneousrecombination）；C：大变异（Cataclysmicmutation）。4.3.1CHC算法

4.3遗传算法的改进

智能优化计算数学与统计学院

2013年选择上一代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体；即使交叉操作产生较劣个体偏多，由于原种群大多数个体残留，不会引起个体的评价值降低；可以更好地保持遗传多样性；排序方法，克服比例适应度计算的尺度问题。4.3.1CHC算法

4.3遗传算法的改进

智能优化计算数学与统计学院

2013年变异在进化前期不采取变异操作，当种群进化到一定收敛时期，从最优个体中选择一部分个体进行初始化；初始化：选择一定比例（扩散率，一般0.35）的基因座，随机地决定它们的位值。4.3.1CHC算法

4.3遗传算法的改进

智能优化计算数学与统计学院

2013年参数分析交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键，直接影响算法的收敛性；Pc越大，新个体产生的速度就越快，但过大会使优秀个体的结构很快被破坏；Pc过小，搜索过程缓慢，以至停止不前；Pm过小，不易产生新个体结构，Pm过大，变成纯粹的随机搜索；4.3.2自适应遗传算法

4.3遗传算法的改进

智能优化计算数学与统计学院

2013年自适应策略Srinvivas等提出一种自适应遗传算法，Pc和Pm能够随适应度自动改变：当种群各个体适应度趋于一致或趋于局部最优时，使Pc和Pm增加；而当群体适应度比较分散时，使Pc和Pm减少；对于适应度较高的个体，对应于较低的Pc和Pm；而较低适应度的个体，对应于较高的Pc和Pm。4.3.2自适应遗传算法

4.3遗传算法的改进

智能优化计算数学与统计学院

2013年自适应方法进一步改进适用于进化后期，不适于进化前期，因为前期的优秀个体有可能是局部最优点；使最大适应度个体的交叉概率和变异概率由0提高到Pc2和Pm2；采用精英选择策略；4.3.2自适应遗传算法

4.3遗传算法的改进

智能优化计算数学与统计学院

2013年自适应方法进一步改进4.3.2自适应遗传算法

4.3遗传算法的改进

智能优化计算数学与统计学院

2013年小生境概念小生境（niche）：生物学中，特定环境中的一种组织功能；在SGA中，容易“近亲繁殖”；NGA（NicheGenericAlgorithm），将每一代个体划分为若干类，每类选出优秀个体组成一个种群；优势：保持解的多样性，提高全局搜索能力，适合复杂多峰函数的优化。4.3.3基于小生境技术的遗传算法

4.3遗传算法的改进

智能优化计算数学与统计学院

2013年排挤（crowding,1975）机制设置排挤因子CF（CF=2或3），随机选取1/CF个个体组成排挤成员，排挤与其相似（用距离来度量）的个体；个体之间的相似性可用个体编码串之间的海明距离来度量。4.3.3基于小生境技术的遗传算法

4.3遗传算法的改进

智能优化计算数学与统计学院

2013年共享（sharing,1987）机制通过个体之间的相似性程度的共享函数来调整各个体的适应度；共享函数的目的：将搜索空间的多个峰值在地理上区分开来，每一个峰值处接受一定比例数目的个体，比例数目与峰值高度有关；4.3.3基于小生境技术的遗传算法

4.3遗传算法的改进

智能优化计算数学与统计学院

2013年共享（sharing,1987）机制共享函数的值越大，表明个体之间越相似，记为Sh(dij)，dij为两个个体i和j之间的距离；

σshare是niche的半径，由使用者给定。4.3.3基于小生境技术的遗传算法

4.4遗传算法的应用

智能优化计算数学与统计学院

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

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

4.4遗传算法的应用

智能优化计算数学与统计学院

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

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年一般方法罚函数法将罚函数包含到适应度评价中：关键是如何设计罚函数，需要谨慎地在过轻或过重惩罚之间找到平衡，针对不同问题设计罚函数。4.4.1解决带约束的函数优化问题

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

乘法4.4遗传算法的应用

智能优化计算数学与统计学院

2013年4.4.1解决带约束的函数优化问题

罚函数法罚函数分类：定量惩罚——简单约束问题变量惩罚——复杂约束问题，包含两个部分：可变惩罚率和违反约束的惩罚量。4.4遗传算法的应用

智能优化计算数学与统计学院

2013年4.4.1解决带约束的函数优化问题

违反约束程度——随违反约束程度变得严重而增加惩罚压力，静态惩罚；进化迭代次数——随着进化过程的进展而增加惩罚压力，动态惩罚。4.4遗传算法的应用

智能优化计算数学与统计学院

2013年求解线性约束优化问题的遗传算法线性约束优化问题一般形式为：4.4.1解决带约束的函数优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年求解线性约束优化问题的遗传算法线性约束优化问题：目标函数可以是线性函数或非线性函数；思路——消除可能的变量，消除等式约束设计罚函数设计特别的遗传操作4.4.1解决带约束的函数优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

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

ai表示i站的供应量，

bj表示j地的需求量，

xij表示从i站到j地的运量。（i,j=1,2,…,7）4.4.1解决带约束的函数优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年求解线性约束优化问题的遗传算法例：7×7运输规划问题4.4.1解决带约束的函数优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年求解线性约束优化问题的遗传算法例：7×7运输规划问题对于非线性目标函数的构造，可以选用以下几种测试函数：（1）函数A4.4.1解决带约束的函数优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年求解线性约束优化问题的遗传算法例：7×7运输规划问题（2）函数B4.4.1解决带约束的函数优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年求解线性约束优化问题的遗传算法例：7×7运输规划问题（3）函数C4.4.1解决带约束的函数优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年求解线性约束优化问题的遗传算法例：7×7运输规划问题（4）函数D4.4.1解决带约束的函数优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年求解线性约束优化问题的遗传算法例：7×7运输规划问题（5）函数E4.4.1解决带约束的函数优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年求解线性约束优化问题的遗传算法例：7×7运输规划问题（6）函数F4.4.1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法例：7×7运输规划问题目标函数为罚函数为其中，k=1，P=1/14，f为第t代群体的平均适应度，T为最大运行代数，dij为约束的违反度。4.4遗传算法的应用

智能优化计算数学与统计学院

2013年4.4.1解决带约束的函数优化问题

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

智能优化计算数学与统计学院

2013年

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

求解线性约束优化问题的遗传算法例：7×7运输规划问题费用参数表对于函数A，取S＝2，对于函数B、E和F，取S＝5。4.4遗传算法的应用

智能优化计算数学与统计学院

2013年4.4.1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法例：7×7运输规划问题消除多余变量：可以消除13个变量，x11,x12,…,x17,x21,x31,x41,x51,x61,x71，其余36个变量设定为y1,y2,…,y36

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

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

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

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年4.4.1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法例：7×7运输规划问题采用的参数：种群大小40，均匀变异概率0.08，边界变异概率0.03，非均匀变异概率0.07，简单交叉概率0.10，单一算术概率0.10，整体算术概率0.10，运行代数8000。

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年4.4.1解决带约束的函数优化问题

求解线性约束优化问题的遗传算法例：7×7运输规划问题结果比较：GENOCOP（约束优化的遗传算法）GAMS（拟牛顿法非线性最优化算法）4.4遗传算法的应用

智能优化计算数学与统计学院

2013年4.4.1解决带约束的函数优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年多目标优化问题

解的存在性怎样求解4.4.2解决多目标优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

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

4.4遗传算法的应用

智能优化计算数学与统计学院

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

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

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

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年多目标优化的遗传算法优势：并行地处理一组可能的解；不局限于Pareto前沿的形状和连续性，易于处理不连续的、凹形的Pareto前沿。目前基于Pareto的遗传算法占据主要地位。4.4.2解决多目标优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年多目标优化的遗传算法

聚合函数法：把多个目标函数表示成一个目标函数作为遗传算法的适应函数（聚合）；无需改动遗传算法，但权值难以确定；改进：自适应权值。4.4.2解决多目标优化问题

数学与统计学院

2013年4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

多目标优化的遗传算法

向量评价遗传算法（非Pareto法）：子种群的产生根据每一个目标函数分别进行选择。

4.4.2解决多目标优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

多目标优化的遗传算法

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

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

多目标优化的遗传算法

小生境Pareto遗传算法：为了保证寻优过程不收敛于可行域的某一局部，使种群向均匀分布于Pareto前沿面的方向进化，通过共享函数定义一小生境加以实现。4.4.2解决多目标优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

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;4504.4.3解决组合优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

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

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

选择：轮盘赌方法

4.4.3解决组合优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

TSPBenchmark问题交叉：有序交叉法1）随机选取两个交叉点；2）两个父个体交换中间部分；3）替换交换后重复的城市序号。4.4.3解决组合优化问题

X1:98|45671|320X2:87|14032|965X1’:98|14032|320X2’:87|45671|965X1’:98|14032|756X2’:83|45671|9024.4遗传算法的应用

智能优化计算数学与统计学院

2013年

TSPBenchmark问题变异：随机选择同一个个体的两个点进行交换；初始参数：种群规模100交叉概率0.8变异概率0.8终止代数20004.4.3解决组合优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年TSPBenchmark问题运行结果：4.4.3解决组合优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

TSPBenchmark问题运行结果：4.4.3解决组合优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年TSPBenchmark问题运行结果：4.4.3解决组合优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

TSPBenchmark问题运行结果：4.4.3解决组合优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年TSPBenchmark问题运行结果：4.4.3解决组合优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年TSPBenchmark问题运行结果：4.4.3解决组合优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

TSPBenchmark问题运行结果：4.4.3解决组合优化问题

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

优化神经网络的权值神经网络建模：4.4.4遗传算法在过程建模中的应用

x1输出层隐藏层输入层x2yxn…………4.4遗传算法的应用

智能优化计算数学与统计学院

2013年优化神经网络的权值例：聚丙烯生产过程熔融指数的软测量模型输入变量：加氢量、釜压、升温时间、反应时间、搅拌电流；输出变量：熔融指数；样本数据：240组现场数据；4.4.4遗传算法在过程建模中的应用

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年优化神经网络的权值个体的表示：w11

w12…w1n…wnm

w1…wm

b1…bm

b

适应度的设计：样本数据与神经网络预测数据的误差和的倒数；4.4.4遗传算法在过程建模中的应用

4.4遗传算法的应用

智能优化计算数学与统计学院

2013年

优化神经网络的权值适应度函数的计算：loaddatat.txt;对样本数据归一化；S1=6;fori=1:S1forj=1:5w1(i,j)=sol((i-1)*5+j);endw2(i)=sol(5*S1+i);b1(i)=sol(6*S1+i);end4.4.4遗传算法在过程建模中的应用

b1=b1';b2=sol(7*S1+1);

A=simuff(P,w1,b1,'logsig',w2,b2,'logsig');mse1=sumsqr(A-T)/s;eval=1/(1+mse1/0.0001);4