改進萬有引力算法在流水作業排序中的應用

王付宇 湯濤

摘要：針對萬有引力搜索算法在處理一些優化問題時比較容易出現早熟和搜索精度不高的缺點，通過引入變異思想和模擬退火思想，提出一種改進的萬有引力搜索算法，并用此算法對以加權總誤工最小為目標的流水作業排序優化問題進行分析，結果表明：改進后的萬有引力算法明顯優于傳統萬有引力算法。

關鍵詞：流水作業;排序;加權總誤SE;萬有引力算法

中圖分類號：TP301.6DOI：10.16375/j.cnki，cn45-1395/t，2020.02.011

0引言

流水作業排序被稱為一種經典的組合優化問題，假設用m臺機器加工n種零件，設加工每一種零件所需機器的次序是固定的，給出每臺機器加工各個工件所需要消耗的時間，以便于確定各個工件的最優加工順序，從而使適應度函數值達到最優，在排序中，機器數量很多的排序問題為NP完全問題，在制定生產計劃時，需思考用什么方法可以使產品進行有序的生產，從而降低時間和成本，為企業帶來效益，因此，流水作業排序問題的研究對于企業在市場競爭中占據有利地位具有重要的作用。

目前，許多學者將粒子群等智能算法以及其他創新方法應用于流水作業排序問題的求解。張壵等于2018年提出了一種基于遺傳鄰域的萬有引力算法對車間產品生產問題進行求解。

萬有引力搜索算法（GSA）是一種新型的群智能優化算法，與遺傳算法和粒子群算法一樣，都是通過粒子更新位置，從局部尋優逐漸尋得全局最優的方法，該算法擁有收斂速度快的特點，己用于解決生活、生產以及其他問題，但是在求解離散復雜組合優化問題時，依然有很多不足，因此，本文對萬有引力搜索算法進行了改進，在加權總誤工的模型基礎上，采用新型的群智能優化算法——離散的改進引力搜索算法對流水作業排序問題進行求解。

1流水作業排序問題

1.1問題描述

流水作業排序可以分為靜態排序和動態排序兩種，當所有工件都在排序生產之前就已經到達車間，可以一次性對它們進行加工排序安排，這種情況被稱為靜態排序問題;當所有工件是在生產過程中間斷到達車間，需要即興安排它們的加工順序，這種情況被稱為動態排序問題，本文研究的便是流水作業的靜態排序問題情況下，確定總加權誤工最小時流水作業中零件的加工順序。

1.2流水作業排序優化模型

假設條件：

1）排序之前，所有工件都已經到達，此時工件完工時間與流程時間相等，

2）同一個工件不可以同時在不同機器上進行加工。

3）工件在排序加工過程中，上一個工序完成后，立刻被送到下個工序加工。

4）不允許間斷，一個工件一旦開始加工，不能中途停止，一直到完工結束。

5）每個工序只在一臺機器上完成。

6）每臺機器同時只能加工一個工件。

根據以上所述可得模型為：

2改進萬有引力算法

萬有引力搜索算法（Gravitational SearchAlgorithm，GSA）是由伊朗克曼大學教授Esmat Rashedi等在2009年提出的群智能優化算法，GSA算法的產生是受到牛頓萬有引力定律的啟發，使種群粒子具有引力質量，其引力質量根據粒子的適應度計算出，基于牛頓萬有引力定律，粒子產生相互之間的吸引力，粒子間作用力和它們的質量成正比關系，和它們之間距離的平方成反比，粒子慣性質量越大，粒子間距離越小，則粒子間的相互作用力越大，粒子在吸引力的驅使下作相對運動，適應度值較大的粒子則其引力質量較大，適應度值較小的粒子則其引力質量較小，在相同力量下，質量大的粒子運動較慢，質量小的粒子運動較快，粒子逐漸收斂到最優位置，依此來達到尋優的目的，傳統的引力搜索算法只能解決連續型編碼問題，即便利用連續實數與離散實數之間的映射關系去編碼求解離散組合優化問題，尋優效果不佳;因此，本文對萬有引力算法做出了改進，從而使求解流水排序問題尋優效果更佳，

該算法借鑒了遺傳算法的變異，提出了一種以引力質量為概率的父代基因片段傳給子代的變異策略，將引力質量大的父代的優秀基因傳給子代，不僅如此，在粒子速度更新的時候，引入了粒子群算法的優點，使粒子有著向自身歷史最佳位置逼近的趨勢和有向群體或領域歷史最佳位置逼近的趨勢，將模擬退火算法與萬有引力算法相結合，以增強算法的局部搜索能力，避免陷入局部最優，通過改進的萬有引力算法有效地求解了流水作業排序問題，結果表明改進的萬有引力算法是可行的。

2.1編碼問題

傳統的萬有引力搜索算法只能解決連續型編碼問題的解，流水作業排序是離散型組合優化問題，所以本文借鑒了陳育興等求解TsP問題時的實數編碼規則，基于連續型數據，通過對隨機生成的連續型數據進行倒序排列，取倒序排列數據的行數作為離散型問題的初始解，萬有引力算法中一個位置即為一個解，表示為：

2.5改進引力算法求解問題步驟

Step1算法初始化，設定各個參數，初始溫度To=1000.種群規模size_pop=300.count=0.Go=100.a=20.降溫系數q=0.96.終止溫度T_end=0.001.

Step 2產生初始粒子群，計算適度值，并更新全局最佳Zbest與個體最佳gbest。

Step 3開始迭代，初始粒子速度為0.將群體里較差的三分之一個體去掉，以較優的三分之一粒子代替，計算群體里各個粒子引力質量m：（t）和慣性質量M（t）。

Step 4計算各個粒子的引力Fid（t）及加速度aid（t）。

Step 5根據速度更新公式更新速度，根據位置更新公式更新位置。

Step6根據父代慣性質量決定是否變異，超出邊界范圍的粒子位置，采用公式控制其在邊界范圍內波動。

Step7根據模擬退火Metropolis原則來接受新解，

Step8更新全局最佳Zbcst與個體最佳gbest，count=count+1.To=g×To。，

Step9判斷是否結束循環，若不結束，返回Step 3.若結束，輸出最優解及其加工序列，

3案例分析

以10個工件，5臺機器的流水作業生產作為案例來進行改進萬有引力算法的求解，Pij表示工件Ji在機器Mi上的加工時間如表1所示。

工件參數如表2所示，

設定粒子群規模為300.初始溫度為1000.終止溫度為0.001.降溫系數q為0.96.速度范圍為[-1.1]，粒子邊界為[-2.2]，初始速度為0.Go=100.a=20.使用matlabR2014b來進行編程，計算機處理器參數Intel（R）Core（TM）i7-1065G7@2.52GHz雙核處理器，RAM為8GB，Window8操作系統64位，

運行改進后的萬有引力算法GSGSA，得到的最優加工序列為2.1.10.6.4.5.3.9.7.8.目標函數最小值為66.75。

傳統的萬有引力算法GSA運行得到的加工序列為2.1.9.6.4.5.3.7.10.8.目標函數最小值為72.171.結果對比如表3所示。

4結論

基于最大完工時間，構造了以加權總誤工為目標函數的優化模型，傳統的萬有引力算法無法對離散型編碼問題求解，將模擬退火與引力算法相結合，增強其尋優效果，速度更新時，借鑒粒子群，使粒子有向最佳位置逼近的趨勢，在相同的配置下，通過改進后的引力算法對流水作業排序問題進行了求解，尋優效果優于原來的GSA算法。