《多目标进化算法总结》由会员分享，可在线阅读，更多相关《多目标进化算法总结（18页珍藏版）》请在金锄头文库上搜索。
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 o
4、perator是一样的不一样的共享函数：表示个体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, rebin
7、ation 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 Paret
8、o 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 whic
9、h 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 t
10、his 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
12、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 distance d; the chosen cluste
13、rs 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）Environmental 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 dominat
