求解離散優(yōu)化問(wèn)題的人工蜂群算法研究
發(fā)布時(shí)間：2019-03-16 16:09
【摘要】：人工蜂群算法(Artificial Bee Colony Algorithm, ABC)是一種受蜜蜂采蜜行為啟發(fā)產(chǎn)生的新型群體智能優(yōu)化算法。由于控制參數(shù)少、易于實(shí)現(xiàn)、計(jì)算簡(jiǎn)潔等特點(diǎn),近年來(lái)ABC算法備受研究者關(guān)注。不過(guò)ABC算法提出時(shí)最早用于求解連續(xù)函數(shù)優(yōu)化、連續(xù)多目標(biāo)優(yōu)化、人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練等問(wèn)題,對(duì)于離散優(yōu)化問(wèn)題的應(yīng)用研究并不太多。離散優(yōu)化問(wèn)題是眾多優(yōu)化問(wèn)題的一個(gè)重要分支且具有廣泛的工業(yè)應(yīng)用需求,為此本文將擴(kuò)展ABC算法使其能夠處理典型應(yīng)用領(lǐng)域的離散優(yōu)化問(wèn)題。本文將基本ABC算法離散化后得到DABC算法,并應(yīng)用它求解基于眾包環(huán)境下的軟件協(xié)同測(cè)試任務(wù)分配問(wèn)題。在與基于啟發(fā)式策略的任務(wù)分配方法進(jìn)行對(duì)比中,DABC算法的分配結(jié)果更優(yōu),可以有效的降低進(jìn)行測(cè)試任務(wù)所需要的成本。本文在總結(jié)學(xué)者對(duì)ABC算法研究工作的基礎(chǔ)上對(duì)離散化后的DABC算法進(jìn)行了改進(jìn),具體改進(jìn)點(diǎn)為：(1)使用基于反向輪盤(pán)賭的選擇策略代替基本人工蜂群算法的輪盤(pán)賭選擇策略以保持種群多樣性,增強(qiáng)算法的尋優(yōu)能力；(2)受差分演化算法和遺傳算子的啟發(fā),提出了一種多維變量擾動(dòng)鄰域搜索策略以提高算法的獲得全局最優(yōu)解的能力。基于以上兩點(diǎn)改進(jìn)得到]DABC算法并將IDABC算法應(yīng)用于求解0-1背包問(wèn)題中,通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的有效性。本節(jié)實(shí)驗(yàn)從三方面出發(fā)：(1)通過(guò)與不同算法所獲得的最優(yōu)解情況進(jìn)行對(duì)比驗(yàn)證算法的求解能力,(2)實(shí)驗(yàn)驗(yàn)證設(shè)置不同的參數(shù)值對(duì)算法的影響,(3)實(shí)驗(yàn)驗(yàn)證了提出的多維變量擾動(dòng)鄰域搜索策略對(duì)于算法尋優(yōu)能力以及加快算法收斂都有所提高。在本文的最后,又基于提出IDABC算法設(shè)計(jì)和實(shí)現(xiàn)了求解0-1背包問(wèn)題的可視化求解工具,用以方便使用者對(duì)不同0-1背包問(wèn)題進(jìn)行求解并以直觀的方式展示出問(wèn)題的解。
[Abstract]:Artificial bee colony algorithm (Artificial Bee Colony Algorithm, ABC) is a new swarm intelligence optimization algorithm inspired by honey harvesting behavior of bees. In recent years, ABC algorithm has attracted much attention due to its few control parameters, easy implementation and concise calculation. However, the ABC algorithm was first put forward to solve the continuous function optimization, continuous multi-objective optimization, artificial neural network training and other problems, but the application of the discrete optimization problem is not much. Discrete optimization problem is an important branch of many optimization problems and has a wide range of industrial application requirements. In this paper, the ABC algorithm will be extended to deal with discrete optimization problems in typical application fields. In this paper, the basic ABC algorithm is discretized and the DABC algorithm is obtained, which is used to solve the task assignment problem of software collaborative testing based on crowdsourcing environment. Compared with the heuristic strategy-based task assignment method, the DABC algorithm has better results, which can effectively reduce the cost of the test task. In this paper, on the basis of summarizing the research work of ABC algorithm, the discrete DABC algorithm is improved. The specific improvement points are as follows: (1) the roulette selection strategy based on reverse roulette is used instead of the basic artificial bee colony algorithm to maintain the diversity of population and enhance the optimization ability of the algorithm; (2) inspired by the differential evolution algorithm and genetic operator, a multi-dimensional variable perturbation neighborhood search strategy is proposed to improve the ability of the algorithm to obtain the global optimal solution. Based on the above two improvements, the DABC algorithm is obtained and the IDABC algorithm is applied to solve the 0 / 1 knapsack problem. The effectiveness of the algorithm is verified by experiments. The experiment in this section starts from three aspects: (1) by comparing with the optimal solutions obtained by different algorithms, the ability of the algorithm is verified; (2) the influence of setting different parameter values on the algorithm is verified by experiments. (3) experiments show that the proposed multi-dimensional variable perturbation neighborhood search strategy can improve the searching ability of the algorithm and accelerate the convergence of the algorithm. At the end of this paper, based on the proposed IDABC algorithm, a visual solution tool is designed and implemented to solve the 0 / 1 knapsack problem, which is used to facilitate users to solve different 0 / 1 knapsack problems and to display the solution of the problem in an intuitive manner.
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
本文編號(hào)：2441708
[Abstract]:Artificial bee colony algorithm (Artificial Bee Colony Algorithm, ABC) is a new swarm intelligence optimization algorithm inspired by honey harvesting behavior of bees. In recent years, ABC algorithm has attracted much attention due to its few control parameters, easy implementation and concise calculation. However, the ABC algorithm was first put forward to solve the continuous function optimization, continuous multi-objective optimization, artificial neural network training and other problems, but the application of the discrete optimization problem is not much. Discrete optimization problem is an important branch of many optimization problems and has a wide range of industrial application requirements. In this paper, the ABC algorithm will be extended to deal with discrete optimization problems in typical application fields. In this paper, the basic ABC algorithm is discretized and the DABC algorithm is obtained, which is used to solve the task assignment problem of software collaborative testing based on crowdsourcing environment. Compared with the heuristic strategy-based task assignment method, the DABC algorithm has better results, which can effectively reduce the cost of the test task. In this paper, on the basis of summarizing the research work of ABC algorithm, the discrete DABC algorithm is improved. The specific improvement points are as follows: (1) the roulette selection strategy based on reverse roulette is used instead of the basic artificial bee colony algorithm to maintain the diversity of population and enhance the optimization ability of the algorithm; (2) inspired by the differential evolution algorithm and genetic operator, a multi-dimensional variable perturbation neighborhood search strategy is proposed to improve the ability of the algorithm to obtain the global optimal solution. Based on the above two improvements, the DABC algorithm is obtained and the IDABC algorithm is applied to solve the 0 / 1 knapsack problem. The effectiveness of the algorithm is verified by experiments. The experiment in this section starts from three aspects: (1) by comparing with the optimal solutions obtained by different algorithms, the ability of the algorithm is verified; (2) the influence of setting different parameter values on the algorithm is verified by experiments. (3) experiments show that the proposed multi-dimensional variable perturbation neighborhood search strategy can improve the searching ability of the algorithm and accelerate the convergence of the algorithm. At the end of this paper, based on the proposed IDABC algorithm, a visual solution tool is designed and implemented to solve the 0 / 1 knapsack problem, which is used to facilitate users to solve different 0 / 1 knapsack problems and to display the solution of the problem in an intuitive manner.
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
【相似文獻(xiàn)】
相關(guān)期刊論文 前1條
1 李志剛;楊繼榮;;基于LINGO9·0軟件的混合離散優(yōu)化方法研究[J];機(jī)床與液壓;2007年01期
相關(guān)碩士學(xué)位論文 前2條
1 毛寧;求解離散優(yōu)化問(wèn)題的人工蜂群算法研究[D];大連海事大學(xué);2016年
2 李明;基于離散優(yōu)化問(wèn)題的分布估計(jì)算法及應(yīng)用研究[D];太原科技大學(xué);2013年
，本文編號(hào)：2441708
本文鏈接：http://www.sikaile.net/kejilunwen/zidonghuakongzhilunwen/2441708.html
最近更新
教材專著
