Computer-aided pipeline operation using genetic algorithms and rule learning. PART II: Rule learning control of a pipeline under normal and abnormal conditions

In this two-paper series, techniques connected with artificial intelligence and genetics are applied to the problem of gas pipeline control. In the first paper, genetic algorithms were applied to two pipeline optimization problems. In this, the second paper, genetic algorithms are used as a basic learning mechanism in a larger rule learning system called a learning classifier system. The learning classifier system is developed and applied to the control of a gas pipeline under normal summer and winter operations as well as abnormal operations during leak events.A learning classifier system is a software system that learns rules called classifiers to guide its behavior in arbitrary environments. Environmental information comes in through sensors and decodes to a finite length message. Messages on a message list match and fire rules called classifiers with explicit pattern recognition capability. Classifiers, once matched, send messages to the message list. These messages may in turn match other classifiers, or they may fire action triggers called effectors. Using environmental reward, the system selects good rules through a reward allocation system based on a competitive service economy. Competition encourages the survival of good rules, those that set up environmental reward. Furthermore, the system tries and learns new rules using a genetic algorithm similar to the one presented in the previous paper.Together, the learning classifier system with its complete rule and message system and powerful learning heuristic is capable of learning how to operate a pipeline under normal and abnormal conditions alike. Computational experiments are presented that demonstrate the systems learning ability under summer and winter conditions starting from a random state of mind. These results compare favorably with a random walk through the decision space. Additionally, the learning classifier system is trained to detect leaks. Repeated exposure to simulated leak events results in the development of rules that permit a high percentage of detected leaks and a low percentage of false alarms.     

On the use of genetic algorithms to solve location problems

This paper seeks to evaluate the performance of genetic algorithms (GA) as an alternative procedure for generating optimal or near-optimal solutions for location problems. The specific problems considered are the uncapacitated and capacitated fixed charge problems, the maximum covering problem, and competitive location models. We compare the performance of the GA-based heuristics developed against well-known heuristics from the literature, using a test base of publicly available data sets.Scope and purposeGenetic algorithms are a potentially powerful tool for solving large-scale combinatorial optimization problems. This paper explores the use of this category of algorithms for solving a wide class of location problems. The purpose is not to “prove” that these algorithms are superior to procedures currently utilized to solve location problems, but rather to identify circumstances where such methods can be useful and viable as an alternative/superior heuristic solution method.     

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.     

Genetic algorithms with age structure

 This paper deals with genetic algorithms with age structure. Evolutionary optimization methods have been successfully applied to complex optimization problems, but the evolutionary optimization methods have a problem of bias in candidate solutions due to genetic drift in search. To solve this problem, we propose the introduction of age structure into genetic algorithms as a simple extension. In nature, an individual is removed from a population when the individual reaches lethal age. Therefore, genetic algorithms with age structure (ASGA) can maintain the genetic diversity of a population by removing aged individuals from the population. First, we conduct simple simulations of two subpopulations considering the age structure. Next, we apply the ASGA to a kanapsack problem. Finally, we discuss the optimal parameters for the age structure of the ASGA. These simulation results indicate that the ASGA can control selection pressure by aging process and relatively maintain the genetic diversity of a population. Received: 17 February 1997/Accepted: 6 May 1997     

Performance assessment of foraging algorithms vs. evolutionary algorithms

The class of foraging algorithms is a relatively new field based on mimicking the foraging behavior of animals, insects, birds or fish in order to develop efficient optimization algorithms. The artificial bee colony (ABC), the bees algorithm (BA), ant colony optimization (ACO), and bacterial foraging optimization algorithms (BFOA) are examples of this class to name a few. This work provides a complete performance assessment of the four mentioned algorithms in comparison to the widely known differential evolution (DE), genetic algorithms (GAs), harmony search (HS), and particle swarm optimization (PSO) algorithms when applied to the problem of unconstrained nonlinear continuous function optimization. To the best of our knowledge, most of the work conducted so far using foraging algorithms has been tested on classical functions. This work provides the comparison using the well-known CEC05 benchmark functions based on the solution reached, the success rate, and the performance rate.     

A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments

Dynamic optimization problems are a kind of optimization problems that involve changes over time.They pose a serious challenge to traditional optimization methods as well as conventional genetic algorithms since the goal is no longer to search for the optimal solution(s) of a fixed problem but to track the moving optimum over time.Dynamic optimization problems have attracted a growing interest from the genetic algorithm community in recent years.Several approaches have been developed to enhance the performance of genetic algorithms in dynamic environments.One approach is to maintain the diversity of the population via random immigrants.This paper proposes a hybrid immigrants scheme that combines the concepts of elitism,dualism and random immigrants for genetic algorithms to address dynamic optimization problems.In this hybrid scheme,the best individual,i.e.,the elite,from the previous generation and its dual individual are retrieved as the bases to create immigrants via traditional mutation scheme.These elitism-based and dualism-based immigrants together with some random immigrants are substituted into the current population,replacing the worst individuals in the population.These three kinds of immigrants aim to address environmental changes of slight,medium and significant degrees respectively and hence efficiently adapt genetic algorithms to dynamic environments that are subject to different severities of changes.Based on a series of systematically constructed dynamic test problems,experiments are carried out to investigate the performance of genetic algorithms with the hybrid immigrants scheme and traditional random immigrants scheme.Experimental results validate the efficiency of the proposed hybrid immigrants scheme for improving the performance of genetic algorithms in dynamic environments.     

Comparison of evolutionary-based optimization algorithms for structural design optimization

In this paper, a comparison of evolutionary-based optimization techniques for structural design optimization problems is presented. Furthermore, a hybrid optimization technique based on differential evolution algorithm is introduced for structural design optimization problems. In order to evaluate the proposed optimization approach a welded beam design problem taken from the literature is solved. The proposed approach is applied to a welded beam design problem and the optimal design of a vehicle component to illustrate how the present approach can be applied for solving structural design optimization problems. A comparative study of six population-based optimization algorithms for optimal design of the structures is presented. The volume reduction of the vehicle component is 28.4% using the proposed hybrid approach. The results show that the proposed approach gives better solutions compared to genetic algorithm, particle swarm, immune algorithm, artificial bee colony algorithm and differential evolution algorithm that are representative of the state-of-the-art in the evolutionary optimization literature.     

A review of applications of genetic algorithms in lot sizing

Lot sizing problems are production planning problems with the objective of determining the periods where production should take place and the quantities to be produced in order to satisfy demand while minimizing production, setup and inventory costs. Most lot sizing problems are combinatorial and hard to solve. In recent years, to deal with the complexity and find optimal or near-optimal results in reasonable computational time, a growing number of researchers have employed meta-heuristic approaches to lot sizing problems. One of the most popular meta-heuristics is genetic algorithms which have been applied to different optimization problems with good results. The focus of this paper is on the recent published literature employing genetic algorithms to solve lot sizing problems. The aim of the review is twofold. First it provides an overview of recent advances in the field in order to highlight the many ways GAs can be applied to various lot sizing models. Second, it presents ideas for future research by identifying gaps in the current literature. In reviewing the relevant literature the focus has been on the main features of the lot sizing problems and the specifications of genetic algorithms suggested in solving these problems.     

基于多近似模型的交互式遗传算法

人的疲劳向题是交互式遗传算法的核心问题,它制约了交互式遗传算法在复杂优化问题中的应用.为了解决该问题,本文提出基于多近似模型的交互式遗传算法.该算法首先将搜索空间划分,然后利用传统交互式遗传算法得到的数据,在不同子空间生成不同的近似模型,最后采用该模型近似人对进化个体的评价,从而减少人评价的数量,有效解决人的疲劳问题.算法性能分析及在服装进化设计系统中的应用验证了其有效性.     

Genetic algorithms in computer aided design

Design is a complex engineering activity, in which computers are more and more involved. The design task can often be seen as an optimization problem in which the parameters or the structure describing the best quality design are sought.Genetic algorithms constitute a class of search algorithms especially suited to solving complex optimization problems. In addition to parameter optimization, genetic algorithms are also suggested for solving problems in creative design, such as combining components in a novel, creative way.Genetic algorithms transpose the notions of evolution in Nature to computers and imitate natural evolution. Basically, they find solution(s) to a problem by maintaining a population of possible solutions according to the ‘survival of the fittest’ principle. We present here the main features of genetic algorithms and several ways in which they can solve difficult design problems. We briefly introduce the basic notions of genetic algorithms, namely, representation, genetic operators, fitness evaluation, and selection. We discuss several advanced genetic algorithms that have proved to be efficient in solving difficult design problems. We then give an overview of applications of genetic algorithms to different domains of engineering design.     

Optimal design of submarine pipeline routes by genetic algorithm with different constraint handling techniques

This work deals with optimization methods for the selection of submarine pipeline routes, employed to carry the oil & gas from offshore platforms. The main motives are related to the assessment of constraint-handling techniques, an important issue in the application of genetic algorithms and other nature-inspired algorithms to such complex, real-world engineering problems.Several methods associated to the modeling and solution of the optimization problem are addressed, including: the geometrical parameterization of candidate routes; their encoding in the context of the genetic algorithm; and, especially, the incorporation into the objective function of the several design criteria involved in the route evaluation. Initially, we propose grouping the design criteria as either “soft” or “hard”, according to the practical consequences of their violation. Then, the latter criteria are associated to different constraint-handling techniques: the classical static penalty function method, and more advanced techniques such as the Adaptive Penalty Method, the ε-Constrained method, and the Ho-Shimizu technique.Case studies are presented to compare the performance of these methods, applied to actual offshore scenarios. The results indicate the importance of clearly characterizing feasible and infeasible solutions, according to the classification of design criteria as “soft” or “hard” respectively. They also indicate that the static penalty approach is not adequate, while the other techniques performed better, especially the ε-Constrained and the Ho-Shimizu methods. Finally, it is seen that the optimization tool may reduce the design time to assess an optimal route, providing accurate results, and minimizing the costs of installation and operation of submarine pipelines.     

Solving fuzzy assembly-line balancing problem with genetic algorithms

Assembly-line balancing problem is known as one of difficult combinatorial optimization problems. This problem has been solved with linear programming, dynamic programming approaches, but unfortunately these approaches do not lead to efficient algorithms. Recently, genetic algorithm has been recognized as an efficient and usefull procedure for solving large and hard combinatorial optimization problems, such as scheduling problems, travelling salesman problems, transportation problems, and so on. Fuzzy sets theory is frequently used to represent uncertainty of information. In this paper, to treat the data of real-world problems we use a fuzzy number to represent the processing time and show that we can get a good performance in solving this problem using genetic algorithms.     

Practical performance models of algorithms in evolutionary program induction and other domains

Evolutionary computation techniques have seen a considerable popularity as problem solving and optimisation tools in recent years. Theoreticians have developed a variety of both exact and approximate models for evolutionary program induction algorithms. However, these models are often criticised for being only applicable to simplistic problems or algorithms with unrealistic parameters. In this paper, we start rectifying this situation in relation to what matters the most to practitioners and users of program induction systems: performance. That is, we introduce a simple and practical model for the performance of program-induction algorithms. To test our approach, we consider two important classes of problems — symbolic regression and Boolean function induction — and we model different versions of genetic programming, gene expression programming and stochastic iterated hill climbing in program space. We illustrate the generality of our technique by also accurately modelling the performance of a training algorithm for artificial neural networks and two heuristics for the off-line bin packing problem.We show that our models, besides performing accurate predictions, can help in the analysis and comparison of different algorithms and/or algorithms with different parameters setting. We illustrate this via the automatic construction of a taxonomy for the stochastic program-induction algorithms considered in this study. The taxonomy reveals important features of these algorithms from the performance point of view, which are not detected by ordinary experimentation.     

Design and analysis of evolutionary bit-length optimization algorithms for floating to fixed-point conversion

Hardware designs need to obey constraints of resource utilization, minimum clock frequency, power consumption, computation precision and data range, which are all affected by the data type representation. Floating and fixed-point representations are the most common data types to work with real numbers where arithmetic hardware units for fixed-point format can improve performance and reduce energy consumption when compared to floating point solution. However, the right bit-lengths estimation for fixed-point is a time-consuming task since it is a combinatorial optimization problem of minimizing the accumulative arithmetic computation error. This work proposes two evolutionary approaches to accelerate the process of converting algorithms from floating to fixed-point format. The first is based on a classic evolutionary algorithm and the second one introduces a compact genetic algorithm, with theoretical evidence that a near-optimal performance, to find a solution, has been reached. To validate the proposed approaches, they are applied to three computing intensive algorithms from the mobile robotic scenario, where data error accumulated during execution is influenced by sensor noise and navigation environment characteristics. The proposed compact genetic algorithm accelerates the conversion process up to 10.2× against the state of art methods reaching similar bit precision and robustness.     

Cartesian path generation of robot manipulators using continuous genetic algorithms

In this paper, the authors describe a novel technique based on continuous genetic algorithms (CGAs) to solve the path generation problem for robot manipulators. We consider the following scenario: given the desired Cartesian path of the end-effector of the manipulator in a free-of-obstacles workspace, off-line smooth geometric paths in the joint space of the manipulator are obtained. The inverse kinematics problem is formulated as an optimization problem based on the concept of the minimization of the accumulative path deviation and is then solved using CGAs where smooth curves are used for representing the required geometric paths in the joint space through out the evolution process. In general, CGA uses smooth operators and avoids sharp jumps in the parameter values. This novel approach possesses several distinct advantages: first, it can be applied to any general serial manipulator with positional degrees of freedom that might not have any derived closed-form solution for its inverse kinematics. Second, to the authors’ knowledge, it is the first singularity-free path generation algorithm that can be applied at the path update rate of the manipulator. Third, extremely high accuracy can be achieved along the generated path almost similar to analytical solutions, if available. Fourth, the proposed approach can be adopted to any general serial manipulator including both nonredundant and redundant systems. Fifth, when applied on parallel computers, the real time implementation is possible due to the implicit parallel nature of genetic algorithms. The generality and efficiency of the proposed algorithm are demonstrated through simulations that include 2R and 3R planar manipulators, PUMA manipulator, and a general 6R serial manipulator.     

Genetic algorithms for a two-agent single-machine problem with release time

Scheduling with two competing agents has drawn a lot of attention lately. However, it is assumed that all the jobs are available in the beginning in most of the research. In this paper, we study a single-machine problem in which jobs have different release times. The objective is to minimize the total tardiness of jobs from the first agent given that the maximum tardiness of jobs from the second agent does not exceed an upper bound. Three genetic algorithms are proposed to obtain the near-optimal solutions. Computational results show that the branch-and-bound algorithm could solve most of the problems with 16 jobs within a reasonable amount of time. In addition, it shows that the performance of the combined genetic algorithm is very good with mean error percentages of less than 0.2% for all the cases.     

Hybrid genetic algorithms for timetabling

Hybrid genetic algorithms are presented that use optimization heuristics and genetic techniques to outperform all existing programs for the timetabling problem. The timetabling problem is very hard (NP-complete) and a general polynomial time deterministic algorithm is not known. An artificial intelligence approach, in a logic programming environment, may be useful for such a problem. The decomposition and classification of constraints and the constraint ordering to obtain the minimization of the backtracking and the maximization of the parallelism are illustrated. The school timetabling problem is discussed in detail as a case study. The genetic algorithm approach is particularly well suited for this kind of problem, since there exists an easy way to assess a good timetable but not a well-structured automatic technique for constructing it. So, a population of timetables is created that evolves toward the best solutions. The evaluation function and the genetic operators are well separated from the domain-specific parts, such as the problem knowledge and the heuristics, i.e., from the timetable builder. A fundamental issue and a general problem in the decision process and automated reasoning is how to efficiently obtain logic decisions under disjunctive constraints. Logic constraint satisfaction problems are in general NP-hard and a general deterministic polynomial time algorithm is not known. The present article illustrates an approach based on the hybridization of constrained heuristic search with novel genetic algorithm techniques. It compares favorably with the best-known programs to solve decisions problems under logic constraints. Complexity of the new algorithms and results of significant experiments are reported. © 1996 John Wiley & Sons, Inc.     

Evolution algorithms in combinatorial optimization

Evolution algorithms for combinatorial optimization have been proposed in the 70's. They did not have a major influence. With the availability of parallel computers, these algorithms will become more important.In this paper we discuss the dynamics of three different classes of evolution algorithms: network algorithms derived from the replicator equation, Darwinian algorithms and genetic algorithms inheriting genetic information.We present a new genetic algorithm which relies on intelligent evolution of individuals. With this algorithm, we have computed the best solution of a famous travelling salesman problem. The algorithm is inherently parallel and shows a superlinear speedup in multiprocessor systems.     

基于多分类支持向量机的优化算法智能推荐系统与实证分析

算法智能推荐是超启发式算法研究领域一个重要分支,其目标是从众多"在线"算法中自动选择出最适于当前问题的算法,从而大大提升解决问题的效率。基于此提出并验证了一种优化算法智能推荐系统,理论依据是无免费午餐定理和Rice算法选择框架,并假设问题特征与算法性能表现之间存在潜在关联关系,从而可以把算法推荐问题转换为一个多分类问题。为了验证假设的成立,以多模式资源约束项目调度问题为测试样本数据集,以粒子群、模拟退火、禁忌搜索和人工蜂群等元启发式优化算法为推荐对象,以支持向量机多分类策略实现算法的分类推荐。交叉验证结果表明,推荐准确率均在90%以上,各项评价指标表现优秀。