TriBA拓?fù)浣Y(jié)構(gòu)的并行遺傳算法研究與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ò)分析遺傳算法的利弊，得出主從式并行遺傳算法（M-SPGA）是一種有效解決帶有約束條件的TSP巡回旅行商問(wèn)題的算法。針對(duì)主從式并行遺傳算法模型解決本課題問(wèn)題的缺陷，提出一種新的TriBA拓?fù)浣Y(jié)構(gòu)的并行遺傳算法模型。TriBA拓?fù)浣Y(jié)構(gòu)的并行遺傳算法模型主要在主從式并行算法模型上做了兩方面改進(jìn)：
　　1.改變了數(shù)據(jù)遷徙方式。TriBA結(jié)構(gòu)中數(shù)據(jù)的遷徙流水方式包括單流水，并行流水，中心流水和流水嵌套四種方式。改變了主

3、從式拓?fù)浣Y(jié)構(gòu)單一的數(shù)據(jù)遷徙方式，有助于最優(yōu)個(gè)體迅速傳播到每個(gè)子種群中。
　　2.改變了拓?fù)浣Y(jié)構(gòu)。通過(guò)新的種群分配方式，有效地解決了主從式結(jié)構(gòu)的負(fù)載不均衡問(wèn)題。TriBA結(jié)構(gòu)是可擴(kuò)展的，可以根據(jù)種群大小，確定子種群的數(shù)目，有效地節(jié)約了硬件資源。
　　利用TriBA結(jié)構(gòu)的并行遺傳算法模型求解城市規(guī)模20*20的TSP問(wèn)題，進(jìn)行適應(yīng)度函數(shù)計(jì)算，交叉、變異操作和遷徙操作，可以成功的尋找到TSP問(wèn)題的最優(yōu)路徑。通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)的分析，對(duì)