改進(jìn)粒子群算法求解TSP問(wèn)題

1、第五屆“挑戰(zhàn)杯”廣西大學(xué)生課外學(xué)術(shù)科技作品申報(bào)書(shū)序號(hào)：編碼： 第五屆挑戰(zhàn)杯”廣西大學(xué)生課外學(xué)術(shù)科技作品競(jìng)賽作品申報(bào)書(shū)作品名稱：基于 k-means 的改進(jìn)粒子群算法求解 TSP問(wèn)題學(xué)校全稱：河池學(xué)院申報(bào)者姓名（集體名稱）：陳國(guó)鴻類(lèi)別：超然科學(xué)類(lèi)學(xué)術(shù)論文哲學(xué)社會(huì)科學(xué)類(lèi)社會(huì)調(diào)查報(bào)告和學(xué)術(shù)論文口科技發(fā)明制作A類(lèi)口科技發(fā)明制作B類(lèi)說(shuō)明1 申報(bào)者應(yīng)認(rèn)真閱讀此說(shuō)明各項(xiàng)內(nèi)容后按要求詳細(xì)填寫(xiě)。2 申報(bào)者在填寫(xiě)申報(bào)作品情況時(shí)只需根據(jù)個(gè)人項(xiàng)目或集體項(xiàng)目填寫(xiě) A1 或 A2 表，根據(jù)作品類(lèi)別（自然科學(xué)類(lèi)學(xué)術(shù)論文、哲學(xué)社會(huì)科學(xué)類(lèi)社會(huì)調(diào)查報(bào)告和學(xué)術(shù)論文、 科技發(fā)明制作） 分別填寫(xiě) B1 、 B2 或 B3 表。所有申報(bào)

2、者可根據(jù)情況填寫(xiě) C 表。3 表內(nèi)項(xiàng)目填寫(xiě)時(shí)一律用鋼筆或打印， 字跡要端正、 清楚，此申報(bào)書(shū)可復(fù)制。4 序號(hào)、編碼由第五屆“挑戰(zhàn)杯”廣西大學(xué)生課外學(xué)術(shù)科技作品競(jìng)賽組委會(huì)填寫(xiě)。5 學(xué)術(shù)論文、社會(huì)調(diào)查報(bào)告及所附的有關(guān)材料必須是中文（若是外文，請(qǐng)附中文版） ，請(qǐng)以四號(hào)楷體打印在A4 紙上，附于申報(bào)書(shū)后，字?jǐn)?shù)在8000字左右（文章版面尺寸14.5X22cm ）。6 參賽作品（數(shù)量參照通知）各一式叁份分別按組委會(huì)規(guī)定的時(shí)間報(bào)至組委會(huì)秘書(shū)處。7 作品申報(bào)書(shū)須按要求由各校競(jìng)賽組織協(xié)調(diào)機(jī)構(gòu)統(tǒng)一寄送。8 其他參賽事宜請(qǐng)向本校競(jìng)賽組織協(xié)調(diào)機(jī)構(gòu)咨詢。9 寄送地址：南寧市古城路4 號(hào)共青團(tuán)廣西區(qū)委學(xué)校部。聯(lián) 系 人：

3、 廖梅宣聯(lián)系電話： （辦公）（手機(jī)）傳 真：郵政編碼： 530022A1.申報(bào)者情況（個(gè)人項(xiàng)目）說(shuō)明：1.必須由申報(bào)者本人按要求填寫(xiě)，申報(bào)者情況欄內(nèi)必須填寫(xiě)個(gè)人作品的第一作者（承擔(dān)申報(bào)作品 60%以上的工作者）2 .本表中的學(xué)籍管理部門(mén)簽章視為對(duì)申報(bào)者情況的確認(rèn)。姓名陳國(guó)鴻性別男出生年月1986年7月中 報(bào) 者 情 況學(xué)校全稱河池學(xué)院專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)現(xiàn)學(xué)歷本科年級(jí)大四學(xué)制4年入學(xué)時(shí)間2007年9月作品全稱基于k-means的改進(jìn)粒子群算法求解TSP問(wèn)題畢業(yè)論文 題目改進(jìn)粒子群算法求解TSP問(wèn)題通訊地址廣西宜州市龍江路42號(hào)河池學(xué)院計(jì)信系郵政編碼546300單位電話0778 常住地 通訊地址

4、廣西宜州市龍江路42號(hào)河池學(xué)院計(jì)信系郵政編碼546300住宅電話0778 合 作 者 情 況姓名性別年齡學(xué)歷所在單位資 格 認(rèn) 士學(xué)校學(xué)籍 管理部門(mén) 意見(jiàn)是否為2011年7月1日前正式注冊(cè)在校的全日制非成 人教育、非在職的各類(lèi)高等院校學(xué)生（含?？粕?、本科生和 研究生）。文 口否若是，其學(xué)號(hào)為：2007107201 （簽章）2011年4月23日院系負(fù)責(zé) 人或?qū)?意見(jiàn)本作品是否為課外學(xué)術(shù)科技或社會(huì)實(shí)踐活動(dòng)成果必是 否負(fù)責(zé)人簽名：2011年4月25日B1.申報(bào)作品情況（自然科學(xué)類(lèi)學(xué)術(shù)論文）說(shuō)明：1.必須由申報(bào)者本人填寫(xiě)。2 .本部分中科研管理部門(mén)簽章視為對(duì)申報(bào)者所填內(nèi)容的確認(rèn)。3 .作品分類(lèi)請(qǐng)按作

5、品學(xué)術(shù)方向或所涉及的主要學(xué)科領(lǐng)域填寫(xiě)。4 .碩士研究生、博士研究生作品不在此列。作品全稱改進(jìn)粒子群算法求解TSP問(wèn)題（8） A.機(jī)械與控制（包括機(jī)械、儀器儀表、自動(dòng)化控制、工程、交通、建筑等）B.信息技術(shù)（包括計(jì)算機(jī)、電信、通訊、電子等）C.數(shù)理（包括數(shù)學(xué)、物理、地球與空間科學(xué)等）作品分類(lèi)D.生命科學(xué)（包括生物、農(nóng)學(xué)、藥學(xué)、醫(yī)學(xué)、健康、衛(wèi)生、食品等）E.能源化工（包括能源、材料、石油、化學(xué)、化工、生態(tài)、環(huán)保等）旅行商問(wèn)題（TSP）又名貨郎擔(dān)問(wèn)題，是一個(gè)典型的 NP難題。其數(shù)學(xué)描 述非常簡(jiǎn)單，但卻無(wú)法找到一個(gè)確定的算法在多項(xiàng)式時(shí)間內(nèi)求解 TSP問(wèn)題, 另一方面很多研究領(lǐng)域出現(xiàn)的復(fù)雜優(yōu)化問(wèn)題可以被

6、抽象概括為 TSP問(wèn)題加 以求解，因此找到能夠有效解決 TSP問(wèn)題的方法，在理論上和實(shí)際應(yīng)用中都作品撰寫(xiě)的目 的和基本思路很有價(jià)值。本文對(duì)基本PSO算法中粒子的位置、速度以及操作進(jìn)行了重新定義，使粒子群算法適合于求解TSP問(wèn)題，并采用貪心算法的思想每一步都取局部 最優(yōu)。這樣產(chǎn)生的初始種群全局最優(yōu)值已經(jīng)比較接近問(wèn)題的解，因此可以節(jié) 省搜索時(shí)間，提高算法收斂速度。針對(duì)粒子群算法易陷入局部最優(yōu)的缺陷，引入了適合于求解TSP問(wèn)題的基于 k-means的改進(jìn)措施，對(duì)粒子群進(jìn)行聚類(lèi)分析，實(shí)現(xiàn)了粒子之間的信息交換，擴(kuò)大了粒子的搜索空間，克服了 PSO算法易陷入局部最優(yōu)的缺陷。兩個(gè)種群同時(shí)尋優(yōu)，種群內(nèi)部獨(dú)立進(jìn)

7、行PSO進(jìn)化，種群個(gè)體最優(yōu)之間以一定概率進(jìn)行交叉。兩個(gè)種群同時(shí)尋優(yōu)可以減小 算法陷入局部最優(yōu)的概率，種群間個(gè)體最優(yōu)的交叉能夠增強(qiáng)兩種群間以及粒 子間的信息共享，及時(shí)傳遞最優(yōu)值信息，提高粒子向更好解進(jìn)化的速度。最后本文對(duì)30點(diǎn)TSP問(wèn)題進(jìn)行仿真測(cè)試，試驗(yàn)表明改進(jìn)后的粒子群算法能肩效地求解TSP問(wèn)題。乍品的科學(xué)性、 先進(jìn)性及獨(dú)特 之處粒子群優(yōu)化（簡(jiǎn)稱PSO）算法在多維連續(xù)優(yōu)化問(wèn)題的應(yīng)用中取得了較好 的效果，但在旅行商（簡(jiǎn)稱TSP問(wèn)題）等組合優(yōu)化問(wèn)題中的應(yīng)用則相對(duì)較少。 為使粒子群算法適合于求解 TSP問(wèn)題本義對(duì)基本PSO算法中粒子的位置、 速度以及操作進(jìn)行了重新定義。初始種群的產(chǎn)生借鑒貪心算法的思

8、想，每一 步都取局部最優(yōu)。這樣產(chǎn)生的初始種群全局最優(yōu)值已經(jīng)比較接近問(wèn)題的解， 因此可以節(jié)省搜索時(shí)間，提高算法收斂速度。針對(duì)粒子群算法易陷入局部最 優(yōu)的缺陷，提出了適合旅行商問(wèn)題的基于 k-means的改進(jìn)措施。采用 k-means對(duì)粒子群進(jìn)行聚類(lèi)分析，實(shí)現(xiàn)了粒子之間的信息交換，擴(kuò)大了粒子 的搜索空間，避免了算法陷入局部最優(yōu)。兩個(gè)種群同時(shí)尋優(yōu)，種群內(nèi)部獨(dú)立 進(jìn)行PSO進(jìn)化，種群個(gè)體最優(yōu)之間以f 概率進(jìn)行交叉，減小算法陷入局 部最優(yōu)的概率，種群間個(gè)體最優(yōu)的交叉能夠增強(qiáng)兩種群間以及粒子間的信息 共享，及時(shí)傳遞最優(yōu)值信息，提高粒子向更好解進(jìn)化的速度。作品的實(shí)際應(yīng) 用價(jià)值和現(xiàn)實(shí) 意義TSP問(wèn)題是一種典型

9、的組合優(yōu)化問(wèn)題，是一種用來(lái)驗(yàn)證算法肩效性的典型算例。由于TSP最優(yōu)解的求解代價(jià)是指數(shù)級(jí)的，因此該問(wèn)題吸引了生物、 物理、數(shù)學(xué)、運(yùn)籌學(xué)、人工智能等諸多領(lǐng)域的研究者，對(duì)其近似解的研究一 直是算法設(shè)計(jì)的一個(gè)重要課題，TSP問(wèn)題的肩效解決對(duì)推動(dòng)整個(gè)組合優(yōu)化領(lǐng) 域的發(fā)展肩重大的影響。作為一類(lèi)組合優(yōu)化問(wèn)題的代表，TSP問(wèn)題在實(shí)際工程中肩許多應(yīng)用，如 計(jì)算機(jī)聯(lián)網(wǎng)、物流等行業(yè)中的車(chē)輛調(diào)度優(yōu)化、電力系統(tǒng)配電網(wǎng)絡(luò)重構(gòu)、城市 管道鋪設(shè)優(yōu)化、交通導(dǎo)航、電氣布線、電子地圖、VLSI單元布局、X射線結(jié)品學(xué)問(wèn)題等。PSO算法在連續(xù)空間優(yōu)化問(wèn)題上已經(jīng)取得了很好的效果，但是將其應(yīng)用 在TSP等離散優(yōu)化問(wèn)題中還是一種嘗試。因此用

10、改進(jìn)的PSO算法有效的求解TSP問(wèn)題，在整個(gè)組合優(yōu)化領(lǐng)域和實(shí)際工程中都有著重要影響和實(shí)際意 義。學(xué)術(shù)論文文摘粒子群優(yōu)化（簡(jiǎn)稱PSO）算法在多維連續(xù)優(yōu)化問(wèn)題的應(yīng)用中取得了較好 的效果，但在旅行商（簡(jiǎn)稱TSP問(wèn)題）等組合優(yōu)化問(wèn)題中的應(yīng)用則相對(duì)較 少。為使粒子群算法適合于求解 TSP問(wèn)題本義對(duì)基本PSO算法中粒子的位 置、速度以及操作進(jìn)行了重新定義。初始種群的產(chǎn)生借鑒貪心算法（簡(jiǎn)稱 GA）的思想，每一步都取局部最優(yōu)。這樣產(chǎn)生的初始種群全局最優(yōu)值已經(jīng)比 較接近問(wèn)題的解，因此可以節(jié)省搜索時(shí)間，提高算法收斂速度。針對(duì)粒子群 算法易陷入局部最優(yōu)的缺陷，提出了適合旅行商問(wèn)題的基于 k-means的改進(jìn)措施。采

11、用k-means對(duì)粒子群進(jìn)行聚類(lèi)分析，實(shí)現(xiàn)了粒子之間的信息交 換，擴(kuò)大了粒子的搜索空間，避免了算法陷入局部最優(yōu)。兩個(gè)種群同時(shí)尋優(yōu)，種群內(nèi)部獨(dú)立進(jìn)行PSO進(jìn)化，種群個(gè)體最優(yōu)之間以f 概率進(jìn)行交叉，減 小算法陷入局部最優(yōu)的概率，種群間個(gè)體最優(yōu)的交叉能夠增強(qiáng)兩種群間以及 粒子間的信息共享，及時(shí)傳遞最優(yōu)值信息，提高粒子向更好解進(jìn)化的速度。實(shí)驗(yàn)證明，改進(jìn)后的粒子群算法能肩效地求解 TSP問(wèn)題。作品在何時(shí)、何 地、何種機(jī)構(gòu)舉 ”的會(huì)議上或 ”刊上發(fā)表登 %及所獲獎(jiǎng)勵(lì)1 .已發(fā)表相似論文：易云飛，陳國(guó)鴻.一種基于收縮因子的改進(jìn)粒子群算法J. 軟件導(dǎo)刊.2009, 9(9): 59-602 .一種基于收縮因子

12、的改進(jìn)粒子群算法獲第四屆挑戰(zhàn)杯”廣西大學(xué)生課外學(xué)術(shù)科技作品競(jìng)賽二等獎(jiǎng)。3 .本次申報(bào)的論文已投往全國(guó)中文核心期刊計(jì)算機(jī)工程與應(yīng)用，目前正在審稿。鑒定結(jié)果青提供對(duì)于理解、審查、評(píng)價(jià) M申報(bào)作品具 ，參考價(jià)值的 “有技術(shù)及技 小義獻(xiàn)的檢索 目錄中報(bào)材料清單 （中報(bào)論文一 篇，相關(guān)資料名 ，爾及數(shù)量）申報(bào)論文改進(jìn)粒子群算法求解 TSP問(wèn)題一篇?？蒲泄芾?部門(mén)簽章（簽章）年 月 日C.當(dāng)前國(guó)內(nèi)外同類(lèi)課題研究水平概述說(shuō)明：1.中報(bào)者可根據(jù)作品類(lèi)別和情況填寫(xiě)。2.填寫(xiě)此欄有助于評(píng)審。最初的PSO是用來(lái)解決連續(xù)空間問(wèn)題的，為了適合求解TSP問(wèn)題，人們對(duì)算法進(jìn)行了各 種改進(jìn)。主要可以分為以下幾個(gè)方面：1 .重

13、新定義PSO的運(yùn)算符號(hào)和規(guī)則：黃嵐等引入交換子和交換序的概念,構(gòu)造一種特殊的PSO用于求解TSP。龐巍采用模糊矩 陣技術(shù)，并重新定義其更新公式。Clerc重新定義了運(yùn)算符號(hào)和規(guī)則,并用于求解TSP。李盤(pán)榮 針對(duì)收斂速度不夠快的缺陷，提出利用量子粒子群優(yōu)化算法 QPSO。鐘一文等，在重新定義運(yùn)算 速度、規(guī)則和運(yùn)動(dòng)方程的基礎(chǔ)上，為防止算法的早熟停滯現(xiàn)象，提出用擾動(dòng)速度來(lái)增加粒子群的 多樣性，為提高算法的求精能力，設(shè)計(jì)了一種高效的近鄰搜索算子來(lái)提高粒子的適應(yīng)值。郭文忠等，為了克服PSO在求解離散問(wèn)題所具有的計(jì)算時(shí)間長(zhǎng)和容易陷入停滯狀態(tài)等問(wèn)題，基于“簇”思想，對(duì)粒子間距離進(jìn)行重新定義并給出了相應(yīng)的動(dòng)態(tài)

14、鄰域PSO算法。通過(guò)引入模糊技術(shù)，給出了一種慣性權(quán)重的模糊自適應(yīng)調(diào)整模型及其相應(yīng)的粒子群優(yōu)化算法。王文峰等，在重新定義了 PSO的速度和位置公式的基礎(chǔ)上，針對(duì)易早熟，收斂慢的缺陷，建立局部極小區(qū)域的擾動(dòng)機(jī) 制，結(jié)合局部搜索算法PSEC,提出了一種混合離散粒子群算法 HDPSO。2 .混合粒子群算法。高尚等結(jié)合遺傳算法、蟻群算法和模擬退火算法的思想 ，提出用混合粒子群算法來(lái)求解 CTSPo譚皓等，提出一種結(jié)合PSO和蟻群算法特點(diǎn)的混合算法。陳曦把免疫系統(tǒng)的免疫信息 處理機(jī)制引入到粒子群優(yōu)化算法中，設(shè)計(jì)了免疫粒子群優(yōu)化算法。3 .其他改進(jìn)的PSO。王翠茹為了更有利于粒子發(fā)現(xiàn)問(wèn)題的全局最優(yōu)解，在算法

15、中引入了更符合自然界生物學(xué) 習(xí)規(guī)律的速度變異機(jī)制和粒子自探索機(jī)制。莫愿斌提出了粒子群復(fù)形（CPSO）算法。對(duì)TSP解序列提出5種運(yùn)算，得到能求解TSP的PSO算法。D.推存者情況及對(duì)作品的說(shuō)明說(shuō)明：1.由推薦者本人填寫(xiě)。2 .推薦者須具有高級(jí)專業(yè)技術(shù)職稱，弁與中報(bào)作品相同或相關(guān)領(lǐng)域的專家學(xué)者或?qū)I(yè)技術(shù)人員 （教研組集體）推薦亦可。3 .推薦者填寫(xiě)此部分，即視為同意推薦。4 .推薦者所在單位簽章僅被視為對(duì)推薦者身份的確認(rèn)。推薦者 情況姓名黃星壽性別男年齡47職稱副教授工作單位河池學(xué)院計(jì)算機(jī)與信息科學(xué)系通訊地址廣西宜州市龍江路42號(hào) 河池學(xué)院計(jì)信系郵政編碼546300單位電話住宅電話推薦者所在 單

16、位簽章（簽章）年 月 日青對(duì)中報(bào)者中報(bào)情 ,真實(shí)性做出闡述申報(bào)者所呈交的作品是在指導(dǎo)教師的指導(dǎo)下獨(dú)立進(jìn)行 研究所取得的研究成果。青對(duì)作品的意義、，術(shù)水平、適用范 司及推廣前景做出 匕的評(píng)價(jià)該作品針對(duì)粒子群算法易陷入局部最優(yōu)的缺陷，引入了適合于求解TSP問(wèn)題的基于k-means的改進(jìn)措施，對(duì)粒子 群進(jìn)行聚類(lèi)分析，實(shí)現(xiàn)了粒子之間的信息交換，擴(kuò)大了粒子 的搜索空間，克服了 PSO算法易陷入局部最優(yōu)的缺陷。實(shí) 驗(yàn)結(jié)果表明改進(jìn)后的粒子群算法能有效地求解TSP問(wèn)題。其它說(shuō)明推 薦 者情 況姓名周永權(quán)性別男年齡49職稱教授工作單位河池學(xué)院計(jì)算機(jī)與信息科學(xué)系（兼職教授）通訊地址廣西宜州市龍江路42號(hào)河池 學(xué)院

17、計(jì)信系郵政 編碼546300單位電話住宅電話推薦者所在 單位簽章（簽章）年 月 日請(qǐng)對(duì)申報(bào)者申報(bào) 情況的真實(shí)性做M闡述該作品是在指導(dǎo)教師易方飛的指導(dǎo)下獨(dú)立進(jìn)行研究所取得 的研究成果，作品中的實(shí)驗(yàn)數(shù)據(jù)是真實(shí)的。請(qǐng)對(duì)作品的意 義、技術(shù)水平、 適用范圍及推廣 前景做出評(píng)價(jià)該作品地提出了一種改進(jìn)的粒子群算法，并將該算法用于 求解TSP問(wèn)題。所提出的改進(jìn)算法提高了算法的有效性；既適 合科學(xué)研究，又特別適合工程應(yīng)用；可廣泛應(yīng)用于函數(shù)尋優(yōu)、神 經(jīng)網(wǎng)絡(luò)訓(xùn)練、模式分類(lèi)、模糊系統(tǒng)控制以及其它的應(yīng)用領(lǐng)域。 仿真實(shí)驗(yàn)表明改進(jìn)后的算法是可行、有效的。其它說(shuō)明產(chǎn)校組織協(xié)調(diào)機(jī) 一確認(rèn)弁簽章（簽章）年 月 日校主管領(lǐng)導(dǎo)或校簽

18、章我單位經(jīng)自查，承諾該作品符合挑戰(zhàn)杯中報(bào)作品的要 求，接受競(jìng)賽組委會(huì)抽查。（簽章）年 月 日各?。▍^(qū)、市）（簽章）年 月 日各?。▍^(qū)、市）審定意見(jiàn)團(tuán)委 （簽章）科協(xié)教育廳學(xué)聯(lián)（簽章） （簽章）（簽章）E.組織委員會(huì)秘書(shū)處資格和形式審查意見(jiàn)組委會(huì)秘書(shū)處資格審查意見(jiàn)審查人（簽名）年 月 日組委會(huì)秘書(shū)處形式審查意見(jiàn)審查人（簽名）年 月 日組委會(huì)秘書(shū)處審查結(jié)果口合格口不合格負(fù)責(zé)人（簽名）年 月 日F1 評(píng)審委員會(huì)預(yù)審意見(jiàn)粘貼處F2.評(píng)審委員會(huì)終審意見(jiàn)粘貼處（正文打印頁(yè)）基于k-means的改進(jìn)粒子群算法求解TSP問(wèn)題陳國(guó)鴻（ 河池學(xué)院 計(jì)算機(jī)與信息科學(xué)系 , 廣西 宜州 546300）摘 要 粒子群優(yōu)

19、化 （簡(jiǎn)稱PSO） 算法在多維連續(xù)優(yōu)化問(wèn)題的應(yīng)用中取得了較好的效果， 但在旅行商（簡(jiǎn)稱TSP問(wèn)題）等組合優(yōu)化問(wèn)題中的應(yīng)用則相對(duì)較少。為使粒子群算法適合于求解TSP問(wèn)題本文對(duì)基本PSO算法中粒子的位置、速度以及操作進(jìn)行了重新定義。初始種群的產(chǎn)生借鑒貪心算法的思想， 每一步都取局部最優(yōu)。 這樣產(chǎn)生的初始種群全局最優(yōu)值已經(jīng)比較接近問(wèn)題的解， 因此可以節(jié)省搜索時(shí)間， 提高算法收斂速度。 針對(duì)粒子群算法易陷入局部最優(yōu)的缺陷，提出了適合旅行商問(wèn)題的基于k-means的改進(jìn)措施。采用k-means對(duì)粒子群進(jìn)行聚類(lèi)分析， 實(shí)現(xiàn)了粒子之間的信息交換， 擴(kuò)大了粒子的搜索空間， 避免了算法陷入局部最優(yōu)。兩個(gè)種群同時(shí)

20、尋優(yōu)，種群內(nèi)部獨(dú)立進(jìn)行PSOS化，種群個(gè)體最優(yōu)之間以一定概率進(jìn)行交叉， 減小算法陷入局部最優(yōu)的概率， 種群間個(gè)體最優(yōu)的交叉能夠增強(qiáng)兩種群間以及粒子間的信息共享， 及時(shí)傳遞最優(yōu)值信息， 提高粒子向更好解進(jìn)化的速度。 實(shí)驗(yàn)證明，改進(jìn)后的粒子群算法能有效地求解TSP問(wèn)題。關(guān)鍵詞旅行商問(wèn)題；粒子群算法； K-means;貪心算法0 引言旅行商問(wèn)題（Traveling Salesman Problem ,簡(jiǎn)稱 TSP僅名貨郎擔(dān)問(wèn)題，是一個(gè)典型的 NP 完全問(wèn)題。原型描述：給定N 個(gè)城市和兩兩城市之見(jiàn)的距離，求一條訪問(wèn)各個(gè)城市且僅訪問(wèn)一次的最短路線。雖然其數(shù)學(xué)描述非常簡(jiǎn)單，但卻無(wú)法找到一個(gè)確定的算法在多項(xiàng)

21、式時(shí)間內(nèi)求解TSP 問(wèn)題，另一方面很多研究領(lǐng)域出現(xiàn)的復(fù)雜優(yōu)化問(wèn)題可以被抽象概括為 TSP 問(wèn)題加以求解，因此找到能夠有效解決 TSP 問(wèn)題的方法, 在理論上和實(shí)際應(yīng)用中都很有價(jià)值。粒子群算法（ Particle SwarmOptimization ， 簡(jiǎn)稱PSO） 算法最早是在1995年由美國(guó)社會(huì)心理學(xué)家 James Kennedy和電氣工程師 Russell Eberhart 共同提 出的一種全局優(yōu)化算法， 該算法的基本思想來(lái)源于對(duì)鳥(niǎo)群簡(jiǎn)化社會(huì)模型的研究及行為模擬， 其中的每個(gè)個(gè)體充分利用群體的與自身的智能， 不斷地調(diào)整學(xué)習(xí)， 最 終得到滿意解。該算法在多維連續(xù)優(yōu)化問(wèn)題的運(yùn)用中取得了較好的效

22、果，但在TSP 等組合優(yōu)化問(wèn)題中的應(yīng)用則相對(duì)較少。本文對(duì)基本PSOT法中粒子的位置、速度以及操作進(jìn)行了重新定義，使粒子 群算法適合于求解tsp問(wèn)題，并采用貪心算法的思想每一步都取局部最優(yōu)。這樣 產(chǎn)生的初始種群全局最優(yōu)值已經(jīng)比較接近問(wèn)題的解， 因此可以節(jié)省搜索時(shí)間， 提 高算法收斂速度。針對(duì)粒子群算法易陷入局部最優(yōu)的缺陷，引入了適合于求解 TSP 問(wèn)題的基于k-means 的改進(jìn)措施，對(duì)粒子群進(jìn)行聚類(lèi)分析， 實(shí)現(xiàn)了粒子之間的信息交換，擴(kuò)大了粒子的搜索空間，克服了PSOT法易陷入局部最優(yōu)的缺陷。兩個(gè)種群同時(shí)尋優(yōu)，種群內(nèi)部獨(dú)立進(jìn)行PSO!化，種群個(gè)體最優(yōu)之間以一定 概率進(jìn)行交叉。 兩個(gè)種群同時(shí)尋優(yōu)可

23、以減小算法陷入局部最優(yōu)的概率， 種群間個(gè) 體最優(yōu)的交叉能夠增強(qiáng)兩種群間以及粒子間的信息共享，及時(shí)傳遞最優(yōu)值信息， 提高粒子向更好解進(jìn)化的速度。最后本文對(duì)30 點(diǎn) TSP 問(wèn)題進(jìn)行仿真測(cè)試，試驗(yàn) 表明改進(jìn)后的粒子群算法能有效地求解TSP問(wèn)題。1 TSP 問(wèn)題TSP是運(yùn)籌學(xué)、圖輪和組合優(yōu)化中的 NP難問(wèn)題。問(wèn)題的具體如下：給定 N 個(gè)城市及兩兩城市之間的距離， 求一條經(jīng)過(guò)各城市一次且僅一次的最短路線。 其 圖論描述為：給定圖G= (V, A),其中V為頂點(diǎn)集，A為各頂點(diǎn)相互連接組成的 弧集，已知各頂點(diǎn)間連接距離，要求確定一條長(zhǎng)度最短的 Hamilton 回路，即遍 歷所有頂點(diǎn)一次且僅一次的最短回路

24、。設(shè)dij 為城市 i 與 j 之間的距離，即弧( i,j) 的長(zhǎng)度。引入決策變量： 1 若旅行商訪問(wèn)城市 i 后訪問(wèn)城市jXij =0 否則 (1.1)nMin Z Xijdij則TSP的目標(biāo)函數(shù)為i,j 1(1.2)TSP 問(wèn)題描述非常簡(jiǎn)單， 但最優(yōu)化求解很困難， 若用窮舉法搜索， 則要考慮所有可能情況， 并兩兩對(duì)比， 找出最優(yōu) , 其算法復(fù)雜性呈指數(shù)增長(zhǎng), 即所謂的 “組 合爆炸”。所以，尋求和研究 TSP的有效啟發(fā)式算法，是問(wèn)題的關(guān)鍵。2基本PSO#法PSO算法主要模擬鳥(niǎo)群飛行的覓食行為，通過(guò)鳥(niǎo)群的集體協(xié)作達(dá)到尋優(yōu)目 的。在PSO算法中，每個(gè)粒子利用自身的歷史最優(yōu)位置和整個(gè)粒子群的全局

25、最優(yōu) 解提供的信息，在解空間內(nèi)不斷飛行，實(shí)現(xiàn)尋找最優(yōu)解的目的。2.1 基本PSOM法的數(shù)學(xué)描述如下：設(shè)搜索空間為N維，總粒子數(shù)為Numi第i個(gè)粒子的位置向量 Xi=(x1，Xi2，Xi3，Xin),第 i 個(gè)粒子的速度向量是 Vi =(Vi1，Vi2，Vi3,Vin),第 i 個(gè) 粒子在“飛行”中的歷史最優(yōu)位置是 P=( Pi1，Pi2，Pi3，-，pin) , Pg表示目前為止在 整個(gè)粒子群中發(fā)現(xiàn)的全局最優(yōu)粒子；粒子按如下方式飛行：Vj(t+1) = w VjXt) + cl randl ( ) PG Xj + c2 rand2 ( ) Pj-為(2.1)Xj(t +1) = Xj (t)

26、+ Vj (t +1)(2.2)其中，下標(biāo)“j”表示第j維，t為飛行的次數(shù)；w為慣性權(quán)重，使粒子保持 運(yùn)動(dòng)慣性，控制前一速度對(duì)當(dāng)前速度的影響，較大的w適于對(duì)解空間進(jìn)行大規(guī)模 探查，較小的w適合于進(jìn)行小范圍開(kāi)挖；c1, c2為加速常數(shù)，通常在02問(wèn) 取值，c1調(diào)節(jié)粒子飛向自身最好位置方向的步長(zhǎng)，c2調(diào)節(jié)粒子向全局最好位置 飛行步長(zhǎng)；rand1()和rand2 ()是0,1 之間相互獨(dú)立的隨機(jī)數(shù)。粒子的位置 向量中各維變化范圍為Xmin , XmaX,速度變化范圍為Vmin , Vmax,迭代中若位 置和速度超過(guò)邊界范圍則取邊界值。PSOJT法通過(guò)粒子在解空間內(nèi)不斷地變化速 度向量來(lái)改變位置，最終

27、找到最優(yōu)解。圖1 .粒子移枷理冏富1粒子移動(dòng)原理圖2.2 基本粒子群算法的流程如下：Stepl:依照初始化過(guò)程，對(duì)粒子群的隨機(jī)位置和速度進(jìn)行初始設(shè)定；Step2:計(jì)算每個(gè)粒子的適應(yīng)值；Step3:對(duì)于每個(gè)粒子，將其適應(yīng)值與所經(jīng)歷過(guò)的最好位置P的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的最好位置；Step4：對(duì)每個(gè)粒子，將其適應(yīng)值與全局所經(jīng)歷的最好位置6的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的全局位置；Step5:根據(jù)方程（2.1）、（2.2）對(duì)粒子的速度和位置進(jìn)行迭代進(jìn)化；Step6:循環(huán)步驟2-5,直到結(jié)束條件為足夠好的適應(yīng)值或達(dá)到一個(gè)預(yù)設(shè)最 大迭代次數(shù)，算法終止。3改進(jìn)的粒子群算法求解TS

28、P問(wèn)題3.1定義更新TSP問(wèn)題為離散問(wèn)題，用PSOtf：解TSP問(wèn)題需要對(duì)基本PSO算法中粒子的位 置、速度以及操作進(jìn)行重新定義：（1） 狀態(tài)空間TSP問(wèn)題的結(jié)果是要求出具有最短路徑的哈密爾頓圈，所以狀態(tài)空間即為所有位置的集合。（2） 粒子的位置粒子的位置可以定義為一個(gè)具有所有節(jié)點(diǎn)的哈密爾頓圈，設(shè)所有ni與ni 1之間的弧存在，粒子的位置可表示為序列x （R,n2,nN, nN 1），其中R E,n nN 1 , E為狀態(tài)空間。（3）粒子的速度速度定義為粒子位置的變換集，表示一組置換序列的有序列表?？梢员硎緸椋簐 （ik，j）（ik，jk，） 12 ，N,k 1,2,忖|（3.1）其中，| v

29、 |表示該速度所含交換的數(shù)目，式（3.1）表示先交換粒子中ni1、 nj1的位置，然后交換 出、nj2的位置，依此類(lèi)推。(4) 粒子位置與速度的加法操作該操作表示將一組置換序列依次作用于某個(gè)粒子位置， 其結(jié)果為一個(gè)新的位置， 即一個(gè)新的節(jié)點(diǎn)的排列。 例如： 位置為 X=l ， 5， 2， 4， 3， l ， 速度為 V=(1 ， 3), (2, 4),則其相加 X+V后結(jié)果為 X=2, 4, 1,5,3,2。(5) 粒子位置與位置的減法操作粒子位置與位置相減后結(jié)果為一組置換序列，即速度。例如 X=2 ， 4， 1，5， 3， 2 ， Y=1， 5， 2， 4， 3， 1 ，由于 X(1)=Y(

30、3)=2,)=2 ，所以第一個(gè)交換為so1 =(1， 3) ， X1=X+ so1 =2,41,5,3,2+(1,3)=1,4,2,5,3,1 ； X1(2)=Y(4)=4 ，因此第二個(gè)交換為 so2=(2,4) ， 作用到粒子的位置X1 后得 X2=X1+ so2 =1 ， 4， 2， 5， 3， 1+(2,4)=1 ， 5， 2，4， 3， 1=Y ， )=Y ，所以位置X 與位置 Y 相減后得到一組置換序列，即 X-Y=(1,3),(2,4) 。(6) 粒子速度與速度的加法操作粒子速度與速度的加法操作為兩個(gè)置換序列的合并，結(jié)果為一個(gè)新的置換序列，即一個(gè)新的速度。例如：速度V1=(1,3)

31、,(2,4),V2=(2,3),(5,4), 相加后得 V=V1+V2=(1,3),(2,4),(2,3),(5,4)。(7) 實(shí)數(shù)與粒子速度的乘法操作實(shí)數(shù) c 為(0 ， 1)的任意實(shí)數(shù)， 設(shè)速度 v 為 k 個(gè)置換序列， 則乘法操作為對(duì)速度置換序列進(jìn)行截取，使得新的速度的置換序列長(zhǎng)度為|c倒(c 4取整)。例如： 速度 V=(2,3),(1,3),(4,5),(5,2),k=4, 若 c=0.78,則 c4=3.12 , |c 四=3 , 相乘后速度為 c>=(2,3),(1,3),(4,5)。3.2 公式更新粒子的速度、 位置及其各種操作重新定義后， 離散粒子群算法的速度更新公式表

32、示如下：k1kk kk k3.2)(3.3)ViwVic1r1(PiXi ) c2r2 (Pg Xi )Xik Vik 1其中，cl、c2與基本PSO算法中定義相同，仍為加速常數(shù)，在02之間取值，門(mén)、r2為兩交換序的合并算子，表示速度與為(0,1)上均勻分布的兩個(gè)相互獨(dú)立的隨機(jī)數(shù)；速度的加法操作； 表示粒子位置與位置的減法操作； 表示粒子位置與速度的加法操作。3.3 基于 k-means 的改進(jìn)措施具有良好多樣性的粒子群能增加粒子在迭代中獲得的有效信息量， 這不僅能擴(kuò)大粒子在解空間內(nèi)的搜索范圍， 而且在算法陷入局部最優(yōu)時(shí)， 有助于粒子逃離局部最優(yōu)區(qū)域，避免PSO算法陷入局部最優(yōu)的境地。在PSO

33、算法中，粒子利用自身信息、 個(gè)體極值信息和全局極值信息， 指導(dǎo)自我的搜索方向： 個(gè)體極值和全局極值信息使粒子能夠迅速地集中于全局極值所在的區(qū)域； 個(gè)體信息使粒子能夠根據(jù)自身的信息避免陷入局部最優(yōu)化。這一機(jī)制下，PSO算法具有較高的搜索效率和較快的收斂速度，但是粒子在搜索中會(huì)過(guò)分依賴粒子群提供的極值信息 ( 無(wú)論是個(gè)體極值信息，還是全局極值信息 ) ，從而導(dǎo)致粒子群更易趨于同質(zhì)化，減少了粒子能夠獲得的有效信息量，降低了粒子逃離局部最優(yōu)的可能性。本文使用聚類(lèi)算法對(duì)粒子的歷史最優(yōu)位置進(jìn)行聚類(lèi)分析， 利用聚類(lèi)后形成的類(lèi)中心 ， 替代式 (3.2) 中個(gè)體的歷史最優(yōu)位置， 避免粒子在搜索中因?yàn)檫^(guò)多極值信

34、息的影響而快速同質(zhì)化。通過(guò)這一改進(jìn)措施，粒子首先利用其他粒子提供的信息，確定粒子群中所有粒子在解空間內(nèi)的相對(duì)位置， 實(shí)現(xiàn)粒子之間的信息交換； 其次，根據(jù)該粒子所在類(lèi)的中心點(diǎn)提供的信息， 更新粒子的速度向量， 從而加強(qiáng)算法對(duì)該類(lèi)所在區(qū)域的局部搜索能力； 最后， 從整個(gè)粒子群的角度看， 由于各粒子的搜索范圍都集中于聚類(lèi)所形成的局部區(qū)域內(nèi)， 可以維持粒子之間的個(gè)體差異， 粒子群能保持較好的多樣性。3.3.1 k-Means 算法k-Means 聚類(lèi)算法屬于聚類(lèi)分析方法中一種基本的且應(yīng)用最廣的劃分方法，是一種在無(wú)類(lèi)標(biāo)號(hào)數(shù)據(jù)中發(fā)現(xiàn)簇和簇中心的方法。該算法的基本思想是：給定n個(gè)數(shù)據(jù)對(duì)象和要生成的簇的數(shù)目k

35、,隨機(jī)選取k 個(gè)對(duì)象作為初始的 k 個(gè)聚類(lèi)中心， 然后計(jì)算剩余各個(gè)樣本到每一個(gè)聚類(lèi)中心的距離， 把該樣本歸到離它最近的那個(gè)聚類(lèi)中心所在的類(lèi)， 對(duì)調(diào)整后的新類(lèi)使用平均值的方法計(jì)算新的聚類(lèi)中心， 如果相鄰兩次的聚類(lèi)中心沒(méi)有任何變化， 說(shuō)明樣本調(diào)整結(jié)束且聚類(lèi)平均誤差準(zhǔn)則函數(shù)已經(jīng)收斂。 本算法在每次迭代中都要考察每個(gè)樣本的分類(lèi)是否正確，若不正確，就要調(diào)整，在全部樣本調(diào)整完后，再修改聚類(lèi)中心，進(jìn)入下一次迭代。如果在一次迭代算法中，所有的樣本被正確分類(lèi)，則不會(huì)有調(diào)整， 聚類(lèi)中心也不會(huì)有任何變化。在算法迭代的過(guò)程中聚類(lèi)平均誤差準(zhǔn)則函數(shù)的值在不斷減小，最終收斂至一個(gè)固定的值。因此，k-Means 算法可以描述

36、如下：輸入：聚類(lèi)個(gè)數(shù)k， n 個(gè)數(shù)據(jù)對(duì)象。輸出：滿足方差最小標(biāo)準(zhǔn)的 k 個(gè)聚類(lèi)。處理流程：（ 1）從 n 個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類(lèi)中心；（ 2）根據(jù)每個(gè)聚類(lèi)對(duì)象的中心對(duì)象，計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離；并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分；（ 3）重新計(jì)算每個(gè)有變化聚類(lèi)的中心對(duì)象。（ 4）循環(huán)（2） 到 （3） 直到每個(gè)聚類(lèi)不再發(fā)生變化為止；k-Means 算法接受輸入量k ，然后將 n 個(gè)數(shù)據(jù)對(duì)象劃分為 k 個(gè)聚類(lèi)以便使得所獲得的聚類(lèi)滿足： 同一聚類(lèi)中的對(duì)象相似度較高， 而不同聚類(lèi)中的對(duì)象相似度較小。 即 k 個(gè)聚類(lèi)具有以下特點(diǎn)： 各聚類(lèi)本身盡可能的緊湊， 而各聚類(lèi)之間

37、盡可能的分開(kāi)。 其中聚類(lèi)相似度是利用各聚類(lèi)中對(duì)象的均值所獲得一個(gè) “中心對(duì)象”（引力中心）來(lái)進(jìn)行計(jì)算的。K-Means 算法的工作過(guò)程說(shuō)明如下： 首先從 n 個(gè)數(shù)據(jù)對(duì)象任意選擇k 個(gè)對(duì)象作為初始聚類(lèi)中心； 然后對(duì)于所剩下的其它對(duì)象， 則根據(jù)它們與這些聚類(lèi)中心的相似度（距離），分別將它們分配給與其最相似的（聚類(lèi)中心所代表的）聚類(lèi)；再計(jì)算每個(gè)新聚類(lèi)的聚類(lèi)中心（該聚類(lèi)中所有對(duì)象的均值）；不斷重復(fù)以上過(guò)程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開(kāi)始收斂為止。 一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù)。3.3.2 基于 k-Means 的改進(jìn)粒子群算法PSOT法在迭代中使用了兩個(gè)不同的粒子群：各粒子的歷史最優(yōu)位置組成的粒子群 1；各粒

38、子在迭代中動(dòng)態(tài)變化的粒子群2。粒子群2在搜索的過(guò)程中是對(duì)整個(gè)解空間進(jìn)行的隨機(jī)搜索， 在每次迭代中其變化的速度較快， 而且其變化后的粒子并不一定代表較好的結(jié)果， 故其提供的信息對(duì)其他粒子而言并不具有很好的指導(dǎo)意義； 相反， 粒子群 1 在迭代過(guò)程中相對(duì)穩(wěn)定， 而且具有的信息往往能夠代表粒子在解空間各局部區(qū)域的優(yōu)質(zhì)信息， 為其他粒子提供了較好的指導(dǎo)信息。 因此，我們選擇對(duì)粒子群1進(jìn)行聚類(lèi)分析。綜上，基于k-means的改進(jìn)PSC#法的速度和位置向量更新方式為：3.4)3.5)Vik 1 wVikc1r1 (cluster (Pik) Xik) c2r2(Pgk Xik)Xik 1Xik Vik 1

39、k其中，cluster(p)表示對(duì)粒子歷代最優(yōu)解聚類(lèi)后粒子X(jué)i所屬類(lèi)的代表對(duì)象，其他參數(shù)的含義與基本PSO算法的含義相同。3.4 貪心算法產(chǎn)生初始種群由于旅行商問(wèn)題為一個(gè)循環(huán)回路，所以起始城市可以為任意的一個(gè)城市。本文采用貪心算法的思想， 隨機(jī)選擇一個(gè)城市作為出發(fā)城市， 并始終選擇距離當(dāng)前城市最近的城市作為下一個(gè)遍歷城市， 直到所有城市均被遍歷后直接連接到出發(fā)城市即可。至此，可以利用這個(gè)貪心算法得到近似最優(yōu)循環(huán)序列，產(chǎn)生一定規(guī)模的初始種群。 這樣產(chǎn)生的初始種群全局最優(yōu)值已經(jīng)比較接近問(wèn)題的解， 因此可以節(jié)省搜索時(shí)間，提高算法收斂速度。3.5 兩個(gè)種群同時(shí)尋優(yōu)生物界中少數(shù)優(yōu)良個(gè)體進(jìn)行交叉，有利于產(chǎn)

40、生優(yōu)良的后代，并保證了父代優(yōu)良品性的繁衍， 符合生物界優(yōu)勝劣汰的進(jìn)化機(jī)制， 因此， 交叉產(chǎn)生的個(gè)體最優(yōu)有利于種群的進(jìn)化。 本文根據(jù)這一生物界的繁衍規(guī)律， 提出兩個(gè)種群同時(shí)尋優(yōu)的機(jī)制，即種群內(nèi)部獨(dú)立進(jìn)行PSO進(jìn)化，種群個(gè)體最優(yōu)之間以一定概率進(jìn)行交叉。兩個(gè)種群同時(shí)尋優(yōu)可以減小算法陷入局部最優(yōu)的概率， 種群間個(gè)體最優(yōu)的交叉能夠增強(qiáng)兩種群間以及粒子間的信息共享， 及時(shí)傳遞最優(yōu)值信息， 提高粒子向更好解進(jìn)化的速度。3.6 改進(jìn)的PSOB法求解TS騎程如下：Stepl:：用貪婪算法產(chǎn)生兩個(gè)初始種群A群和B群，隨機(jī)產(chǎn)生兩個(gè)基本交換序作為兩個(gè)種群的初始速度， 每個(gè)粒子位置向量的每一維隨機(jī)取0,1 之間的實(shí)數(shù)，

41、設(shè)定粒子群算法的參數(shù)w, cl, c2;Step2：計(jì)算粒子適應(yīng)度，確定個(gè)體極值 pbest和全局極值gbest;Step3:使用k-Means對(duì)粒子的歷史最優(yōu)解進(jìn)行聚類(lèi)分析，確定每個(gè)粒子所k在的類(lèi)以及類(lèi)的中心點(diǎn)cluster(P)。Step4：以一定概率將小粒子的個(gè)體最優(yōu)與端粒子的個(gè)體最優(yōu)進(jìn)行交叉， 產(chǎn)生新的個(gè)體最優(yōu)；Step5:為每個(gè)粒子按照式(3.4)和式(3.5)確定新的速度向量和下一代的位 置向量，并產(chǎn)生兩個(gè)新的全局最優(yōu)。Step6:對(duì)新形成的粒子群按照Step2的方法確定各粒子代表的可行解的路 徑長(zhǎng)度，更新粒子個(gè)體的歷史最優(yōu)位置和粒子群的全局最優(yōu)解。Step7:如未滿足終止條件(一

42、個(gè)種群兩次進(jìn)化適應(yīng)度之差小于最小誤差 ), 則返回step3。改進(jìn)算法的流程圖如圖2所示：圖2改進(jìn)粒子群算法流程圖4實(shí)驗(yàn)結(jié)果及分析為了檢驗(yàn)算法的有效性，本文選用Oliver30作為實(shí)驗(yàn)例子，并與基本 PSO算法，遺傳算法進(jìn)行比較。目前已知Oliver30問(wèn)題的最好解為423.7406,巡回路 徑為：1-2-3-9-18-19-20-21-10-11-7-8-14-15-24-25-26-27-28-29-16-17-22-23-3012-13-4-5-6 。距離丈圖3 Oliver30 問(wèn)題優(yōu)化結(jié)果采用Microsoft Visual Studio 2005為編程工具，實(shí)驗(yàn)環(huán)境為Intel(R

43、)Core(TM) i3,2.13GHz CPU,2GBj存,Windows Vista 系統(tǒng)。為便于比較，將該改 進(jìn)PSOT法與基本PSOT法、遺傳算法分別連續(xù)進(jìn)行30次實(shí)驗(yàn)，對(duì)其結(jié)果進(jìn)行比較 分析。幾種算法中，種群的粒子數(shù)均為100。粒子群算法中慣性權(quán)重 W1. 4線性 遞減到0.5,加速常數(shù)C1=C2=1.2,K-mean殯類(lèi)數(shù)為5,最大迭代次數(shù)1000。遺傳 算法交叉概率Pc=0.2,變異概率Pm=06實(shí)驗(yàn)結(jié)果如表1所示，得到的最優(yōu)結(jié)果 巡回路彳如圖3所示，其巡回路徑與目前已知最好解一致。表1 Oliver30實(shí)驗(yàn)結(jié)果比較算法平均值最好解最差解收斂率次數(shù)基本PSO457.6632435

44、.9918480.14520.00遺傳算法425.6905423.7406429.487625.37%735.40改進(jìn)PSO424.7926423.7406425.693174.59%583.00表1中，收斂率是30次實(shí)驗(yàn)中，算法收斂到最優(yōu)值423.7406的次數(shù)與實(shí)驗(yàn) 次數(shù)30之比。由表中數(shù)據(jù)可知，改進(jìn)的 PSO算法最優(yōu)解為423.7406,與當(dāng)前 Oliver30問(wèn)題的最優(yōu)解一致，基本 PSOB法最優(yōu)解為435.9918 ,無(wú)法收斂到當(dāng) 前最優(yōu)解，遺傳算法雖然也能收斂到當(dāng)前最優(yōu)解，但其收斂率25.37%?口收斂速度遠(yuǎn)不如改進(jìn)的PSOB法制攵斂率74.59%收斂速度。綜上所述，用改進(jìn)的PSO 算法求解TSP問(wèn)