A New Genetic Algorithm Encoding for Coalition Structure Generation Problems
Journal
Mathematical Problems in Engineering
ISSN
1024-123X
1563-5147
Date Issued
2020
Author(s)
Juan Pablo Contreras
Franco Basso
Type
Resource Types::text::journal::journal article
Abstract
Genetic algorithms have proved to be a useful improvement heuristic for tackling several combinatorial problems, including the coalition structure generation problem. In this case, the focus lies on selecting the best partition from a discrete set. A relevant issue when designing a Genetic algorithm for coalition structure generation problems is to choose a proper genetic encoding that enables an efficient computational implementation. In this paper, we present a novel hybrid encoding, and we compare its performance against several genetic encoding proposed in the literature. We show that even in difficult instances of the coalition structure generation problem, the proposed approach is a competitive alternative to obtaining good quality solutions in reasonable computing times. Furthermore, we also show that the encoding relevance increases as the number of players increases.
Subjects
computational efficiency
;
encoding (symbols)
;
genetic algorithms
;
heuristic algorithms
;
coalition structure
;
combinatorial problem
;
computational implementations
;
difficult instances
;
discrete sets
;
genetic encoding
;
hybrid encoding
;
new genetic algorithms
;
signal encoding