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

1、第五屆“挑戰(zhàn)杯”廣西大學(xué)生課外學(xué)術(shù) 科技作品申報(bào)書(shū)序號(hào)：編碼：第五屆挑戰(zhàn)杯”廣西大學(xué)生課外學(xué)術(shù)科技作品競(jìng)賽作品名稱：基于 k-means 的改進(jìn)粒子群算法求解 TSP問(wèn)題學(xué)校全稱：河池學(xué)院陳國(guó)鴻申報(bào)者姓名（集體名稱）類別：回自然科學(xué)類學(xué)術(shù)論文哲學(xué)社會(huì)科學(xué)類社會(huì)調(diào)查報(bào)告和學(xué)術(shù)論文科技發(fā)明制作A類科技發(fā)明制作B類說(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ù)作品類別（自然科學(xué)類學(xué)術(shù)論文、 哲學(xué)社會(huì)科學(xué)類社會(huì)調(diào)查報(bào)告和學(xué)術(shù)論文、 科技發(fā)明制作） 分別 填寫(xiě) B1、B2 或 B3 表。所有申報(bào)者可根據(jù)情況填寫(xiě)

2、 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.5 X22cm ）。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冋題畢業(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è)在校的全日制非成 人教育、非在職的各類高等院校學(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é)類學(xué)術(shù)論文）說(shuō)明：1.必須由申報(bào)者本人填寫(xiě)。2 .本部分中科研管理部門(mén)簽章視為對(duì)申報(bào)者所填內(nèi)容的確認(rèn)。3 .作品分類請(qǐng)按作品學(xué)術(shù)方向

5、或所涉及的主要學(xué)科領(lǐng)域填寫(xiě)。4 .碩士研究生、博士研究生作品不在此列。作品全稱改進(jìn)粒子群算法求解TSP問(wèn)題作品分類（B） A .機(jī)械與控制（包括機(jī)械、儀器儀表、自動(dòng)化控 制、工程、交通、建筑等）B. 信息技術(shù)（包括計(jì)算機(jī)、電信、通訊、電子等）C. 數(shù)理（包括數(shù)學(xué)、物理、地球與空間科學(xué)等）D .生命科學(xué)（包括生物、農(nóng)學(xué)、藥學(xué)、醫(yī)學(xué)、健 康、衛(wèi)生、食品等）E.能源化工（包括能源、材料、石油、化學(xué)、化 工、生態(tài)、環(huán)保等）作品撰寫(xiě)的目 的和基本思路旅行商問(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)

6、域出現(xiàn)的復(fù)雜優(yōu)化問(wèn)題可以被抽象概括為T(mén)SP問(wèn)題加以求解，因此找到能夠有效解決 TSP問(wèn)題的方法，在理論上和實(shí)際應(yīng)用中都 很有價(jià)值。本文對(duì)基本PSO算法中粒子的位置、速度以及操作進(jìn)行了重新定義， 使粒子群算法適合于求解TSP問(wèn)題，并采用貪心算法的思想每一步都取局部 最優(yōu)。這樣產(chǎn)生的初始種群全局最優(yōu)值已經(jīng)比較接近問(wèn)題的解，因此可以節(jié) 省搜索時(shí)間，提高算法收斂速度。針對(duì)粒子群算法易陷入局部最優(yōu)的缺陷，引入了適合于求解TSP冋題的基于k-means的改進(jìn)措施，對(duì)粒子群進(jìn)行聚 類分析，實(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)的缺陷， 提出了適合旅行商冋題的基于 k-means的改進(jìn)措施。米用 k-means對(duì)粒子群進(jìn)行聚類分析，實(shí)現(xiàn)了粒子之間的信息交換，擴(kuò)大了粒子 的搜索空間，避免了算法陷入局部最優(yōu)。兩個(gè)種群同時(shí)尋優(yōu)，種群內(nèi)部獨(dú)立 進(jìn)行PSO進(jìn)化，種群個(gè)體最優(yōu)之間以一定概率進(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ā)展有重大的影響。作為一類組合優(yōu)化問(wèn)題的代表，TSP問(wèn)題在實(shí)際工程中有許多應(yīng)用，如 計(jì)算機(jī)聯(lián)網(wǎng)、物流等行業(yè)中的車輛調(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)化冋題中還是一種嘗試。因

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)行聚類分析，實(shí)現(xiàn)了粒子之間的信息交 換，擴(kuò)大了粒子的搜索空間，避免了算法陷入局部最優(yōu)。兩個(gè)種群同時(shí)尋優(yōu)，種群內(nèi)部獨(dú)立進(jìn)行PSO進(jìn)化，種群個(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)題。作品在何時(shí)、何 地、何種機(jī)構(gòu)舉 行的會(huì)議上或 報(bào)刊上發(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é)果請(qǐng)?zhí)峁?duì)于理 解、審查、評(píng)價(jià) 所申報(bào)作品具 有參考價(jià)值的 現(xiàn)有技術(shù)及技 術(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)外同類課題研究水平概述說(shuō)明：1 .申報(bào)者可根據(jù)作品類別和情況填寫(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)

14、的動(dòng)態(tài)鄰域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)求解 CTSP。譚皓等,提出一種結(jié)合PSO和蟻群算法特點(diǎn)的混合算法。陳曦把免疫系統(tǒng)的免疫信息 處理機(jī)制引入到粒子群優(yōu)化算法中，設(shè)計(jì)了免疫粒子群優(yōu)化算法。3. 其他改進(jìn)的PSO o王翠茹為了更有利于粒子發(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、所在 單位簽章（簽章）年 月日請(qǐng)對(duì)申報(bào)者申報(bào)情況真實(shí)性做出闡述申報(bào)者所呈交的作品是在指導(dǎo)教師的指導(dǎo)下獨(dú)立進(jìn)行 研究所取得的研究成果。請(qǐng)對(duì)作品的意義、 技術(shù)水平、適用范 圍及推廣前景做出 您的評(píng)價(jià)該作品針對(duì)粒子群算法易陷入局部最優(yōu)的缺陷，引入了適合于求解TSP問(wèn)題的基于k-means的改進(jìn)措施，對(duì)粒子 群進(jìn)行聚類分析，實(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)河

17、池學(xué)院計(jì)信系郵政 編碼546300單位電話住宅電話推薦者所在 單位簽章（簽章）年 月日請(qǐng)對(duì)申報(bào)者申報(bào) 情況的真實(shí)性做 出闡述該作品是在指導(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)練、模式分類、模糊系統(tǒng)控制以及其它的應(yīng)用領(lǐng)域。 仿真實(shí)驗(yàn)表明改進(jìn)后的算法是可行、有效的。其它說(shuō)明學(xué)校組織協(xié)調(diào)機(jī) 構(gòu)確認(rèn)并簽章年（簽章） 月日校主管領(lǐng)導(dǎo)或

18、校主管部門(mén)確認(rèn)并我單位經(jīng)自查，承諾該作品符合挑戰(zhàn)杯申報(bào)作品的要簽章求，接受競(jìng)賽組委會(huì)抽查。（簽章）年月日各?。▍^(qū)、市） 評(píng)審委員會(huì)初評(píng) 意見(jiàn)年（簽章） 月日各?。▍^(qū)、市）組織協(xié)調(diào)委員會(huì) 審定意見(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é)系 ,

19、 廣西 宜州 546300）摘 要粒子群優(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)生借鑒貪心算法的思想， 每一步都取局部最優(yōu)。 這樣產(chǎn)生的初始種群全局最優(yōu)值已經(jīng)比較 接近問(wèn)題的解， 因此可以節(jié)省搜索時(shí)間， 提高算法收斂速度。 針對(duì)粒子群算法易陷入局部最 優(yōu)的缺陷，提出了適合旅行商問(wèn)題的基于 k-mea ns的改進(jìn)措施。采用k-mea ns對(duì)粒子群進(jìn)行 聚類分析， 實(shí)現(xiàn)了粒子之間的信息交換， 擴(kuò)大了粒

20、子的搜索空間， 避免了算法陷入局部最 優(yōu)。兩個(gè)種群同時(shí)尋優(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)題。原型描述：給定求一條訪問(wèn)各個(gè)城市且僅訪問(wèn)一次的最短路線。N 個(gè)城市和兩兩城市之見(jiàn)的距

21、離, 雖然其數(shù)學(xué)描述非常簡(jiǎn)單, 但卻TSP 問(wèn)題,另一方面很多研究領(lǐng) 域出現(xiàn)的復(fù)雜優(yōu)化問(wèn)題可以被抽象概括為 TSP 問(wèn)題加以求解,因此找到能夠有無(wú)法找到一個(gè)確定的算法在多項(xiàng)式時(shí)間內(nèi)求解效解決 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í)， 最 終

22、得到滿意解。該算法在多維連續(xù)優(yōu)化問(wèn)題的運(yùn)用中取得了較好的效果，但在 TSP 等組合優(yōu)化問(wèn)題中的應(yīng)用則相對(duì)較少。本文對(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)行聚類分析，實(shí)現(xiàn)了粒子之間的信息交換，擴(kuò)大了粒子的搜索空間，克服了 PSO算法易陷入局部最優(yōu)的缺 陷。兩個(gè)種群同時(shí)尋優(yōu)，種群內(nèi)部獨(dú)立進(jìn)行PSO進(jìn)化，

23、種群個(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)題。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)度最短的 Hamilto

24、n 回路，即遍 歷所有頂點(diǎn)一次且僅一次的最短回路。設(shè)dij 為城市 i 與 j 之間的距離，即弧( i,j) 的長(zhǎng)度。引入決策變量：1 若旅行商訪問(wèn)城市 i 后訪問(wèn)城市 jXij =0 否則 (1.1)nMin ZXij dij則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算法中，

25、每個(gè)粒子利用自身的歷史最優(yōu)位置和整個(gè)粒子群的全局最優(yōu) 解提供的信息，在解空間內(nèi)不斷飛行，實(shí)現(xiàn)尋找最優(yōu)解的目的。2.1基本PSO算法的數(shù)學(xué)描述如下：設(shè)搜索空間為N維，總粒子數(shù)為Num 第i個(gè)粒子的位置向量 人=(冷必2必3,，滄)，第)個(gè)粒子的速度向量是Vi =(Vii，Vi2，Vi3，-, Vin)，第i個(gè) 粒子在“飛行”中的歷史最優(yōu)位置是 P=( Pi1, Pi2, Pi3,，Pn)，Pg表示目前為止在 整個(gè)粒子群中發(fā)現(xiàn)的全局最優(yōu)粒子；粒子按如下方式飛行：Vj(t+1) = w VjXt) + ci rartdl ( ) P><(t)-Xj + c2 rand2 ( ) P矗(t

26、)-対(t) (2.1)Xj(t +1) = Xj(t) + 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間 取值，c1調(diào)節(jié)粒子飛向自身最好位置方向的步長(zhǎng)，c2調(diào)節(jié)粒子向全局最好位置 飛行步長(zhǎng)；rand1()和rand2 ()是0,1 之間相互獨(dú)立的隨機(jī)數(shù)。粒子的位置 向量中各維變化范圍為Xmin , Xmax，速度變化范圍為Vmin, Vmax，迭代中若位 置和速度超過(guò)邊界范圍則取邊界值。PSO算法通過(guò)

27、粒子在解空間內(nèi)不斷地變化速 度向量來(lái)改變位置，最終找到最優(yōu)解。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)歷的最好位置Pg的適應(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

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

29、2,N,k 1,2,v其中，| v |表示該速度所含交換的數(shù)目，式(3.1)表示先交換粒子中ni1n j1的位置，然后交換n2、nj2的位置，依此類推(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,由

30、于 X(1)=Y(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 &取整)。例如： 速度 V=(2,3),(1,3),(4,5),(5,2),k=4,若 c=0.78,貝U c&=3.12 , |c =3 ,相乘后速度為 c刃=(2,3),(1,3),(4,5)。3.2 公式更新粒子的速度、 位置及其各種操作重新定義后， 離散粒子群算法的

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

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

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

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

36、準(zhǔn) 則函數(shù)的值在不斷減小，最終收斂至一個(gè)固定的值。因此， k-Means 算法可以描述如下： 輸入：聚類個(gè)數(shù) k， n 個(gè)數(shù)據(jù)對(duì)象。 輸出：滿足方差最小標(biāo)準(zhǔn)的 k 個(gè)聚類。 處理流程：（1）從 n 個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類中心；（2）根據(jù)每個(gè)聚類對(duì)象的中心對(duì)象，計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離；并 根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分；（3）重新計(jì)算每個(gè)有變化聚類的中心對(duì)象。（4）循環(huán)（2） 到（3）直到每個(gè)聚類不再發(fā)生變化為止；k-Means 算法接受輸入量 k ，然后將 n 個(gè)數(shù)據(jù)對(duì)象劃分為 k 個(gè)聚類以便 使得所獲得的聚類滿足： 同一聚類中的對(duì)象相似度較高， 而不同聚類中

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

38、進(jìn)粒子群算法PSO算法在迭代中使用了兩個(gè)不同的粒子群： 各粒子的歷史最優(yōu)位置組成的 粒子群 1；各粒子在迭代中動(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)行聚類分析。綜上，基于k-means的改進(jìn)PSO算法的 速度和位置向量更新方式為：3.4)XiXik Vik

39、 13.5)Vik 1 wVikc1r1 (cluster (Pi k ) Xik) c2r2(Pgk Xik)其中，clusteMRk）表示對(duì)粒子歷代最優(yōu)解聚類后粒子 Xi所屬類的代表對(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)比較

40、接近問(wèn)題的解， 因此可以節(jié)省 搜索時(shí)間，提高算法收斂速度。3.5 兩個(gè)種群同時(shí)尋優(yōu)生物界中少數(shù)優(yōu)良個(gè)體進(jìn)行交叉，有利于產(chǎn)生優(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)的PSO算法求解TSP流程如下：Step1 ：用

41、貪婪算法產(chǎn)生兩個(gè)初始種群 A 群和 B 群，隨機(jī)產(chǎn)生兩個(gè)基本交 換序作為兩個(gè)種群的初始速度， 每個(gè)粒子位置向量的每一維隨機(jī)取 0,1 之間的 實(shí)數(shù)，設(shè)定粒子群算法的參數(shù)w, cl, c2;Step2:計(jì)算粒子適應(yīng)度，確定個(gè)體極值pbest和全局極值gbest;Step3 :使用k-Means對(duì)粒子的歷史最優(yōu)解進(jìn)行聚類分析，確定每個(gè)粒子所 在的類以及類的中心點(diǎn)山血仆。Step4:以一定概率將A群粒子的個(gè)體最優(yōu)與B群粒子的個(gè)體最優(yōu)進(jìn)行交叉， 產(chǎn)生新的個(gè)體最優(yōu)；Step5 :為每個(gè)粒子按照式（3.4）和式（3.5）確定新的速度向量和下一代的位 置向量，并產(chǎn)生兩個(gè)新的全局最優(yōu)。Step6 :對(duì)新形成的

42、粒子群按照Step2的方法確定各粒子代表的可行解的路 徑長(zhǎng)度，更新粒子個(gè)體的歷史最優(yōu)位置和粒子群的全局最優(yōu)解。Step7 :如未滿足終止條件（一個(gè)種群兩次進(jìn)化適應(yīng)度之差小于最小誤差），則返回step3。改進(jìn)算法的流程圖如圖2所示:NU'fbi鎳東圖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-30

43、12-13-4-5-6 。圖3 Oliver30 問(wèn)題優(yōu)化結(jié)果采用Microsoft Visual Studio 2005為編程工具，實(shí)驗(yàn)環(huán)境為Intel(R)Core(TM) i3,2.13GHz CPU,2G內(nèi)存，Windows Vista 系統(tǒng)。為便于比較，將該改 進(jìn)PSOT法與基本PSOT法、遺傳算法分別連續(xù)進(jìn)行30次實(shí)驗(yàn)，對(duì)其結(jié)果進(jìn)行比較 分析。幾種算法中，種群的粒子數(shù)均為100。粒子群算法中慣性權(quán)重 唄1. 4線性 遞減到0.5，加速常數(shù)3= C2=1.2,K-means聚類數(shù)為5,最大迭代次數(shù)1000。遺傳 算法交叉概率Pc=0.2，變異概率Pm=05實(shí)驗(yàn)結(jié)果如表1所示，得到的最

44、優(yōu)結(jié)果 巡回路徑如圖3所示，其巡回路徑與目前已知最好解一致。表1 Oliver30實(shí)驗(yàn)結(jié)果比較算法平均值最好解最差解收斂率平均迭代 次數(shù)基本PSO457.6632435.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)解一致，基本 PSO算法最優(yōu)解為435.9918，無(wú)法收斂到當(dāng) 前最優(yōu)解，遺傳算法雖然也能收斂到當(dāng)前最優(yōu)解，但其收斂率25.37%和收斂速度遠(yuǎn)不如改進(jìn)的PSO算法的收斂率74.59%和收斂速度。綜上所述，用改進(jìn)的PSO 算法求解T