混合模拟退火及分散搜索优化过道布置问题

针对过道布置问题的求解复杂性,提出了一种混合模拟退火及分散搜索算法。该算法通过引入模拟退火操作进一步优化参考集中的解,以提高获得全局最优解的概率。设计了包含高质量和多样性解的双层参考集,扩大了搜索范围,避免算法陷入局部最优。同时采用动态参考集更新方法,及时替换参考集中质量或多样性较差的解,加快算法的收敛速度,并改进子集产生方法,避免产生重复的解,从而提高算法的求解效率。应用所提算法对24个不同规模的测试问题进行验算与对比,结果表明所提算法的求解质量与平稳性均优于基本模拟退火算法和分散搜索算法,且较已有的4种方法更具求解优势。     

考虑面积成本的双目标环形过道布置建模及改进禁忌搜索优化

针对现代建筑结构的形式多样化和面积成本在总成本中的占比越来越大等问题，建立了考虑面积成本的双目标环形过道布置问题的数学模型，并对考虑面积成本下的双目标环形过道布置问题的总成本进行优化.结合问题和模型特点，提出了一种加入动态禁忌长度和变异操作的改进禁忌搜索算法.所提算法随着迭代次数的增加，动态禁忌长度不断变化，从而缩小了搜索空间，提高了解的集中性，并融合了变异操作使其跳出局部最优，扩大了算法搜索范围.通过对不同规模实例的测试验证了算法的可行性.通过将所提算法与基本禁忌搜索算法进行对比，结果表明了改进算法的有效性和优越性.     

烟花算法求解JSP问题的研究

烟花算法是一种新型智能优化算法,该算法模拟烟花在空中爆炸产生火花这一过程。烟花算法的求解过程包含两种机制：产生爆炸火花,从而实现算法的局部和全局寻优过程;产生高斯变异火花,从而增加种群的多样性以便将优良个体遗传到下一代。通过设计四个参数实验,分析了主要参数对算法求解能力的影响,找出求解作业车间调度问题的较优参数。最后通过对作业车间调度的标准问题进行仿真对比实验,证明了烟花算法求解作业车间调度问题的有效性和稳定性。     

应用混沌烟花算法求解置换流水车间问题

改进烟花算法求解置换流水车间问题。用最大位置法编码,将连续变量映射到离散空间。引入动态半径因子,平衡局部搜索与全局搜索。精英个体混沌搜索,进一步挖掘个体信息。用锦标赛策略替代原有的选择算子,群体中的优良个体被选择的概率增大。通过正交实验选择合适参数,求解Car类和Rec类基准问题。与基本烟花算法、萤火虫算法和粒子群算法的对比实验说明,改进后的混沌烟花算法在寻优率、寻优速度等上具有一定的优势,是求解置换流水车间问题的有效工具。     

求解N-车探险问题的Memetic烟花算法

{{\baselinestretch     

改进离散烟花算法求解旅行商问题的研究

旅行商问题是一个经典的组合优化难题,它具有重要的理论研究价值以及实际应用意义.针对此问题提出一种基于改进选择策略的离散烟花算法,将上一代适应度值最小的火花保留,同时加入动态参数自适应调整选择数目和概率,将最优火花和动态选择火花作为子代,该选择方式兼顾了适应度大小及子代选择的优劣性,并且使算法能够跳出局部最优增强了算法的全局搜索能力,保证了种群的多样性.实验表明了改进后的算法的优化程度及可行性.     

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

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

烟花算法求解非线性方程组

烟花算法是最近提出的一种效率较高的优化算法,已被用于求解众多的优化问题.给出利用烟花算法求解非线性方程组的方法.实验表明,所提出的算法对于求解变量耦合的非线性方程组比其他算法占有优势,进一步分析存在优势的原因.     

A fast two-stage hybrid meta-heuristic algorithm for robust corridor allocation problem

The optimisation of the corridor allocation problem (CAP) belongs to the optimisation of the efficiency of the automated production line. The goal is to reduce the material handling cost (MHC) in the production process through a reasonable layout of the facilities, so as to save expenses for the enterprise. In recent years, with the acceleration of market changes, product design and production process adjustments have become more frequent, and more attention has been paid to the research on the layout of facilities under the condition of changes in the flow of materials between production facilities over time. On the basis of the CAP model, this paper considers the optimisation problem of row layout when the flow of materials between facilities fluctuates in a certain range. The new model can be utilised to obtain the overall optimisation solution under the condition of the floating material flow matrix, so as to achieve the goal of optimising the total MHC in the entire production process. As the new model introduces more variables and intermediate parameters, a two-stage solution method is previously required, which greatly increases the time to solve the problem. This paper proposes a targeted meta-heuristic algorithm optimisation method combining the advantages of tabu search algorithm and harmony search algorithm, which simplifies the solution phase of calling the precise solver in the two-stage algorithm of row facility layout problem, improves the problem solving efficiency, and makes the solution of large-scale problems become possible. The proposed model is verified through Lingo software, and then the model and the hybrid algorithm in the MATLAB environment are verified with each other. Finally, the proposed simplified algorithm is utilised to solve the large-scale problems that could not be solved by the two-stage algorithm before.     

The corridor allocation problem

The corridor allocation problem (CAP) seeks an arrangement of facilities along a central corridor defined by two horizontal lines parallel to the x-axis of a Cartesian coordinate system. The objective is to minimize the total communication cost among facilities, while respecting two main conditions: (i) no space is allowed between two adjacent facilities; (ii) the left-most point of the arrangement on either line should have zero abscissa. The conditions (i) and (ii) are required in many applications such as the arrangement of rooms at office buildings or hospitals. The CAP is a NP-Hard problem. In this paper, a mixed-integer programming formulation of the CAP is proposed, which allows us to compute optimal layouts in reasonable time for problem instances of moderate sizes. Moreover, heuristic procedures are presented that can handle larger instances.     

自适应爆炸半径的改进烟花算法

为充分利用被丢弃的爆炸火花个体的信息,对烟花算法进行优化,提出具有自适应爆炸半径特性的改进烟花算法。利用全局最优烟花个体gBest以及每个烟花所产生的最优爆炸火花个体的集合sparkpBest来构造新的爆炸半径,使其能够自适应地调整步长;在寻优过程中,对gBest进行高斯扰动来增加种群的多样性,避免烟花种群过快陷入局部最优。与其它群智能算法(粒子群算法PSO、带有高斯扰动的粒子群算法GPSO、蝙蝠算法BA、烟花算法FWA、自适应烟花算法AFWA以及增强烟花算法EFWA)对比,通过仿真可知,提出的改进烟花算法总体性能优于其它6种对比算法。     

求解机组组合问题的改进型人工鱼群算法研究

提出了改进型人工鱼群算法。采用线性递减的函数取代标准人工鱼群算法（BAFSA）中的固定视野;在觅食行为中,利用粒子群算法（PSO）中的惯性权重线性递减的视野来加速算法的收敛速度;同时用混沌现象代替BAFSA中的随机现象。给出了算法的全局收敛性证明,并将算法应用于求解电力系统机组组合问题,分别对基准测试函数、三机组和十机组系统进行仿真计算,结果均表明新算法能有效跳出局部极值,收敛速度快且具有更高的精度。因此,改进型算法可以作为求解机组组合问题的有效算法。     

Parallel hyper heuristic algorithm based on reinforcement learning for the corridor allocation problem and parallel row ordering problem

Hyper heuristics is a relatively new optimisation algorithm. Numerous studies have reported that hyper heuristics are well applied in combinatorial optimisation problems. As a classic combinatorial optimisation problem, the row layout problem has not been publicly reported on applying hyper heuristics to its various sub-problems. To fill this gap, this study proposes a parallel hyper-heuristic approach based on reinforcement learning for corridor allocation problems and parallel row ordering problems. For the proposed algorithm, an outer layer parallel computing framework was constructed based on the encoding of the problem. The simulated annealing, tabu search, and variable neighbourhood algorithms were used in the algorithm as low-level heuristic operations, and Q-learning in reinforcement learning was used as a high-level strategy. A state space containing sequences and fitness values was designed. The algorithm performance was then evaluated for benchmark instances of the corridor allocation problem (37 groups) and parallel row ordering problem (80 groups). The results showed that, in most cases, the proposed algorithm provided a better solution than the best-known solutions in the literature. Finally, the meta-heuristic algorithm applied to three low-level heuristic operations is taken as three independent algorithms and compared with the proposed hyper-heuristic algorithm on four groups of parallel row ordering problem instances. The effectiveness of Q-learning in selection is illustrated by analysing the comparison results of the four algorithms and the number of calls of the three low-level heuristic operations in the proposed method.     

改进差分进化算法在可靠性冗余分配问题中的应用

提出一种改进差分进化算法(IDE),以解决系统可靠性冗余分配问题.在罚函数法的基础上,对约束处理方法进行改进. 新约束处理方法在搜索过程中不需要在每一步都计算惩罚函数值,加快了寻优速度.具有良好的通用性,可以引入到其他智能优化算法中.将改进的算法用于求解4类典型的系统可靠性冗余分配问题,实验结果表明了所提出的改进算法具有很好的寻优精度和收敛速度.     

An improved fireworks algorithm for the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP), which aims at minimizing travel costs, is a wellknown NP-hard combinatorial optimization. Owing to its hardness, many heuristic search algorithms have been proposed to tackle this problem. This paper explores a recently proposed heuristic algorithm named the fireworks algorithm (FWA), which is a swarm intelligence algorithm. We adopt FWA for the combinatorial CVRP problem with several modifications of the original FWA: it employs a new method to generate "sparks" according to the selection rule, and it uses a new method to determine the explosion amplitude for each firework. The proposed algorithm is compared with several heuristic search methods on some classical benchmark CVRP instances. The experimental results show a promising performance of the proposed method. We also discuss the strengths and weaknesses of our algorithm in contrast to traditional algorithms.     

Improved algorithm for the widest empty 1-corner corridor

Given a set P of n points on a 2D plane, an empty corridor is an open region bounded by two parallel polygonal chains that does not contain any point of P, and partitions the point-set P into two non-empty parts. An empty corridor is said to be a 1-corner empty corridor if each of the two bounding polygonal chains has exactly one corner point. We present an improved algorithm for computing the widest empty 1-corner corridor. It runs in O(n³log²n) time and O(n²) space. This improves the time complexity of the best known algorithm for the same problem by a factor of [J.M. Diaz-Banez, M.A. Lopez, J.A. Sellares, On finding a widest empty 1-corner corridor, Information Processing Letters 98 (2006) 199-205].