多目标进化算法总结.docx

《多目标进化算法总结.docx》由会员分享，可在线阅读，更多相关《多目标进化算法总结.docx（15页珍藏版）》请在课桌文档上搜索。

1、MOGA是第t代种群中个体，其rank值定义为：为第t代种群中所有支配的个体数目适应值（fitness value）分配算法：1、 将所有个体依照rank值大小排序分类；2、 利用插值函数给所有个体分配适应值（从rank1到rank ），一般采用线性函数3、 适应值共享：rank值相同的个体拥有相同的适应值，保证后期选择时同一rank值的个体概率相同最后采用共享适应值随机选取的方法选择个体进入下一代一种改进的排序机制（ranking scheme）：向量和比较goal vector：分为以下三种情况：1、2、当支配时，选择3、当支配时，选择优点：算法思想容易，效率优良缺点：算法容易受到小生境的

2、大小影响理论上给出了参数的计算方法NPGA基本思想：1、初始化种群Pop2、锦标赛选择机制：随机选取两个个体和和一个Pop的子集CS(parison Set)做参照系。若被CS中不少于一个个体支配，而没有被CS中任一个体支配，则选择。3、其他情况一律称为死结（Tie），采用适应度共享机制选择。个体适应度：小生境计数（Niche Count）：共享函数：共享适应度（the shared fitness）：选择共享适应度较大的个体进入下一代优点：能够快速找到一些好的非支配最优解域能够维持一个较长的种群更新期缺点：需要设置共享参数需要选择一个适当的锦标赛机制限制了该算法的实际应用效果NPGA II基

3、本思想：1、初始化种群Pop2、Pareto排序：非支配个体rank=0；其余个体 rank=支配该个体的个体数目3、锦标赛选择机制：种群中任选两个个体和，若，则选择；若是，称为死结（Tie），采用适应度共享机制选择。小生境计数（Niche Count）：这里的Pop只包含当前一代里的个体，在NPGA中，计算公式中的Pop包含当前一代以及已经产生的属于下一代的所有个体最后，选择计数较小的个体进入下一代在计算Niched Count之前还要对函数值进行标准化：NSGA和简单的遗传算法的不同点在于selection operator works， crossover and mutation op

4、erator是一样的不一样的共享函数：表示个体i和j之间的距离是共享参数，表示小生境的半径小生境计数（Niche Count）：共享适应值：最后采用随机余数比例算法选择个体进行重新构造种群的基础优点：优化目标个数任选非支配最优解分布均匀允许存在多个不同的等效解缺点：计算复杂度过高（）不具有精英保留机制需要预设共享参数NSGA II加入精英保留机制快速非支配排序方法（Fast Nondominated Sorting Approach）：支配计数：支配解p的解数量支配解集：解p支配的解集合1、 计算出每一个解的和，第一级非支配解，单独放入一个集合；2、 遍历成员q和，逐步递减，如果可以减少为0，

5、将p放入单独的集合Q，构成第二级非支配解；3、 重复步骤2，直到所有成员全部分类完成。Crowded-parison Approach1、 计算集合I的长度，初始化；2、 对每一个目标，利用目标值进行排序；3、 赋予边界点（第一个和最后一个）最大值，确保它们不会被剔除；4、 循环计算其他点的crowded distance.其中，I为非支配集合，表示第m个目标在第i个个体处的目标值，分别表示第m个目标的最大最小函数值值越小，越拥挤Crowded-parison Operator： if or Replace the sharing function approach in NSGA可以一定程度

6、上消除一下两点：（1）the sharing function 太过于依赖共享参数，不容易设定（2）the sharing function 时间复杂度达到算法主循环：1、 初始种群（），并利用binary tournament selection, rebination and mutation operators构建一个子代种群（）;2、 合并和，记第t代：合并和，记对进行非支配分类，结果记作循环计算crowded distance of ，并入对当前进行crowded distance 排序，选择前个成员并入，确保利用binary tournament selection, rebina

7、tion and mutation operators构建进入下一次循环SPEACharacters:a) Storing nondominated solutions e*ternally in a second, continuously updated populationb) Evaluating an individuals fitness dependent on the number of e*ternal nondominated points that dominate itc) Preserving population diversity using the Pareto

8、 dominance relationshipd) Incorporating a clustering procedure in order to reduce the nondominated set without destroying its characteristicsSteps:1) Generate an initial population P and create the empty e*ternal nondominated set .2) Copy nondominated member of P to .3) Remove solutions within which

9、 are covered by any other member of .4) If the number of e*ternally stored nondominated solutions e*ceeds a given ma*imum , prune by means of clustering.5) Calculate the fitness of each individual in P as well as in .6) Select individuals from (multiset union), until the mating pool is filled. In th

10、is study, binary tournament selection with replacement is used.7) Apply problem-specific crossover and mutation operators as usual.8) If the ma*imum number of generations is reached, then stop, else go to Step 2.Fitness Assignment:1) 外部群落赋值，称作strength，和的数量成正比，定义：适应值=2）当前群落其中，适应值加1是为了确保外部群落的个体适应值优于当前

11、群落这里适应值越小，被选中的概率越大（small fitness values correspond to high reproduction probabilities）聚簇缩减：1）Initialize cluster set C; each e*ternal nondominated point constitutes a distinct cluster: .2) If , go to Step 5, else go to Step 3.3) Calculate the distance of all possible pairs of clusters. The distance d

12、 of two clusters is given as the average distance between pairs of individuals across the two clusterswhere the metric reflects the distance between two individuals (in this study an Euclidean metric on the objective space is used)4) Determine two clusters with minimal distance d; the chosen cluster

13、s amalgamate into a larger cluster: . Go to Step 2.5) pute the reduced nondominated set by selecting a representative individual per cluster. We consider the centroid (the point with minimal average distance to all other points in the cluster) as representative solution.优点：SPEA IISPEA可改进点：1）Fitness

14、Assignment当成员只有一个时，P中所有成员的适应值都是相同的。会导致选择压力（Selection Pressure）降低，SPEA退化为随机搜索算法。2）Density Estimation群落分布太过稀疏，以至于很多成员之间不存在互相支配关系，这些成员所提供的信息十分有限。如果能够添加密度信息，则就能够更加有效地（Effectively）搜索非支配成员。聚簇（Clustering）方法只对有效，而对P没有影响。3）Archive Truncation聚簇算法会删减中部分成员，这其中也极有可能包含了外部解（outer solutions），造成信息截断（truncation），不利于非

15、支配解的扩散。SPEA 2 Main LoopInput: N(Population size)(Archive size) T(Ma*imum number of generations)Output: A (Nondominated set)1）Initialization：Generate an initial population and create the empty archive (e*ternal set) . Set .2）Fitness assignment：Calculate fitnessvalues of individuals in and 3）Environme

16、ntal selection: Copy all nondomianted individuals in and to . If size of e*ceeds then reduce by means of the truncation operator, otherwise if size of is less than then full with dominated individuals in and .4）Termination：If or another stopping criterion is satisfied then set A to the set of decisi

17、on vectors represented by the nondominated individuals in . STOP!5）Mating selection：Perform binary tournament selection with replacement on in order to fill the mating pool.6）Variation：Apply rebination and mutation operators to the mating pool and set to the resulting population. Increment generatio

18、n counter and go to Step 2.Fitness Assignment: denotes the cardinality of a setStrength value:Raw fitness value:加入density information，采用k-th nearest neighbor method计算个体i所处环境的密度。这里k的取值：。将所有其他个体与个体i 的距离全部计算出来，并升序排序，取第k个距离值，记作：。density：分母加2是为了保证适应值：Environmental Selection:Step 3）与SPEA中有两点不同：1、中的个体数量始终保

19、持不变2、截断方法可以防止边界值被删除构造分三种情况讨论：（1）如果构造的外部群落成员数量正好满足要求，即，构造完成；（2）如果外部群落成员数量偏少，即，则从中挑选个支配个体（dominated individuals）进行填充；（3）如果外部群落成员数量偏多，即，则采用archive truncation method对中成员进行剔除，直到。一、课程介绍计算智能课程对计算智能领域的主要算法进行介绍，重点讨论各种算法的思想来源、流程结构、发展改进、参数设置和相关应用。内容包括绪论以及进化计算、群体智能、人工免疫算法、分布估计算法、神经网络、模糊逻辑和多目标进化算法等。并从工程应用及与其他人工智

20、能研究方向相结合的角度讨论人工智能的实际问题及其解决方法。二、教学内容1. 导论(1课时)（1） 计算智能简介（2） 计算智能典型方法2. 优化理论 (2课时)（1） 优化问题（2） 优化方法分类a) 非约束优化b) 约束优化c) 多解问题d) 多目标优化e) 动态优化问题3. 进化计算(9课时)(1) 进化计算导论(2) 遗传算法a) 经典遗传算法b) 交叉、变异c) 控制参数d) 模式定理与积木块假设e) 遗传算法的变体f) 前沿专题（小生境遗传算法、约束处理、多目标优化、动态环境）g) 应用(3) 遗传编程、进化规划、进化策略(4) 差分进化(5) 文化计算(6) 协同进化4. 人工免疫

21、系统(6课时)（1） 自然免疫系统（2） 人工免疫模型a) 克隆选择模型b) 网络理论模型c) 危险理论（3） 免疫优化计算5. 群体智能(3课时)（1） 粒子群优化（2） 蚁群算法6. 多目标进化算法及应用（6课时）5.1 绪论5.2 主要的多目标进化算法5.3 多目标进化算法性能评价和问题测试集5.4 多目标优化的新进展5.5 应用实例7. 神经网络(6课时)（1） 人工神经元（2） 监督学习神经网络（3） 非监督学习神经网络（4） 径向基函数网络（5） 增强学习（6） 监督学习的性能问题8. 深度学习算法（Deep Learning）（3课时）9. 分布估计算法(3课时)10. 计算智能算法在各研究方向的应用(69课时)（讨论计算智能算法在每个研究生的研究方向中的结合应用）三、教材与参考书1、著，谭营译.计算智能导论M.清华大学.2010.6.2、*军,詹志辉.计算智能M.清华大学.2009.11.3、*微,周春光,梁艳春.智能计算M.高等教育.2009.12.4、段海滨,*祥银,*春芳.仿生智能计算.科学.2011.1.