Training and testing a self-adaptive multi-operator evolutionary algorithm for constrained optimization

Over the last two decades, many different evolutionary algorithms (EAs) have been introduced for solving constrained optimization problems (COPs). Due to the variability of the characteristics in different COPs, no single algorithm performs consistently over a range of practical problems. To design and refine an algorithm, numerous trial-and-error runs are often performed in order to choose a suitable search operator and the parameters. However, even by trial-and-error, one may not find an appropriate search operator and parameters. In this paper, we have applied the concept of training and testing with a self-adaptive multi-operator based evolutionary algorithm to find suitable parameters. The training and testing sets are decided based on the mathematical properties of 60 problems from two well-known specialized benchmark test sets. The experimental results provide interesting insights and a new way of choosing parameters.     

Surface registration using a dynamic genetic algorithm

Robust and fast free-form surface registration is a useful technique in various areas such as object recognition and 3D model reconstruction for animation. Notably, an object model can be constructed, in principle, by surface registration and integration of range images of the target object from different views. In this paper, we propose to formulate the surface registration problem as a high dimensional optimization problem, which can be solved by a genetic algorithm (GA) (Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989). The performance of the GA for surface registration is highly dependent on its speed in evaluating the fitness function. A novel GA with a new fitness function and a new genetic operator is proposed. It can compute an optimal registration 1000 times faster than a conventional GA. The accuracy, speed and the robustness of the proposed method are verified by a number of real experiments.     

Crew pairing optimization by a genetic algorithm with unexpressed genes

We propose a genetic algorithm to solve the pairing optimization problem for subway crew scheduling. Our genetic algorithm employs new crossover and mutation operators specially designed to work with the chromosomes of set-oriented representation. To enhance the efficiency of the search with the newly designed genetic operators, we let a chromosome consist of an expressed part and an unexpressed part. While the genes in both parts evolve, only the genes in the expressed part are used when an individual is evaluated. The purpose of the unexpressed part is to preserve information susceptible to be lost by the application of genetic operators, and thus to maintain the diversity of the search. Experiments with real-world data have shown that our genetic algorithm outperforms other local search methods such as simulated annealing and tabu search. Received: June 2005/Accepted: December 2005     

A naive genetic approach for non-stationary constrained problems

An algorithm to be effective for solving non-stationary problems should be robust, adaptive to the changing environment and efficient. Genetic algorithms (GAs) are increasingly being used to solve non-stationary problems. We use GA with a new approach of gene induction (Bhatia and Basu in Soft Comput 8(1):1–9, 2003) to solve non-stationary constrained problems. The approach combines high value genes to form chromosomes from the initial population itself. The efficacy of the method is demonstrated on non-stationary versions of 0/1 knapsack and pure-integer programming problems. The results obtained with the approach are compared with those obtained with feedback thermodynamical genetic algorithm (FTDGA) (Mori et al. in 5th parallel problem solving from nature, number 1498 in LNCS, pp 149–157, 1998). It shows that gene-induction approach is more accurate and requires less time compared to the FTDGA.A preliminary version of the paper appeared in the proceedings of the 5th international conference on advances in pattern recognition (Basu and Bhatia 2003).     

基于遗传算法的结晶器液位约束广义预测控制

针对实际连铸过程中结晶器液位控制须满足多种约束的问题,将一种基于遗传算法的有约束广义预测控制方法（ＧＣＧＰＣ）应用于结晶器液位控制．首先基于机理模型构造了有约束结晶器液位广义预测控制器;然后以遗传算法处理带约束的非线性优化问题,并以此作为滚动优化策略,求得最优控制律．仿真结果表明,在有效处理了约束的基础上,基于遗传算法的有约束广义预测控制效果优于ＰＩＤ 控制以及无约束广义预测控制．     

Trend predictions of tick-wise stock prices by means of technical indicators selected by genetic algorithm

We propose a systematic method for predicting the trend of the price time-series at several ticks ahead of the current price by means of a genetic algorithm, used to optimize the combination of the frequently used technical indicators such as various moving averages, the deviation indicator from the moving averages, and so on. We show that the proposed method gives good predictions on the directions of motion, with the rate as high as 80% for multiple stocks of NYSE selected from four different business types. We also show that the performance improves if we combine two or three indicators compared to the case of using a single indicator. However, the performance seems to go down as we increase the number of the indicators from the optimum value. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

Optimum design of structures by an improved genetic algorithm using neural networks

Optimum design of large-scale structures by standard genetic algorithm (GA) makes the computational burden of the process very high. To reduce the computational cost of standard GA, two different strategies are used. The first strategy is by modifying the standard GA, called virtual sub-population method (VSP). The second strategy is by using artificial neural networks for approximating the structural analysis. In this study, radial basis function (RBF), counter propagation (CP) and generalized regression (GR) neural networks are used. Using neural networks within the framework of VSP creates a robust tool for optimum design of structures.     

Research on a face recognition system by the genetic algorithm

Computer vision and recognition is playing an increasingly important role in modern intelligent control. Object detection is the first and most important step in object recognition. Traditionally, a special object can be recognized by the template matching method, but the recognition speed has always been a problem. In this article, an improved general genetic algorithm-based face recognition system is proposed. The genetic algorithm (GA) has been considered to be a robust and global searching method. Here, the chromosomes generated by GA contain the information needed to recognize the object. The purpose of this article is to propose a practical method of face detection and recognition. Finally, the experimental results, and a comparison with the traditional template matching method, and some other considerations, are also given. This work was presented in part at the 11th International Symposium on Artificial Life and Robotics, Oita, Japan, January 23–25, 2006     

A genetic algorithm for a bi-objective capacitated arc routing problem

The capacitated arc routing problem (CARP) is a very hard vehicle routing problem for which the objective—in its classical form—is the minimization of the total cost of the routes. In addition, one can seek to minimize also the cost of the longest trip.In this paper, a multi-objective genetic algorithm is presented for this more realistic CARP. Inspired by the second version of the Non-dominated sorted genetic algorithm framework, the procedure is improved by using good constructive heuristics to seed the initial population and by including a local search procedure. The new framework and its different flavour is appraised on three sets of classical CARP instances comprising 81 files.Yet designed for a bi-objective problem, the best versions are competitive with state-of-the-art metaheuristics for the single objective CARP, both in terms of solution quality and computational efficiency: indeed, they retrieve a majority of proven optima and improve two best-known solutions.     

Determination of optimum robot base location considering discrete end-effector positions by means of hybrid genetic algorithm

The performance of a robot manipulator during a process depends on its position relative to the corresponding path. An ill-placed manipulator risks inefficient operation as well as blocks due to singularities. The paper deals with an optimization algorithm to determine the base position and the joint angles of a spatial robot, when the end-effector poses are prescribed, avoiding the singular configurations. The optimization problem is solved through a hybrid heuristic method that combines the advantages of a genetic algorithm, a quasi-Newton algorithm and a constraints handling method. Six cases of a 6-DOF manipulator are studied to verify the feasibility of the proposed algorithm.     

A simulation-based genetic algorithm approach for remanufacturing process planning and scheduling

Remanufacturing has attracted growing attention in recent years because of its energy-saving and emission-reduction potential. Process planning and scheduling play important roles in the organization of remanufacturing activities and directly affect the overall performance of a remanufacturing system. However, the existing research on remanufacturing process planning and scheduling is very limited due to the difficulty and complexity brought about by various uncertainties in remanufacturing processes. We address the problem by adopting a simulation-based optimization framework. In the proposed genetic algorithm, a solution represents the selected process routes for the jobs to be remanufactured, and the quality of a solution is evaluated through Monte Carlo simulation, in which a production schedule is generated following the specified process routes. The studied problem includes two objective functions to be optimized simultaneously (one concerned with process planning and the other concerned with scheduling), and therefore, Pareto-based optimization principles are applied. The proposed solution approach is comprehensively tested and is shown to outperform a standard multi-objective optimization algorithm.     

Evolution of a vision system by genetic algorithm

This paper proposes a framework for a genetic algorithm applied to determine and construct an organ, especially the neural network of a virtual creature. The vision system of the creature is a result of genetic evolution, and we are trying to realize this on the computer. We examine how the visual organ of the animal is evolved under a special environment (e.g., the specialized visual organ of an animal to catch a moving insect), and how many variations of neural networks exist. We also think it is possible to generalize the method to an automatic generation of various kinds of visual recognition system by adding various kinds of evolution any directions. This work was presented, in part, at the Second International Symposium on Artificial Life and Robotics, Oita, Japan, February 18–20, 1997     

Mesh optimization for surface approximation using an efficient coarse-to-fine evolutionary algorithm

The investigated mesh optimization problem C(N,n) for surface approximation, which is NP-hard, is to minimize the global error between a digital surface and its approximating mesh surface by efficiently locating a limited number n of grid points which are a subset of the original N sample points. This paper proposes an efficient coarse-to-fine evolutionary algorithm (CTFEA) with a novel orthogonal array crossover (OAX) for solving the mesh optimization problem. OAX adaptively divides the meshes of parents into a number of parts using a tuning parameter for applying a coarse-to-fine technique. Meshes of children are formed from an intelligent combination of the good parts from their parents rather than the conventional random combination. The better one of two parts in two parents is chosen by evaluating the contribution of the individual parts to the fitness function based on orthogonal experimental design. The coarse-to-fine technique of CTFEA can advantageously solve large mesh optimization problems. Furthermore, CTFEA using an additional inheritance technique can further efficiently locate the grid points in the mesh surface. It is shown empirically that CTFEA outperforms the existing evolutionary algorithm in terms of both approximation quality and convergence speed, especially in solving large mesh optimization problems.     

A genetic algorithm approach for multi-objective optimization of supply chain networks

Supply chain network (SCN) design is to provide an optimal platform for efficient and effective supply chain management. It is an important and strategic operations management problem in supply chain management, and usually involves multiple and conflicting objectives such as cost, service level, resource utilization, etc. This paper proposes a new solution procedure based on genetic algorithms to find the set of Pareto-optimal solutions for multi-objective SCN design problem. To deal with multi-objective and enable the decision maker for evaluating a greater number of alternative solutions, two different weight approaches are implemented in the proposed solution procedure. An experimental study using actual data from a company, which is a producer of plastic products in Turkey, is carried out into two stages. While the effects of weight approaches on the performance of proposed solution procedure are investigated in the first stage, the proposed solution procedure and simulated annealing are compared according to quality of Pareto-optimal solutions in the second stage.     

Multiple change-point detection with a genetic algorithm

 A common change-point problem is considered where the population mean of a random variable is suspected of undergoing abrupt changes in course of a time series. It is usual in practice that no information on positions or number of such shifts is available beforehand. Finding the change points, i.e. the positions of the shifts, in such a situation is a delicate statistical problem since any considered sample may actually represent a mixture of two or more populations where values from both sides of a yet unrecognized change point are unconsciously assembled. If this is the case, underlying assumptions of an employed statistical two-sample test are usually violated. Consequently, no definite decision should be based on just one value of the test statistic. Such a value is rather, as a precaution, to be regarded as an only approximate indicator of the quality of a hypothesis about change-point positions. Given these conclusions, it is found imperative to treat the problem of multiple change-point detection as one of global optimization. A cost function is constructed in such a manner that the change-point configuration yielding the global optimum is compliant with statistical-theoretical requirements to the utmost extent. The used advanced optimization tool, a genetic algorithm, is both efficient – as it takes advantage of the information about promising change-point positions encountered in previously investigated trial configurations – and flexible (as it is open to any modification of the change-point configuration at any time). Experiments using numerical simulation confirm adequate performance of the method in an application where a common change-point detection procedure based on Student's two-sample t-test is used to detect an arbitrary number of shifts in the mean of a normally distributed random variable.     

Comparison of genetic algorithm to particle swarm for constrained simulation-based optimization of a geothermal power plant

The performance of a genetic algorithm is compared with that of particle swarm optimization for the constrained, non-linear, simulation-based optimization of a double flash geothermal power plant. Particle swarm optimization converges to better (higher) objective function values. The genetic algorithm is shown to converge more quickly and more tightly, resulting in a loss of solution diversity. Particle swarm optimization obtains solutions within 0.1% and 0.5% of the best known optimum in significantly fewer objective function evaluations than the genetic algorithm.     

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     

A genetic algorithm for optimization of laminated dies manufacturing

Laminated tooling is based on taking sheets of metal and stacking them to produce the final product, after cutting each layer profile using laser or other techniques. CNC machining removes the extra material and brings the final product to specific tolerances. To reduce the cost of laminated dies manufacturing, the amount of the extra material and the number of slices must likewise be reduced. This is considered an optimization problem, which can be solved by genetic algorithms (G.A.). However, in most instances, premature convergence prevents the system from searching for a more optimal solution, a common problem in many G.A. applications. To address this problem, a new niching method is presented in this paper. Using the proposed method, results show not only a significant improvement in the quality of the optimum solution but also a substantial reduction in the processing time.     

Structural topology optimization using a genetic algorithm with a morphological geometric representation scheme

This paper describes a versatile methodology for solving topology design optimization problems using a genetic algorithm (GA). The key to its effectiveness is a geometric representation scheme that works by specifying a skeleton which defines the underlying topology/connectivity of a structural continuum together with segments of material surrounding the skeleton. The required design variables are encoded in a chromosome which is in the form of a directed graph that embodies this underlying topology so that appropriate crossover and mutation operators can be devised to recombine and help preserve any desirable geometry characteristics of the design through succeeding generations in the evolutionary process. The overall methodology is first tested by solving ‘target matching’ problems—simulated topology optimization problems in each of which a ‘target’ geometry is first created and predefined as the optimum solution, and the objective of the optimization problem is to evolve design solutions to converge towards this target shape. The methodology is then applied to design two path-generating compliant mechanisms—large-displacement flexural structures that undergo some desired displacement paths at some point when given a straight line input displacement at some other point—by an actual process of topology/shape optimization.     

Performance evaluation of a two stage adaptive genetic algorithm (TSAGA) in structural topology optimization

Genetic algorithm with island and adaptive features has been used for reaching the global optimal solution in the context of structural topology optimization. A two stage adaptive genetic algorithm (TSAGA) involving a self-adaptive island genetic algorithm (SAIGA) for the first stage and adaptive techniques in the second stage is proposed for the use in bit-array represented topology optimization. The first stage, consisting a number of island runs each starting with a different set of random population and searching for better designs in different peaks, helps the algorithm in performing an extensive global search. After the completion of island runs the initial population for the second stage is formed from the best members of each island that provides greater variety and potential for faster improvement and is run for a predefined number of generations. In this second stage the genetic parameters and operators are dynamically adapted with the progress of optimization process in such a way as to increase the convergence rate while maintaining the diversity in population. The results obtained on several single and multiple loading case problems have been compared with other GA and non-GA-based approaches, and the efficiency and effectiveness of the proposed methodology in reaching the global optimal solution is demonstrated.