A block-based evolutionary algorithm for flow-shop scheduling problem

Combinatorial problems like flow shop scheduling, travel salesman problem etc. get complicated and are difficult to solve when the problem size increases. To overcome this problem, we present a block-based evolutionary algorithm (BBEA) which will conduct evolutionary operations on a set of blocks instead of genes. BBEA includes the block mining and block recombination approaches. A block mining algorithm is developed to decompose a chromosome into a set of blocks and rest of genes. The block is with a fixed length and can be treated as a building block in forming a new chromosome later on. To guide the block mining process, a gene linkage probability matrix is defined that shows the linkage strength among genes. Therefore the blocks can be further evolved during the evolutionary processes using this matrix. In the block recombination approach, the blocks along with the rest of genes are recombined to form a new chromosome. This new evolutionary approach of BBEA is tested on a set of discrete problems. Experimental results show that BBEA is very competitive when compared with traditional GA, EA or ACGA and HGIA approaches and it can largely improve the performance of evolutionary algorithm and save a fair amount of computational times simultaneously.     

A rock-paper-scissors evolutionary algorithm for the TDMA broadcast scheduling problem

In wireless ad-hoc networks, the broadcast scheduling problem (BSP) is commonly viewed as a well-known NP-complete combinatorial optimization problem. The purpose of the BSP is to achieve a transmission schedule with collision-free time slots in a time division multiple access ad-hoc network. The transmission schedule is optimized by minimizing the frame length of the node transmissions and maximizing the utilization of the shared channel. In this work, we propose a new evolutionary algorithm to solve the BSP by adopting the rock-paper-scissors dynamics found in natural systems. We use three types of species with strategies of different levels of intensification and diversification to simulate the rock-paper-scissors dynamics. Based on this evolutionary game, in which the success of one species relies on the behavior of others, the dynamic coexistence of three species can be achieved to control the balance between intensification and diversification. The experimental results demonstrate that our algorithm is efficient and effective at solving large instances of the BSP.     

A multi-objective evolutionary algorithm to exploit the similarities of resource allocation problems

The complexity of a resource allocation problem (RAP) is usually NP-complete, which makes an exact method inadequate to handle RAPs, and encourages heuristic techniques to this class of problems for obtaining approximate solutions in polynomial time. Different heuristic techniques have already been investigated for handling various RAPs. However, since the properties of an RAP can help in characterizing other RAPs, instead of individual solution techniques, the similarities of different RAPs might be exploited for developing a common solution technique for them. Two RAPs of quite different nature, namely university class timetabling and land-use management, are considered here for such a study. The similarities between the problems are first explored, and then a common multi-objective evolutionary algorithm (a kind of heuristic techniques) for them is developed by exploiting those similarities. The algorithm is problem-dependent to some extent and can easily be extended to other similar RAPs. In the present work, the algorithm is applied to two real instances of the considered problems, and its properties are derived from the obtained results.     

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.     

An evolutionary algorithm for the one‐dimensional cutting stock problem

This paper deals with the one‐dimensional integer cutting stock problem, which consists of cutting a set of available objects in stock in order to produce ordered smaller items in such a way as to minimize the waste of material. The case in which there are various types of objects available in stock in limited quantities is studied. A new heuristic method based on the evolutionary algorithm concept is proposed to solve the problem. This heuristic is empirically analyzed by solving randomly generated instances and the results are compared with other methods from the literature.     

A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows

This paper addresses the multiobjective vehicle routing problem with time windows (MOVRPTW). The objectives are to minimize the number of vehicles and the total distance simultaneously. Our approach is based on an evolutionary algorithm and aims to find the set of Pareto optimal solutions. We incorporate problem-specific knowledge into the genetic operators. The crossover operator exchanges one of the best routes, which has the shortest average distance, the relocation mutation operator relocates a large number of customers in non-decreasing order of the length of the time window, and the split mutation operator breaks the longest-distance link in the routes. Our algorithm is compared with 10 existing algorithms by standard 100-customer and 200-customer problem instances. It shows competitive performance and updates more than 1/3 of the net set of the non-dominated solutions.     

用多目标演化优化算法解决约束选址问题

约束选址问题是一个多目标约束优化问题，传统算法（加权法）一次只能得到一个候选解，用多目标演化优化算法对其进行求解，可以一次得到多个候选解，给决策者提供更多的选择余地，以期获得更大的利益，数字试验表明，该方法优于传统多目标优化方法。     

柔性作业调度的串并行模型对比与求解

作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。     

Multi-objective genetic algorithm for berth allocation problem considering daytime preference

Maximization of operational efficiency and minimization of cost are pursued by terminal operators, whereas daytime preference is increasingly emphasized by governments, terminal operators and workers. Daytime preference in berth allocation schedule refers to schedule the workloads in nights as fewer as possible, which improves working comfort, safety, and green and energy-savings degrees, but may decrease the throughput and total operational efficiency. By extending existing dynamic discrete berth allocation model, a bi-objective model considering daytime preference is established to minimize the delayed workloads and the workloads in nights. Based on the well known NSGA-II algorithm, a multi-objective genetic algorithm (moGA) is developed for solving the bi-objective model by using a two-part representation scheme. The sensitivities of the algorithmic parameters and tradeoffs between daytime preference and delayed workloads are analyzed by numerical experiments. The algorithmic aspects of the proposed approach and the effects of daytime preference on solutions are all examined. Finally, the managerial implications are discussed.     

A differential evolution algorithm to solve redundancy allocation problems

To improve system reliability without changing its nature, three methods are proposed. The first method uses more reliable components and the second method provides redundant components within the system. The third method is a combination of these two methods. The redundancy allocation problem (RAP) finds the appropriate mix of components and redundancies within a system to maximize its reliability or minimize its cost due to several constraints, such as cost, weight, and volume. This paper presents a methodology to solve the RAP, which is an NP‐hard problem, modeled with discrete variables. In this paper, we use a metaheuristic to solve the RAP of a series–parallel system with a mix of components. Our metaheuristic offers a practical method with specific solution encoding, and combines a penalty function to solve large instances of the relaxed RAP, where different types of components can be used in parallel. The efficiency of the algorithm was tested through a set of well‐known benchmark problems from the literature. Testing of the algorithm achieved satisfactory results in reasonable computing time.     

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

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

一种求解旅行商问题的热力学演化算法

在综合国内外演化计算研究现状的基础上,基于热力学中的自由能极小化原理,设计了一个全新的热力学演化算法,并通过对于流动旅行商问题求解的数值实验,测试了热力学演化算法的优良性能,实验结果表明了热力学演化算法求出的解比一般演化算法求出的解更加接近于全局最优。     

A parallel double-level multiobjective evolutionary algorithm for robust optimization

Robust optimization is a popular method to tackle uncertain optimization problems. However, traditional robust optimization can only find a single solution in one run which is not flexible enough for decision-makers to select a satisfying solution according to their preferences. Besides, traditional robust optimization often takes a large number of Monte Carlo simulations to get a numeric solution, which is quite time-consuming. To address these problems, this paper proposes a parallel double-level multiobjective evolutionary algorithm (PDL-MOEA). In PDL-MOEA, a single-objective uncertain optimization problem is translated into a bi-objective one by conserving the expectation and the variance as two objectives, so that the algorithm can provide decision-makers with a group of solutions with different stabilities. Further, a parallel evolutionary mechanism based on message passing interface (MPI) is proposed to parallel the algorithm. The parallel mechanism adopts a double-level design, i.e., global level and sub-problem level. The global level acts as a master, which maintains the global population information. At the sub-problem level, the optimization problem is decomposed into a set of sub-problems which can be solved in parallel, thus reducing the computation time. Experimental results show that PDL-MOEA generally outperforms several state-of-the-art serial/parallel MOEAs in terms of accuracy, efficiency, and scalability.     

一种求解Shubert函数优化问题的演化算法

综合国内外演化计算研究现状,基于热力学中的自由能极小化原理, 设计了一个全新的热力学演化算法,并通过对于Shubert函数优化问题求解的数值试验,测试了热力学演化算法的优良性能,实验结果表明了热力学演化算法求出的解比一般演化算法求出的解更加接近于全局最优。     

A tabu search based hybrid evolutionary algorithm for the max-cut problem

This paper presents a tabu search based hybrid evolutionary algorithm (TSHEA) for solving the max-cut problem. The proposed algorithm integrates a distance-and-quality based solution combination operator and a tabu search procedure based on neighborhood combination of one-flip and constrained exchange moves. Comparisons with leading reference algorithms from the literature disclose that the proposed algorithm discovers new best solutions for 15 out of 91 instances, while matching the best known solutions on all but 4 instances. Analysis indicates that the neighborhood combination and the solution combination operator play key roles to the effectiveness of the proposed algorithm.     

多目标资源优化分配问题的Memetic 算法

针对传统算法求解多目标资源优化分配问题收敛慢、Pareto解不能有效分布在Pareto 前沿面的问题, 提出一种新的Memetic 算法. 在遗传算法的交叉算子中引入模拟退火算法, 加强了遗传算法的局部搜索能力, 加快了收敛速度. 为了使Pareto 最优解均匀分布在Pareto 前沿面, 在染色体编码中引入禁忌表, 增加了种群的多样性, 避免了传统遗传算法后期Pareto 解集过于集中的缺点. 通过与已有的遗传算法、蚁群算法、粒子群算法进行比较, 仿真实验表明了所提出算法的有效性, 并分析了禁忌表长度和模拟退火参数对算法收敛性的影响.

     

求解人力资源分配问题的多目标微粒群优化算法*

提出一种改进的多目标微粒群优化算法来求解人力资源分配问题.通过对种群进行正交初始化,保证了个体在整个可行解空间上的均匀分散,使得算法能够在整个可行解空间上进行均匀搜索;通过基于网格技术的外部存档非劣解删选策略,有效地保留了逼近Pareto前沿的非劣解;引入一种广义的学习策略来提升粒子向Pareto前沿收敛的概率.实验结...     

货架分配问题的一个有效混合遗传算法

针对货架分配问题提出了一个遗传算法与模拟退火算法及一个局部搜索算法混合的算法。首先,设计了一种比较直观的编码方法,用一个矩阵作为一种货架分配方案。第二,设计了与编码相应的杂交和变异算子,并且杂交、变异都能生成可行解,不需要对解进行修正。第三,为了能够生成好的初始种群,定义了一个阀值,这个阀值不仅反映了解的适应值的信息,而且还反映解的结构的信息。第四,为了增加算法的局部搜索能力,同时又尽量不增加计算的复杂度,让模拟退火算法和一种局部搜索算法并行作用于相应的子群。通过大量的数据模拟实验及与其他的几种算法模拟结果进行比较,实验显示,该算法不论是计算结果还是算法的稳定性都优于其他算法。     

An evolutionary game algorithm for grid resource allocation under bounded rationality

Resource allocation cannot reach equilibrium in one‐off game in grid environment because of the bounded rationality of the users. To address this issue, an evolutionary game algorithm for grid resource allocation is proposed in this paper. The evolutionary game theory is introduced to study the selection process of user strategy from the dynamic viewpoint. Firstly, the problem of multiple users competing for a common resource is formulated as a symmetric game. Secondly, replicated dynamic mechanism is used to produce the evolutionary stable point that leads to a satisfied allocation scenario. Finally, the relationships among the evolutionary stable point, valuation functions, and convergence time are discussed in detail. The results of the experiments show that the proposed evolutionary game algorithm is convergent and generates better utility results compared with the classical game algorithm. Copyright © 2009 John Wiley & Sons, Ltd.     

具有同时集送货需求车辆路径问题的混沌量子进化算法研究

针对量子进化算法中旋转角取值的离散性使其解空间的搜索具有跳跃性,提出了基于混沌理论的精英均值计算旋转角算法,并将其应用于具有同时集送货需求车辆路径问题的求解.在理论上分析了解的强可行和弱可行条件的基础上,使用启发式算子对解进行改进.通过仿真实验与其他算法进行了比较,仿真结果表明所提出算法是求解此类问题的有效方法.