用SFLA算法解決NW調度問題

目錄TOC\o"1-5"\h\z\o"CurrentDocument"緒論 1組合優(yōu)化問題 11.2調度問題 21.3本文結構 3\o"CurrentDocument"生產調度問題 4生產調度問題 42.2流水車間調度問題 8\o"CurrentDocument"蛙跳算法 10蛙跳算法簡介 103.2蛙跳算法國內外研究情況 11蛙跳算法原理 123.4蛙跳算法的相關研究 153.5蛙跳算法的優(yōu)缺點 17\o"CurrentDocument"4零等待策略（NW）的Flowshop調度問題 184.1零等待策略（NW）的Flowshop調度問題數學模型 18仿真分析 19\o"CurrentDocument"小結 30\o"CurrentDocument"5總結與展望 315.1本文總結 31\o"CurrentDocument"展望 31\o"CurrentDocument"參考文獻 32致謝 錯誤！未定義書簽。1緒論1.1組合優(yōu)化問題由于科學技術突飛猛進地發(fā)展，隨著人們在生活和工作中碰到各種各樣的問題，而解決這些問題的方案又有許多，其中組合優(yōu)化問題日益得到了國內外的廣泛重視。組合優(yōu)化問題是一種離散最優(yōu)化問題，就是在給定約束條件下，求出使目標函數極?。ɑ驑O大）的變量組合問題。優(yōu)化是個古老的課題，它所研究的問題是在眾多方案中尋找最優(yōu)方案。長期以來，人們對優(yōu)化問題進行探討和研究。早在17世紀，英國Newton和德國Leibnitz發(fā)明的微積分就蘊含了優(yōu)化的內容。而法國數學家Cauchy則首次采用梯度下降法解決無約束優(yōu)化問題，后來針對約束優(yōu)化問題又提出了Lagrange乘數法。人們關于優(yōu)化問題的研究工作，隨著歷史的發(fā)展不斷深入。但是，任何科學的進步都受到歷史條件的限制，直到二十世紀四十年代，計算機的應用被大量運用于這個問題，至此，優(yōu)化問題的研究不僅成為一種迫切需要，而且有了求解的有力工具。因此，優(yōu)化理論和算法迅速發(fā)展起來，形成一門新的學科。至今已出現線性規(guī)劃、整數規(guī)劃、非線性規(guī)劃、幾何規(guī)劃、動態(tài)規(guī)劃、隨機規(guī)劃、網絡流等許多分支。這些優(yōu)化技術在實際應用中正發(fā)揮越來越大的作用。不過隨著人類生存空間的擴大，以及認識世界和改造世界范圍的拓寬，常規(guī)優(yōu)化方法已經無法處理人們所面對的復雜問題，因此高效的優(yōu)化算法成為科學工作者的研究目標之一[1]。優(yōu)化方法涉及的工程領域很廣，問題種類與性質繁多。歸納而言，最優(yōu)化問題可以分為無約束問題與約束優(yōu)化問題兩大類。若決策變量x的解空間為Rn，則該問題為無約束最優(yōu)化問題；若決策變量x的解空間受到一些約束函數的限制，則該問題被稱為約束優(yōu)化問題。按對象是連續(xù)狀態(tài)還是離散狀態(tài)，最優(yōu)化問題也可分為函數優(yōu)化問題和組合優(yōu)化問題兩大類，其中函數優(yōu)化問題的對象是一定區(qū)域內的連續(xù)變量，而組合優(yōu)化問題是解空間中的離散狀態(tài)[1]。1.1.1無約束最優(yōu)化與約束優(yōu)化最優(yōu)化問題的一般形式為minf（x） （1-1）其中s,t,xGX其中xgRn是決策變量，f（x）為目標函數，XuRn為約束集或可行域。特別地，如果約束集X=Rn，則最優(yōu)化問題(1-1)稱為無約束最優(yōu)化問題；minf(x) (1-2)其中xeRn約束最優(yōu)化問題通常寫為minf(x)s,t,c(x)=0,ieE (1-3)ic(x)>0,ieIi這里E和I分別是等式約束的指標集和不等式約束的指標集，c(x)是約束函數。i當目標函數和約束函數均為線性函數時，我們把問題稱為線性規(guī)劃。當目標函數和約束函數中至少有一個是變量x的非線性函數時，則問題稱為非線性規(guī)劃。此外，根據決策變量、目標函數和要求的不同，最優(yōu)化還被分成了整數規(guī)劃、動態(tài)規(guī)劃、網絡規(guī)劃、非光滑規(guī)劃、隨機規(guī)劃、幾何規(guī)劃、多目標規(guī)劃等若干個分支［1］。函數優(yōu)化與組合優(yōu)化函數優(yōu)化問題通常可描述為：令S為Rn上的有界子集(即變量的定義域)，f:STR為n維實值函數，所謂函數f在S域上全局最小化就是尋求X eS使得min在S域上全局最小。典型的組合優(yōu)化問題有旅行商問題(TravelingSalesmanProblem，TSP)、時間表問題(TimetablingProblem，TTP)、加工調度問題(SchedulingProblem，如Flow-Shop,Job-Shop)、0-1背包問題(KnapsackProblem)、裝箱問題(BinPackingProblem)、圖著色問題(GraphColoringProblem)>聚類問題(ClusteringProblem)等⑵。1.2調度問題調度問題(Scheduling)是組合優(yōu)化問題的一種，它是根據生產目標和約束條件為每個加工對象確定具體的加工路徑、時間、機器和操作方式等，在一定的約束條件下，合理地分配資源(Resource)完成一批給定的任務(Task)或作業(yè)(Job),獲得某些性能指標(PerformanceCriterion)如完成時間或生產成本等的最優(yōu)化。這里的資源是一種泛指，如人員、金錢、機器、工具、材料和能源等，而任務也可以有不同的解釋，從制造系統(tǒng)的機器分配到計算機系統(tǒng)的信息處理等。在有些文獻中調度問題也被稱為排序問題(Sequencing)。但“排序”與“調度”存在一定的區(qū)別，以生產車間的機器加工為例，“排序”主要考慮的是所有機器上一個工件序列的分配和置換問題。而“調度”不僅考慮次序問題（包括被加工對象“工件”的次序和提供加工對象“機器”的次序），而且更重要的是對時間的分配。因此，有些學者認為“排序”是一種特殊的調度，“調度”一詞也被更廣泛的使用。生產調度是在生產任務和產品產量需求給定的情況下，確定較合理的生產方案，即在滿足單元設備的處理能力和生產工藝要求的前提下，對給定的單元裝置進行任務的分配或重分配，包括對各產品在生產時間和空間（生產流程線）的規(guī)劃，使生產任務得以完成［1］。優(yōu)良的調度對于增強企業(yè)的競爭能力、提高經濟效益有著極大的作用。調度問題中一個非常典型的問題是FlowShop問題。自從Johnson在2003年發(fā)表了第一篇關于流水車間調度問題的文章以來，流水車間調度問題引起了許多學者的關注，提出了許多解決的方法，整數規(guī)劃和分枝定界法是尋求最優(yōu)解的常用方法，但流水車間調度問題是NP完全問題，對于一些大規(guī)模甚至中等規(guī)模的問題，整數規(guī)劃和分枝定界法仍不是很有效。因此又相繼提出一些啟發(fā)式算法，最近一些智能搜索算法也被應用于解決FlowShop調度問題，如禁忌搜索方法、模擬退火算法、遺傳算法、蟻群算法等。其中無等待流水線（NWFlowshop）調度問題是一個具有廣泛應用背景和重要理論價值的組合優(yōu)化問題，是許多實際生產調度過程的簡化模型，廣泛存在于煉鋼、食品加工、化工和制藥等工業(yè)領域。隨著當代科技的進步，研究方向逐漸轉變到如何使效率最大化，這就要建立在有效的理論基礎上。本文通過蛙跳算法（SFLA）來解決零等待調度問題［2］。1.3本文結構本文第二章從總到分的介紹生產調度問題，分為流水線調度問題及零等待流水線調度問題；第三章介紹蛙跳算法概念、基本原理及相關研究情況，并為零等待調度問題編程進行鋪墊，第四章為進NW的調度問題的編程及其仿真，包括編程內容，仿真結果等；第五章為全文的總結，包括完成全文的過程及自我感覺的不足之處等。2生產調度問題2.1生產調度問題2.1.1生產調度問題簡介生產調度是指在滿足約束的條件下確定工件的加工順序使得目標函數達到最優(yōu)。其中FlowShop調度問題是一種典型的組合優(yōu)化問題，它具有很強的工程應用背景，其特點是單個工件在各個機器階段上的加工順序是相同的。該調度問題是一種典型的NP完全問題，隨著問題規(guī)模的增大，解的規(guī)模將成指數增長。因此，開發(fā)高效的優(yōu)化算法具有極其重要的理論和應用價值。求解這一問題的傳統(tǒng)方法僅能處理小規(guī)模問題，并且存在計算量太大的缺點。另有一些啟發(fā)式算法雖能達到快速求解，但是存在求解質量不高、對向題的依賴性過強以及一旦完成決策就無法再修改等問題［2］。調度是在滿足某些約束（作業(yè)的先后關系、預定的完成時間、最早開始時間和資源能力等）的條件下對操作（作業(yè)）的排序，按照排序的次序給它們分配資源和時間，并且使某個執(zhí)行目標達到最優(yōu)（如總的執(zhí)行時間、拖期時間和生產費用等）。調度理論源于對制造車間生產計劃與控制的研究，從誕生之日起它就引起了管理科學家和應用數學家等的重視，人們在這個領域發(fā)表了大量的文獻著作，還有一些學者從不同的廣度和深度考察了調度理論的發(fā)展狀況。經過幾十年的研究與探索，調度理論逐漸發(fā)展成為一個比較完整的科學理論，在企業(yè)的生產中得到了一定程度的應用。由于企業(yè)車間的生產計劃與控制問題在所有調度問題中最具典型性，所以對車間調度問題的研究一直在調度理論中占據主導地位。特別是近幾年，更多領域的研究人員都對車間調度問題產生了濃厚的興趣，他們各自用不同的技術和方法對這個問題進行了更為廣泛、深入、細致的研究，取得了豐碩的成果。生產調度，即對生產過程進行作業(yè)計劃，作為一個關鍵模塊，是整個先進生產制造系統(tǒng)實現管理技術、運籌技術、優(yōu)化技術、自動化與計算機技術發(fā)展的核心。有效的調度方法和優(yōu)化技術的研究與應用，是實現先進制造和提高生產效益的基礎和關鍵。改善生產調度方案，可大大提高生產效益和資源利用率，進而增強企業(yè)的競爭能力。生產調度問題是在一定的時間內，進行可用共享資源的分配和生產任務的排序，以滿足某些指定的性能指標。簡單地說，生產調度問題就是按時間分配資源來完成任務的問題。生產調度問題一般可以描述為：針對某項可分解的工作，在一定約束條件下，如何安排其組成部分（操作）所占有的資源、加工時間、先后順序，以獲得產品制造時間或成本等最優(yōu)。從數學規(guī)劃的角度來說。生產調度問題可表述為等式或不等式約束下，對目標函數所進行的優(yōu)化。生產調度問題主要集中在車間的計劃與調度方面。制造系統(tǒng)的生產調度是針對一項可分解的工作（如產品制造），探討在盡可能滿足約束條件（如交貨期、工藝路線、資源情況）的前提下，通過下達生產指令，安排其組成部分（操作）使用哪些資源、其加工時間及加工的先后順序，以獲得產品制造時間或成本的最優(yōu)化。在理論研究中，生產調度問題常被稱為排序問題或資源分配問題。生產調度中涉及的資源包括：原料、設備（加工、存貯、運輸）、人力、資金、能源等。資源的詳細分配受到產品的生產工藝的限制。調度問題受到工廠管理方法的影響，調度問題的優(yōu)化目標、優(yōu)化策略隨不同的管理方法而變化，因而其優(yōu)化數學模型也不同?？梢赃@樣說：很難用一個生產環(huán)境的調度方案，去解決另一個生產環(huán)境的生產調度，因為幾乎每一個生產環(huán)境都是唯一的。由于生產環(huán)境的動態(tài)性，生產領域知識的多樣性，調度問題的復雜性，必須將人、數學方法和信息技術結合起來研究生產領域的管理調度問題[3]。生產調度問題研究近況調度問題的研究始于20世紀50年代，S.MJohnson提出了解決n/2/F/c和部分特殊max的n/3/F/c問題的優(yōu)化算法，這是調度理論的開始；直至五十年代末期，許多研究成max果主要是針對規(guī)模較小的單機和簡單的流水車間問題，提出了解析優(yōu)化方法，研究范圍較窄，但是這些研究卻成為經典調度理論的基石。六十年代，多是利用混合或純整數規(guī)劃、動態(tài)規(guī)劃和分枝定界法解決一些有代表性的問題口Story的研究。同時也有人開始嘗試用啟發(fā)式算法研究此問題，如Gavett提出的方法。六十年代末期，經典調度理論體系初步形成。七十年代，人們開始了算法復雜性的研究，多數調度問題被證明屬于NP-完全問題或NP-難問題，難以找到多項式算法，因此開始關注啟發(fā)式算法。Panwalkar總結和歸納出了113條調度規(guī)則，并對其進行了分類。七十年代末期，經典調度理論趨向成熟。八十年代初期，Stephen等從三個方面對調度進行了重新考察，對未來發(fā)展做了分析和預測，認為理論與實際的結合將會成為研究熱點。這個富有挑戰(zhàn)性的課題吸引了機械、計算機、管理等諸多領域的學者，許多跨學科的方法被應用到研究中。其中最引人注目的就是以Carnegie-Mellon大學的M.Fox為代表的學者們開展的基于約束傳播的ISIS研究，它標志了人工智能開始真正應用于調度問題。八十年代后期，Giffler等人總結了生產調度的理論和實踐方面的最新研究進展，從七個方面論述了生產調度的技術和方法，認為生產調度無論在理論還是實踐上都已突破了傳統(tǒng)界限[3]。九十年代至今，各種方法在生產調度問題的研究中得到了充分的發(fā)揮，同時新的研究手段層出不窮?？v觀目前國內外的研究成果，從總體趨勢上來講，經典調度理論依然是調度理論不可動搖的基石，但智能調度理論己嶄露頭角，逐漸趨于成熟，且二者的融合也將會成為一種趨勢。2.1.3生產調度問題的分類及特點車間調度問題的分類，根據研究的側重點不同有多種分類方式，如按照資源約束種類和數量劃分，分為單資源車間調度、雙資源車間調度、多資源車間調度，本文研究的零等待策略的流水車間調度問題則屬于按照零件和車間的構成劃分：流水車間調度(Flowshop):在這種車間中，每個零件都有相同的加工路徑。這樣，機床設備的布局如同流水線一樣，零件一次從流水線的一端浸入，最后從另一端流出。作業(yè)車間調度(Jobshop):在這種車間中，機床設備的布局可以是任意的，因此零件的加工路徑也是任意的，并且各零件的工序內容和數量也是任意的。這是一種最一般的車間調度形式。開放式車間調度(Openshop):每個零件的工序之間的加工次序是任意的。零件的加工可以從任何一道工序開始，在任何一道工序結束。單車間調度(Singleshop):在這種車間中，每個零件只能有一道工序⑶。其他的分類方法還有按照零件的加工特點劃分，例如分為靜態(tài)車間調度、動態(tài)車間調度等，這里不再贅述。車間調度問題的特點具有建模的復雜性，計算的復雜性，動態(tài)的隨機性，多約束性，多目標性。復雜性:車間中工件、機器、緩存和搬運系統(tǒng)之間相互影響、相互作用。每個工件要考慮它的加工時間、安裝時間和操作順序等因素，因而相當復雜。調度問題是在等式或不等式約束下求指標的優(yōu)化，在計算量上往往是具有NP特性，隨著問題規(guī)模的增大，其計算量急劇增加，使得一些常規(guī)的方法無能為力，對于這一點已經證明。隨機性:在實際的作業(yè)車間調度系統(tǒng)中存在很多隨機的和不確定的因素，環(huán)境是不斷變化的，在運行過程中會遇到多種隨機干擾，比如工件到達時間的不確定性、作業(yè)的加工時間也有一定的隨機性，而且生產系統(tǒng)中常出現一些突發(fā)偶然事件，如設備的損壞、修復、作業(yè)交貨期的改變等，故作業(yè)車間調度過程是一個動態(tài)的隨機過程。多約束性:車間調度問題中資源的數量、緩存的容量、工件加工時間以及工件的操作順序等都是約束。此外還有一些人為的因素，如要求各機器上的負荷要平衡等。多目標性:實際的車間調度問題是多目標的，而且這些目標之間往往是發(fā)生沖突的。調度目標分為三類:基于作業(yè)交貨期的目標、基于作業(yè)完成時間的目標和基于生產成本的目標［3］。2.1.4生產調度問題的調度策略由于車間調度問題的復雜性，各種不同的具體問題往往有很多不同的解決方法，因此需要從策略上去考慮調度問題，以支持生產調度高層次的決策部分。并行和分布策略一般調度問題很復雜，一旦問題規(guī)模加大就更難求解，因此不少研究者提出并行或分解的策略來解決調度問題。多智能體系統(tǒng)的研究是目前分布式人工智能領域的研究熱點。大量的研究表明多智能體系統(tǒng)特別適用于解決復雜問題，尤其是那些經典方法無法解決的單元間有大量交互作用的問題。由于調度問題的復雜性和并發(fā)性等特點，最近多智能體已在調度上得到了較多的應用。多智能體系統(tǒng)不但速度快、可靠性高、可擴展性強、能處理帶有空間分布的問題。對不確定性數據和知識有較好的容錯性；而且由于是高度模塊化系統(tǒng)，因而能澄清概念和簡化設計。因此它必將得到更加廣泛的應用。分解或成組策略利用分解和成組調度策略可以大大降低問題的計算復雜性和規(guī)模，求得調度問題的較優(yōu)解。成組技術基本思想是根據工件、機器等之間的相似性將它們分組，利用組內的相似性降低問題的計算復雜性和規(guī)模，求得調度問題的較優(yōu)解，同時優(yōu)化系統(tǒng)的一些性能指標。動態(tài)重調度策略由于實際的加工系統(tǒng)具有隨機性和不確定性，特別在動態(tài)環(huán)境下，調度本身就是不斷地動態(tài)重調度的過程。基于目前的研究，動態(tài)調度的觸發(fā)方式主要有：周期調度、事件驅動調度、連續(xù)調度、以及周期與事件調度相結合的混合調度等。滾動優(yōu)化的思想很早就被應用于生產調度。與常規(guī)調度方法相比，滾動調度可避免生產的大幅度波動，在滾動調度中，對某一些區(qū)間內的工件(工件窗口)進行調度，但按時間只對此區(qū)間內的部分工件進行實際加工，然后再向工件窗口中加入新工件來形成滾動。滾動調度不僅可以應付刑S中的不確定性和突發(fā)偶然事件，而且每次只對工件窗口內的工件進行調度，可使問題求解規(guī)模大大減小。(4)多目標決策實際調度問題往往是多目標的，如最短生產期、最大生產利潤，而且這些目標往往相互沖突。對多目標優(yōu)化問題，數學規(guī)劃中的處理方法有約束法、評價函數法、功效函數法、分層序列法等。人機交互策略為了取得好的調度結果，并考慮實際調度中存在的各種復雜因素，往往需要好的人機交互策略去啟發(fā)和利用調度決策者的經驗和知識。大量的研究成功表明在目前的知識條件下人機交互策略是解決困難問題的一條有效途徑［3］。

流水車間調度問題2.2.1流水車間調度問題的描述流水車間調度問題一般可以描述為n個工件要在m臺機器上加工，每個工件需要經過m道工序，每道工序要求不同的機器。n個工件在m臺機器上加工的順序相同，工件i在機器m上的加工時間是給定的，設為t（i=1,2,...,n,j=1,2,...,m）。問題的目標是確定i,jn個工件在每臺機器上的最優(yōu)加工順序，使最大流程時間達到最小。對該問題常常作如下假設：（1） 每個工件在機器上的加工順序是給定的；（2） 每臺機器同時只能加工一個工件；（3） 一個工件不能同時在不同機器上加工；（4） 工序不能預訂；（5） 工序的準備時間與順序無關，且包含在加工時間中；（6） 工件在每臺機器上的加工順序相同，且是確定的。令c（j,k）表示工件j在機器k上的加工完成時間，｛j,jj｝表示工件的調度，那i i 1 2n么，對于無限中間存儲方式，n個工件、m臺機器的流水車間調度問題的完工時間可表示為：c(j1,1)=tji1c(j,k)=c(j,k-1)+t11 jikik=2,...,mc(j,1)=1cc(j,1)=11-1 j.1ii=2,...,n+ti jikic(j,k)=max{c(+ti jikii i-12-1)2-2)2-3)最大流程時間為c=c2-1)2-2)2-3)最大流程時間為c=c（j,m），max n調度目標就是確定｛j,jj｝，1 2n使得c 最小［3］。max2.2.2流水車間調度問題的求解方法流水車間調度問題的求解方法很多，啟發(fā)式算法比較常見。啟發(fā)式算法（Heuristicalgorithm）是相對于最優(yōu)算法提出的。一個問題的最優(yōu)算法是求解該問題的最優(yōu)解而啟發(fā)式算法是在可接受費用內尋找最好的解，但不一定能保證所得解的可行性和最優(yōu)性，甚至在多數情況下，無法闡述所得解同最優(yōu)解的近似程度。事實上，在實際問題中，最優(yōu)算法因問題的難度使其計算時問隨問題規(guī)模的增加以指數速度增加，使人無法接受。這時只能通過啟發(fā)式算法求得問題的一個可行解。啟發(fā)式算法可定義為：一個基于直觀或經驗構造的算法，在可接受的花費（指計算時間、占用空間等）下，給出待解決組合優(yōu)化問題每一個實例的一個可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預料。33蛙跳算法3.1蛙跳算法簡介蛙跳算法是新發(fā)展起來的一種啟發(fā)式算法，它通過啟發(fā)函數(某一數學函數)進行啟發(fā)式搜索，從而找到問題的解。事實上，蛙跳算法結合了以遺傳行為為基礎的Memetic算法和以社會行為為基礎的粒子群優(yōu)化PSO算法的優(yōu)點。Memetic算法Memetic算法是一種通過啟發(fā)式搜索解決優(yōu)化問題的群智能算法，受Dawkin提出的memeM念的啟發(fā)而出現的。1989年，由Moscato第一次使用這種算法。"memetic"來自于單詞"meme"，meme指的是寄存于人或動物的大腦中能指導他們的行為并能傳播的信息。meme的內容，被稱為memotype，類似于基因中的染色體。一個想法或信息直到它被重復或傳播才能成為一個meme。所有可傳播的知識都是memetic。這種算法和遺傳算法相似，不同的是，在MAs中，組成染色體的元素被稱為memes，而不是基因。Memetic算法的特征是所有的染色體和后代可以在進化之前通過局部搜索獲得一些經驗。這樣，Memetic算法通常被描述為增加了局部搜索的遺傳算法⑴。3.1.2粒子群算法粒子群優(yōu)化(ParticleSwarmOptimize，PSO)算法由Kennedy和Eberhart于1995年提出的，是一種基于群智能(SwarmIntelligence)方法的演化計算技術。PSO算法通過模擬鳥群的捕食行為來實現優(yōu)化問題的求解。首先在解空間內隨機初始化烏群，鳥群中的每一只鳥稱為“粒子”，這些“粒子”具有位置和速度兩個特征，在解空間內以某種規(guī)律移動，經過若干次迭代后找到所求解問題的最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己的速度和位置。第一個是粒子本身的最優(yōu)解p，另一個極值是整個粒子群best目前找到的最優(yōu)解G。PSO的速度、位置算是表示如下:bestVk+1 Vk+1 k-1Vk+cRandii1()C—Xkii)+cRand2()Qk—Xki3-1)Xk+1=Xk+Vk+1

3-1)式中，Vk為粒子i在第k次迭代中的速度；Xk為粒子i在第k次迭代中的位置；Pki i i為粒子i的個體極值；Gk為在第k次迭代中的全局極值；Rand()為在區(qū)間［0,1］上的隨機數;-為慣性權重；S是認知系數，調節(jié)向的飛行步長；c2是社會系數，調節(jié)向Gk的飛行步長。迭代過程中，粒子的速度和位置都限制在特定的范圍內，同時Pk和Gk不i斷更新，最后輸出Gk就是全局最優(yōu)解⑴。蛙跳算法國內外研究情況目前僅有很少的關于蛙跳算法的研究，相關的成果如下：2003年Eusuff和Lansey首次將這種算法用來解決管道網絡擴充中的管道尺寸最小化問題，在SFLA基礎上提出了一個計算模型SFLANET，并且為了評價該模型的性能在一些實例上進行了測試［4］。2005年Elbeltagi等在連續(xù)優(yōu)化和離散優(yōu)化方面將遺傳算法、Memetic算法、微粒群算法、蟻群算法和蛙跳算法五種進化算法的模型和結果進行了比較［5］。實驗結果表明：蛙跳算法在解決某些連續(xù)函數問題時成功率和收斂速度優(yōu)于遺傳算法，近似于粒子群算法［5］。2006年Eusuff等將發(fā)展了的蛙跳算法用于解決組合優(yōu)化問題，通過具體應用得出：蛙跳算法是一種解決組合優(yōu)化問題的有效工具，在收斂效果和速度上優(yōu)于遺傳算法［4］。2007年，AlirezaRahimi,Vahed等提出了混合多目標蛙跳算法HMOSFLA用于解決多目標的混合型裝配線排序問題，且HMOSFLA的性能優(yōu)于MOGA，這一優(yōu)勢在求解大型問題時尤為突出［4］。國內學者直到2007年才開始對蛙跳算法予以關注，相關成果更是很少，主要成果包括：2007年，王輝，錢鋒討論了四種群體智能優(yōu)化算法一蟻群算法、微粒群算法、人工魚群算法和混合蛙跳算法，對其算法的原理、發(fā)展及應用進行了綜述。提出了群體智能優(yōu)化算法統(tǒng)一框架模式，并對群體智能優(yōu)化算法進一步發(fā)展進行了討論［6］。2007年，李英海等針對蛙跳算法局部更新策略引起的更新操作前后個體空間位置變化較大，容易降低收斂速度這一問題，提出了一種基于閾值選擇策略的改進混合蛙跳算法。通過不滿足閾值條件的個體分量不予更新的策略，減少了個體空間差異，從而改善算法性能［7］。蛙跳算法是一種新興的群智能算法，對于該算法的研究還處于非常初步的階段，僅有極少的文獻，不過已經顯示出較大的潛力，存在很大的發(fā)展空間。適用范圍。SFLA的應用僅在函數優(yōu)化、聚類、組合優(yōu)化、多目標優(yōu)化方面有較少的應用，并且其應用大多數還和具體問題相關，僅停留在研究階段，其它的很多應用還尚未開始。顯然，SFLA不會僅僅局限于目前的這些領域。如果將SFLA引入機器學習、自動控制等領域，將大大地促進算法的研究和發(fā)展。數學基礎。SFLA的有效性在一些實例和數值實驗中得到證明，但并沒有給出收斂性、收斂速度估計、分布性、多樣性等方面的數學證明。雖然有些文獻對收斂性等根據實驗數據做了一些研究，但是目前其理論和數學基礎的研究還很不夠。算法收斂性以及算法本身的研究都需要在理論上進行更加深入的探索，僅僅依靠實驗方法是不夠的。參數的設計與選擇。SFLA中的參數選擇依賴于具體問題，設計合適的參數需要經過多次實驗。研究如何選擇和設計參數，使其減少對具體問題的依賴，也將大大促進SFLA的發(fā)展和應用。算法性能的改進。應該致力于補充和擴展SFLA與其他算法或技術的結合，克服SFLA相關的缺點?？梢灶A見，隨著SFLA和一些相關領域學科的發(fā)展，SFLA在不久的將來一定會大顯身手，并有新的突破［1］。3.3蛙跳算法原理蛙跳算法基本概念青蛙(frog):又稱為個體。等同于GA中的染色體，是生物遺傳物質的主要載體?？梢允褂靡唤M二進制0，1代碼或實數表示?；?Gene):基本的遺傳物質的結構單位，若干個基因組成一個青蛙。種群(population)：—定數量的個體(frog)組成了種群。種群中數量的大小稱之為種群規(guī)模。生物進化算法的基本思想是模擬生物由一個種群進化到一個新的種群的過程。⑷族群：由種群劃分得到的一組個體(frog)。類似于一個國家中的民族，所有族群組成種群。適應度(fitness):用來描述個體(frog)對當前環(huán)境的適應程度。通常由數值表示的個體優(yōu)劣程度。適應度一般就是要優(yōu)化的目標函數，這個函數的設定決定了算法最終尋優(yōu)結果的優(yōu)劣。⑹分組(group):把種群以一定方式劃分為族群。可以采用隨機分組、循環(huán)分組等多種形式。選擇：和GA不同，SFLA算法只考慮當前族群中適應度值最優(yōu)的個體對族群中最差個體的更新，更新體現青蛙活動的方向性。更新:SFLA算法有特定的更新公式，替代了GA中的交叉、變異的工作。更新是SFLA算法的核心［8］。蛙跳算法原理描述圖3-1是蛙跳算法的原理示意圖［1］。

Sesuhspace：雪⑺gy切perfbiminglocai豳◎then\they口朗聽irfonratflnwi(h)othergroups.圖3-1蛙跳算法的圖解如圖所示，在SFLA中，種群由很多青蛙組成，每只青蛙代表一個解。種群被分成了多個子群，每個子群包括一定數量的青蛙，稱為一個memeplex。不同的memeplex可以看作是具有不同文化的青蛙群，分別執(zhí)行局部搜索。在每個memeplex中，每只青蛙都有自己的想法，并且還受其它青蛙想法的影響，通過Memetic算法來進化發(fā)展。這樣，經過一定的Memetic進化以及跳躍過程，這些想法思路就在各個memeplex中傳播開來。然后，繼續(xù)局部搜索和跳躍，直到收斂標準滿足為止［1］。蛙跳算法（shuffledfrogleapingalgorithm,SFLA）是Eusuff等受生物模仿啟發(fā)提出的一種基于群體協同搜索的模因算法。模因是一種通過感染人或動物的思想，進行傳播、復制和交流的信息體。模因算法最顯著特征是群體在進行傳統(tǒng)進化過程之前，通過某種局部搜索方式，模因之間或內部可進行經驗、知識和信息的共享和交流。因此，模因算法對傳統(tǒng)遺傳算法模型中的個體賦予了智能水平。SFLA的群體由互相能夠交流的青蛙構成，每個青蛙可看作一個模因的載體，通過青蛙個體之間的交流可使算法執(zhí)行模因進化。目前該算法已經在比例-積分-微分控制器控制等工程問題以及一些經典組合優(yōu)化問題上取得成功應用［8］。算法首先初始化隨機一組群體，然后計算每一個frog的適應度值，然后根據適應度值進行排序，排序后，根據它們的排列序號進行分組，分組采用余數相同原則進行分組，如共分三組，第一個放入一組，第二個放入第二組，第三個放入第三組，第四個放入第一組，以此類推。分組進行完成之后，每一組內進行更新，更新使用適應度值最高的frog通過更新公式對適應度值最低的frog進行更新，如果更新成功，則替換原有frog，迭代執(zhí)行，否則隨機生成一個新的frog?；旌纤衒rog，重新分組，直到所有滿足終止條件。蛙跳算法的核心步驟：（1） 局部搜索：局部搜索是在每個族群內部進行信息交互（更新公式），每次主要是兩個青蛙個體不斷的迭代進行信息交互（族群內最優(yōu)個體和族群內最劣個體），使整個族群向著最優(yōu)解的方向跳轉，從而達到局部深度搜索（局部內考慮更多的可能解）的目的。（2） 全局信息交互：當局部搜索完成后，每一個青蛙個體會被重新計算適應度值，進而進行重新排序、分組。再次分組后每個族群中的個體均會發(fā)生改變，因此局部搜索中族群間可以進行信息交互，加快求解速度。局部搜索能夠快速有效地在一個特定區(qū)域找尋極值，加快搜索進程；全局交互避免陷入局部最優(yōu)解的問題［8］?；旌贤芴惴üぷ鬟^程描述如下：隨機生成含有f個青蛙的群體P={X,XX}，對于解為t維的問題，第i個青蛙的位置X=［x,x，…,x］?生成群12 F i i1i2 it體之后，計算每個青蛙位置的適應度值f（X），將其從大到小進行排序。將排序后的青i蛙按式（3-2）平均分配到m個族群，每個族群有n個青蛙，因此有F=mn.M={X ePII<l<n},1<i<m （3-2）i i+m（l—1）其中，m為第i個族群。族群中適應度函數值最小的青蛙位置用x表示，按（3-3）iw和式（3-4）更新。TOC\o"1-5"\h\zD=r（X—X） （3-3）swX=X+D,D<D<D （3-4）ww min max其中，X為當前族群適應度最佳的青蛙位置；r為（0,l］內的隨機數；D為青蛙移動s距離；D和D分別為青蛙位置所允許移動距離的最大值和最小值。更新后若適應度maxmin值優(yōu)于原適應度值，則用X'取代X；否則，用式（3-5）代替式（3-3）wwD=r（X—X） （3-5）bw其中，X為當前整個群體適應度最佳的青蛙位置，若更新后仍無改進，則隨機生成一b行解代替X，在族群內重復此操作，知道設定的迭代次數。隨后對所有族群的青蛙重w新混合并排序，更新群體最佳青蛙位置X，然后重新劃分族群，進行局部深度搜索，b如此循環(huán)直到滿足終止條件［4］。圖3-2為蛙跳算法流程圖。

開始構造下一彳弋的新種群停止條件滿足確定種群大小Ftmemqitex的數量用，開始構造下一彳弋的新種群停止條件滿足確定種群大小Ftmemqitex的數量用，毎組memeplex中最大迭代次數%,每組m詢即T中青蛙的個數?青蛙在不同memeplex中跳躍：重新匯合、排序將尸只青蛙分別放■在m組iDiineplex中將所有奇睡袪適配值降序排列円箏每只育蛙的適配值用Memetic算法局部搜索＜A)初始化種群輸出最優(yōu)解片圖3-2蛙跳算法流程圖蛙跳算法的相關研究鑒于SFLA的優(yōu)越性，SFLA已經廣泛應用于許多自然科學與工程科學領域，顯示出強大的優(yōu)勢和潛力。關于SFLA的相關研究已經涉及資源網絡優(yōu)化問題、連續(xù)優(yōu)化問題、離散優(yōu)化問題、聚類問題、流水車間調度問題、裝配線排序問題、TSP問題以及參數調節(jié)問題等。3.4.1資源網絡優(yōu)化問題在資源網絡優(yōu)化方面，2003年Eusuff和Lanseyr將SFLA用于求解水資源網絡的管徑選擇和管網擴張問題中。在該文中，解向量南表示管徑類型的一串整數值構成。算法作為優(yōu)化工具，采用成熟軟件EPANET作為約束檢驗工具。通過與其他文獻的求解結果相比較，作者展示了SFLA的優(yōu)越性，給出了SFLA算法在求解這類問題時的適用參數組合［6］。連續(xù)優(yōu)化問題2005年，Elbeltagi等人對SFLA算法、元算法(MA)、粒子群算法(PSO)、蟻群算法(AntColonyOptimization，ACA)及遺傳算法(GA)進行了比較，詳細描述了各種算法，給出了各個算法的簡單實現過程的偽碼及合理化的參數組合。采用F8和F10這兩個具有連續(xù)變量的函數，評價了SFLA算法的計算性能，結果顯示SFLA在F10函數的求解方面性能不夠理想，在F8函數的求解上性能優(yōu)于GA算法，與PSO算法的性能相近［9］。離散優(yōu)化問題2005年，Elbeltagi等人對SFLA算法、元算法(MA)、粒子群算法(PSO)、蟻群算法(AntColonyOptimization，AC0)及遺傳算法(GA)采用建筑業(yè)的項目管理問題對5種算法的求解結果進行了比較，結果顯示SFLA求解效果不夠理想，僅優(yōu)于GA算法。2006年，Eusuff等人采用5個標準離散函數測試了SFLA算法的求解效果，系統(tǒng)地測試并給出了算法的最佳參數組合。之后，他們將SFLA算法用于求解地表水模型標定問題.并通過與GA相比較來說明SFLA算法的有效性。2007年。李英海等人對SFLA算法進行了改進，通過概率的方式來決定是否改進最差蛙的位置。通過F7等4個參數的計算結果，表明改進后的算法在求解效果方面得到了改善和提高［6］。聚類問題2008年，Yang等采用SFLA與GA的混合算法求解了基于聚類的基因選擇問題，取得了較好的結果。2009年，Amili等人采用SFLA求解了K均值聚類問題。通過多組數據集對算法的求解效果進行了測試，并與其他4種算法進行了比較.結果顯示SFLA算法的目標函數值(距離矩陣中所有數值和的最小值)明顯優(yōu)于其他算法的目標值。此外，他們還系統(tǒng)地測試了算法參數組合，給出了算法的最佳參數組合［8］。其他優(yōu)化問題2006年，Elbehairy等人求解了橋面修復決策問題，比較了SFLA算法和GA算法在該問題上的求解性能。結果表明，在各自的合理化參數組合下，SFLA和GA都能達到令人滿意的求解效果，但總體看來，SFLA效果略好于GA算法。2007年。Rahimi，Vahed等人采用SFLA求解了多目標混合模型裝配線排序問題。通過將產品類型與數字進行對應，從而將解向量按整數串形式進行編碼。通過將算法與其他3種不同的GA算法進行比較，表明SFLA算法得到了更多的Pareto解。錯誤率比其他3個GA算法更小，并且Pareto解集的多樣性更好。2008年,Luo等人采用SFLA求解了TSP問題,通過與TSPLIB中的標準測試問題的結果進行比較，證明了SFLA算法的優(yōu)越性.得到了新的6組改進解。2008年，Huynh采用混合SFLA算法求解了多變量PID控制器參數調節(jié)問題.結果證明混合SFLA算法的控制能力更強，控制效果比GA等算法更好。2009年，Rahimi,Vahed等人求解了具有雙準則的帶緩沖區(qū)流水車間調度問題。采用Pareto解的數和錯誤率作為評價標準，將混合SFLA與2個GA算法進行了比較，結果表明SFLA算法在多目標問題求解上有優(yōu)越性［8］。蛙跳算法的優(yōu)缺點蛙跳算法的優(yōu)點：較少的參數。相對于其它進化算法，參數較少。計算速度快。由于在SFLA算法中采用了分組策略，每一組frog可以搜尋一個方向，并由一直帶頭frog指引方向(更新策略)，使得算法執(zhí)行過程中能在局部快速找到最優(yōu)解。全局搜索。由于SFLA算法執(zhí)行中會采用分組策略，每組進行局部深度搜索，多組并行進行全局搜索，并在執(zhí)行一定次數的局部搜索后，進行全局性的個體融合，然后再次分組，實現不同組間的信息交互，達到快速全局搜索的目的。每次迭代過程中，所有的frog均可以通過融合操作達到多次選擇參與進化的目的。蛙跳算法的缺點：作為進化算法，蛙跳算法也存在著諸多進化算法的缺點，即算法的執(zhí)行過程中含有參數，算法時間復雜度較高，最優(yōu)解不唯一等。綜上所述，蛙跳算法是一種尋優(yōu)能力很強的算法，能夠快速求解優(yōu)化問題，避免了傳統(tǒng)進化算法易陷入局部最優(yōu)解的問題［8］。4零等待策略（NW）的Flowshop調度問題4.1零等待策略（NW）的Flowshop調度問題數學模型在間歇過程中，有些化學反應經常要求中間產物在某個設備處理完畢后，立即轉移到下一個加工設備中，不能延誤或者中間存儲，這時需要采用零等待存儲策略。在典型的間歇過程中，如染料生產中，一些活性染料和還原染料的生產過程會生成不穩(wěn)定的中間產物，為了保證中間產物的反應活性和操作安全，反應通常在氮氣保護或低溫下進行，而設立中間儲罐會使生產的保持變得相當困難，因而每一步操作完成后，都要立刻轉移到下游設備中進行下一步操作；又如許多生化制品的生產需要在無菌、無氧的條件下進行，中間存儲對于保持適宜的生產條件是很不利的；在鋼鐵加工過程中，加熱過的金屬在降溫前需要經過一系列不間斷的操作過程，以防止其成品的組分中存在缺陷；在塑料加工行業(yè)也存在同樣的過程，它在不同的加工單元中加工必須是連續(xù)的，從而防止其老化。生產過程中采用零等待ZW存儲策略的另一個原因是中間儲罐會增加設備的投資，增加過程控制的難度，因此這種操作方式在生產中被廣泛應用。Flowshop調度問題可以這樣描述:有n個產品需要加工；可供選用的設備單元有m個，第i個被加工的產品在第j個設備上需要的加工時間為T，它包括裝配時間、傳輸ij時間、卸載時間、加工時間以及清洗時間等；每個產品的加工工序都相同，并且以相同的次序在各設備上加工；過程按零等待方式進行，即一批產品在設備j加工完畢之后，必須立即轉移到下一個加工設備j+1中去；定義S和C分別表示產品i在設備j上的開ij ij始加工時間和完工時間，S.和T分別是產品i的最后一道工序的開始加工時間和處理時ieie間，以最小化總加工周期為調度目標。首先作如下假設:（1） 所有產品在每個加工單元上的操作次序相同，即為排序；（2） 產品之間沒有優(yōu)先性；（3） 一個設備不能同時處理多種產品，一種產品不能同時為多個設備處理；（4） 對最終的產品有足夠的存儲容量；（5） 產品的加工過程中不允許中斷。上面的定義和假設可以用下面的數學模型表示min Z=max （S+T）}（4-1）ie ies.t. S=S +T（4-2）ij i（j-1） i（j-1）S>S、+T,、 iGN,jGMij （i-1）j （i-1）j（4-3）S>0（4-4）ij

式（4-2）表示加工產品的順序約束，產品i的第j道工序必須在第j-1道工序完成后才能開始，即任何一道工序的加工開始時間必須大于等于該產品前一道工序的結束時間；式（4-3）表示加工產品的資源約束，一批產品的生產必須在前一批產品在某一處理單元處理完畢后才能進入該處理單元，即任一時刻該處理單元不能同時處理兩個產品；式（4-4）說明產品的開始加工時間大于或等于零。由于產品的加工方式是零等待，在第一個加工單元上的產品的開始操作時間需要適當的延遲。令加工順序中產品s和產品t相鄰，k為加工單元上處理產品的排序號，貝U兩個產品的延遲時間為：d=max<m-11d=max<m-110,乙T—乙T4-5)stm-2,Mstst)=)=min(Z)。min（makespan4.2仿真分析基于蛙跳算法解決零等待Flowshop問題，算法用Matlab語言進行編程，仿真7個工件在7臺機床上進行加工的Flowshop調度問題。進行三次基于不同蛙跳算法設定值的仿真。表4.1是產品的加工時間。表4.1產品的加工時間JobUnit12345671692310832630258147255258158214214147753806347547578557885226994231966962145863568775158325530785325565412679687421423689689830275422055789633258001204.2.1示例1基于上述工件與機床設定并采用上述算法并基于模型使用Matlab軟件進行第一次仿真，取種群分組數M_pop=30，每組青蛙包含的個數N_frog=30，組內迭代數Ni_MAX=20,最大步長S_max=5,種群總進化代數MAXGEN=100,進行尋求最優(yōu)解仿真，結果如圖4-1。7600 1 1 1 1 1 1 1 1 1 0 10 20 30 40 50 60 70 80 90 100Generation圖4-1最優(yōu)解遺傳演化曲線1圖4-1為最優(yōu)解的遺傳演化曲線，橫軸為演化代數，即演化時間，縱軸為目標函數值，優(yōu)化目標為minZ=maX5+I"。圖中有曲線折線兩條線，上方曲線為種群內的平均值曲線，下方紅線為種群的最優(yōu)值曲線，每代中子群最優(yōu)化后種群最優(yōu)化，隨著代數的不斷增加，目標函數收斂，并達到最優(yōu)質且穩(wěn)定，證明了算法的收斂及有效性。該圖的設定值所仿真出的最優(yōu)排序為(2,4,5,3,7,6,1)，所對應的甘特圖如圖4-2，所模擬問題為零等待的加工序列，所以由圖看出，同一編號的工件在不同機床上加工時，每道工序的結束時間和下一道工序的開始時間一定是一樣的，就做到了零等待加工，所以在同一機床上看，加工完一件工件后，會有一定的時間間隔，那么這個時間間隔的大小就是通過蛙跳算法的模擬計算出來的一個最優(yōu)解。005①ELLmugOESOL沖r~—r--609566ZS6舄T-S9二圖4-2最優(yōu)調度結果Gantt圖示寸 0 3euii|oe[A|BuisseooJd66ZS0蜀G0品S0IN呂EUJO窗呂H-西r--UJL晝壬g9SMOS00匚INong±±ns(D」6u虧p￡oso￡示例2基于上述工件與機床設定并采用上述算法并基于模型使用Matlab軟件進行第二次仿真，取種群分組數M_pop=40,每組青蛙包含的個數N_frog=30,組內迭代數Ni_MAX=20,最大步長S_max=5,種群總進化代數MAXGEN=100,進行尋求最優(yōu)解仿真，結果如圖4-3。圖4-3最優(yōu)解遺傳演化曲線2該圖所對應的最優(yōu)排序為(4,2,7,6,3,5,1),由圖看出,同一編號的工件在不同機床上加工時,每道工序的結束時間和下一道工序的開始時間一定是一樣的,做到零等待加工,所以在同一機床上看,加工完一件工件后,有一定的時間間隔,通過蛙跳算法則體現在族群內優(yōu)化與族群間優(yōu)化的先后過程,并得出最終優(yōu)化結果中。按照本示例的參數設定,可以看出,在第30代左右時達到了最小時間并趨于穩(wěn)定,所求目標時間函數大概在7800左右。示例2與示例1的不同之處在于,示例2的紅色最優(yōu)值曲線較為穩(wěn)定,優(yōu)化過程有效性很高。按照此順序進行加工,其模擬的甘特圖如圖4-4：茗幕冨爲asgCN色ucmgEMEgmssgoesOS窗9￡S*995旳S気ZZZOE9￡S#6尊LG韶gsissfc比￡2專EoezLS2S0O0gLssc?□0oogo

QC3

寸G6LF30INSLt.CM寸匚窩C50On對 m eeuiqoeiAiGuisseooJd示例3基于上述工件與機床設定并采用上述算法并基于模型使用Matlab軟件進行第二次仿真，取種群分組數M_pop=30,每組青蛙包含的個數N_frog=30,組內迭代數Ni_MAX=20,最大步長S_max=3,種群總進化代數MAXGEN=100,進行尋求最優(yōu)解仿真，結果如圖4-5。圖4-5最優(yōu)解遺傳演化曲線3該圖所對應的最優(yōu)排序為(4,5,3,7,6,1,2),同樣的,按照示例參數設定,仿真出的零等待機床為前一工件的加工完成時間一定等于同一工件的下一步驟開始時間,滿足零等待加工的要求,那么由示例3的設定仿真看出,同樣在第30代左右求出最優(yōu)解,即30代左右達到最小加工時間,最小加工時間大約為7900左右。精確的時間則由甘特圖可以看出,最小加工時間為7895,最后完成工件為2號。按照此順序進行加工,其模擬的甘特圖如圖4-6：rd

uJ京心」g-npo-IZos心￡6S3窩石OOZST-S9OLis卜烹9L6Z6CD￡nrtLi』E06ZSZOE盟4-6最優(yōu)調度結果Gantt圖示63L 寸M06Z雷胃呂劉SE00S0009002①一U___L口匚一留山30」丄0SP000E00009;Jon cmauiqoeiAjGuissaoojd000L示例4基于上述工件與機床設定并采用上述算法并基于模型使用Matlab軟件進行第二次仿真，取種群分組數M_pop=40,每組青蛙包含的個數N_frog=40,組內迭代數Ni_MAX=20,最大步長S_max=3,種群總進化代數MAXGEN=100,進行尋求最優(yōu)解仿真，結果如圖4-7。9009000008600840082008000托肚 1 1 1 1 1 1 1 1 1 0 10 20 30 40 50 60 70 80 90 100Generation圖4-7最優(yōu)解遺傳演化曲線4該圖所對應的最優(yōu)排序為(2,4,5,6,7,3,1)，同樣的，按照示例參數設定，仿真出的零等待機床為前一工件的加工完成時間一定等于同一工件的下一步驟開始時間，滿足零等待加工的要求，那么看到示例4的改變參數將族群分組數增加到了40，每組青蛙包含的個數同時增加到40，經過優(yōu)化得到的最優(yōu)曲線卻在40代左右趨于平穩(wěn)，于預期的分組數越多達到穩(wěn)定越快不符合，下面將繼續(xù)研究。精確的時間則由甘特圖可以看出，最小加工時間為7705，最后完成工件為1號。按照此順序進行加工，其模擬的甘特圖如圖4-8：

±±nsal6u=npollos￡1寸曇F=留UJUJv.r'-xBUJL茁1g■y■J①E±±nsal6u=npollos￡1寸曇F=留UJUJv.r'-xBUJL茁1g■y■J①E匚b匚一ssOJlJEdSS呂導呂屆Z g M7) 寸 n CMeumoeiA]BuissesoJd圖4-8最優(yōu)調度結果Gantt圖示

示例5基于上述工件與機床設定并采用上述算法并基于模型使用Matlab軟件進行第二次仿真，取種群分組數M_pop=20,每組青蛙包含的個數N_frog=20,組內迭代數Ni_MAX=20,最大步長S_max=3,種群總進化代數MAXGEN=150,進行尋求最優(yōu)解仿真，結果如圖4-9。圖4-9最優(yōu)解遺傳演化曲線5該圖所對應的最優(yōu)排序同樣為(2,4,5,6,7,3,1),同樣的,按照示例參數設定,仿真出的零等待機床為前一工件的加工完成時間一定等于同一工件的下一步驟開始時間,滿足零等待加工的要求,那么看到示例4的改變參數將族群分組數恢復20,每組青蛙包含的個數同樣恢復20,經過優(yōu)化得到的最優(yōu)曲線卻在25代左右趨于平穩(wěn),由此和前面的示例進行對比,發(fā)現種群進化代數越大,得到優(yōu)化成功的速度越快,此結論符合理論,證實了算法的有效性,正確性。精確的時間則由甘特圖可以看出,最小加工時間為7705,最后完成工件為1號。按照此順序進行加工,其模擬的甘特圖如圖4-10：

giY■jSS①giY■jSS①6wcrlsclJ30」d§s§seuiL|3e|/\|Buissesojd圖4-9最優(yōu)解遺傳演化曲線5從以上的所有仿真中可以看出，當我們確定了一套機床去解決一系列工件的加工問題后，如果需要做到零等待的加工，采用蛙跳算法來解決，我們的目的是讓工作時間最小化。由三次仿真看出，當示例1和示例2分別設定了較大的種群分組數和較大的最大步長時，目標函數時間較短，結果較精確，而示例3將種群分組和最大步長減小時，模擬出的結果不是很精確。結果在30代左右趨于最優(yōu)，所耗時間最短，當種群分組數和種群總進化代數增加時，會明顯提高搜索的效率，使趨于穩(wěn)定的代數提前，但同時，如果增大了每組青蛙的數量時，由于搜索的可能性加多，效率會減低，但不同的參數和設定值的組合還是會對排序結果造成更多的影響。4.3小結本章為解決NW調度問題提供了具體仿真研究，首先建立了零等待調度問題的數學模型，并用Matlab對蛙跳算法及NW調度問題進行編程，考慮到零等待調度的特點，建立模型后以最小化生產周期為目標函數進行優(yōu)化，從而模擬出用于實際生產的甘特圖，得出了較滿意的結果，驗證了編程與所建模型的可操作行和有效性。5總結與展望5.1本文總結本文研究運用蛙跳算法解決實際操作中的零等待流水線調度問題，本文分別介紹了調度問題和蛙跳算法，并將兩者結合進行仿真實驗解決問題。零等待流水線調度問題屬于組合優(yōu)化問題的一種，本文在介紹組合優(yōu)化問題的基礎上，介紹調度問題的類型，特點，研究近況等，并分層詳細引出零等待調度問題。對蛙跳算法的介紹注重概念和原理的介紹，探討了在零等待流水車間問題的應用，設計出該問題的算法，過程較易于實現。通過仿真實驗的過程，基本證明了編程的正確性和有效性，仿真的結果也證明了所建模型的正確性和算法的有效性。蛙跳算法在處理一類組合優(yōu)化問題上參數較少，采用了分組策略，使得計算速度較快，而且在分組局部深度搜索的基礎上進行全局搜索，實現了不同組之間的信息交互，具有準確快速的特點，較適合解決此類問題，但也存在待改進的地方，比如在仿真過程中含有參數，對參數的修改導致最優(yōu)解不唯一等問題。在完成論文的過程中我自身也存在很多不足之處，在建模與編程方面依然存在相當的不足，對整個調度問題的研究方向了解很不全面，在今后的生活中希望能彌補這方面的不足。5.2展望隨著科學技術水平的飛速發(fā)展，人們已將視線逐漸關注于如何提高生產效率、如何將理論最優(yōu)化的應用在實際生產中，Flowshop問題漸漸得到相當的重視。實際問題往往相當復雜，未來的研究定將在實際的應用中建立更加精確的模型，對工件加工的零等待調度問題和如何最大化的縮小工時，提高工作效率，將會是未來研究的一大方向。同時，在理論方面，蛙跳算法作為一種最優(yōu)化算法，其自身也將不斷優(yōu)化，并有可能衍生出更加適合具體操作問題的算法，理論將對具體問題有具體的分析，匹配度更高，從而更有效率的解決生產生活中的具體問題，為生產的運轉提供更多的支持，帶來更多的便利。參考文獻⑴王亞敏.蛙跳算法的研究與應用.[D]北京工業(yè)大學，碩士論文⑵徐震浩，顧幸生.不確定條件下具有零等待的流水車間免疫調度算法.J]計算機集成制造系統(tǒng)，2004，10-13⑶張松艷，基于遺傳算法的FlowShop調度的研究與應用.[D]浙江工業(yè)大學,2008.M．M．Eusuff，K．E．Lansey．Optimizationofwaterdistributionnetworkdesignusingtheshuffledfrogleapingalgorithm．WaterResourPlanManage，2003，129(3)：210-225，Rippin，D.W.T.，1993，Batchprocesssystemengineeringretrospectiveandprospectivereview，ComputChemEng，17:S1E．Elbeltagi，T．Hegazy，D．Grierson．Comparisonamongfiveevolutionary_basedoptimizationalgorithm.AdvancedEngineeringInformatics，2005，19(1):43-53⑹王輝，錢鋒.群體智能優(yōu)化算法.[J]化工自動化及儀表，2007,34(5):7-13.⑺李英海，周建中?一種基于選擇策略的改進混合蛙跳算法 .[J]計算機工程與應用.2007，43(35):19-21．⑻駱劍平，李霞.求解TSP的改進混合蛙跳算法.[J]深圳大學學報理工版,2010:27-28肖力.改進免疫算法在Flowshop調度上的應用.[J]計算機仿真,2008,03:13-17昊華麗,汪玉春，陳坤明,等?基于混合蛙跳算法的成品油管網優(yōu)化設計.[J]石油工程建設,2008(1):14-16高尚，楊靜字.群智能算法及其應用.[D]中國水利水電出版社,2006:2-4王亞敏,冀俊忠,潘全科.基于離散蛙跳算法的零空閑流水線調度問題求解.北京工業(yè)大學學報,2010,36:124-130常俊林,邵慧鶴.兩機零等待流水車間調度問題的啟發(fā)式算法.2005,07:13-16ALLAHVERDIT,GUPTAJ,