Evolutionary algorithms (EAs) are well-established techniques to approach those problems which for the classical optimization methods are difficult to solve. Tackling problems with mixed-type of variables, many local optima, undifferentiable or non-analytical functions are some examples to highlight the outstanding capabilities of the evolutionary algorithms. Among the various kinds of evolutionary algorithms, differential evolution (DE) is well known for its effectiveness and robustness. Many comparative studies confirm that the DE outperforms many other optimizers. Finding more accurate solution(s), in a shorter period of time for complex black-box problems, is still the main goal of all evolutionary algorithms. The opposition concept, on the other hand, has a very old history in philosophy, set theory, politics, sociology, and physics. But, there has not been any opposition-based contribution to optimization. In this thesis, firstly, the opposition-based optimization (OBO) is constituted. Secondly, its advantages are formally supported by establishing mathematical proofs. Thirdly, the opposition-based acceleration schemes, including opposition-based population initialization and generation jumping, are proposed. Fourthly, DE is selected as a parent algorithm to verify the acceleration effects of proposed schemes. Finally, a comprehensive set of well-known complex benchmark functions is employed to experimentally compare and analyze the algorithms. Results confirm that opposition-based DE (ODE) performs better than its parent (DE), in terms of both convergence speed and solution quality. The main claim of this thesis is not defeating DE, its numerous versions, or other optimizers, but to introduce a new notion into nonlinear continuous optimization via innovative metaheuristics, namely the notion of opposition. Although, ODE has been compared with six other optimizers and outperforms them overall. Furthermore, both presented experimental and mathematical results conform with each other and demonstrate that opposite points are more beneficial than pure random points for black-box problems; this fundamental knowledge can serve to accelerate other machine learning approaches as well (such as reinforcement learning and neural networks). And perhaps in future, it could replace the pure randomness with random-opposition model when there is no a priori knowledge about the solution/problem. Although, all conducted experiments utilize DE as a parent algorithm, the proposed schemes are defined at the population level and, hence, have an inherent potential to be utilized for acceleration of other DE extensions or even other population-based algorithms, such as genetic algorithms (GAs). Like many other newly introduced concepts, ODE and the proposed opposition-based schemes still require further studies to fully unravel their benefits, weaknesses, and limitations.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/2784 |
| Date | 25 April 2007 |
| Creators | Rahnamayan, Shahryar |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Format | 16147018 bytes, application/pdf |
Page generated in 0.0021 seconds