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

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

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

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