【摘要】：人工蜂群算法(Artificial Bee Colony Algorithm, ABC)是一種受蜜蜂采蜜行為啟發(fā)產(chǎn)生的新型群體智能優(yōu)化算法。由于控制參數(shù)少、易于實現(xiàn)、計算簡潔等特點,近年來ABC算法備受研究者關注。不過ABC算法提出時最早用于求解連續(xù)函數(shù)優(yōu)化、連續(xù)多目標優(yōu)化、人工神經(jīng)網(wǎng)絡訓練等問題,對于離散優(yōu)化問題的應用研究并不太多。離散優(yōu)化問題是眾多優(yōu)化問題的一個重要分支且具有廣泛的工業(yè)應用需求,為此本文將擴展ABC算法使其能夠處理典型應用領域的離散優(yōu)化問題。本文將基本ABC算法離散化后得到DABC算法,并應用它求解基于眾包環(huán)境下的軟件協(xié)同測試任務分配問題。在與基于啟發(fā)式策略的任務分配方法進行對比中,DABC算法的分配結(jié)果更優(yōu),可以有效的降低進行測試任務所需要的成本。本文在總結(jié)學者對ABC算法研究工作的基礎上對離散化后的DABC算法進行了改進,具體改進點為：(1)使用基于反向輪盤賭的選擇策略代替基本人工蜂群算法的輪盤賭選擇策略以保持種群多樣性,增強算法的尋優(yōu)能力；(2)受差分演化算法和遺傳算子的啟發(fā),提出了一種多維變量擾動鄰域搜索策略以提高算法的獲得全局最優(yōu)解的能力。基于以上兩點改進得到]DABC算法并將IDABC算法應用于求解0-1背包問題中,通過實驗驗證了算法的有效性。本節(jié)實驗從三方面出發(fā)：(1)通過與不同算法所獲得的最優(yōu)解情況進行對比驗證算法的求解能力,(2)實驗驗證設置不同的參數(shù)值對算法的影響,(3)實驗驗證了提出的多維變量擾動鄰域搜索策略對于算法尋優(yōu)能力以及加快算法收斂都有所提高。在本文的最后,又基于提出IDABC算法設計和實現(xiàn)了求解0-1背包問題的可視化求解工具,用以方便使用者對不同0-1背包問題進行求解并以直觀的方式展示出問題的解。
[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.
【學位授予單位】：大連海事大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP18

【相似文獻】

相關期刊論文 前1條

1 李志剛;楊繼榮;;基于LINGO9·0軟件的混合離散優(yōu)化方法研究[J];機床與液壓;2007年01期

相關碩士學位論文 前2條

1 毛寧;求解離散優(yōu)化問題的人工蜂群算法研究[D];大連海事大學;2016年

2 李明;基于離散優(yōu)化問題的分布估計算法及應用研究[D];太原科技大學;2013年

，

本文編號：2441708