Recent developments in evolutionary computation for manufacturingoptimization: problems, solutions, and comparisons

The use of intelligent techniques in the manufacturing field has been growing the last decades due to the fact that most manufacturing optimization problems are combinatorial and NP hard. This paper examines recent developments in the field of evolutionary computation for manufacturing optimization. Significant papers in various areas are highlighted, and comparisons of results are given wherever data are available. A wide range of problems is covered, from job shop and flow shop scheduling, to process planning and assembly line balancing     

解决多目标优化问题的差分进化算法研究进展

差分进化(differential evolution,DE)是一种简单但功能强大的进化优化算法.由于其优秀的性能,其诞生之日起就吸引了各国研究人员的关注.作为一种基于群体的全局性启发式搜索算法,差分进化算法在科学和工程中有许多成功的应用.本文对解决多目标优化问题的差分进化算法研究进行了综述,对差分进化的基本概念进行了详细的描述,给出了几种解决多目标优化问题的差分进化算法变体,并且给出了差分进化算法解决多目标优化问题的理论分析,最后,给出了差分进化算法解决多目标优化问题的工程应用,并指出了未来具有挑战性的研究领域.     

Multiobjective evolutionary algorithm based on multimethod with dynamic resources allocation

In the last two decades, multiobjective optimization has become main stream and various multiobjective evolutionary algorithms (MOEAs) have been suggested in the field of evolutionary computing (EC) for solving hard combinatorial and continuous multiobjective optimization problems. Most MOEAs employ single evolutionary operators such as crossover, mutation and selection for population evolution. In this paper, we suggest a multiobjective evolutionary algorithm based on multimethods (MMTD) with dynamic resource allocation for coping with continuous multi-objective optimization problems (MOPs). The suggested algorithm employs two well known population based stochastic algorithms namely MOEA/D and NSGA-II as constituent algorithms for population evolution with a dynamic resource allocation scheme. We have examined the performance of the proposed MMTD on two different MOPs test suites: the widely used ZDT problems and the recently formulated test instances for the special session on MOEAs competition of the 2009 IEEE congress on evolutionary computation (CEC’09). Experimental results obtained by the suggested MMTD are more promising than those of some state-of-the-art MOEAs in terms of the inverted generational distance (IGD)-metric on most test problems.     

Multi-objective differential evolution with performance-metric-based self-adaptive mutation operator for chemical and biochemical dynamic optimization problems

Each mutation operator of differential evolution (DE) algorithm is generally suitable for certain specific types of multi-objective optimization problems (MOPs) or particular stages of the evolution. To automatically select an appropriate mutation operator for solving MOPs in different phases of the evolution, a multi-objective differential evolution with performance-metric-based self-adaptive mutation operator (MODE-PMSMO) is proposed in this study. In MODE-PMSMO, a modified inverted generational distance (IGD) is utilized to evaluate the performance of each mutation operator and guide the evolution of mutation operators. The proposed MODE-PMSMO is then compared with seven multi-objective evolutionary algorithms (MOEAs) on five bi-objective and five tri-objective optimization problems. Generally, MODE-PMSMO exhibits the best average performance among all compared algorithms on ten MOPs. Additionally, MODE-PMSMO is employed to solve four typical multi-objective dynamic optimization problems in chemical and biochemical processes. Experimental results indicate that MODE-PMSMO is suitable for solving these actual problems and can provide a set of nondominated solutions for references of decision makers.     

A novel adaptive control strategy for decomposition-based multiobjective algorithm

Recently, evolutionary algorithm based on decomposition (MOEA/D) has been found to be very effective and efficient for solving complicated multiobjective optimization problems (MOPs). However, the selected differential evolution (DE) strategies and their parameter settings impact a lot on the performance of MOEA/D when tackling various kinds of MOPs. Therefore, in this paper, a novel adaptive control strategy is designed for a recently proposed MOEA/D with stable matching model, in which multiple DE strategies coupled with the parameter settings are adaptively conducted at different evolutionary stages and thus their advantages can be combined to further enhance the performance. By exploiting the historically successful experience, an execution probability is learned for each DE strategy to perform adaptive adjustment on the candidate solutions. The proposed adaptive strategies on operator selection and parameter settings are aimed at improving both of the convergence speed and population diversity, which are validated by our numerous experiments. When compared with several variants of MOEA/D such as MOEA/D, MOEA/D-DE, MOEA/D-DE+PSO, ENS-MOEA/D, MOEA/D-FRRMAB and MOEA/D-STM, our algorithm performs better on most of test problems.     

可求解多目标优化问题的演化博弈优化算法

借鉴演化博弈的思想和选择机制,提出了一种新的基于演化博弈的优化算法(EGOA)用于多目标问题的求解.算法框架具备对该类问题的通用性.为了对算法性能进行评估,采用了一组多目标优化问题(MOPs)的测试函数进行实验.实验结果表明,使用本算法搜索得到的演化稳定策略集合能够很好地逼近多目标优化问题的帕累托前沿,与一些经典的演化算法相比具有良好的问题求解能力.     

A review of the current applications of genetic algorithms in assembly line balancing

Most of the problems involving the design and plan of manufacturing systems are combinatorial and NP-hard. A well-known manufacturing optimization problem is the assembly line balancing problem (ALBP). Due to the complexity of the problem, in recent years, a growing number of researchers have employed genetic algorithms. In this article, a survey has been conducted from the recent published literature on assembly line balancing including genetic algorithms. In particular, we have summarized the main specifications of the problems studied, the genetic algorithms suggested and the objective functions used in evaluating the performance of the genetic algorithms. Moreover, future research directions have been identified and are suggested.     

Firing sequences backward algorithm for simple assembly line balancing problem of type 1

The objective of simple assembly line balancing problem type-1 (SALBP-1) is to minimize the number of workstations on an assembly line for a given cycle time. Since SALBP-1 is NP-hard, many iterative backtracking heuristics based on branch and bound procedure, tabu search, and genetic algorithms were developed to solve SALBP-1. In this study, a new heuristic algorithm based on Petri net approach is presented to solve the problem. The presented algorithm makes an order of firing sequence of transitions from Petri net model of precedence diagram. Task is assigned to a workstation using this order and backward procedure. The algorithm is coded in MATLAB, and its efficiency is tested on Talbot’s and Hoffmann’s benchmark datasets according to some performance measures and classifications. Computational study validates its effectiveness on the benchmark problems. Also comparison results show that the algorithm is efficiency to solve SALBP-1.     

The type E simple assembly line balancing problem: A mixed integer linear programming formulation

Although the simple assembly line balancing problem (SALBP) is the topic of many studies, typically they either consider minimizing the number of stations for a given cycle time (called type one), or minimizing the cycle time for a given number of stations (called type two). Rarely, type E of the problem has been considered. In the type E, cycle time and number of stations are both decision variables, and the objective is to maximize the line efficiency. This paper presents a mixed integer linear programming formulation for the type E simple assembly line balancing problem. Moreover, to further strengthen the presented formulation, two enhancement techniques in the form of valid inequalities and auxiliary variables are proposed. As the secondary objectives of the problem, minimization of the number of stations, the cycle time, and the smoothness index are studied as well. In the case of workload smoothing, three different linearization methods are employed and compared for minimizing the smoothness index. The results of computational study on the benchmark data set demonstrate the efficacy of the improved formulation     

Solution of multiobjective optimization problems: coevolutionary algorithm based on evolutionary game theory

When attempting to solve multiobjective optimization problems (MOPs) using evolutionary algorithms, the Pareto genetic algorithm (GA) has now become a standard of sorts. After its introduction, this approach was further developed and led to many applications. All of these approaches are based on Pareto ranking and use the fitness sharing function to keep diversity. On the other hand, the scheme for solving MOPs presented by Nash introduced the notion of Nash equilibrium and aimed at solving MOPs that originated from evolutionary game theory and economics. Since the concept of Nash Equilibrium was introduced, game theorists have attempted to formalize aspects of the evolutionary equilibrium. Nash genetic algorithm (Nash GA) is the idea to bring together genetic algorithms and Nash strategy. The aim of this algorithm is to find the Nash equilibrium through the genetic process. Another central achievement of evolutionary game theory is the introduction of a method by which agents can play optimal strategies in the absence of rationality. Through the process of Darwinian selection, a population of agents can evolve to an evolutionary stable strategy (ESS). In this article, we find the ESS as a solution of MOPs using a coevolutionary algorithm based on evolutionary game theory. By applying newly designed coevolutionary algorithms to several MOPs, we can confirm that evolutionary game theory can be embodied by the coevolutionary algorithm and this coevolutionary algorithm can find optimal equilibrium points as solutions for an MOP. We also show the optimization performance of the co-evolutionary algorithm based on evolutionary game theory by applying this model to several MOPs and comparing the solutions with those of previous evolutionary optimization models. This work was presented, in part, at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24#x2013;26, 2003.     

Multi-objective immune algorithm with Baldwinian learning

By replacing the selection component, a well researched evolutionary algorithm for scalar optimization problems (SOPs) can be directly used to solve multi-objective optimization problems (MOPs). Therefore, in most of existing multi-objective evolutionary algorithms (MOEAs), selection and diversity maintenance have attracted a lot of research effort. However, conventional reproduction operators designed for SOPs might not be suitable for MOPs due to the different optima structures between them. At present, few works have been done to improve the searching efficiency of MOEAs according to the characteristic of MOPs. Based on the regularity of continues MOPs, a Baldwinian learning strategy is designed for improving the nondominated neighbor immune algorithm and a multi-objective immune algorithm with Baldwinian learning (MIAB) is proposed in this study. The Baldwinian learning strategy extracts the evolving environment of current population by building a probability distribution model and generates a predictive improving direction by combining the environment information and the evolving history of the parent individual. Experimental results based on ten representative benchmark problems indicate that, MIAB outperforms the original immune algorithm, it performs better or similarly the other two outstanding approached NSGAII and MOEA/D in solution quality on most of the eight testing MOPs. The efficiency of the proposed Baldwinian learning strategy has also been experimentally investigated in this work.     

Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey

Scheduling is an important tool for a manufacturing system, where it can have a major impact on the productivity of a production process. In order to find an optimal solution to scheduling problems it gives rise to complex combinatorial optimization problems. Unfortunately, most of them fall into the class of NP-hard combinatorial problems. In this paper, we focus on the design of multiobjective evolutionary algorithms (MOEAs) to solve a variety of scheduling problems. Firstly, we introduce fitness assignment mechanism and performance measures for solving multiple objective optimization problems, and introduce evolutionary representations and hybrid evolutionary operations especially for the scheduling problems. Then we apply these EAs to the different types of scheduling problems, included job shop scheduling problem (JSP), flexible JSP, Automatic Guided Vehicle (AGV) dispatching in flexible manufacturing system (FMS), and integrated process planning and scheduling (IPPS). Through a variety of numerical experiments, we demonstrate the effectiveness of these Hybrid EAs (HEAs) in the widely applications of manufacturing scheduling problems. This paper also summarizes a classification of scheduling problems, and illustrates the design way of EAs for the different types of scheduling problems. It is useful to guide how to design an effective EA for the practical manufacturing scheduling problems. As known, these practical scheduling problems are very complex, and almost is a combination of different typical scheduling problems.     

一种改进的基于差分进化的多目标进化算法

近年来运用进化算法（EAs）解决多目标优化问题（Multi-objective Optimization Problems MOPs）引起了各国学者们的关注。作为一种基于种群的优化方法,EAs提供了一种在一次运行后得到一组优化的解的方法。差分进化（DE）算法是EA的一个分支,最开始是用来解决连续函数空间的问题。提出了一种改进的基于差分进化的多目标进化算法（CDE）,并且将它与另外两个经典的多目标进化算法（MOEAs）NSGA-II和SPEA2进行了对比实验。     

Evolutionary techniques for optimization problems in integrated manufacturing system: State-of-the-art-survey

Integrated manufacturing system (IMS) is a novel manufacturing environment which has been developed for the next generation of manufacturing and processing technologies. It consists of engineering design, process planning, manufacturing, quality management, and storage and retrieval functions. Improving the decision quality in those fields give rise to complex combinatorial optimization problems, unfortunately, most of them fall into the class of NP-hard problems. Find a satisfactory solution in an acceptable time play important roles. Evolutionary techniques (ET) have turned out to be potent methods to solve such kind of optimization problems. How to adapt evolutionary technique to the IMS is very challenging but frustrating. Many efforts have been made in order to give an efficient implementation of ET to optimize the specific problems in IMS.In this paper, we address four crucial issues in IMS, including design, planning, manufacturing, and distribution. Furthermore, some hot topics in these issues are selected to demonstrate the efficiency of ET’s application, such as layout design (LD) problem, flexible job-shop scheduling problem (fJSP), multistage process planning (MPP) problem, and advanced planning and scheduling (APS) problem. First, we formulate a generalized mathematic models for all those problems; several evolutionary algorithms which adapt to the problems have been proposed; some test instances based on the practical problems demonstrate the effectiveness and efficiency of our proposed approach.     

Modified differential evolution approach for optimization of planar parallel manipulators force capabilities

The global optimization problem is not easy to solve and is still an open challenge for researchers since an analytical optimal solution is difficult to obtain even for relatively simple application problems. Conventional deterministic numerical algorithms tend to stop the search in local minimum nearest to the input starting point, mainly when the optimization problem presents nonlinear, non-convex and non-differential functions, multimodal and nonlinear. Nowadays, the use of evolutionary algorithms (EAs) to solve optimization problems is a common practice due to their competitive performance on complex search spaces. EAs are well known for their ability to deal with nonlinear and complex optimization problems. The primary advantage of EAs over other numerical methods is that they just require the objective function values, while properties such as differentiability and continuity are not necessary. In this context, the differential evolution (DE), a paradigm of the evolutionary computation, has been widely used for solving numerical global optimization problems in continuous search space. DE is a powerful population-based stochastic direct search method. DE simulates natural evolution combined with a mechanism to generate multiple search directions based on the distribution of solutions in the current population. Among DE advantages are its simple structure, ease of use, speed, and robustness, which allows its application on several continuous nonlinear optimization problems. However, the performance of DE greatly depends on its control parameters, such as crossover rate, mutation factor, and population size and it often suffers from being trapped in local optima. Conventionally, users have to determine the parameters for problem at hand empirically. Recently, several adaptive variants of DE have been proposed. In this paper, a modified differential evolution (MDE) approach using generation-varying control parameters (mutation factor and crossover rate) is proposed and evaluated. The proposed MDE presents an efficient strategy to improve the search performance in preventing of premature convergence to local minima. The efficiency and feasibility of the proposed MDE approach is demonstrated on a force optimization problem in Robotics, where the force capabilities of a planar 3-RRR parallel manipulator are evaluated considering actuation limits and different assembly modes. Furthermore, some comparison results of MDE approach with classical DE to the mentioned force optimization problem are presented and discussed.     

基于分布估计的离散差分演化算法

差分演化(DE)是解决优化问题的非常有效的新兴智能算法,但它主要用于连续优化领域,至今尚不能象解决连续优化问题那样有效的处理组合优化问题.首先提出了离散DE用于组合优化问题,然后在离散DE中引入分布估计算法(EDA)来提高性能,把EDA抽样得到的全局统计信息和离散DE获得的局部演化信息相结合来产生新解,形成基于EDA的离散DE算法.为了保持种群多样性,在提出的算法中引入了位翻转变异操作.实验结果表明,EDA能大大提高离散DE的性能.     

一种基于混合高斯模型的多目标进化算法

目前,大多数多目标进化算法采用为单目标优化所设计的重组算子.通过证明或实验分析了几个典型的单目标优化重组算子并不适合某些多目标优化问题.提出了基于分解技术和混合高斯模型的多目标优化算法（multiobjective evolutionary algorithm based on decomposition and mixture Gaussian models,简称MOEA/D-MG）.该算法首先采用一个改进的混合高斯模型对群体建模并采样产生新个体,然后利用一个贪婪策略来更新群体.针对具有复杂Pareto前沿的多目标优化问题的测试结果表明,对给定的大多数测试题,该算法具有良好的效果.     

基于Pareto熵的多目标粒子群优化算法

粒子群优化算法因形式简洁、收敛快速和参数调节机制灵活等优点,同时一次运行可得到多个解,且能逼近非凸或不连续的Pareto最优前端,因而被认为是求解多目标优化问题最具潜力的方法之一.但当粒子群优化算法从单目标问题扩展到多目标问题时,Pareto最优解集的存储与维护、全局和个体最优解的选择以及开发与开采的平衡等问题亦随之出现.通过目标空间变换方法,采用Pareto前端在被称为平行格坐标系统的新目标空间中的分布熵及差熵评估种群的多样性及进化状态,并以此为反馈信息来设计进化策略,使得算法能够兼顾近似Pareto前端的收敛性和多样性.同时,引入格占优和格距离密度的概念来评估Pareto最优解的个体环境适应度,以此建立外部档案更新方法和全局最优解选择机制,最终形成了基于Pareto熵的多目标粒子群优化算法.实验结果表明：在IGD性能指标上,与另外8种对等算法相比,该算法在由ZDT和DTLZ系列组成的12个多目标测试问题集中表现出了显著的性能优势.     

An immune multi-objective optimization algorithm with differential evolution inspired recombination

According to the regularity of continuous multi-objective optimization problems (MOPs), an immune multi-objective optimization algorithm with differential evolution inspired recombination (IMADE) is proposed in this paper. In the proposed IMADE, the novel recombination provides two types of candidate searching directions by taking three recombination parents which distribute along the current Pareto set (PS) within a local area. One of the searching direction provides guidance for finding new points along the current PS, and the other redirects the search away from the current PS and moves towards the target PS. Under the background of the SBX (Simulated binary crossover) recombination which performs local search combined with random search near the recombination parents, the new recombination operator utilizes the regularity of continuous MOPs and the distributions of current population, which helps IMADE maintain a more uniformly distributed PF and converge much faster. Experimental results have demonstrated that IMADE outperforms or performs similarly to NSGAII, NNIA, PESAII and OWMOSaDE in terms of solution quality on most of the ten testing MOPs. IMADE converges faster than NSGAII and OWMOSaDE. The efficiency of the proposed DE recombination and the contributions of DE and SBX recombination to IMADE have also been experimentally investigated in this work.     

Game model-based co-evolutionary algorithm with non-dominated memory and Euclidean distance selection mechanisms for multi-objective optimization

Many real-world problems involve simultaneous optimization of several incommensurable and often competing objectives. In the search for solutions to multi-objective optimization problems (MOPs), we find that there is no single optimum but rather a set of optimums known as the “Pareto optimal set”. Co-evolutionary algorithms are well suited to optimization problems which involve several often competing objectives. Co-evolutionary algorithms are aimed at evolving individuals through individuals competing in an objective space. In order to approximate the ideal Pareto optimal set, the search capability of diverse individuals in an objective space can be used to determine the performance of evolutionary algorithms. Non-dominated memory and Euclidean distance selection mechanisms for co-evolutionary algorithms have the goal of overcoming the limited search capability of diverse individuals in the population space. In this paper, we propose a method for maintaining population diversity in game model-based co-evolutionary algorithms, and we evaluate the effectiveness of our approach by comparing it with other methods through rigorous experiments on several MOPs.