计算智能与深度学习 课件 4遗传算法-3

第4章遗传算法（续）

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模式定理4.3遗传算法的改进

4.3.1CHC算法

4.3.2自适应遗传算法

4.3.3基于小生境技术的遗传算法4.4遗传算法的应用

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

4.4.2解决多目标优化问题

4.4.3解决组合优化问题

4.4.4遗传算法在过程建模中的应用

4.4.5遗传算法在模式识别中的应用4.3遗传算法的改进

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

4.3遗传算法的改进

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

4.3遗传算法的改进

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

4.3遗传算法的改进

交叉均匀交叉的改进：当两个父个体位值相异的位数为m时，从中随机选取m/2个位置，实行父个体位值的交换；显然，这样的操作对模式具有很强的破坏性。确定一阈值，当个体间距离低于该阈值时，不进行交叉操作。进化收敛的同时，逐渐地减小该阈值。4.3.1CHC算法

4.3遗传算法的改进

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

4.3遗传算法的改进

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

4.3遗传算法的改进

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

；而较低适应度的个体，对应于较高的Pc和Pm

。4.3.2自适应遗传算法

4.3遗传算法的改进

自适应方法

fmax——群体中最大的适应度值；

favg——每代群体的平均适应度值；

f’——要交叉的两个个体中较大的适应度值；

f——要交叉或变异的个体适应度值；4.3.2自适应遗传算法

k1、k2、k3、k4取(0,1)的值4.3遗传算法的改进

自适应方法进一步改进适用于进化后期，不适于进化前期，因为前期的优秀个体有可能是局部最优点；使最大适应度个体的交叉概率和变异概率由0提高到Pc2和Pm2

；采用精英选择策略；4.3.2自适应遗传算法

4.3遗传算法的改进

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

4.3遗传算法的改进

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

4.3遗传算法的改进

选择策略预选择机制、排挤机制、分享机制；预选择（preselection,1970）机制当子个体的适应度超过其父个体适应度时，子个体才可以替代父个体，否则父个体仍保留；有效维持种群多样性，造就小生境进化环境。4.3.3基于小生境技术的遗传算法

4.3遗传算法的改进

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

4.3遗传算法的改进

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

4.3遗传算法的改进

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

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

4.3遗传算法的改进

共享（sharing,1987）机制共享法将个体的适应度降低，即适应度值fi除以一个niche计数mi：在距离为σshare的范围内的个体彼此削减适应度，这些个体将收敛在一个niche内，避免了整个种群的收敛。4.3.3基于小生境技术的遗传算法

4.4遗传算法的应用

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

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

一般方法协同进化遗传算法（CoevolutionaryGeneticAlgorithm,1997）以食物链关系、共生关系等为基础的生物进化现象称为协同进化；一个种群由问题的解组成，另一个种群由约束组成，两个种群协同进化，较好的解应满足更好的约束，较优的约束则被更多的解所违背。4.4.1解决带约束的函数优化问题

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

乘法4.4遗传算法的应用

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

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

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

违反约束程度——随违反约束程度变得严重而增加惩罚压力，静态惩罚；进化迭代次数——随着进化过程的进展而增加惩罚压力，动态惩罚。罚函数法交叉运算：设父个体为x=[x1,x2,…,xn]和y=[y1,y2,…,yn]

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

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

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

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

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

地的单位运费是Cij，

ai表示i

站的供应量，

bj表示j

地的需求量，

xij表示从i

站到j

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

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

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

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

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

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

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

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

4.4遗传算法的应用

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

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

4.4遗传算法的应用

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

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

4.4遗传算法的应用

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

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

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

函数ABCDEFGAMS96.001141.602535.29565.15208.2543527.54GENOCOP24.15205.602571.04480.16204.82119.61误差%297.52455.25-1.4117.701.6736291.224.4遗传算法的应用

多目标优化问题

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

多目标优化的遗传算法

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

4.4遗传算法的应用

多目标优化的遗传算法

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

4.4.2解决多目标优化问题

4.4遗传算法的应用

多目标优化的遗传算法

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

4.4遗传算法的应用

多目标优化的遗传算法

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

4.4遗传算法的应用

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遗传算法的应用

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

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

选择：轮盘赌方法

4.4.3解决组合优化问题

4.4遗传算法的应用

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遗传算法的应用

TSPBenchmark问题变异：随机选择同一个个体的两个点进行交换；初始参数：种群规模100

交叉概率0.8

变异概率0.8

终止代数20004.4.3解决组合优化问题

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

4.4遗传算法的应用

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

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

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

4.4遗传算法的应用

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

w12…w1n…wnm

w1…wm

b1…bm

b

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

4.4遗传算法的应用

优化神经网络的权值适应度函数的计算：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=sums