Abstract
Tabu search is a widely used heuristic search method. One of the main components of tabu search is tabu list, which makes several latest moves forbidden in order to escape from a small loop. The algorithm starts from an initial solution, and moves the current solution to the best neighborhood which is not forbidden. These iterations will be repeated until the terminating condition is reached. There are two main drawbacks in the traditional tabu search. First, tabu search only provides an approximate solution. There is no way to know the quality of the obtained solutions. Second, although tabu list helps the search avoiding a small cycling problem, it cannot prevent a previously searched area to be searched again or forming a large cycle.The computation efficiency of a tabu search can be improved by implementing a parallel tabu search, which uses multiple processors to search in parallel. In the study, we propose an enhanced parallel tabu search, which attempts to compute more efficiently and conquer the two drawbacks mentioned above. The ratio of finding the old local optimum solutions may suggest the confidence level of the best solution we find at the end of search. Also, the historical memory of local optimum solutions helps us to avoid searching old areas again.To validate the efficiency of the new approach, we will use a series of number sequencing problems. In addition, we apply statistical method to test the suggested relationship between the ratio of old local optimum and the confidence level of the obtained solution. The result of experiments shows that it takes less time for the enhanced parallel tabu search to find global optimum solutions than conventional one. The ratio of finding the old local optimums does not precisely estimates the confidence level of the best solution. However, our results show that the probability of finding the global optimal solutions should be larger than the computed ratio.1.1研究背景 11.2研究動機 11.3研究架構 3第2章 文獻回顧 42.1塔布搜尋法 42.2平行塔布搜尋法 92.3塔布搜尋效率的改善方法 11第3章 方法構建 133.1改進之平行塔布搜尋法 133.1.1子空間的定義 133.1.2隨機起始解 143.1.3長期記憶結構 153.1.4落入涵蓋區域的比率 163.2改進之平行處理演算法 193.3改進之平行塔布搜尋法的優點 23第4章 實驗設計與分析 244.1問題描述 244.1.1多個處理器的模擬方法 244.1.2數字排序問題 254.2 求解數字排序問題的改進之平行塔布搜尋法的設定 264.3 離開舊區域最佳解後脫離方向的比較 274.4涵蓋比率的實驗設計 294.4.1落入涵蓋區域的比率的實驗 294.4.2驗證子空間是否為均勻的分佈 324.5比較搜尋速度的實驗結果與分析 35第5章 結論與未來展望 38參考文獻 39