求解离散优化问题的人工蜂群算法研究
发布时间：2019-03-16 16:09
【摘要】：人工蜂群算法(Artificial Bee Colony Algorithm, ABC)是一种受蜜蜂采蜜行为启发产生的新型群体智能优化算法。由于控制参数少、易于实现、计算简洁等特点,近年来ABC算法备受研究者关注。不过ABC算法提出时最早用于求解连续函数优化、连续多目标优化、人工神经网络训练等问题,对于离散优化问题的应用研究并不太多。离散优化问题是众多优化问题的一个重要分支且具有广泛的工业应用需求,为此本文将扩展ABC算法使其能够处理典型应用领域的离散优化问题。本文将基本ABC算法离散化后得到DABC算法,并应用它求解基于众包环境下的软件协同测试任务分配问题。在与基于启发式策略的任务分配方法进行对比中,DABC算法的分配结果更优,可以有效的降低进行测试任务所需要的成本。本文在总结学者对ABC算法研究工作的基础上对离散化后的DABC算法进行了改进,具体改进点为：(1)使用基于反向轮盘赌的选择策略代替基本人工蜂群算法的轮盘赌选择策略以保持种群多样性,增强算法的寻优能力；(2)受差分演化算法和遗传算子的启发,提出了一种多维变量扰动邻域搜索策略以提高算法的获得全局最优解的能力。基于以上两点改进得到]DABC算法并将IDABC算法应用于求解0-1背包问题中,通过实验验证了算法的有效性。本节实验从三方面出发：(1)通过与不同算法所获得的最优解情况进行对比验证算法的求解能力,(2)实验验证设置不同的参数值对算法的影响,(3)实验验证了提出的多维变量扰动邻域搜索策略对于算法寻优能力以及加快算法收敛都有所提高。在本文的最后,又基于提出IDABC算法设计和实现了求解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
本文编号：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.
【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【相似文献】
相关期刊论文 前1条
1 李志刚;杨继荣;;基于LINGO9·0软件的混合离散优化方法研究[J];机床与液压;2007年01期
相关硕士学位论文 前2条
1 毛宁;求解离散优化问题的人工蜂群算法研究[D];大连海事大学;2016年
2 李明;基于离散优化问题的分布估计算法及应用研究[D];太原科技大学;2013年
，本文编号：2441708
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2441708.html
