Flexible job shop scheduling using hybrid differential evolution algorithms

This paper proposes hybrid differential evolution (HDE) algorithms for solving the flexible job shop scheduling problem (FJSP) with the criterion to minimize the makespan. Firstly, a novel conversion mechanism is developed to make the differential evolution (DE) algorithm that works on the continuous domain adaptive to explore the problem space of the discrete FJSP. Secondly, a local search algorithm based on the critical path is embedded in the DE framework to balance the exploration and exploitation by enhancing the local searching ability. In addition, in the local search phase, the speed-up method to find an acceptable schedule within the neighborhood structure is presented to improve the efficiency of whole algorithms. Extensive computational results and comparisons show that the proposed algorithms are very competitive with the state of the art, some new best known solutions for well known benchmark instances have even been found.     

A hybrid harmony search algorithm for the flexible job shop scheduling problem

In this paper, a novel hybrid harmony search (HHS) algorithm based on the integrated approach, is proposed for solving the flexible job shop scheduling problem (FJSP) with the criterion to minimize makespan. First of all, to make the harmony search (HS) algorithm adaptive to the FJSP, the converting techniques are developed to convert the continuous harmony vector to a kind of discrete two-vector code for the FJSP. Secondly, the harmony vector is mapped into a feasible active schedule through effectively decoding the transformed two-vector code, which could largely reduce the search space. Thirdly, a resultful initialization scheme combining heuristic and random strategies is introduced to make the initial harmony memory (HM) occur with certain quality and diversity. Furthermore, a local search procedure is embedded in the HS algorithm to enhance the local exploitation ability, whereas HS is employed to perform exploration by evolving harmony vectors in the HM. To speed up the local search process, the improved neighborhood structure based on common critical operations is presented in detail. Empirical results on various benchmark instances validate the effectiveness and efficiency of our proposed algorithm. Our work also indicates that a well designed HS-based method is a competitive alternative for addressing the FJSP.     

粒子群与多种群元胞遗传混合优化算法

元胞遗传算法通过限定个体之间的相互作用邻域提高算法的全局收敛率,但在一定程度降低搜索效率。文中提出一种粒子群与多种群元胞遗传混合优化算法。首先将群体分割成多个相互之间没有邻域关系的元胞子种群,适度降低算法的选择压力,从而更好地保持种群的多样性。算法的变异操作被粒子群算法替代,使得局部搜索能力明显提高。元胞群体分割和粒子群变异较好地均衡全局探索和局部寻优之间的关系。分析混合算法的选择压力和多样性变化规律。实验结果表明,该算法在保证搜索效率较高的同时还显著提高元胞遗传算法的全局收敛率且稳定性得到明显改善。     

A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times

A hybrid estimation of distribution algorithm (EDA) with iterated greedy (IG) search (EDA-IG) is proposed for solving the unrelated parallel machine scheduling problem with sequence-dependent setup times (UPMSP-SDST). For makespan criterion, some properties about neighborhood search operators to avoid invalid search are derived. A probability model based on neighbor relations of jobs is built in the EDA-based exploration phase to generate new solutions by sampling the promising search region. Two types of deconstruction and reconstruction as well as an IG search are designed in the IG-based exploitation phase. Computational complexity of the algorithm is analyzed, and the effect of parameters is investigated by using the Taguchi method of design-of-experiment. Numerical tests on 1640 benchmark instances are carried out. The results and comparisons demonstrate the effectiveness of the EDA-IG. Especially, the bestknown solutions of 531 instances are updated. In addition, the effectiveness of the properties is also demonstrated by numerical comparisons.      

A copula-based hybrid estimation of distribution algorithm for m-machine reentrant permutation flow-shop scheduling problem

Aiming at the m-machine reentrant permutation flow-shop scheduling problem (MRPFSSP), a copula-based hybrid estimation of distribution algorithm (CHEDA) is presented to minimize the makespan criterion. Firstly, we establish both the operation-based model and the graph model for MRPFSSP, and then several inherent properties about critical path and blocks are proposed and analyzed. Secondly, the copula theory is utilized to build CHEDA’s probability model (i.e., the joint distribution function, JDF) to efficiently extract the useful information from the excellent individuals. Thirdly, the global search based on the JDF model and a new population sampling method is designed to find the promising sub-regions in the total solution space. Fourthly, a problem-dependent local search based on the critical path and blocks is embedded into CHEDA to enhance the local exploitation ability. Finally, simulation experiments and comparisons demonstrate the effectiveness of the proposed CHEDA.     

动态小生境半径两阶段多模态差分进化算法

针对多模态优化问题, 提出一种动态小生境半径两阶段多模态差分进化算法. 基于构象空间退火思想, 设计一种两阶段退火策略来动态调整小生境半径, 并根据退火过程将整个优化过程分为两个阶段. 在第1 阶段, 通过差分限制变异策略生成高质量的新个体来维持种群的多样性, 促进多模收敛; 在第2 阶段, 利用种子邻近变异策略对已探测到的生境高度搜索, 加快算法的收敛速度. 实验结果表明, 所提出算法能够有效实现从全局探测到局部增强的自适应平滑过渡, 是一种有效的多模态优化算法.

     

一种多策略混合的粒子群优化算法

针对传统粒子群优化算法在解决一些复杂优化问题时易陷入局部最优且收敛速度较慢的问题,提出一种多策略混合的粒子群优化算法(Hybrid Particle Swarm Optimization with Multiply Strategies,HPSO)。该算法利用反向学习策略产生反向解群,扩大粒子群搜索的范围,增强算法的全局勘探能力;同时,为避免种群陷入局部最优,算法对种群中部分较差的个体实施柯西变异,以产生远离局部极值的个体,而对群体中较好的个体施以差分进化变异,以增强算法的局部开采能力。对这3种策略进行了有机结合以更好地平衡粒子群算法全局勘探和局部开采的能力。将HPSO算法与其他3种知名的粒子群算法在10个标准测试函数上进行了性能比较实验,结果表明HPSO算法在求解精度和收敛速度上具有较显著的优势。     

一种求解多维背包问题的混合分布估计算法

针对多维背包问题（MKP）,提出一种基于分布估计算法的混合求解算法,该算法基于优势种群构建概率模型,并基于概率模型采样产生新个体;同时,提出一种基于MKP问题信息的修复机制,有效修复采样后种群中的不可行解．另外,设计了一种自适应的局部搜索操作,以增强算法的局部搜索能力,基于标准测试集的仿真结果和算法比较验证了所提出的混合算法的有效性和鲁棒性．     

不等式约束的非线性规划混合遗传算法

针对带不等式约束的非线性规划问题,提出了一个混合遗传算法。该算法分为全局探测和局部开采两个阶段,全局探测阶段是通过在有潜力的小生境内嵌入单纯形搜索,快速确定有前景的区域;而局部开采阶段则是在最有前景的区域进行单纯形搜索。该算法增强了局部搜索能力并同时保持种群的多样性,有效地解决了遗传算法的过早收敛和局部搜索能力弱的问题。典型非线性规划算例验证了混合算法的效率、精度和可靠性。     

一种协调勘探和开采的遗传算法：收敛性及性能分析

提出了一种新的遗传算法结构。在该结构中,每一代的新种群由保留种 群、繁殖种群的随机种群三部分组成,而它们的相对数量则由不同的参数进行控制,这体现了该算法在运行过程中对搜索空间勘探和开采操作的协调和权衡。通过把该算法建模为齐次的有限Markov链,该文证明了该算法具有全局收敛性。对试验数据的分析表明,该算法能够有效协调算法对问题解空间的勘探和开采操作,因而在处理复杂问题时表现出较高的性能。     

An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem

In this paper, an effective hybrid algorithm based on estimation of distribution algorithm (EDA) is proposed to solve the multidimensional knapsack problem (MKP). With the framework of EDA, the probability model is built with the superior population and the new individuals are generated based on probability model. In addition, an updating mechanism of the probability model is proposed and a mechanism for initializing the probability model based on the specific knowledge of the MKP is also proposed to improve the convergence speed. Meanwhile, an adaptive local search is proposed to enhance the exploitation ability. Furthermore, the influences of parameters are investigated based on Taguchi method of design of experiment and the importance of repair operator is also studied via simulation testing and comparisons. Finally, numerical simulation is carried out based on the benchmark instances, and the comparisons with some existing algorithms demonstrate the effectiveness of the proposed algorithm.     

针对混合变量优化问题的协同进化蚁群优化算法

针对由连续变量和分类变量构成的混合变量优化问题（MVOP）,采用协同进化策略来对混合变量决策空间进行搜索,提出了一种协同进化蚁群优化算法（CACOA_MV）。CACOA_MV分别采用连续和离散蚁群优化（ACO）策略生成连续和分类变量子种群,通过合作者来对连续和分类变量子向量进行评价,分别对连续和分类变量子种群进行更新来实现对混合变量决策空间的高效协同搜索。进一步地,利用信息素平滑机制增强对分类变量解空间的全局探索能力,并设计了一种面向协同进化框架的“最佳+随机合作者”的重启策略来提高协同搜索效率。与混合变量的蚁群（ACO_MV）算法和种群规模线性变小的差分进化-蚁群混合变量优化算法（L-SHADE_ACO）的比较表明,CACOA_MV能够进行更有效的局部开发,从而提高最终结果在目标空间中的近似精度;与基于集合的混合变量差分进化算法（DE_MV）相比较,CACOA_MV能够在决策空间中更好地逼近全局最优解,具有更好的全局探索能力。综上,采用协同进化机制的CACOA_MV能有效保持全局探索和局部开发的平衡,从而具有更好的寻优性能。     

多目标粒子群优化算法在柔性车间调度中的应用

将粒子群优化(Particle Swarm Optimization,PSO)算法和混沌搜索方法结合在一起,提出一种求解多目标柔性作业车间调度问题(Flexible job shop scheduling problem,FJSP)的新算法,利用混沌对PSO的参数进行自适应优化来有效平衡算法的全局搜索和局部开挖能力,并采用混沌局部优化策略来改善算法的搜索性能.此外,为了搜索到问题的所有非劣解,采用基于模糊逻辑的适应度函数来评价粒子.对于四个典型FJSP实例的实验验证了算法的可行性和有效性.     

基于混合微粒群优化的多目标柔性Job- shop 调度

应用传统方法求解多目标柔性Job-shop调度问题是十分困难的,微粒群优化采用基于种群的搜索方式,融合了局部搜索和全局搜索,具有很高的搜索效率.模拟退火算法使用概率来避免陷入局部最优,整个搜索过程可由冷却表来控制.通过对这两种算法的合理组合,建立了一种快速且易于实现的新的混合优化算法.实例计算以及与其他算法的比较说明,该算法是求解多目标柔性Job-shop调度问题的可行且高效的方法.     

聚类佳点集交叉的约束优化混合进化算法

提出一种基于聚类佳点集多父代交叉和自适应约束处理技术的混合进化算法用于求解约束优化问题.新算法的主要特点是:在搜索机制方面,利用佳点集方法构造初始化种群,使个体能够均匀地分布在整个搜索空间.然后根据父代个体的相似度将种群个体进行聚类分析,从聚类中随机选择个体进行佳点集多父代交叉操作,利用多个父代个体所携带的信息产生新的具有代表性的子代个体,能够维持和增加种群的多样性.另外,引入局部搜索策略以提高算法局部搜索能力和收敛速度.在约束处理技术上,新算法引入了一个自适应约束处理技术,即根据当前种群中可行解的比例自适应选择不同的个体比较准则.通过15个标准测试函数验证了新算法的有效性.     

多策略调和的布谷鸟搜索算法

布谷鸟搜索（CS）算法是一种新型的群智能算法,结构简单且寻优能力较强,但存在勘探与开采不平衡以及易陷入局部极值的问题。提出一种多策略调和的布谷鸟搜索（MSRCS）算法,基于概率规则选择由自适应步长和改进解更新方法组成的调和策略对布谷鸟个体进行更新,其中自适应步长引导布谷鸟在更好的方向上寻优,3种改进的解更新方法分别从自身邻域、当前最优个体和随机位置3个角度对勘探和开采进行调和,从而提升全局搜索和局部搜索在迭代过程中的适应性。在CEC2013测试集的28个基准函数上的实验结果表明,MSRCS算法至少有12个测试函数优于原始CS及其7种改进算法且排名第一,在求解单峰、多峰和组合函数问题时寻优能力更强,同时相比于3种经典群智能优化算法具有更快的收敛速度和更高的解精度。     

利用条件概率和Gibbs抽样技术为分布估计算法构造通用概率模型

本文针对传统分布估计算法在建立概率模型时面临的各种困难,提出一种基于条件概率和Gibbs抽样的概率模型,能有效改进分布估计算法的通用性.使用该模型的分布估计算法利用进化过程中有前途的优秀个体构造出多个监督学习样本集,并对每个样本集估计出对应分量的条件概率,再使用这一组条件概率进行Gibbs抽样产生新的个体替代种群中的劣等个体.通过仿真实验表明,改进后的算法能够求解出可加性降解函数的全局最优解,表现出较强的全局优化能力.     

基于共轭增强策略的差分进化算法

为了平衡差分进化算法的全局探测能力和局部搜索能力,提出基于共轭增强策略的差分进化算法.首先,根据个体适应度信息设计基于轮盘赌的个体选择策略,选取适应值较差的个体组建子种群;然后,基于个体的时间和空间知识设计共轭增强方向,在不丧失全局探测能力的前提下实现子种群的局部增强,以提高算法的局部搜索能力;最后,18个标准测试函数的实验结果表明,所提算法在计算代价、可靠性及收敛速度方面均优于所介绍的主流改进差分进化算法和非差分进化算法.     

耦合横纵向个体更新策略的改进MVO算法

为提高多元宇宙优化算法(MVO)的全局探索和局部开采性能,提出一种耦合横纵向个体更新策略的改进MVO算法(IMVO).横向更新策略是建立在宇宙种群层级的一种水平迁移进化机制,通过引入加权学习因子保证子代个体同时向多个父代宇宙继承位置信息,以改善种群的个体多样性和算法全局探索性能,适定性修正虫洞存在概率表达以保证种群个体间的充分信息交互;纵向更新策略是基于宇宙个体层级的一种纵向自我学习进化机制,根据最优宇宙历史信息,通过模拟认知的历史遗忘记忆特性实现记忆均值邻域的再开采,以增强算法局部开采性能.最后通过数值实验验证不同加权学习因子函数对算法性能的差异性影响,改进算法的优化性能和算法稳健性等.     

结合禁忌搜索的改进粒子群优化算法

为提高粒子群优化算法的全局搜索和局部开采能力,提出一种结合禁忌搜索(TS)的改进粒子群优化算法。在搜索过程中,以线性递增的概率对最优粒子实施随机扰动,在全局搜索收敛到一定程度后,引入TS算法进行局部搜索,使算法快速收敛到全局最优解。分析结果表明,该算法收敛精度较高,能有效克服早熟收敛问题。