遗传算法授课课件-2

遗传算法（续）3遗传算法的改进CHC算法自适应遗传算法基于小生境技术的遗传算法4遗传算法的应用解决带约束的函数优化问题解决多目标优化问题解决组合优化问题遗传算法在模式识别中的应用3遗传算法的改进改进的途径改变遗传算法的组成成分；采用混合遗传算法；采用动态自适应技术；采用非标准的遗传操作算子；采用并行遗传算法等。遗传算法的改进改进思路1991年Eshelman提出的一种改进遗传算法；C：跨代精英选择（Crossgenerationalelitistselection）策略；H：异物种重组（Heterogeneousrecombination）；C：大变异（Cataclysmicmutation）。1.CHC算法遗传算法的改进选择上一代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体；即使交叉操作产生较劣个体偏多，由于原种群大多数个体残留，不会引起个体的评价值降低；可以更好地保持遗传多样性；排序方法，克服比例适应度计算的尺度问题。CHC算法遗传算法的改进交叉均匀交叉的改进：当两个父个体位值相异的位数为m时，从中随机选取m/2个位置，实行父个体位值的交换；显然，这样的操作对模式具有很强的破坏性。确定一阈值，当个体间距离低于该阈值时，不进行交叉操作。进化收敛的同时，逐渐地减小该阈值。CHC算法遗传算法的改进变异在进化前期不采取变异操作，当种群进化到一定收敛时期，从最优个体中选择一部分个体进行初始化；初始化：选择一定比例（扩散率，一般0.35）的基因座，随机地决定它们的位值。CHC算法遗传算法的改进参数分析交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键，直接影响算法的收敛性；Pc越大，新个体产生的速度就越快，但过大会使优秀个体的结构很快被破坏；Pc过小，搜索过程缓慢，以至停止不前；Pm过小，不易产生新个体结构，Pm过大，变成纯粹的随机搜索；2自适应遗传算法遗传算法的改进自适应策略Srinvivas等提出一种自适应遗传算法，Pc和Pm能够随适应度自动改变：当种群各个体适应度趋于一致或趋于局部最优时，使Pc和Pm增加；而当群体适应度比较分散时，使Pc和Pm减少；对于适应度较高的个体，对应于较低的Pc和Pm；而较低适应度的个体，对应于较高的Pc和Pm。自适应遗传算法遗传算法的改进自适应方法fmax——群体中最大的适应度值；favg——每代群体的平均适应度值；f’——要交叉的两个个体中较大的适应度值；f——要交叉或变异的个体适应度值；自适应遗传算法avgavgavgmavgavgavgcffkffffffkPffkffffffkP,,)(,,)'(4maxmax32maxmax1k1、k2、k3、k4取(0,1)的值遗传算法的改进自适应方法进一步改进适用于进化后期，不适于进化前期，因为前期的优秀个体有可能是局部最优点；使最大适应度个体的交叉概率和变异概率由0提高到Pc2和Pm2；采用精英选择策略；自适应遗传算法遗传算法的改进自适应方法进一步改进自适应遗传算法001.0,1.0,6.0,9.0,,)()(,,)')((21211maxmax32111max211mmccavgmavgavgmmmmavgcavgavgavgccccPPPPffPffffffkPPPPffPffffffPPPP遗传算法的改进小生境概念小生境（niche）：生物学中，特定环境中的一种组织功能；在自然界中，往往特征、性状相似的物种相聚在一起，并在同类中交配繁衍后代。在SGA中，容易“近亲繁殖”；NGA（NicheGenericAlgorithm），将每一代个体划分为若干类，每类选出优秀个体组成一个种群；优势：保持解的多样性，提高全局搜索能力，适合复杂多峰函数的优化。3基于小生境技术的遗传算法遗传算法的改进选择策略预选择机制、排挤机制、分享机制；预选择（preselection,1970）机制当子个体的适应度超过其父个体适应度时，子个体才可以替代父个体，否则父个体仍保留；有效维持种群多样性，造就小生境进化环境。基于小生境技术的遗传算法遗传算法的改进排挤（crowding,1975）机制设置排挤因子CF（CF=2或3），随机选取1/CF的个体组成排挤成员，排挤与其相似的个体；个体之间的相似性可用个体编码串之间的海明距离来度量。基于小生境技术的遗传算法遗传算法的改进共享（sharing,1987）机制通过个体之间的相似性程度的共享函数来调整各个体的适应度；共享函数的目的：将搜索空间的多个峰值在地理上区分开来，每一个峰值处接受一定比例数目的个体，比例数目与峰值高度有关；基于小生境技术的遗传算法遗传算法的改进共享（sharing,1987）机制共享函数的值越大，表明个体之间越相似，记为Sh(dij)，dij为两个个体i和j之间的距离；σshare是niche的半径，由使用者给定。基于小生境技术的遗传算法shareshareshareddddSh,0,1)(遗传算法的改进共享（sharing,1987）机制共享法将个体的适应度降低，即适应度值fi除以一个niche计数mi：在距离为σshare的范围内的个体彼此削减适应度，这些个体将收敛在一个niche内，避免了整个种群的收敛。基于小生境技术的遗传算法PopjijidShm)(4遗传算法的应用约束最优化问题（ConstrainedOptimizationProblems）的表述1解决带约束的函数优化问题,,1,0)(,,1,0)()(iiijiuxlnjxhmixgxfMinimize遗传算法的应用解决途径将有约束问题转化为无约束问题（罚函数法，penaltyfunctionmethod），历史较长；改进无约束问题的方法，使之能用于有约束的情况（梯度投影算法），发展较晚。遗传算法解决有约束问题的关键是对约束条件的处理（直接按无约束问题处理是行不通的：随机生成的初始点中可能有大量不可行解；遗传算子作用于可行解后可能产生不可行解）。解决带约束的函数优化问题遗传算法的应用一般方法罚函数法将罚函数包含到适应度评价中：关键是如何设计罚函数，需要谨慎地在过轻或过重惩罚之间找到平衡，针对不同问题设计罚函数。解决带约束的函数优化问题为罚函数尺度系数。，满足罚函数rXxXxxPxPxrPxf,0,0)()()()(遗传算法的应用一般方法协同进化遗传算法（CoevolutionaryGeneticAlgorithm,1997）以食物链关系、共生关系等为基础的生物进化现象称为协同进化；一个种群由问题的解组成，另一个种群由约束组成，两个种群协同进化，较好的解应满足更好的约束，较优的约束则被更多的解所违背。解决带约束的函数优化问题罚函数法评价函数的构造：加法乘法遗传算法的应用XxXxxPxrPxf,0,0)()()(解决带约束的函数优化问题XxXxxPxPxf,1,1)()()(罚函数法罚函数分类：定量惩罚——简单约束问题变量惩罚——复杂约束问题，包含两个部分：可变惩罚率和违反约束的惩罚量。遗传算法的应用解决带约束的函数优化问题违反约束程度——随违反约束程度变得严重而增加惩罚压力，静态惩罚；进化迭代次数——随着进化过程的进展而增加惩罚压力，动态惩罚。罚函数法交叉运算：设父个体为x=[x1,x2,…,xn]和y=[y1,y2,…,yn]简单交叉单点算术交叉整体算术交叉基于方向的交叉：x’=r(x-y)+x，r为(0,1)之间的随机数，并假设f(x)≥f(y)。遗传算法的应用解决带约束的函数优化问题罚函数法变异运算：设父个体为x=[x1,x2,…,xn]均匀变异非均匀变异（动态变异）边界变异：x’=[x1,x2,…,xk’,…,xn]，xk’等概率地取用变异量的上界或下界，当最优解在可行域边界上或附近时，边界变异算子较为有效；基于方向的变异：x’=x+r•d，d为目标函数的近似梯度。遗传算法的应用解决带约束的函数优化问题遗传算法的应用求解线性约束优化问题的遗传算法线性约束优化问题一般形式为：解决带约束的函数优化问题niuxldxcxcdxcxcbxaxabxaxatosubjectxxfMinimizeiiilnlnlnnmnmnmnnn,,1,),,(111111111111111uxldCxbΑxx)(tosubjectfMinimize遗传算法的应用求解线性约束优化问题的遗传算法线性约束优化问题：目标函数可以是线性函数或非线性函数；思路——消除可能的变量，消除等式约束设计罚函数设计特别的遗传操作解决带约束的函数优化问题遗传算法的应用多目标优化问题解的存在性怎样求解2解决多目标优化问题,,1,0)(,,1,0)()](,),(),([21iiijikuxlnjxhmixgxfxfxfMinimize遗传算法的应用Pareto最优性理论在一个有k个目标函数最小化的问题中，称决策向量x*∈F是Pareto最优的，当不存在另外一个决策向量x∈F同时满足解决多目标优化问题},,2,1{),()(},,2,1{),()(**kjxfxfkixfxfjjii遗传算法的应用Pareto最优性理论多目标优化问题的解通常是多个满意解的集合，称为Pareto最优集，解集中的决策向量称为非劣的。解决多目标优化问题遗传算法的应用传统方法多目标加权法层次优化法目标规划法等特点：将多目标函数转化为单目标函数处理，只能得到特定条件下的某一Pareto解。解决多目标优化问题遗传算法的应用多目标优化的遗传算法优势：并行地处理一组可能的解；不局限于Pareto前沿的形状和连续性，易于处理不连续的、凹形的Pareto前沿。目前基于Pareto的遗传算法占据主要地位。解决多目标优化问题遗传算法的应用多目标优化的遗传算法聚合函数法：把多个目标函数表示成一个目标函数作为遗传算法的适应函数（聚合）；无需改动遗传算法，但权值难以确定；改进：自适应权值。解决多目标优化问题kiiixfwMinimize1)(遗传算法的应用多目标优化的遗传算法向量评价遗传算法（非Pareto法）：子种群的产生根据每一个目标函数分别进行选择。解决多目标优化问题遗传算法的应用多目标优化的遗传算法基于排序的多目标遗传算法：根据“Pareto最优个体”的概念对所有个体进行排序，依据这个排列次序来进行进化过程中的选择运算，从而使得排在前面的Pareto最优个体将有更多的机会遗传到下一代群体。解决多目标优化问题遗传算法的应用多目标优化的遗传算法小生境Pareto遗传算法：为了保证寻优过程不收敛于可行域的某一局部，使种群向均匀分布于Pareto前沿面的方向进化，通过共享函数定义一小生境加以实现。解决多目标优化问题遗传算法的应用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;4503解决组合优化问题遗传算法的应用TSPBenchmark问题编码：直接采用解的表示形式，30位（30个城市）长，每位代表所经过的城市序号（无重复）；适应度函数：个体所代表的路径距离的倒数；选择：轮盘赌方法解决组合优化问题遗传算法的应用TSPBenchmark问题交叉：有序交叉法1）随机选取两个交叉点；2）两个父个体交换中间部分；3）替换交换后重复