OpenAIR @ RGU >
Design and Technology >
Theses (Computing) >
Please use this identifier to cite or link to this item:
|Title: ||Multivariate Markov networks for fitness modelling in an estimation of distribution algorithm.|
|Authors: ||Brownlee, Alexander Edward Ian|
|Supervisors: ||McCall, John|
|Keywords: ||Evolutionary algorithm|
Estimation of distribution algorithm
|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.