Effective anytime algorithm for multiobjective combinatorial optimization problems
In multiobjective optimization, the result of an optimization algorithm is a set of efficient solutions from which the decision maker selects one. It is common that not all the efficient solutions can be computed in a short time and the search algorithm has to be stopped prematurely to analyze the solutions found so far. A set of efficient solutions that are well-spread in the objective space is preferred to provide the decision maker with a great variety of solutions. However, just a few exact algorithms in the literature exist with the ability to provide such a well-spread set of solutions at any moment: we call them anytime algorithms. We propose a new exact anytime algorithm for multiobjective combinatorial optimization combining three novel ideas to enhance the anytime behavior. We compare the proposed algorithm with those in the state-of-the-art for anytime multiobjective combinatorial optimization using a set of 480 instances from different well-known benchmarks and four different performance measures: the overall non-dominated vector generation ratio, the hypervolume, the general spread and the additive epsilon indicator. A comprehensive experimental study reveals that our proposal outperforms the previous algorithms in most of the instances.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationMultiobjective OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Pareto Set Learning for Neural Multi-objective Combinatorial Optimization
Multiobjective combinatorial optimization (MOCO) problems can be found in many real-world applications. However, exactly solving these problems would be very challenging, particularly when they are NP-hard. Many handcraf…
Combinatorial OptimizationTraveling Salesman ProblemPreference Conditioned Neural Multi-objective Combinatorial Optimization
Multiobjective combinatorial optimization (MOCO) problems can be found in many real-world applications. However, exactly solving these problems would be very challenging, particularly when they are NP-hard. Many handcraf…
Combinatorial OptimizationTraveling Salesman ProblemAED: An Anytime Evolutionary DCOP Algorithm
Evolutionary optimization is a generic population-based metaheuristic that can be adapted to solve a wide variety of optimization problems and has proven very effective for combinatorial optimization problems. However, t…
Combinatorial OptimizationMODRL/D-EL: Multiobjective Deep Reinforcement Learning with Evolutionary Learning for Multiobjective Optimization
Learning-based heuristics for solving combinatorial optimization problems has recently attracted much academic attention. While most of the existing works only consider the single objective problem with simple constraint…
Combinatorial OptimizationDeep Reinforcement LearningMultiobjective Optimizationreinforcement-learning+1Experimental Analysis of Design Elements of Scalarizing Functions-based Multiobjective Evolutionary Algorithms
In this paper we systematically study the importance, i.e., the influence on performance, of the main design elements that differentiate scalarizing functions-based multiobjective evolutionary algorithms (MOEAs). This cl…
Combinatorial OptimizationEvolutionary Algorithms