一種基于正交離散過程的蟻群算法畢業(yè)論文.doc

鄭州航空工業(yè)管理學(xué)院畢 業(yè) 論 文（設(shè) 計） XXXXXXXXX 屆 機械設(shè)計制造及其自動化 專業(yè) 班級題 目 基于正交離散過程的蟻群算法 姓 名 XXXXXXXXXX 學(xué) 指導(dǎo)教師 XXX 職稱 XX 二一 年 五 月 十八 日基于正交離散過程的蟻群算法內(nèi) 容 摘 要 蟻群算法是一種仿生優(yōu)化算法，其靈感來源于真實蟻群的覓食機理，這種思想吸收了螞蟻群體有規(guī)律的行為，通過對真實蟻群搜索食物過程的模擬來完成對問題的求解。 本文首先介紹了蟻群算法的研究進(jìn)展和基本原理，然后對蟻群算法的改進(jìn)優(yōu)化和仿真應(yīng)用分別進(jìn)行了描述。為了解決蟻群算法在初始階段執(zhí)行效率低下、信息素隨機分布、路徑雜亂無章的缺點，本文采取了幾項改進(jìn)措施。例如：將正交設(shè)計方法引入初始化中，創(chuàng)建正交離散過程，形成正交優(yōu)化的路徑設(shè)置；優(yōu)化初始化過程，以便形成初始解；以動態(tài)概率轉(zhuǎn)移規(guī)則來構(gòu)造新的路徑；精練的選路策略等改進(jìn)措施的初始路徑優(yōu)化模型。該模型提高了算法的執(zhí)行效率，其成功應(yīng)用于解決連續(xù)域問題的啤酒配方設(shè)計方面，表明該方法是有效可行的，同時開辟了一條解決啤酒配方設(shè)計問題的新途徑，對蟻群算法解決連續(xù)域問題提供了可供參考的模型和求解方法。 關(guān)鍵詞蟻群算法；正交設(shè)計；正交離散；連續(xù)優(yōu)化；啤酒配方設(shè)計 Ant Colony Algorithm based on orthogonal discrete process (Mechanical and electrical engineering institute, Aviation industry management college in zheng zhou )Abstract The ant colony algorithm is a novel simulated evolutionary algorithm, which is inspired by foraging mechanisms of real ant colonies. This idea absorbs the regular behaviors of the ants colonies, by simulating the process of the real ant colonys searching for food to solve the problems.The current research progresses and basic principle of ant colony algorithm are firstly introduced in this paper, then the improvement optimization and simulation application of ant colony algorithm are also overviewed respectively. In order to solve the problems of low efficiency, randomly distributed pheromone, scrambled paths in the initial stage of the ant colony algorithm. Several improved methods of the initial paths optimization model are proposed. For example, the orthogonal design method is introduced to the initial route optimization course so as to create orthogonal discrete process and form the path settings of orthogonal optimization; The initial course is optimized in order to get the initial solutions; Dynamical transfer rules are used to construct the new paths; Refined routing strategies and so on. This model enhances the implementation efficiency of the algorithm. And then the beer recipe design simulation application is successfully presented to prove validity and feasibility of the proposed method, consequently, opening up a new way in terms of beer recipe design, and the method offers referenced models and solving methods for ant colony algorithm to solve the continual domain problems. Key wordsAnt Colony Algorithm; orthogonal design; orthogonal discretion; continuous optimization; beer recipe design 目 錄內(nèi)容摘要. 1Abstract. 2第一章 緒論61.1 研究背景61.2 國內(nèi)外對蟻群算法的研究進(jìn)展71.3 本文的研究主線及體系結(jié)構(gòu)7第二章 蟻群算法92.1 蟻群算法的基本原理及其數(shù)學(xué)模型92.1.1 真實蟻群的覓食機理92.1.2 基本蟻群算法數(shù)學(xué)模型的建立112.1.3 基本蟻群算法的系統(tǒng)學(xué)特征132.2 基本蟻群算法的具體實現(xiàn)142.2.1 基本蟻群算法的實現(xiàn)步驟142.2.2 基本蟻群算法的程序結(jié)構(gòu)流程圖15第三章 基于正交離散過程的蟻群算法173.1 正交試驗設(shè)計173.1.1 正交試驗設(shè)計的基本概念173.1.2 正交試驗設(shè)計的基本原理173.1.3 正交表及其基本性質(zhì)193.2 基于正交離散過程的蟻群算法203.2.1 正交離散過程蟻群算法的基本原理203.2.2 正交離散過程蟻群算法的尋優(yōu)過程233.2.3 正交離散過程蟻群算法的數(shù)學(xué)模型263.3 正交離散過程蟻群算法的具體實現(xiàn)273.3.1 正交離散過程蟻群算法的實現(xiàn)步驟273.3.2 正交離散過程蟻群算法的程序結(jié)構(gòu)流程圖273.4 正交離散過程蟻群算法的仿真應(yīng)用29第四章 本文的工作總結(jié)與展望344.1 本文的工作總結(jié)344.2 展望34致 謝35參考文獻(xiàn)36 第一章 緒論1.1 研究背景根據(jù)螞蟻群體尋找食物的行為，1991年，意大利學(xué)者Dorigo M.等人在法國巴黎召開的第一屆歐洲人工生命會議上提出了基本蟻群算法的基本模型；1992年，Dorigo M在其博士論文中又進(jìn)一步描述了蟻群算法的基本原理。蟻群算法是最新發(fā)展起來的一種模擬螞蟻群體智能行為的仿生優(yōu)化算法，該算法采用了正反饋并行自催化機制，在解決許多實際復(fù)雜優(yōu)化問題方面展現(xiàn)出了良好性能和巨大的發(fā)展?jié)摿?，近幾年吸引了國?nèi)外許多學(xué)者對蟻群算法進(jìn)行了多方面的研究工作。國際頂級學(xué)術(shù)期刊Nature曾多次對蟻群算法的研究成果進(jìn)行報道，IEEE Transactions On Evolutionary Computation和Future Generation Computer Systems分別在2001年和2003年出版了蟻群算法特刊，在布魯塞爾每兩年召開一次的蟻群算法國際研討會進(jìn)一步促進(jìn)了該仿生優(yōu)化算法的學(xué)術(shù)交流，從而使蟻群算法展示出了勃勃生機和廣闊的發(fā)展前景。目前，這種新生的仿生優(yōu)化算法已成為在國際智能計算領(lǐng)域中備受關(guān)注的前沿性課題和研究熱點。1.2 國內(nèi)外對蟻群算法的研究進(jìn)展自從1991年意大利學(xué)者DorigoM.首次提出蟻群算法以后，蟻群算法逐漸得到了世界許多研究者的關(guān)注，其在很多領(lǐng)域得到了很好的應(yīng)用，在這期間國內(nèi)外大量有價值的研究成果也陸續(xù)發(fā)表。2000年，Dorigo M和Bonabeau E等在國際頂級學(xué)術(shù)刊物Nature上發(fā)表了蟻群算法的研究綜述，從而把這一領(lǐng)域的研究推向了國際學(xué)術(shù)最前沿性的課題，鑒于Dorigo M在蟻群算法研究領(lǐng)域做出的的杰出貢獻(xiàn)，2003年11月歐盟委員會特別授予他“居里夫人杰出成就獎”。我國在蟻群算法領(lǐng)域的研究也取得了一些令世人矚目的成就：陳燁在2001年發(fā)表了帶雜交算子的蟻群算法一文，并且基于Visual Basic開發(fā)了一個功能齊全人性化的“蟻群算法實驗室”。在2003到2005年間，李艷君、段海濱提出了一種基于網(wǎng)格劃分措施的自適應(yīng)連續(xù)域蟻群算法和一種用于求解連續(xù)域優(yōu)化問題的自適應(yīng)連續(xù)域蟻群算法。在2008年，鄭松為了解決蟻群算法在解決組合優(yōu)化問題時收斂速度慢、消耗時間長的缺點，提出將確定性搜索引入基本蟻群算法的搜索過程中，并研究了改進(jìn)后的蟻群算法在啤酒配方優(yōu)化設(shè)計中的具體應(yīng)用。1.3 本文的研究主線及體系結(jié)構(gòu)1）本文的研究主線：研究主線是基于正交離散過程的蟻群算法，通過將蟻群算法與正交試驗設(shè)計相結(jié)合，把連續(xù)性問題離散化，在常規(guī)搜索中創(chuàng)建正交離散過程，優(yōu)化路徑設(shè)置提高算法的搜索速度和運行效率。將基于正交離散過程的蟻群算法應(yīng)用于啤酒原料配方設(shè)計實踐中，取得了非常好的效果，從而開辟了一種解決連續(xù)域變量問題的求解方法。2）本文的體系結(jié)構(gòu)：本文全面地介紹了蟻群算法的理論、方法及其具體實現(xiàn)，按照分析、深化、改進(jìn)、仿真應(yīng)用的邏輯結(jié)構(gòu)進(jìn)行安排，本文共分為四章，其內(nèi)容基本上構(gòu)成了一個完整體系，具體而言，各章主要包括如下內(nèi)容：第一章 闡述了蟻群算法的研究背景及國內(nèi)外對蟻群算法的研究進(jìn)展，同時列舉了部分改進(jìn)的蟻群算法及其應(yīng)用情況，最后給出了本文的研究主線和體系結(jié)構(gòu)。第二章 在介紹螞蟻的群體覓食行為特征的基礎(chǔ)上，從深層意義上進(jìn)一步分析蟻群算法的機制原理、數(shù)學(xué)模型、以及具體實現(xiàn)步驟，最后討論了基本蟻群算法的系統(tǒng)學(xué)特征。本章主要內(nèi)容對基本蟻群算法原理進(jìn)行分析，也是后面章節(jié)對蟻群算法進(jìn)行改進(jìn)研究的基礎(chǔ)。第三章 詳細(xì)闡述基于正交離散過程的蟻群算法。分析了正交試驗設(shè)計的基本原理、正交離散的基本原理、特點，以及正交離散過程蟻群算法實現(xiàn)尋優(yōu)過程的尋優(yōu)規(guī)則、數(shù)學(xué)模型，并分析了該改進(jìn)型蟻群算法在啤酒原料配方設(shè)計方面的仿真應(yīng)用等內(nèi)容。第四章 對本文的主要內(nèi)容進(jìn)行總結(jié)，討論了目前蟻群算法所存在的主要問題，然后從蟻群算法的模型改進(jìn)、理論分析、并行實現(xiàn)、應(yīng)用領(lǐng)域等方面對蟻群算法在以后的研究進(jìn)展方向進(jìn)行了討論。第二章 蟻群算法2.1 蟻群算法的基本原理及其數(shù)學(xué)模型2.1.1 真實蟻群的覓食機理 根據(jù)研究者的長期觀察發(fā)現(xiàn)：螞蟻在運動時會在路徑上釋放出一種信息素來尋找路徑。當(dāng)它們碰到一個陌生路口時，就任意挑選一條路徑前進(jìn)，同時釋放出與路徑長度相關(guān)的一定強度信息素。螞蟻走過的路徑越長，所釋放的信息素就越少。當(dāng)后來的螞蟻再次來到這個路口時，選擇信息素強度較大路徑的可能性較大，這樣蟻群之間就會形成一種信息正反饋機制。最短路徑上的信息素強度逐漸增大，而其他路徑上的信息素強度隨著時間的推移而逐漸消減，最終整個蟻群就會找出最佳路徑。如圖2.1.1（a）所示，我們總可以觀察到螞蟻群體在蟻穴與食物之間形成近似于直線形狀的路徑，而不是曲線、折線等其他形狀。如圖2.1.1（b）所示，在螞蟻運動路線上有障礙物出現(xiàn)時，開始時各只螞蟻均勻分布，不管路徑是長是短，螞蟻先隨機選擇各條路徑。螞蟻在運動過程中在經(jīng)過的路徑上留下一定強度的信息素，其他螞蟻能夠感知這種物質(zhì)的強度，并以此指導(dǎo)自己繼續(xù)向信息素濃度高的方向移動，如圖2.1.1（c）所示，螞蟻傾向于選擇信息素濃度高的路徑，在相等時間內(nèi)，較短路徑上遺留的信息素逐漸增多，選擇較短路徑的螞蟻也越來越多。螞蟻集體行為存在著一種信息正反饋現(xiàn)象，即螞蟻在某一路徑上經(jīng)過的次數(shù)越多，后來的螞蟻就越有可能選擇該路徑，螞蟻個體之間就是通過這種信息正反饋機制來搜索食物并最終找到最優(yōu)路徑的，如圖2.1.1（d）所示。 圖2.1.1 現(xiàn)實中蟻群尋找食物的過程 由上述可見，在整個尋優(yōu)過程中，雖然單只螞蟻的尋優(yōu)能力有限，但是整個蟻群的行為通過信息素的作用便具有非常高的自組織性能，螞蟻之間交換路徑信息素，最終通過螞蟻的正反饋機制找到最佳路徑。2.1.2 基本蟻群算法數(shù)學(xué)模型的建立蟻群算法首先成功應(yīng)用于TSP問題，TSP問題就是給定n個城市與城市之間的距離，某一旅行商從某一城市出發(fā)，逐個訪問各個城市一次且僅一次后再回到原來出發(fā)的城市，找出一條最短的巡游路徑。下面我們以簡單的TSP問題為例來說明蟻群算法基本原理。將m只螞蟻隨機放在n個城市上,設(shè)初始時刻各個城市之間每一條路徑上的信息素強度=c (c是常數(shù)), 表示禁忌表,記錄當(dāng)前螞蟻所走過的城市集合, 不允許螞蟻再次訪問禁忌表中的城市結(jié)點。當(dāng)n個城市結(jié)點都進(jìn)入禁忌表中時,表示螞蟻進(jìn)行了一次完整循環(huán)。在搜索當(dāng)中, 螞蟻根據(jù)狀態(tài)轉(zhuǎn)移概率來選擇各條路徑上的城市節(jié)點。在t時刻,螞蟻k（k=1,2,m）由城市i轉(zhuǎn)移到城市j的轉(zhuǎn)移概率為 （1）式（1）中有：表示t時刻路徑（i,j）上的信息素強度；表示信息素啟發(fā)因子，表示螞蟻在運動過程中積累的信息素所起的作用；是期望啟發(fā)式因子，表示路徑能見度的相對重要程度，反映了螞蟻在選擇路徑過程中啟發(fā)式信息所起的作用；是啟發(fā)函數(shù)，在TSP問題中，通常取=,是相鄰兩個城市節(jié)點之間的距離，啟發(fā)函數(shù)表示螞蟻k從i城市移動到j(luò)城市的期望程度；=1,2,n-表示不在禁忌表中的城市集合，表示螞蟻下一步要繼續(xù)搜索的城市集合。為了避免信息素殘留的過多引起殘留信息掩蓋啟發(fā)信息，在每只螞蟻走完一步或遍歷完所有城市后，要對殘留的信息素進(jìn)行適時更新。在t+n時刻在路徑（i，j）上的信息素強度要可按以下公式更新調(diào)整：（） （）其中表示螞蟻在本次循環(huán)中路徑(i,j)上的信息素增量,設(shè)初始時刻。表示螞蟻k在本次循環(huán)中在路徑（i,j）上的信息素增量。是信息素?fù)]發(fā)系數(shù)，1-則表示信息素殘留系數(shù)，為了防止信息素累積過多，的取值范圍應(yīng)該為：。信息素?fù)]發(fā)因子的取值大小影響到蟻群算法的全局搜索效率和收斂速度，信息素殘留因子1-表示了螞蟻個體之間相互影響的程度。根據(jù)不同的信息素更新措施，Dorigo M提出了三種基本蟻群算法模型，分別是Ant-Cycle模型、Ant-Quantity模型和Ant-Density模型，它們之間的差別在于的求法有所不同。在Ant-Cycle模型中 （）式（）中,L表示第k只螞蟻在本次循環(huán)中所經(jīng)過路徑的總長度，Q為常數(shù)，指信息素強度，表示的是螞蟻在本次循環(huán)中釋放在所經(jīng)過路徑上的信息素總量。在Ant-Quantity模型中 （） 在Ant-Density模型中 （）它們的區(qū)別在于：式（）和（）中表示的是局部信息素，也就是螞蟻在走完一步后更新路徑上的信息素；而式（）中表示的是整體信息素，即螞蟻完成一次完整循環(huán)后更新所經(jīng)過路徑上的信息素，（4）在求解TSP問題時性能比較好，因此通常采用公式（）作為蟻群算法的基本模型。2.1.3 基本蟻群算法的系統(tǒng)學(xué)特征1）基本蟻群算法是一個系統(tǒng)系統(tǒng)強調(diào)系統(tǒng)元素之間的相互影響程度以及系統(tǒng)對其中元素的整體作用。螞蟻群體就構(gòu)成了一個系統(tǒng)，在該系統(tǒng)中，螞蟻的個體行為可作為系統(tǒng)中的元素，螞蟻個體之間的相互影響表現(xiàn)了系統(tǒng)的相關(guān)性，而整個螞蟻群體能夠完成個體所完成不了的復(fù)雜任務(wù)則體現(xiàn)了系統(tǒng)的整體性。在基本蟻群算法中，多只螞蟻的求解結(jié)果明顯好于單只螞蟻的求解結(jié)果，因此基本蟻群算法是一個系統(tǒng)。2）分布式計算類似于人體很多細(xì)胞相互獨立地完成某一項工作，當(dāng)其中一個細(xì)胞停止工作后，人身體的整體功能不會因此而受到影響。蟻群算法也體現(xiàn)了分布式特點。每只螞蟻個體在整個問題空間的多個節(jié)點相互獨立地構(gòu)造問題的解，而整個問題的求解過程不會因為其中某只螞蟻無法求解而受到影響。分布式特征增強了蟻群算法的可靠性。3）自組織性昆蟲群落中的生物個體相互作用，可以協(xié)同完成一項集體工作，體現(xiàn)了較強的自組織性能。蟻群算法就體現(xiàn)了自組織性。在算法的初始階段，單只螞蟻雜亂無章地尋找解，但是算法經(jīng)過一段時間的演化過程，螞蟻越來越傾向于搜索那些接近于最優(yōu)解的一部分解，這就體現(xiàn)出螞蟻行為從無序到有序的自組織性。自組織性增強了算法的魯棒性。4)正反饋從自然界中真實蟻群的覓食行為機制可以發(fā)現(xiàn)，螞蟻之所以能夠找到最優(yōu)路徑，主要是由于信息素不斷地在較優(yōu)路徑上的累積，而信息素的累積過程就是一個正反饋過程?；鞠伻核惴ǖ姆答仚C制是在較優(yōu)路徑上留下更多的信息素，而更多的信息素又吸引來了更多的螞蟻，這個過程引導(dǎo)著整個系統(tǒng)不斷向最優(yōu)解的方向進(jìn)化。以上從系統(tǒng)學(xué)方面分析了蟻群算法的機理，可見蟻群算法體現(xiàn)了不同于常規(guī)算法的許多新思想，這也正是基本蟻群算法在系統(tǒng)學(xué)上研究的意義所在。2.2 基本蟻群算法的具體實現(xiàn)2.2.1 基本蟻群算法的實現(xiàn)步驟 基本蟻群算法的具體實現(xiàn)步驟如下：（）令初始時刻循環(huán)次數(shù)，設(shè)最大循環(huán)次數(shù)為，將個螞蟻隨機放在個元素節(jié)點上，設(shè)每條路徑（，）的初始化信息量（為常數(shù)），初始時刻設(shè)置每條路徑上的信息素增量。（）循環(huán)次數(shù)。（）設(shè)初始時刻螞蟻的禁忌表索引號。（）螞蟻數(shù)目。（）螞蟻個體根據(jù)狀態(tài)轉(zhuǎn)移概率公式（）選擇下一個元素，然后繼續(xù)往前搜索移動，此時。（）選擇好下一個元素之后，再將螞蟻移動到新的元素節(jié)點，并把該元素轉(zhuǎn)移到該螞蟻個體的禁忌表中，此時，。（）如果集合中元素還沒有遍歷完，即，則跳轉(zhuǎn)到第（）步，否則執(zhí)行第（）步。（）根據(jù)路徑上信息量更新公式（）和信息量變化公式（）更新每條路徑（，）上的信息量。（）如果滿足結(jié)束條件，即循環(huán)次數(shù)，則本次循環(huán)結(jié)束，輸出程序計算的最佳結(jié)果，否則清空禁忌表并跳轉(zhuǎn)到第（）步。2.2.2 基本蟻群算法的程序結(jié)構(gòu)流程圖基本蟻群算法的程序結(jié)構(gòu)流程圖如圖2.2.2所示。圖2.2.2 基本蟻群算法的程序結(jié)構(gòu)流程圖開始初始化迭代次數(shù)N=N+1螞蟻k=1螞蟻k=k+1按照狀態(tài)轉(zhuǎn)移概率公式（1）選擇下一個元素修改禁忌表=+1k螞蟻總數(shù)m？ 按照公式（2）和公式（3）進(jìn)行信息素更新滿足結(jié)束條件？輸出程序計算結(jié)果結(jié)束NNYY第三章 基于正交離散過程的蟻群算法3.1 正交試驗設(shè)計3.1.1 正交試驗設(shè)計的基本概念在正交試驗要解決的實際問題中，要明確評價試驗效果的影響指標(biāo)，影響試驗評價指標(biāo)者稱為因素，因素在試驗中變化的狀態(tài)稱為水平。對于單因素或者兩因素試驗，其因素數(shù)較少，試驗的設(shè)計、安排都比較簡單。但在實際生產(chǎn)過程中要研究許多因素多水平對產(chǎn)品指標(biāo)的影響。例如因素數(shù)為a, 因素的水平數(shù)為b, 則多因素全面試驗方案的次數(shù)為次,從試驗次數(shù)的公式可知, 因素數(shù)和水平數(shù)增多, 試驗次數(shù)將會大大增加。例如有5個因素，每個因素有4個水平，若全面試驗就要進(jìn)行次，這樣試驗規(guī)模就會大大增加，給研究工作帶來了繁重的任務(wù), 而且也會消耗大量時間、原材料和財力。正交試驗設(shè)計就是利用正交表來安排、分析多因素多水平試驗的一種設(shè)計方法。它是從全面試驗的全部水平組合中，挑選出一部分代表性很強的水平組合進(jìn)行試驗，通過分析這部分有代表性水平組合的試驗結(jié)果，來了解全面試驗的情況，減少試驗次數(shù)，從而找出最優(yōu)水平組合。3.1.2 正交試驗設(shè)計的基本原理在試驗安排中，當(dāng)因素水平數(shù)不多時，適合進(jìn)行全面試驗，例如，一個三因素三水平試驗，各因素各水平之間的全部水平組合就有33=27種?？梢杂靡粋€立方體來表示多因素試驗的選優(yōu)區(qū)域，對于3因素3水平試驗，就可以選擇有27個網(wǎng)格點的立方體作為選優(yōu)區(qū)，如果這27個格點都進(jìn)行試驗，就是全面試驗。全面試驗的數(shù)據(jù)試驗點分布如圖3.1.21所示。圖3.1.21 全面試驗的數(shù)據(jù)試驗點分布由圖可見：全面試驗數(shù)據(jù)均勻分布，各個因素水平全面搭配，缺點就是試驗次數(shù)太多，如果是5因素4水平試驗，全面試驗的話就要進(jìn)行次試驗，這會因?qū)嶒灄l件的實際限制而難于實施，因此全面試驗適用于因素水平數(shù)不多的情況下。正交試驗設(shè)計就是從全面試驗點中挑選一部分具有代表性的試驗點來進(jìn)行試驗。對于3因素3水平而言，設(shè)有A,B,C三個因素，A因素有三個試驗水平，B因素有三個試驗水平，C因素有三個試驗水平，利用正交表 從27個試驗點中挑選出9個試驗點，這9個試驗點為：（1）；（2）；（3）;（4）;（5）;（6）;（7）;（8）;（9）。這種選擇保證了A因素的3個水平與B、C因素的3個水平在試驗過程中各搭配一次，對于A、B、C這3個因素來說，正交試驗次數(shù)僅是全面試驗次數(shù)的三分之一，這樣就大大減少了試驗次數(shù)。正交試驗設(shè)計的數(shù)據(jù)試驗點在立方體選優(yōu)區(qū)中的分布如圖3.1.22所示:圖3.1.22 正交試驗設(shè)計的數(shù)據(jù)試驗點分布 從圖3.1.22中可以看到，9個試驗數(shù)據(jù)點在選優(yōu)區(qū)中均衡分布，在立方體的每個平面上恰好只有3個試驗點，在立方體的每條線上恰好只有1個試驗點。所選的這9個試驗點在整個立方體內(nèi)均衡分布，代表性很強，能夠全面反映整個立方體選優(yōu)區(qū)內(nèi)的基本情況。因此它們能很好地代表27次全面試驗的情況，這就是正交試驗設(shè)計的優(yōu)點。3.1.3 正交表及其基本性質(zhì)正交表是正交試驗設(shè)計的基本工具，正交試驗設(shè)計安排以及分析試驗結(jié)果都要用到正交表，合理選用正交表是正交設(shè)計的基礎(chǔ)。常用的正交表已經(jīng)規(guī)范標(biāo)準(zhǔn)化，我們根據(jù)試驗需要從參考書中選取合適的正交表。正交表的記號為，其中L代表正交表，是試驗次數(shù)即正交表的行數(shù)，b表示水平數(shù)，表示因素數(shù)即列數(shù)。正交表的基本性質(zhì)如下：1）正交性：在正交表中任意一列中，某因素的所有水平都出現(xiàn)，且出現(xiàn)的次數(shù)是相等的，在任意兩列之間，兩因素的各種不同水平組合都出現(xiàn)，并且出現(xiàn)的次數(shù)也相等。2）均衡分布性：在正交表中的各因素水平組合在選優(yōu)區(qū)中均衡分布。例如圖3.1.22所示，在立方體中，每一平面內(nèi)只有3個數(shù)據(jù)試驗點，每一條直線上只包含1個試驗點，正交試驗點均衡分布在全面試驗點中。3）獨立性：正交表中沒有完全重復(fù)的水平組合，從全面試驗組合中挑出的這一部分試驗組合沒有重復(fù)試驗的情況，在討論某一因素時，不用考慮其他因素的影響，正交表中的試驗方案能夠綜合處理大量的信息。4）整齊可比性：整齊可比是指各個因素的各個水平之間具有可比性。正交表中某一因素的各個水平都均勻搭配著其他因素的各個水平。如在3因素3水平試驗中的A、B、C3個因素，A因素的3個水平A1、A2、A3各搭配 B、C兩因素的3個不同水平，即：（1）；（2）；（3）;（4）;（5）;（6）;（7）;（8）;（9）。在這9個水平組合中，A因素下的3個水平分別組合了B、C兩因素的3個水平，且任意兩個水平組合不會有重復(fù)的情況。A因素3水平之間具有整齊可比性。同理B、C兩因素的3水平間也具有整齊可比性。3.2 基于正交離散過程的蟻群算法3.2.1 正交離散過程蟻群算法的基本原理傳統(tǒng)基本蟻群算法在實際應(yīng)用中主要是解決離散域的組合優(yōu)化問題，而難于解決連續(xù)域變量的函數(shù)優(yōu)化問題，在原料配方設(shè)計等連續(xù)變量領(lǐng)域中應(yīng)用困難。然而正交試驗設(shè)計可以綜合處理大量信息，有效地解決連續(xù)域變量問題。正交離散主要是將基本蟻群算法與正交試驗設(shè)計相結(jié)合，通過正交設(shè)計形成正交離散點，使連續(xù)域問題離散化，讓螞蟻在正交試驗得出的幾條優(yōu)化路徑中尋找最優(yōu)解，改進(jìn)了初始階段蟻群算法信息素隨機分布、路徑雜亂無章的缺點，最終可以取得滿意的結(jié)果。以原料配方設(shè)計為例進(jìn)一步說明正交離散過程的蟻群算法。設(shè)原料品種（）為橫坐標(biāo)，原料用量為，原料品種所占的比例從0100連續(xù)均勻變化，屬于典型的連續(xù)域變量問題。由于從0100之間有無窮多個節(jié)點，若用基本蟻群算法，那么螞蟻將會從start點開始訪問無窮多個節(jié)點，這樣必然會造成龐大的計算量而無限延長計算時間，所求的結(jié)果也會比較分散，所以應(yīng)把問題離散化。在正交試驗優(yōu)化中，以品種數(shù)作為因素數(shù)，每個原料品種在所占比例范圍內(nèi)選定水平數(shù)。例如：有四個原料品種，也就是有四個因素，每個品種有三個水平，也就是4因素3水平正交試驗，則選用正交試驗表，產(chǎn)生12個正交離散節(jié)點，組成9個初始配方組合，讓初始螞蟻在這9個初始路徑中釋放一定的信息素，然后運行螞蟻更加趨向于從這9個配方組合中尋找適應(yīng)解配方，最終確定最優(yōu)解，這樣就實現(xiàn)了把連續(xù)性問題離散化處理了。原料成分離散化及配方搜索圖如圖3.2.1所示： 0100各原料所占的質(zhì)量分?jǐn)?shù)圖3.2.1 原料正交離散及配方搜索圖Startend品種因素 為了能夠有效運用正交離散的蟻群算法，要把研究對象離散化成如圖3.2.1所示的形式，這樣就大大縮小了搜索范圍，在很大程度上改善了尋優(yōu)性能，極大縮短了計算時間。首先挑選四個原料品種作為四個因素，即品種，每個因素再選擇三個水平，即因素有三個水平、因素有三個水平、因素有三個水平、因素有三個水平，由正交試驗表可知可以組成9個初始配方組合，也就是如圖3.2.1所示的9條已經(jīng)初始化一定量信息素的路徑，即（1）；（2）；（3）;（4）;（5）;（6）;（7）;（8）;（9）。創(chuàng)建正交試驗表，如表格3.2.2所示:表3.2.2 因素水平正交試驗分配方案表因素試驗編號ABCD1A1B1C1D12A1B2C2D23A1B3C3D34A2B1C2D35A2B2C3D16A2B3C1D27A3B1C3D28A3B2C1D39A3B3C2D1如圖3.2.1所示，一只螞蟻從Start點開始出發(fā)，逐步經(jīng)過每個品種上的正交離散節(jié)點，最后到達(dá)代表最后一個品種的end點，完成一次循環(huán)就形成一個完整的配方，多只螞蟻循環(huán)上述過程便形成多種配方組合。通過對原料用量正交離散化處理，大大減少了搜索初始解集的試驗配方次數(shù)，提高了蟻群算法的運算效率。由圖3.2.1可見，這12個正交離散點所組成的配方組合總共有種，而這81條路徑具有很強的代表性，它們可以代表原料比例在0100范圍內(nèi)全面試驗的無窮多條路徑，而正交試驗中的9種初始化配方組合代表了所挑選的這部分全面試驗中的81種配方組合。根據(jù)專業(yè)知識和實踐經(jīng)驗，再對所研究問題具體分析，明確哪幾個因素及其哪幾個水平對試驗指標(biāo)的影響比較大，然后再挑選這幾種因素及其水平進(jìn)行試驗。在正交表3.2.2中確定的9種優(yōu)化組合配方中很有可能存在最佳配方，也就是說螞蟻最有可能在這已經(jīng)初始化一定信息素的9條路徑中搜索到最優(yōu)解，比如圖3.2.1中加黑加粗的那條路徑2，即配方組合有可能是最優(yōu)解。但是除了這9條路徑之外的其它72條路徑中的一條配方組合也有可能是最優(yōu)解，只不過這9條路徑中的一條成為最優(yōu)解的可能性比較大，而其他72條路徑成為最優(yōu)解的可能性比較小而已。這種方法將會克服基本蟻群算法隨機搜索無規(guī)律、效率低、結(jié)果分散的缺陷，在很大程度上提高了蟻群算法的求解精度。因此，基于正交離散過程的蟻群算法能很好地解決連續(xù)域變量的配方組合優(yōu)化問題。3.2.2 正交離散過程蟻群算法的尋優(yōu)過程在正交優(yōu)化過程中，螞蟻主要有初始螞蟻和運行螞蟻兩種。初始螞蟻的主要任務(wù)是在圖3.2.1中的9條正交優(yōu)化路徑上釋放一定的信息素，即螞蟻初始化信息素（為常數(shù)）。螞蟻從start點出發(fā)進(jìn)行尋優(yōu)，結(jié)束于end點，在尋優(yōu)過程中，相鄰兩個因素的各個水平節(jié)點之間都存在連接路徑，螞蟻在各個水平節(jié)點之間按照動態(tài)概率轉(zhuǎn)移規(guī)則構(gòu)造新的路徑，當(dāng)所有的螞蟻遍歷完后，就可以找出最優(yōu)解。在螞蟻創(chuàng)建優(yōu)化解的過程中，螞蟻逐個訪問各個離散節(jié)點，位于節(jié)點r上的螞蟻根據(jù)偽隨機比例規(guī)則選擇下一個將要訪問的節(jié)點s，單個螞蟻在遍歷的過程中根據(jù)信息素局部更新規(guī)則對它所經(jīng)過的路徑進(jìn)行信息素更新，當(dāng)所有的螞蟻遍歷完所有的節(jié)點后，再按照全局信息素更新規(guī)則對所經(jīng)過的路徑進(jìn)行信息素更新。 1）偽隨機比例規(guī)則：該規(guī)則主要是在螞蟻探索一條新路徑和根據(jù)螞蟻所積累的搜索經(jīng)驗開發(fā)一條新路徑這兩者之間保持體一種平衡狀態(tài)。位于節(jié)點r的螞蟻k利用以下規(guī)則選擇下一個將要訪問的節(jié)點s： （7） 式（7）中，函數(shù)argmaxf(x)表示尋找最優(yōu)解的參量，表示的是定義域中的一個子集，而該子集中的任一元素都可使函數(shù)f(x)取得最優(yōu)解。表示螞蟻k下一步要訪問的節(jié)點集合，表示路徑（r,j）上的信息素強度，=,表示啟發(fā)式信息。q是服從均勻分布的一個隨機數(shù)，是自定義的一個參數(shù)。S是根據(jù)以下的概率公式（8）計算得來的隨機變量。 （8）由式（7）和（8）決定的狀態(tài)轉(zhuǎn)移規(guī)則被稱為偽隨機比例規(guī)則。偽隨機比例規(guī)則使螞蟻更傾向于選擇距離短且信息素濃度高的路徑。參數(shù)決定了“探索”一條新路徑和利用螞蟻積累的有效搜索經(jīng)驗“開發(fā)”一條路徑這兩種過程之間的相對重要程度。參數(shù)要根據(jù)路徑信息素分布情況和尋優(yōu)目標(biāo)適時地進(jìn)行調(diào)節(jié)，這樣可以發(fā)揮在選擇節(jié)點、尋找最優(yōu)解過程中的作用。螞蟻在開始時的 、中間選擇節(jié)點時的和最終找到最優(yōu)解時的都應(yīng)適時地進(jìn)行調(diào)節(jié)，這樣在初始階段可以加快算法運算的速度，在尋優(yōu)過程中又可以避免算法陷入局部最優(yōu)狀態(tài)。當(dāng)螞蟻從節(jié)點r向節(jié)點s移動時，它會選擇一個隨機數(shù)，如果，按照（7）式根據(jù)啟發(fā)式信息和信息素強度選擇最優(yōu)路徑，否則按照（8）式的隨機比例規(guī)則選擇下一步要移動的路徑。2）信息素全局更新規(guī)則：當(dāng)螞蟻訪問完所有的節(jié)點以后，只增強那些屬于最短路徑上的信息素濃度，信息素全局更新規(guī)則使蟻群算法尋找最優(yōu)解的過程具有更強的指導(dǎo)性。當(dāng)所有的螞蟻遍歷完所有的節(jié)點之后，按照以下的公式進(jìn)行信息素全局更新： （9） （10）其中參數(shù)（）是信息素衰減系數(shù)，表示試驗開始至今所找到的全局最短路徑的長度。3）信息素局部更新規(guī)則：單個螞蟻在節(jié)點之間遍歷時按照信息素局部更新規(guī)則對所經(jīng)過路徑上的信息素進(jìn)行更新： （11）其中參數(shù)是信息素?fù)]發(fā)系數(shù)。實驗表明，（是初始化信息素）時算法的效果比較好。應(yīng)用信息素局部更新規(guī)則會使螞蟻經(jīng)過路徑上的信息素減少一部分，這樣后來的螞蟻選擇這些路徑的可能性就會地減少了，從而增強了算法的“探索”能力，有效地避免了算法進(jìn)入局部停滯狀態(tài)，避免螞蟻收斂到同一條路徑。3.2.3 正交離散過程蟻群算法的數(shù)學(xué)模型目標(biāo)函數(shù)根據(jù)所研究問題的實際限定因素而設(shè)定，例如：目標(biāo)函數(shù)： (12)表示經(jīng)濟目標(biāo)比如最大利潤、最低成本等；表示各種原料的價格系數(shù)；表示各種原料在配方中的比例（）；n為變量數(shù)。根據(jù)配方中各原料用量的相關(guān)標(biāo)準(zhǔn)確定約束條件：（13）為約束值，也就是配方應(yīng)該滿足的各項指標(biāo)（原料重量、營養(yǎng)價值等指標(biāo)）；為各種原料的相應(yīng)化學(xué)成分含量；m為約束方程的個數(shù)。 3.3 正交離散過程蟻群算法的具體實現(xiàn)3.3.1 正交離散過程蟻群算法的實現(xiàn)步驟正交離散過程蟻群算法具體實現(xiàn)步驟如下所示：第一步：明確正交離散過程蟻群算法需要解決的實際問題。 第二步：根據(jù)實際問題確定目標(biāo)函數(shù)，根據(jù)實際限定因素確定約束函數(shù)條件，建立正交離散過程蟻群算法的基本數(shù)學(xué)模型。 第三步：根據(jù)正交設(shè)計優(yōu)化路徑設(shè)置，將研究對象正交離散化處理。 第四步：初始螞蟻在正交試驗設(shè)計中所確定的幾條優(yōu)化路徑中釋放一定量的信息素，對蟻群算法參數(shù)進(jìn)行初始化。然后運行螞蟻根據(jù)初始螞蟻建立的路徑信息素強度和啟發(fā)信息按照偽隨機比例規(guī)則運行，進(jìn)行全局范圍內(nèi)的搜索尋優(yōu)移動。 第五步：適時調(diào)節(jié)參數(shù)，動態(tài)調(diào)整狀態(tài)轉(zhuǎn)移概率，優(yōu)化路徑設(shè)置。 第六步：動態(tài)地進(jìn)行信息素局部和全局更新優(yōu)化，以提高尋優(yōu)效率。 第七步：如果滿足結(jié)束的條件，計算目標(biāo)函數(shù)值，否則回到第二步。第八步：最終輸出程序計算的最佳結(jié)果。3.3.2 正交離散過程蟻群算法的程序結(jié)構(gòu)流程圖正交離散過程蟻群算法的程序結(jié)構(gòu)流程圖如圖3.3.2所示：開始明確研究問題定義目標(biāo)函數(shù)、約束函數(shù)條件，建立數(shù)學(xué)模型正交離散化初始化蟻群算法參數(shù)狀態(tài)轉(zhuǎn)移概率優(yōu)化信息素動態(tài)更新優(yōu)化進(jìn)行選路尋優(yōu)計算滿足結(jié)束條件？計算目標(biāo)函數(shù)值輸出程序計算最佳結(jié)果結(jié)束N迭代 Y 圖3.3.2 正交離散過程蟻群算法的程序結(jié)構(gòu)流程圖3.4 正交離散過程蟻群算法的仿真應(yīng)用配方試驗設(shè)計就是連續(xù)域變量優(yōu)化問題，在滿足實際意義的約束條件下，求解各種原料配方的最佳比例，使問題的目標(biāo)函數(shù)值達(dá)到最大或最小的效果。下面以啤酒原料配方設(shè)計為例對正交離散過程蟻群算法進(jìn)行仿真應(yīng)用驗證。啤酒配方主要包括多種大麥和大米等原料，這些原料糖化處理制成麥汁，再經(jīng)過發(fā)酵制成啤酒。以某企業(yè)所要求的具體生產(chǎn)指標(biāo)和原料種類為例對該算法進(jìn)行仿真驗證。假設(shè)該企業(yè)可提供的原料種類有以下幾種：寧麥加麥、寧麥澳麥、寧麥哈默林、九源甘三、九得利KA4B、寶應(yīng)甘三、小麥麥芽和大米。不同原料具有各自不同的營養(yǎng)參數(shù)屬性，具體營養(yǎng)標(biāo)準(zhǔn)如表3.4.1所示： 表3.4.1 啤酒原料營養(yǎng)參數(shù)標(biāo)準(zhǔn)麥芽品種單價/（元/kg）產(chǎn)槽率/（L/kg）氨基氮/（mg/100g）總可溶性氮/（mg/100g）葡萄糖/（mg/100g）糖化力/（WK/100g）寧麥加麥2.702180695155335寧麥澳麥2.712165650125350寧麥哈默林2.703205795120405九源甘三2.372200805175320九得利KA4B2.403205795210405寶應(yīng)甘三2.393206796185410小麥麥芽2.411.5195105590485大米1.850.360000該啤酒企業(yè)要求的啤酒原料配方各項生產(chǎn)指標(biāo)主要有5個約束條件：（1）保證糟層的厚度不低于22cm;(2)保證麥汁氨基氮的含量在160mg/L210mg/L范圍內(nèi);(3)保證麥汁總可溶性氮含量在650mg/L1000mg/L范圍內(nèi)；（4）保證麥汁葡萄糖含量90mg/L250mg/L范圍內(nèi)；（5）保證原料的糖化力在1600WK/kg2100WK/kg范圍內(nèi)。參考該啤酒企業(yè)的原料配方設(shè)計手冊，定義算法所研究問題的數(shù)學(xué)模型如下：目標(biāo)函數(shù)為最低成本函數(shù)： （14）約束條件為各種期望生產(chǎn)指標(biāo)： （15） （16） （17） （18） （19） 在以上各式中，表示一批次所需要的啤酒原料總質(zhì)量；表示過濾槽設(shè)備的直徑；表示第種原料的成本單價；表示配方中第種原料所占的百分比含量；表示第種原料糖化力的數(shù)值；表示第種原料總氮含量；表示第種原料氨基氮的含量；表示第種原料葡萄糖含量；表示第種原料產(chǎn)槽率。優(yōu)化的最終目標(biāo)就是實現(xiàn)原料的總成本最低，即定義函數(shù)為最終目標(biāo)函數(shù)。啤酒原料麥芽品種所占的百分比含量在0100范圍內(nèi)均勻變化，屬于典型的連續(xù)變量優(yōu)化問題，由于從0到100之間有無窮多個節(jié)點，如果讓螞蟻在0100范圍內(nèi)逐個進(jìn)行訪問的話，必然會造成龐大的計算量而無限延長計算時間，求解的結(jié)果也會比較分散，因此無法用傳統(tǒng)的蟻群算法對其進(jìn)行研究，必須把原料用量正交離散化處理。在對研究對象進(jìn)行正交離散化處理的過程中，根據(jù)啤酒原料營養(yǎng)標(biāo)準(zhǔn)手冊和相關(guān)實踐經(jīng)驗確定幾個對試驗指標(biāo)效果影響比較大的因素數(shù)以及水平數(shù)。以寧麥澳麥、寧麥哈默林、寶應(yīng)甘三、九得利KA4B、九源甘三、小麥六種主要啤酒原料配方為基礎(chǔ)，作為正交試驗設(shè)計中的六個因素，每種原料可確定五個用量比例等級，根據(jù)相關(guān)配方手冊和實踐經(jīng)驗，啤酒原料用量的最佳比例應(yīng)該在這五個數(shù)量比例范圍之內(nèi)，然后將其作為正交設(shè)計中的五個水平，即6因素5水平的正交試驗。采用正交表，創(chuàng)建正交離散配方搜索圖，產(chǎn)生30個正交離散點，進(jìn)行25次試驗，并產(chǎn)生25個初始配方組合，即產(chǎn)生25條初始化優(yōu)化路徑。各原料參數(shù)正交試驗水平表如表3.4.2所示： 表3.4.2 各原料參數(shù)正交試驗水平表因素水平寧麥澳麥寧麥哈默林寶應(yīng)甘三九得利KA4B九源甘三小麥10.54.08.05.59.07.521.05.08.56.59.58.531.56.09.07.510.09.542.07.09.58.510.510.552.58.010.09.511.011.5根據(jù)啤酒原料配方設(shè)計的數(shù)學(xué)模型采用基于正交離散過程的蟻群算法求解程序，即根據(jù)圖3.3.2 正交離散過程蟻群算法的程序結(jié)構(gòu)流程圖進(jìn)行運算，運算步驟如下所示：（1）根據(jù)相關(guān)標(biāo)準(zhǔn)和實踐經(jīng)驗從研究對象中挑選6個因素，每個因素5個水平如表3.4.2所示，構(gòu)建正交離散原料配方搜索圖，由此可產(chǎn)生30個正交離散節(jié)點，形成25個初始化優(yōu)化路徑。（2）讓初始螞蟻在這25條試驗路徑上初始化一定量的信息素，優(yōu)化路徑設(shè)置，運行螞蟻根據(jù)此信息素強度尋優(yōu)，將試驗對象正交離散化。（3）讓m只螞蟻從start點開始出發(fā)，每只螞蟻獨立地按照（7）式和（8）式組成的偽隨機比例規(guī)則追蹤生成配方方案。（4）排除不滿足該企業(yè)生產(chǎn)指標(biāo)的不可行方案，然后按照公式（14）計算可行方案的目標(biāo)函數(shù)值并保存其最小值，把方案記為當(dāng)前最好方案。（5）對于找到可行方案的螞蟻所經(jīng)過的路徑按照公式（9）、（10）和（11）進(jìn)行信息素局部和全局更新優(yōu)化。（6）若滿足結(jié)束條件，即如果循環(huán)次數(shù)，則循環(huán)結(jié)束，輸出程序計算的最佳結(jié)果。在運算時可采用以下參數(shù)值：配方搜索圖上節(jié)點個數(shù),信息素?fù)]發(fā)系數(shù)，信息素痕跡強度，啟發(fā)信息權(quán)重，參數(shù)，信息增量和路徑信息素的初始值，根據(jù)該企業(yè)的實際生產(chǎn)情況，一個批次所需的啤酒原料總質(zhì)量,過濾槽設(shè)備的直徑。采用正交離散過程的蟻群算法獨立進(jìn)行20次迭代優(yōu)化，運算后的具體結(jié)果如表3.4.3所示：表3.4.3 啤酒原料最佳優(yōu)化配方詳細(xì)配方啤酒原料用量寧麥澳麥1.5寧麥哈默林6.0寶應(yīng)甘三9.5九得利KA4B8.5九源甘三9.5寧麥加麥0.5小麥9.5大米55約束條件營養(yǎng)水平含量糖化力18