項目優(yōu)化調(diào)度的病毒協(xié)同進化遺傳算法doc(存儲版)
【正文】 hard問題,有兩種以上的不可重復(fù)使用的資源約束的MPS是一個NPplete[4][5]提出了比較完整的求解PS的串行和并行的理論和方法,Kolisch[6]等人給出了求解PS的局部搜索算法,Reych[7]采用了分支定界方法對PS進行求解,Fayez[8]和Taeho[9]等人對MPS進行了研究,并給出了啟發(fā)式求解方法,Joanna[10],對企業(yè)來說,成本也是一個重要的經(jīng)營目標,因此對以成本為目標的PS的研究同樣具有重要意義.根據(jù)病毒進化理論[11],病毒是一種特有的生物,具有一種特有的感染功能,它能獲得一個個體的染色體基因,并且感染給另一個個體,使得該個體的部分染色體基因發(fā)生相應(yīng)的變化,從而改變該個體的遺傳信息,這種遺傳信息又通過遺傳傳遞給下一代,Kubota提出了基于病毒進化理論的遺傳算法VEGA(virus coevolution genetic algorithm),并成功地用于求解旅行商問題[11]、自組織制造系統(tǒng)的調(diào)度問題[12]、彈道規(guī)劃問題[13]、背包問題[14]等,:,進行GA的遺傳操作,在上下代群體之間縱向傳遞進化基因,在同代個體之間橫向傳遞進化基因,實施解空間的局部搜索,VEGA將主群體的全局進化和病毒群體的局部進化進行動態(tài)結(jié)合,(multimode project schedulingvirus coevolution genetic algorithm).1 問題描述一個MPS可以描述為:活動集,0和分別表示虛擬的起始活動和結(jié)束活動。199。(4) ,稱為v按w裁剪.顯然,向量的這兩種運算和集合對應(yīng)的運算不同在于:向量運算后仍然是一個向量,且各分量仍然保持在運算前原向量中的偏序關(guān)系,因此向量的這兩種運算的意義是在交叉操作過程中保持活動之間的次序約束關(guān)系,通過交叉操作產(chǎn)生MPS活動的一個最優(yōu)的調(diào)度順序.2 病毒協(xié)同進化遺傳算法MPSVEGA 染色體編碼方案 主個體染色體編碼主個體(host)染色體編碼由兩部分組成:.J表示MPS活動的一個調(diào)度順序,M表示MPS活動對應(yīng)的資源模式向量,采用串行調(diào)度算法[5],活動的開始時間向量S不難惟一確定,因此每個染色體惟一地對應(yīng)了一個調(diào)度. 病毒個體染色體編碼由于模式向量M確定了項目的成本,(virus)編碼為.,是模式向量M的子串,串中包含通配符*,通配符*,有效字符表示一個活動的具體資源模式,. 適應(yīng)度 主個體的適應(yīng)度函數(shù)主個體I的適應(yīng)度函數(shù)為,其中,和分別是染色體I對應(yīng)的項目成本和項目工期,B和T分別是項目的最大成本和最長工期,為模式向量M對資源υ的超出額度:,其中.由于,因此適應(yīng)度可以保證在目標成本大小相差不大的情況下選擇時間較優(yōu)的調(diào)度,(包括活動的調(diào)度順序J和資源模式向量M)的優(yōu)劣程度,其中項目工期由活動的調(diào)度順序J惟一確定(由串行調(diào)度算法[5]確定各個活動的開始時間(項目工期)),因此它體現(xiàn)了調(diào)度順序J的優(yōu)劣程度,而直接體現(xiàn)了資源模式向量M的優(yōu)劣程度. 病毒個體的適應(yīng)度函數(shù)一個病毒個體可以感染若干個主個體,U中主個體l被感染前后的適應(yīng)度函數(shù)分別表示為和,則病毒i的適應(yīng)度函數(shù)為.U中的一個主個體l表示的是MPS解空間中的一個解,其適應(yīng)度體現(xiàn)了解的優(yōu)劣程度,因此,病毒個體的適應(yīng)度體現(xiàn)了部分活動的模式對MPS解空間中的多個解的進化計算效果.病毒的生存時間用生命力(life)來表現(xiàn),第代的病毒個體i的生命力表示如下:,其中g(shù)為生命力遞減率,如果,說明該部分活動的模式已不能對MPS的解產(chǎn)生進化效果,則需要產(chǎn)生MPS新的部分活動的模式. 進化操作 主個體的遺傳操作GA初始群體的產(chǎn)生(initialization):通過以下步驟產(chǎn)生規(guī)模為偶數(shù)的初始群體hostpop(t).首先,為每個活動選擇模式,為所有模式中消耗資源υ數(shù)量最少的一種,從而生成一個資源υ可行的第1個模式向量。Mutation: 由crosshostpop(t+1)產(chǎn)生muthostpop(t+1),計算每個主個體j的適應(yīng)度。計算lifei,t+1。增加病毒群體的規(guī)模有助于搜索到MPS的最優(yōu)解,對于MPS,當參數(shù)取值為=/10,=, VEGA能以較快的速度產(chǎn)生最優(yōu)的調(diào)度順序和資源模式. Curves of avg. gen changing with N圖6 平均計算代數(shù)隨N變化的曲線 Curves of avg. sec changing with N圖5 平均計算時間隨N變化的曲線 Curves of avg. opt changing with N圖7 平均最優(yōu)值隨N變化的曲線 Effects of virus population size and max infection rate圖8 病毒群體大小和最大感染概率的影響POPvirus4 結(jié) 論本文對于一種以成本為優(yōu)化目標的多模式項目調(diào)度問題MPS進行了研究,提出了這一問題的優(yōu)化模型,從而能以很好的收斂速度求得MPS的最優(yōu)解,MPSVEGA的收斂速度、,同時對于研究不同優(yōu)化目標的MPS具有一定的理論貢獻和實際應(yīng)用價值.References:[1] Sprecher A, Kolisch R, Drexl A. SemiActive, active, and nondelay schedules for the resourceconstrained project scheduling problem. European Journal of Operational Research, 1995,80(1):94~102.[2] Nudtasomboon N, Randhawa SU. ResourceConstrained project scheduling with renewable and nonrenewable resources and timeresource tradeoffs. Comp
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1