第四章--遗传算法3课件.ppt

1、 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w改进的途径改进的途径改变遗传算法的组成成分；改变遗传算法的组成成分；采用混合遗传算法；采用混合遗传算法；采用动态自适应技术；采用动态自适应技术；采用非标准的遗传操作算子；采用非标准的遗传操作算子；采用并行遗传算法等。采用

2、并行遗传算法等。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w改进思路改进思路1991年年Eshelman提出的一种改进遗传算法；提出的一种改进遗传算法；C：跨世代精英选择（：跨世代精英选择（Cross generational elitist selection）策略；）策略；H：异物种重组（：异物种重组（Heterogeneous recombination）；）；C：大变异（：大变异（Cataclysmic mutation）。）。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w选择选择上一

3、代种群与通过新的交叉方法产生的个体群混合上一代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体；起来，从中按一定概率选择较优的个体；即使交叉操作产生较劣个体偏多，由于原种群大多即使交叉操作产生较劣个体偏多，由于原种群大多数个体残留，不会引起个体的评价值降低；数个体残留，不会引起个体的评价值降低；可以更好地保持遗传多样性；可以更好地保持遗传多样性；排序方法，克服比例适应度计算的尺度问题。排序方法，克服比例适应度计算的尺度问题。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w交叉交叉均匀交叉的改进：当两个父个体位值相异的位数为

4、均匀交叉的改进：当两个父个体位值相异的位数为m时，从中随机选取时，从中随机选取m/2个位置，实行父个体位值个位置，实行父个体位值的交换；的交换；确定一阈值，当个体间距离低于该阈值时，不进行确定一阈值，当个体间距离低于该阈值时，不进行交叉操作。进化收敛的同时，逐渐地减小该阈值。交叉操作。进化收敛的同时，逐渐地减小该阈值。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w变异变异在进化前期不采取变异操作，当种群进化到一定收在进化前期不采取变异操作，当种群进化到一定收敛时期，从最优个体中选择一部分个体进行初始化；敛时期，从最优个体中选择一部分个体进行初始

5、化；初始化：选择一定比例（扩散率，一般初始化：选择一定比例（扩散率，一般0.35）的基）的基因座，随机地决定它们的位值。因座，随机地决定它们的位值。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w参数分析参数分析交叉概率交叉概率Pc和变异概率和变异概率Pm的选择是影响遗传算法行的选择是影响遗传算法行为和性能的关键，直接影响算法的收敛性；为和性能的关键，直接影响算法的收敛性；Pc越大，新个体产生的速度就越快，但过大会使优越大，新个体产生的速度就越快，但过大会使优秀个体的结构很快被破坏；秀个体的结构很快被破坏；Pc过小，搜索过程缓过小，搜索过程缓慢，

6、以至停止不前；慢，以至停止不前；Pm过小，不易产生新个体结构，过小，不易产生新个体结构，Pm过大，变成纯过大，变成纯粹的随机搜索；粹的随机搜索；华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w自适应策略自适应策略Srinvivas等提出一种自适应遗传算法，等提出一种自适应遗传算法，Pc和和Pm能够能够随适应度自动改变：随适应度自动改变：当种群各个体适应度趋于一致或趋于局部最优时，当种群各个体适应度趋于一致或趋于局部最优时，使使Pc和和Pm增加；而当群体适应度比较分散时，使增加；而当群体适应度比较分散时，使Pc和和Pm减少；减少；对于适应度较高的个

7、体，对应于较低的对于适应度较高的个体，对应于较低的Pc和和Pm；而较低适应度的个体，对应于较高的而较低适应度的个体，对应于较高的Pc和和Pm。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w自适应方法自适应方法 fmax群体中最大的适应度值；群体中最大的适应度值；favg每代群体的平均适应度值；每代群体的平均适应度值；f要交叉的两个个体中较大的适应度值；要交叉的两个个体中较大的适应度值；f要交叉或变异的个体适应度值；要交叉或变异的个体适应度值；avgavgavgmavgavgavgcffkffffffkPffkffffffkP ,)(,)(4ma

8、xmax32maxmax1k1、k2、k3、k4取取(0,1)的值的值 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w自适应方法进一步改进自适应方法进一步改进适用于进化后期，不适于进化前期，因为前期的优适用于进化后期，不适于进化前期，因为前期的优秀个体有可能是局部最优点；秀个体有可能是局部最优点；使最大适应度个体的交叉概率和变异概率由使最大适应度个体的交叉概率和变异概率由0提高提高到到Pc2和和Pm2；采用精英选择策略；采用精英选择策略；华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w自适应方法进

9、一步改进自适应方法进一步改进 001.0 ,1.0 ,6.0 ,9.0 ,)()(,)(21211maxmax32111max211mmccavgmavgavgmmmmavgcavgavgavgccccPPPPffPffffffkPPPPffPffffffPPPP 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w小生境概念小生境概念小生境（小生境（niche）：生物学中，特定环境中的一种）：生物学中，特定环境中的一种组织功能；组织功能；在在SGA中，容易中，容易“近亲繁殖近亲繁殖”；NGA（Niche Generic Algorithm），将每一

10、代个体），将每一代个体划分为若干类，每类选出优秀个体组成一个种群；划分为若干类，每类选出优秀个体组成一个种群；优势：保持解的多样性，提高全局搜索能力，适合优势：保持解的多样性，提高全局搜索能力，适合复杂多峰函数的优化。复杂多峰函数的优化。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w选择策略选择策略预选择机制、排挤机制、分享机制；预选择机制、排挤机制、分享机制；w预选择（预选择（preselection,1970）机制）机制当子个体的适应度超过其父个体适应度时，子个体当子个体的适应度超过其父个体适应度时，子个体才可以替代父个体，否则父个体仍保留

11、；才可以替代父个体，否则父个体仍保留；有效维持种群多样性，造就小生境进化环境。有效维持种群多样性，造就小生境进化环境。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w排挤（排挤（crowding,1975）机制）机制设置排挤因子设置排挤因子CF（CF=2或或3），随机选取），随机选取1/CF个个个体组成排挤成员，排挤与其相似（用距离来度量）个体组成排挤成员，排挤与其相似（用距离来度量）的个体；的个体；个体之间的相似性可用个体编码串之间的海明距离个体之间的相似性可用个体编码串之间的海明距离来度量。来度量。华东理工大学自动化系华东理工大学自动化系华东

12、理工大学自动化系 200720072007年年年 w共享（共享（sharing,1987）机制）机制通过个体之间的相似性程度的共享函数来调整各个通过个体之间的相似性程度的共享函数来调整各个体的适应度；体的适应度；共享函数的目的：将搜索空间的多个峰值在地理上共享函数的目的：将搜索空间的多个峰值在地理上区分开来，每一个峰值处接受一定比例数目的个体，区分开来，每一个峰值处接受一定比例数目的个体，比例数目与峰值高度有关；比例数目与峰值高度有关；华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w共享（共享（sharing,1987）机制）机制共享函数的值越大

13、，表明个体之间越相似，记为共享函数的值越大，表明个体之间越相似，记为Sh(dij)，dij为两个个体为两个个体i和和j之间的距离；之间的距离；share是是niche的半径，由使用者给定。的半径，由使用者给定。shareshareshareddddSh ,0 ,1)(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w共享（共享（sharing,1987）机制）机制共享法将个体的适应度降低，即适应度值共享法将个体的适应度降低，即适应度值fi除以一除以一个个niche计数计数mi：在距离为在距离为share的范围内的个体彼此削减适应度，这的范围内的个体

14、彼此削减适应度，这些个体将收敛在一个些个体将收敛在一个niche内，避免了整个种群的内，避免了整个种群的收敛。收敛。PopjijidShm)(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w约束最优化约束最优化问题（问题（Constrained Optimization Problems）的表述）的表述 ,1 ,0)(,1 ,0)()(iiijiuxlnjxhmixgxfMinimize 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w解决途径解决途径将有约束问题转化为无约束问题（罚函数法，将有约束

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

16、学自动化系华东理工大学自动化系 200720072007年年年 w一般方法一般方法罚函数法罚函数法 将罚函数包含到适应度评价中：将罚函数包含到适应度评价中：关键是如何设计罚函数，需要谨慎地在过轻或过重关键是如何设计罚函数，需要谨慎地在过轻或过重惩罚之间找到平衡，针对不同问题设计罚函数。惩罚之间找到平衡，针对不同问题设计罚函数。为罚函数尺度系数。，满足罚函数0 ,0 ,0)()()()(rXxXxxPxPxrPxf 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w一般方法一般方法协同进化遗传算法（协同进化遗传算法（Coevolutionary Ge

17、netic Algorithm,1997）以食物链关系、共生关系等为基础的生物进化现象以食物链关系、共生关系等为基础的生物进化现象称为协同进化；称为协同进化；一个种群由问题的解组成，另一个种群由约束组成，一个种群由问题的解组成，另一个种群由约束组成，两个种群协同进化，较好的解应满足更好的约束，两个种群协同进化，较好的解应满足更好的约束，较优的约束则被更多的解所违背。较优的约束则被更多的解所违背。w罚函数法罚函数法评价函数的构造：评价函数的构造：加法加法 乘法乘法 XxXxxPxrPxf ,0 ,0)()()(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007

18、年年年 XxXxxPxPxf ,1 ,1)()()(w罚函数法罚函数法罚函数分类：罚函数分类：定量惩罚定量惩罚简单约束问题简单约束问题 变量惩罚变量惩罚复杂约束问题，包含两个部分：复杂约束问题，包含两个部分：可变可变惩罚率惩罚率和违反约束的惩罚量。和违反约束的惩罚量。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 违反约束程度违反约束程度随违反约束程度变得严重而增随违反约束程度变得严重而增加惩罚压力，静态惩罚；加惩罚压力，静态惩罚；进化迭代次数进化迭代次数随着进化过程的进展而增加惩随着进化过程的进展而增加惩罚压力，动态惩罚。罚压力，动态惩罚。w罚函

19、数法罚函数法交叉运算：设父个体为交叉运算：设父个体为x=x1,x2,xn和和y=y1,y2,yn 简单交叉简单交叉 单点算术交叉单点算术交叉 整体算术交叉整体算术交叉 基于方向的交叉：基于方向的交叉：x=r(x-y)+x，r为为(0,1)之间的随机之间的随机数，并假设数，并假设f(x)f(y)。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w罚函数法罚函数法变异运算：设父个体为变异运算：设父个体为x=x1,x2,xn 均匀变异均匀变异 非均匀变异（动态变异）非均匀变异（动态变异）边界变异：边界变异：x=x1,x2,xk,xn，xk等概率地取等概率

20、地取用变异量的上界或下界，当最优解在可行域边界上用变异量的上界或下界，当最优解在可行域边界上或附近时，边界变异算子较为有效；或附近时，边界变异算子较为有效；基于方向的变异：基于方向的变异：x=x+rd，d为目标函数的近似为目标函数的近似梯度。梯度。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 线性约束优化问题一般形式为：线性约束优化问题一般形式为：niuxldxcxcdxcxcbxaxabx

21、axatosubjectxxfMinimizeiiilnlnlnnmnmnmnnn,1 ,),(111111111111111uxldCxbxx )(tosubjectfMinimize 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 线性约束优化问题：线性约束优化问题：目标函数可以是线性函数或非线性函数；目标函数可以是线性函数或非线性函数；思路思路消除可能的变量，消除等式约束消除可能的变量，消除等式约束 设计罚函数设计罚函数 设计特别的遗传操作设计特别的遗传操作 华东理工大学自动化系

22、华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 将物品由将物品由7个起运站运到个起运站运到7个目的地；个目的地；已知由已知由 i 站运到站运到 j 地的单位运费是地的单位运费是Cij，ai表示表示 i 站的供应量，站的供应量，bj表示表示 j 地的需求量，地的需求量，xij表示从表示从 i 站到站到 j 地的运量。地的运量。（i,j=1,2,7）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w求解线性约束优化问题的遗传算

23、法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 20202020252827 )(77767574737271676665646362615756555453525147464544434241373635343332312726252423222117161514131211xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtosubjectxfMinimizeij7,2,1 ,7,2,1 ,02625262320202077675747372717766656463626167565554535251574645444

24、342414736353433323137262524232221271615141312111jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxij 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 对于非线性目标函数的构造，可以选用以下几种测对于非线性目标函数的构造，可以选用以下几种测试函数：试函数：（1）函数）函数A ijijijijijijijijijijijijxSSxSSxSSxSSx

25、SSxcccccxA554433220 54320)(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 （2）函数）函数B ijijijijijijijijijxSSxSSxSSxccSxcxB220 )21()(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 （3）函数）函数C 2)(ijijijxcx

26、C 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 （4）函数）函数D ijijijxcxD)(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 （5）函数）函数E 222)47(11)49(11)2(11)(SxSxSxcxEijijijijij 华东理工大学自动化系华东理工大学自动化系华东理工大学自动

27、化系 200720072007年年年 w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 （6）函数）函数F )1)45(sin()(SxxcxFijijijijw求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 目标函数为目标函数为 罚函数为罚函数为 其中，其中，k=1，P=1/14，f为第为第t代群体的平均适应度，代群体的平均适应度，T为最大运行代数，为最大运行代数，dij为约束的违反度。为约束的违反度。Pxfjiij,)(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200

28、720072007年年年 7171ijijPdfTtkPw求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 对于约束对于约束 ，个体染色体表示，个体染色体表示 为（为（v11,v77），其约束违反度定义为：），其约束违反度定义为：7,2,1 ,WvalxijWjiij华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 ijWjiijijvalvd,w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 费用参数表费用参数表对于函数对于函数A，取，取S2，对于

29、函数，对于函数B、E和和F，取，取S5。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 cij27282520202020200215062937710002021017546710004820501706098672523625460027100038269367982704742257710006710004703526100048253842350w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 消除多余变量：消除多余变量：可以消除可以消除13个变量，个变量，x11,x12,x17,x21,

30、x31,x41,x51,x61,x71，其余，其余36个变量设定为个变量设定为y1,y2,y36 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 将原规划问题转化为：将原规划问题转化为：华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 25191373631125191373631302311313021204011393200yyyyyyyyyyyyyyyyyiiiiiiiiw求解线性约束优化问题的遗传

31、算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 采用的参数：种群大小采用的参数：种群大小40，均匀变异概率，均匀变异概率0.08，边，边界变异概率界变异概率0.03，非均匀变异概率，非均匀变异概率0.07，简单交叉，简单交叉概率概率0.10，单一算术概率，单一算术概率0.10，整体算术概率，整体算术概率0.10，运行代数运行代数8000。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w求解线性约束优化问题的遗传算法求解线性约束优化问题的遗传算法 例：例：77运输规划问题运输规划问题 结果比较：结果比较：GENOCOP（约

32、束优化的遗传算法）（约束优化的遗传算法）GAMS（拟牛顿法非线性最优化算法）（拟牛顿法非线性最优化算法）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 函数函数ABCDEFGAMS96.001141.602535.29565.15208.2543527.54GENOCOP24.15205.602571.04480.16204.82119.61误差误差%297.52455.25-1.4117.701.6736291.22 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w多目标优化问题多目标优化问题 解的

33、存在性解的存在性怎样求解怎样求解 ,1 ,0)(,1 ,0)()(,),(),(21iiijikuxlnjxhmixgxfxfxfMinimize 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wPareto最优性最优性理论理论 在一个有在一个有k个目标函数最小化的问题中，称决策向个目标函数最小化的问题中，称决策向量量x*F是是Pareto最优的，当不存在另外一个决策最优的，当不存在另外一个决策向量向量xF同时满足同时满足 ,2,1),()(,2,1),()(*kjxfxfkixfxfjjii 华东理工大学自动化系华东理工大学自动化系华东理工大学

34、自动化系 200720072007年年年 wPareto最优性最优性理论理论 多目标优化问题的解通常是多个满意解的集合，称多目标优化问题的解通常是多个满意解的集合，称为为Pareto最优集，解集中的决策向量称为非劣的。最优集，解集中的决策向量称为非劣的。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w传统方法传统方法 多目标加权法多目标加权法 层次优化法层次优化法 目标规划法等目标规划法等 特点：将多目标函数转化为单目标函数处理，只能特点：将多目标函数转化为单目标函数处理，只能得到特定条件下的某一得到特定条件下的某一Pareto解。解。华东理工大

35、学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w多目标优化的遗传算法多目标优化的遗传算法 优势：优势：并行地处理一组可能的解；并行地处理一组可能的解；不局限于不局限于Pareto前沿的形状和连续性，易于处理不前沿的形状和连续性，易于处理不连续的、凹形的连续的、凹形的Pareto前沿。前沿。目前基于目前基于Pareto的遗传算法占据主要地位。的遗传算法占据主要地位。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w多目标优化的遗传算法多目标优化的遗传算法 聚合函数法聚合函数法：把多个目标函数表示成一个目标函数作为

36、遗传算法把多个目标函数表示成一个目标函数作为遗传算法的适应函数（聚合）；的适应函数（聚合）；无需改动遗传算法，但权值难以确定；无需改动遗传算法，但权值难以确定；改进：自适应权值。改进：自适应权值。kiiixfwMinimize1)(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w多目标优化的遗传算法多目标优化的遗传算法 向量评价遗传算法（非向量评价遗传算法（非Pareto法）法）：子种群的产生根据每一个目标函数分别进行选择。子种群的产生根据每一个目标函数分别进行选择。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072

37、007年年年 w多目标优化的遗传算法多目标优化的遗传算法 基于排序的多目标遗传算法基于排序的多目标遗传算法：根据根据“Pareto最优个体最优个体”的概念对所有个体进行排的概念对所有个体进行排 序，依据这个排列次序来进行进化过程中的选择运序，依据这个排列次序来进行进化过程中的选择运 算，从而使得排在前面的算，从而使得排在前面的Pareto最优个体将有更多最优个体将有更多 的机会遗传到下一代群体。的机会遗传到下一代群体。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w多目标优化的遗传算法多目标优化的遗传算法 小生境小生境Pareto遗传算法遗传算法

38、：为了保证寻优过程不收敛于可行域的某一局部，为了保证寻优过程不收敛于可行域的某一局部，使种群向均匀分布于使种群向均匀分布于Pareto前沿面的方向进化，前沿面的方向进化，通过共享函数定义一小生境加以实现。通过共享函数定义一小生境加以实现。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wTSP Benchmark 问题问题 41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74

39、 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wTSP Benchmark 问题问题 编码：直接采用解的表示形式，编码：直接采用解的表示形式，30位（位（30个城市）个城市）长，每位代表所经过的城市序号（无重复）；长，每位代表所经过的城市序号（无重复）；适应度函数：个体所代表的路径距离的倒数；适应度函数：个体所代表的路径距离的倒数；选择：轮盘赌方法选择：轮盘赌方法 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系

40、 200720072007年年年 wTSP Benchmark 问题问题 交叉：有序交叉法交叉：有序交叉法 1）随机选取两个交叉点；）随机选取两个交叉点；2）两个父个体交换中间部分；）两个父个体交换中间部分；3）替换交换后重复的城市序号。）替换交换后重复的城市序号。X1:9 8|4 5 6 7 1|3 2 0X2:8 7|1 4 0 3 2|9 6 5X1:9 8|1 4 0 3 2|3 2 0X2:8 7|4 5 6 7 1|9 6 5X1:9 8|1 4 0 3 2|7 5 6X2:8 3|4 5 6 7 1|9 0 2 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200

41、720072007年年年 wTSP Benchmark 问题问题 变异：随机选择同一个个体的两个点进行交换；变异：随机选择同一个个体的两个点进行交换；初始参数：初始参数：种群规模种群规模 100 交叉概率交叉概率 0.8 变异概率变异概率 0.8 终止代数终止代数 2000 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wTSP Benchmark 问题问题 运行结果：运行结果：华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wTSP Benchmark 问题问题 运行结果：运行结果：华东理工大学自动

42、化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wTSP Benchmark 问题问题 运行结果：运行结果：华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wTSP Benchmark 问题问题 运行结果：运行结果：华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wTSP Benchmark 问题问题 运行结果：运行结果：华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wTSP Benchmark 问题问题 运行结果：运行结果：

43、华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wTSP Benchmark 问题问题 运行结果：运行结果：华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w优化神经网络的权值优化神经网络的权值 神经网络建模：神经网络建模：x1输出层输出层隐藏层隐藏层输入层输入层x2yxn 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w优化神经网络的权值优化神经网络的权值 例：聚丙烯生产过程熔融指数的软测量模型例：聚丙烯生产过程熔融指数的软测量模型 输入变量：加氢量、釜

44、压、升温时间、反应时间、输入变量：加氢量、釜压、升温时间、反应时间、搅拌电流；搅拌电流；输出变量：熔融指数；输出变量：熔融指数；样本数据：样本数据：240组现场数据；组现场数据；华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w优化神经网络的权值优化神经网络的权值 个体的表示：个体的表示：w11 w12 w1n wnm w1 wm b1 bm b 适应度的设计：样本数据与神经网络预测数据的误适应度的设计：样本数据与神经网络预测数据的误差和的倒数；差和的倒数；华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年

45、 w优化神经网络的权值优化神经网络的权值 适应度函数的计算：适应度函数的计算：load datat.txt;对样本数据归一化；对样本数据归一化；S1=6;for i=1:S1 for j=1:5 w1(i,j)=sol(i-1)*5+j);end w2(i)=sol(5*S1+i);b1(i)=sol(6*S1+i);end 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);华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 2007

46、20072007年年年 w优化神经网络的权值优化神经网络的权值 遗传算子：可采用各种方法；遗传算子：可采用各种方法；bounds=ones(43,1)*-1 1;x endPop bpop trace=ga(bounds,jbx,1e-8 1 1,maxGenTerm,1000,normGeomSelect,0.08,simpleXover,0.6,binaryMutation,0.05);华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w优化神经网络的权值优化神经网络的权值 优化结果：优化结果：华东理工大学自动化系华东理工大学自动化系华东理工大学

47、自动化系 200720072007年年年 w用遗传算法进行特征提取用遗传算法进行特征提取 目的：从可能的目的：从可能的m个特征中依据某个评价标准选出个特征中依据某个评价标准选出d个特征（个特征（md）；）；华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w用遗传算法进行特征提取用遗传算法进行特征提取 个体的表示方法：一个长度为个体的表示方法：一个长度为L的个体对应于一个的个体对应于一个L维的二进制特征矢量，它的每一位就表示包括或维的二进制特征矢量，它的每一位就表示包括或排除一个相应的特征。一个个体即是一个可能的最排除一个相应的特征。一个个体即是一个

48、可能的最优特征子集；优特征子集；适应度函数的设计：个体所代表的特征子集进行分适应度函数的设计：个体所代表的特征子集进行分类时的识别率；类时的识别率；遗传算子：可采用各种方法；遗传算子：可采用各种方法；华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w用遗传算法进行特征提取用遗传算法进行特征提取 例：作品鉴别例：作品鉴别 将图像分为将图像分为mn格，对每一个格格，对每一个格 进行数据分析，得到进行数据分析，得到L个特征，个特征，从从L中选出中选出l个（个（Ll）特征送入）特征送入 分类器进行识别。分类器进行识别。华东理工大学自动化系华东理工大学自动化

49、系华东理工大学自动化系 200720072007年年年 w用遗传算法进行特征提取用遗传算法进行特征提取 例：作品鉴别例：作品鉴别 个体的表示：个体的表示：l位长，每位代表一个特征的序号，位长，每位代表一个特征的序号，不可重复；不可重复；适应度函数的设计：识别率的函数；适应度函数的设计：识别率的函数；遗传算子：符合个体编码要求的算子。遗传算子：符合个体编码要求的算子。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w内容内容 用遗传算法解决下面函数的极小值问

50、题：用遗传算法解决下面函数的极小值问题：32|,20)/)2cos(exp()/2.0exp(20)(5015012iiiiixenxnxXf 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w要求要求 1.遗传算法的具体实施策略不限；遗传算法的具体实施策略不限；2.最好用最好用MATLAB；3.上交内容包括：源程序（如非上交内容包括：源程序（如非MATLAB语言编制，语言编制，则包括源代码和可执行文件）和运行结果（图、表则包括源代码和可执行文件）和运行结果（图、表等，等，WORD文档），发送至文档），发送至 w时限时限 2007年年10月月18日