[發明專利]使用基于MapReduce的蟻群優化技術求解組合優化問題的方法

無效

• 申請號: 201210433343.8
• 申請日: 2012-11-02
• 公開（公告）號: CN102982389A
• 公開（公告）日: 2013-03-20
• 發明（設計）人: 吳剛;吳碧晗;王巖冰;楊夢東;劉翔宇;漆桂林
• 申請（專利權）人: 東南大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

1.使用基于MapReduce的蟻群優化技術求解組合優化問題的方法，其特征在于，包括以下步驟：?

1）根據設定的mapper的數量劃分指定組合優化問題的解空間；?

2）Map階段，每個mapper獨立并行地在步驟1)劃分得到的子問題解空間中執行改進的蟻群算法，搜索局部最優解；?

3）Reduce階段，reducer接受所有mapper在不同解空間搜索到的局部最優解，根據步驟1)中采用的解空間劃分情況綜合得到全局最優解；?

4）輸出reducer當前得到的全局最優解，結束。?

2.根據權利要求1所述的使用基于MapReduce的蟻群優化技術求解組合優化問題的方法，其特征在于，步驟1），具體為：分析指定組合優化問題的解空間類型，并根據設定的mapper數量劃分解空間，令每個mapper分別在不同的子空間內搜索局部問題的解；其中，所述的問題的解空間是指：設問題的解向量為x=(x₁，x₂，…,x_i…,x_n)，x_i的取值范圍為有窮集S,把x的所有可能取值組合稱為問題的解空間，i、n均為自然數；每一個組合是問題的一個可能解；可行解是滿足約束條件的解，是解空間中的一個子集；最優解是使目標函數取極值的可行解；解空間組織成子集樹或排列樹形式。?

3.根據權利要求1所述的使用基于MapReduce的蟻群優化技術求解組合優化問題的方法，其特征在于，步驟2），即MapReduce的Map函數，其中，所述的改進的蟻群算法，具體包括如下步驟：?

①根據步驟1)劃分得到的子問題規模選擇螞蟻數和迭代次數，初始化個體的信息素值和待選個體集，具體設置如下：?

假設子問題規模為n_i（i∈[0,m-1]），則對于解空間為子集樹的問題，設置所需螞蟻數a_i=n_i/100+1，所需迭代次數l_i=n_i/10+1；對于解空間為排列樹的問題，設置所需螞蟻數a_i=n_i，所需迭代次數l_i=10n_i；初始化每個個體的信息素值為τ_ij(0)=0.5(j∈[0,n_i-1]）；初始化待選個體集C_i為子問題所包含的所有個體S_i；?

②設置待選個體集中每個個體的被選擇概率，每個螞蟻根據該值隨機選擇個體，具體方法如下：?

設置每個個體被選擇概率為k∈C_i；?

③其中每個物品的被選到的概率只與在其上的信息素有關，剛開始時初始化為0.5表示每個物品被選到與沒選到的概率是一樣的；這樣每只螞蟻生成的物品集完全是獨立且隨機的，直到根據物品價值與重量比的好壞更新信息素來影響物品的選擇；比較所有螞蟻在步驟②中通過選擇個體生成的解，從中選擇局部最優解對應的螞蟻b，為自然數，用該局部最優螞蟻生成的解更新相應個體的信息素，τ_i(t+1)=(1-ρ)τ_i(t)+Δτ^b，而其它個體信息素值不更新；?

其中，t為迭代次數，0<ρ＜1是信息素蒸發系數；0<Δτ^b1是個體b信息素的增量；?

④當滿足終止條件時，輸出當前mapper執行過程中保存的局部信息素向量，否則轉步驟②。?

4.根據權利要求1所述的使用基于MapReduce的蟻群優化技術求解組合優化問題的方法，其特征在于，步驟3）即MapReduce的Reduce函數，其功能是當所有mapper運行完對子問題的搜索后，將解傳遞到reducer后，使reducer根據步驟1)中采用的解空間劃分的具體情況來綜合得到全局最優解；其中，所述的根據步驟1)中采用的解空間劃分的具體情況來綜合得到全局最優解，具體分為如下兩種情況：?

當問題的解空間是子集樹時，集合S中的n個元素被均勻分配給m個mapper中，采用將各mapper中得到的部分個體的信息素值進行合并得到集合S中全部個體的信息素值，進而按照步驟2)中所采用的改進的蟻群算法②~④計算全局最優解，所不同的有兩處，一是每個個體被選擇概率為實數α和β分別用于控制信息素濃度τ_ij和啟發式因子η_i(j)對生成個體選擇概率P_ij的影響程度，缺省?情況下設置α=β=1，其中，啟發式因子η_i(j)是預先設置的對個體選擇性的先驗知識，是問題相關的；每只螞蟻從待選個體C_i中根據個體被選擇概率P_ij按輪盤賭選擇算法隨機選擇個體；?

另一個是信息素更新公式，Δτ^ijb=Tσ，即增量平衡系數T與增量步進值σ之積；T和σ根據具體問題不同而分別設置經驗值；?

當問題的解空間按是排列樹時，由于集合S中所有n個元素的n!個不同排列被均勻分配給m個mapper的方法，因此簡單比較各mapper中得到的局部最優解，選擇其中的最優解作為當前計算得到的最優解。?