工件排序的改進蟻群算法優(yōu)化

王欣盛, 馬 良

(上海理工大學(xué)管理學(xué)院)

工件排序的改進蟻群算法優(yōu)化

王欣盛, 馬 良

(上海理工大學(xué)管理學(xué)院)

就工件排序問題中的一種類型設(shè)計了融合局部改進策略的蟻群算法進行求解,并用Delphi在計算機上實現(xiàn)了相應(yīng)的算法軟件.經(jīng)大量算例測試,獲得了較好的效果,驗證了算法的可行性和有效性.

排序問題;蟻群算法;組合優(yōu)化

工件排序問題[1]是組合優(yōu)化中的著名難題,由于其一般情形下的NP(nondeterminstic polynomial)難解性,人們一直在不斷地對其進行研究.而排序問題在現(xiàn)實中的應(yīng)用,如航班著陸排序、汽車組裝線排序等,更是對人們的日常生活和工作有著重大的影響.

自20世紀90年代以后,來自自然界的仿生類算法開始引起人們的關(guān)注,尤其是在解決組合優(yōu)化難題方面,得到了一系列的嘗試和深入研究.其中,源自生物世界的蟻群算法在近十幾年里獲得了長足的發(fā)展[2-9].

本文主要針對一類工件排序問題設(shè)計了一種改進的蟻群算法,并在計算機上實現(xiàn)了相應(yīng)的軟件程序,經(jīng)大量算例測試,獲得了較好的效果.

1 問題概述

考慮單工序、多品種、多機器工件加工排序問題,即有多個品種的工件,其中,每個工件只有一道加工工序,眾多工件同時在多臺加工機器上并行加工,具體描述為:

有x件工件,y臺不同種類的機器,每個工件可以在任何一臺機器上加工,第i件工件在第j臺機器上的加工時間為t ij,U={U1,U2,…,U y},U是在第i臺機器上所有加工工件的集合,優(yōu)化的目標是使各臺機器上的最大加工時間值最小.

2 基于蟻群算法的改進

2.1 算法改進思想

現(xiàn)介紹有關(guān)概念的定義.

節(jié)點:每個節(jié)點代表兩個實體---加工機器和工件,有M*N個節(jié)點,其含義為第i個工件在第j個機器上加工.

邊與邊長:蟻群算法在處理此類型工件排序問題上,可忽略邊的存在,轉(zhuǎn)而關(guān)注從節(jié)點到節(jié)點轉(zhuǎn)移所花費的時間.若要從某個節(jié)點轉(zhuǎn)移到另一節(jié)點,需要花費的時間可以在目標節(jié)點中獲得,即從節(jié)點i轉(zhuǎn)移到節(jié)點j所需要的時間為節(jié)點j(節(jié)點j是由第x個工件與第y臺機器組合而成)第x個工件在第y臺機器的加工時間.

螞蟻:在眾多的節(jié)點中轉(zhuǎn)移,通過其轉(zhuǎn)移到的節(jié)點,來確定工件排序的可行解,并且通過對可行解的比較,得出問題的最優(yōu)解.

2.2 算法改進關(guān)鍵點

對基本蟻群算法作如下改進:

a.將待加工工件與加工機器的組合作為蟻群算法中每個螞蟻所要轉(zhuǎn)移的節(jié)點.

b.將工件加工時間作為螞蟻在節(jié)點轉(zhuǎn)移中所花費的時間,該時間與所要轉(zhuǎn)移的節(jié)點有關(guān),即節(jié)點為第i個工件在第j臺機器加工,則轉(zhuǎn)移所需花費的時間為第i個工件在第j臺機器加工的時間.

c.轉(zhuǎn)移概率結(jié)合考慮轉(zhuǎn)移花費時間與其他螞蟻留下的信息素濃度.

d.解是由M(機器臺數(shù))個子解集構(gòu)成,每個解集代表在該臺機器加工的工件號.

e.每次循環(huán)后(即同一時刻出發(fā)的螞蟻全部完成覓食后),對信息素進行更新.

2.3 改進蟻群算法描述

首先隨機放置m個螞蟻到n個節(jié)點上,然后對每個螞蟻進行節(jié)點轉(zhuǎn)移.在螞蟻要選擇一個節(jié)點作為移動目標前,按轉(zhuǎn)移概率選擇可能轉(zhuǎn)移的節(jié)點.螞蟻轉(zhuǎn)移的可能性為軌跡強度的增函數(shù)、花費時間的減函數(shù),即轉(zhuǎn)移花費時間越少,可見度越大,越容易被選擇;而走過的螞蟻越多,在邊上留下的軌跡信息素越多,軌跡強度就越強,也越容易被選擇.經(jīng)多次循環(huán)后,所有的螞蟻所走的路線趨向于最佳路徑.

由于這里研究的是單工序、多工件、多機器的加工工件排序問題,其解的形式不同于雙機N件工件排序問題的解形式,最終所得的解是由M個(加工機器數(shù))子解集的集合,每個子解集的值代表在該加工機器上需要加工的工件號.

3 改進蟻群算法規(guī)則及步驟

在原始蟻群算法規(guī)則和步驟基礎(chǔ)上,即可實現(xiàn)具體的改進蟻群算法

3.1 相關(guān)參數(shù)

α為信息素相對重要性,α≥0;β為轉(zhuǎn)移時間相對重要性,β≥0;ρ為軌跡衰減度,0≤ρ≤1;τ為信息素,τ≥0;m為螞蟻數(shù),m≥0;U i為第i臺機器加工的工件集合;S i為集合的U i未來總加工時間,Si≥0;Q為螞蟻一次所留信息素的量為一個常數(shù);d為節(jié)點轉(zhuǎn)移所需時間;η為節(jié)點能見度,等于1/d;θ為某機器未來加工總時間的相對重要度,θ≥0;P為轉(zhuǎn)移概率;p kse為第k只螞蟻從節(jié)點s轉(zhuǎn)移到節(jié)點e的轉(zhuǎn)移概率;s,e分別為所在節(jié)點,轉(zhuǎn)移目標節(jié)點;Δτij為節(jié)點i到j(luò)的信息素增量;d ij為第i個工件在第j個機器加工時間.

3.2 目標函數(shù)

3.3 規(guī)則

3.3.1 狀態(tài)轉(zhuǎn)移規(guī)則

當轉(zhuǎn)移目標節(jié)點e不在禁忌表T中,計算轉(zhuǎn)移概率;如果該點在T中,則不考慮轉(zhuǎn)移到該節(jié)點.當p k

se=0時,直接將其視為最佳轉(zhuǎn)移概率.如果有相同轉(zhuǎn)移概率的節(jié)點存在,則從中隨機選取一個作為轉(zhuǎn)移節(jié)點.其中,i與e節(jié)點的加工機器號相等.

3.3.2 軌跡強度更新規(guī)則

在蟻群算法中,第k只螞蟻從節(jié)點s到節(jié)點e的轉(zhuǎn)移路徑所留下的信息素,可由有該螞蟻覓食的時間來決定,故該螞蟻在從s節(jié)點轉(zhuǎn)移到e節(jié)點所留下的信息素為

同一時刻出發(fā)的螞蟻全部完成覓食(找到可行解)后,軌跡強度更新規(guī)則為

3.4 算法步驟

步驟1初始化.初始化各個節(jié)點的信息素,賦值為0;T表(禁忌表)初始化,置空;隨機將m個螞蟻放置于n個節(jié)點上;將路徑信息素賦初值,這里使用Q/(min加工時間×零件數(shù)).

步驟2將T表與U相對應(yīng),螞蟻的初始出發(fā)點置于T表中,同時給相對應(yīng)的U i集合添加該工件號.

步驟3對每個螞蟻計算轉(zhuǎn)移概率p krs,按最大轉(zhuǎn)移概率將該螞蟻從現(xiàn)節(jié)點轉(zhuǎn)移至s節(jié)點,并將s節(jié)點放T表中,在相對應(yīng)的U i集合添加該工件號.如所對應(yīng)的U i為空,則將該工件號直接放入該子解集中;如不為空,則計算每個U i的所含有的元素的加工時間總和.選取加工時間總和最小的U i集合,放入所選節(jié)點的工件號,若有多個U i集合加工時間總和最小,則隨機選取一個集合.

步驟4在螞蟻獲得可行解后,計算每個螞蟻的目標函數(shù)值,在同一時刻出發(fā)的所有螞蟻得到可行解后,作鄰域搜索局部改進,并更新軌跡強度.

步驟5如循環(huán)次數(shù)達到或超過給定的最大循環(huán)次數(shù),結(jié)束排序,輸出當前最佳結(jié)果;否則,轉(zhuǎn)步驟2.

4 改進蟻群算法的Delphi實現(xiàn)

整個算法用Delphi 10實現(xiàn),并在Windows XP環(huán)境下運行通過.相應(yīng)的算法軟件界面如圖1和圖2所示.

算法軟件可通過導(dǎo)入數(shù)據(jù)文件、手工輸入或通過測試數(shù)據(jù)生成器來形成原始數(shù)據(jù),并在軟件的輸入框中顯示這些數(shù)據(jù).在軟件求解完畢后,會在右輸出框中顯示相應(yīng)的結(jié)果.

圖1 測試用例生成器Fig.1 Test data generator

圖2 軟件計算示意圖Fig.2 Software computation

5 算例測試

例1數(shù)據(jù)如表1所示.

表1 算例數(shù)據(jù)1Tab.1 Sample data 1

在工件數(shù)為7,加工機器數(shù)為3,螞蟻數(shù)量為10,能見度重要性為1.5,已經(jīng)過路徑長度重要性為2,軌跡衰減度為0.1,循環(huán)次數(shù)為50的情況下,所得計算結(jié)果如表2所示.

優(yōu)化結(jié)果為:

1號機器加工:→第5個工件→第6個工件→第7個工件(實際加工時間為10);

2號機器加工:→第1個工件→第4個工件(實際加工時間為10);

3號機器加工:→第2個工件→第3個工件(實際加工時間為10);

機器最大加工時間為10.

例2數(shù)據(jù)略.

在工件數(shù)為7,加工機器數(shù)為3,螞蟻數(shù)量為20,能見度重要性為1.5,已經(jīng)過路徑長度重要性為2,軌跡衰減度為0.1,循環(huán)次數(shù)為80的情況下,所得計算結(jié)果如表3所示.機器最大加工時間為42.5.

表2 計算結(jié)果1Tab.2 Computational results 1

表3 計算結(jié)果2Tab.3 Computational results 2

例3數(shù)據(jù)如表4所示.

表4 算例數(shù)據(jù)3Tab.4 Sample data 3

在工件數(shù)為7,加工機器數(shù)為3,螞蟻數(shù)量為10,能見度重要性為1.5,已經(jīng)過路徑長度重要性為2,軌跡衰減度為0.1,循環(huán)次數(shù)為50的情況下,所得計算結(jié)果如表5所示.

表5 計算結(jié)果3Tab.5 Computational results 3

最終結(jié)果為:

1號機器加工:→第1個工件→第2個工件→第5個工件→第6個工件→第7個工件(實際加工時間為5);

2號機器加工:→第4個工件(實際加工時間為4);

3號機器加工:→第3個工件(實際加工時間為4);

機器最大加工時間為5.

6 結(jié)束語

蟻群算法是一種仿生智能優(yōu)化算法,在求解許多NP-難題中表現(xiàn)出了良好的性能.這種隨機尋優(yōu)方法具有很強的發(fā)展?jié)摿?同時,還常常能與其他的優(yōu)化算法相結(jié)合.本文僅對單工序、多工件、多加工機器的工件排序問題設(shè)計了相應(yīng)的改進蟻群算法,并在計算機上予以實現(xiàn),為實際問題的求解提供了方便的軟件工具.

[1] 陳義保,姚建初,鐘毅芳,等.基于蟻群系統(tǒng)的工件排序問題的一種新算法[J].系統(tǒng)工程學(xué)報,2002,10(5):476-480.

[2] 馬良,王波.基礎(chǔ)運籌學(xué)教程[M].北京:高等教育出版社,2006.

[3] 馬良,朱剛,寧愛兵.蟻群優(yōu)化算法[M].北京:科學(xué)出版社,2008.

[4] 雷德明,嚴新平.多目標智能優(yōu)化算法及其應(yīng)用[M].北京:科學(xué)出版社,2009.

[5] 王洪剛,馬良.TSP的量子螞蟻算法求解[J].運籌與管理,2009,18(6):11-13.

[6] 朱剛,馬良,高巖.離散元胞螞蟻算法及其收斂性[J].科學(xué)技術(shù)與工程,2009,9(5):1115-1119.

[7] 朱剛,馬良.生長競爭型函數(shù)優(yōu)化的蟻群算法[J].數(shù)學(xué)的實踐與認識,2010,40(2):108-112.

[8] 朱剛,馬良.多目標優(yōu)化的生長競爭蟻群算法[J].系統(tǒng)工程,2010,28(12):91-95.

[9] 劉勇,馬良.非線性0- 1規(guī)劃的元胞蟻群算法[J].系統(tǒng)管理學(xué)報,2010,19(3):351-355.

Improved ant colony optimization for scheduling problem

WANGXin-sheng, MA Liang
(University of Shanghai for Science and Technology,Shanghai 200093,China)

Combined with the local searching strategy,an ant colony optimization algorithm was proposed for a kind of scheduling problems.The algorithm is coded in Delphi and runs on microcomputer.By solving series of experimental examples,the modified algorithm was tested and validated with satisfactory results achieved.The computational results prove the feasibility and effectiveness of the algorithm for solving scheduling problems.

scheduling problem;ant colony algorithm;sombinatorial optimization

O 22

A

1007-6735(2011)04-0362-05

2010-06-09

王欣盛(1988-),男,本科.研究方向:系統(tǒng)科學(xué).E-mail:wangxsh42@126.com馬 良(聯(lián)系人),男,教授.研究方向:智能優(yōu)化.E-mail:maliang@usst.edu.cn