Investigation on Optimal Mixing With Linkage Sets and Its Application
Date Issued
2014
Date
2014
Author(s)
Wang, Shih-Ming
Abstract
The optimal mixing evolutionary algorithm (OM) utilizes a linkage set (LS) which is composed of a set of masks to exchange variables between a pair of solutions, and the result of such exchange is adopted only if the exchange leads to improvement of the solution quality. The performance of OM highly depends on the LS it utilizes. This thesis demonstrates that previously proposed LS, the linkage tree model (LT), does not yield the optimal performance. Further investigation shows that the effectiveness of each mask varies from generation to generation. To find out the best way of utilizing the masks, this thesis analyzes OM from the perspective of model efficiency and population sizing. Specifically, cost-performance (CP) index is proposed to measure the efficiency of a set of masks. If fixed population is used, OM with LSs of higher CP values require less number of function evaluations (NFEs). However, a LS with higher CP values might lead to larger population size for OM to solve the problem. Therefore, the effect of the masks on population sizing are considered to normalize CP index. Two algorithms named OMCPE1 and OMCPE2 are then proposed with normalized CP index as the mask selecting metric. Both OMCPE1 and OMCPE2 adopts two stage crossover. In the first stage, normalized CP values of the masks in the LT are estimated by performing the original crossover. In the second stage, masks of higher normalized CP values are utilized to generate solutions based on the solutions generated in the first stage. Generally speaking, the different methods of CP value estimation make OMCPE2 more robust than OMCPE1. Also, OMCPE2 outperforms OM with LT in terms of both NFEs and scalability on most tested fully separable problems. As for problems with overlap, although OMCPE2 still shows performance gain on more than half of the tested instances, it is less robust such that it might require much larger population size on some extreme instances.
Subjects
模形建構基因演算法
局部搜索
最佳混合
模型效率
族群成長
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-103-R01921055-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):965f03ea621cf9cf1ab6729734f1a686