一類平滑自適應(yīng)蟻群算法的設(shè)計與實驗

【摘 要】 在解決Job shop調(diào)度問題過程中，針對蟻群算法在收斂速度和全局尋優(yōu)方面的缺陷，提出一種改進(jìn)的平滑自適應(yīng)蟻群算法（SA-ACO）。該算法在循環(huán)過程中通過改變自適應(yīng)參數(shù)的值，隨機(jī)改變螞蟻搜索范圍；并采用自適應(yīng)平滑機(jī)制對信息素進(jìn)行更新，加快算法收斂速度。當(dāng)算法陷入局部最優(yōu)時，自適應(yīng)地改變揮發(fā)系數(shù)的取值，使算法跳出局部最優(yōu)，最終收斂到全局最優(yōu)解，同時采用獎罰策略加快算法收斂速度。

【關(guān)鍵詞】 改進(jìn)蟻群算法；Job shop調(diào)度；平滑機(jī)制；自適應(yīng)；車間調(diào)度

隨著科學(xué)技術(shù)的進(jìn)步和計算機(jī)技術(shù)的發(fā)展，促使大規(guī)模定制生產(chǎn)方式向品種多批量小的生產(chǎn)方式轉(zhuǎn)變。本文采用一群算法，針對車間生產(chǎn)調(diào)度問題具有的建模/計算復(fù)雜性、不確定性、多目標(biāo)性、多約束性、離散性等特點[2]，提出一種改進(jìn)的平滑自適應(yīng)蟻群算法，提高算法收斂速度；當(dāng)算法進(jìn)入局部最優(yōu)時，采用自適應(yīng)平滑機(jī)制對信息素的值進(jìn)行調(diào)整，提高算法的全局搜索能力[3]。

一、工序轉(zhuǎn)移規(guī)則

所有螞蟻在搜索最優(yōu)路徑的過程中，只能選擇前期工序已經(jīng)加工完成而本身尚未加工的工序，將所有符合條件的工序節(jié)點放入可選工序集ap中，將所有已經(jīng)完成的工序放入螞蟻路徑集tabu中。根據(jù)以下公式計算出各可選工序的轉(zhuǎn)移概率。

（1）

其中，為從節(jié)點到節(jié)點的轉(zhuǎn)移概率，螞蟻位于節(jié)點，為可選工序集，即在工序加工完成后，被放入螞蟻路徑集tabu中。 和分別表示信息素和可見度的偏重系數(shù)。

二、改進(jìn)信息素更新策略

該算法對最優(yōu)路徑進(jìn)行獎勵，對最差路徑進(jìn)行懲罰，可以加快算法收斂速度并跳出局部最優(yōu)。但此方法不能保證徹底清除早熟現(xiàn)象，故將信息素平滑機(jī)制與之結(jié)合，其主要作用是當(dāng)各路徑上的信息素濃度相差比較大時，可以降低較優(yōu)路徑上信息素的濃度[4]。基本做法是：當(dāng)前路徑上的信息素濃度明顯高于其它路徑時，為防止算法局部收斂，采用信息素平滑機(jī)制，降低該路徑上的信息素的值，進(jìn)而擴(kuò)大搜索范圍，既加快算法的運(yùn)行速度，還提高該算法尋優(yōu)性能。在整個螞蟻尋優(yōu)路徑中，只讓最短路徑上的螞蟻釋放信息素

四、本章小結(jié)

本文提出的改進(jìn)平滑自適應(yīng)蟻群算法針對不同的情況，給出了工序選擇規(guī)則、信息素更新規(guī)則和新解接受規(guī)則等改進(jìn)蟻群算法基本規(guī)則的設(shè)計方法。采用兩種信息素自適應(yīng)調(diào)整策略和獎懲措施相結(jié)合，并與平滑機(jī)制相結(jié)合，成功解決了原始算法全局搜索性差，收斂速度慢的問題，并提高了算法的穩(wěn)定性。

參考文獻(xiàn)：

[1]宋存利.生產(chǎn)調(diào)度問題及其智能優(yōu)化算法研究[D].遼寧：大連理工大學(xué)，2011：1-20.

[2]徐俊剛，戴國忠，王宏安.生產(chǎn)調(diào)度理論和方法研究綜述[J].計算機(jī)研究與發(fā)展：2004，41（2）：257-267.

[3]許瑞，陳華平，邵浩等.極小化總完工時間批調(diào)度問題的兩種蟻群算法[J].計算機(jī)集成制造系統(tǒng)：2010，16（6）：1255-1264.

[4]Gu Wen bin， Tang Dun bing， Zheng Kun. Minimizing makespan in Job-shop Scheduling Problem Using an Improved Adaptive Particle Swarm Optimization Algorithm[C]. Chinese Control and Decision Conference （CCDC）， 2012， 24： 3189-3193.