[發明專利]一種基于改進的帝國競爭算法的智能排產算法

在審

• 申請號: 201810320429.7
• 申請日: 2018-04-11
• 公開（公告）號: CN110363368A
• 公開（公告）日: 2019-10-22
• 發明（設計）人: 王忠民;宋國豪;苑慶濤;藺偉;張恒山
• 申請（專利權）人: 西安郵電大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/04
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于改進的帝國競爭算法的智能排產方法，其特征在于，包括以下步驟：

步驟1: 參數設置，設置帝國競爭算法求解柔性作業車間調度問題的相關參數，包括：國家數量N_pop、帝國主義國家數量N_imp、殖民地國家數量N_col、迭代次數N_iter；

步驟2：初始化國家個體，每一個國家代表一組生產排產調度問題的可行方案，隨機產生N_pop個體；

步驟3：通過代價函數，計算每個國家的代價函數值；

步驟4：產生帝國主義國家和殖民地國家，按照每個國家的代價函數值計算每個國家的勢力大小，依據之前設定的帝國主義國家數量，從中選取勢力較大的前N_imp個國家作為帝國主義國家，剩下的N_col個國家作為這些帝國的殖民地，相應的帝國和殖民地組成一個帝國集團；

步驟5：帝國內部進行同化操作，帝國內部的殖民地國家與帝國主義國家之間進行同化操作，使得殖民地國家不斷向帝國主義國家移動；

步驟6：帝國內部判斷是否更換帝國主義國家，當殖民地向帝國移動的過程中，它的勢力可能會比其所屬帝國的勢力更大，在這種情況下，交換帝國和殖民地的位置；

步驟7：帝國之間的競爭操作，勢力最強的帝國占有勢力最弱的帝國中的殖民地，使得強大的帝國更加強大，弱小的帝國更加弱小；

步驟8：殖民地改革操作，帝國內部的殖民地國家為防止同化作用造成過早收斂，需要進行革命操作；

步驟9：帝國消除操作，帝國之間的競爭，勢力較大的帝國通過占有其他帝國的殖民地變得日益強大，而勢力較小的帝國其殖民地個數卻不斷減少，當沒有殖民地時，保留該個體并將其歸屬于占有它最后一個殖民地的帝國；

步驟10：重新計算每個國家的代價函數值；

步驟11：判斷算法是否終止，算法不斷迭代，當只存在一個帝國或者達到迭代次數時，算法結束；反之，算法還沒有終止，則回到步驟5繼續執行。

2.如權利要求1所述的一種基于改進的帝國競爭算法的智能排產方法，其特征是，所述步驟5中的帝國內部進行同化操作：借鑒遺傳算法中的交叉和變異操作，實現了殖民地向帝國的移動，以及移動過程中的偏移；采用如下所示的兩點交叉方法,隨機的選擇兩個基因片段并交換它們的位置。

3.如權利要求1所述的一種基于改進的帝國競爭算法的智能排產方法，其特征是，所述步驟8中的殖民地改革操作：表現為隨機選取殖民地兩個位置的編號進行交換；在避免無效隨機搜索的同時, 能夠充分發揮革命機制保持種群多樣性功能, 從運算代數和所屬帝國權力兩方面對革命概率P_minp建立調節公式：

(1)

其中：P_minp為殖民地所屬殖民國家的標準化勢力，p_max 為所有殖民國家中最大的標準化勢力：n 為當前運算迭代次數，N_iter 為總共迭代次數， 默認p₀= 0.3 ；對于權力越小的殖民國家，該帝國內所有殖民地革命的概率越大， 這可以促進解的不斷優化。

4.如權利要求1所述的一種基于改進的帝國競爭算法的智能排產方法，其特征是，所述步驟9中的帝國消除操作：帝國之間的競爭，勢力較大的帝國通過占有其他帝國的殖民地變得日益強大，而勢力較小的帝國其殖民地個數卻不斷減少；當一個帝國失去所有的殖民地時，消除該帝國；然而這樣就損失了優勢個體，不利于算法收斂，由于該帝國個體優于一般殖民地國家，因此保留該個體并將其歸屬于占有它最后一個殖民地的帝國；保留較優個體，使得進化過程中能夠找到更優解。