An investigation of the effects of local neighborhood structure on the performance of randomized optimization methods
LE3 .A278 2017
Master of Science
Mathematics and Statistics
Mathematics & Statistics
In this thesis we survey how some features of an optimization algorithm influence its performance on various objective functions. We employ randomness and iterative methods in the search by using stochastic optimization algorithms. In order to measure and fully compare the performance of these algorithms we implement a process of computing the average expected hitting time (AEHT) for all possible distinct objective functions on different structures. We perform an exhaustive study for a small numberof points in the state space (four, five, six, seven). In the first part of this thesis, we study the effects of local neighborhood structure on the performance of the (1+1) Evolutionary algorithm (EA). The neighborhood structure is given by the details of the mutation operator, and so we are really studying the effectiveness of different mutations. The (1+1)EA is same as the rest of local search algorithms which get stuck in the local minimum. One fact about using (1+1)EA is that the AEHT is infinite if and only if the objective function has a local minimum. Thus, in terms of the total edges that are missing we distinguish the preferable structure that produces fewer objective functions that lead to infinite AEHT. In the second part of this thesis, we modify (1+1)EA with a new version of this algorithm, and we call it the q-algorithm, allowing an uphill step but with a probability of q. For q > 0, AEHT is always finite. Significantly, there are cases when (1+1)EA gives a finite AEHT for some objective functions but the q-algorithm gives an even smaller value.
The author retains copyright in this thesis. Any substantial copying or any other actions that exceed fair dealing or other exceptions in the Copyright Act require the permission of the author.