Multi-armed Bandit Based Evolutionary Model Adaptation for Permutation Problems
Date Issued
2014
Date
2014
Author(s)
Hsu, Chu-Yu
Abstract
This thesis has provided a framework of model adaptation for estimation of distribution algorithms (EDA) on permutation problems.
Characterized by the use of probabilistic models to represent the solutions and the dependencies between the variables of the problem, EDAs are known as powerful evolutionary algorithms that have been widely used for diverse types of problems.
However, since the semantics of permutation problems differs, each model developed for EDAs can only deal with a subset of permutation problems.
The performance suffers from inappropriate model choice.
Furthermore, permutation problem may go beyond the existing models can handle.
Motivated by these difficulties mentioned above, several model adaptation frameworks, which incorporate multiple models and dynamically decide to use which model, are trialled.
In the first trial, the enumeration method samples multiple models simultaneously and shows better performance on Linear Ordering Problem.
To reduce the waste of sampling unpromising models, the Bayesian method has been proposed characterized by measuring the
quality of each model.
However, the Bayesian method tends to choose inappropriate model because of the selection and the template mechanism.
Considering the similarity between model adaptation and multi-armed bandit problem, a multi-armed bandit based model adaptation framework has been proposed.
In order to prove the potential of the proposed framework, different permutation problems have been tested.
The results show that the proposed framework outperforms the other single model EDA on problems that don''t have dedicated models like the vehicle routing problem with time window, and is close to the EDAs with dedicated models on the specific problem like the traveling salesman problem.
Subjects
分配估計演算法
模型適應
排列問題
多臂吃角子老虎問題
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-103-R01921096-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):4a7ddb7043645ba743434f285bf4cc94