一种求解背包问题的混合差异演化算法

为增强差异演化算法在求解背包问题时的局部搜索能力,提出拉马克-鲍德温混合差异演化算法。该算法采用双种群协同进化,以差异演化算法为主体,在演化过程中分别引入拉马克进化和鲍德温效应2种局部搜索算子,引导种群进化方向。仿真实验结果表明,该算法求解精度高,收敛速度快,能够高效求解背包问题。     

基于记忆库拉马克进化算法的作业车间调度

多种群遗传算法相比遗传算法在性能上能够有所提高,但对具有较多局部最优解的作业车间调度问题,多种群遗传算法仍然难以改善易陷入局部最优解和局部搜索能力差的缺点.因此,提出了一种求解作业车间调度问题的新算法MGA-MBL(multi-population genetic algorithm based on memory-base and Lamarckian evolution for job shop scheduling problem).MGA-MBL在多种群遗传算法的基础上通过引入记忆库策略,不但使子种群间的个体可以进行信息交换,而且有利于保持整个种群的多样性;通过构造基于拉马克进化机制的局部搜索算子来提高多种群遗传算法中子种群进化的局部搜索能力.由于MGA-MBL采用了全局寻优能力较强的模拟退火算法对记忆库中的个体进行优化,从而缓解了多种群遗传算法易陷入局部最优解的问题,并提高了算法求解作业车间调度问题的性能.对著名的benchmark数据进行测试,实验结果证实了MGA-MBL在求解作业车间调度问题上的有效性.     

基于多种群差分进化的多目标优化算法

针对差分进化算法(Differential Evolution Algorithm,DE)求解多目标优化问题时易陷入局部最优的问题,设计了一种双向搜索机制,它通过对相反进化方向产生的两个子代个体进行评价,来增强DE算法的局部搜索能力;设计了多种群机制,它可令各子群独立进化一定次数再执行全局进化,以完成子群间进化信息的交流,这一方面降低了算法陷入局部最优的风险,另一方面增强了Pareto解集的多样性,使Pareto前沿面的解集分布更为均匀。实验结果表明,相比于NSGA-II等同类算法,所提方法在搜索Pareto最优解时效率更高,并且Pareto最优解集的精度及分布程度比前者更好。     

新颖的阻塞流水车间调度量子差分进化算法

针对阻塞流水车间调度问题(BFSP),提出了一种新颖的量子差分进化(NQDE)算法,用于最小化最大完工时间。该算法将量子进化算法(QEA)与差分进化(DE)相结合,设计一种新颖的量子旋转机制控制种群进化方向,增强种群多样性;采用高效的基于变邻域搜索的量子进化算法(QEA-VNS)协同进化策略增强算法的全局搜索能力,进一步提高解的质量。基于Taillard's benchmark实例仿真,结果表明,所提算法在最优解数量上明显高于目前较好的启发式算法--INEH,改进了110个实例中64个实例的当前最优解;在性能上也优于目前有效的元启发式算法--新型蛙跳算法(NMSFLA)和混合量子差分进化(HQDE),产生最优解的平均百分比偏差(ARPD)均下降约6%。NQDE算法适合大规模阻塞流水车间调度问题。     

协同进化混合蛙跳算法

针对基本混合蛙跳算法收敛速度慢、求解精度低且易陷入局部最优的问题,提出了一种新的协同进化混合蛙跳算法。该算法在局部搜索策略中,对子群内最差个体的更新引入平均值的同时充分利用最优个体的优秀基因,可有效扩大搜索空间,增加种群的多样性;同时对子群内少量的较差青蛙采取交互学习策略向邻近子群的最优个体交流学习,增加子群间交互的频繁性,提高信息共享程度,有利于进化。在全局迭代过程中采取精英群自学习进化机制,以对精英空间进行精细搜索,获得更优解,进一步提升算法的全局寻优能力,正确导向算法的进化。实验结果表明,所提算法在七个测试函数中均能收敛到最优解0,成功率为100%,优于其他对比算法。所提算法可有效避免陷入早熟收敛,极大地提高了算法的收敛速度和优化精度。     

基于Memetic框架的混合粒子群算法

提出一种Memetic框架下的混合粒子群优化算法(HM-PSO)。针对粒子群算法的搜索结果,该算法采用基于拉马克学习的局部搜索策略帮助具有一定改进能力的个体提高收敛速度,同时利用禁忌策略帮助可能陷入局部最优的个体跳出局部最优点。HM-PSO算法在加速个体收敛的同时提高算法搜索的多样性,避免陷入局部最优。实验结果表明,改进拉马克学习策略有效可行,HM-PSO算法具有良好的全局寻优性能。     

混合模式搜索的分布式memetic差分进化算法

针对差分进化（DE）算法存在的早熟收敛与搜索停滞的问题,提出memetic分布式差分进化（DDE）算法。将memetic算法的思想融入到差分进化算法中,采用分布式的种群结构以及memetic算法中的混合策略,前者将初始种群分为多个子种群,子种群间根据冯·诺依曼拓扑结构周期性地实现信息交流,后者将差分进化算法作为进化的主要框架,模式搜索作为辅助手段,从而平衡算法的探索与开发能力。所提算法充分利用了模式搜索和差分进化算法的优势,建立了有效的搜索机制,增强了算法摆脱局部最优的能力,能够满足搜索过程对种群多样性及收敛速度的需求。将所提算法与几种先进的差分进化算法相比较,对标准测试函数进行优化的实验结果显示：所提算法在解的质量和收敛性能方面,均优于其他几种相比较的先进的差分进化算法。     

基于反向学习的自适应差分进化算法

为解决差分进化（DE）算法过早收敛与搜索能力低的问题,讨论对控制参数的动态调整,提出一种基于反向学习的自适应差分进化算法。该算法通过反向精英学习机制来增强种群的局部搜索能力,获取精确度更高的最优个体;同时,采用高斯分布随机性提高单个个体的开发能力,通过扩充种群的多样性,避免算法过早收敛,整体上平衡全局搜索与局部寻优的能力。采用CEC 2014中的6个测试函数进行仿真实验,并与其他差分进化算法进行对比,实验结果表明所提算法在收敛速度、收敛精度及可靠性上表现更优。     

求解置换流水线调度问题的混合离散果蝇算法

针对置换流水线调度问题,提出了一种新颖的混合离散果蝇算法.算法每一代进化包括4个搜索阶段:嗅觉搜索、视觉搜索、协作进化和退火过程.在嗅觉搜索阶段,采用插入方式生成邻域解;在视觉搜索阶段,选择最优邻域解更新个体;在协作进化阶段,基于果蝇个体间的差分信息产生引导个体;在退火操作阶段,以一定概率接受最优引导个体从而更新种群.同时,通过试验设计方法对算法参数设置进行了分析,并确定了合适的参数组合.最后,通过基于标准测试集的仿真结果和算法比较验证了所提算法的有效性和鲁棒性.     

一种基于多Agent的进化多目标优化算法

将进化多Agent系统引入多目标优化问题求解,通过Agent的局部搜索机制及Agent种群的协同进化机制来寻求Pareto最优解。在设计的进化算法当中借鉴了人工生命系统中的一些基本方法,如能量、小生境和迁移机制等。实例表明通过该进化算法求得Pareto最优解集具有很高的效率。     

Distributed memetic differential evolution with the synergy of Lamarckian and Baldwinian learning

As a population-based optimizer, the differential evolution (DE) algorithm has a very good reputation for its competence in global search and numerical robustness. In view of the fact that each member of the population is evaluated individually, DE can be easily parallelized in a distributed way. This paper proposes a novel distributed memetic differential evolution algorithm which integrates Lamarckian learning and Baldwinian learning. In the proposed algorithm, the whole population is divided into several subpopulations according to the von Neumann topology. In order to achieve a better tradeoff between exploration and exploitation, the differential evolution as an evolutionary frame is assisted by the Hooke–Jeeves algorithm which has powerful local search ability. We incorporate the Lamarckian learning and Baldwinian learning by analyzing their characteristics in the process of migration among subpopulations as well as in the hybridization of DE and Hooke–Jeeves local search. The proposed algorithm was run on a set of classic benchmark functions and compared with several state-of-the-art distributed DE schemes. Numerical results show that the proposed algorithm has excellent performance in terms of solution quality and convergence speed for all test problems given in this study.     

A HYBRID METAHEURISTIC FOR THE SINGLE-MACHINE TOTAL WEIGHTED TARDINESS PROBLEM

This article presents a new hybrid algorithm for combinatorial optimization that combines differential evolution (DE) with variable neighborhood search (VNS). DE (a population heuristic for optimization over continuous search spaces) is used as global optimizer for solution evolution guiding the search toward the optimal regions of the search space; VNS (a random local search heuristic based on the systematic change of neighborhood) is used as a local optimizer performing a sequence of local changes on individual DE solutions until a local optimum is found. The effectiveness of a DE-VNS approach is demonstrated on the solution of the single-machine total weighted tardiness scheduling problem. The concepts of Lamarckian and Baldwinian learning are also investigated and discussed. Experiments on known benchmark data sets show that DE-VNS with Lamarckian learning can produce high-quality schedules in a rather short computation time. DE-VNS uses a self-adapted mechanism for tuning the required control parameters, a critical feature rendering it applicable to real-life scheduling problems.     

Memetic algorithm using multi-surrogates for computationally expensive optimization problems

In this paper, we present a multi-surrogates assisted memetic algorithm for solving optimization problems with computationally expensive fitness functions. The essential backbone of our framework is an evolutionary algorithm coupled with a local search solver that employs multi-surrogate in the spirit of Lamarckian learning. Inspired by the notion of ‘blessing and curse of uncertainty’ in approximation models, we combine regression and exact interpolating surrogate models in the evolutionary search. Empirical results are presented for a series of commonly used benchmark problems to demonstrate that the proposed framework converges to good solution quality more efficiently than the standard genetic algorithm, memetic algorithm and surrogate-assisted memetic algorithms.     

A competent memetic algorithm for complex scheduling

We face the job shop scheduling problem with sequence dependent setup times and makespan minimization by memetic algorithm. This algorithm combines a classic genetic algorithm with a local searcher. The performance of the local searcher relies on the combination of a tabu search algorithm with a neighborhood structure termed N ^S that are thoroughly described and analyzed. Also, two evolution models are considered: Lamarckian and Baldwinian evolution. We report results from an experimental study across conventional benchmark instances showing that the proposed algorithm outperforms the current state-of-the-art methods and that Lamarckian evolution is better than Baldwinian evolution.     

动态适应布谷鸟搜索算法

介绍一种新的生物启发算法—–布谷鸟搜索(CS)及其相关的L′evy飞行搜索机制.为了进一步提高算法的适应性,将反馈引入算法框架,建立了CS算法参数的闭环控制系统.将Rechenberg的1/5法则作为进化的评价指标,引入学习因子平衡种群的多样性和集中性,提出动态适应布谷鸟算法(DACS).最后,通过数值实验验证了所提出算法的有效性.     

全局竞争和声搜索算法

提出一种全局竞争和声搜索(GCHS) 算法, 给出随机局部平均和声和全局平均和声的概念, 建立竞争搜索机制, 实现每次迭代产生两个和声向量并进行竞争选择. 设计自适应全局调整和局部学习策略, 平衡算法的局部搜索和全局搜索, 详细分析参数HMS、HMCR和PAR对算法优化性能的影响. 数值结果表明, GCHS 算法在精度、收敛速度和鲁棒性方面比和声搜索算法及最近文献中提出的7 种优秀改进和声搜索算法要好.

     

基于动态学习策略的群集蜘蛛优化算法

为了提高群集蜘蛛优化(SSO) 算法的性能, 提出一种基于动态学习策略的群集蜘蛛优化(DSSO) 算法. 该算法通过群体协作过程中学习因子的动态选择, 平衡算法的搜索能力和勘探能力; 采用随机交叉策略和云模型改进协作过程个体更新方式, 在维持种群多样性的同时尽量提高收敛速度. 基于标准测试函数的仿真实验表明, DSSO 算法可有效避免早熟收敛, 在收敛速度和收敛精度上较标准SSO 算法和其余4 种较具代表性的优化算法均有显著提高.

     

Balancing exploration and exploitation in memetic algorithms: A learning automata approach

One of the problems with traditional genetic algorithms (GAs) is premature convergence, which makes them incapable of finding good solutions to the problem. The memetic algorithm (MA) is an extension of the GA. It uses a local search method to either accelerate the discovery of good solutions, for which evolution alone would take too long to discover, or reach solutions that would otherwise be unreachable by evolution or a local search method alone. In this paper, we introduce a new algorithm based on learning automata (LAs) and an MA, and we refer to it as LA‐MA. This algorithm is composed of 2 parts: a genetic section and a memetic section. Evolution is performed in the genetic section, and local search is performed in the memetic section. The basic idea of LA‐MA is to use LAs during the process of searching for solutions in order to create a balance between exploration performed by evolution and exploitation performed by local search. For this purpose, we present a criterion for the estimation of success of the local search at each generation. This criterion is used to calculate the probability of applying the local search to each chromosome. We show that in practice, the proposed probabilistic measure can be estimated reliably. On the basis of the relationship between the genetic section and the memetic section, 3 versions of LA‐MA are introduced. LLA‐MA behaves according to the Lamarckian learning model, BLA‐MA behaves according to the Baldwinian learning model, and HLA‐MA behaves according to both the Baldwinian and Lamarckian learning models. To evaluate the efficiency of these algorithms, they have been used to solve the graph isomorphism problem. The results of computer experimentations have shown that all the proposed algorithms outperform the existing algorithms in terms of quality of solution and rate of convergence.     

基于自主学习和精英群的多子群粒子群算法

为了提高动态多子群粒子群算法中粒子学习的自主性,提出一种基于自主学习和精英群的粒子群算法.该算法借鉴教育心理学自主学习的理念,用基础群中粒子自主选择学习对象的操作代替子群的重组操作,并通过精英群局部搜索的配合来达到寻优的目的.将所提出的算法应用于6个测试函数,并与动态多子群PSO等算法进行了比较,比较结果表明,新算法在提高收敛速度、精度和寻优时间等方面具有良好的性能。