多目标优化算法
一般，处理多目标优化问题有两种方式：
1） 归一化处理，转化为单目标优化问题，计算出单一权重组合下的最优方案。
2） 采用多目标优化算法，计算出所有权重组合的最优方案，即得到Pareto解集合
在iSIGHT中，对应的方法有：
u 归一化解法
l 权重法
l MTA( Multi-criteria Trade-off Analysis )
l 满足化trade-off法(Satisficing Trade-off Analysis)
u 非归一化解法
l 多目标遗传运算
u NCGA
u NSGAII
“归一化”的概念：
我们可以这样设想：如果把多目标问题转化成单目标的问题并能保证其转化的准确性，就可以照搬单目标优化问题的解法来处理多目标问题了。
把多目标的目标函数变换为单一评价尺度就叫做归一化
“Pareto解”的概念：
u Pareto解：也叫非劣解，非支配解。
u 在多目标优化问题中，我们所要找的并不是所有子目标的最优解，而是所谓的Pareto解。
u 由于目标函数间的矛盾性质，一般说来使每个目标函数同时达到各自最优值的解是不存在的。多目标最优问题的解为Pareto最优解的条件是解的任何一个目标函数的值在不使其他目标函数值恶化的条件下已不可能进一步改进。
u 很显然的，Pareto最优解不止一个，事实上在一般多目标优化问题中，Pareto最优解常是连续的而且有无限多个，这就构成了Pareto前沿的概念。
u 多目标优化问题的最终解是从所有pareto最优解中挑一个最优折衷解。
MOGA——NCGA
u NCGA是由同志社大学的三木・广安研究室在2002年发布的运算规则。
u NCGA有效的继承了前人的成果，加上由同一研究室的提高GA的并行运算性能的研究过程得到的知识，谋求提高探索性能。
u 在研究提高GA的并行性能的过程中发现，为了并行而分割父种群的时候，把属于父种群的个体中有相似性的分在一起比较好。
l 这样的意思是说，在进行交叉的时候，不是在具有完全不同的遗传因子信息的个体间进行，而是在具有一定程度的类似性的个体之间进行比较好。
l 在NCGA中这种思考方法作为“近傍交叉”写明且被引入，意在提高探索性。
u 在NCGA中，遗传因子的表现依照graycode使用比特量子化。交叉和突然变异方法与GA方法相同。
u NCGA方法的优点和缺点
优点
l 能够生成具有多样性的解
u 因为在目标空间里没有重复的个体，比起NSGA-II和SPEA2有更加容易生成更多样的解的倾向
l 近傍交叉也被确认为在这样的多峰性问题上可以得到好的结果
缺点
l 在父集团的多样性不是很重要的问题中，不会向适应度高的个体积极的施加选择压。和会施加选择压的NSGA-II以及SPEA2相比，frontier的发展比较落后。
l NCGA是比特量子化型的GA方法，对于那些实数变量问题且是在非常广阔的空间里寻找最优解的问题较为不利。
MOGA——NSGA-II
u NSGA-II，作为1994年发布的NSGA(Non-Dominated Sorting Genetic Algorithm)的改良版，由K. Deb，S. Agrawal等在2000年提出。
u NSGA的特征：
l 非支配排序（Non-Dominated Sorting）：
¡ 进化过程中，将当前父代群体进行交叉和变异得到子群体，将两个群体合并。
¡ 在目标空间中按照Pareto最优关系将群体中个体两两按其目标函数向量进行比较，将群体中所有个体分成多个依次控制的前沿层(front)。
l 适应度共享（fitness sharing）：
¡ 在进化过程中必须采用某种策略来保持群体的多样性，防止群体最终只收敛到个别少数解上(即早熟收敛)；
¡ NSGA方法为同一层的个体指定相同的适应度，从而为了保证种群的分布多样性；
¡ 对于接近到了一定距离以后的个体，利用对适应度打折扣的方法提高frontier的被覆盖性；
¡ 因为在最前沿的个体具有最大的适应度，所以被传递到下一代的可能性也就越大。
u NSGA-II相对于NSGA方法的改进：
l 在NSGA-II中，除了非支配排序以外的部分，与NSGA完全不同的运算规则。
l 在NSGA-II中，全面引入存档（archive）这个的概念。
¡ Pareto frontier的前进、扩大和NSGA相比，变得更加可靠 ；
¡ 因为父代探索种群是从archive中根据淘汰选择生成的，对Pareto优越性高的个体，施加大的选择压(在后面详细叙述)。
¡ 这个特征，表现为较高的Pareto frontier的前进能力。
l 作为NSGA中的适应度共享的替换方法，导入了“拥挤距离”和“拥挤距离排序”的方法。
¡ 避免探索集中于Pareto frontier的一部分；
¡ 另外，避免Pareto frontier端头部分个体群被一起剔除的情况。由这一点frontier的扩大被保存了下来。
u NSGA-II方法的优点和缺点
优点：
l 探索性能良好
¡ 在非支配排序中，因为接近frontier的个体的确被选择了，使锋面前进的力变强。
¡ 拥挤距离排序中不会削除frontier的端头部分，所以frontier不会收束到一部分的领域里。
缺点：
l 非劣解集合（F1）的大小超过了N，对F1使用拥挤距离排序时需要把非劣个体的个数限制为N个以下。
¡ 这时，或许会发生非劣个体的数目少到t-1代为止的步骤中得到的非劣解的情况。
¡ 在世代系列中眺望frontier的发展，这一点以frontier的后退为结果而表现出来。
发表于：
2008-04-28 14:23 赛特达 阅读(825)
评论(0) 收藏(0)
好文推荐
作者该类其他文章：