Integrated crossover rules in real coded genetic algorithms

Modifications in crossover rules and localization of searches are suggested to the real coded genetic algorithms for continuous global optimization. Central to our modifications is the integration of different crossover rules within the genetic algorithm. Numerical experiments using a set of 50 test problems indicate that the resulting algorithms are considerably better than the previous version considered and offer a reasonable alternative to many currently available global optimization algorithms, especially for problems requiring ‘direct search type’ methods.     

Global and local real-coded genetic algorithms based on parent-centric crossover operators

Parent-centric real-parameter crossover operators create the offspring in the neighbourhood of one of the parents, the female parent. The other parent, the male one, defines the range of the neighbourhood. With the aim of improving the behaviour of these crossover operators, we present three processes that are performed before their application. First, a female and male differentiation process determines the individuals in the population that may become female or/and male parents. Then, two different selection mechanisms choose the female and male parents from each group. In addition, we tackle the election of the most adequate evolution model to take out profit from these parent selection mechanisms. The experimental results confirm that these three processes may enhance the operation of the parent-centric crossover operators.     

I-binomial scrambling of digital nets and sequences

The computational complexity of the integration problem in terms of the expected error has recently been an important topic in Information-Based Complexity. In this setting, we assume some sample space of integration rules from which we randomly choose one. The most popular sample space is based on Owen's random scrambling scheme whose theoretical advantage is the fast convergence rate for certain smooth functions.This paper considers a reduction of randomness required for Owen's random scrambling by using the notion of i-binomial property. We first establish a set of necessary and sufficient conditions for digital (0,s)-sequences to have the i-binomial property. Then based on these conditions, the left and right i-binomial scramblings are defined. We show that Owen's key lemma (Lemma 4, SIAM J. Numer. Anal. 34 (1997) 1884) remains valid with the left i-binomial scrambling, and thereby conclude that all the results on the expected errors of the integration problem so far obtained with Owen's scrambling also hold with the left i-binomial scrambling.     

Chaos optimization algorithms based on chaotic maps with different probability distribution and search speed for global optimization

Chaos optimization algorithms (COAs) usually utilize the chaotic map like Logistic map to generate the pseudo-random numbers mapped as the design variables for global optimization. Many existing researches indicated that COA can more easily escape from the local minima than classical stochastic optimization algorithms. This paper reveals the inherent mechanism of high efficiency and superior performance of COA, from a new perspective of both the probability distribution property and search speed of chaotic sequences generated by different chaotic maps. The statistical property and search speed of chaotic sequences are represented by the probability density function (PDF) and the Lyapunov exponent, respectively. Meanwhile, the computational performances of hybrid chaos-BFGS algorithms based on eight one-dimensional chaotic maps with different PDF and Lyapunov exponents are compared, in which BFGS is a quasi-Newton method for local optimization. Moreover, several multimodal benchmark examples illustrate that, the probability distribution property and search speed of chaotic sequences from different chaotic maps significantly affect the global searching capability and optimization efficiency of COA. To achieve the high efficiency of COA, it is recommended to adopt the appropriate chaotic map generating the desired chaotic sequences with uniform or nearly uniform probability distribution and large Lyapunov exponent.     

A niche hybrid genetic algorithm for global optimization of continuous multimodal functions

A niche hybrid genetic algorithm (NHGA) is proposed in this paper to solve continuous multimodal optimization problems more efficiently, accurately and reliably. It provides a new architecture of hybrid algorithms, which organically merges the niche techniques and Nelder–Mead's simplex method into GAs. In the new architecture, the simplex search is first performed in the potential niches, which likely contain a global optimum, to locate the promising zones within search space, quickly and reliably. Then another simplex search is used to quickly discover the global optimum in the located promising zones. The proposed method not only makes the exploration capabilities of GAs stronger through niche techniques, but also has more powerful exploitation capabilities by using simplex search. So it effectively alleviates premature convergence and improves weak exploitation capacities of GAs. A set of benchmark functions is used to demonstrate the validity of NHGA and the role of every component of NHGA. Numerical experiments show that the NHGA may, efficiently and reliably, obtain a more accurate global optimum for the complex and high-dimension multimodal optimization problems. It also demonstrates that the new hybrid architecture is potential and can be used to generate more potential hybrid algorithms.     

A new genetic algorithm for global optimization of multimodal continuous functions

In this paper a new genetic algorithm is developed to find the near global optimal solution of multimodal nonlinear optimization problems. The algorithm defined makes use of a real encoded crossover and mutation operator. The performance of GA is tested on a set of twenty-seven nonlinear global optimization test problems of variable difficulty level. Results are compared with some well established popular GAs existing in the literature. It is observed that the algorithm defined performs significantly better than the existing ones.     

A Metropolis algorithm combined with Hooke-Jeeves local search method applied to global optimization

A hybridization of a recently introduced Metropolis algorithm named the Particle Collision Algorithm (PCA) and the Hooke-Jeeves local search method is applied to a testbed of global optimization functions and to real-world chemical equilibrium nonlinear systems. The results obtained by this method, called HJPCA, are compared against those achieved by two state-of-the-art global optimization methods, C-GRASP and GLOBAL. HJPCA performs better than both algorithms, thus demonstrating its potential for other applications.     

Parallel algorithms for global optimization

In this paper, we report results of implementations of algorithms designed (i) to solve the global optimization problem (GOP) and (ii) to run on a parallel network of transputers. There have always been two alternative approaches to the solution of the GOP, probabilistic and deterministic. Interval methods can be implemented on our network of transputers using Concurrent ADA, and a secondary objective of the tests reported was to investigate the relative computer times required by parallel interval algorithms compared to probabilistic methods.     

Heuristic algorithms for siting alternative-fuel stations using the Flow-Refueling Location Model

This paper presents three heuristic algorithms that solve for the optimal locations for refueling stations for alternative-fuels, such as hydrogen, ethanol, biodiesel, natural gas, or electricity. The Flow-Refueling Location Model (FRLM) locates refueling stations to maximize the flow that can be refueled with a given number of facilities. The FRLM uses path-based demands, and because of the limitations imposed by the driving range of vehicles, longer paths require combinations of more than one station to refuel round-trip travel. A mixed-integer linear programming (MILP) version of the model has been formulated and published and could be used to obtain an optimal solution. However, because of the need for combinations of stations to satisfy demands, a realistic problem with a moderate size network and a reasonable number of candidate sites would be impractical to generate and solve with MILP methods. In this research, heuristic algorithms—specifically the greedy-adding, greedy-adding with substitution and genetic algorithm—are developed and applied to solve the FRLM problem. These algorithms are shown to be effective and efficient in solving complex FRLM problems. For case study purposes, the heuristic algorithms are applied to locate hydrogen-refueling stations in the state of Florida.     

Global one-dimensional optimization using smooth auxiliary functions

In this paper new global optimization algorithms are proposed for solving problems where the objective function is univariate and has Lipschitzean first derivatives. To solve this problem, smooth auxiliary functions, which are adaptively improved during the course of the search, are constructed. Three new algorithms are introduced: the first used the exact a priori known Lipschitz constant for derivatives; the second, when this constant is unknown, estimates it during the course of the search and finally, the last method uses neither the exact global Lipschitz constant nor its estimate but instead adaptively estimates the local Lipschitz constants in different sectors of the search region during the course of optimization. Convergence conditions of the methods are investigated from a general viewpoint and some numerical results are also given. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

A fully adaptive hybrid optimization of aircraft engine blades

A new fully adaptive hybrid optimization method (AHM) has been developed and applied to an industrial problem in the field of the aircraft engine industry. The adaptivity of the coupling between a global search by a population-based method (Genetic Algorithms or Evolution Strategies) and the local search by a descent method has been particularly emphasized. On various analytical test cases, the AHM method overperforms the original global search method in terms of computational time and accuracy. The results obtained on the industrial case have also confirmed the interest of AHM for the design of new and original solutions in an affordable time.     

Global optimization algorithms for a CAD workstation

This paper describes two new versions of the controlled random search procedure for global optimization (CRS). Designed primarily to suit the user of a CAD workstation, these algorithms can also be used effectively in other contexts. The first, known as CRS3, speeds the final convergence of the optimization by combining a local optimization algorithm with the global search procedure. The second, called CCRS, is a concurrent version of CRS3. This algorithm is intended to drive an optimizing accelerator, based on a concurrent processing architecture, which can be attached to a workstation to achieve a significant increase in speed. The results are given of comparative trials which involve both unconstrained and constrained optimization.This work was funded by the Science and Engineering Research Council.     

Integrating particle swarm optimization with genetic algorithms for solving nonlinear optimization problems

Heuristic optimization provides a robust and efficient approach for solving complex real-world problems. The aim of this paper is to introduce a hybrid approach combining two heuristic optimization techniques, particle swarm optimization (PSO) and genetic algorithms (GA). Our approach integrates the merits of both GA and PSO and it has two characteristic features. Firstly, the algorithm is initialized by a set of random particles which travel through the search space. During this travel an evolution of these particles is performed by integrating PSO and GA. Secondly, to restrict velocity of the particles and control it, we introduce a modified constriction factor. Finally, the results of various experimental studies using a suite of multimodal test functions taken from the literature have demonstrated the superiority of the proposed approach to finding the global optimal solution.     

A distance based rule for removing population members in genetic algorithms

In this paper we propose a new rule for removal of population members. We tested the new approach for solving the Quadratic Assignment Problem with excellent results.Received: January 2005, AMS classification: 68T20, 90C59     

Reliability and Performance of UEGO, a Clustering-based Global Optimizer

UEGO is a general clustering technique capable of accelerating and/or parallelizing existing search methods. UEGO is an abstraction of GAS, a genetic algorithm (GA) with subpopulation support, so the niching (i.e. clustering) technique of GAS can be applied along with any kind of optimizers, not only genetic algorithm. The aim of this paper is to analyze the behavior of the algorithm as a function of different parameter settings and types of functions and to examine its reliability with the help of Csendes' method. Comparisons to other methods are also presented.     

Constraint decomposition algorithms in global optimization

Many global optimization problems can be formulated in the form min{c(x, y): x X, y Y, (x, y) Z, y G} where X, Y are polytopes in ^p , ⁿ , respectively, Z is a closed convex set in ^p+n, while G is the complement of an open convex set in ⁿ . The function c: ^p+n is assumed to be linear. Using the fact that the nonconvex constraints depend only upon they-variables, we modify and combine basic global optimization techniques such that some new decomposition methods result which involve global optimization procedures only in ⁿ . Computational experiments show that the resulting algorithms work well for problems with smalln.     

CFD modeling and multi-objective optimization of cyclone geometry using desirability function,artificial neural networks and genetic algorithms

The low-mass loading gas cyclone separator has two performance parameters, the pressure drop and the collection efficiency (cut-off diameter). In this paper, a multi-objective optimization study of a gas cyclone separator has been performed using the response surface methodology (RSM) and CFD data. The effects of the inlet height, the inlet width, the vortex finder diameter and the cyclone total height on the cyclone performance have been investigated. The analysis of design of experiment shows a strong interaction between the inlet dimensions and the vortex finder diameter. No interaction between the cyclone height and the other three factors was observed. The desirability function approach has been used for the multi-objective optimization. A new set of geometrical ratios (design) has been obtained to achieve the best performance. A numerical comparison between the new design and the Stairmand design confirms the superior performance of the new design. As an alternative approach for applying RSM as a meta-model, two radial basis function neural networks (RBFNNs) have been used. Furthermore, the genetic algorithms technique has been used instead of the desirability function approach. A multi-objective optimization study using NSGA-II technique has been performed to obtain the Pareto front for the best performance cyclone separator.     

Evolving fuzzy rule based controllers using genetic algorithms

The synthesis of genetics-based machine learning and fuzzy logic is beginning to show promise as a potent tool in solving complex control problems in multi-variate non-linear systems. In this paper an overview of current research applying the genetic algorithm to fuzzy rule based control is presented. A novel approach to genetics-based machine learning of fuzzy controllers, called a Pittsburgh Fuzzy Classifier System # 1 (P-FCS1) is proposed. P-FCS1 is based on the Pittsburgh model of learning classifier systems and employs variable length rule-sets and simultaneously evolves fuzzy set membership functions and relations. A new crossover operator which respects the functional linkage between fuzzy rules with overlapping input fuzzy set membership functions is introduced. Experimental results using P-FCS 1 are reported and compared with other published results. Application of P-FCS1 to a distributed control problem (dynamic routing in computer networks) is also described and experimental results are presented.     

Product line selection and pricing analysis: Impact of genetic relaxations

A model for the product line selection and pricing problem (PLSP) is presented andthree solution procedures based on a genetic algorithm are developed to analyze the results based on consumer preference patterns. Since the PLSP model is nonlinear and integer, two of the solution procedures use genetic encoding to “relax” the NP hard model. The relaxations result in linear integer and shortest path models for the fitness evaluation which are solved using branch and bound and labeling algorithms, respectively. Performance of the quality of solutions generated by the procedures is evaluated for various problem sizes and customer preference structures. The results show that the genetic relaxations provide efficient and effective solution methodologies for the problem, when compared to the pure artificial intelligence technique of genetic search. The impact of the preference structure on the product line and the managerial implications of the solution characteristics generated by the genetic relaxations are also discussed. The models can be used to explicitly consider tradeoffs between marketing and operations concerns in designing a product line.     

Local search based heuristics for global optimization: Atomic clusters and beyond

Finding good solutions to large scale, hard, global optimization problems, is a demanding task with many relevant applications. It is well known that, in order to tackle a difficult problem, an algorithm has to incorporate all of the available information on the problem domain. However, as we will show in this paper, some general purpose methods and the ideas on which they are built can provide guidance towards the efficient solution of difficult instances. Most of this paper will be devoted to heuristic techniques applied to the problem of finding a minimum energy configuration of a cluster of atoms in R³${\mathbb{R}}^3$. This is a very relevant problem with a large set of applications which has triggered considerable research efforts in the last decade. We will show how some relatively simple ideas can be used to generate fairly efficient methods which have been employed to discover many new cluster structures. In this paper we will introduce some of the main algorithmic ideas which have proven to be particularly successful in the field of global optimization applied to atomic cluster conformation problems. We will mainly discuss Basin Hopping methods, as well as their population–based variant, and some specific technique based on “direct moves”. These methods, although designed for the specific problem, have a much wider applicability. In fact, one of the aims of this paper is also that of suggesting that similar ideas can be employed in order to design innovative methods even for totally different global optimization problems, like, e.g., circle packing and space trajectory planning.