OpenAIR OpenAIR
 
 

OpenAIR @ RGU >
Design and Technology >
Computing >
Theses (Computing) >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10059/381
This item has been viewed 60 times in the last year. View Statistics

Files in This Item:

File Description SizeFormat
Alexander Brownlee thesis.pdf2.4 MBAdobe PDFView/Open
Title: Multivariate Markov networks for fitness modelling in an estimation of distribution algorithm.
Authors: Brownlee, Alexander Edward Ian
Supervisors: McCall, John
Brown, Deryck
Zhang, Qingfu
Keywords: Evolutionary algorithm
EDA
Estimation of distribution algorithm
Markov networks
Issue Date: May-2009
Publisher: The Robert Gordon University
Citation: BROWNLEE, A. E. I., MCCALL, J. A. W. and BROWN, D. F., 2007. Solving the MAXSAT problem using a multivariate EDA based on Markov networks. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007). 2007. New York: ACM Press. pp. 2423-2428.
BROWNLEE, A. E. I., MCCALL, J. A. W., ZHANG, Q. and BROWN, D., 2008. Approaches to selection and their effect on fitness modeling in an estimation of distribution algorithm. In: Proceedings of the IEEE World Congress on Computational Intelligence (CEC 2008). Piscataway, NJ: IEEE Press. pp. 2621-2628.
BROWNLEE, A. E. I., WU, Y., MCCALL, J. A. W., GODLEY, P. M., CAIRNS, D. E. and COWIE, J., 2008. Optimisation and fitness modelling of bio-control in mushroom farming using a Markov network EDA. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008). New York: ACM Press. pp. 465-466.
BROWNLEE, A. E. I., MCCALL, J. A. W., SHAKYA, S. K. and ZHANG, Q., 2009. Structure learning and optimisation in a Markov-network based estimation of distribution algorithm. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2009). Piscataway, NJ: IEEE Press. pp. 447-454.
WU, , Y., MCCALL, J., GODLEY, P., BROWNLEE, A. and CAIRNS, D., 2008. Bio-control in mushroom farming using a Markov network EDA. In: Proceedings of the IEEE World Congress on Computational Intelligence (CEC 2008). Piscataway, NJ: IEEE Press. pp. 2996-3001.
BROWNLEE, A. E. I., PELIKAN, M., MCCALL, J. A. W. and PETROVSKI, A., 2008. An application of a multivariate estimation of distribution algorithm to cancer chemotherapy. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008). New York: ACM Press. pp. 463-464.
SHAKYA, S. K., BROWNLEE, A. E. I., MCCALL, J. A. W., FOURNIER, F. and OWUSU, G., 2009. A fully multivariate DEUM algorithm. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2009). Piscataway, NJ: IEEE Press. pp. 479-486.
Abstract: A well-known paradigm for optimisation is the evolutionary algorithm (EA). An EA maintains a population of possible solutions to a problem which converges on a global optimum using biologically-inspired selection and reproduction operators. These algorithms have been shown to perform well on a variety of hard optimisation and search problems. A recent development in evolutionary computation is the Estimation of Distribution Algorithm (EDA) which replaces the traditional genetic reproduction operators (crossover and mutation) with the construction and sampling of a probabilistic model. While this can often represent a significant computational expense, the benefit is that the model contains explicit information about the fitness function. This thesis expands on recent work using a Markov network to model fitness in an EDA, resulting in what we call the Markov Fitness Model (MFM). The work has explored the theoretical foundations of the MFM approach which are grounded in Walsh analysis of fitness functions. This has allowed us to demonstrate a clear relationship between the fitness model and the underlying dynamics of the problem. A key achievement is that we have been able to show how the model can be used to predict fitness and have devised a measure of fitness modelling capability called the fitness prediction correlation (FPC). We have performed a series of experiments which use the FPC to investigate the effect of population size and selection operator on the fitness modelling capability. The results and analysis of these experiments are an important addition to other work on diversity and fitness distribution within populations. With this improved understanding of fitness modelling we have been able to extend the framework Distribution Estimation Using Markov networks (DEUM) to use a multivariate probabilistic model. We have proposed and demonstrated the performance of a number of algorithms based on this framework which lever the MFM for optimisation, which can now be added to the EA toolbox. As part of this we have investigated existing techniques for learning the structure of the MFM; a further contribution which results from this is the introduction of precision and recall as measures of structure quality. We have also proposed a number of possible directions that future work could take.
Appears in Collections:Theses (Computing)

All items in OpenAIR are protected by copyright, with all rights reserved.

 

 
   Disclaimer | Freedom of Information | Privacy Statement |Copyright ©2012 Robert Gordon University, Schoolhill, Aberdeen, AB10 1FR, Scotland, UK: a Scottish charity, registration No. SCO13781