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 harmony search algorithm for the blocking permutation flow shop scheduling problem

This paper proposes a hybrid modified global-best harmony search (hmgHS) algorithm for solving the blocking permutation flow shop scheduling problem with the makespan criterion. First of all, the largest position value (LPV) rule is proposed to convert continuous harmony vectors into job permutations. Second, an efficient initialization scheme based on the Nawaz-Enscore-Ham (NEH) heuristic is presented to construct the initial harmony memory with a certain level of quality and diversity. Third, harmony search is employed to evolve harmony vectors in the harmony memory to perform exploration, whereas a local search algorithm based on the insert neighborhood is embedded to enhance the local exploitation ability. Moreover, a new pitch adjustment rule is developed to well inherit good structures from the global-best harmony vector. Computational simulations and comparisons demonstrated the superiority of the proposed hybrid harmony search algorithm in terms of solution quality.     

多维多极值函数优化的和声退火算法

针对多极值实函数优化问题,本文结合和声搜索与模拟退火算法,提出了一种新的搜索算法,即和声退火算法。新算法保留了和声搜索的搜索机理,但对和声搜索中于和声记忆库外的搜索方法用超快速模拟退火算法作了改进,对和声记忆库内新解产生方法也作了相应的调整,从而提高了对多维问题的搜索效率。数值实验结果表明算法对和声搜索有明显的改进,收敛速度更快,跳出局部极值点的能力较强。新算法在解决多维多极值优化问题方面比遗传算法更具效率,值得进一步研究与推广应用。     

基于混合和声搜索算法求解竞争选址问题

针对竞争选址问题,提出一种新的混合和声搜索算法。混合和声搜索算法初始化和声记忆库时结合了贪婪算法,降低了初始解的不可行性概率。在寻优过程中,引入了鱼群算法的觅食行为,提高了算法跳出局部最优解的能力和收敛速度。即兴产生一个新的和声时,充分考虑了当前最优解的指导作用,提出了新的基因调整方法,增强了算法的探索能力。在竞争选址问题上对所提出的算法进行了测试,仿真结果验证了所提出算法的有效性。     

A novel global harmony search algorithm for reliability problems

Inspired by the swarm intelligence of particle swarm, a novel global harmony search algorithm (NGHS) is proposed to solve reliability problems in this paper. The proposed algorithm includes two important operations: position updating and genetic mutation with a small probability. The former enables the worst harmony of harmony memory to move to the global best harmony rapidly in each iteration, and the latter can effectively prevent the NGHS from trapping into the local optimum. Based on a large number of experiments, the proposed algorithm has demonstrated stronger capacity of space exploration than most other approaches on solving reliability problems. The results show that the NGHS can be an efficient alternative for solving reliability problems.     

和声搜索-分布估计混合算法求解多目标优化问题

针对和声搜索算法不能很好地求解多目标优化问题的缺陷,提出一种多目标和声搜索—分布估计混合算法(MHS-EDA)。该算法一方面利用分布估计的采样操作对和声记忆库内进行搜索,拓宽了和声记忆库内空间;另一方面对和声记忆库外进行外部档案搜索,实现群体间信息交换,从而提高了多目标和声算法的全局搜索能力。数值实验选取六个常用测试函数,并与多目标遗传算法、多目标分布估计算法、多目标和声搜索算法进行比较,测试结果表明提出的混合算法能够有效地解决多目标优化问题。     

A self-guided differential evolution with neighborhood search for permutation flow shop scheduling

The permutation flow shop scheduling problem (PFSSP) is one of the most widely studied production scheduling problems and a typical NP-hard combinatorial optimization problems as well. In this paper, a self-guided differential evolution with neighborhood search (NS-SGDE) is presented for the PFSSP with the objectives of minimizing the maximum completion time. Firstly, some constructive heuristics are incorporated into the discrete harmony search (DHS) algorithm to initialize the population. Secondly, a guided agent based on the probabilistic model is proposed to guide the DE-based exploration phase to generate the offspring. Thirdly, multiple mutation and crossover operations based on the guided agent are employed to explore more effective solutions. Fourthly, the neighborhood search based on the variable neighborhood search (VNS) is designed to further improve the search ability. Moreover, the convergence of NS-SGDE for PFSSP is analyzed according to the theory of Markov chain. Computational simulations and comparisons with some existing algorithms based on some widely used benchmark instances of the PFSSP are carried out, which demonstrate the effectiveness of the proposed NS-SGDE in solving the PFSSP.     

基于记忆库粒子群算法的海上协作搜寻计划制定

海上搜寻任务通常由多个设施协作完成。针对海上协作搜寻计划制定问题,提出一种记忆库粒子群算法。该算法利用组合优化策略和连续优化策略,首先为单个设施生成相应的备选解并构建记忆库,通过从记忆库中学习、随机生成两种方式生成新的备选解;然后采用网格法更新记忆库,每个网格中最多有一个备选解保存在记忆库中,保证记忆库中备选解的多样性,基于此对解空间进行有效的全局搜索;最后通过从记忆库中随机选择多个备选解组合生成初始协作搜寻方案,利用粒子群策略围绕质量较好的备选解进行有效的局部搜索。实验结果表明,在效率方面,所提算法运行时间较短,在获取最小方差的同时可提高1%~5%的任务成功率,可有效应用于海上协作搜寻计划制定。     

A self-adaptive multi-objective harmony search algorithm based on harmony memory variance

Although harmony search (HS) algorithm has shown many advantages in solving global optimization problems, its parameters need to be set by users according to experience and problem characteristics. This causes great difficulties for novice users. In order to overcome this difficulty, a self-adaptive multi-objective harmony search (SAMOHS) algorithm based on harmony memory variance is proposed in this paper. In the SAMOHS algorithm, a modified self-adaptive bandwidth is employed, moreover, the self-adaptive parameter setting based on variation of harmony memory variance is proposed for harmony memory considering rate (HMCR) and pitch adjusting rate (PAR). To solve multi-objective optimization problems (MOPs), the proposed SAMOHS uses non-dominated sorting and truncating procedure to update harmony memory (HM). To demonstrate the effectiveness of the SAMOHS, it is tested with many benchmark problems and applied to solve a practical engineering optimization problem. The experimental results show that the SAMOHS is competitive in convergence performance and diversity performance, compared with other multi-objective evolutionary algorithms (MOEAs). In the experiment, the impact of harmony memory size (HMS) on the performance of SAMOHS is also analyzed.     

An integrated search heuristic for large-scale flexible job shop scheduling problems

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop scheduling problem (JSP), where each operation is allowed to be processed by any machine from a given set, rather than one specified machine. In this paper, two algorithm modules, namely hybrid harmony search (HHS) and large neighborhood search (LNS), are developed for the FJSP with makespan criterion. The HHS is an evolutionary-based algorithm with the memetic paradigm, while the LNS is typical of constraint-based approaches. To form a stronger search mechanism, an integrated search heuristic, denoted as HHS/LNS, is proposed for the FJSP based on the two algorithms, which starts with the HHS, and then the solution is further improved by the LNS. Computational simulations and comparisons demonstrate that the proposed HHS/LNS shows competitive performance with state-of-the-art algorithms on large-scale FJSP problems, and some new upper bounds among the unsolved benchmark instances have even been found.     

基于动态行为选择的和声搜索算法

和声搜索算法是一种模拟音乐即兴创作过程的元启发式搜索,已成功应用于解决许多实际问题.针对高维函数优化问题,提出一种基于动态行为选择的和声搜索算法.在算法中新和声的即兴创作有3种策略,迭代过程中通过计算每个策略的即时价值和综合价值选择和声的即兴创作策略,并通过个体即兴创作策略选择方法提升寻优速度或避免陷入局部最优解.将所提出算法与9个改进和声搜索算法在22个基准函数上进行对比.实验结果表明,所提出算法具有较好的求解精度、稳定性和收敛速度,擅长于解决复杂的高维问题.     

改进的多目标和声搜索算法

针对和声搜索算法不能很好求解多目标优化问题的缺陷,引入邻域搜索算子,对和声记忆库内搜索到的分量进行扰动,对和声记忆库外进行Pareto邻域搜索,实现群体间信息交换,提高算法的全局搜索能力。数值实验选取4个常用测试函数并与NSGA-II、SPEA2、MOPSO 3个多目标算法进行比较,测试结果验证了改进算法的有效性。     

基于和声退火算法的多维函数优化*

在研究和声搜索对多维函数优化问题的基础上,结合传统的模拟退火算法,提出一种混合优化算法——和声退火算法。该算法改进了和声的搜索机制,选取合理的取值概率HMCR以及动态的微调概率PAR,在和声记忆库内随机搜索,获得较高质量的新和声;然后对新和声执行一次Metropolis算法,从而增强了全局探索能力,减小了陷入局部极小值的机会。仿真实验数据表明,算法明显优于和声搜索和模拟退火算法,具有较高的求解质量和效率。     

多样性保持的和声搜索算法及其TSP求解

为了改善和声记忆库群体多样性, 提高算法的全局寻优能力, 在度量群体多样性指标的基础上, 从参数动态调整方法、和声记忆库更新策略两个方面对基本和声搜索算法进行了改进, 提出了多样性保持的和声搜索算法, 并将该算法应用于TSP的求解。结合TSP问题特点, 设计了基于交换和插入算子的和声微调方法。实例优化结果表明, 改进后的算法不容易陷入局部最优, 优化性能显著提高。     

动态子和声算法求解无等待批量流水线问题

针对无等待批量流水线调度问题,根据和声算法的机理,提出了一种改进的和声算法对其进行求解。利用NEH和混沌序列相结合的方法产生初始解,并实现了和声向量与工序之间的转换;充分利用最优解,设计新的更新算子,为了避免陷入局部最优,引入了变异策略;结合蛙跳算法分组的特点,将和声库随机动态的分成了几个子和声;为平衡算法的全局开发和局部搜索的能力,对子和声中的最优解执行了局部搜索。通过仿真实验与其他几种算法进行比较,证明了算法的有效性。     

一种全局和声搜索算法求解绝对值方程

绝对值方程Ax-|x|=b是一个不可微的NP-hard问题。在假设矩阵A的奇异值大于1时, 给出了一个求解绝对值方程的全局和声搜索算法。新的和声搜索算法使用了位置更新和小概率变异策略, 实验结果表明, 该算法具有较强的全局搜索能力, 且收敛快、数值稳定性好、参数少等优点, 是求解绝对值方程的一种有效算法。     

基于变异和信息素扩散的多维背包问题的蚁群算法

针对蚁群算法在求解大规模多维背包问题时存在的迭代次数过多、精度不高的不足,提出一种新的高性能的蚁群求解算法.算法将信息素更新和随机搜索机制的改进相融合.首先,基于对较优解的偏爱,采用Top-k策略从每次迭代的k个解中挖掘出对象间的关联距离;其次,以对象为信源借助关联距离建立信息素的扩散模型,通过信息素扩散的耦合补偿,强化了蚂蚁间的协作和交流;最后,利用一种简单的变异策略对迭代的结果进行优化.在通用数据集上的大量实验表明:与最新的蚁群算法相比,新算法不仅能获得更好的最优解,而且收敛速度有显著的提高.     

混合灰狼优化算法求解柔性作业车间调度问题

将灰狼优化算法(GWO)用于柔性作业车间调度问题(FJSP),以优化最大完工时间为目标,提出一种混合灰狼优化算法(HGWO).首先,采用两段式编码方式,建立GWO连续空间与FJSP离散空间的映射关系;其次,设计种群初始化方法,保证算法初始解的质量;然后,嵌入一种变邻域搜索策略,加强算法的局部搜索能力,引入遗传算子,提升算法的全局探索能力;最后,通过实验数据验证HGWO算法在求解FJSP问题方面的有效性.     

一种基于最大最小策略和非均匀变异的萤火虫算法

针对多目标萤火虫算法勘探能力弱、求解精度差的问题,本文提出了一种基于最大最小策略和非均匀变异的萤火虫算法(HVFA-M).该算法首先引入Maximin策略,实现对外部档案的动态调整和对精英解的随机选择;其次,精英解结合当前最好解共同引导萤火虫进行全局搜索以扩大算法的搜索范围,提高算法的勘探能力,从而增加找寻全局最优解的...     

学习型和声搜索算法及其在0-1 背包问题中的应用

针对现有和声搜索算法存在的不足,提出一种学习型和声搜索算法(LHS).根据目标函数值的变化,自适应调整和声记忆考虑概率(HMCR);引入学习机制,加快算法的搜索速度;动态调节基音调整概率(PAR),增强算法的全局搜索能力.对16个标准函数的测试结果表明,所提出的LHS算法与其他4种和声搜索算法相比具有较好的效果.最后将改进算法应用于10个0-1背包问题和1个经典的50维背包实例,实验结果表明LHS算法优于其他算法.关键词:和声搜索算法;自适应;学习策略;搜索速度;0-1背包问题