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

Positional Consensus of Multi-Agent Systems Using Linear Programming Based Decentralized Control with Rectilinear Decision Domain

In this paper we develop a Linear Programming (LP) based decentralized algorithm for a group of multiple autonomous agents to achieve positional consensus. Each agent is capable of exchanging information about its position and orientation with other agents within their sensing region. The method is computationally feasible and easy to implement. Analytical results are presented. The effectiveness of the approach is illustrated with simulation results.

Imaging in vivo Neuronal Transport in Genetic Model Organisms Using Microfluidic Devices

Microfluidic devices have been developed for imaging behavior and various cellular processes in Caenorhabditis elegans, but not subcellular processes requiring high spatial resolution. In neurons, essential processes such as axonal, dendritic, intraflagellar and other long-distance transport can be studied by acquiring fast time-lapse images of green fluorescent protein (GFP)-tagged moving cargo. We have achieved two important goals in such in vivo studies namely, imaging several transport processes in unanesthetized intact animals and imaging very early developmental stages. We describe a microfluidic device for immobilizing C. elegans and Drosophila larvae that allows imaging without anesthetics or dissection. We observed that for certain neuronal cargoes in C. elegans, anesthetics have significant and sometimes unexpected effects on the flux. Further, imaging the transport of certain cargo in early developmental stages was possible only in the microfluidic device. Using our device we observed an increase in anterograde synaptic vesicle transport during development corresponding with synaptic growth. We also imaged Q neuroblast divisions and mitochondrial transport during early developmental stages of C. elegans and Drosophila, respectively. Our simple microfluidic device offers a useful means to image high-resolution subcellular processes in C. elegans and Drosophila and can be readily adapted to other transparent or translucent organisms.

Genetic regulation of flower development

Flower development provides a model system to study mechanisms that govern pattern formation in plants. Most flowers consist of four organ types that are present in a specific order from the periphery to the centre of the flower. Reviewed here are studies on flower development in two model species: Arabidopsis thaliana and Antirrhinum majus that focus on the molecular genetic analysis of homeotic mutations affecting pattern formation in the flower. Based on these studies a model was proposed that explains how three classes of regulatory genes can together control the development of the correct pattern of organs in the flower. The universality of the basic tenets of the model is apparent from the analysis of the homologues of the Arabidopsis genes from other plant species

Genetic search: Analysis using fitness moments

Genetic Algorithms are efficient and robust search methods that are being employed in a plethora of applications with extremely large search spaces. The directed search mechanism employed in Genetic Algorithms performs a simultaneous and balanced, exploration of new regions in the search space and exploitation of already discovered regions.This paper introduces the notion of fitness moments for analyzing the working of Genetic Algorithms (GAs). We show that the fitness moments in any generation may be predicted from those of the initial population. Since a knowledge of the fitness moments allows us to estimate the fitness distribution of strings, this approach provides for a method of characterizing the dynamics of GAs. In particular the average fitness and fitness variance of the population in any generation may be predicted. We introduce the technique of fitness-based disruption of solutions for improving the performance of GAs. Using fitness moments, we demonstrate the advantages of using fitness-based disruption. We also present experimental results comparing the performance of a standard GA and GAs (CDGA and AGA) that incorporate the principle of fitness-based disruption. The experimental evidence clearly demonstrates the power of fitness based disruption.

On generating optimal signal probabilities for random tests: A genetic approach

Genetic Algorithms are robust search and optimization techniques. A Genetic Algorithm based approach for determining the optimal input distributions for generating random test vectors is proposed in the paper. A cost function based on the COP testability measure for determining the efficacy of the input distributions is discussed, A brief overview of Genetic Algorithms (GAs) and the specific details of our implementation are described. Experimental results based on ISCAS-85 benchmark circuits are presented. The performance pf our GA-based approach is compared with previous results. While the GA generates more efficient input distributions than the previous methods which are based on gradient descent search, the overheads of the GA in computing the input distributions are larger. To account for the relatively quick convergence of the gradient descent methods, we analyze the landscape of the COP-based cost function. We prove that the cost function is unimodal in the search space. This feature makes the cost function amenable to optimization by gradient-descent techniques as compared to random search methods such as Genetic Algorithms.

Sibling rivalry between seeds within a fruit: Some population genetic models

Competition between seeds within a fruit for parental resources is described using one-locus-two-allele models. While a �normal� allele leads to an equitable distribution of resources between seeds (a situation which also corresponds to the parental optimum), the �selfish� allele is assumed to cause the seed carrying it to usurp a higher proportion of the resources. The outcome of competition between �selfish� alleles is also assumed to lead to an asymmetric distribution of resources, the �winner� being chosen randomly. Conditions for the spread of an initially rare selfish allele and the optimal resource allocation corresponding to the evolutionarily stable strategy, derived for species with n-seeded fruits, are in accordance with expectations based on Hamilton�s inclusive fitness criteria. Competition between seeds is seen to be most intense when there are only two seeds, and decreases with increasing number of seeds, suggesting that two-seeded fruits would be rarer than one-seeded or many-seeded ones. Available data from a large number of plant species are consistent with this prediction of the model.

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.

Solving linear programming problems exactly

A linear programming problem in an inequality form having a bounded solution is solved error-free using an algorithm that sorts the inequalities, removes the redundant ones, and uses the p-adic arithmetic. (C) Elsevier Science Inc., 1997

Shape optimization of RC flexural members

A natural velocity field method for shape optimization of reinforced concrete (RC) flexural members has been demonstrated. The possibility of shape optimization by modifying the shape of an initially rectangular section, in addition to variation of breadth and depth along the length, has been explored. Necessary shape changes have been computed using the sequential quadratic programming (SQP) technique. Genetic algorithm (Goldberg and Samtani 1986) has been used to optimize the diameter and number of main reinforcement bars. A limit-state design approach has been adopted for the nonprismatic RC sections. Such relevant issues as formulation of optimization problem, finite-element modeling, and solution procedure have been described. Three design examples-a simply supported beam, a cantilever beam, and a two-span continuous beam, all under uniformly distributed loads-have been optimized. The results show a significant savings (40-56%) in material and cost and also result in aesthetically pleasing structures. This procedure will lead to considerable cost saving, particularly in cases of mass-produced precast members and a heavy cast-in-place member such as a bridge girder.

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.

Identification of delamination in composite beams using spectral estimation and a genetic algorithm

An efficient strategy for identification of delamination in composite beams and connected structures is presented. A spectral finite-element model consisting of a damaged spectral element is used for model-based prediction of the damaged structural response in the frequency domain. A genetic algorithm (GA) specially tailored for damage identification is derived and is integrated with finite-element code for automation. For best application of the GA, sensitivities of various objective functions with respect to delamination parameters are studied and important conclusions are presented. Model-based simulations of increasing complexity illustrate some of the attractive features of the strategy in terms of accuracy as well as computational cost. This shows the possibility of using such strategies for the development of smart structural health monitoring softwares and systems.