Title: Differential evolution for a constrained combinatorial optimisation problem

Authors: Marcus Randall

Addresses: School of Information Technology, Bond University, University Drive, Queensland 4229, Australia

Abstract: Differential evolution (DE) has been extensively applied to continuous problems, its mechanics naturally lending themselves to such. While some efforts have been made to adapt it to combinatorial problems, these have largely been problem specific and have not dealt extensively with constraint handling beyond penalty approaches. In this paper, a simple and generic strategy, relying on pre-developed heuristic units, is applied to DE and the generalised assignment problem. In addition, a simple, parameter-free approach to adapting control parameters is used. The results are competitive with other well established meta-heuristics. However, there is still scope for further improvement in the way that DE may be applied to constrained combinatorial optimisation.

Keywords: differential evolution; constrained combinatorial optimisation; extremal optimisation; generalised assignment problem; GAP; constraint handling.

DOI: 10.1504/IJMHEUR.2011.044302

International Journal of Metaheuristics, 2011 Vol.1 No.4, pp.279 - 297

Received: 15 Sep 2010
Accepted: 21 Jun 2011

Published online: 28 Feb 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article