Open AccessAnt Decision Systems for Combinatorial Optimization with Binary Constraints
Author(s) -
Nicolas Zufferey
Publication year - 2020
Publication title -
international journal of computers and communications
Language(s) - English
Resource type - Journals
ISSN - 2074-1294
DOI - 10.46300/91013.2020.14.8
Subject(s) - metaheuristic , mathematical optimization , ant colony optimization algorithms , computer science , combinatorial optimization , ant colony , binary number , constructive , scheduling (production processes) , linear programming , mathematics , algorithm , process (computing) , arithmetic , operating system
In this paper is considered a problem (P) which consists in minimizing an objective function f while satisfying a set of binary constraints. Function f consists in minimizing the number of constraints violations. Problem (P) is NP-hard and has many applications in various fields (e.g., graph coloring, frequency assignment, satellite range scheduling). On the contrary to exact methods, metaheuristics are appropriate algorithms to tackle medium and large sized instances of (P). A specific type of ant metaheuristics is designed to tackle (P), where in contrast with state-of-the-art ant algorithms, an ant is a decision helper and not a constructive procedure.