改進遷徙策略的TriBA并行遺傳算法及其在TSP問題的應(yīng)用.pdf

1、巡回旅行商問題（TSP）是一個組合優(yōu)化方面的問題，已經(jīng)成為測試組合優(yōu)化新算法的標準問題。從理論上講，使用窮舉法不但可以求解TSP問題，而且還可以求出該問題的最優(yōu)解。但是對現(xiàn)有的計算機來說，使用常規(guī)窮舉法在如此龐大的搜索空間中尋求最優(yōu)解，幾乎是不可能的。所以，各種求解TSP問題的優(yōu)化算法應(yīng)運而生，適用于TSP巡回旅行商路徑優(yōu)化的算法有很多，例如模擬退火算法、人工魚群算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法等。
　　本課題主要圍繞TSP問題的路徑

2、尋優(yōu)問題展開研究，通過分析遺傳算法的利弊，得知并行遺傳算法（Parallel Genetic Algorithm）是一種有效解決帶有約束條件的TSP巡回旅行商問題的算法。針對并行遺傳算法解決本課題問題的缺陷，提出一種基于評價算子的TriBA并行遺傳算法。基于評價算子的TriBA并行遺傳算法主要在并行算法上做了三方面改進：
　　改變了拓撲結(jié)構(gòu)。通過新的種群分配方式，有效地解決了主從式結(jié)構(gòu)的負載不均衡問題。TriBA結(jié)構(gòu)是可擴展的，可

3、以根據(jù)種群大小，確定子種群的數(shù)目，有效地節(jié)約了硬件資源。
　　改變了數(shù)據(jù)遷徙方式。TriBA結(jié)構(gòu)中數(shù)據(jù)的遷徙方式包括全局遷徙方式，快速遷徙方式，局部遷徙方式和混合遷徙方式四種方式。改變了主從式拓撲結(jié)構(gòu)單一的數(shù)據(jù)遷徙方式，有助于最優(yōu)個體迅速傳播到每個子種群中。
　　提出了一種基于評價算子的遷徙操作。通過評價算子，可以反映當前種群的局部收斂程度，當局部收斂度滿足設(shè)定的評價算子時，再進行遷徙操作。實現(xiàn)了子種群最優(yōu)個體的異步遷徙，提