【正文】 ptimization problems。 flocking behavior。geic algorithms 2 1 緒論 課題背景及意義 優(yōu)化問題是 工業(yè)設計 中經(jīng)常遇到的問題 ,許多問題最后都可以歸結(jié)為優(yōu)化問題 。 組合優(yōu)化，又稱離散優(yōu)化問題，是通過對數(shù)學方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，是運籌學中一個經(jīng)典且重要的分支， 隨著計算機科學、管理科學、現(xiàn)代化生產(chǎn)技術等的日益發(fā)展，這類問題與日俱增，受到諸多學者的 高度重視。典型的組合優(yōu)化問題有旅行商問題、背包問題、車間作業(yè)調(diào)度問題、裝箱問題、圖著色問題、聚類問題等。這些問題描述簡單，并且有很強的工程代表性，但最優(yōu)化求解很困難，其主要原因是求解這些問題的算法需要極長的運行時間與極大的存儲空間，以致根本不可能在現(xiàn)有計算機上實現(xiàn)，即所謂的“組合爆炸”。目前常見的啟發(fā)式算法有遺傳算法、模擬退火算法、禁忌搜索算法、人工魚群算法、蟻群算法、粒子群算法等。 人工魚群算法是我國學者在 20xx 年提出的一種新的群智能算法。得到國內(nèi)外學者的廣泛關注，目前處于研究改進階段。人工魚群算法已經(jīng) 成為交叉學科中一個非?；钴S的研究問題。人工魚群算法對目標函數(shù)的性質(zhì)要求不高，對初值要不高，對參數(shù)設定的要求不高，具備全局優(yōu)化能力，能夠快速跳出局部極值點。具有并行性，簡單性，全局性，快速性。 課題的研究現(xiàn)狀 優(yōu)化問題是生產(chǎn)過程中廣泛存在的一個問題，經(jīng)過優(yōu)化處理后，生產(chǎn)過程系統(tǒng)會降低能量消耗、提高生產(chǎn)效率。為提供解決優(yōu)化領域的問題的有效方法，智能搜索算法綜合了生物學、計算機和人工智能等各個科學領域的知識，隨著各個科學的發(fā)展，也是逐漸深入的。人工魚群算法是一種新型的智能優(yōu)化算法，目前用人工魚群算法解決組合 優(yōu)化問題還是一個比較新的領域。人工魚群算法（ AFSA）是浙江大學的李曉磊、錢積新等人提出的， 20xx 年李曉磊在其博士論文中對人工魚群算法進行了系統(tǒng)的介紹。與其他群集智能算法相比，人工魚群算法既有相同點又有自己的特點和相異之處。對 TSP 問題，優(yōu)化專家們提出各種不同啟發(fā)式算法，以得到該問題的近似優(yōu)化算法。這些不同算法的共同目的是盡量提高其解的精度。各類啟發(fā)式算法是目前比較理想的算法，適用于不同規(guī)模和時間要求的TSP 問題，他們都可以得到局部最優(yōu)解或全局最優(yōu)解。 3 近年連來有很多的國內(nèi)外學者在研究遺傳算法，粒子群算法 解決 TSP 問題。并且取得了一定的成效。 JSP 問題的研究廣泛吸收遺傳算法，粒子群算法，人工神經(jīng)網(wǎng)絡，模擬退火算法的精髓。解決 TSP 問題主要有三步 :JSP 仿生，創(chuàng)建 JSP遺傳算法所需要的材料，包括 JSP 染色體以及個體群組 。JSP 遺傳進化創(chuàng)造 JSP遺傳算法所需要的遺傳算子，包括選擇，交叉，變異，組合算子，同時設定遺傳進化參數(shù) 。JSP 仿真，以 JSP 的實際需求為依據(jù)，定義 JSP 遺傳算法所需要的 JSP個體適應度，并設計 JSP 個體適應度的求解方法。 2 解決組合優(yōu)化問題的幾種智能算法 遺傳算法 遺傳算法是從代表問題可 能潛在的解集的一個 種群 （ population）開始的，而一個種群則由經(jīng)過 基因 （ gene）編碼的一定數(shù)目的個體 (individual)組成。每個個體實際上是 染色體 (chromosome)帶有特征的實體。染色體作為 遺傳物質(zhì) 的主要載體，即多個基因的 集合 ，其內(nèi)部表現(xiàn)（即 基因型 ）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現(xiàn)從 表現(xiàn)型 到基因型的 映射 即 編碼 工作。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如 二進制 編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（ generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的 適應度 （ fitness）大小選擇（ selection）個體，并借助于自然遺傳學的遺傳 算子 （ geic operators）進行組合交叉（ crossover）和變異（ mutation），產(chǎn)生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過 解碼 （ decoding），可以作為問題近似最優(yōu)解。 與傳統(tǒng)的優(yōu)化算法相比，遺傳算法具有以下特點 : (1)遺傳算法從問題解的串集開始搜索，而不是從單個解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初始值 迭代 求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆 蓋面大，利于全局擇優(yōu)。 (2)遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優(yōu)解的風險，同時算法本身易于實現(xiàn)并行化。 4 (3)遺傳算法基本上不用搜索空間的知識或其它 輔助信息 ，而僅用 適應度 函數(shù)值 來評估個體，在此基礎上進行 遺傳操作 。 適應度 函數(shù)不僅不受 連續(xù)可微 的約束，而且其 定義域 可以任意設定。這一特點使得遺傳算法的應用范圍大大擴展。 (4)遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來 指導 他的搜索方向。 (5)具有自 組織、自適應和自學習性。遺傳算法利用進化過程獲得的信息自行組織搜索時， 適應度 大的個體具有較高的生存概率，并獲得更適應 環(huán)境 的 基因結(jié)構(gòu) 。 蟻群算法 蟻群算法，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法。它由 Marco Dorigo 于 1992 年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。針對 PID 控制器參數(shù)優(yōu)化設計問題，將蟻群算法設計的結(jié)果與遺傳算法設計的結(jié)果進行了比較，數(shù)值仿真結(jié)果表明，蟻群算法具有一種新的模擬進化優(yōu)化方法的有效性和應用價值。 與遺傳算法，模擬退火算法等模擬進化算法一樣，通過候選解組成的群體在 進化過程中來尋找最優(yōu)解具有以下特點 : (l)較強通用性，對基本蟻群算法模型稍加修改，便可以應用于其它問題 。 (2)分布式計算，蟻群算法是一種基于種群的進化算法，具有本質(zhì)并行性，易于并行實現(xiàn) 。 (3)易與其它方法結(jié)合 :蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法的功能 。 諸多研究表明，蟻群算法具有很強的尋優(yōu)能力，不僅利用了正反饋原理，而且是一種本質(zhì)并行算法，不同個體之間不斷進行著信息交流與傳遞，從而能夠相互 協(xié)作，有利于發(fā)現(xiàn)較好的解。 蟻群算法解決組合優(yōu)化問題的主要步驟有 :(l)設置參數(shù)，初始信息蹤跡。 (2)對于蟻群中的每只螞蟻，每個解構(gòu)造。螞蟻按照信息素及啟發(fā)式信息的指引構(gòu)造一步問題的解，進行局部信息素更新。 (3)以某些已獲得的解為起點進行鄰域搜索 .(4)根據(jù)某些己知獲得的質(zhì)量進行全局信息素更新。 (5)如果不滿足結(jié)束條件，再轉(zhuǎn)到 (2)。 (6)達到條件，結(jié)束。以上算法 5 中，螞蟻逐步構(gòu)造問題的可行解，在一步解構(gòu)造過程中，螞蟻以概率方式選擇信息素強且啟發(fā)式因子高的弧達到下一個節(jié)點，直到不能繼續(xù)移動為止。此時，螞蟻走過的路徑對應求解問題的一個可行解。局部信息素更新針對螞蟻當前走過的一步路徑上的信息素進行，全局信息素更新 是在所有螞蟻找到可行解之后，根據(jù)發(fā)現(xiàn)解的質(zhì)量或者當前算法找到的最好路徑上的信息素進行更新。蟻群算法的參數(shù)的選擇更多還是依靠實驗和經(jīng)驗，沒有定理來確定解決組合優(yōu)化問題的幾種智能算法，而且計算時間偏長。 我們以求解平面上 n 個城市的 JSP 問題 (1， 2，?， n 表示城市序號 )為例說明 蟻群算法 的模型。 n 個城市的 TSP 問題就是尋找通過 n 個城市各 一次 且 最后回到出發(fā)點的最短路徑。 為模擬實際螞蟻的行為，首先引人如下記號：設 m 是蟻群巾螞蟻的數(shù)量。 ijd（ ji, =1， 2... n ）表示城市 i 和 j