混合二进制差异演化算法解0-1背包问题

为了有效求解0-1背包问题,提出一种混合二进制差异演化算法.该算法基于差异演化算法框架,采用二进制编码,通过增加映射操作、S型变换操作和逆映射操作等3种新的操作,将差异演化算法从实数优化领域推广至离散优化领域,成功解决了差异演化算法直接求解离散优化问题时的计算不封闭问题.此外,在每次迭代求解时,利用贪婪变换法对违反约束条件的不可行解进行变换,使其成为可行解.不同规模的背包问题的数值实验结果表明了该算法的有效性与适用性.     

蜜蜂进化型的类电磁机制算法

针对类电磁机制算法求解高维问题耗时的缺点,提出了一种蜜蜂进化型类电磁机制算法。在该算法中,种群的最优粒子作为蜂王与被选的每个粒子（雄蜂）以概率进行交叉操作,增强了对种群最优粒子所包含信息的开采能力。为了避免算法过早收敛,结合邻域搜索技术来改进种群中的粒子,提高了算法的勘探能力。理论分析表明新算法以概率1收敛到问题的最优解。实验结果表明,蜜蜂进化型类电磁机制算法是一种提高类电磁机制算法性能的有效改进算法。     

混合差异演化算法求解多维背包问题

提出了一种求解多维0-1背包问题的混合差异演化算法,算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品的贪婪算法和基于二进制编码的差异演化算法。对10个测试算例进行了仿真试验,结果表明文章提出的算法可以快速找到这些测试算例的最优解,是求解多维背包问题的一种有效方法。     

求解0-1背包问题的改进排挤遗传算法

提出了两种用于求解0-1背包问题的改进排挤遗传算法PFCGA和GCGA,PFCGA使用惩罚函数和排挤操作使算法能够比较稳定地求得最优解,GCGA把排挤遗传和贪婪算法相结合,对种群中非法染色体表示的不可行解进行修复使其变为可行解,对非优可行解进行修正使其尽量靠近最优解,GCGA在保证求解精度的前提下加快求解速度。通过仿真实验和比较分析结果表明,PFCGA和GCGA能够获得很高的求解精度和正确率,是求解0-1背包问题的有效算法。     

求解0/1背包问题的离散差分进化算法

0/1背包问题是实际中经常遇到的一类经典NP难组合优化问题.针对0/1背包问题,提出一种融合贪婪变换的离散差分进化算法.该算法中通过模2运算来实现变异操作;为了满足约束上限,融合了贪婪变换;为了防止早熟,采用了在进化若干代后重新初始化种群的策略.经数值实验表明,该算法在求解0/1背包问题时是可行的,有效的,比单纯的贪婪算法,融合贪婪变换的粒子群优化算法及融合贪婪变换的遗传算法更加稳健,良好.     

基于改进差分进化的车辆路径优化算法

差分进化算法是一种具有记忆个体最优解和种群内部信息共享的特点的新型进化算法,本质上可看做是一种基于实数编码的、具有保优思想的贪婪遗传算法。针对具有NP难的车辆路径优化问题,提出了一种改进的差分进化算法。利用贪心算法产生初始种群,定义合法化修复变异个体的方法,采用改进的顺序交叉,并在变异操作之后,加入新的选择机制。使用Matlab进行了算法的实现,实验结果表明了改进DE算法能够高效地解决VRP问题。     

混合差异演化算法在背包问题中的应用

提出了一种用于求解0-1背包问题的混合差异演化算法,详细阐述了该算法求解背包问题的具体操作过程。算法主要使用了两个思想策略,即启发式贪婪算法和基于二进制编码的差异演化算法。通过对其它文献中仿真实例的计算和结果对比,表明该算法对求解0-1背包问题的有效性,这对差异演化算法解决其它离散问题会有些帮助。     

求解多背包问题的混合蛙跳算法

针对多背包问题,提出一种改进的离散混合蛙跳算法。算法中对青蛙个体采用十进制整数编码方式,应用遗传算法中的交叉操作来对个体进行更新,扩展了传统混合蛙跳算法模型。将改进的算法用于多背包问题求解,仿真实验表明了所提算法的有效性。     

连续背包问题贪婪算法最优解的实现

贪婪法是用于设计数值最优化问题的算法之一,它能应用于求解不同领域的多种问题,如应用于集装箱问题的背包贪婪算法。贪婪法不追求最优解,不要回溯,只希望得到较为满意的解,使用贪婪法不能保证一定得到最优解。本文通过对连续背包问题不同贪婪准则的讨论,给出了一个贪婪算法最优解实现的C程序。     

改进的细菌觅食优化算法求解0-1背包问题

细菌觅食优化算法作为一种新兴的智能优化算法,一般用来解决连续域的问题。为了解决离散域问题,提出了一种改进的细菌觅食优化算法。采用线性递减的思想和随机的游动长度代替固定步长和随机游动方向,改进了趋向性操作方案,并将其应用于解决0-1背包问题。将改进的细菌觅食优化算法与遗传算法、离散粒子群优化算法及基本的离散化细菌觅食优化算法分别在小规模和大规模的0-1背包问题上进行了仿真比较,表明了改进的细菌觅食优化算法能取得较好的效果,寻优能力强。     

面向自动组卷问题的改进类电磁算法

类电磁算法（EM）中局部搜索是按一定步长进行线性搜索,在这个范围内寻找个体在某一维上的最优值。由于步长的限定,求得的该维上最优值可能远离实际的最优值。采用遗传算法（GA）中选择因子和交叉因子可以很好地解决这一问题。在组卷系统中,通过基于遗传算法改进的类电磁算法（Based Genetic Electromagnetism-like Mechanism Algorithm,GEM）与GA算法以及采用线性局部搜索的EM算法实验的比较,证明该算法有更高的组卷效率。     

资源受限项目调度问题的改进类电磁算法

在资源受限项目调度中,工序必须在特定时间窗口中执行。为此,在类电磁(EM)算法的基础上提出一种基于变邻域搜索(VNS)的改进类电磁算法(IEMA)。采用VNS作为IEMA的局部搜索策略,对EM算法中的电荷、合力以及粒子解移动的方式做改进。将IEMA应用于求解标准问题库PSPLIB,并与EM、IEM以及基于邻域搜索的改进类电磁算法IEM-NS进行比较分析,仿真结果表明,IEMA具有更好的求解性能。     

求全局最优的类电磁机制算法

针对类电磁机制算法中数据溢出、计算量过大的问题,改进了电量计算公式和合力计算公式,引入了函数值最小下界,增加了粒子过滤公式,从而得到一种新类电磁机制算法。从测试标准测试函数与经典类电磁算法的比较可看出,新算法收敛速度快,并从数值上验证了该算法的可行性和有效性。     

A new experiential learning electromagnetism-like mechanism for numerical optimization

The Electromagnetism-like Mechanism algorithm (EM) is a population-based search algorithm which has shown good achievements in solving various types of complex numerical optimization problems so far. To date, the study on experience-based local search mechanism is relatively limited, and there is no study in the literature to integrate experience-based features into the EM. This work introduces an experience-learning feature into the EM for the first time. A new Experiential Learning Electromagnetism-like Mechanism algorithm (ELEM) is proposed in this paper. The ELEM is integrated with two new components. The first component is the particle memory concept which allows the particles to remember the details of their past search experience. The second component is the experience analysing and decision making mechanisms which enables the particles to adjust the settings for the coming iterations. Combining the advantages of this strong exploitation strategy and the powerful exploration mechanism of the EM, the proposed ELEM strikes a good balance in providing well diversified solutions with high accuracy. The results from extensive numerical experiments carried out using 21 challenging test functions show that ELEM is able to provide very competitive solutions and significantly outperforms other optimization techniques. It can thus be concluded from the results that the proposed ELEM performs well in solving high dimensional numerical optimization problems.     

一种改进的类电磁机制算法

文章以无约束优化问题为研究对象,分析了类电磁机制算法的原理,即模拟了电磁场中带电粒子之间的吸引排斥机制,通过该机制使得粒子朝着最优粒子移动。针对原算法中存在的运算量大、收敛速度慢等问题,提出了一种改进的类电磁机制算法。新算法采用归一化目标函数值方法,简化了电量计算公式;同时引入自适应移动算子,将粒子的优劣和迭代的过程体现在粒子的移动过程中,使得算法在搜索过程中能朝着更精确的解移动。实验证明,改进后的算法具有更好的收敛效果和更高的执行效率。     

A hybrid Electromagnetism-like Mechanism/tabu search procedure for the single machine scheduling problem with a maximum lateness objective

This paper presents a hybrid meta-heuristic search procedure to solve the well-known single machine scheduling problem to minimize the maximum lateness over all jobs, where precedence relations may exist between some of the jobs. The hybridization consists of a well-designed balance between the principles borrowed from an Electromagnetism-like Mechanism algorithm and the characteristics used in a tabu search procedure. The Electromagnetism-like Mechanism (EM) algorithm follows a search pattern based on the theory of physics to simulate attraction and repulsion of solutions in order to move towards more promising solutions. The well-known tabu search enhances the performance of a local search method by using memory structures by prohibiting visited solutions during a certain time of the search process. The hybridization of both algorithms results in an important trade-off between intensification and diversification strategies. These strategies will be discussed in detail. To that purpose, a new set of data instances is used to compare different elements of the hybrid search procedure and to validate the performance of the algorithm.     

求解约束优化问题的新方法

提出了用于解决约束优化问题的新的类电磁机制算法,针对约束优化问题,利用惩罚函数法,构造了新的适应度函数,将约束问题转化为无约束问题求解,结合类电磁机制算法的寻优特点,设计了适合于问题特点的局部搜索过程,并重新定义了粒子的电荷和力的计算公式,以使在算法实现过程中,引导不可行点逐步向可行点转化,并最终找到问题的最优解。数值模拟结果验证了算法的有效性。     

求解广义背包问题的贪心DS_BPSO算法

首先针对演化算法求解背包问题定义了贪心变换的概念,并给出了该变换的一种有效实现算法;然后将此算法与文献[5]中提出的具有双重结构编码的二进制粒子群优化算法(DS_BPSO)相结合,提出了一种解决广义背包问题GKP(General Knapsack Problem)的快速算法:基于贪心变换的DS_BPSO算法(GDS_BPSO).利用该算法求解文献[3,6]中的著名背包实例,给出了该背包实例的目前最好结果.此外,对于随机生成的大规模背包实例,通过与文献[3]中的HGA算法对比计算表明:GDS_BPSO算法是求解广义背包问题的一种高效方法.     

Shuffled frog leaping algorithm and its application to 0/1 knapsack problem

This paper proposes a modified discrete shuffled frog leaping algorithm (MDSFL) to solve 01 knapsack problems. The proposed algorithm includes two important operations: the local search of the ‘particle swarm optimization’ technique; and the competitiveness mixing of information of the ‘shuffled complex evolution’ technique. Different types of knapsack problem instances are generated to test the convergence property of MDSFLA and the result shows that it is very effective in solving small to medium sized knapsack problems. Further, computational experiments with a set of large-scale instances show that MDSFL can be an efficient alternative for solving tightly constrained 01 knapsack problems.     

求解0-1背包问题的烟花算法

为了克服现有方法在求解0-1背包问题时存在的缺陷,提出了一种改进的烟花算法.在给出0-1背包问题的数学模型后,利用Kent混沌映射对基本烟花算法的解初始化以使初始位置分布更加均匀,同时引入Sigmoid函数得到渐变的爆炸半径使得算法的求解精度与搜索速度达到某种平衡,用改进的烟花算法来对其进行求解.通过对典型测试函数和0-1背包问题的求解结果说明了所提出的改进烟花算法求解精度更高,性能更加稳定.