[發(fā)明專利]針對分離約束背包問題的一種協(xié)同的并行鄰域搜索方法

在審

• 申請?zhí)枺?/td>: 201711418903.1
• 申請日: 2017-12-25
• 公開（公告）號: CN108009013A
• 公開（公告）日: 2018-05-08
• 發(fā)明（設(shè)計）人: 全哲;葉婷;樂雨泉
• 申請（專利權(quán)）人: 湖南大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/54
• 代理公司: 深圳市興科達(dá)知識產(chǎn)權(quán)代理有限公司 44260
• 代理人: 王翀;賈慶

1.一種針對分離約束背包問題的一種協(xié)同的并行鄰域搜索方法，其特征在于，包括如下步驟：

步驟一、初始化：設(shè)置一個根線程和m個子線程，同時為根線程設(shè)置一個大小為n的解池，n<m，m為子線程數(shù)；子線程各自用LNS搜索得到自己的局部最優(yōu)解返回給根線程，初始化解池；

步驟二：協(xié)同搜索：根線程給每個子線程隨機(jī)分配一個解池中的解；

步驟三：獨(dú)立搜索：

1)子線程接收根線程分配來的解；

2)子線程使用PAMP算法搜索各自的局部最優(yōu)解；

步驟四：各子線程將自己的局部最優(yōu)解返回給根線程，根線程在各子線程反饋的局部最優(yōu)解與解池中原有的解中選取最優(yōu)的前n個解來更新解池，同時更新最優(yōu)解；

步驟五：重復(fù)步驟二、三、四，直到設(shè)置的時間到達(dá)，得到最終的最優(yōu)解。

2.如權(quán)利要求1所述的針對分離約束背包問題的一種協(xié)同的并行鄰域搜索方法，其特征在于，所述PAMP算法包括如下步驟：

步驟一、t子線程(t＝1,2,…m)接收從根線程傳來的解得到t子線程所找到的最佳局部解和根線程傳來的解之間的共同的項目的集合，使用LNS算法的移除過程從共同部分的集合中移除部分項目得到開始參照其中在使用LNS算法的移除操作從同部分的集合中移除部分項目的步驟中，我們在排序時使用了以下三種排序準(zhǔn)則：

2.1)根據(jù)pi/wi的值進(jìn)行升序排序；

2.2)根據(jù)reduced cost的值進(jìn)行降序排序；

2.3)根據(jù)reduced cost的值進(jìn)行升序排序；

根據(jù)這三種不同的排序準(zhǔn)則，我們得到三種不同的移除過程，也就是得到了三種不同的建立過程

隨機(jī)選擇三種排序準(zhǔn)則中的一種作為LNS算法移除過程的排序方法，以從同部分的集合中移除部分項目；

步驟二、將t子線程上次的解記為隨機(jī)選擇一個建立過程bt來從中移除不包含在中的項目，得到子線程t的開始解

步驟三、得到開始解之后，建立過程bt從建立一個鄰域然后調(diào)用禁忌搜索方法ts搜素鄰域禁忌搜索方法ts設(shè)置有禁忌表，用ISP表示前一次迭代得到的局部最優(yōu)解相關(guān)的獨(dú)立集，ISc表示當(dāng)前迭代所得到局部最優(yōu)解相關(guān)的獨(dú)立集；如果當(dāng)前的解比前一次的差，則比較ISp和ISc中的項目,在ISp和ISc不相同的的項目部分中隨機(jī)選擇25％加入到禁忌表，被加入到禁忌表中的項目將在之后的15次迭代中不能被搜索到。