[發明專利]一種基于煙花算法和遺傳算法的多目標排程方法

在審

• 申請號: 202110682625.0
• 申請日: 2021-06-18
• 公開（公告）號: CN113505974A
• 公開（公告）日: 2021-10-15
• 發明（設計）人: 馬開凱;祝耀;吳連秋
• 申請（專利權）人: 寧波沙塔信息技術有限公司
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12;G06Q50/04
• 代理公司: 寧波奧圣專利代理有限公司 33226
• 代理人: 程曉明

本發明公開了一種基于煙花算法和遺傳算法的多目標排程方法，特點是設定初始參數；生成初始種群，將初始種群作為當前種群開始迭代；計算當前種群的非支配解并判斷是否產生新的非支配解，若是，則將新的非支配解輸入至最優解集中；若不是，則判斷是否達到設定的迭代總數，若是，則輸出最優解集；若不是，則計算煙花規模得到煙花群；對煙花群進行煙花爆炸操、高斯變異操作；進行遺傳選擇；進行煙花選擇；進行種群交叉操作；進行種群變異操作，并將進行種群變異操作后的種群作為當前種群繼續迭代；優點是本發明結合了遺傳算法和煙花算法，具有收斂速度快、求解精度高的優點，從而有效地提高了多品種小批量生產模式下的排程效率和排程精度。

技術領域

本發明涉及生產排程技術領域，尤其是一種基于煙花算法和遺傳算法的多目標排程方法。

背景技術

隨著客戶需求日益多樣化，市場競爭愈加激烈，多品種小批量的生產方式逐漸流行起來；多品種小批量是指在一定工期內，需要生產的商品的種類很多，而每個商品種類需要生產的數量較少；多品種小批量的生產方式的復雜度較高，生產排程的難度也很大，這給生產排程帶來了極大的挑戰。

在多目標排程中，由于多品種小批量生產模式下，生產需求復雜多變，時常出現生產需求超出生產設備負荷的情況，因此需要求出多項指標最優的生產計劃，傳統的遺傳算法只能求得單項指標最優的生產計劃，不能有效求出多項指標最優的生產計劃；且現有的多目標排程方法在求解復雜的多目標排程問題時，求得的帕累托最優解集不夠全面，即求解精度還不夠高。

發明內容

本發明所要解決的技術問題是提供一種基于煙花算法和遺傳算法的多目標排程方法，不但提高了排程求解的精度，而且提高了排程求解的效率。

本發明解決上述技術問題所采用的技術方案為：一種基于煙花算法和遺傳算法的多目標排程方法，包括以下步驟：

S1設定初始參數，所述的初始參數包括精英規模H、種群規模G、變異次數、迭代總數和最優解集；

S2獲取多目標排程的多個優化目標，根據設定的種群規模，對多個優化目標采用二階段式的方法生成初始種群，將初始種群作為當前種群開始進行迭代；

S3計算當前種群中每個個體的帕累托強度值，將每個個體的帕累托強度值作為每個個體的適應值，并將帕累托強度值小于1的個體所對應的生產計劃作為當前種群的非支配解；

S4判斷是否產生新的當前種群的非支配解，若是，則將新的當前種群的非支配解輸入至最優解集中；若不是，則進入步驟S5；

S5判斷是否達到設定的迭代總數，若是，則終止并輸出最優解集；若不是，則進入步驟S6；

S6根據基于收斂情況的動態調節機制計算煙花規模，并記為f：

其中，c表示收斂指數，a表示預設的煙花規模開始隨著收斂指數增長的閾值，b表示預設的煙花規模的上限值；基于收斂情況的動態調節機制對收斂情況進行實時的監測，當算法正處于不斷優化的狀態時，則認為此時種群正在快速收斂，這時種群中的個體以遺傳算法得到的個體為主，使遺傳算法收斂速度快的特點充分得到發揮；當種群經過了一定次數的迭代后，對應的最優解集沒有進行更新，則認為目前種群處于一個局部最優的狀態，此時逐漸加大煙花爆炸在算法中的比重，使進入下一代種群的個體中，煙花爆炸得到的火花占比增加，以此來增加種群的多樣性，在引入了煙花算法的機制后，種群能夠及時地擺脫局部最優狀態的問題。

S7從當前種群中隨機選取f個個體作為煙花群；

S8對煙花群進行煙花爆炸操作，得到爆炸火花群；

S9對爆炸火花群進行高斯變異操作，得到高斯火花群，并將高斯火花群加入到爆炸火花群中，得到更新后的火花群；

S10根據設定的精英規模，采用精英保留結合錦標賽選擇的策略對當前種群進行遺傳選擇，得到下一代種群；