【正文】 ....................... .8 算法全局收斂性 ............................................... 11 各參數(shù)對收斂性能的影響分析 .， ................................ .12 應(yīng)用 ........................................................ .12 小結(jié) ......................................................... 12 4 總結(jié)和展望 ................................................... .. .14 參考文獻 ......................................... ...... ...... ..14 致謝 ....................................................... .....15 1 人工魚群算法在組合優(yōu)化問題的研究 何少武 摘 要： 組合優(yōu)化問題在現(xiàn)實生活中有著很廣泛的應(yīng)用，并且有很強的工程代表性，但最優(yōu)化解很困難，目前對組合優(yōu)化問題的求解主要以啟發(fā)式算法為主。近年來得到廣泛關(guān)注和應(yīng)用。蟻群算法決旅行商問題存在收斂速度慢，而且參數(shù)的設(shè)定對算法的性能影響很大，而人工魚群算經(jīng)過實例證明具有優(yōu)于蟻群算法的收斂速度。組合優(yōu)化問題 。 binatorial optimization problems。geic algorithms 2 1 緒論 課題背景及意義 優(yōu)化問題是 工業(yè)設(shè)計 中經(jīng)常遇到的問題 ,許多問題最后都可以歸結(jié)為優(yōu)化問題 。典型的組合優(yōu)化問題有旅行商問題、背包問題、車間作業(yè)調(diào)度問題、裝箱問題、圖著色問題、聚類問題等。目前常見的啟發(fā)式算法有遺傳算法、模擬退火算法、禁忌搜索算法、人工魚群算法、蟻群算法、粒子群算法等。得到國內(nèi)外學者的廣泛關(guān)注，目前處于研究改進階段。人工魚群算法對目標函數(shù)的性質(zhì)要求不高，對初值要不高，對參數(shù)設(shè)定的要求不高，具備全局優(yōu)化能力，能夠快速跳出局部極值點。 課題的研究現(xiàn)狀 優(yōu)化問題是生產(chǎn)過程中廣泛存在的一個問題，經(jīng)過優(yōu)化處理后，生產(chǎn)過程系統(tǒng)會降低能量消耗、提高生產(chǎn)效率。人工魚群算法是一種新型的智能優(yōu)化算法，目前用人工魚群算法解決組合 優(yōu)化問題還是一個比較新的領(lǐng)域。與其他群集智能算法相比，人工魚群算法既有相同點又有自己的特點和相異之處。這些不同算法的共同目的是盡量提高其解的精度。 3 近年連來有很多的國內(nèi)外學者在研究遺傳算法，粒子群算法 解決 TSP 問題。 JSP 問題的研究廣泛吸收遺傳算法，粒子群算法，人工神經(jīng)網(wǎng)絡(luò)，模擬退火算法的精髓。JSP 遺傳進化創(chuàng)造 JSP遺傳算法所需要的遺傳算子，包括選擇，交叉，變異，組合算子，同時設(shè)定遺傳進化參數(shù) 。 2 解決組合優(yōu)化問題的幾種智能算法 遺傳算法 遺傳算法是從代表問題可 能潛在的解集的一個 種群 （ population）開始的，而一個種群則由經(jīng)過 基因 （ gene）編碼的一定數(shù)目的個體 (individual)組成。染色體作為 遺傳物質(zhì) 的主要載體，即多個基因的 集合 ，其內(nèi)部表現(xiàn)（即 基因型 ）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如 二進制 編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（ generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的 適應(yīng)度 （ fitness）大小選擇（ selection）個體，并借助于自然遺傳學的遺傳 算子 （ geic operators）進行組合交叉（ crossover）和變異（ mutation），產(chǎn)生出代表新的解集的種群。 與傳統(tǒng)的優(yōu)化算法相比，遺傳算法具有以下特點 : (1)遺傳算法從問題解的串集開始搜索，而不是從單個解開始。傳統(tǒng)優(yōu)化算法是從單個初始值 迭代 求最優(yōu)解的；容易誤入局部最優(yōu)解。 (2)遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優(yōu)解的風險，同時算法本身易于實現(xiàn)并行化。 適應(yīng)度 函數(shù)不僅不受 連續(xù)可微 的約束，而且其 定義域 可以任意設(shè)定。 (4)遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來 指導 他的搜索方向。遺傳算法利用進化過程獲得的信息自行組織搜索時， 適應(yīng)度 大的個體具有較高的生存概率，并獲得更適應(yīng) 環(huán)境 的 基因結(jié)構(gòu) 。它由 Marco Dorigo 于 1992 年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。針對 PID 控制器參數(shù)優(yōu)化設(shè)計問題，將蟻群算法設(shè)計的結(jié)果與遺傳算法設(shè)計的結(jié)果進行了比較，數(shù)值仿真結(jié)果表明，蟻群算法具有一種新的模擬進化優(yōu)化方法的有效性和應(yīng)用價值。 (2)分布式計算，蟻群算法是一種基于種群的進化算法，具有本質(zhì)并行性，易于并行實現(xiàn) 。 諸多研究表明，蟻群算法具有很強的尋優(yōu)能力，不僅利用了正反饋原理，而且是一種本質(zhì)并行算法，不同個體之間不斷進行著信息交流與傳遞，從而能夠相互 協(xié)作，有利于發(fā)現(xiàn)較好的解。 (2)對于蟻群中的每只螞蟻，每個解構(gòu)造。 (3)以某些已獲得的解為起點進行鄰域搜索 .(4)根據(jù)某些己知獲得的質(zhì)量進行全局信息素更新。 (6)達到條件，結(jié)束。此時，螞蟻走過的路徑對應(yīng)求解問題的一個可行解。蟻群算法的參數(shù)的選擇更多還是依靠實驗和經(jīng)驗，沒有定理來確定解決組合優(yōu)化問題的幾種智能算法，而且計算時間偏長。 n 個城市的 TSP 問題就是尋找通過 n 個城市各 一次 且 最后回到出發(fā)點的最短路徑。 ijd（ ji, =1， 2... n ）表示城市 i 和 j 之間的路徑上殘留的信息量。 在初始化的時候， m 個螞蟻被放置在不同的城市上，賦予每條邊上的信息量為 ij? （ 0） 。 用 )(tpkij 表示在￡時刻螞蟻 k 由城市 i 轉(zhuǎn)移到城市 j 的概率，則 )(tpkij =?o th e r w is ea llo w e djtttt ka llo w e dr ijijijijk ,0,)()( )()( ??????????? （ 1） 其中 kallowed 表示螞蟻 k 下一步允許走過的城市的集合，它隨螞蟻 k 的行進過程而動態(tài)改變；信息量 )(tij?? 隨時間的推移會逐步衰減，用 1? 表示 ??, 分別 表示螞蟻在運動過程中所積累的信息量及 啟發(fā)式因子在螞蟻選擇路徑中所起的不同作用 , )(tij? 為由城市 i 轉(zhuǎn)移到城市 j 的期望程度 可根據(jù)某種啟發(fā)算法而定。螞蟻 k 走完所有的城市，完成一次循環(huán)。 粒子群算法 粒子群算法，也稱 粒子群優(yōu)化算法 （ Particle Swarm Optimization），縮寫為 PSO， 是近年來發(fā)展起來的一種新的進化算法（ Evolu2tionary Algorithm EA）。這種算法以其實現(xiàn)容易、精度高、收斂快等優(yōu)點引起了學術(shù)界的重視，并且在解決實際問題中展示了其優(yōu)越性。在這個區(qū)域里只有一塊食物。但是他們知 道當前的位置離食物還有多遠。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。 PSO 中，每個優(yōu)化問題的解都是搜索空間中的一只鳥。所有的例子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值 (fitnessvalue)，每個粒子還有一個速度決定他們飛翔的方向和距離。 PSO 初始化為一群隨機粒子 (隨機解 )。在每一次疊代中，粒子通過跟蹤兩個 極值 來更新自己。這個解叫做個體極值 。另外也可以不用整個種群而只是用其中一部分最為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。 通常 1