Oppositional Biogeography-Based Optimization for Combinatorial Problems
IEEE Congress on Evolutionary Computation
In this paper, we propose a framework for employing opposition-based learning to assist evolutionary algorithms in solving discrete and combinatorial optimization problems. To our knowledge, this is the first attempt to apply opposition to combinatorics. We introduce two different methods of opposition to solve two different type of combinatorial optimization problems. The first technique, open-path opposition, is suited for combinatorial problems where the final node in the graph does not have be connected to the first node, such as the graphcoloring problem. The latter technique, circular opposition, can be employed for problems where the endpoints of a graph are linked, such as the well-known traveling salesman problem (TSP). Both discrete opposition methods have been hybridized with biogeography-based optimization (BBO). Simulations on TSP benchmarks illustrate that incorporating opposition into BBO improves its performance. Index Terms—Biogeography-based optimization, opposition, combinatorics, discrete optimization, evolutionary algorithms, graph-coloring problem, traveling salesman problem.
Ergezer, Mehmet and Simon, Daniel J., "Oppositional Biogeography-Based Optimization for Combinatorial Problems" (2011). Electrical Engineering & Computer Science Faculty Publications. 161.
M. Ergezer and D. Simon. (2011). Oppositional Biogeography-Based Optimization for Combinatorial Problems. IEEE Congress on Evolutionary Computation, 1496–1503,