[發明專利]一種基于多層遺傳算法的冰壺比賽對陣組合設計方法

在審

• 申請號: 201510727233.6
• 申請日: 2015-10-30
• 公開（公告）號: CN105184428A
• 公開（公告）日: 2015-12-23
• 發明（設計）人: 董紅斌;丁蕊;張丹;邢薇;印桂生;孔飛;劉文杰;張萬松
• 申請（專利權）人: 哈爾濱工程大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于計算機應用領域，具體涉及一種解決了冰壺比賽對陣組合自動設計方法中難于找到最優解問題的基于多層遺傳算法的冰壺比賽對陣組合設計方法。

背景技術

在本發明之前已經嘗試使用的技術方法包括：

傳統的枚舉法、貪心法

枚舉法是利用計算機運算速度快、精確度高的特點，對要解決問題的所有可能情況逐一檢驗，從中找出符合要求的答案，通過犧牲時間來換取答案的全面性。貪心算法是指在對問題求解時，總是做出在當前看來是最好的選擇，算法不從整體最優上加以考慮，尋找的僅是在某種意義上的局部最優解。嘗試使用枚舉法結合貪心算法進行冰壺比賽對陣組合的自動設計。在枚舉的過程中，通過對各種限制條件做剪枝，根據剪枝后的結果使用貪心算法找到在此基礎上的最優解，最終得出一個相對較好的解。但是由于冰壺比賽對陣安排問題的難度和算法自身的時間復雜度局限，該方法難以取得較優的比賽方案。其不足具體表現在：1、當隊數和賽道數略多的時候，跑不出可行結果，如12支隊伍6賽道；2、自動編排的輪數經常超出理論最佳輪數；3、深淺壺均衡分布效果不理想；4、同一隊不在一個場地連續使用2次同色壺的約束顧前顧不到后。這種枚舉法結合貪心算法的對陣組合自動設計方法不能滿足現實要求。

基本遺傳算法

遺傳算法是計算數學中用于解決最優化問題的搜索算法，是進化算法的一種。對于一個最優化問題，將一定數量的候選解(稱為個體)組成的種群向更好的解進化。通常進化從完全隨機的個體組成的初始種群開始，之后不斷迭代優化。在每一代中，整個種群中的個體適應度被評價，從當前種群中基于適應度值按某種選擇策略選擇多個個體，通過個體間的交叉和變異產生新的個體并形成新一代種群，在新一代種群中重復此前的優化過程，直到滿足算法終止條件。

在使用基本遺傳算法實現冰壺對陣組合設計的過程中，構建了冰壺比賽方案編排問題的數學模型，設計了染色體結構，明確了初始化種群的方法，構造了適應度函數，設計了選擇、交叉和變異三個遺傳操作并提出了改進策略，確定了算法的終止條件。但該方法仍存在一個致使的缺陷，即算法不是一定能找到最優解。由于遺傳算法自身的特點和冰壺比賽諸多約束的限制，導制該方法在最優解存在的情況下，也無法一定找到最優解。

目前為止，在冰壺比賽對陣組合的自動設計中僅嘗試了以上二種方法，效果都不理想，并且國內外并未有其它相關成果發表。

發明內容

本發明的目的是提出一種解決精典遺傳算法在解決冰壺比賽對陣組合自動設計中存在的難于找到最優解的不足的基于多層遺傳算法的冰壺比賽對陣組合設計方法

本發明的目的是這樣實現的：

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

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