Oppositional Biogeography Based Optimization

Download or read book Oppositional Biogeography-based Optimization written by Mehmet Ergezer and published by . This book was released on 2014 with total page 181 pages. Available in PDF, EPUB and Kindle. Book excerpt: Abstract: This dissertation outlines a novel variation of biogeography-based optimization (BBO), which is an evolutionary algorithm (EA) developed for global optimization. The new algorithm employs opposition-based learning (OBL) alongside BBO migration to create oppositional BBO (OB BO). Additionally, a new opposition method named quasi-reflection is introduced. Quasireflection is based on opposite numbers theory and we mathematically prove that it has the highest expected probability of being closer to the problem solution among all OBL methods that we explore. Performance of quasi-opposition is validated by mathematical analysis for a single-dimensional problem and by simulations for higher dimensions. Experiments are performed on benchmark problems taken from the literature as well as real-world optimization problems provided by the European Space Agency. Empirical results demonstrate that with the assistance of quasi-reflection, OB BO significantly outperforms BBO in terms of success rate and the number of fitness function evaluations required to find an optimal solution for a set of standard continuous domain benchmarks. The oppositional algorithm is further revised by the addition of fitness dependent quasi-reflection which gives a candidate solution that we call ^xKr. In this algorithm, the amount of reflection is based on the fitness of the individual and can be non-uniform. We find that for small reflection weights, ^xKr has a higher probability of being closer to the solution, but only by a negligible amount. As the reflection weight increases, ^xKr gets closer (on average) to the solution of an optimization problem as the probability of being closer decreases. In addition, we extend the idea of opposition to combinatorial problems. We introduce two different methods of opposition to solve two types 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 graph-coloring 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 standard graph coloring and TSP benchmarks illustrate that incorporating opposition into BBO improves performance.