Hybridizing metaheuristics for multi-and many-objective problems in a multi-agent architecture

Abstract

Hybrid algorithms combine the best features of individual metaheuristics. They have proven to find high-quality solutions for multi-objective optimization problems. Architec- tures provide generic functionalities and features for implementing new hybrid algorithms to solve arbitrary optimization problems. Architectures based on agent intelligence and multi-agent concepts, such as learning and cooperation, give several benefits for hybridiz- ing metaheuristics. Nevertheless, there is a lack of studies on architectures that fully explore these concepts for multi-objective hybridization. This thesis studies a multi-agent architecture named MO-MAHM, inspired by Particle Swarm Optimization concepts. In the MO-MAHM, particles are intelligent agents that learn from past experiences and move in the search space, looking for high-quality solutions. The main contribution of this work is to study the MO-MAHM potential to hybridize metaheuristics for solving combinatorial optimization problems with two or more objectives. We investigate the benefits of machine learning methods for agents’ learning support and propose a novel velocity operator for moving the agents in the search space. The proposed velocity operator uses a path-relinking technique and decomposes the objective space without requiring aggregation functions. Another contribution of this thesis is an extensive survey of existing multi-objective path-relinking techniques. Due to a lack in the literature of effective multi- and many-objective path-relinking techniques, we present a novel decomposition-based one, referred to as MOPR/D. Experiments comprise three differently structured combi- natorial optimization problems with up to five objective functions: 0/1 multidimensional knapsack, quadratic assignment, and spanning tree. We compared the MO-MAHM with existing hybrid approaches, such as memetic algorithms and hyper-heuristics. Statistical tests show that the architecture presents competitive results regarding the quality of the approximation sets and solution diversity.