In a genetic algorithm with integer fitnesses, ties in selection tournaments result in the selection of parent chromosomes effectively at random. A secondary measure that estimates how likely chromosomes are to be improved by the GA's variation operators can break such ties to the algorithm's advantage. Such a secondary fitness for the Bin Packing Problem is based on the maximum unused capacity in any one bin. In tests on 70 instances of the Bin Packing Problem, a permutation-coded genetic algorithm performs better when it applies this measure as a tie-breaker in tournament selection and in elitism than when it does not. The results suggest that similar measures should improve the performance of other GAs that apply tournament selection to chromosomes with integer fitnesses

When evaluating a heuristic for a combinatorial problem, randomly generated instances of the problem may not provide a thorough exploration of the heuristic's performance, and it may not be obvious what kinds of instances challenge or confound the heuristic. An evolutionary algorithm can search a space of problem instances for cases that are heuristically difficult. Evaluation in such an EA requires an exact algorithm for the problem, which limits the sizes of the instances that can be explored, but the EA's (small) results can reveal misleading patterns or structures that can be replicated in larger instances. As an example, a genetic algorithm searches for instances of the quadratic knapsack problem that are difficult for a straightforward greedy heuristic. The GA identifies such instances, which in turn reveal patterns that mislead the heuristic.

Given a collection of terminals, each with a demand, a collection of concentrators, each with a capacity, and costs of connecting the terminals to the concentrators, the terminal assignment problem seeks a set of such connections of minimum cost and without the total demand at any concentrator exceeding its capacity. One genetic algorithm for this problem encodes candidate solutions as strings of concentrator labels; in three other GAs, chromosomes are permutations of terminal labels decoded by a greedy decoder. In comparisons on 40 instances of the problem, the string-coded GA consistently performs poorly, while among the three permutation-coded GAs, one that applies only mutation almost always outperforms the other two, which use crossover operators as well as mutation.

An evolutionary algorithm for some instances of the single-source capacitated plant location problem encodes candidate solutions in two permutations, one of plant locations and a second of customers, with an integer that indicates the number of open locations. A greedy decoder identifies the solution such a genotype represents, and the EA searches for good solutions using only selection and mutation. In tests on 36 problem instances, the EA is competitive with a recent algorithm, though two superficially promising heuristic extensions do not improve its performance. The results support the general effectiveness of permutation codings in EAs that search for optimum subsets.

Given an edge-labeled, connected, undirected graph G and a bound r>1, the bounded minimum-label spanning tree problem seeks a spanning tree on G whose edges carry the fewest possible labels and in which no label appears more than r times. Two greedy heuristics for the unbounded version of the problem are adapted to the bounded version. Two genetic algorithms for the problem encode labeled spanning trees as permutations of G's edges. A simple GA performs poorly, but the addition of local search enables consistently good results.

When an evolutionary algorithm addresses a sequence of instances of the same problem, it can seed its population with solutions that it found for previous instances. This technique is called case injection. How similar must the instances be for case injection to help an EA's search? We consider this question by applying a genetic algorithm, without and with case injection, to sequences of instances of binary quadratic programming. When the instances are similar, case injection helps; when the instances differ sufficiently, case injection is no help at all.

The quadratic multiple knapsack problem extends the quadratic knapsack problem with K knapsacks, each with its own capacity Ck. A greedy heuristic fills the knapsacks one at a time with objects whose contributions are likely to be large relative to their weights. A hill-climber and a genetic algorithm encode candidate solutions as strings over {0,1,...,K} with length equal to the number of objects. The hill-climber's neighbor operator is also the GA's mutation. In tests on 60 problem instances, the GA performed better than the greedy heuristic on the smaller instances, but it fell behind as the numbers of objects and knapsacks grew. The hill-climber always outperformed the greedy heuristic, and on the larger instances, also the GA.

A genetic algorithm for the longest common subsequence problem encodes candidate sequences as binary strings that indicate subsequences of the shortest or first string. Its fitness function penalizes sequences not found in all the strings. In tests on 84 sets of three strings, a dynamic programming algorithm returns optimum solutions quickly on smaller instances and increasingly slowly on larger instances. Repeated trials of the GA always identify optimum subsequences, and it runs in reasonable times even on the largest instances.

Given a connected, undirected graph G with labeled edges, the minimum label spanning tree problem seeks a spanning tree on G to whose edges are attached the smallest possible number of labels. A greedy heuristic for this NP-hard problem greedily chooses labels so as to reduce the number of components in the subgraphs they induce as quickly as possible. A genetic algorithm for the problem encodes candidate solutions as per mutations of the labels; an initial segment of such a chromosome lists the labels that appear on the edges in the chromosome's tree. Three versions of the GA apply generic or heuristic crossover and mutation operators and a local search step. In tests on 27 randomly-generated instances of the minimum-label spanning tree problem, versions of the GA that apply generic operators, with and without the local search step, perform less well than the greedy heuristic, but a version that applies the local search step and operators tailored to the problem returns solutions that require on average 10 fewer labels than the heuristic's.

Many graph problems seek subgraphs of minimum weight that satisfy a set of constraints. Examples include the minimum spanning tree problem (MSTP), the degree-constrained minimum spanning tree problem (d-MSTP), and the traveling salesman problem (TSP). Low-weight edges predominate in optimum solutions to such problems, and the performance of evolutionary algorithms (EAs) is often improved by biasing variation operators to favor these edges. We investigate the impact of biased edge-exchange mutation. In a large-scale empirical investigation on Euclidean and uniform random instances, we describe the distributions of edges in optimum solutions of the MSTP, the d-MSTP, and the TSP in terms of the edges' weight-based ranks. We approximate these distributions by exponential functions and derive approximately optimal probabilities for selecting edges to be incorporated into candidate solutions during mutation. A theoretical analysis of the expected running time of a (1+1)-EA on nondegenerate instances of the MSTP shows that when using the derived probabilities for edge selection in mutation, the (1+1)-EA is asymptotically as fast as a classical implementation of Kruskal's minimum spanning tree algorithm. In experiments on the MSTP, d-MSTP, and the TSP, we compare the new edge-selection strategy to four alternative methods. The results of a (1+1)-EA on instances of the MSTP support the theory and indicate that the new strategy is superior to the other methods in practice. On instances of the d-MSTP, a more sophisticated EA with a larger population and unbiased recombination performs better with the new biased mutation than with alternate mutations. On the TSP, the advantages of weight-biased mutation are generally smaller, because the insertion of a specific new edge into a tour requires the insertion of a second dependent edge as well. Although we considered Euclidean and uniform random instances only, we conjecture that the same biasing toward low-weight edges also works well on other instance classes structured in different ways.

Among the many codings of spanning trees for evolutionary search are those based on bijections between Prüfer strings---strings of n-2 vertex labels---and spanning trees on the labeled vertices. One of these bijections, called the Blob Code, showed promise as an evolutionary coding, but EAs that use it to represent spanning trees have not performed well. Here, a genetic algorithm that represents spanning trees via the Blob Code is faster than, and returns results competitive with those of, a GA that encodes spanning trees as edge-sets on Euclidean instances of the minimum routing cost spanning tree problem. On instances whose edge weights have been chosen at random, the Blob-coded GA maintains its time advantage, but its results are inferior to those of the edge-set-coded GA, and both GAs are hard pressed to keep up with a simple stochastic hill-climber on all the test instances.

Augmenting an evolutionary algorithm with knowledge of its target problem can yield a more effective algorithm, as this presentation illustrates. The Quadratic Knapsack Problem extends the familiar Knapsack Problem by assigning values not only to individual objects but also to pairs of objects. In these problems, an object's value density is the sum of the values associated with it divided by its weight. Two greedy heuristics for the quadratic problem examine objects for inclusion in the knapsack in descending order of their value densities. Two genetic algorithms encode candidate selections of objects as binary strings and generate only strings whose selections of objects have total weight no more than the knapsack's capacity. One GA is naive; its operators apply no information about the values associated with objects. The second extends the naive GA with greedy techniques from the non-evolutionary heuristics. Its operators examine objects for inclusion in the knapsack in orders determined by tournaments based on objects' value densities. All four algorithms are tested on twenty problem instances whose optimum knapsack values are known. The greedy heuristics do well, as does the naive GA, but the greedy GA exhibits the best performance. In repeated trials on the test instances, it identifies optimum solutions more than nine times out of every ten.

Given concentrations of metabolites over a sequence of time steps, the metabolic pathway prediction problem seeks a set of reactions and rate constants for them that could yield the concentration-time data. Such metabolic pathways can be modeled with Petri nets: bipartite graphs whose nodes are called places and transitions and in which tokens move from place to place through the transitions. Thus the pathway prediction problem can be addressed by searching a space of Petri nets, and such a search can be undertaken evolutionarily. Here, a genetic algorithm performs such a search. The GA seeks only the net’s structure; a hill-climbing step applied as part of evaluation approximates parameters associated with the net’s transitions. On one contrived problem instance, the GA sometimes identifies the pathway used to generate the given data, but on a second contrived instance, apparently no harder, it fails. On an instance drawn from real biology—the pathway for phospholipid synthesis—the genetic algorithm identifies a Petri net whose pathway is very similar, but not identical to, the real one. In all three cases, the GA develops Petri nets that represent pathways that closely reproduce the target concentration-time data.

The fundamental design choices in an evolutionary algorithm (EA) are its representation of candidate solutions and the operators that will act on that representation. We propose representing spanning trees in EAs for network design problems directly as sets of their edges and we describe initialization, recombination, and mutation operators for this representation. The operators offer locality, heritability, and computational efficiency. Initialization and recombination depend on an underlying random spanning-tree algorithm. Three choices for this algorithm, based on the minimum spanning-tree algorithms of Prim and Kruskal and on random walks, respectively, are examined analytically and empirically. We demonstrate the usefulness of the edge-set encoding in an EA for the NP-hard degree-constrained minimum spanning-tree problem. The algorithm's operators are easily extended to generate only feasible spanning trees and to incorporate local, problem-specific heuristics. Comparisons of this algorithm to others that encode candidate spanning trees via the Blob Code, with network random keys, and as strings of weights indicate the superiority of the edge-set encoding, particularly on larger instances.

The rectilinear Steiner problem seeks the shortest tree made up of horizontal and vertical line segments that connects a set of points in the plane. The extra points where the segments meet are called Steiner points. Evolutionary algorithms for this problem have encoded rectilinear Steiner trees by extending codings of spanning trees to specify Steiner point choices for the spanning tree edges. These algorithms have been slow and have performed poorly on larger problem instances. The genetic algorithm presented here searches only the space of Steiner point assignments to the edges of a minimum rectilinear spanning tree. In tests on 45 instances of the rectilinear Steiner problem, it returns good, though never optimal, trees. The algorithm scales well; it evaluates chromosomes in time that is linear in the number of points, and its performance does not deteriorate as that number increases.

Genetic algorithms sometimes select chromosomes to be parents according to exponentially normalized probabilities, which decrease by a constant factor r from the population's best chromosome to its worst. Identifying and using such probabilities require sorting the GA's population. A L-tournament with replacement can simulate selection according to exponentially normalized probabilities, but only for population sizes and values of r that correspond to integer tournament sizes (Back 1996, Julstrom 1999). A weighted k-tournament assigns fixed probabilities to its contestants' ranks and selects contestants to be parents according to those probabilities. This paper describes a scheme whereby weighted k-tournaments with replacement can simulate arbitrary exponentially normalized probabilities. The minimum size of such a tournament is a simple function of the GA's population size and the factor of the target exponential normalization. The scheme's second parameter, the factor of exponentially normalized probabilities within the tournament, can be approximated numerically from the approximating and target probabilities or analytically from the target selection pressure.

One of the defining operations of genetic algorithms is selection: choosing chromesomes from the population to generate offspring via crossover or mutation. Researchers have described many selection algorithms, including schemes that apply probabilities based on chromosomes' ranks in the population and that simulate tournaments among chromosomes. The paper investigates two rank based assignments of probabilities: linear normalization and exponential normalization, and two tournament selection schemes: 2-tournament selection without replacement and k-tournament selection with replacement. It makes explicit the probabilities that each associates with the population's chromosomes; demonstrates, following other researchers but using elementary arguments based on these probabilities, the equivalence of linear normalization with 2-tournament selection and of exponential normalization with k-tournament selection; and argues for the use of tournament selection rather than the explicit assignment of rank based probabilities whenever possible.