Evolutionary design of Evolutionary Algorithms

Manual design of Evolutionary Algorithms (EAs) capable of performing very well on a wide range of problems is a difficult task. This is why we have to find other manners to construct algorithms that perform very well on some problems. One possibility (which is explored in this paper) is to let the evolution discover the optimal structure and parameters of the EA used for solving a specific problem. To this end a new model for automatic generation of EAs by evolutionary means is proposed here. The model is based on a simple Genetic Algorithm (GA). Every GA chromosome encodes an EA, which is used for solving a particular problem. Several Evolutionary Algorithms for function optimization are generated by using the considered model. Numerical experiments show that the EAs perform similarly and sometimes even better than standard approaches for several well-known benchmarking problems.     

Applying genetic algorithms to zone design

Genetic algorithms (GA) have been found to provide global near optimal solutions in a wide range of complex problems. In this paper genetic algorithms have been used to deal with the complex problem of zone design. The zone design problem comprises a large number of geographical tasks, from which electoral districting is probably the most well known. The electoral districting problem is described and formalized mathematically. Different problem encodings, suited to GA optimization, are presented, together with different objective functions. A practical real world example is given and tests performed in order to evaluate the effectiveness of the GA approach.     

A hybrid differential evolution augmented Lagrangian method for constrained numerical and engineering optimization

We present a new hybrid method for solving constrained numerical and engineering optimization problems in this paper. The proposed hybrid method takes advantage of the differential evolution (DE) ability to find global optimum in problems with complex design spaces while directly enforcing feasibility of constraints using a modified augmented Lagrangian multiplier method. The basic steps of the proposed method are comprised of an outer iteration, in which the Lagrangian multipliers and various penalty parameters are updated using a first-order update scheme, and an inner iteration, in which a nonlinear optimization of the modified augmented Lagrangian function with simple bound constraints is implemented by a modified differential evolution algorithm. Experimental results based on several well-known constrained numerical and engineering optimization problems demonstrate that the proposed method shows better performance in comparison to the state-of-the-art algorithms.     

Using Disruptive Selection to Maintain Diversity in Genetic Algorithms

Genetic algorithms are a class of adaptive search techniques based on the principles of population genetics. The metaphor underlying genetic algorithms is that of natural evolution. With their great robustness, genetic algorithms have proven to be a promising technique for many optimization, design, control, and machine learning applications. A novel selection method, disruptive selection, has been proposed. This method adopts a nonmonotonic fitness function that is quite different from conventional monotonic fitness functions. Unlike conventional selection methods, this method favors both superior and inferior individuals. Since genetic algorithms allocate exponentially increasing numbers of trials to the observed better parts of the search space, it is difficult to maintain diversity in genetic algorithms. We show that Disruptive Genetic Algorithms (DGAs) effectively alleviate this problem by first demonstrating that DGAs can be used to solve a nonstationary search problem, where the goal is to track time-varying optima. Conventional Genetic Algorithms (CGAs) using proportional selection fare poorly on nonstationary search problems because of their lack of population diversity after convergence. Experimental results show that DGAs immediately track the optimum after the change of environment. We then describe a spike function that causes CGAs to miss the optimum. Experimental results show that DGAs outperform CGAs in resolving a spike function.     

基于改进元胞多目标遗传算法的机床主轴优化

为了进一步提高元胞遗传算法在求解多目标优化问题时的收敛性和分布性。在多目标元胞遗传算法的基础上,引入了三维空间元胞,提出了三维元胞多目标遗传算法。采用多目标基准测试函数对该算法进行了测试,并将其与目前比较流行的几种多目标遗传算法进行对比。结果表明,此种算法在收敛性和分布性上取得了更好的效果。采用以上这几种算法分别对机床主轴多目标优化问题进行了求解,相比其他几种算法,改进的多目标元胞遗传算法得到了更优的结果,说明了改进的算法在求解此问题时行之有效。     

Optimizing thermal design of data center cabinets with a new multi-objective genetic algorithm

There is an ever increasing need to use optimization methods for thermal design of data centers and the hardware populating them. Airflow simulations of cabinets and data centers are computationally intensive and this problem is exacerbated when the simulation model is integrated with a design optimization method. Generally speaking, thermal design of data center hardware can be posed as a constrained multi-objective optimization problem. A popular approach for solving this kind of problem is to use Multi-Objective Genetic Algorithms (MOGAs). However, the large number of simulation evaluations needed for MOGAs has been preventing their applications to realistic engineering design problems. In this paper, details of a substantially more efficient MOGA are formulated and demonstrated through a thermal analysis simulation model of a data center cabinet. First, a reduced-order model of the cabinet problem is constructed using the Proper Orthogonal Decomposition (POD). The POD model is then used to form the objective and constraint functions of an optimization model. Next, this optimization model is integrated with the new MOGA. The new MOGA uses a “kriging” guided operation in addition to conventional genetic algorithm operations to search the design space for global optimal design solutions. This approach for optimal design is essential to handle complex multi-objective situations, where the optimal solutions may be non-obvious from simple analyses or intuition. It is shown that in optimizing the data center cabinet problem, the new MOGA outperforms a conventional MOGA by estimating the Pareto front using 50% fewer simulation calls, which makes its use very promising for complex thermal design problems. Recommended by: Monem Beitelmal     

GENETIC ALGORITHMS: A Search Technique Applied to Behavior Analysis

Abstract

Genetic algorithms are powerful generalized search techniques. This paper shows that genetic algorithms can solve a difficult class of problems in general systems theory quickly and efficiently. Genetic algorithms appear to be ideally suited to solving the combinatorially complex problem of behavior analysis. The search space of behavior analysis experiences exponential growth as a function of the number of variables. The genetic algorithm converges after considering a small percentage of these potential solutions. The number of solutions that need to be examined by the genetic algorithm seems to be a polynomial function of the number of variables and, in fact, the growth appears to be linear     

Multiobjective controller design handling human preferences

Trends in controller design point to the integration of several objectives to achieve new performances. Moreover, it is easy to set the controller design problem as an optimization problem. Therefore, future improvements are likely to be based on the adequate formulation and resolution of the multiobjective optimization problem. The multiobjective optimization strategy called physical programming provides controller designers with a flexible tool to express design preferences with a ‘physical’ meaning. For each objective (settling time, overshoot, disturbance rejection, etc.) preferences are established through categories such as desirable, tolerable, unacceptable, etc. to which numerical values are assigned. The problem is normalized and converted to a single-objective optimization problem but normally it results in a multimodal problem very difficult to solve. Genetic algorithms provide an adequate solution to this type of problems and open new possibilities in controller design and tuning.     

Swarm-based intelligent optimization approach for layout problem

Layout problem is a kind of NP-Complete problem. It is concerned more and more in recent years and arises in a variety of application fields such as the layout design of spacecraft modules, plant equipment, platforms of marine drilling well, shipping, vehicle and robots. The algorithms based on swarm intelligence are considered powerful tools for solving this kind of problems. While usually swarm intelligence algorithms also have several disadvantages, including premature and slow convergence. Aiming at solving engineering complex layout problems satisfactorily, a new improved swarm-based intelligent optimization algorithm is presented on the basis of parallel genetic algorithms. In proposed approach, chaos initialization and multi-subpopulation evolution strategy based on improved adaptive crossover and mutation are adopted. The proposed interpolating rank-based selection with pressure is adaptive with evolution process. That is to say, it can avoid early premature as well as benefit speeding up convergence of later period effectively. And more importantly, proposed PSO update operators based on different versions PSO are introduced into presented algorithm. It can take full advantage of the outstanding convergence characteristic of particle swarm optimization (PSO) and improve the global performance of the proposed algorithm. An example originated from layout of printed circuit boards (PCB) and plant equipment shows the feasibility and effectiveness of presented algorithm.     

利用遗传算法求解圆排列问题

圆排列问题是一个典型的组合优化问题,也是一个NP完全问题.遗传算法是根据自然界生物学进化而发展起来的一种进化方法,其具有简单、易行、抽象性与鲁棒性特征,已成功地解决了许多工程优化问题.给出基于改进遗传算法给出求解圆排列问题的新方法.首先,分析了圆排列问题与旅行商问题之间的关系.然后,将圆排列问题转化为旅行商问题.接着,利用所给改进遗传算法进行了求解.最后,在仿真实验中,与已有算法进行了比较,结果表明,所给算法是一种能够简单有效地求解圆排列问题的新方法.     

Human-competitive lens system design with evolution strategies

Lens system design provides ideal problems for evolutionary algorithms: a complex non-linear optimization task, often with intricate physical constraints, for which there is no analytical solutions. This paper demonstrates, through the use of two evolution strategies, namely non-isotropic Self-Adaptive evolution strategy (SA-ES) and Covariance Matrix Adaptation evolution strategy (CMA-ES), as well as multiobjective Non-Dominated Sort Genetic Algorithm 2 (NSGA-II) optimization, the human competitiveness of an approach where an evolutionary algorithm is hybridized with a local search algorithm to solve both a classic benchmark problem, and a real-world problem.     

A generic genetic algorithm for product family design

Product family design (PFD) has been well recognized as an effective means to satisfy diverse market niches while maintaining the economies of scale and scope. PFD essentially entails a configuration problem by “combination," where combinatorial explosion always occurs and is known to be mathematically intractable or NP-hard. Although genetic algorithms (GAs) have been proven to excel in solving combinatorial optimization problems, it is difficult to adopt the traditional GA to deal with the complex data and interrelationships inherent in the PFD problem. This paper proposes a generic genetic algorithm (GGA) for PFD. A generic encoding scheme is developed to adapt to diverse PFD scenarios. A hybrid constraint-handling strategy is proposed to handle complex and distinguishing constraints at different stages along the evolutionary process. The design and implementation procedures of the GGA are discussed in detail. An application of the proposed GGA to motor family design is reported. The GGA efficiency is also tested through efficiency analysis in terms of the probability of generating feasible solutions, as well as through analysis of the GGA complexity.     

EXPLICA: An Explorative Imperialist Competitive Algorithm based on the notion of Explorers with an expansive retention policy

Meta-heuristic algorithms are of considerable importance in solving optimization problems. This importance is more highlighted when the problems to be optimized are too complicated to achieve a solution using conventional methods or, the traditional methods are somehow not applicable for solving them. Imperial Competitive Algorithm has been proved to be an efficient and effective meta-heuristic optimization algorithm and it has been successfully applied in many scientific and engineering problems. By introducing the concept of explorers and retention policy, the original algorithm is enhanced with a dynamic population mechanism in this paper and hence, the performance of the Imperial Competitive Algorithm is improved. Performance of the proposed modification is tested with experiments of optimizing real-values functions and results are compared with results obtained with the original Imperialistic Competitive Algorithm, Genetic Algorithm, Particle Swarm Optimization and Simulated Annealing. Also, the applicability of the proposed improvement is verified by optimizing a ship propeller design problem.     

基于GA-NN的复杂工艺生产过程多目标优化研究

在复杂非线性多目标优化问题求解中,非线性模型结构很难事先给定,需要检验的参数也非常繁多,应用传统的建模方法和优化模型已难以解决更为复杂的现实问题。人工神经网络技术为解决复杂非线性系统建模问题提供了一条新的途径。将神经网络响应面作为目标函数或者约束条件,加上其他常规约束条件进行系统模型的建立,再应用遗传算法进行优化,从而实现设计分析与设计优化的分离。以某化工企业的生产过程优化问题为例,利用BP神经网络建立了工艺参数与性能目标之间的模型,然后利用遗传算法搜索最优工艺参数,获取了用于指导生产的样本点数据。研究结果表明,该方法能够获得高精度的多目标优化模型,从而使优化效率大为提高。     

遗传算法在图像处理中的应用

遗传算法是一种基于生物自然选择与遗传机理的随机搜索与优化方法。近年来,由于遗传算法求解复杂优化问题的巨大潜力及其在工业工程领域的成功应用,这种算法受到了国内外学者的广泛关注。本文介绍了遗传算法的基本理论,描述了它的主要特点和基本性质;重点综述了遗传算法在数字图像处理中的主要应用,特别是在图像分割和边缘检测、图像压缩、图像恢复、图像匹配、图像增强以及图像重建等方面的作用;探讨了目前遗传算法在图像处理领域中存在的问题及其在今后的发展方向。     

基于混合遗传算法的订单生产调度在机车车辆行业中的应用

机车车辆行业作为典型的面向订单的机械制造企业,优化的生产调度方法能提高订单的准时交货,缩短产品的生产周期,提高企业的市场竞争力。订单生产调度问题是典型的NP-hard问题。遗传算法(Genetic Algorithms)为求具有多个约束的复杂问题提供了有效的方法。但是遗传算法的局部搜索能力比较差,在解决订单生产调度问题中存在着明显的不足。本文引入了局部搜索能力很强的禁忌搜索算法,用遗传算法和禁忌搜索算法相结合的混合遗传算法来解决机车车辆行业中面向订单生产调度问题。     

Evolutionary Algorithms for Minimax Problems in Robust Design

Many robust design problems can be described by minimax optimization problems. Classical techniques for solving these problems have typically been limited to a discrete form of the problem. More recently, evolutionary algorithms, particularly coevolutionary optimization techniques, have been applied to minimax problems. A new method of solving minimax optimization problems using evolutionary algorithms is proposed. The performance of this algorithm is shown to compare favorably with the existing methods on test problems. The performance of the algorithm is demonstrated on a robust pole placement problem and a ship engineering plant design problem.     

A genetic algorithm-based solution methodology for modular design

Combinatorial optimization problems usually have a finite number of feasible solutions. However, the process of solving these types of problems can be a very long and tedious task. Moreover, the cost and time for getting accurate and acceptable results is usually quite large. As the complexity and size of these problems grow, the current methods for solving problems such as the scheduling problem or the classification problem have become obsolete, and the need for an efficient method that will ensure good solutions for these complicated problems has increased. This paper presents a genetic algorithm (GA)-based method used in the solution of a set of combinatorial optimization problems. A definition of a combinatorial optimization problem is first given. The definition is followed by an introduction to genetic algorithms and an explanation of their role in solving combinatorial optimization problems such as the traveling salesman problem. A heuristic GA is then developed and used as a tool for solving various combinatorial optimization problems such as the modular design problem. A modularity case study is used to test and measure the performance of the developed algorithm.     

Computer-aided pipeline operation using genetic algorithms and rule learning. PART I: Genetic algorithms in pipeline optimization

In this two-paper series, techniques connected with artificial intelligence and genetics are applied to achieve computer-based control of gas pipeline systems. In this, the first paper, genetic algorithms are developed and applied to the solution of two classical pipeline optimization problems, the steady serial line problem, and the single transient line problem. Simply stated, genetic algorithms are canonical search procedures based on the mechanics of natural genetics. They combine a Darwinian survival of the fittest with a structured, yet randomized, information exchange between artificial chromosomes (strings). Despite their reliance on stochastic processes, genetic algorithms are no simple random walk; they carefully and efficiently exploit historic information to guide future trials.In the two pipeline problems, a simple three-operator genetic algorithm consisting of reproduction, crossover, and mutation finds near-optimal performance quickly. In, the steady serial problem, near-optimal performance is found after searching less than 1100 of 1.1(10¹²) alternatives. Similarly, efficient performance is demonstrated in the transient problem.Genetic algorithms are ready for application to more complex engineering optimization problems. They also can serve as a searning mechanism in a larger rule learning procedure. This application is discussed in the sequal.     

Interdigitation for effective design space exploration using iSIGHT

Optimization studies for nonlinear constrained problems (i.e. most complex engineering design problems) have repeatedly shown that (i) no single optimization technique performs best for all design problems, and (ii) in most cases, a mix of techniques perform better than a single technique for a given design problem. iSIGHT^TM is a generic software framework for integration, automation, and optimization of design processes that has been developed on the foundation of interdigitation: the strategy of combining multiple optimization algorithms to exploit their desirable aspects for solving complex problems. With the recent paradigm shift from traditional optimization to design space exploration for evaluating “what-if” scenarios and trade-off studies, iSIGHT has grown from an optimization software system to a complete design exploration environment, providing a suite of design exploration tools including a collection of optimization techniques, design of experiments techniques, approximation methods, and probabilistic quality engineering methods. Likewise, the interdigitation design methodology embodied in iSIGHT has grown to support the interdigitation of all design exploration tools for effective design space exploration. In this paper we present an overview of iSIGHT, past and present, of the interdigitation design methodology and its implementation for multiple design exploration tools, and of an industrial case study for which elements of this methodology have been applied. Received December 30, 2000