王付宇 湯濤

摘要：針對(duì)萬(wàn)有引力搜索算法在處理一些優(yōu)化問(wèn)題時(shí)比較容易出現(xiàn)早熟和搜索精度不高的缺點(diǎn)，通過(guò)引入變異思想和模擬退火思想，提出一種改進(jìn)的萬(wàn)有引力搜索算法，并用此算法對(duì)以加權(quán)總誤工最小為目標(biāo)的流水作業(yè)排序優(yōu)化問(wèn)題進(jìn)行分析，結(jié)果表明：改進(jìn)后的萬(wàn)有引力算法明顯優(yōu)于傳統(tǒng)萬(wàn)有引力算法。

關(guān)鍵詞：流水作業(yè);排序;加權(quán)總誤SE;萬(wàn)有引力算法

中圖分類(lèi)號(hào)：TP301.6DOI：10.16375/j.cnki，cn45-1395/t，2020.02.011

0引言

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

目前，許多學(xué)者將粒子群等智能算法以及其他創(chuàng)新方法應(yīng)用于流水作業(yè)排序問(wèn)題的求解。張壵等于2018年提出了一種基于遺傳鄰域的萬(wàn)有引力算法對(duì)車(chē)間產(chǎn)品生產(chǎn)問(wèn)題進(jìn)行求解。

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

1流水作業(yè)排序問(wèn)題

1.1問(wèn)題描述

流水作業(yè)排序可以分為靜態(tài)排序和動(dòng)態(tài)排序兩種，當(dāng)所有工件都在排序生產(chǎn)之前就已經(jīng)到達(dá)車(chē)間，可以一次性對(duì)它們進(jìn)行加工排序安排，這種情況被稱(chēng)為靜態(tài)排序問(wèn)題;當(dāng)所有工件是在生產(chǎn)過(guò)程中間斷到達(dá)車(chē)間，需要即興安排它們的加工順序，這種情況被稱(chēng)為動(dòng)態(tài)排序問(wèn)題，本文研究的便是流水作業(yè)的靜態(tài)排序問(wèn)題情況下，確定總加權(quán)誤工最小時(shí)流水作業(yè)中零件的加工順序。

1.2流水作業(yè)排序優(yōu)化模型

假設(shè)條件：

1）排序之前，所有工件都已經(jīng)到達(dá)，此時(shí)工件完工時(shí)間與流程時(shí)間相等，

2）同一個(gè)工件不可以同時(shí)在不同機(jī)器上進(jìn)行加工。

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

4）不允許間斷，一個(gè)工件一旦開(kāi)始加工，不能中途停止，一直到完工結(jié)束。

5）每個(gè)工序只在一臺(tái)機(jī)器上完成。

6）每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件。

根據(jù)以上所述可得模型為：

2改進(jìn)萬(wàn)有引力算法

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

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

2.1編碼問(wèn)題

傳統(tǒng)的萬(wàn)有引力搜索算法只能解決連續(xù)型編碼問(wèn)題的解，流水作業(yè)排序是離散型組合優(yōu)化問(wèn)題，所以本文借鑒了陳育興等求解TsP問(wèn)題時(shí)的實(shí)數(shù)編碼規(guī)則，基于連續(xù)型數(shù)據(jù)，通過(guò)對(duì)隨機(jī)生成的連續(xù)型數(shù)據(jù)進(jìn)行倒序排列，取倒序排列數(shù)據(jù)的行數(shù)作為離散型問(wèn)題的初始解，萬(wàn)有引力算法中一個(gè)位置即為一個(gè)解，表示為：

2.5改進(jìn)引力算法求解問(wèn)題步驟

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

Step 2產(chǎn)生初始粒子群，計(jì)算適度值，并更新全局最佳Zbest與個(gè)體最佳gbest。

Step 3開(kāi)始迭代，初始粒子速度為0.將群體里較差的三分之一個(gè)體去掉，以較優(yōu)的三分之一粒子代替，計(jì)算群體里各個(gè)粒子引力質(zhì)量m：（t）和慣性質(zhì)量M（t）。

Step 4計(jì)算各個(gè)粒子的引力Fid（t）及加速度aid（t）。

Step 5根據(jù)速度更新公式更新速度，根據(jù)位置更新公式更新位置。

Step6根據(jù)父代慣性質(zhì)量決定是否變異，超出邊界范圍的粒子位置，采用公式控制其在邊界范圍內(nèi)波動(dòng)。

Step7根據(jù)模擬退火Metropolis原則來(lái)接受新解，

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

Step9判斷是否結(jié)束循環(huán)，若不結(jié)束，返回Step 3.若結(jié)束，輸出最優(yōu)解及其加工序列，

3案例分析

以10個(gè)工件，5臺(tái)機(jī)器的流水作業(yè)生產(chǎn)作為案例來(lái)進(jìn)行改進(jìn)萬(wàn)有引力算法的求解，Pij表示工件Ji在機(jī)器Mi上的加工時(shí)間如表1所示。

工件參數(shù)如表2所示，

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

運(yùn)行改進(jìn)后的萬(wàn)有引力算法GSGSA，得到的最優(yōu)加工序列為2.1.10.6.4.5.3.9.7.8.目標(biāo)函數(shù)最小值為66.75。

傳統(tǒng)的萬(wàn)有引力算法GSA運(yùn)行得到的加工序列為2.1.9.6.4.5.3.7.10.8.目標(biāo)函數(shù)最小值為72.171.結(jié)果對(duì)比如表3所示。

4結(jié)論

基于最大完工時(shí)間，構(gòu)造了以加權(quán)總誤工為目標(biāo)函數(shù)的優(yōu)化模型，傳統(tǒng)的萬(wàn)有引力算法無(wú)法對(duì)離散型編碼問(wèn)題求解，將模擬退火與引力算法相結(jié)合，增強(qiáng)其尋優(yōu)效果，速度更新時(shí)，借鑒粒子群，使粒子有向最佳位置逼近的趨勢(shì)，在相同的配置下，通過(guò)改進(jìn)后的引力算法對(duì)流水作業(yè)排序問(wèn)題進(jìn)行了求解，尋優(yōu)效果優(yōu)于原來(lái)的GSA算法。