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.     

Mathematical formulation and a new metaheuristic for the constrained double-floor corridor allocation problem

A layout plan for a manufacturing system that is designed without any facility constraints will most likely be infeasible when confronted with reality. Additionally, considering that land available for building industrial plants is limited and its cost is high, it is necessary to investigate the layout planning of two and multi-floor facilities. To address these shortages in the scientific literature, we focus on the double-floor corridor allocation problem (DFCAP) which covers a wide range of complex facility constraints, such as fixed floor constraints, fixed row constraints, fixed positioning constraints, mutual floor constraints, mutual row constraints, sequencing constraints and adjacency constraints. For the model mentioned above, we term it as a constrained DFCAP (cDFCAP). A mixed-integer linear programming model is formulated for the cDFCAP. In order to solve larger realistic problems, a constrained metaheuristic with the memetic algorithm framework customised for solving the cDFCAP is introduced in this work. In our algorithm, four problem-specific heuristic rules to construct a set of initial solutions are developed. In addition, an ideal parameter combination for our constrained memetic algorithm is determined through a Taguchi experimental design. Finally, the results of a set of cDFCAP instances with different sizes (n = 10∼80) report that our provided approach is effective for the considered problem.     

A GRASP algorithm based new heuristic for the capacitated location routing problem

Abstract

In this paper, the capacitated location-routing problem (CLRP) is studied. CLRP is composed of two hard optimisation problems: the facility location problem and the vehicle routing problem. The objective of CLRP is to determine the best location of multiple depots with their vehicle routes such that the total cost of the solution is minimal. To solve this problem, we propose a greedy randomised adaptive search procedure. The proposed method is based on a new heuristic to construct a feasible CLRP solution, and then a local search-based simulated annealing is used as improvement phase. We have used a new technique to construct the clusters around the depots. To prove the effectiveness of our algorithm, several LRP instances are used. The results found are very encouraging.     

基于分区间强化学习的集群导弹快速任务分配EI北大核心CSCD

针对集群导弹在线任务分配面临的环境不确定、耗时过长等问题,本文研究了一种基于分区间强化学习的集群导弹快速任务分配算法.首先,建立集群导弹的综合攻防性能模型,并将存在环境不确定性的集群导弹任务分配问题表述为马尔可夫决策过程.其次,针对该过程采用分区间强化学习,通过将搜索空间划分成若干个子区间,降低搜索维度,加快算法的收敛过程,并通过理论证明给出了最优区间划分依据.最后,通过3组仿真实验,分别从收敛速度、不确定条件下的寻优能力以及导弹和目标数量可变情况下的决策能力3个方面,验证了所提算法的快速性和优化性能.     

基于任务分配与调度的GSAT算法求解3-SAT问题

基于不同分配策略的云计算任务调度以及任务分配与调度的主要目的,提出了一种新的算法—求解3-SAT问题的基于任务分配与调度的GSAT算法。该算法将3-SAT问题中的每一个变量形成一个任务,在GSAT算法的基础上,引入任务分配与调度指导贪心搜索;同时,在保留原有贪心搜索的前提下,根据任务分配与调度的思想和3-SAT问题的特点,设计了两种新的策略—分配策略和调度策略共同完成整个贪心搜索过程。以标准的SATLAB库中变量个数从 20～250的3 700个不同规模的标准Uniform Random 3-SAT 问题对新的算法的性能进行了合理的测试,并与高效和普通性能改进的GSAT算法的结果作了比较,结果表明,该算法具有更高的成功率和更少的翻转次数。     

A learning architecture based on reinforcement learning for adaptive control of the walking machine LAURON

The learning of complex control behaviour of autonomous mobile robots is one of the actual research topics. In this article an intelligent control architecture is presented which integrates learning methods and available domain knowledge. This control architecture is based on Reinforcement Learning and allows continuous input and output parameters, hierarchical learning, multiple goals, self-organized topology of the used networks and online learning. As a testbed this architecture is applied to the six-legged walking machine LAURON to learn leg control and leg coordination.     

A heuristic algorithm based on Lagrangian relaxation for the closest string problem

The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as a mixed-integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Computational experiments will show that the proposed algorithm can find good approximate solutions very fast.     

Discrete optimisation based on the combined use of reinforcement and constraint satisfaction schemes

A new approach is presented for finding near-optimal solutions to discrete optimisation problems that is based on the cooperation of two modules: an optimisation module and a constraint satisfaction module. The optimisation module must be able to search the problem state space through an iterative process of sampling and evaluating the generated samples. To evaluate a generated point, first a constraint satisfaction module is employed to map that point to another one satisfying the problem constraints, and then the cost of the new point is used as the evaluation of the original one. The scheme that we have adopted for testing the effectiveness of the method uses a reinforcement learning algorithm in the optimisation module and a general deterministic constraint satisfaction algorithm in the constraint satisfaction module. Experiments using this scheme for the solution of two optimisation problems indicate that the proposed approach is very effective in providing feasible solutions of acceptable quality.     

A heuristic block-loading algorithm based on multi-layer search for the container loading problem

This paper presents an efficient heuristic block-loading algorithm based on multi-layer search for the three-dimensional container loading problem. First, a basic heuristic block-loading algorithm is introduced. This algorithm loads one block, determined by a block selecting algorithm, in one packing phase, according to a fixed strategy, until no blocks are available. Second, the concept of composite block is introduced, the difference between traditional block and composite block being that composite block can contain multiple types of boxes in one block under some restrictions. Third, based on the depth-first search algorithm, a multi-layer search algorithm is developed for determining the selected block in each packing phase, and making this result closer to the optimal solution. Computational results on a classic data set show that the proposed algorithm outperforms the best known algorithm in almost all the test data.     

A parallel immune algorithm for traveling salesman problem and its application on cold rolling scheduling

Parallel computing provides efficient solutions for combinatorial optimization problem. However, since the communications among computing processes are rather cost-consuming, the actual parallel or distributed algorithm comes with substantial expenditures, such as, hardware, management, and maintenance. In this study, a parallel immune algorithm based on graphic processing unit (GPU) that originally comes to process the computer graphics in display adapter is proposed. Genetic operators and a structure of vaccine taboo list are designed, and the internal memory utility of GPU structure is optimized. To verify the effectiveness and efficiency of the proposed algorithm, various middle-scale traveling salesman problems (TSP) are employed to demonstrate the potential of the proposed techniques. The simulation examples demonstrate that the developed method can greatly improve the computing efficiency for solving the TSP, and the results are more remarkable when the scale of TSP becomes higher. Furthermore, the derived algorithm is verified by a practical application in steel industry that arranges the cold rolling scheduling of a batch of steel coils.     

基于多起点和Mask策略的深度强化学习算法求解覆盖旅行商问题

覆盖旅行商问题(covering salesman problem, CSP)是旅行商问题的变体,在防灾规划、急救管理中有着广泛应用.由于传统方法求解问题实例耗时严重,近年来深度神经网络被提出用于解决该类组合优化问题,在求解速度和泛化性上有明显的优势.现有基于深度神经网络求解CSP的方法求解质量较低,特别在大规模实例上与传统的启发式方法相比存在较大差距.针对上述问题,提出一种新的基于深度强化学习求解CSP的方法,由编码器对输入特征进行编码,提出新的Mask策略对解码器使用自注意力机制构造解的过程进行约束,并提出多起点策略改善训练过程、提高求解质量.实验结果表明,所提方法对比现有基于深度神经网络的求解方法进一步缩小了最优间隙,同时有着更高的样本效率,在不同规模和不同覆盖类型的CSP中展现出更强的泛化能力,与启发式算法相比在求解速度上有10～40倍的提升.     

基于深度强化学习与自学习的多无人机近距空战机动策略生成算法

为解决多无人机近距空战机动决策问题,提出一种基于参数共享Q网络与虚拟自我对局的多无人机近距空战机动策略生成算法.首先,设计一种适用于不同无人机编队规模的混合马尔可夫博弈模型与多无人机机动决策策略生成强化学习框架一参数共享Q网络,并通过自编码器对状态空间进行压缩以提高策略学习效率.然后,使用虚拟自我对局方法使机动策略收敛...     

A tabu search procedure based on a random Roulette diversification for the weighted maximal planar graph problem

An efficient and effective tabu search implementation for the weighted maximal planar graph problem is proposed. The search incorporates a number of novel features including: the introduction of a new set of two-move operators; a move-cache-memory structure for efficiently searching the neighbourhood space; and a random roulette selection from a ranked list of best moves for diversification. The effects of these and other features on solution quality are investigated. Computational results are reported on a set of 100 benchmark instances of sizes varying from 20 to 100 vertices. The results demonstrate that the new probabilistic tabu search algorithm is very competitive with state of the art algorithms in the literature in terms of both solution quality and computational effort.Scope