- 學位論文
基於區塊之估計分配演算法應用於旅行推銷員問題
A Block-Based Estimation of Distribution Algorithms for Traveling Salesman Problem
摘要
演化式演算法最常用於求解組合性問題，其中大多數的演算法可求得不錯的求解品質。但隨著組合性問題的求解複雜度逐漸提升，因此，過去的演化式演算法容易產生過早收斂或失去群族多樣性的問題。傳統演化式演算法所求得的解是以適合度函數作為評判優劣，然而本研究進一步計算解的部分優勢資訊（區塊），藉由保留具有優勢資訊進而提升求解的效率。本研究提出一種新的演化式演算法稱之為基於區塊之演化式演算法（Block Based Evolutionary Algorithms, BBEAs），主要是透過估計分配演算法（Estimation of Distribution Algorithms, EDAs）建構的優勢矩陣，有效地找出具有優勢的區塊，並經由區塊組成具有競爭優勢的人造解，因此，所提出的演算法是兼具效率以及效果之萬用型演化式演算法。本研究透過組合性標竿問題中的旅行推銷員問題（Traveling Salesman Problem）來驗證BBEAs的求解品質，由實驗結果可知在Kro、Pr、PCB等系列問題上，BBEAs求解品質皆優於傳統演化式演算法。
並列摘要
Evolutionary algorithms are most often used to solve the combination problems. Most of the algorithms can achieve a good solution quality, but due to the combination of problems the complexity of solution is gradually increased, therefore, the evolution algorithm is likely to occur premature convergence or loss group of ethnic diversity. The solution obtained by the traditional evolutionary algorithm is based on fitness function. Further for some advantages of this study we implement some information (Block), by preserving the advantage of information which enhances the efficiency of solution. This study proposes a new evolutionary algorithm called Block Based Evolutionary Algorithms (BBEAs), which is based on Estimated of Distribution Algorithms (EDAs). The construction of EDAs is based on probability matrix which effectively identify blocks have better probability. To show the effectiveness of BBEAs, we apply this BBEAs on Travelling salesman Problem on different instances like Kro, Pr, and And PCB series. Based on experimental analysis we proposed that BBEAs have better solution quality than traditional evolutionary algorithm.