New Hybrid Genetic Algorithms for Parameter Search

Research student:  Tarek El-Mihoob
Supervisors:Adrian Hopgood
 Lars Nolle
 Alan Battersby
PhD awarded:19 July 2006

Abstract from thesis

A genetic algorithm is a computational optimisation algorithm that is inspired by the principles of natural selection and genetic dynamics. Hybridising other optimisation techniques within the genetic algorithm framework can enhance the search performance. The chances of improving the performance of a hybrid depend on the details of its design.

This thesis aims to employ learning to utilise the genetic information that is readily available to maximise the effectiveness and the efficiency of a hybrid. Learning can be incorporated in different ways to achieve this goal. It can utilise solution-specific knowledge to improve its contribution in the search process. It can also utilise the direct and indirect influence of the design choices on the exploration-exploitation trade-off to adapt the search control parameters to a problem without external control.

This thesis examines the different hybrid design issues and their effect on the hybrid's performance. It contributes towards discovering the nature of the relations between the hybrid design choices and the hybrid's performance. The research demonstrates that the two main drawbacks of the basic learning models, which are the hindering effect and the diversity limitation, can be alleviated through adjusting the duration and the probability of local search. Some of the search method's features that enable it to be incorporated within a genetic search to accelerate finding high quality solutions are defined. They empower the search method to learn the nature of the search space through using the genetic information. An effective model with such features is also presented.

This thesis also investigates different ways of achieving a balance between exploration and exploitation. Utilising learning to make use of the direct influence of the details of the local method on this balance can help to find an optimal setup for this method. The investigation demonstrates the effectiveness of applying co-evolution for such utilisation. It also analyses the effect of using the fitness as productivity metric on the search's behaviour. It also illustrates the impact of the hindering effect on this mechanism and the possible ways to combat it. The research shows the effectiveness and the efficiency of employing evolution to use the indirect influence of the learning model on the utilisation of the search time for online learning of the effectiveness of the different learning strategies. It also explains the slow convergence of the evolutionary self-adaptive algorithms that adjust more than one control parameter based on the probabilities of introducing epistasis.

A novel form of hybridisation between ant-based and genetic-local hybrid algorithms is proposed. This work has demonstrated the ability of ant-based algorithms for reinforcement learning. They have been shown to be capable of finding, without any form of human intervention, an optimal setup for a genetic-local hybrid algorithm that can effectively and efficiently solve a given problem.

Return to Adrian Hopgood's page.

Valid HTML 4.01! Owner:
  Adrian Hopgood
  June 2013