Mayowa Ayodele
Effective and efficient estimation of distribution algorithms for permutation and scheduling problems.
Ayodele, Mayowa
Authors
Contributors
Professor John McCall j.mccall@rgu.ac.uk
Supervisor
Olivier Regnier-Coudert
Supervisor
Abstract
Estimation of Distribution Algorithm (EDA) is a branch of evolutionary computation that learn a probabilistic model of good solutions. Probabilistic models are used to represent relationships between solution variables which may give useful, human-understandable insights into real-world problems. Also, developing an effective PM has been shown to significantly reduce function evaluations needed to reach good solutions. This is also useful for real-world problems because their representations are often complex needing more computation to arrive at good solutions. In particular, many real-world problems are naturally represented as permutations and have expensive evaluation functions. EDAs can, however, be computationally expensive when models are too complex. There has therefore been much recent work on developing suitable EDAs for permutation representation. EDAs can now produce state-of-the-art performance on some permutation benchmark problems. However, models are still complex and computationally expensive making them hard to apply to real-world problems. This study investigates some limitations of EDAs in solving permutation and scheduling problems. The focus of this thesis is on addressing redundancies in the Random Key representation, preserving diversity in EDA, simplifying the complexity attributed to the use of multiple local improvement procedures and transferring knowledge from solving a benchmark project scheduling problem to a similar real-world problem. In this thesis, we achieve state-of-the-art performance on the Permutation Flowshop Scheduling Problem benchmarks as well as significantly reducing both the computational effort required to build the probabilistic model and the number of function evaluations. We also achieve competitive results on project scheduling benchmarks. Methods adapted for solving a real-world project scheduling problem presents significant improvements.
Citation
AYODELE, M. 2018. Effective and efficient estimation of distribution algorithms for permutation and scheduling problems. Robert Gordon University, PhD thesis.
Thesis Type | Thesis |
---|---|
Publication Date | May 1, 2018 |
Deposit Date | Aug 31, 2018 |
Publicly Available Date | Aug 31, 2018 |
Keywords | Estimation of distribution algorithm; Probabilistic model; Random key; Genetic algorithm; Real world project scheduling problem; Optimisation; Gaussian distribution; Permutation flowshop scheduling problem |
Public URL | http://hdl.handle.net/10059/3102 |
Files
AYODELE 2018 Effective and efficient estimation
(4 Mb)
PDF
Publisher Licence URL
https://creativecommons.org/licenses/by-nc/4.0/
Copyright Statement
Copyright: the author and Robert Gordon University
You might also like
An analysis of indirect optimisation strategies for scheduling.
(2018)
Conference Proceeding
Performance analysis of GA and PBIL variants for real-world location-allocation problems.
(2018)
Conference Proceeding
Estimation of distribution algorithms for the multi-mode resource constrained project scheduling problem.
(2017)
Conference Proceeding
A random key based estimation of distribution algorithm for the permutation flowshop scheduling problem.
(2017)
Conference Proceeding
BPGA-EDA for the multi-mode resource constrained project scheduling problem.
(2016)
Conference Proceeding