Genetic algorithms: a survey

Genetic algorithms provide an alternative to traditional optimization techniques by using directed random searches to locate optimal solutions in complex landscapes. We introduce the art and science of genetic algorithms and survey current issues in GA theory and practice. We do not present a detailed study, instead, we offer a quick guide into the labyrinth of GA research. First, we draw the analogy between genetic algorithms and the search processes in nature. Then we describe the genetic algorithm that Holland introduced in 1975 and the workings of GAs. After a survey of techniques proposed as improvements to Holland's GA and of some radically different approaches, we survey the advances in GA theory related to modeling, dynamics, and deception

On an exact populationary model of genetic algorithms

Genetic algorithms (GAs) are search methods that are being employed in a multitude of applications with extremely large search spaces. Recently, there has been considerable interest among GA researchers in understanding and formalizing the working of GAs. In an earlier paper, we have introduced the notion of binomially distributed populations as the central idea behind an exact ''populationary'' model of the large-population dynamics of the GA operators for objective functions called ''functions of unitation.'' In this paper, we extend this populationary model of GA dynamics to a more general class of objective functions called functions of unitation variables. We generalize the notion of a binomially distributed population to a generalized binomially distributed population (GBDP). We show that the effects of selection, crossover, and mutation can be exactly modelled after decomposing the population into GBDPs. Based on this generalized model, we have implemented a GA simulator for functions of two unitation variables-GASIM 2, and the distributions predicted by GASIM 2 match with those obtained from actual GA runs. The generalized populationary model of GA dynamics not only presents a novel and natural way of interpreting the workings of GAs with large populations, but it also provides for an efficient implementation of the model as a GA simulator. (C) Elsevier Science Inc. 1997.

Automatic decomposition of unstructured meshes employing genetic algorithms for parallel FEM computations

Parallel execution of computational mechanics codes requires efficient mesh-partitioning techniques. These mesh-partitioning techniques divide the mesh into specified number of submeshes of approximately the same size and at the same time, minimise the interface nodes of the submeshes. This paper describes a new mesh partitioning technique, employing Genetic Algorithms. The proposed algorithm operates on the deduced graph (dual or nodal graph) of the given finite element mesh rather than directly on the mesh itself. The algorithm works by first constructing a coarse graph approximation using an automatic graph coarsening method. The coarse graph is partitioned and the results are interpolated onto the original graph to initialise an optimisation of the graph partition problem. In practice, hierarchy of (usually more than two) graphs are used to obtain the final graph partition. The proposed partitioning algorithm is applied to graphs derived from unstructured finite element meshes describing practical engineering problems and also several example graphs related to finite element meshes given in the literature. The test results indicate that the proposed GA based graph partitioning algorithm generates high quality partitions and are superior to spectral and multilevel graph partitioning algorithms.

Applying Genetic Algorithms to Optimize Power in Tiled SNUCA Chip Multicore Architectures

We propose a novel technique for reducing the power consumed by the on-chip cache in SNUCA chip multicore platform. This is achieved by what we call a "remap table", which maps accesses to the cache banks that are as close as possible to the cores, on which the processes are scheduled. With this technique, instead of using all the available cache, we use a portion of the cache and allocate lesser cache to the application. We formulate the problem as an energy-delay (ED) minimization problem and solve it offline using a scalable genetic algorithm approach. Our experiments show up to 40% of savings in the memory sub-system power consumption and 47% savings in energy-delay product (ED).

Applying Genetic Algorithms to Optimize Power in Tiled SNUCA Chip Multicore Architectures

We propose a novel technique for reducing the power consumed by the on-chip cache in SNUCA chip multicore platform. This is achieved by what we call a "remap table", which maps accesses to the cache banks that are as close as possible to the cores, on which the processes are scheduled. With this technique, instead of using all the available cache, we use a portion of the cache and allocate lesser cache to the application. We formulate the problem as an energy-delay (ED) minimization problem and solve it offline using a scalable genetic algorithm approach. Our experiments show up to 40% of savings in the memory sub-system power consumption and 47% savings in energy-delay product (ED).

Combination of similarity measures for time series classification using genetic algorithms

Time series classification deals with the problem of classification of data that is multivariate in nature. This means that one or more of the attributes is in the form of a sequence. The notion of similarity or distance, used in time series data, is significant and affects the accuracy, time, and space complexity of the classification algorithm. There exist numerous similarity measures for time series data, but each of them has its own disadvantages. Instead of relying upon a single similarity measure, our aim is to find the near optimal solution to the classification problem by combining different similarity measures. In this work, we use genetic algorithms to combine the similarity measures so as to get the best performance. The weightage given to different similarity measures evolves over a number of generations so as to get the best combination. We test our approach on a number of benchmark time series datasets and present promising results.

Framework for the Shape Optimization of Aerodynamic Profiles Using Genetic Algorithms

This study developed a framework for the shape optimization of aerodynamics profiles using computational fluid dynamics (CFD) and genetic algorithms. Agenetic algorithm code and a commercial CFD code were integrated to develop a CFD shape optimization tool. The results obtained demonstrated the effectiveness of the developed tool. The shape optimization of airfoils was studied using different strategies to demonstrate the capacity of this tool with different GA parameter combinations.

Optimal design of building structures using genetic algorithms

A general framework for multi-criteria optimal design is presented which is well-suited for automated design of structural systems. A systematic computer-aided optimal design decision process is developed which allows the designer to rapidly evaluate and improve a proposed design by taking into account the major factors of interest related to different aspects such as design, construction, and operation.

The proposed optimal design process requires the selection of the most promising choice of design parameters taken from a large design space, based on an evaluation using specified criteria. The design parameters specify a particular design, and so they relate to member sizes, structural configuration, etc. The evaluation of the design uses performance parameters which may include structural response parameters, risks due to uncertain loads and modeling errors, construction and operating costs, etc. Preference functions are used to implement the design criteria in a "soft" form. These preference functions give a measure of the degree of satisfaction of each design criterion. The overall evaluation measure for a design is built up from the individual measures for each criterion through a preference combination rule. The goal of the optimal design process is to obtain a design that has the highest overall evaluation measure - an optimization problem.

Genetic algorithms are stochastic optimization methods that are based on evolutionary theory. They provide the exploration power necessary to explore high-dimensional search spaces to seek these optimal solutions. Two special genetic algorithms, hGA and vGA, are presented here for continuous and discrete optimization problems, respectively.

The methodology is demonstrated with several examples involving the design of truss and frame systems. These examples are solved by using the proposed hGA and vGA.