[發(fā)明專利]一種改進(jìn)文化基因算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題

在審

• 申請?zhí)枺?/td>: 201610097447.4
• 申請日: 2016-02-22
• 公開（公告）號: CN106611379A
• 公開（公告）日: 2017-05-03
• 發(fā)明（設(shè)計(jì)）人: 湯琴;胡成華
• 申請（專利權(quán)）人: 四川用聯(lián)信息技術(shù)有限公司
• 主分類號: G06Q50/04
• 分類號: G06Q50/04;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種改進(jìn)文化基因算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題，該算法涉及作業(yè)車間調(diào)度技術(shù)領(lǐng)域，具體地涉及用算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題，其特征在于：該算法的步驟如下：

步驟1：對種群規(guī)模POP_SIZE、最大迭代次數(shù)、交叉和變異次數(shù)N、變異概率等參數(shù)進(jìn)行初始化；

步驟2：隨機(jī)生成POP_SIZE個(gè)個(gè)體作為初始種群，計(jì)算每個(gè)個(gè)體的適應(yīng)度，設(shè)置迭代次數(shù)t=0，并設(shè)置當(dāng)前種群=；

步驟3：對進(jìn)行適應(yīng)度排序，得到其中的非支配個(gè)體集合，并將非支配個(gè)體數(shù)設(shè)置為中的元素個(gè)數(shù)；

步驟4：將中的個(gè)體直接拷貝到下一代種群，設(shè)置的個(gè)體個(gè)數(shù)n=；

步驟5：在中隨機(jī)選擇一對個(gè)體：父代1和父代2；

步驟6：如果父代1、父代2的所有目標(biāo)函數(shù)值都相等，則轉(zhuǎn)步驟8；否則，

執(zhí)行下一步驟；

步驟7：分別以概率對父代1、父代2進(jìn)行變異，然后對父代1、父代2執(zhí)行

N次交叉操作產(chǎn)生包含有2N個(gè)元素的子代個(gè)體集合ChildPop，對ChildPop進(jìn)

行適應(yīng)度排序，在其Pareto前端集合中隨機(jī)選擇一個(gè)個(gè)體進(jìn)入新種群，

設(shè)置的個(gè)體個(gè)數(shù)n=n+1；

步驟8：如果nPOP_SIZE，轉(zhuǎn)步驟5；否則，執(zhí)行下一步驟；

步驟9：對種群中的每個(gè)個(gè)體執(zhí)行爬山法局部搜索，并用所得的局部最

優(yōu)解替換原個(gè)體；

步驟10：將和合并，選擇最好的POP_SIZE個(gè)個(gè)體組成新的；

步驟11：如果迭代次數(shù)t，則算法結(jié)束；否則，更新種群=,并設(shè)置迭代次數(shù)t=t+1,然后轉(zhuǎn)步驟3。

2.根據(jù)權(quán)利要求1所述的一種改進(jìn)文化基因算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題，其特征在于：所述步驟7交叉：本算法采用SPX交叉，過程如下：

（1）將工件集合隨機(jī)分成兩個(gè)非空集合和；

（2）設(shè)置子代個(gè)體的當(dāng)前元素小標(biāo)為1，如果第一個(gè)父代的第一個(gè)元素屬于 ，則子代個(gè)體的當(dāng)前元素賦值為第一個(gè)父代個(gè)體的第一個(gè)元素，且當(dāng)前元素下標(biāo)加1；

（3）如果第二個(gè)父代個(gè)體的第一個(gè)元素屬于，則子代個(gè)體的當(dāng)前元素下標(biāo)加1，以此類推，直到子代個(gè)體的所有元素均賦值；

（4）交換兩個(gè)非空集合和中的元素，重復(fù)以上步驟可以得到另一個(gè)子代

個(gè)體。

3.根據(jù)權(quán)利要求1所述的一種改進(jìn)文化基因算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題，其特征在于：所述步驟7變異：本算法以相等的概率從插入變異和替換變異兩種方法中隨機(jī)選擇一種對種群中的個(gè)體進(jìn)行變異，兩種變異如下：

（1）插入變異：在父代個(gè)體中隨機(jī)選取一個(gè)基因，將其插入到另一個(gè)隨機(jī)選取的基因之前；

(2)替換變異:在父代個(gè)體中，隨機(jī)選一段基因串，然后將其插入到一個(gè)隨機(jī)選取的基因之前。

4.根據(jù)權(quán)利要求1所述的一種改進(jìn)文化基因算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題，其特征在于：所述步驟9，本算法采用爬山法進(jìn)行局部搜索，既能夠跳出局部最優(yōu)得到更好的解，也能夠減少計(jì)算時(shí)間，具體如下：

對于優(yōu)化問題的一個(gè)解s，鄰域是指對s實(shí)施一個(gè)操作M后能夠得到的解的集合，用表示s的鄰域，則： ，步驟如下：

（1）選定一個(gè)當(dāng)前解s；

（2）按照鄰域結(jié)構(gòu)定義生成s的一個(gè)鄰域解集合；

（3）將中比s質(zhì)量差的解刪除得到改善解集合;

（4）計(jì)算中解的個(gè)數(shù)；

（5）如果不等于零，則從中按照一定控制策略選擇一個(gè)替換s，轉(zhuǎn)本步驟2；否則轉(zhuǎn)本步驟6

（6）算法結(jié)束；

本算法采用此爬山法進(jìn)行局部搜索之后，對所有鄰域解集合進(jìn)行非劣排序，在其Pareto前端集合中隨機(jī)選擇一個(gè)個(gè)體替換當(dāng)前解。