多目标优化问题的求解算法分类

点击次数:   更新时间:2020-07-23 22:03     来源:竞技宝官网

  实际中遇到的优化问题通常都会从不同角度来定义目标函数,如从成本角度,则为最小化运营成本或最大化利润,从效率角度,则为最小化总完成时间或者makespan等,如图1所示,求解多目标优化问题的算法大致可以分为3类

  (1) 为不同目标函数分配权重,通过加权和(Weighted sum)转化为单目标函数

  此类方法只适合于那些能够明确定义目标函数权重的问题,不适用于那些目标函数相对重要性不明确的问题,同时,所得到的解可能与目标函数所定义的权重紧密相关。通过将多目标函数加权转化为单目标函数,即可使用单目标函数求解的方法。

  此类方法适合于不同目标函数具有明显重要性或优先级的问题,即不能降低高优先级目标函数的取值来改进低优先级的目标函数。但是,这类方法不能为决策者提供不同目标函数权衡的比较分析。

  此类方法适合于不同目标函数重要性或优先级不明确的问题,可以为决策者提供所有可行分非支配最优解,因而,能够为决策者提供不同且矛盾目标之间的权衡分析(trade-off analysis)。但是,决策者需从一系列非支配最优解中选择合适的解作为最终的方案,因此,这类方法不适合实时的优化问题,更适用于战略层或战术层方面的决策优化问题。求解此类问题常用的方法包括epsilon-约束法、NSGA-II、MOEA/D等。

  以上3类算法是求解多目标优化问题的基本思想,具体到如何设计算法,一般基于这些思想,既可以尝试使用CPLEX等优化求解器,也可使用元启发式算法(Metaheuristics)。

竞技宝官网
CopyRight 竞技宝官网 ALL Rights Reserved