改進粒子群算法求解TSP問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、校主管部門確認并我單位經(jīng)自查，承諾該作品符合挑戰(zhàn)杯申報作品的要簽章求，接受競賽組委會抽查。（簽章）年月日各?。▍^(qū)、市） 評審委員會初評 意見年（簽章） 月日各省（區(qū)、市）組織協(xié)調(diào)委員會 審定意見團委科協(xié)教育廳學聯(lián)（簽章）（簽章）（簽章）（簽章）年月日E.組織委員會秘書處資格和形式審查意見組委會秘書處資格審查意見審查人（簽名） 年 月日組委會秘書處形式審查意見審查人（簽名）年 月日組委會秘書處審查結(jié)果合格不合格負責人（簽名）年 月日F1.評審委員會預(yù)審意見粘貼處F2 評審委員會終審意見粘貼處（正文打印頁 ）基于k-means的改進粒子群算法求解TSP問題陳國鴻（ 河池學院 計算機與信息科學系 ,

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

20、子的搜索空間， 避免了算法陷入局部最 優(yōu)。兩個種群同時尋優(yōu)，種群內(nèi)部獨立進行PSOS化，種群個體最優(yōu)之間以一定概率進行交叉， 減小算法陷入局部最優(yōu)的概率， 種群間個體最優(yōu)的交叉能夠增強兩種群 間以及粒子間的信息共享， 及時傳遞最優(yōu)值信息， 提高粒子向更好解進化的速度。 實驗證明， 改進后的粒子群算法能有效地求解 TSP問題。關(guān)鍵詞旅行商問題；粒子群算法； K-means;貪心算法0 引言旅行商問題 (Traveling Salesman Problem，簡稱TSP）又名貨郎擔問題,是一個典型的 NP 完全問題。原型描述：給定求一條訪問各個城市且僅訪問一次的最短路線。N 個城市和兩兩城市之見的距

21、離, 雖然其數(shù)學描述非常簡單, 但卻TSP 問題,另一方面很多研究領(lǐng) 域出現(xiàn)的復(fù)雜優(yōu)化問題可以被抽象概括為 TSP 問題加以求解,因此找到能夠有無法找到一個確定的算法在多項式時間內(nèi)求解效解決 TSP 問題的方法 ,在理論上和實際應(yīng)用中都很有價值。粒子群算法（Particle SwarmOptimization，簡稱PSO算法最早是在1995 年由美國社會心理學家 James Kennedy和電氣工程師 Russell Eberhart 共同提出的一種全局優(yōu)化算法， 該算法的基本思想來源于對鳥群簡化社會模型的研究及 行為模擬， 其中的每個個體充分利用群體的與自身的智能， 不斷地調(diào)整學習， 最 終

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

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

24、n 回路，即遍 歷所有頂點一次且僅一次的最短回路。設(shè)dij 為城市 i 與 j 之間的距離，即弧( i,j) 的長度。引入決策變量：1 若旅行商訪問城市 i 后訪問城市 jXij =0 否則 (1.1)nMin ZXij dij則TSP的目標函數(shù)為i,j 1(1.2)TSP 問題描述非常簡單， 但最優(yōu)化求解很困難， 若用窮舉法搜索， 則要考慮所有可能情況， 并兩兩對比， 找出最優(yōu) , 其算法復(fù)雜性呈指數(shù)增長 , 即所謂的“組 合爆炸”。所以，尋求和研究 TSP的有效啟發(fā)式算法，是問題的關(guān)鍵。2基本PSO算法PSO算法主要模擬鳥群飛行的覓食行為，通過鳥群的集體協(xié)作達到尋優(yōu)目 的。在PSO算法中，

25、每個粒子利用自身的歷史最優(yōu)位置和整個粒子群的全局最優(yōu) 解提供的信息，在解空間內(nèi)不斷飛行，實現(xiàn)尋找最優(yōu)解的目的。2.1基本PSO算法的數(shù)學描述如下：設(shè)搜索空間為N維，總粒子數(shù)為Num 第i個粒子的位置向量 人=(冷必2必3,，滄)，第)個粒子的速度向量是Vi =(Vii，Vi2，Vi3，-, Vin)，第i個 粒子在“飛行”中的歷史最優(yōu)位置是 P=( Pi1, Pi2, Pi3,，Pn)，Pg表示目前為止在 整個粒子群中發(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)其中，下標“j”表示第j維，t為飛行的次數(shù)；w為慣性權(quán)重，使粒子保持 運動慣性，控制前一速度對當前速度的影響，較大的w適于對解空間進行大規(guī)模 探查，較小的w適合于進行小范圍開挖；c1，c2為加速常數(shù)，通常在02間 取值，c1調(diào)節(jié)粒子飛向自身最好位置方向的步長，c2調(diào)節(jié)粒子向全局最好位置 飛行步長；rand1()和rand2 ()是0,1 之間相互獨立的隨機數(shù)。粒子的位置 向量中各維變化范圍為Xmin , Xmax，速度變化范圍為Vmin, Vmax，迭代中若位 置和速度超過邊界范圍則取邊界值。PSO算法通過

27、粒子在解空間內(nèi)不斷地變化速 度向量來改變位置，最終找到最優(yōu)解。2.2 基本粒子群算法的流程如下:Stepl :依照初始化過程，對粒子群的隨機位置和速度進行初始設(shè)定；Step2 :計算每個粒子的適應(yīng)值；Step3:對于每個粒子，將其適應(yīng)值與所經(jīng)歷過的最好位置P的適應(yīng)值進行比較，若較好，則將其作為當前的最好位置；Step4 :對每個粒子，將其適應(yīng)值與全局所經(jīng)歷的最好位置Pg的適應(yīng)值進行比較，若較好，則將其作為當前的全局位置；Step5 :根據(jù)方程(2.1)、(2.2)對粒子的速度和位置進行迭代進化；Step6 :循環(huán)步驟2-5，直到結(jié)束條件為足夠好的適應(yīng)值或達到一個預(yù)設(shè)最 大迭代次數(shù)，算法終止。3

28、改進的粒子群算法求解TSP問題3.1 定義更新TSP問題為離散問題，用PSO求解TSP問題需要對基本PSO算法中粒子的位 置、速度以及操作進行重新定義：(1) 狀態(tài)空間TSP問題的結(jié)果是要求出具有最短路徑的哈密爾頓圈，所以狀態(tài)空間即為所有位置的集合。(2) 粒子的位置粒子的位置可以定義為一個具有所有節(jié)點的哈密爾頓圈，設(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) 粒子位置與速度的加法操作 該操作表示將一組置換序列依次作用于某個粒子位置， 其結(jié)果為一個新的位 置，即一個新的節(jié)點的排列。 例如：位置為 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 ,所以第一個交換為so1 =(1,3),X1=X+ so1 =2,41,5,3,2+(1,3)=1,4,2,5,3,1 ；X1(2)=Y(4)=4 ,因此第二個交換 為 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) 粒子速度與速度的加法操作 粒子速度與速度的加法操作為兩個置換序列的合并,結(jié)果為一個新的置換 序列,即一個新的速度。例如：速度 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ù) c 為(0, 1 )的任意實數(shù), 設(shè)速度 v 為 k 個置換序列, 則乘法操作為對速 度置換序列進行截取，使得新的速度的置換序列長度為|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) 上均勻分布的兩個相互獨立的隨機數(shù)；為兩交換序的合并算子，表示速度與速度的加法操作； 表示粒子位置與位置的減法操作； 表示粒子位置與速度的 加法操作。3.3 基于 k-means 的改進措施 具有良好多樣性的粒子群能增加粒子在迭代中獲得的有效信息量， 這不僅能 擴大粒子在解空間內(nèi)的搜索范圍， 而且在算法陷入局部最優(yōu)時， 有助于粒子逃離 局部最優(yōu)區(qū)域

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

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

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

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

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

38、進粒子群算法PSO算法在迭代中使用了兩個不同的粒子群： 各粒子的歷史最優(yōu)位置組成的 粒子群 1；各粒子在迭代中動態(tài)變化的粒子群 2。粒子群 2 在搜索的過程中是對 整個解空間進行的隨機搜索， 在每次迭代中其變化的速度較快， 而且其變化后的 粒子并不一定代表較好的結(jié)果， 故其提供的信息對其他粒子而言并不具有很好的 指導意義； 相反，粒子群 1 在迭代過程中相對穩(wěn)定， 而且具有的信息往往能夠代 表粒子在解空間各局部區(qū)域的優(yōu)質(zhì)信息， 為其他粒子提供了較好的指導信息。 因此，我們選擇對粒子群1進行聚類分析。綜上，基于k-means的改進PSO算法的 速度和位置向量更新方式為：3.4)XiXik Vik

39、 13.5)Vik 1 wVikc1r1 (cluster (Pi k ) Xik) c2r2(Pgk Xik)其中，clusteMRk）表示對粒子歷代最優(yōu)解聚類后粒子 Xi所屬類的代表對象，其 他參數(shù)的含義與基本PSO算法的含義相同。3.4 貪心算法產(chǎn)生初始種群由于旅行商問題為一個循環(huán)回路，所以起始城市可以為任意的一個城市。本文采用貪心算法的思想， 隨機選擇一個城市作為出發(fā)城市， 并始終選擇距離當 前城市最近的城市作為下一個遍歷城市， 直到所有城市均被遍歷后直接連接到出 發(fā)城市即可。至此，可以利用這個貪心算法得到近似最優(yōu)循環(huán)序列，產(chǎn)生一定規(guī)模的初 始種群。這樣產(chǎn)生的初始種群全局最優(yōu)值已經(jīng)比較

40、接近問題的解， 因此可以節(jié)省 搜索時間，提高算法收斂速度。3.5 兩個種群同時尋優(yōu)生物界中少數(shù)優(yōu)良個體進行交叉，有利于產(chǎn)生優(yōu)良的后代，并保證了父代 優(yōu)良品性的繁衍， 符合生物界優(yōu)勝劣汰的進化機制， 因此， 交叉產(chǎn)生的個體最優(yōu) 有利于種群的進化。 本文根據(jù)這一生物界的繁衍規(guī)律， 提出兩個種群同時尋優(yōu)的 機制，即種群內(nèi)部獨立進行 PSO進化，種群個體最優(yōu)之間以一定概率進行交叉。 兩個種群同時尋優(yōu)可以減小算法陷入局部最優(yōu)的概率， 種群間個體最優(yōu)的交叉能 夠增強兩種群間以及粒子間的信息共享， 及時傳遞最優(yōu)值信息， 提高粒子向更好 解進化的速度。3.6改進的PSO算法求解TSP流程如下：Step1 ：用

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

42、粒子群按照Step2的方法確定各粒子代表的可行解的路 徑長度，更新粒子個體的歷史最優(yōu)位置和粒子群的全局最優(yōu)解。Step7 :如未滿足終止條件（一個種群兩次進化適應(yīng)度之差小于最小誤差），則返回step3。改進算法的流程圖如圖2所示:NU'fbi鎳東圖2改進粒子群算法流程圖4實驗結(jié)果及分析為了檢驗算法的有效性，本文選用Oliver30作為實驗例子，并與基本 PSO算法，遺傳算法進行比較。目前已知Oliver30問題的最好解為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 問題優(yōu)化結(jié)果采用Microsoft Visual Studio 2005為編程工具，實驗環(huán)境為Intel(R)Core(TM) i3,2.13GHz CPU,2G內(nèi)存，Windows Vista 系統(tǒng)。為便于比較，將該改 進PSOT法與基本PSOT法、遺傳算法分別連續(xù)進行30次實驗，對其結(jié)果進行比較 分析。幾種算法中，種群的粒子數(shù)均為100。粒子群算法中慣性權(quán)重 唄1. 4線性 遞減到0.5，加速常數(shù)3= C2=1.2,K-means聚類數(shù)為5,最大迭代次數(shù)1000。遺傳 算法交叉概率Pc=0.2，變異概率Pm=05實驗結(jié)果如表1所示，得到的最

44、優(yōu)結(jié)果 巡回路徑如圖3所示，其巡回路徑與目前已知最好解一致。表1 Oliver30實驗結(jié)果比較算法平均值最好解最差解收斂率平均迭代 次數(shù)基本PSO457.6632435.9918480.14520.00遺傳算法425.6905423.7406429.487625.37%735.40改進PSO424.7926423.7406425.693174.59%583.00表1中，收斂率是30次實驗中，算法收斂到最優(yōu)值423.7406的次數(shù)與實驗 次數(shù)30之比。由表中數(shù)據(jù)可知，改進的 PSO算法最優(yōu)解為423.7406，與當前 Oliver30問題的最優(yōu)解一致，基本 PSO算法最優(yōu)解為435.9918，無法收斂到當 前最優(yōu)解，遺傳算法雖然也能收斂到當前最優(yōu)解，但其收斂率25.37%和收斂速度遠不如改進的PSO算法的收斂率74.59%和收斂速度。綜上所述，用改進的PSO 算法求解T