Date of Award

2014

Degree Type

Dissertation

Department

Electrical and Computer Engineering

First Advisor

Simon, Dan

Subject Headings

Biogeography -- Mathematical models, Computer algorithms, Evolutionary computation, Mathematical optimization, Opposition, Theory of, evolutionary algorithms, optimization, opposition

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

Download
COinS