多目标进化算法总结

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(Comparison Set)做参照系。若被CS中不少于一 个个体支配，而没有被CS中任一个体支配，则选择。3、其他情况一律称为死结（Tie），采用适应度共享机制选择。个体适应度：小生境计数（Niche Count）：共享函数：共享适应度（the shared fitness）：选择共享适应度较大的个体进入下一代优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期缺点：需要设置共享参数 需要选择一个适当的锦标赛机制 限制了该算法的实际应用效

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

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

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

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

7、ament selection, recombination and mutation operators构建进入下一次循环SPEACharacters:a) Storing nondominated solutions externally in a second, continuously updated populationb) Evaluating an individuals fitness dependent on the number of external nondominated points that dominate itc) Preserving population

8、diversity using the Pareto 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 external nondominated set .2) Copy nondominated member of P to .3) Rem

9、ove solutions within which are covered by any other member of .4) If the number of externally stored nondominated solutions exceeds a given maximum , 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 ma

10、ting pool is filled. In this study, binary tournament selection with replacement is used.7) Apply problem-specific crossover and mutation operators as usual.8) If the maximum number of generations is reached, then stop, else go to Step 2.Fitness Assignment:1) 外部群落 赋值，称作strength， 和的数量成正比，定义：适应值=2）当前群

11、落 其中，适应值加1是为了确保外部群落的个体适应值优于当前群落这里适应值越小，被选中的概率越大（small fitness values correspond to high reproduction probabilities）聚簇缩减：1）Initialize cluster set C; each external nondominated point constitutes a distinct cluster: .2) If , go to Step 5, else go to Step 3.3) Calculate the distance of all possible pair

12、s of clusters. The distance d 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 d

13、istance d; the chosen clusters amalgamate into a larger cluster: . Go to Step 2.5) Compute 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 soluti

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

15、olutions），造成信息截断（truncation），不利于非支配解的扩散。SPEA 2 Main LoopInput: N (Population size) (Archive size) T (Maximum number of generations)Output: A (Nondominated set)1）Initialization：Generate an initial population and create the empty archive (external set) . Set .2）Fitness assignment：Calculate fitness val

16、ues of individuals in and 3）Environmental selection: Copy all nondomianted individuals in and to . If size of exceeds 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 sati

17、sfied then set A to the set of decision 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 recombination and mutation operators to the mating pool and set to the r

18、esulting population. Increment generation 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

19、 Selection:Step 3）与SPEA中有两点不同：1、中的个体数量始终保持不变2、截断方法可以防止边界值被删除构造 分三种情况讨论：（1）如果构造的外部群落成员数量正好满足要求，即，构造完成；（2）如果外部群落成员数量偏少，即，则从中挑选个支配个体（dominated individuals）进行填充；（3）如果外部群落成员数量偏多，即，则采用archive truncation method对中成员进行剔除，直到。一、课程介绍计算智能课程对计算智能领域的主要算法进行介绍，重点讨论各种算法的思想来源、流程结构、发展改进、参数设置和相关应用。内容包括绪论以及进化计算、群体智能、人工免疫算法、分布估计算法、神经网络、模糊逻辑和多目标进化算法等。并从工程应用及与其他人工智能研究方向相结合的角度讨论人工智能的实际问题及其解决方法。 二、教学内容1. 导论(1课时)（1） 计算智能简介（2） 计算智能典型方法2. 优化理论 (2课时)（1） 优化问题（2） 优化方法分类a) 非约束优化b) 约束优化c) 多解问题d) 多目标优化e) 动态优化问题3. 进化计算(9课时)(1) 进化计算