多目标优化问题.ppt

多目标优化问题
第1页，共16页，编辑于2022年，星期三
多目标优化的国内外研究现状
：权重法，约束法，混合法，目标规划法，最大最小法等。
特点：将多个目标聚合成一个函数。
缺点：各目标加权值的分配带有较大的主多目标优化问题
第1页，共16页，编辑于2022年，星期三
多目标优化的国内外研究现状
：权重法，约束法，混合法，目标规划法，最大最小法等。
特点：将多个目标聚合成一个函数。
缺点：各目标加权值的分配带有较大的主观性；优化过程中各目标的优度进展不可操作等；在处理高维数、多模态、非线性等复杂问题上存在许多不足。
第2页，共16页，编辑于2022年，星期三
多目标优化的国内外研究现状
遗传算法是模拟自然界生物进化过程与机制，求解优化与搜索问题的一类自组织、自适应的人工智能技术。由于遗传算法是对整个群体进行的进化运算操作，它着眼于个体的集合，而多目标优化问题的非劣解一般也是一个集合，遗传算法的这个特性表明遗传算法非常适合求解多目标优化问题。近年来，遗传算法应用于多目标优化领域 。
第3页，共16页，编辑于2022年，星期三
多目标优化的国内外研究现状
：VEGA，HLGA，FFGA，MOGA，NPGA，NSGA，SPEA，NSGA-II，SPEA2，PAES
缺点：

，即与个体 编码方式的关系很密切

，如果设置不恰当会导致算法运行的性能下降
第4页，共16页，编辑于2022年，星期三
多目标问题的定义
多目标优化问题的定义为：在可行域中确定由决策变量组成的向量，使得一组相互冲突的目标函数值尽量同时达到极小。设有 q 个优化目标，且这 q个优化目标可能是相互冲突的。其数学表达式为：

其中， 为不等式约束条件。
可行域 S 为：
目标空间 Z 为：
第5页，共16页，编辑于2022年，星期三
支配关系
设p和q是Pop中的任意二个个体，我们称p支配
（dominated）q，则必须满足下列二个条件：
（1）对所有的子目标，p不比q差。
即 ，其中r为子目标的数量（求极小值） 。
（2）至少存在一个子目标，使p比q好。
即
此时称p为非支配的，q为被支配的。
第6页，共16页，编辑于2022年，星期三
支配关系
其中1、2、3、4代表四个可行解，点4表示的解支配点1、2、3所表示的解，点2、3所表示的解均支配点1表示的解；点2与点3所表示的解彼此不相关。
第7页，共16页，编辑于2022年，星期三
Pareto 边界
非劣解又称为Pareto最优解，多目标优化问题有很多个Pareto最优解，解决多目标优化问题的关键在于获得有这些Pareto最优解组成的集合。Pareto 最优解集在解空间中往往会形成一条边界线（面）。
第8页，共16页，编辑于2022年，星期三
NSGA
非支配排序遗传算法NSGA（Non-dominated Sorting Genetic Algorithm）是由Srinivas和Deb于1995年提出的，这是一种基于Pareto最优概念的遗传算法。
优点：优化目标个数任选，非劣最优解分布均匀，并允许存在多个不同的等价解。
缺点：
a）计算复杂度较高，算法复杂度是 (其中N为种群大小，M为目标函数的个数)，当种群较大时，计算相当耗时；
b）没有精英策略，精英策略能加速算法的执行速度，而且也能在一定程度上确保已经找到的满意解不被丢失；
c）需要指定共享半径
第9页，共16页，编辑于2022年，星期三
NSGA-II
2000年，Deb等人针对NSGA的不足之处，提出NSGA的改进算法—带精英策略的非支配集排序遗传算法（NSGA-II）。
，以降低算法的计算复杂度。
，代替了需要指定共享半径的适应度共享策略，并在快速排序后的同级比较中作为胜出标准，使Pareto域中的个体能扩展到整个Pareto域，并均匀分布。
3. 它采用了新的选择操作：在包含父种群和子种群的交配池中，依照适应度和分布度选择最好的N（种群大小）个个体，从而使解有较好的收敛性。
第10页，共16页，编辑于2022年，星期三
NSGA-II
：
为了根据个体的非劣解水平将种群分类，必须将每一个体与其他个体进行比较。