多目标优化问题国内外研究现状ppt课件.ppt

1 多目标优化问题 几乎现实世界中的所有问题都存在多个目标 而这些目标通常是相互冲突 相互竞争的 一个目标的改善往往同时引起其他目标性能的降低 也就是说 不存在使各目标函数同时达到最优的解 而只能对他们进行协调和折衷处理 多目标优化问题 就是寻找满足约束条件和所有目标函数的一组决策变量和相应各目标函数值的集合 Pareto最优解 并将其提供给决策者 由决策者根据偏好或效用函数确定可接受的各目标函数值及相应的决策状态 2 多目标优化的国内外研究现状 1 传统的方法 权重法 约束法 混合法 目标规划法 最大最小法等 特点 将多个目标聚合成一个函数 缺点 各目标加权值的分配带有较大的主观性 优化过程中各目标的优度进展不可操作等 在处理高维数 多模态 非线性等复杂问题上存在许多不足 3 多目标优化的国内外研究现状 遗传算法是模拟自然界生物进化过程与机制 求解优化与搜索问题的一类自组织 自适应的人工智能技术 由于遗传算法是对整个群体进行的进化运算操作 它着眼于个体的集合 而多目标优化问题的非劣解一般也是一个集合 遗传算法的这个特性表明遗传算法非常适合求解多目标优化问题 近年来 遗传算法应用于多目标优化领域 4 多目标优化的国内外研究现状 2 多目标优化遗传算法 VEGA HLGA FFGA MOGA NPGA NSGA SPEA NSGA II SPEA2 PAES缺点 1 多目标遗传算法的局部搜索能力较差2 求解过程依赖于染色体的表示形式 即与个体编码方式的关系很密切3 非劣最优解域收敛性分析困难4 参数较多 如果设置不恰当会导致算法运行的性能下降 5 多目标问题的定义 多目标优化问题的定义为 在可行域中确定由决策变量组成的向量 使得一组相互冲突的目标函数值尽量同时达到极小 设有q个优化目标 且这q个优化目标可能是相互冲突的 其数学表达式为 其中 为不等式约束条件 可行域S为 目标空间Z为 6 支配关系 设p和q是Pop中的任意二个个体 我们称p支配 dominated q 则必须满足下列二个条件 1 对所有的子目标 p不比q差 即 其中r为子目标的数量 求极小值 2 至少存在一个子目标 使p比q好 即此时称p为非支配的 q为被支配的 7 支配关系 其中1 2 3 4代表四个可行解 点4表示的解支配点1 2 3所表示的解 点2 3所表示的解均支配点1表示的解 点2与点3所表示的解彼此不相关 8 Pareto边界 非劣解又称为Pareto最优解 多目标优化问题有很多个Pareto最优解 解决多目标优化问题的关键在于获得有这些Pareto最优解组成的集合 Pareto最优解集在解空间中往往会形成一条边界线 面 9 NSGA 非支配排序遗传算法NSGA Non dominatedSortingGeneticAlgorithm 是由Srinivas和Deb于1995年提出的 这是一种基于Pareto最优概念的遗传算法 优点 优化目标个数任选 非劣最优解分布均匀 并允许存在多个不同的等价解 缺点 a 计算复杂度较高 算法复杂度是 其中N为种群大小 M为目标函数的个数 当种群较大时 计算相当耗时 b 没有精英策略 精英策略能加速算法的执行速度 而且也能在一定程度上确保已经找到的满意解不被丢失 c 需要指定共享半径 10 NSGA II 2000年 Deb等人针对NSGA的不足之处 提出NSGA的改进算法 带精英策略的非支配集排序遗传算法 NSGA II 1 提出了非支配集排序的方法 以降低算法的计算复杂度 2 采用拥挤度距离 代替了需要指定共享半径的适应度共享策略 并在快速排序后的同级比较中作为胜出标准 使Pareto域中的个体能扩展到整个Pareto域 并均匀分布 3 它采用了新的选择操作 在包含父种群和子种群的交配池中 依照适应度和分布度选择最好的N 种群大小 个个体 从而使解有较好的收敛性 11 NSGA II 1 快速的非劣解分类方法 为了根据个体的非劣解水平将种群分类 必须将每一个体与其他个体进行比较 NSGA II算法采用快速的非劣解分类方法 计算速度提高 首先 对每一个解计算两个属性 1 ni 支配解i的解数目 2 si 解i所支配解的集合 找到所有ni 0的解并将其放入F1 称F1是当前非劣解 其等级为1 对当前非劣解中的每一个解i 考察其支配集中si的每一点j并将nj减少一个 如果某一个体j其nj成为零 我们把它放入单独的类H 如此反复考察所有的点 得到当前非劣解H 依次类推 直至所有解被分类 12 NSGA II 2 拥挤距离的计算 为了保持个体分布均匀 防止个体在局部堆积 NSGA II算法首次提出了拥挤距离的概念 它指目标空间上的每一点与同等级相邻两点之间的局部拥挤距离 使用这一方法可自动调整小生境 使计算结果在目标空间比较均匀地散布 具有较好的鲁棒性 13 NSGA II 14 NSGA II 3 选择运算 选择过程使优化朝Pareto最优解的方向进行并使解均匀散布 比较两个个体 如果非劣等级不同 则取等级高 级数值小 的点 否则 如果两点在同一等级上 则取比较稀疏区域内的点 以使进化朝非劣解和均匀散布的方向进行 15 NSGA II 4 精英保留策略 首先 将父体和子代全部个体合并成一个统一的种群放入进化池中 种群的个体数成为2N 然后种群按非劣解等级分类并计算每一个体的局部拥挤距离 依据等级的高低逐一选取个