Statistical racing techniques for improved empirical evaluation of evolutionary algorithms

In empirical studies of Evolutionary Algorithms, it is usually desirable to evaluate and compare algorithms using as many different parameter settings and test problems as possible, in border to have a clear and detailed picture of their performance. Unfortunately, the total number of experiments required may be very large, which often makes such research work computationally prohibitive. In this paper, the application of a statistical method called racing is proposed as a general-purpose tool to reduce the computational requirements of large-scale experimental studies in evolutionary algorithms. Experimental results are presented that show that racing typically requires only a small fraction of the cost of an exhaustive experimental study.

On building a principled framework for evaluating and testing evolutionary algorithms: A continuous landscape generator

In this paper, we address some issue related to evaluating and testing evolutionary algorithms. A landscape generator based on Gaussian functions is proposed for generating a variety of continuous landscapes as fitness functions. Through some initial experiments, we illustrate the usefulness of this landscape generator in testing evolutionary algorithms.

Genetic basis of inosine triphosphate pyrophosphohydrolase (ITPA) deficiency

Inosine triphosphate pyrophosphohydrolase (ITPase) deficiency is a common inherited condition characterized by the abnormal accumulation of inosine triphosphate (ITP) in erythrocytes. The genetic basis and pathological consequences of ITPase deficiency are unknown. We have characterized the genomic structure of the ITPA gene, showing that it has eight exons. Five single nucleotide polymorphisms were identified, three silent (138GMA, 561GMA, 708GMA) and two associated with ITPase deficiency (94CMA, IVS2+21AMC). Homozygotes for the 94CMA missense mutation (Pro32 to Thr) had zero erythrocyte ITPase activity, whereas 94CMA heterozygotes averaged 22.5% of the control mean, a level of activity consistent with impaired subunit association of a dimeric enzyme. ITPase activity of IVS2+21AMC homozygotes averaged 60% of the control mean. In order to explore further the relationship between mutations and enzyme activity, we examined the association between genotype and ITPase activity in 100 healthy controls. Ten subjects were heterozygous for 94CMA (allele frequency: 0.06), 24 were heterozygotes for IVS2+21AMC (allele frequency: 0.13) and two were compound heterozygous for these mutations. The activities of IVS2+21AMC heterozygotes and 94CMA/IVS2+21AMC compound heterozygotes were 60% and 10%, respectively, of the normal control mean, suggesting that the intron mutation affects enzyme activity. In all cases when ITPase activity was below the normal range, one or both mutations were found. The ITPA genotype did not correspond to any identifiable red cell phenotype. A possible relationship between ITPase deficiency and increased drug toxicity of purine analogue drugs is proposed.

The Genetic Speciation of Archaeological Fish Bone: A Feasibility Study from Southeast Queensland

Current genetic methods enable highly specific identification of DNA from modern fish bone. The applicability of these methods to the identification of archaeological fish bone was investigated through a study of a sample from late Holocene southeast Queensland sites. The resultant overall success rate of 2% indicates that DNA analysis is, as yet, not feasible for identifying fish bone from any given site. Taphonomic issues influencing the potential of genetic identification methods are raised and discussed in light of this result.

Development of a physical and genetic map of the virulent Wolbachia strain wMelPop

We report here the construction of a physical and genetic map of the virulent Wolbachia strain, wMelPop. This map was determined by ordering 28 chromosome fragments that resulted from digestion with the restriction endonucleases FseI, ApaI, SmaI, and AscI and were resolved by pulsed-field gel electrophoresis. Southern hybridization was done with 53 Wolbachia-specific genes as probes in order to determine the relative positions of these restriction fragments and use them to serve as markers. Comparison of the resulting map with the whole genome sequence of the closely related benign Wolbachia strain, wMel, shows that the two genomes are largely conserved in gene organization with the exception of a single inversion in the chromosome.

Control of vector-borne disease by genetic manipulation of insect populations: technological requirements and research priorities

The possibility of controlling vector-borne disease through the development and release of transgenic insect vectors has recently gained popular support and is being actively pursued by a number of research laboratories around the world. Several technical problems must be solved before such a strategy could be implemented: genes encoding refractory traits (traits that render the insect unable to transmit the pathogen) must be identified, a transformation system for important vector species has to be developed, and a strategy to spread the refractory trait into natural vector populations must be designed. Recent advances in this field of research make it seem likely that this technology will be available in the near future. In this paper we review recent progress in this area as well as argue that care should be taken in selecting the most appropriate disease system with which to first attempt this form of intervention. Much attention is currently being given to the application of this technology to the control of malaria, transmitted by Anopheles gambiae in Africa. While malaria is undoubtedly the most important vector-borne disease in the world and its control should remain an important goal, we maintain that the complex epidemiology of malaria together with the intense transmission rates in Africa may make it unsuitable for the first application of this technology. Diseases such as African trypanosomiasis, transmitted by the tsetse fly, or unstable malaria in India may provide more appropriate initial targets to evaluate the potential of this form of intervention.

Algorithms for sequence analysis via mutagenesis

Despite many successes of conventional DNA sequencing methods, some DNAs remain difficult or impossible to sequence. Unsequenceable regions occur in the genomes of many biologically important organisms, including the human genome. Such regions range in length from tens to millions of bases, and may contain valuable information such as the sequences of important genes. The authors have recently developed a technique that renders a wide range of problematic DNAs amenable to sequencing. The technique is known as sequence analysis via mutagenesis (SAM). This paper presents a number of algorithms for analysing and interpreting data generated by this technique.

Population subdivision in marine environments: the contributions of biogeography, geographic distance, and discontinuous habitat to genetic differentiation in a blennioid

The relative importance of factors that may promote genetic differentiation in marine organisms is largely unknown. Here, contributions to population structure from biogeography, habitat distribution, and isolation by distance were investigated in Axoclinus nigricaudus, a small subtidal rock reef fish, throughout its range in the Gulf of California. A 408 basepair fragment of the mitochondrial control region was sequenced from 105 individuals. Variation was significantly partitioned between many pairs of populations. Phylogenetic analyses, hierarchical analyses of variance, and general linear models substantiated a major break between two putative biogeographic regions. This genetic discontinuity coincides with an abrupt change in ecological characteristics (including temperature and salinity) but does not coincide with known oceanographic circulation patterns. Geographic distance and the nature of habitat separating populations (continuous habitat along a shoreline, discontinuous habitat along a shoreline, and open water) also contributed to population structure in general linear model analyses. To verify that local populations are genetically stable over time, one population was resampled on four occasions over eighteen months; it showed no evidence of a temporal component to diversity. These results indicate that having a planktonic life stage does not preclude geographically partitioned genetic variation over relatively small geographic distances in marine environments. Moreover, levels of genetic differentiation among populations of Axoclinus nigricaudus cannot be explained by a single factor, but are due to the combined influences of a biogeographic boundary, habitat, and geographic distance.

Comparison of BR and QR Eigenvalue Algorithms for Power System Small Signal Stability Analysis

The BR algorithm is a novel and efficient method to find all eigenvalues of upper Hessenberg matrices and has never been applied to eigenanalysis for power system small signal stability. This paper analyzes differences between the BR and the QR algorithms with performance comparison in terms of CPU time based on stopping criteria and storage requirement. The BR algorithm utilizes accelerating strategies to improve its performance when computing eigenvalues of narrowly banded, nearly tridiagonal upper Hessenberg matrices. These strategies significantly reduce the computation time at a reasonable level of precision. Compared with the QR algorithm, the BR algorithm requires fewer iteration steps and less storage space without depriving of appropriate precision in solving eigenvalue problems of large-scale power systems. Numerical examples demonstrate the efficiency of the BR algorithm in pursuing eigenanalysis tasks of 39-, 68-, 115-, 300-, and 600-bus systems. Experiment results suggest that the BR algorithm is a more efficient algorithm for large-scale power system small signal stability eigenanalysis.

A study of the stability of subcycling algorithms in structural dynamics

Algorithms for explicit integration of structural dynamics problems with multiple time steps (subcycling) are investigated. Only one such algorithm, due to Smolinski and Sleith has proved to be stable in a classical sense. A simplified version of this algorithm that retains its stability is presented. However, as with the original version, it can be shown to sacrifice accuracy to achieve stability. Another algorithm in use is shown to be only statistically stable, in that a probability of stability can be assigned if appropriate time step limits are observed. This probability improves rapidly with the number of degrees of freedom in a finite element model. The stability problems are shown to be a property of the central difference method itself, which is modified to give the subcycling algorithm. A related problem is shown to arise when a constraint equation in time is introduced into a time-continuous space-time finite element model. (C) 1998 Elsevier Science S.A.

Extended GCD and Hermite normal form algorithms via lattice basis reduction

Extended gcd calculation has a long history and plays an important role in computational number theory and linear algebra. Recent results have shown that finding optimal multipliers in extended gcd calculations is difficult. We present an algorithm which uses lattice basis reduction to produce small integer multipliers x(1), ..., x(m) for the equation s = gcd (s(1), ..., s(m)) = x(1)s(1) + ... + x(m)s(m), where s1, ... , s(m) are given integers. The method generalises to produce small unimodular transformation matrices for computing the Hermite normal form of an integer matrix.

Genetic structure and evolution of species in the mangrove genus Avicennia (Avicenniaceae) in the Indo-West Pacific

Allozyme variation in species of the mangrove genus Avicennia was screened in 25 populations collected from 22 locations in the Indo-West Pacific and eastern North America using 11 loci. Several fixed gene differences supported the specific status of Avicennia alba, A. integra, A. marina, and A. rumphiana from the Indo-West Pacific, and A. germinans from the Atlantic-East Pacific. The three varieties of A. marina, var. marina, var. eucalyptifolia, and var. australasica, had higher genetic similarities (Nei's I) and no fixed gene differences, confirming their conspecific status. Strong genetic structuring was observed in A. marina, with sharp changes in gene frequencies at the geographical margins of varietal distributions. The occurrence of alleles found otherwise in only one variety, in only immediately adjacent populations of another variety, provided evidence of introgession between varieties. The varieties appear to have diverged recently in the Pleistocene and are apparently not of ancient Cretaceous origin, as suggested earlier. Despite evidence of high degrees of outcrossing, gene flow among populations was relatively low (N(e)m less than or equal to 1-2), except where populations were geographically continuous, questioning assumptions that these widespread mangrove species achieve high levels of long-distance dispersal.

Effects of data characteristics on the results of reserve selection algorithms

We tested the effects of four data characteristics on the results of reserve selection algorithms. The data characteristics were nestedness of features (land types in this case), rarity of features, size variation of sites (potential reserves) and size of data sets (numbers of sites and features). We manipulated data sets to produce three levels, with replication, of each of these data characteristics while holding the other three characteristics constant. We then used an optimizing algorithm and three heuristic algorithms to select sites to solve several reservation problems. We measured efficiency as the number or total area of selected sites, indicating the relative cost of a reserve system. Higher nestedness increased the efficiency of all algorithms (reduced the total cost of new reserves). Higher rarity reduced the efficiency of all algorithms (increased the total cost of new reserves). More variation in site size increased the efficiency of all algorithms expressed in terms of total area of selected sites. We measured the suboptimality of heuristic algorithms as the percentage increase of their results over optimal (minimum possible) results. Suboptimality is a measure of the reliability of heuristics as indicative costing analyses. Higher rarity reduced the suboptimality of heuristics (increased their reliability) and there is some evidence that more size variation did the same for the total area of selected sites. We discuss the implications of these results for the use of reserve selection algorithms as indicative and real-world planning tools.