分散式基因演算法應用於旅行家銷售員問題

distributed genetic algorithm apply to travel salesman problem

李捷隆(Chieh-Lung Lee)

指導教授 ： 阮議聰

中原大學/工學院/資訊工程研究所/碩士(2004年)

https://doi.org/10.6840/cycu200400710

摘要

在本論文中我們提出一個分散式基因演算法系統來處理旅行家銷售員問題，主要目的是為了將單機版的基因演算法，做有效的分散處理，使得最終求得的解精確度能提升。在資料的遷移方面採用兩種方式，分別為同步及非同步，並比較在最後的最佳解的差異 。
在非同步遷移(asynchronous migration)部分，提出了一個全區域基因池的方法，與一般的island model分散式基因演算法在各節點間做遷移有些差異，本文的非同步分散式所有的遷移都是發生在master節點與其他slave節點之間，且利用每次的遷移過程進化整個基因池，使池內的解越來越優良;另外也比較了許多參數組合對演算法結果的影響，在單機版如: 選擇方法、交配率、突變率、最佳解保留率;分散式的部分如: 遷移的拓璞排列方式、遷移的時機等等..並對這些參數的影響提出討論 。
最後討論此系統的等倍增長性效能，以及提出此系統優缺點的探討跟未來的發展空間 。
關鍵字: 基因演算法、分散式系統、旅行家銷售員問題、非同步分散式基因演算法

關鍵字

非同步分散式基因演算法 ； 分散式系統 ； 基因演算法 ； 旅行家銷售員問題

並列摘要

In this paper, we propose a distributed genetic algorithm to solve Travel Salesman Problem , The purpose is to parallelize serial GA efficiently and then the final answer could be more acceptable .For Data migration method , we use asynchronous and synchronous ways to implement migration , and do some experiments to compare the results .
In asynchronous migration , we present a global gene pool in the master node for all slaves , while migration happen between master and slave , the gene pool get better individual and raise it’s value , that kind of evaluation is not the same with normal island model DGA .
In Chapter 5 we do some experiments to test the best combination of parameters like crossover rate , mutation rate , best keep rate ,and selection methods. With DGA we discuss the topology , migration interval that make influence with the final result.
Finally we test the system scalability to check if this system is extendable . Discuss the disadvantage and how to conquer it in the future.

Keywords: Genetic Algorithm , Travel Salesman Problem , Distributed GA , Asynchronous migration

並列關鍵字

Travel Salesman Problem ； Genetic Algorithm ； Asynchronous migration ； Distributed GA

參考文獻

[1] “A survey of recoverable distributed shared virtual memory systems”

[3] “Solving the traveling salesman problem with annealing-based heuristics: a computational study” Pepper, J.W.; Golden, B.L.; Wasil, E.A.;Systems, Man and Cybernetics, Part A, IEEE Transactions on , Volume: 32 , Issue: 1 , Jan. 2002 Pages:72 – 77

[4] “Genetic algorithms: a survey” Srinivas, M.; Patnaik, L.M.;Computer , Volume: 27 , Issue: 6 , June 1994 Pages:17 – 26

[7] “Generation expansion planning based on an advanced evolutionary programming” Young-Moon Park; Jong-Ryul Won; Jong-Bae Park; Dong-Gee Kim;Power Systems, IEEE Transactions on , Volume: 14 , Issue: 1 , Feb. 1999 Pages:299 - 305

[8]Donald L. Kreher, Douglas R. Stinson,”COMBINATORIAL ALGORITHMS Generation, Enumeration, and Search”,1999,pp.163-185