利用目标规划加速多目标问题求解,提升效率与效果。
An Efficient Application of Goal Programming to Tackle Multiobjective Problems with Recurring Fitness Landscapes
- 用昂贵算法求解首个实例,获取优质解集
- 后续实例用高效目标规划快速求解,计算时间显著缩短
- 适合具有相似适应度景观的多目标优化场景
许多现实应用需在多个冲突目标下评估解的质量。对于高度约束的多目标问题,即使使用现代多目标算法也难以获得良好近似解集。当同一问题场景的不同实例具有相似的适应度景观时,我们提出一种方法:先用计算成本高的多目标算法求解一个实例,得到优质近似解集;再利用目标规划与高效的单目标算法求解其他实例。在带时间窗的多目标车辆路径问题基准测试中,采用三种基于目标的客观函数,该方法能在极短时间内获得良好结果。该方法结合了先进多目标算法的有效性与目标规划的高效性,适用于实例间适应度景观重复出现的问题场景。
原文摘要 · Abstract (English)
Many real-world applications require decision-makers to assess the quality of solutions while considering multiple conflicting objectives. Obtaining good approximation sets for highly constrained many-objective problems is often a difficult task even for modern multiobjective algorithms. In some cases, multiple instances of the problem scenario present similarities in their fitness landscapes. That is, there are recurring features in the fitness landscapes when searching for solutions to different problem instances. We propose a methodology to exploit this characteristic by solving one instance of a given problem scenario using computationally expensive multiobjective algorithms to obtain a good approximation set and then using Goal Programming with efficient single-objective algorithms to solve other instances of the same problem scenario. We use three goal-based objective functions and show that on benchmark instances of the multiobjective vehicle routing problem with time windows, the methodology is able to produce good results in short computation time. The methodology allows to combine the effectiveness of state-of-the-art multiobjective algorithms with the efficiency of goal programming to find good compromise solutions in problem scenarios where instances have similar fitness landscapes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。