最佳混合搭配鏈結集合之分析及其應用

Abstract

最佳混合演化式演算法(optimal mixing evolutionary algorithm)使用由一組遮罩組成的鏈結集合(linkage set)以交換一對解之間的變數,交換的結果僅當在交換造成解的品質進步時才會被採用。最佳混合演化式演算法的表現高度相依於其使用得鏈結集合。本論文展示了之前所提出稱為鏈結樹(linkage tree)的鏈結集合並沒有達到最好的表現。更進一步的研究指出,遮罩的效用隨著代數而改變。為了找出利用遮罩最好的方法,本論文從模型效率以及族群成長兩方面分析了最佳混合演化式演算法。具體而言,成本性能指標(cost-performance index)被提出並用以度量一組遮罩的效率。當族群大小固定時，最佳混合演化式演算法搭配擁有較高成本性能指標的鏈結集合所需的適應度函數計算次數較少。然而, 擁有較高成本性能指標的鏈結集合可能導致最佳混合演化式演算法需要較大的族群大小來解決問題。因此 遮罩對於族群成長的效果被納入考量以正規化成本性能指標。兩個名為OMCPE1及OMCPE2、利用正規化成本性能指標選擇遮罩 的演算法接著被提出。OMCPE1及OMCPE2兩者皆採用兩階段的交配。在第一階段，原本的交配被執行以估計鏈節樹遮罩的正規化成本性能指標之值。在第一階段產生的解的基礎下，第二階段用擁有較高正規化成本性能指標值的遮罩產生解。一般而言,不同估計成本性能指標的方法導致OMCPE2比OMCPE1更為穩 健。同樣的,在大部分測試的完全可分的問題(fully separable problem)上,OMCPE2比起最佳混合演化式演算法搭配鏈結樹，不僅在適應度函數計算次數上,在擴展性上也表現得更好。至於有重疊之問題(problems with overlap)，儘管OMCPE2在過半數測試的實例上仍展現了性能的增進，它卻較為不穩建。在一些極端的實例上，它會需要更大的族群大小。

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.