离散和声求解带启动时间批量流水线调度问题

分别在有等待和无等待的情况下,深入分析了带有启动时间的批量调度问题,以最小化最大完成时间为目标,提出了两种离散和声搜索算法。针对算法本质连续而问题离散的矛盾,对和声搜索算法进行改进。首先提出了基于工序的编码方式,采用inver-over和重组两种离散算子产生候选解的进化机制;并利用改进的NEH(NawazEnscore-Ham)方法进行初始化,产生的高质量和多样化的初始种群有效地指导了算法的进化方向,提高收敛速度;最后将一种简单而有效的局部邻域搜索方法嵌入到和声搜索算法中以增强其局部搜索能力。仿真实验和比较结果表明了所提算法的有效性。     

基于离散和声搜索与模拟退火的混合算法

和声搜索是一种启发式优化算法,对和声搜索算法进行离散化,使其能够适用于组合优化问题,就离散和声搜索算法进行两点改进,针对离散和声搜索算法容易陷入局部最优的缺陷,提出一种离散和声搜索与模拟退火算法的混合策略。实验结果表明,基于改进离散和声搜索与模拟退火的混合算法具有较高的求解质量。     

求解NWFS调度的改进和声搜索算法

以无等待流水车间(NWFS)总流水时间为优化目标,提出一种改进的和声搜索算法。建立NWFS调度优化的问题模型,设计总流水时间的快速评估方法。采用LPV规则实现离散问题的连续编码,给出改进的和声搜索算法对总流水时间执行优化,达到总流水时间的全局和局部最优。对标准算例做仿真,并在相同条件下与现有算法比较,验证该算法的可行性和有效性。     

基于混合差分进化算法的无等待流水车间总流水时间优化*

以调度的总流水时间为优化目标, 提出一种混合差分进化算法。 首先, 建立无等待流水车间调度的问题模型,并用快速方法评估总流水时间指标。 其次,采用LPV规则,实现离散问题的连续编码; 用差分进化算法对总流水时间指标执行优化;引入插入邻域和基于pairwise的局部搜索算法, 分别对差分进化算法产生的新个体和差分进化算法的最优解执行邻域搜索, 达到优化目标全局和局部的最优。 最后,通过计算标准算例, 并与其他算法比较, 验证该混合差分进化算法的有效性。     

求解零空闲流水线调度问题的和声退火算法

针对以最大完工时间为目标的零空闲流水线调度问题提出了和声退火算法。首先引入了基于ROV规则的编码方式,使和声搜索应用于离散问题,从初始化方法、参数调整、候选解的产生、和声记忆库的更新方法等四个方面对基本和声搜索算法进行了改进,基于此提出了改进的和声搜索算法;其次,结合和声搜索和模拟退火算法的优点,分别对和声搜索过程中的最优解、和声记忆库中的随机选中的解及一个新解分别进行模拟退火,提出了三种不同的和声退火算法。仿真实验表明所提算法的有效性和优越性。     

一种新的智能优化及其改进研究

研究了一种新的进化算法-和声搜索(HS)算法,针对其在处理复杂函数优化问题时容易陷入局部最优、收敛精度低的缺点,提出一种改进的和声搜索算法,算法在保留和声搜索的搜索机理的同时,把混合蛙跳算法中的局部搜索策略引入其中,维持了和声库的多样性,从而提高了对复杂问题的搜索效率.与同类算法相比,本文提出的和声搜索算法全局搜索能力强,收敛速度快,数值实验结果验证了算法的有效性和鲁棒性.     

基于改进离散和声算法的批量流水线调度研究

针对批量流水线调度问题,提出了以总流经时间为目标的改进离散和声算法。与基本的和声算法相比,该算法首先采用了基于工件序列的编码方式,使其直接应用于调度问题,同时运用NEH和SWAP方法产生初始和声库,保证了初始种群具有较高的质量和多样性。使用自适应和声微调概率参数和INSERT方法产生新解,提高了算法的优化性能。为了提高算法的局部搜索能力,结合交换扰动策略和插入邻域搜索算法给出了两种混合求解策略。仿真实验表明所提算法的有效性。     

全局竞争和声搜索算法

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

     

基于遗传和声算法求解函数优化问题*

针对遗传算法和和声搜索算法各自的特点,提出了一种新的搜索算法——遗传和声算法（GAHS）。新算法利用遗传算法改进了和声算法中和声记忆库初始解的产生方式,同时对和声算法中新解的产生方式也作了改进;将此改进算法应用到函数优化问题中,并分别对六个测试函数进行了仿真,用于验证算法的可行性。仿真结果表明,遗传和声算法提高了函数优化的搜索效率,具有较高的寻优性能和较强的跳出局部极小的能力。     

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

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

A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flow shop scheduling problem

In this paper, a local-best harmony search (HS) algorithm with dynamic sub-harmony memories (HM), namely DLHS algorithm, is proposed to minimize the total weighted earliness and tardiness penalties for a lot-streaming flow shop scheduling problem with equal-size sub-lots. First of all, to make the HS algorithm suitable for solving the problem considered, a rank-of-value (ROV) rule is applied to convert the continuous harmony vectors to discrete job sequences, and a net benefit of movement (NBM) heuristic is utilized to yield the optimal sub-lot allocations for the obtained job sequences. Secondly, an efficient initialization scheme based on the NEH variants is presented to construct an initial HM with certain quality and diversity. Thirdly, during the evolution process, the HM is dynamically divided into many small-sized sub-HMs which evolve independently so as to balance the fast convergence and large diversity. Fourthly, a new improvisation scheme is developed to well inherit good structures from the local-best harmony vector in the sub-HM. Meanwhile, a chaotic sequence to produce decision variables for harmony vectors and a mutation scheme are utilized to enhance the diversity of the HM. In addition, a simple but effective local search approach is presented and embedded in the DLHS algorithm to enhance the local searching ability. Computational experiments and comparisons show that the proposed DLHS algorithm generates better or competitive results than the existing hybrid genetic algorithm (HGA) and hybrid discrete particle swarm optimization (HDPSO) for the lot-streaming flow shop scheduling problem with total weighted earliness and tardiness criterion.     

A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem

In this paper, a discrete artificial bee colony (DABC) algorithm is proposed to solve the lot-streaming flow shop scheduling problem with the criterion of total weighted earliness and tardiness penalties under both the idling and no-idling cases. Unlike the original ABC algorithm, the proposed DABC algorithm represents a food source as a discrete job permutation and applies discrete operators to generate new neighboring food sources for the employed bees, onlookers and scouts. An efficient initialization scheme, which is based on the earliest due date (EDD), the smallest slack time on the last machine (LSL) and the smallest overall slack time (OSL) rules, is presented to construct the initial population with certain quality and diversity. In addition, a self adaptive strategy for generating neighboring food sources based on insert and swap operators is developed to enable the DABC algorithm to work on discrete/combinatorial spaces. Furthermore, a simple but effective local search approach is embedded in the proposed DABC algorithm to enhance the local intensification capability. Through the analysis of experimental results, the highly effective performance of the proposed DABC algorithm is shown against the best performing algorithms from the literature.     

An artificial bee colony algorithm approach for the team orienteering problem with time windows

This study addresses a highly constrained NP-hard problem called the team orienteering problem with time windows (TOPTW), which belongs to a well-known class of vehicle routing problems. This study proposes a relatively new technique called artificial bee colony (ABC) approach to solve the TOPTW. Moreover, considering that the number of studies for discrete optimization with an ABC algorithm is comparatively low, this study presents a new use of the ABC algorithm for a difficult discrete optimization problem. Additionally, this study introduces a new food source acceptance criterion and a new scout bee search behavior, both of which significantly contribute to the solution quality. The results show that the proposed method is effective, efficient, and comparable to other approaches.     

求解流水线调度问题的万有引力搜索算法

研究了以最大完工时间为目标的流水线调度问题,使用万有引力算法求解调度问题,提出了一种最大排序规则,利用物体间各个位置分量值存在的大小次序关系,并结合随机键编码的方法产生,将物体的连续位置转变成了一个可行的调度方案;提出了一种边界变异的策略使得越界的物体不再聚集在边界上,而是分布在边界附近的可行空间内,从而增加种群的多样性;结合交换算子和插入算子提出了一种新的局部搜索算法,有效地避免了算法陷入局部最优值,进一步提高了解的质量.最后证明了算法的收敛性,并且计算了算法的时间复杂度和空间复杂度,仿真实验说明了所得算法的有效性.     

一种求解旅行商问题的离散状态转移算法

本文提出了一种求解旅行商问题的离散状态转移算法,设计了交换、平移、对称等3种转移算子,讨论了算法的收敛性和时间复杂度等问题,研究了参数对算法的影响.实验结果表明,与模拟退火算法及蚁群算法等经典组合优化算法相比,该算法具有耗时短、寻优能力强等优点,这也表明了状态转移算法的适应性很好.     

An effective hybrid discrete differential evolution algorithm for the flow shop scheduling with intermediate buffers

In this paper, an effective hybrid discrete differential evolution (HDDE) algorithm is proposed to minimize the maximum completion time (makespan) for a flow shop scheduling problem with intermediate buffers located between two consecutive machines. Different from traditional differential evolution algorithms, the proposed HDDE algorithm adopted job permutation to represent individuals and applies job-permutation-based mutation and crossover operations to generate new candidate solutions. Moreover, a one-to-one selection scheme with probabilistic jumping is used to determine whether the candidates will become members of the target population in next generation. In addition, an efficient local search algorithm based on both insert and swap neighborhood structures is presented and embedded in the HDDE algorithm to enhance the algorithm’s local searching ability. Computational simulations and comparisons based on the well-known benchmark instances are provided. It shows that the proposed HDDE algorithm is not only capable to generate better results than the existing hybrid genetic algorithm and hybrid particle swarm optimization algorithm, but outperforms two recently proposed discrete differential evolution (DDE) algorithms as well. Especially, the HDDE algorithm is able to achieve excellent results for large-scale problems with up to 500 jobs and 20 machines.     

用于二维不规则排样的离散临界多边形模型

提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.新模型是只含有点和区间的简单模型,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地求解该问题.计算结果表明,基于离散临界多边型模型的排样算法是很有效的.     

VARIANCE-BASED HARMONY SEARCH ALGORITHM FOR UNIMODAL AND MULTIMODAL OPTIMIZATION PROBLEMS WITH APPLICATION TO CLUSTERING

This article presents a novel variance-based harmony search algorithm (VHS) for solving optimization problems. VHS incorporates the concepts borrowed from the invasive weed optimization technique to improve the performance of the harmony search algorithm (HS). This eliminates the main problem of constant parameter setting in the algorithm proposed recently and named as explorative HS. It uses the variance of a current population as well as presents a solution vector to improvise the harmony memory. In addition, the dynamic pitch adjustment operator is used to avoid solution oscillation. The proposed algorithm is evaluated on 14 standard benchmark functions of various characteristics. The performance of the proposed algorithm is investigated and compared with classical HS, an improved version of HS, the global best HS, self-adaptive HS, explorative HS, and the recently proposed state-of-art gravitational search algorithm. Experimental results reveal that the proposed algorithm outperforms the above-mentioned approaches. The effects of scalability, noise, harmony memory size, and harmony memory consideration rate have also been investigated with the proposed algorithm. The proposed algorithm is then employed for a data clustering problem. Four real-life datasets selected from the UCI machine learning repository have been used. The results indicate that the VHS-based clustering outperforms the existing well-known clustering algorithms.     

改进和声搜索算法及其在连续函数优化中的应用

针对一般和声搜索(HS)算法在求解连续函数优化问题时存在的困难,提出一种改进的多样化和声搜索(IDHS)算法。该算法借鉴模拟退火算法的思想对参数的更新方式作出调整,并且限制保存在和声记忆矩阵中的一致和声的数量以增加解的多样性。数值仿真结果表明,与其他几种传统的和声搜索算法相比,该方法进一步提高了计算精度和收敛速度,以及全局寻优能力。     

基于编码转换的离散演化算法设计与应用

为了利用演化算法求解离散域上的组合优化问题,借鉴遗传算法（GA）、二进制粒子群优化（BPSO）和二进制差分演化（HBDE）中的映射方法,提出了一种基于映射变换思想设计离散演化算法的实用方法——编码转换法（ETM）,并利用一个简单有效的编码转化函数给出了求解组合优化问题的离散演化算法一般算法框架A-DisEA.为了说明ETM的实用性与有效性,首先基于A-DisEA给出了一个离散粒子群优化算法（DisPSO）,然后分别利用BPSO、HBDE和DisPSO等求解集合联盟背包问题和折扣{0-1}背包问题,通过对计算结果的比较表明：BPSO、HBDE和DisPSO的求解性能均优于GA,这不仅说明基于ETM的离散演化算法在求解KP问题方面具有良好的性能,同时也说明利用ETM方法设计离散演化算法是一种简单且有效的实用方法.