工件排序的改進蟻群算法優化

王欣盛, 馬 良

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

工件排序的改進蟻群算法優化

王欣盛, 馬 良

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

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

排序問題;蟻群算法;組合優化

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

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

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

1 問題概述

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

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

2 基于蟻群算法的改進

2.1 算法改進思想

現介紹有關概念的定義.

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

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

螞蟻:在眾多的節點中轉移,通過其轉移到的節點,來確定工件排序的可行解,并且通過對可行解的比較,得出問題的最優解.

2.2 算法改進關鍵點

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

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

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

c.轉移概率結合考慮轉移花費時間與其他螞蟻留下的信息素濃度.

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

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

2.3 改進蟻群算法描述

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

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

3 改進蟻群算法規則及步驟

在原始蟻群算法規則和步驟基礎上,即可實現具體的改進蟻群算法

3.1 相關參數

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

3.2 目標函數

3.3 規則

3.3.1 狀態轉移規則

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

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

3.3.2 軌跡強度更新規則

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

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

3.4 算法步驟

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

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

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

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

步驟5如循環次數達到或超過給定的最大循環次數,結束排序,輸出當前最佳結果;否則,轉步驟2.

4 改進蟻群算法的Delphi實現

整個算法用Delphi 10實現,并在Windows XP環境下運行通過.相應的算法軟件界面如圖1和圖2所示.

算法軟件可通過導入數據文件、手工輸入或通過測試數據生成器來形成原始數據,并在軟件的輸入框中顯示這些數據.在軟件求解完畢后,會在右輸出框中顯示相應的結果.

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

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

5 算例測試

例1數據如表1所示.

表1 算例數據1Tab.1 Sample data 1

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

優化結果為:

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

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

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

機器最大加工時間為10.

例2數據略.

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

表2 計算結果1Tab.2 Computational results 1

表3 計算結果2Tab.3 Computational results 2

例3數據如表4所示.

表4 算例數據3Tab.4 Sample data 3

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

表5 計算結果3Tab.5 Computational results 3

最終結果為:

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

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

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

機器最大加工時間為5.

6 結束語

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

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

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

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

[4] 雷德明,嚴新平.多目標智能優化算法及其應用[M].北京:科學出版社,2009.

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

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

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

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

[9] 劉勇,馬良.非線性0- 1規劃的元胞蟻群算法[J].系統管理學報,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-),男,本科.研究方向:系統科學.E-mail:wangxsh42@126.com馬 良(聯系人),男,教授.研究方向:智能優化.E-mail:maliang@usst.edu.cn