• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    蟻群算法的參數(shù)優(yōu)化配置研究

    2011-02-09 01:57:30屹,李
    制造業(yè)自動化 2011年5期
    關(guān)鍵詞:小生境螞蟻因素

    甘 屹,李 勝

    (上海理工大學(xué) 機(jī)械工程學(xué)院,上海 200093)

    0 引言

    蟻群優(yōu)化(Ant Colony Optimization, ACO)是一種模擬自然界螞蟻尋找食物的行為智能優(yōu)化算法[1]。目前,對ACO 算法的研究已經(jīng)由單一的旅行商問題(Traveling Salesman Problem, TSP)領(lǐng)域擴(kuò)展到了多個應(yīng)用領(lǐng)域。在運(yùn)用蟻群算法求解問題時,參數(shù)數(shù)值的設(shè)置直接影響算法的收斂性。本文通過正交試驗(yàn)法獲取小生境蟻群優(yōu)化(Microhabitat ACO,MACO)[2,3]的參數(shù)配置,對小生境蟻群算法性能進(jìn)行優(yōu)化。并用以求解旅行商問題(Traveling Salesman Problem, TSP)[4,5]和車間調(diào)度問題(job shop scheduling Problems,JSSP)問題[6]。

    1 小生境蟻群優(yōu)化概述

    針對基本蟻群算法存在的問題,MACO從蟻群信息素分布多樣性、更新信息素策略、信息差突變等機(jī)制上,對基本蟻群算法進(jìn)行改進(jìn),并應(yīng)用于求解動態(tài)聯(lián)盟伙伴選擇問題和車間調(diào)度問題[2]。

    MACO對經(jīng)驗(yàn)信息和啟發(fā)信息的利用是隨著搜索演化進(jìn)程而變化的。在蟻群搜索最優(yōu)解的初期,小生境中可利用的經(jīng)驗(yàn)信息還不多,這時螞蟻運(yùn)用初始啟發(fā)信息,以“探索”為主;隨著搜索的演進(jìn),小生境中經(jīng)驗(yàn)信息增多,這時螞蟻的搜索則以“利用”經(jīng)驗(yàn)信息為主,加速解的收斂;而到了搜索的后期,要避免算法早熟、停滯的現(xiàn)象,就要在已有解的基礎(chǔ)上“再探索”,以擴(kuò)大解的搜索空間,使更優(yōu)解得以突現(xiàn)。

    MACO算法的螞蟻更新信息素的方式有兩種:局部更新和全局更新。局部更新規(guī)則是螞蟻每移向下一個結(jié)點(diǎn),就會在該路徑上留下信息素;全局更新則是在每一次搜索周期結(jié)束時(即所有尋優(yōu)群體都搜索結(jié)束時),更新全部路徑的信息素。全局更新考慮了每一批尋優(yōu)群體尋路的結(jié)果,隱含了信息反饋,使得算法更容易趨優(yōu)。本文采用全局更新。

    MACO算法還生成小生境信息差(Information Difference),以增加信息的多樣性,擴(kuò)大搜索空間。根據(jù)具體問題的特點(diǎn),小生境信息差可以有不同的產(chǎn)生方法。對于TSP,本文對每代螞蟻搜索的解采用遺傳操作(遺傳交叉,遺傳變異),產(chǎn)生小生境信息差,擴(kuò)大解的搜索空間,保證更優(yōu)解的突現(xiàn)。 對于JSSP,本文的選擇概率選擇下一可達(dá)結(jié)點(diǎn)時,以隨機(jī)概率產(chǎn)生小生境信息差[3],以跳出局部最優(yōu),擴(kuò)展搜索范圍,保持解的多樣性。

    MACO算法的參數(shù)包括關(guān)于啟發(fā)信息、經(jīng)驗(yàn)信息的α0,β0,kα和kβ等,這些參數(shù)體現(xiàn)出蟻群優(yōu)化進(jìn)行尋優(yōu)的同時和真實(shí)螞蟻受環(huán)境影響一樣,也受到多種因素的影響。這些參數(shù)的取值直接關(guān)系到算法的尋優(yōu)效能。

    2 正交試驗(yàn)設(shè)計(jì)

    針對蟻群優(yōu)化多參數(shù)的多種取值,本文運(yùn)用小生境蟻群優(yōu)化算法求解TSP和JSSP問題,利用正交試驗(yàn)法分析參數(shù)α0、β0、kα、kβ對算法尋優(yōu)性能的影響。

    2.1 正交試驗(yàn)因素與水平

    在小生境蟻群優(yōu)化中,一次螞蟻搜索循環(huán)是指所有螞蟻從初始節(jié)點(diǎn)出發(fā),找到一條符合條件的路徑的過程。如果最大循環(huán)次數(shù)NC_m過大,會使算法的收斂時間比較長;如果NC_m偏小,會使算法的結(jié)果隨機(jī)性能增加,影響尋優(yōu)性能。通過大量實(shí)例計(jì)算,一般NC_m=500時,算法性能較穩(wěn)定。同樣,如果螞蟻數(shù)目越大,算法的全局搜索能力越強(qiáng),但是算法的計(jì)算速度將成指數(shù)級遞增。對于TSP,螞蟻數(shù)目一般為城市規(guī)模n的2/3[7]。對于JSSP, 每代的螞蟻數(shù)目取為工件數(shù)目[8]。通過大量實(shí)例計(jì)算,本文中,對于TSP,信息揮發(fā)率ρ=0.1,對于JSSP,ρ=0.7。

    在正交試驗(yàn)中,選取各參數(shù)的代表性取值。取α0、β0分別以1的步長遞增,lgkα、lgkβ分別取-4.699、-4、-3.699、-3、-2.699。取實(shí)驗(yàn)10次的平均值作為實(shí)驗(yàn)結(jié)果。影響MACO求解的因素與水平如表1所示。由于小生境信息差中的信息是相互關(guān)聯(lián)的[2],所以考慮α0和β0,kα和kβ,α0和kα以及β0和kβ之間可能存在交互作用,希望通過正交實(shí)驗(yàn)設(shè)計(jì)找出好的因素水平搭配。本文測試的仿真編程軟件為MATLAB R2008b,操作系統(tǒng)為Windows XP,CPU為2.0GHz,內(nèi)存為1.99GB。

    表1 正交試驗(yàn)因素和水平

    這是個4因素5水平的正交試驗(yàn),考慮到的交互交互作用有4個,所以采用L50 (511)正交表進(jìn)行試驗(yàn)。對應(yīng)的表頭設(shè)計(jì)如表2所示。

    表2 L50 (511)表頭設(shè)計(jì)

    2.2 試驗(yàn)結(jié)果

    表3是根據(jù)正交表 L25 (56)表頭測試48個城市的Att48問題[9]的結(jié)果及分析。其中,

    Tour_ length =(算法計(jì)算所得最短距離-已知最優(yōu)解)/已知最優(yōu)解×100%

    Iteration _Time =(算法計(jì)算所得最短耗費(fèi)時間-已知最優(yōu)解)/已知最優(yōu)解×100%

    根據(jù)表3計(jì)算出每列的極差。極差最大的因素意味著它的不同水平造成的實(shí)驗(yàn)差別比較大,由此確定出各個因素對MACO在求解TSP問題的重要性,如表4所示。

    表3 各方案的試驗(yàn)結(jié)果

    設(shè)目標(biāo)函數(shù)f(x)=minL。由表4可知,若L為旅行距離,則各因素指標(biāo)影響的重要性順序?yàn)椋害?>β0>kα> kβ>α0×β0>β0×kβ>α0×kα>kα×kβ;若L為耗費(fèi)時間,則各因素指標(biāo)影響的重要性順序?yàn)椋害?> kα×kβ>β0>kβ> kα>α0×β0>α0×kα>β0×kβ。這也說明求解該問題不能同時滿足兩個目標(biāo)函數(shù)最優(yōu)。

    由表4可得正交水平與因素的關(guān)系,如圖1所示。圖1中,目標(biāo)函數(shù)為f(x)=minL,若L為旅行距離,各因素的最佳組合為,α0=1,β0=3,kα=0.0002,kβ=0.001;若L為耗費(fèi)時間,各因素的最佳組合為,α0=1,β0=1,kα=0.002,kβ=0.001。

    表4 各方案下實(shí)驗(yàn)指標(biāo)結(jié)果分析

    圖1 正交水平與因素的關(guān)系

    3 計(jì)算和結(jié)果分析

    3.1 計(jì)算

    對于TSP問題,考慮不同的城市規(guī)模,選用4個TSP基準(zhǔn)算例[9]:Bayg29, Att48, Kroc100,A180。目標(biāo)函數(shù)f(x)=minL,L為旅行距離,得到的解如表5所示。

    表5 通過正交試驗(yàn)得到的TSP參數(shù)配置

    對于JSSP問題,選用6個JSSP基準(zhǔn)算例[10]:FT06, FT10, FT20, LA06,LA22,LA22。目標(biāo)函數(shù)為單位工時,得到的解如表6所示。

    表6 通過正交試驗(yàn)得到的JSSP參數(shù)配置

    3.2 結(jié)果分析

    表7給出了目標(biāo)函數(shù)f(x)=minL(L為旅行距離),利用正交試驗(yàn)優(yōu)化配置參數(shù),求解以上4個算例的結(jié)果。

    表7 參數(shù)配置后的計(jì)算結(jié)果

    注:N-城市規(guī)模,Opt.-樣例的已知最優(yōu)解,Best-獲得的最好解,Ave. -平均最優(yōu)解,Orig.-優(yōu)化配置以前的結(jié)果(隨機(jī)20次的平均值)。

    由表7可以看出,通過優(yōu)化配置參數(shù)的最優(yōu)解與隨機(jī)解相比,更接近已知的最優(yōu)解,說明正交試驗(yàn)的參數(shù)配置可以在較短的計(jì)算時間獲得較好的尋優(yōu)結(jié)果。若目標(biāo)函數(shù)f(x)=minL(L為耗費(fèi)時間)也得到相似結(jié)論。

    對于JSSP問題,利用表6的參數(shù)配置求解對應(yīng)基準(zhǔn)算例[10]的結(jié)果如表8所示。從表8可看出,采用所配置的參數(shù),在求解問題規(guī)模逐漸增大時,MACO能獲得的較滿意的解。

    表8 JSSP基準(zhǔn)測試問題的求解結(jié)果

    圖2 優(yōu)化配置前后的MACO進(jìn)化特征曲線

    圖2 給出了優(yōu)化配置后的MACO求解FT06和FT10的進(jìn)化特征曲線。從圖2可以看出優(yōu)化配置之后的MACO再求解JSSP問題時用了100次的迭代的收斂速度但是一般都在30到40次收斂,隨著規(guī)模的增加收斂次數(shù)會逐漸增多。

    4 結(jié)論

    為了提高M(jìn)ACO求解時的尋優(yōu)性能,本文采用正交試驗(yàn)的方法進(jìn)行MACO的參數(shù)配置。當(dāng)然,采用正交試驗(yàn)獲得的參數(shù)優(yōu)選值,具有一定的局限性。這些優(yōu)選值是所設(shè)定的試驗(yàn)所用水平的某種組合,優(yōu)選結(jié)果不會超越所取水平的范圍。本文通過適當(dāng)選取試驗(yàn)水平,對不同計(jì)算規(guī)模的TSP、JSSP基準(zhǔn)算例的求解,所得到結(jié)果證明了MACO算法及通過正交試驗(yàn)獲得的參數(shù)配置在求解精度和收斂速度上可以獲得最優(yōu)和準(zhǔn)最優(yōu)解。

    [1] Macro D.Thomas stutzle.ant colony optimization[J].Cambridge:MIT Press,2003.

    [2] 甘屹,李勝,張志偉.小生境蟻群優(yōu)化及其在JSSP中的應(yīng)用研究[J].中國機(jī)械工程,2010,21(10):1173-1178.

    [3] 甘屹,齊從謙,杜繼濤.基于蟻群算法的動態(tài)聯(lián)盟伙伴選擇研究[J].系統(tǒng)仿真學(xué)報(bào),2006,18(2):517-520,525.

    [4] Dorigo M,Gambardella L M.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation,1997,41(1):53-66.

    [5] 鄭向瑜,彭勇.求解旅行Agent 問題的自適應(yīng)蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(16):52-54.

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

    [7] 蔣玲艷,張軍,鐘樹鴻.蟻群算法參數(shù)分析[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(20),31-36.

    [8] 張曉玲,楊健,杜英國.基于正交實(shí)驗(yàn)的蟻群算法在車間調(diào)度問題中的應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2010,19(4),152-156.

    [9] http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.[10]http://people.brunel.ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html.

    猜你喜歡
    小生境螞蟻因素
    喀斯特小生境與植物物種多樣性的關(guān)系
    ——以貴陽花溪公園為例
    解石三大因素
    中國寶玉石(2019年5期)2019-11-16 09:10:20
    我們會“隱身”讓螞蟻來保護(hù)自己
    螞蟻
    基于小生境遺傳算法的相控陣?yán)走_(dá)任務(wù)調(diào)度
    短道速滑運(yùn)動員非智力因素的培養(yǎng)
    小生境遺傳算法在網(wǎng)絡(luò)編碼優(yōu)化中的應(yīng)用研究
    螞蟻找吃的等
    多交叉混沌選擇反向小生境遺傳算法
    怎樣理解人是戰(zhàn)爭的決定因素?
    軍事歷史(1981年2期)1981-08-14 08:27:58
    重庆市| 肇东市| 荃湾区| 拜城县| 娄烦县| 清徐县| 合山市| 绥江县| 景宁| 连江县| 当雄县| 台北市| 海口市| 修水县| 喀什市| 洱源县| 福安市| 昂仁县| 石屏县| 资中县| 大英县| 泽州县| 鹤山市| 阿鲁科尔沁旗| 高邑县| 上虞市| 资兴市| 景东| 崇文区| 丰都县| 郧西县| 铜川市| 南雄市| 恩平市| 顺昌县| 龙游县| 通州区| 巴中市| 长春市| 晋中市| 西充县|