Font Size: a A A

A Research On Artificial Bee Colony Algorithm For Solving Discrete Optimization Problems

Posted on:2017-05-06Degree:MasterType:Thesis
Country:ChinaCandidate:N MaoFull Text:PDF
GTID:2308330482479888Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
Artificial Bee Colony (ABC) algorithm is a new type of swarm intelligence optimization algorithm inspired by gathering honey, which draws many researchers’ attention owning to the characteristics of less control parameters, easier implementation, and succincter calculation. The ABC algorithm was first proposed for solving the problems of continuous optimization, continuous multi-objective optimization, and artificial neural network training. while there is an exploitable aspect in discrete optimization problems using this algorithm. For the purpose mentioned above, in this paper, the ABC algorithm was extended to process discrete optimization problems in typical application area.In this paper, the DABC algorithm was generated by the basic ABC algorithm which is processed with the discrete way, and was applied to solve software collaborative test task allocation problem based on crowdsourcing solving environment. Comparing with the task allocation method based on heuristic strategy, the result of DABC algorithm outperforms and reduce the cost of test task effectively.In our work, the discrete DABC algorithm was improved based on the research achievements of ABC algorithm, and there are the following three improved points:(1)to keep population’s diversity and improve optimizing capacity, selection strategy based on the reverse of the roulette was replaced by selection strategy based on artificial colony algorithm of roulette.(3)inspired by differential evolution algorithm and genetic operator, propose multidimensional variable disturbance neighborhood search strategy to improve the ability of searching globally optimal solution. The IDABC algorithm is improved based on the two points mentioned above, and verified its effectiveness by solving 0-1 knapsack problem using experiments. The experiments in this section proceed from the following two aspects:(1) verify the solving ability of algorithm by comparing the optimal solutions obtained by different algorithms. (2) the experiments verify the effect of the parameters by setting different values on the algorithm. (3) the experiments prove that the multidimensional variable disturbance neighborhood search strategy has the better ability of optimizing capacity and the faster convergence rate.At the end of this paper, based on IDABC algorithm proposed by us, design and implement the visual tool which is good at solving the different 0-1 knapsack problem posed by users and displaying the results generated in the intuitive way.
Keywords/Search Tags:Artificial Bee Colony algorithm, Discrete optimization problem, 0-1 knapsack problem, Task allocation, Crowdsouring testing
PDF Full Text Request
Related items