以工業(yè)生產(chǎn)中面臨的實(shí)際生產(chǎn)問(wèn)題為背景,提出了分布式異構(gòu)并行機(jī)的調(diào)度問(wèn)題模型,進(jìn)而針對(duì)該問(wèn)題設(shè)計(jì)了一種混合果蠅優(yōu)化算法,用于最小化最大完工時(shí)間。在算法中,首先,在初始化階段加入競(jìng)爭(zhēng)機(jī)制,有效地提高了初始解的質(zhì)量;其次,在嗅覺(jué)搜索階段引入了自適應(yīng)搜索半徑,實(shí)現(xiàn)了對(duì)解空間的有效搜索;最后,在更新階段融入了三階段局部搜索,使全局搜索和局部搜索達(dá)到了較好平衡。仿真實(shí)驗(yàn)和算法比較驗(yàn)證了所提混合果蠅優(yōu)化算法的有效性和魯棒性。 

【文章來(lái)源】：控制工程. 2020,27(02)北大核心CSCD

【文章頁(yè)數(shù)】：10 頁(yè)

【部分圖文】：

工廠一對(duì)應(yīng)的甘特圖Fig.1Ganttmapoffactoryone

第2期黃元元等：混合果蠅算法求解分布式異構(gòu)并行機(jī)調(diào)度·257·表中‘/’表示該工件不能在該機(jī)器上加工。對(duì)π=[6,3,2,5,4,1]應(yīng)用規(guī)則ECF[7]，可得1,1T=2，1,2T=1,2,1T=1,2,2T=2,1,11,11,112[,][6,4]TTTπ=ππ=,1,21,21[][5]TTπ=π=,2,12,11[][3]TTπ=π=,2,22,21[,TTπ=π2,22][2,1]Tπ=，工廠一和工廠二對(duì)應(yīng)的甘特圖，分別如圖1和圖2所示。圖1工廠一對(duì)應(yīng)的甘特圖Fig.1Ganttmapoffactoryone圖2工廠二對(duì)應(yīng)的甘特圖Fig.2Ganttmapoffactorytwo3混合果蠅優(yōu)化算法果蠅優(yōu)化算法是一種基于果蠅覓食行為而提出的群智能優(yōu)化算法。將果蠅種群的覓食過(guò)程模擬為算法尋找優(yōu)化解的過(guò)程，基于果蠅覓食行為中的嗅覺(jué)和視覺(jué)行為來(lái)設(shè)計(jì)相應(yīng)的操作，通過(guò)不斷對(duì)果蠅種群中心位置的優(yōu)化，進(jìn)而找到食物存在的位置。原始果蠅優(yōu)化算法的流程如下[15]：步驟1初始化種群中心位置。步驟2嗅覺(jué)搜索：根據(jù)種群中心位置隨機(jī)產(chǎn)生NP個(gè)鄰域解。步驟3評(píng)價(jià)個(gè)體：計(jì)算每個(gè)個(gè)體的評(píng)價(jià)值。步驟4視覺(jué)搜索：選擇最優(yōu)鄰域解，替換更新種群中心位置。步驟5判斷終止準(zhǔn)則是否滿足：是，則輸出最優(yōu)解；否則，轉(zhuǎn)至步驟2。HFOA不同于傳統(tǒng)的FOA：首先，在初始化種群時(shí)引入了競(jìng)爭(zhēng)機(jī)制從而有效的提高了初始解的質(zhì)量；其次，在視覺(jué)和嗅覺(jué)搜索過(guò)程中加入了自適應(yīng)搜索半徑，實(shí)現(xiàn)了對(duì)解空間的有效搜索；最后，將基于三階段的局部搜索融入了算法更新階段：首先對(duì)最優(yōu)排序進(jìn)行了擾動(dòng)操作；其次，添加了對(duì)最優(yōu)排序的領(lǐng)域搜索操作；最后，對(duì)最大完成工廠內(nèi)部排序進(jìn)行基?

基于swap2的局部搜索是從最優(yōu)排序中任意挑出兩個(gè)工件進(jìn)行交換操作。第一階段的擾動(dòng)避免算法在搜索過(guò)程中過(guò)早陷入局部最優(yōu)；第二個(gè)階段的局部搜索操作保證了搜索方向的正確性；第三個(gè)階段的搜索操作是在較優(yōu)排序中找到一個(gè)最優(yōu)的分配方案；多階段的局部搜索同時(shí)應(yīng)用，有效地提高了局部搜索的能力。3.5HFOA流程圖HFOA主要包括3個(gè)主要環(huán)節(jié)：基于競(jìng)爭(zhēng)機(jī)制的初始化、基于自適應(yīng)搜索半徑的嗅覺(jué)和視覺(jué)搜索階段、基于三階段的局部搜索。求解分布式異構(gòu)并行機(jī)的HFOA的流程圖，如圖3所示。圖3HFOA流程圖Fig.3HFOAflowchart4仿真實(shí)驗(yàn)與分析為驗(yàn)證所提算法解決分布式異構(gòu)并行機(jī)調(diào)度問(wèn)題的有效性，首先，將改進(jìn)過(guò)后的算法與基本的果蠅優(yōu)化算法進(jìn)行比較，具體數(shù)據(jù)，見(jiàn)表3和表4。表3基本果蠅和改進(jìn)初始化果蠅的比較Tab.3Comparisonofbasicfruitfliesandimprovedinitializationoffruitflies初始化改進(jìn)的果蠅基本果蠅J_M_F最小值最大值平均值標(biāo)準(zhǔn)差最小值最大值平均值標(biāo)準(zhǔn)差運(yùn)行時(shí)間:50*J20_2_32072302235.848077243254249.052.8191320_3_2233262246.56.06218267302285.111.4188430_2_4236253246.53.91791277296288.25.36283530_3_5131155143.458.065203176183179.651.423940_3_4229247240.155.659284255266260.12.42693

【參考文獻(xiàn)】：
期刊論文
[1]果蠅優(yōu)化算法研究進(jìn)展[J]. 王凌,鄭曉龍.  控制理論與應(yīng)用. 2017(05)
[2]自適應(yīng)果蠅算法優(yōu)化模糊均值聚類算法圖像分割[J]. 孫立新,張栩之,鄧先瑞,魏萍.  控制工程. 2016(04)
[3]基于果蠅優(yōu)化算法的冒口優(yōu)化[J]. 王瞳,周建新,殷亞軍,沈旭,周琴.  特種鑄造及有色合金. 2016(03)
[4]分布式車(chē)間調(diào)度優(yōu)化算法研究綜述[J]. 王凌,鄧瑾,王圣堯.  控制與決策. 2016(01)
[5]基于免疫果蠅混合優(yōu)化算法的多配送中心選址問(wèn)題研究[J]. 劉勇,孫靜杰,王萱.  世界科技研究與發(fā)展. 2015(01)
[6]基于FOA-ELM的客戶基金購(gòu)買(mǎi)行為預(yù)測(cè)仿真[J]. 李棟,張文宇.  計(jì)算機(jī)仿真. 2014(06)
[7]求解一類異構(gòu)并行機(jī)調(diào)度問(wèn)題的分布估計(jì)算法[J]. 李作成,錢(qián)斌,胡蓉,向鳳紅,車(chē)國(guó)霖.  計(jì)算機(jī)集成制造系統(tǒng). 2013(09)



本文編號(hào)：3384027