基于混合人工蜂群算法的多目标柔性作业车间调度问题研究

传统的优化算法在求解面对多目标柔性作业车间调度时,往往求解效率低且难以获得最优解。为了求解多目标柔性作业车间调度问题,设计了混合人工蜂群算法。种群的初始化采用了多种方法相结合的策略。在人工蜂群算法的不同阶段采用不同的搜索机制,在雇佣蜂阶段采用开发搜索,针对跟随蜂阶段蜜蜂跟随的对象的优秀解进行小幅度的更新,从而提高了搜索的表现。禁忌搜索与改进的人工蜂群算法相结合,有效的提升了获得最优解的概率。通过相关文献中的标准实例对设计的混合人工蜂群算法进行一系列求解测试,实验的结果有效的说明了算法在求解柔性作业车间调度问题时效果显著。通过求解结果对比表明人工蜂群算法的高效性和优越性。     

全局最优引导的差分演化二进制人工蜂群算法

针对基本二进制人工蜂群算法开采能力弱、收敛速度慢的缺点,提出一种全局最优引导的差分二进制人工蜂群算法。算法仿照粒子群优化,将全局最优参数引入二进制人工蜂群算法中以提高开采能力;同时受差分演化算法中“交叉”操作的启发,提出多维邻域搜索方式,加快收敛速度。采用0-1背包问题进行仿真,实验结果表明与传统算法相比,提出算法不仅寻优能力增强且收敛速度明显提高。对于10维背包问题,提出算法的收敛速度比基本二进制人工蜂群算法提高近10倍。     

Dynamic clustering with improved binary artificial bee colony algorithm

One of the most well-known binary (discrete) versions of the artificial bee colony algorithm is the similarity measure based discrete artificial bee colony, which was first proposed to deal with the uncapacited facility location (UFLP) problem. The discrete artificial bee colony simply depends on measuring the similarity between the binary vectors through Jaccard coefficient. Although it is accepted as one of the simple, novel and efficient binary variant of the artificial bee colony, the applied mechanism for generating new solutions concerning to the information of similarity between the solutions only consider one similarity case i.e. it does not handle all similarity cases. To cover this issue, new solution generation mechanism of the discrete artificial bee colony is enhanced using all similarity cases through the genetically inspired components. Furthermore, the superiority of the proposed algorithm is demonstrated by comparing it with the basic discrete artificial bee colony, binary particle swarm optimization, genetic algorithm in dynamic (automatic) clustering, in which the number of clusters is determined automatically i.e. it does not need to be specified in contrast to the classical techniques. Not only evolutionary computation based algorithms, but also classical approaches such as fuzzy C-means and K-means are employed to put forward the effectiveness of the proposed approach in clustering. The obtained results indicate that the discrete artificial bee colony with the enhanced solution generator component is able to reach more valuable solutions than the other algorithms in dynamic clustering, which is strongly accepted as one of the most difficult NP-hard problem by researchers.     

ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times

To date, the topic of unrelated parallel machine scheduling problems with machine-dependent and job sequence-dependent setup times has received relatively little research attention. In this study, a hybrid artificial bee colony (HABC) algorithm is presented to solve this problem with the objective of minimizing the makespan. The performance of the proposed HABC algorithm was evaluated by comparing its solutions to state-of-the-art metaheuristic algorithms and a high performing artificial bee colony (ABC)-based algorithm. Extensive computational results indicate that the proposed HABC algorithm significantly outperforms these best-so-far algorithms. Since the problem addressed in this study is a core topic for numerous industrial applications, this article may help to reduce the gap between theoretical progress and industrial practice.     

A new bee colony optimization algorithm with idle-time-based filtering scheme for open shop-scheduling problems

Open shop scheduling problems (OSSP) are one of the most time-consuming works in scheduling problems. Currently, many artificial intelligence algorithms can reduce the problem-solving time to an acceptable time range, and even can further downsize the range of solution space. Although the range of solution space is technically downsized, in most scheduling algorithms every partial solution still needs to be completely solved before this solution can be evaluated. For example, if there is a schedule with 100 operations, then all 100 operations must be scheduled before the scheduler can evaluate its fitness. Therefore, the time–cost of unnecessary partial solutions is no longer saved.In order to improve the weakness stated above, this paper proposes a new bee colony optimization algorithm, with an idle-time-based filtering scheme, according to the inference of “the smaller the idle-time, the smaller the partial solution”, and the “smaller the makespan (Cmax) will be”. It can automatically stop searching a partial solution with insufficient profitability, while the scheduler is creating a new scheduling solution, and therefore, save time–cost for the remaining partial solution. The architecture and details of the bee colony optimization heuristic rule is detailed in this paper.     

A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops

Obtaining an optimal solution for a permutation flowshop scheduling problem with the total flowtime criterion in a reasonable computational timeframe using traditional approaches and optimization tools has been a challenge. This paper presents a discrete artificial bee colony algorithm hybridized with a variant of iterated greedy algorithms to find the permutation that gives the smallest total flowtime. Iterated greedy algorithms are comprised of local search procedures based on insertion and swap neighborhood structures. In the same context, we also consider a discrete differential evolution algorithm from our previous work. The performance of the proposed algorithms is tested on the well-known benchmark suite of Taillard. The highly effective performance of the discrete artificial bee colony and hybrid differential evolution algorithms is compared against the best performing algorithms from the existing literature in terms of both solution quality and CPU times. Ultimately, 44 out of the 90 best known solutions provided very recently by the best performing estimation of distribution and genetic local search algorithms are further improved by the proposed algorithms with short-term searches. The solutions known to be the best to date are reported for the benchmark suite of Taillard with long-term searches, as well.     

考虑多目标的柔性工艺与调度集成优化算法

针对工艺规划与车间调度集成优化问题,在考虑零件的加工工序柔性、工序次序柔性及加工机器柔性的基础上,以最大完工时间、总加工成本和总拖期时间为优化目标,对多目标柔性工艺与车间调度集成问题建模,提出一种基于改进人工蜂群算法的多目标柔性工艺与车间调度集成优化策略,并提出邻域变异操作以及全局交叉操作,对种群进行更新。引入Pareto方法,通过对适应度评价、贪婪准则、Pareto最优解集构造和保存以及解得多样性维护等方面进行改进,设计了一种基于Pareto方法的多目标人工蜂群算法。最后,通过采用基本人工蜂群算法及改进人工蜂群算法对六个工件、五台机床的柔性工艺与车间调度集成问题进行优化,验证了改进算法的有效性。     

The continuous artificial bee colony algorithm for binary optimization

Artificial bee colony (ABC) algorithm, one of the swarm intelligence algorithms, has been proposed for continuous optimization, inspired intelligent behaviors of real honey bee colony. For the optimization problems having binary structured solution space, the basic ABC algorithm should be modified because its basic version is proposed for solving continuous optimization problems. In this study, an adapted version of ABC, ABC_bin for short, is proposed for binary optimization. In the proposed model for solving binary optimization problems, despite the fact that artificial agents in the algorithm works on the continuous solution space, the food source position obtained by the artificial agents is converted to binary values, before the objective function specific for the problem is evaluated. The accuracy and performance of the proposed approach have been examined on well-known 15 benchmark instances of uncapacitated facility location problem, and the results obtained by ABC_bin are compared with the results of continuous particle swarm optimization (CPSO), binary particle swarm optimization (BPSO), improved binary particle swarm optimization (IBPSO), binary artificial bee colony algorithm (binABC) and discrete artificial bee colony algorithm (DisABC). The performance of ABC_bin is also analyzed under the change of control parameter values. The experimental results and comparisons show that proposed ABC_bin is an alternative and simple binary optimization tool in terms of solution quality and robustness.     

基于混合人工蜂群算法的并行测试任务优化研究

并行测试技术可以同时进行多个任务的测试,提高资源利用率,节约测试成本;并行测试调度问题是一种复杂的组合优化问题,是并行测试技术的核心要素;并行测试系统作为并行测试技术的载体,自身的性能和求解效率尤其重要;对并行测试完成时间极限定理进行了研究,建立了并行测试任务调度的数学模型,分析了传统元启发式算法求解并行测试问题的不足,提出了基于动态规划的递归搜索技术和人工蜂群算法相结合的混合人工蜂群算法,并采用整数规划精确算法和遗传算法对混合人工蜂群算法进行验证;得出结论采用混合人工蜂群算法进行并行测试任务的调度节约了接近50%的时间,降低了约20%的硬件资源占用,提高了测试效率,可以满足工程实际的应用。     

求解车辆路径问题的人工蜂群算法

采用人工蜂群算法对车辆路径问题进行求解,给出食物源的自然数编码方法,并采用邻域倒位方法生成候选食物源。应用算法求解了多个车辆路径问题的实例,并将结果与其它一些启发式算法进行了比较和分析。计算结果表明,人工蜂群算法可以有效求解车辆路径问题,同时也为算法求解其它一些组合优化问题提供了有益思路。     

Fast artificial bee colony and its application to stereo correspondence

Nature-inspired meta-heuristics have gained popularity for solutions to many real-world complex problems, and the artificial bee colony algorithm is one of the most powerful optimisation methods among meta-heuristics. However, inefficient exploitation of onlooker bees prevents the artificial bee colony algorithm from finding the final result accurately and efficiently for complex problems. In this paper, a novel optimisation method is proposed based on the artificial bee colony algorithm. The proposed optimisation method adaptively exploits onlooker bees over generations. In addition, the proposed optimisation method is applied to a stereo-matching problem to minimise the segment-based integer energy function, which is also introduced in this paper. The experimental results show that the proposed optimisation method outperforms state-of-the-art population-based meta-heuristics, such as the genetic algorithm, differential evolution, conventional artificial bee colony, and clonal selection algorithm, for benchmark functions as well as for the stereo-matching problem.     

基于地标特征和元学习方法推荐最适用优化算法

设计并实证研究一种基于地标特征和元学习方法推荐最佳优化算法的实现框架.地标特征摒弃了传统的问题简单特征、统计特征和信息理论特征复杂的提取过程,通过简化运行算法并仅以算法的相对性能表现作为问题特征集.在此基础上,利用元学习方法训练建模并针对新问题作出算法推荐.为验证推荐效果,以多模式资源约束的项目调度问题(MRCPSP)为优化对象,以人工蜂群、蚁群、粒子群和禁忌搜索4种元启发式算法作为推荐对象,分别使用人工神经网络、k最近邻、决策树以及随机森林4种元学习方法建立推荐元模型.计算结果表明,多种元学习方法均指向相近的推荐准确率,平均稳定在70%以上,最高可达95%.基于地标特征和元学习方法实现优化算法推荐是一个值得进一步探讨的新方向.     

具有混合群智能行为的萤火虫群优化算法研究

萤火虫群优化算法是一种新型的群智能优化算法,基本的萤火虫群优化算法存在收敛精度低等问题。为了提高算法的性能,借鉴蜂群和鸟群的群体智能行为,改进萤火虫群优化算法的移动策略。运用均匀设计调整改进算法的参数取值。若干经典测试问题的实验仿真结果表明,引入混合智能行为大幅提升了算法的优化性能。     

The improvement of glowworm swarm optimization for continuous optimization problems

Glowworm swarm optimization (GSO) algorithm is the one of the newest nature inspired heuristics for optimization problems. In order to enhances accuracy and convergence rate of the GSO, two strategies about the movement phase of GSO are proposed. One is the greedy acceptance criteria for the glowworms update their position one-dimension by one-dimension. The other is the new movement formulas which are inspired by artificial bee colony algorithm (ABC) and particle swarm optimization (PSO). To compare and analyze the performance of our proposed improvement GSO, a number of experiments are carried out on a set of well-known benchmark global optimization problems. The effects of the parameters about the improvement algorithms are discussed by uniform design experiment. Numerical results reveal that the proposed algorithms can find better solutions when compared to classical GSO and other heuristic algorithms and are powerful search algorithms for various global optimization problems.     

A modified artificial bee colony approach for the 0-1 knapsack problem

The 0-1 knapsack problem (KP01) is one of the classical NP-hard problems in operation research and has a number of engineering applications. In this paper, the BABC-DE (binary artificial bee colony algorithm with differential evolution), a modified artificial bee colony algorithm, is proposed to solve KP01. In BABC-DE, a new binary searching operator which comprehensively considers the memory and neighbour information is designed in the employed bee phase, and the mutation and crossover operations of differential evolution are adopted in the onlooker bee phase. In order to make the searching solution feasible, a repair operator based on greedy strategy is employed. Experimental results on different dimensional KP01s verify the efficiency of the proposed method, and it gets superior performance compared with other five metaheuristic algorithms.     

混合离散人工蜂群算法求解含不相关并行机的分布式柔性流水线调度

研究每阶段含不相关并行机的分布式柔性流水线调度问题.考虑顺序相关准备时间和工件动态到达时间,以最小化总加权提前/拖期惩罚为目标建立整数规划模型,提出一种融合离散差分进化算法、变邻域下降算法和局域搜索的混合离散人工蜂群算法以获取近优解.该算法采用基于工厂-工件号的编码以及基于机器最早空闲时间的动态解码机制,通过随机规则和均衡分派策略生成初始工厂-工件序列群,在引领蜂阶段引入离散差分进化算法产生优质工厂-工件序列,在跟随蜂阶段利用变邻域下降算法在被选择序列附近继续搜索以得到邻域序列,在侦察蜂阶段设计基于关键/非关键工厂间插入的局域搜索提高算法搜索能力.通过仿真实验测试不同规模的算例,实验结果表明,所提出的混合离散人工蜂群算法表现出较好的求解性能.     

基于新型人工蜂群算法的分布式不相关并行机调度

针对考虑预防性维修的分布式不相关并行机调度问题,提出了一种新型人工蜂群算法(ABC)以最小化最大完成时间.为了获得高质量的计算结果,该算法将整个种群划分为1个引领蜂群和3个跟随蜂群,跟随蜂有自己的蜜源且采用新方式跟随引领蜂, 4种蜂群运用彼此各异的搜索策略产生新解以增强种群多样性,提出一种新策略处理侦查蜂的搜索,并利用优化数据更新整个种群.通过大量仿真实验验证了新型ABC在求解所研究问题方面的有效性和优势.     

基于ABC-SA混合算法的群控电梯优化调度

为解决电梯群控系统（Elevator group control system,EGCS）时间和能耗性能不理想的问题,提出一种基于改进人工蜂群的电梯群控多目标优化调度算法。首先,针对EGCS控制目标复杂性,建立具有多评价指标的群控电梯调度模型,依据该模型的适应度值进行合理派梯选择;其次,引入模拟退火准则优化基本人工蜂群算法结构以解决算法易陷入局部最优解的问题,使用混合改进的人工蜂群算法进行多目标优化调度。仿真结果表明,所提算法在侯梯时间、乘梯时间和停靠次数三个性能指标上对比基本人工蜂群算法均有所提高,有效说明该方法在求解柔性多目标群控电梯优化调度时具有一定的优越性。     

A food source-updating information-guided artificial bee colony algorithm

Artificial bee colony algorithm simulates the foraging behavior of honey bees, which has shown good performance in many application problems and large-scale optimization problems. To model the bees foraging behavior more accurately, a food source-updating information-guided artificial bee colony algorithm is proposed in this paper. In this algorithm, some food source-updating information obtained during optimizing time is introduced to redefine the foraging strategies of artificial bees. The proposed algorithm has been tested on a set of test functions with dimension 30, 100, 1000 and compared with some recently proposed related algorithms. The experimental results show that the performance of artificial bee colony algorithm is significantly improved for both rotated problems and large-scale problems. Compared with the related algorithms, the proposed algorithm can achieve better or competitive performance on most test functions and greatly better performance on parts of test functions.

     

基于改进二进制人工蜂群算法的多用户检测器

最优多用户检测(OMD)技术可以达到理论上的最小错误概率,但已经证明它是一个非确定多项式(NP)问题。作为一种新型的群智能算法,人工蜂群(ABC)算法已被广泛用于各种优化问题,但传统二进制人工蜂群算法具有收敛速度过慢、易陷入局部最优等缺点。针对这一缺点,提出了一种改进二进制人工蜂群算法并将其用于求解最优多用户检测问题。算法简化了初始化的过程,采用单维求反的邻域搜索策略,计算量与最优多用户检测相比明显降低。仿真结果表明,提出的多用户检测方案在抗多址干扰和抗“远近”效应能力方面与传统检测方案相比,都有显著提高。