多目标优化问题.ppt

多目标优化问题几乎现实世界中的所有问题都存在多个目标，而这 些目标通常是相互冲突，相互竞争的一个目标的改善 往往同时引起其他目标性能的降低也就是说，不存在 使各目标函数同时达到最优的解，而只能对他们进行协 调和折衷处理多目标优化问题，就是寻找满足约束条件和所有目 标函数的一组决策变量和相应各目标函数值的集合（ Pareto最优解），并将其提供给决策者由决策者根据 偏好或效用函数确定可接受的各目标函数值及相应的决 策状态多目标优化的国内外研究现状l1.传统的方法：权重法，约束法，混合法，目标规划 法，最大最小法等l特点：将多个目标聚合成一个函数l缺点：各目标加权值的分配带有较大的主观性；优化 过程中各目标的优度进展不可操作等；在处理高维数 、多模态、非线性等复杂问题上存在许多不足 多目标优化的国内外研究现状l 遗传算法是模拟自然界生物进化过程与机制，求解 优化与搜索问题的一类自组织、自适应的人工智能技术 由于遗传算法是对整个群体进行的进化运算操作，它 着眼于个体的集合，而多目标优化问题的非劣解一般也 是一个集合，遗传算法的这个特性表明遗传算法非常适 合求解多目标优化问题近年来，遗传算法应用于多目 标优化领域 。

多目标优化的国内外研究现状2.多目标优化遗传算法：VEGA，HLGA，FFGA ，MOGA，NPGA，NSGA，SPEA，NSGA-II ，SPEA2，PAES缺点：1.多目标遗传算法的局部搜索能力较差2.求解过程依赖于染色体的表示形式，即与个体 编码方式的关系很密切l 3.非劣最优解域收敛性分析困难l 4.参数较多，如果设置不恰当会导致算法运行的 性能下降多目标问题的定义多目标优化问题的定义为：在可行域中确定由决策变量组成的 向量，使得一组相互冲突的目标函数值尽量同时达到极小设 有 q 个优化目标，且这 q个优化目标可能是相互冲突的其数 学表达式为：其中， 为不等式约束条件可行域 S 为：目标空间 Z 为：支配关系设p和q是Pop中的任意二个个体，我们称p支配 （dominated）q，则必须满足下列二个条件： （1）对所有的子目标，p不比q差即 ，其中r为子目标的数量（ 求极小值） （2）至少存在一个子目标，使p比q好即此时称p为非支配的，q为被支配的 支配关系其中1、2、3、4代表四个可行解，点4表示的解支配点 1、2、3所表示的解，点2、3所表示的解均支配点1表 示的解；点2与点3所表示的解彼此不相关。

Pareto 边界非劣解又称为非劣解又称为ParetoPareto最优解，多目标优化问题有很最优解，多目标优化问题有很 多个多个ParetoPareto最优解，解决多目标优化问题的关键在最优解，解决多目标优化问题的关键在 于获得有这些于获得有这些ParetoPareto最优解组成的集合最优解组成的集合Pareto Pareto 最最 优解集在解空间中往往会形成一条边界线（面）优解集在解空间中往往会形成一条边界线（面） NSGA非支配排序遗传算法NSGA（Non-dominated Sorting Genetic Algorithm）是由Srinivas和Deb于1995年提出的，这 是一种基于Pareto最优概念的遗传算法 优点：优化目标个数任选，非劣最优解分布均匀，并允许存在 多个不同的等价解 缺点： a）计算复杂度较高，算法复杂度是 (其中N为种群大小 ，M为目标函数的个数)，当种群较大时，计算相当耗时； b）没有精英策略，精英策略能加速算法的执行速度，而且也 能在一定程度上确保已经找到的满意解不被丢失； c）需要指定共享半径 NSGA-IIl2000年，Deb等人针对NSGA的不足之处，提出NSGA的改进算法 —带精英策略的非支配集排序遗传算法（NSGA-II）。

l1.提出了非支配集排序的方法，以降低算法的计算复杂度l2.采用拥挤度距离，代替了需要指定共享半径的适应度共享 策略，并在快速排序后的同级比较中作为胜出标准，使 Pareto域中的个体能扩展到整个Pareto域，并均匀分布l3. 它采用了新的选择操作：在包含父种群和子种群的交配池 中，依照适应度和分布度选择最好的N（种群大小）个个体， 从而使解有较好的收敛性NSGA-II1.快速的非劣解分类方法：为了根据个体的非劣解水平将种群分类，必须将每一个 体与其他个体进行比较NSGA-II算法采用快速的非劣解分 类方法，计算速度提高首先，对每一个解计算两个属性：（1）ni，支配解i的解数目；（2）si，解i所支配解的集合找到所有ni=0的解并将其放入F1，称F1是当前非劣解， 其等级为 1对当前非劣解中的每一个解i，考察其支配集 中si的每一点j并将nj减少一个，如果某一个体j其nj成为零 ，我们把它放入单独的类H如此反复考察所有的点，得到 当前非劣解H依次类推，直至所有解被分类NSGA-II2. 拥挤距离的计算 :为了保持个体分布均匀，防止个体在局部堆积 ，NSGA-II算法首次提出了拥挤距离的概念。

它指目 标空间上的每一点与同等级相邻两点之间的局部拥 挤距离使用这一方法可自动调整小生境，使计算 结果在目标空间比较均匀地散布，具有较好的鲁棒 性NSGA-IINSGA-II3.选择运算:选择过程使优化朝Pareto最优解的方向进行并 使解均匀散布比较两个个体，如果非劣等级不同 ，则取等级高（级数值小）的点否则，如果两点 在同一等级上，则取比较稀疏区域内的点，以使进 化朝非劣解和均匀散布的方向进行NSGA-II4.精英保留策略:首先，将父体和子代全部个体合并成一个统一 的种群放入进化池中，种群的个体数成为2N然后 种群按非劣解等级分类并计算每一个体的局部拥挤 距离依据等级的高低逐一选取个体直到个体总数 达到N，从而形成新一轮进化的父代种群，其个体数 为N在此基础上开始新一轮的选择，交叉和变异， 形成新的子代种群这种方法可加快进化的速度NSGA-II。