[發(fā)明專利]一種基于多層遺傳算法的冰壺比賽對(duì)陣組合設(shè)計(jì)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201510727233.6
• 申請(qǐng)日: 2015-10-30
• 公開（公告）號(hào): CN105184428A
• 公開（公告）日: 2015-12-23
• 發(fā)明（設(shè)計(jì)）人: 董紅斌;丁蕊;張丹;邢薇;印桂生;孔飛;劉文杰;張萬松
• 申請(qǐng)（專利權(quán)）人: 哈爾濱工程大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于多層遺傳算法的冰壺比賽對(duì)陣組合設(shè)計(jì)方法，其特征在于：

(1)編碼：使用固定長度的十進(jìn)制整數(shù)進(jìn)行編碼，表示群體中的個(gè)體；冰壺參數(shù)隊(duì)伍集合A＝{a₁,a₂,a₃,…a_n}；賽道集合R＝{r₁,r₂,r₃,…r_m}；比賽輪次集合T＝{t₁,t₂,t₃,…t_k}；其中a∈N₊,r∈N₊,t∈N₊；小組賽時(shí)小組集合H＝{h1,h2,…h(huán)p}，其中的元素如h1也是一個(gè)集合，包含隊(duì)伍集合A中的元素.隊(duì)伍對(duì)陣集合C＝{(x,y)|x∈A,y∈A,x≠y}；C中的元素稱為基因，共有n*(n-1)/2個(gè)基因；個(gè)體Xi表現(xiàn)為一串長為len＝n×(n-1)的整數(shù)，包含C中的全部元素；每m個(gè)C中的元素稱為一輪，共有k輪；

(2)初始種群生成；在滿足約束條件下隨機(jī)生成包含popsize個(gè)個(gè)體的初始種群，約束條件為包含C中的所有對(duì)陣對(duì)且僅包含一次；一個(gè)整數(shù)編碼的個(gè)體就是由所有對(duì)陣組合組成的一種冰壺比賽的對(duì)陣的完整方案；通過將C中所有的元素隨機(jī)排列來生成個(gè)體X_i，popsize個(gè)這樣的初始個(gè)體組成初始種群，popsize為種群大?。?/p>

(3)根據(jù)適應(yīng)度函數(shù)計(jì)算種群內(nèi)每個(gè)個(gè)體的適應(yīng)度函數(shù)值fit(X_i)；冰壺問題的每一個(gè)約束條件都抽象為一個(gè)適應(yīng)度函數(shù)分量fit_j(X_i)，j∈D,D為約束條件集合；多個(gè)約束條件就有多個(gè)適應(yīng)度函數(shù)分量，這些適應(yīng)度函數(shù)分量通過加權(quán)求和的方式組成算法最后的適應(yīng)度函數(shù)fit(x)=Σi=17wifi(x);]]>

(4)在每一代中，根據(jù)適應(yīng)度函數(shù)值的大小，分別對(duì)每一個(gè)個(gè)體進(jìn)行分層優(yōu)化：

第一層優(yōu)化使用靶向自交叉算子，逐個(gè)檢查個(gè)體中的基因(x,y)是否滿足一個(gè)隊(duì)伍不能同時(shí)參加同一輪次中的兩場(chǎng)比賽的約束；此約束記為B₁；b₁＝a_nt_k，其中N是參賽隊(duì)伍數(shù),K是比賽輪次數(shù)；

如果該約束尚不滿足，記錄不滿足的基因的位置，并將其值變異成當(dāng)前輪中沒出現(xiàn)的隊(duì)伍代表的整數(shù)，成為新的基因值；查找新基因值原來在個(gè)體中的基因位置，將原基因值與新基因值原來所在的位置互換，實(shí)現(xiàn)確定位置的二個(gè)基因位的值之間的交換；同一時(shí)間進(jìn)行的比賽稱為一輪比賽；

第二層優(yōu)化使用定點(diǎn)-隨機(jī)自交叉；逐個(gè)檢查個(gè)體中的基因是否滿足其他約束條件，如果不滿足，確定不滿足的基因的位置及原因，找到經(jīng)過同輪基因間交換可以滿足約束條件的基因及位置，隨機(jī)選擇其中的一個(gè)與原來不滿足約束條件的基因值進(jìn)行互換以實(shí)現(xiàn)交叉；此時(shí)的其他約束條件包括：

平均分配場(chǎng)地，參賽隊(duì)在賽道分配上具有相同的比例，記為B₂；

b₂＝a_nr_m其中M是賽道數(shù)量，N是所有參賽隊(duì)伍數(shù)量，假設(shè)a_n所在的小組內(nèi)有n₁個(gè)參賽隊(duì)伍；

參賽隊(duì)不應(yīng)在同一賽道連續(xù)比賽兩場(chǎng)，以免形成某個(gè)隊(duì)伍擁有主場(chǎng)優(yōu)勢(shì)，記為B₃；

b₃＝a_nt_k1r_m1t_k2,其中N是參賽隊(duì)伍數(shù)量，K是比賽輪次數(shù)，M是賽道數(shù)量；

各個(gè)小組的比賽場(chǎng)次在每個(gè)賽道均勻分布，記為B4；b₄＝h_pr_m,其中P是小組個(gè)數(shù)，M是賽道數(shù)量，h_p小組內(nèi)有n₁個(gè)參賽隊(duì)伍；

深淺壺次數(shù)均衡，記為B5；

f1(x)=Σm=1MrmC1;]]>

f2(x)=Σm=1MrmC2]]>

其中M是賽道數(shù)量，C1格式為{(x,y1),(x,y2)…(x,yn-1)}；C2格式為{(y1,x),(y2,x)…(yn-1,x)}；r_mC1表示C1集合內(nèi)的隊(duì)伍對(duì)陣方式在r_m賽道中的個(gè)數(shù)；r_mC2表示C2集合內(nèi)的隊(duì)伍對(duì)陣方式在r_m賽道中的個(gè)數(shù)；

B5=Σn=1Nf1(an)f2(an)]]>其中N是參賽隊(duì)伍數(shù)量；

同一隊(duì)伍不得在同一賽道連續(xù)使用同色壺，記為B6；

B6=Σn=1NΣm=1MΣk1=1KΣk2=k1+1xb6,b6=anrmtk1tk2C1C2]]>

其中N是參賽隊(duì)伍數(shù)量，M是賽道數(shù)量，K是比賽輪次數(shù)，C₁∈C,C₂∈C，C₁格式為{(x,y₁),(x,y₂)…(x,y_n-1)}，C₂格式為{(y₁,x),(y₂,x)…(y_n-1,x)}；

(5)混合選擇策略選擇個(gè)體成為下一代；計(jì)算經(jīng)過二層優(yōu)化后產(chǎn)生的個(gè)體的適應(yīng)度值；根據(jù)適應(yīng)度值，采用混合選擇算子跨代選取個(gè)體進(jìn)入下一代；混合選擇算子是指將精英選擇與錦標(biāo)賽選擇相結(jié)合；將第4步中優(yōu)化前的個(gè)體和優(yōu)化后的個(gè)體放在一起，對(duì)于所有個(gè)體，如果fit(X_i)<gate,則稱為精英個(gè)體將其保留，gate為算法指定的閾值；統(tǒng)計(jì)精英個(gè)體的數(shù)目Num，使0≤Num≤popsize*3/5；對(duì)于剩下的沒有精英保留的個(gè)體，則實(shí)行父代與子代間的錦標(biāo)賽跨代選擇方式進(jìn)行個(gè)體的保留；以此混合選擇算子跨代選取個(gè)體進(jìn)入下一代；

(6)判斷算法是否滿足預(yù)設(shè)條件；在新一代種群中，記錄下最優(yōu)個(gè)體的適應(yīng)度函數(shù)值，判斷算法是否達(dá)到最大迭代次數(shù)或滿足最優(yōu)解的預(yù)設(shè)條件，如果滿足最優(yōu)解的條件，則執(zhí)行步驟7，如果達(dá)到最大迭代次數(shù)，則執(zhí)行步驟8；如果算法沒有滿足以上二個(gè)預(yù)設(shè)條件中的任何一個(gè)，則算法轉(zhuǎn)到第3步，重復(fù)第3、4、5、6步；

(7)找到最優(yōu)解決方案，算法停止并輸出適應(yīng)度值滿足預(yù)設(shè)條件的個(gè)體，這個(gè)個(gè)體就是滿足指定約束條件的一組比賽對(duì)陣組合；

(8)多層遺傳優(yōu)化；保留當(dāng)前種群中適應(yīng)度值小于閾值gate的精英個(gè)體；對(duì)種群進(jìn)行部分個(gè)體的重置，轉(zhuǎn)到第3步開始下一層的遺傳算法優(yōu)化；個(gè)體重置是指按第2步的方法重新生成指定數(shù)目的個(gè)體；重置個(gè)體的數(shù)目由上一代的精英個(gè)體數(shù)量動(dòng)態(tài)決定；如果沒有滿足條件的精英個(gè)體，則重置個(gè)體的數(shù)目為初始種群大小，重置個(gè)體的最少數(shù)目為popsize*2/5。