A comparative study of population-based algorithms for a political districting problem. Issue 1 (9th January 2017)

• Record Type: Journal Article
• Authors: Rincón-García, Eric Alfredo; Gutiérrez-Andrade, Miguel Ángel; de-los-Cobos-Silva, Sergio Gerardo; Mora-Gutiérrez, Roman Anselmo; Ponsich, Antonin; Lara-Velázquez, Pedro
• Is Part Of: Kybernetes. Volume 46:Issue 1(2017)
• Page Start: 172
• Page End: 190
• Publication Date: 2017-01-09
• Subjects: Simulated annealing -- Particle swarm optimization -- Artificial bee colony -- Districting -- Method of musical composition; Cybernetics -- Periodicals; Systems engineering -- Periodicals; 003.505
• DOI: 10.1108/K-06-2016-0130
• Languages: English
• ISSNs: 0368-492X

Abstract

Abstract : Purpose: This paper aims to propose comparing the performance of three algorithms based on different population-based heuristics, particle swarm optimization (PSO), artificial bee colony (ABC) and method of musical composition (DMMC), for the districting problem. Design/methodology/approach: In order to compare the performance of the proposed algorithms, they were tested on eight instances drawn from the Mexican electoral institute database, and their respective performance levels were compared. In addition, a simulated annealing-based (simulated annealing – SA) algorithm was used as reference to evaluate the proposed algorithms. This technique was included in this work because it has been used for Federal districting in Mexico since 1994. The performance of the algorithms was evaluated in terms of the quality of the approximated Pareto front and efficiency. Regarding solution quality, convergence and dispersion of the resulting non-dominated solutions were evaluated. Findings: The results show that the quality and diversification of non-dominated solutions generated by population-based algorithms are better than those produced by Federal Electoral Institute's (IFE's) SA-based technique. More accurately, among population-based techniques, discrete adaptation of ABC and MMC outperform PSO. Originality/value: The performance of three population-based techniques was evaluated for the districting problem. In this paper, the authors used the objective function proposed by the Mexican IFE, a weight aggregation function that seeks for a districting plan that represents the best balance between population equality and compactness. However, the weighting factors can be modified by political agreements; thus, the authors decided to produce a set of efficient solutions, using different weighting factors for the computational experiments. This way, the best algorithm will produce high quality solutions no matter the weighting factors used for a real districting process. The computational experiments proved that the proposed artificial bee colony and method of musical composition-based algorithms produce better quality efficient solutions than its counterparts. These results show that population-based algorithms can outperform traditional local search strategies. Besides, as far as we know, this is the first time that the method of musical composition is used for this kind of problems.