項目優(yōu)化調(diào)度的病毒協(xié)同進化遺傳算法doc(編輯修改稿)
2024-08-14 16:22 本頁面
【文章內(nèi)容簡介】 ()表示()中活動對應的模式,()表示()中活動對應的模式,則和產(chǎn)生的兩個子代個體分別是,.交叉操作的作用是,在MPS的解空間中隨機產(chǎn)生活動的新的調(diào)度順序和資源模式.變異(mutation):設表示活動的所有前行活動的集合,對于每個活動,如果,則以概率發(fā)生變異:和換位。每個模式以概率發(fā)生變異:從中隨機選擇一個模式替換.變異操作使得MPS活動的部分調(diào)度順序和資源模式發(fā)生變化從而產(chǎn)生活動的新的調(diào)度順序和資源模式.選擇(selection):為了使當前最優(yōu)解保持下去,采用排序法(ranking)[16],即對遺傳操作前后的所有個體按適應度值進行排序,使最優(yōu)的個體保持下去.選擇的作用是,從MPS已有的解集中選擇出較優(yōu)的調(diào)度順序和資源模式. 病毒個體的進化操作VE病毒感染(virus_infection):利用病毒染色體基因替換主染色體中相應的模式基因,從而產(chǎn)生新的主個體,如果某主個體感染后的適應度減小了,病毒感染操作的作用在于,用部分活動的資源模式替換MPS的多個解的活動的資源模式,如果替換后的解優(yōu)于替換前的解,則用替換后的解代替替換前的解.復制(copy):隨機選擇一個主個體,主染色體每個模式基因以概率代換病毒染色體中相應基因,從而產(chǎn)生新的有效字符更多的病毒個體,即通過一個主染色體以概率復制到一個“無感染能力(infectless)”的病毒個體,用MPS一個解的部分活動的資源模式替換已有的一個部分活動的資源模式,從而增加其進化計算能力,或者產(chǎn)生一個新的部分活動的資源模式.刪減(cut):病毒染色體每個基因以概率用通配符代換,減少一個已有的一個部分活動的資源模式的數(shù)量,從而降低其進化計算能力. Copy operator for virus圖2 病毒復制操作Host:Virus:CopyVirus_Infection Virus_Infection operator圖1 病毒感染操作Host:Virus: Copy operator for initial virus圖3 初始病毒復制操作Host:Virus:Copy Cut operator for virus圖4 病毒刪減操作CutVirus: 病毒進化遺傳算法MPSVEGAMPSVEGA可以描述如下:參數(shù)初始化: ,,,g 。群體初始化: 執(zhí)行Initialization操作產(chǎn)生個個體j的初始主群體hostpop(t),計算。執(zhí)行Copy操作產(chǎn)生個個體i的初始病毒群體viruspop(t),初始化相關參數(shù),ai,t:=0,lifei,t:=0。//以下步驟執(zhí)行GA操作.Crossover: 由hostpop(t)產(chǎn)生crosshostpop(t+1)。Mutation: 由crosshostpop(t+1)產(chǎn)生muthostpop(t+1),計算每個主個體j的適應度。Selection: 由hostpop(t)200。muthostpop(t+1)產(chǎn)生個個體的hostpop(t+1)。//以下步驟執(zhí)行病毒的進化操作VE,對viruspop(t)中每個病毒個體i執(zhí)行以下操作. Virus_Infection: 病毒個體i以概率感染hostpop(t+1)中每個主個體,記hostpop(t+1)中被病毒i感染后的子群體為U。計算U中每個個體l的適應度,如果,則用個體l替換hostpop(t+1)中相應的個體。計算和ai,t+1:=ai,t。Copy或Cut: 如果,則從U中隨機選擇一個主個體對病毒個體i執(zhí)行Copy操作。否則對病毒個體i執(zhí)行Cut操作,將病毒個體i記入viruspop(t+1)。計算lifei,t+1。產(chǎn)生新病毒: 如果lifei,t+10,則從hostpop(t+1)中隨機選擇一個主個體執(zhí)行Copy操作,產(chǎn)生新的病毒個體,替換viruspop(t+1)中的病毒個體i,并初始化相關參數(shù),。結束條件: ,若滿足停止條件,則從hostpop(t)中選擇適應度最小的個體進行解碼得到最優(yōu)解.MPSVEGA由GA和VE兩部分組成,GA進行MPS最優(yōu)解(包括活動的調(diào)度順序和資源模式)的全局搜索,通過Crossover和Mutation在MPS的全局解空間中隨機搜索活動的調(diào)度順序和資源模式,通過Selection產(chǎn)生MPS解空間中較優(yōu)的調(diào)度順序和資源模式。VE進行MPS最優(yōu)解的局部搜索,通過Virus_Infection在MPS的解空間中產(chǎn)生多個部分活動具有相同的較優(yōu)資源模式的解(包括活動的調(diào)度順序和資源模式),通過Copy可以增加這些解中具有相同較優(yōu)資源模式的活動的數(shù)目,如果調(diào)度順序和資源模式較優(yōu),則通過Copy逐漸加速它的產(chǎn)生過程。如果非優(yōu),則通過Cut逐漸減緩它的產(chǎn)生過程,因此相對于GA,VEGA可以極大地加快MPS的最優(yōu)調(diào)度順序和資源模式的產(chǎn)生過程. 病毒進化遺傳算法的性能分析模板理論是分析進化算法性能的一種重要方法,病毒進化遺傳算法在本質上也是一種進化算法,因此其進化計算的速度在于以較快的速度產(chǎn)生較多的模板的期望個數(shù).首先定義主個體I的另一種適應度函數(shù)如下:.這樣每個主個體就可以采用輪盤賭方式進行選擇,由病毒個體的編碼方法可知,一個病毒個體實質上表示的是一個模板(Schema).設表示在群體hostpop(t)中具有模板的主個體的集合,經(jīng)過GA的進化計算后,在hostpop(t+1)中具有模板的主個體的期望數(shù)[16]為,其中,表示所包含的主個體數(shù),即,如果再通過病毒進行進化計算后,則在hostpop(t+1)中具有模板的主個體的期望數(shù)為.由于,所以,.這就是說,VEGA能夠比GA以更快的速度產(chǎn)生較多的模板的期望個數(shù).3 實驗結果隨機產(chǎn)生活動個數(shù)依次為N=10,20,30,40,50,60,70,80,90,100的MPS問題10個,對每個問題又隨機生成10個實例,對這100個實例分別進行GA,VE和VEGA的計算,采用3種指標評價它們的算法性能:每個問題的10個實例
環(huán)評公示相關推薦
鄂ICP備17016276號-1