On the Topology of Genetic Algorithms

1 Introduction

Genetic algorithms (GAs) are search techniques which fall in the broader class of evolutionary algorithms (EAs). Within EAs a population of candidate solutions for a problem is evolved through iterative production and selection. Selection bias is used to ensure that with high probability the quality of the overall population improves in each generation (round of selection). The quality of a solution is referred to as its fitness. GAs are specific for their use of techniques which mimic genetic mechanisms observed in nature, such as gene crossover and mutation, to produce new candidates.

A GA is thus the recursive application of so-called genetic operators to an evolving population P2PM(X), where X is the space of all solutions and PM(X) denotes all multisets which can be constructed from elements in X. A genetic operator may be seen as a random function either mapping from PM(X) to PM(X), or from a finite product, X k ↪k2N, to the solution space X. In other words, if K is a genetic operator from X k to X then for any x1↪ ▷▷▷↪xk2X, K(x1↪ ▷▷▷↪xk) is a random variable on X. Similarly K(A)

may be a random variable on PM(X) for all A2PM(X). Common examples of genetic operators taking values in X include recombination, which produces a random x2X , and takes as argument (usually) two members y↪z2X, known as the parents of x, and mutation, which takes a single argument from X and returns a random element of X which tends to be similar. On the other hand, selection operators take arguments in PM(X) and return a random subset of the argument. Selection operators are used to determine which individuals are used for recombination, as well as to determine which individuals survive in the subsequent generation.

The term "Genetic Algorithm" was coined by John Holland in his seminal work [Holland, 1975], where the potential of GAs was described through schema analysis and the concept of implicit parallelism. Here each candidate solution is encoded as a binary string of fixed length. The positions on such a string are analogies for the gene locations along a genome.

A schema is a template for such representations. Specifically it is a subset of the space of gene representations for which certain positions in the string (gene locations) have specified values. For example, if solutions are encoded using strings of length 7, then a schema in which the first position has value a, and the fourth and fifth positions take values b and c respectively may be represented by

where ⇤'s may assume any value. The schema theorem then states that schemata with simple structure which have above average fitness will tend to proliferate [Holland, 1975]. Simple structure in this case means that few positions have specified value, and also the distance between the first and last specified position is small. With a relative abundance of high quality schemata present in a population, the search inherently operates on the schemata and not the individual positions, and hence there is an implicit reduction in the dimension of the problem [Goldberg, 1989]. Implicit parallelism in the context of GAs refers to the fact that the number of schemata effectively being processed is, in general, far greater than the number of individual candidate solutions. For practically sized problems [Holland, 1980] and [Goldberg, 1985] have shown that O(n3 ) schemata are present for n random binary strings.

The specificity of schema analysis, arising from the fact that solutions must be encoded as linearly arranged strings of a fixed length, has been argued as too limiting and generalisations of the associated theory have been developed by, for example [Vose, 1991], [Radcliffe, 1992], and [Greene, 2000]. Most relevant, and central to the motivation for this paper, is that of [Radcliffe, 1992], and the concept of forma analysis. Forma analysis provides a basis for the representation of candidate solutions in terms of their equivalence class memberships arising from an arbitrary collection of equivalence relations. The representation through equivalance relations provides a convenient and meaningful connection with topology through uniformities. In finite dimensional GAs it is shown that the associated topology is pseudo-metrisable, and provided the choice of equivalence relations is sufficient to describe each solution uniquely the corresponding distance function is a metric. A generalisation of convexity is defined within this topological framework, and connections with forma analysis are established. This notion of convexity is then extended to genetic operators in a way which is consistent with the design constraints given by [Radcliffe, 1994] in the context of forma analysis, and is shown to have connections with exploitation and population convergence.

The success and versatility of GAs has led to a number of explorations into their theoretical properties, including their algebraic structure [Radcliffe, 1994], the spectral properties of genetic operators [Schmitt, 2001], the geometric relationships between genetic operators and the fitness landscape [Moraglio, 2007], and the long run behaviour of GAs through fixed points of dynamical systems [Vose, 1999] and their limiting distributions as Markov chains [Nix and Vose, 1992], [Suzuki, 1995], [Schmitt, 2001] and [Schmitt, 2004]. To our knowledge this is the first paper to formally investigate the topological structure of genetic algorithms.

The remainder of this paper is as follows. In Section 2 forma analysis is discussed in greater detail. Concepts relevant in the remaining paper are also introduced. Section 3 describes the proposed topological framework and provides the main results of this paper. In Section 4 some concluding remarks are given.

2 Forma Analysis

It has been argued [Radcliffe, 1992] that unless the representation of solutions has relevance within the actual solution space, GAs can't do better than random search, and that the emergence of powerful schemata is incidental. That is, unless similarities in the representations described by schemata imply similarity within the solution space as well, the distribution of fitness across schemata is random and collections of highly fit individuals within schemata occur by chance.

A direct and principled address of this concern is given in the context of forma analysis [Radcliffe, 1992]. Here the representation is directly related to subsets of the solution space within which solutions have similar characteristics, which can be defined in terms of equivalence relations. These equivalence relations can also be used to encode information about the fitness function used to evaluate solutions. The representation of a solution is therefore given by the collection of equivalence classes to which it belongs, under an arbitrary collection of equivalence relations over the solution space. These equivalence classes are referred to as formae, and a rigorous presentation of the algebraic structure of formae has been developed [Radcliffe, 1994].

This representation is sufficiently general to capture arguably any problem space, but provides added benefits in terms of interpretability. It also ensures the relevance of the relationship between solutions arising in the same equivalence classes, where in the case of schema analysis these relationships may be fairly arbitrary [Radcliffe, 1992].

Note that a representation via equivalence classes is a generalisation of schema analysis, since schemata can be formulated through equivalence relations. If we return to strings of length 7 then a variable template written as

where ⌅'s represent specified (but variable) positions and ⇤'s are as before unspecified positions, then (2) represents an equivalence relation under which two solutions are equivalent iff they are equal in the first, fourth and fifth positions. The schema given in (1) is therefore an equivalence class arising from this relation.

Henceforth equivalence relations will be written as ⇠, and if two solutions x and y are equivalent under ⇠, we write x⇠y. The equivalence class of a solution x under ⇠ will be written [x]⇠. Combinations of equivalence relations can combine to form smaller and smaller equivalence classes, as described in the following lemma, which can be found in any standard text on algebra.

Lemma 2.1 Let ⇠1 and ⇠2 be two equivalence relations on a set X. Then their intersection ⇠1↪2=⇠1\⇠2, defined as

is an equivalence relation on X and the induced equivalence classes satisfy [x]⇠1↪2 =[x]⇠1 \[x]⇠2 .

This leads us to consider the collection of equivalence relations which result from intersecting different combinations of relations.

Definition Let E be a collection of equivalence relations on a set X. Then the generated set of E, G(E), is defined as the collection of finite intersections of members of E. That is,

The following definitions arise from [Radcliffe, 1994] and are important in the theory presented in Section 3.

Definition A collection of equivalence relations E covers X iff for any x↪y2X with x6=y;9⇠2E s.t. x6⇠y.

Coverage can be understood as a separation of points in X by the members of E. Separation of points is fundamental to the structure of topological spaces, and the notion of coverage above is used to establish a metrisable topology on the search space in the following section.

Definition A collection of equivalence relations E on X is orthogonal if any collection of equivalence classes induced by different members of E has nonempty intersection.

Orthogonality ensures that the mapping from representation to solution is fully defined, but is also crucial in the formulation of convexity which we propose. Convexity requires that the underlying space has no "gaps", i.e., that generalisations of the line segments between points in the representation space are not broken by missingness in the solution space.

[Radcliffe, 1994] also provides useful characterisations of recombination operators; genetic operators which recombine the genes of a small collection of (usually two) members of X. While the results of the following section may be generalised, we will limit attention to recombinations of two individuals' genes.

Definition Let E be a collection of equivalence relations on X. A recombination operator, K, mapping from X⇥X to X, transmits genes if for any pair x↪y2X and ⇠2E, one has Support(K(x↪ y)) ⇢ [x]⇠ [ [y]⇠.

A child solution arising fromK is therefore related to at least one of its parents by each element of E.

Definition Let E be a collection of equivalence relations on X . A recombination operator, K, mapping from X ⇥X to X , respects genes if for any ⇠2G(E) and any y2[x]⇠ one has Support(K(x↪ y)) ⇢ [x]⇠.

Any shared information in the parent solutions, which is expressible in terms of the formae, will remain in all of their children arising from K.

Definition Let E be a collection of equivalence relations on X. A recombination operator, K, mapping from X⇥X to X, assorts genes if for any ⇠1↪⇠22G(E) and x↪y2X with [x]⇠1 \[y]⇠2 6=;, it is possible to produce (possibly over multiple generations) z2[x]⇠1 \[y]⇠2 using only x↪y and their descendents resulting from applications of K.

The assorting property of K means that any combination of genes in a pair of solutions can arise in their descendants. Alternatively, the entirety of their dynastic potential, defined below, can be explored using only the operator K.

Definition Let E be a collection of equivalence relations on X and let L2PM(X). The dynastic potential of L, denoted Γ(L), is defined as all members of X which are related to a member of L by each ⇠2E. Formally,

Γ(L):= {y2X ∣∣8⇠2E9x2L s.t. y⇠x ▷ In the following section these properties of recombination operators will be discussed theoretically in the context of convexity, establishing connections between these definitions and the concepts of exploitative search and population convergence. Conditions are also described which permit the designation of Γ(L) as the potential child solutions arising fromL, their potential "dynasty".

3 The Topology of Genetic Algorithms

This section introduces a topological structure for the solution space of GAs. The equivalence relation formulation adopted in forma analysis provides a convenient and meaningful link with topology through uniform structures.

A uniformity V is a filter on the product X⇥X, i.e., a non-empty collection of subsets of X⇥X which does not contain the empty set and is stable under finite intersection and supersets, which satisfies the following. Each entourage V 2V contains the diagonal of X, ¶(x↪x)♣x2X♦⇢V . For each V 2V there is a U2V s.t. the square of U, U ·U := ¶(x↪y)♣9z2X with (x↪z)↪(z↪y)2U♦, is contained in V . Finally, if V 2V, then the inverse of V , V -1 :=¶(x↪y)♣(y↪x)2 V ♦, is in V.

V generates a topology on X in which the basic neighbourhoods of a point x2X are given by ¶V (x)♦V 2V where, V (x):=¶y2X♣(x↪y)2V ♦. A basis for a uniformity is simply a filter base on X ⇥X for which the generated filter is a uniformity. The following lemma can be found in any extensive text on general topology.

Lemma 3.1 Let E be a non-empty collection of equivalence relations on a set X . Then BE :=¶V⇠♣⇠2G(E)♦, where

is a basis for a uniformity on X , say VE .

We now introduce some of the properties of this topology, in relation to GAs and forma analysis. Firstly, it can be shown that in most practical cases the resulting topology is metrisable. In addition, in the case of representation by binary strings, the metric is equivalent to the hamming distance function.

Lemma 3.2 Let the conditions of Lemma 3.1 hold. If E is finite then the topology generated by VE is pseudo-metrisable.

Proof Consider the function

where ♣ · ♣ is the cardinality operator. It is easy to verify that d is a pseudo-metric. To see that the topologies are equivalent, consider that a point x2X has a smallest pseudometric neighbourhood described by ¶y2X♣x⇠y8⇠2E♦= ¶y2X♣d(x↪y)=0♦. Similarly x has a smallest uniform neighbourhood described by V\⇠2E⇠(x), which is plainly the same set. Thus every pseudo-metric neighbourhood contains a uniform neighbourhood, and vice versa, and hence the topologies are equivalent. ⌅

Corollary 3.3 Let the conditions of Lemma 3.1 hold. If E is finite and covers X then VE is metrisable.

Proof Let d be defined as in the proof of Lemma 3.2. Since E covers X we have 8x↪y2X↪x6=y↪9⇠2E s.t. x6⇠y and so

Therefore d is a metric.

⌅

We can thus endow the space with a topology that conveniently coincides with the theory of forma analysis, and the basic neighbourhoods of a point are merely the formae to which it belongs.

In order to establish connections with exact search methods through convexity it is necessary to define convexity within the current context. Convexity in exact search and optimisation is ostensibly an algebraic property, yet in essence it is a geometric concept. It should therefore be defined witihin topological spaces, and specifically those wherein structure obeys rigidity, namely metrisable topologies.

An existing definition of convexity in general metric spaces already exists [Blumenthal, 1953], yet this definition is not consistent with the algebraic formulation used in search and optimisation. Here a set C is convex in a metric space (X↪d) iff whenever x↪y2C with x6=y there exists z2C distinct from both x and y satisfying d(x↪y)=d(x↪z)+d(z↪y). To see that this is not consistent with the algebraic definition of convexity it is sufficient to consider the rational numbers, Q, in the space (R↪du), where du is the Euclidean metric.

A preferable definition for the current investigation is as follows.

Definition Let (X↪d) be a metric space. A set C⇢X is convex with respect to d iff whenever x↪y2C and 9z2X s.t. d(x↪y)=d(x↪z)+d(z↪y), then z2C.

We will refer to the condition d(x↪y)=d(x↪z)+d(z↪y) as "z is d-between x and y". It is straightforward to check that this definition is consistent with the algebraic notion of convexity.

With this definition we can show that the dynastic potential of a set is equivalent to its convex hull, which is useful for understanding population convergence within the proposed framework. For brevity in the remaining paper we will occasionally not make an explicit distinction between a multiset and the set containing its unique elements. For example, we may state that Γ(L)=L, where Γ(L) by definition is a set and hence this statement is not strictly true whenever L contains repeated elements. What is meant by this equality is Γ(L)⇢L and L⇢Γ(L) for the natural interpretation of inclusion for multisets.

Lemma 3.4 Let the conditions of Lemma 3.1 hold. If E is finite and orthogonal and covers X then the dynastic potential of a set L2PM(X) is equal to its convex hull with respect to the forma based topology.

Proof Plainly L⇢Γ(L). To show that Γ(L) is convex, consider x↪y2Γ(L) and suppose 9z2X s.t. d(x↪y)=d(x↪z)+ d(z↪y). Suppose now that z62Γ(L), then 9⇠2E s.t. z6⇠ w 8w2L. But x↪y2Γ(L))9wx↪wy2L s.t. x⇠wx and y⇠wy, thus z6⇠x and z6⇠y and so ¶⇠2E♣z6⇠x♦\¶⇠2 E♣z 6⇠y♦6=;. Now observe that

But since the two sets on the right hand side have non empty intersection, and E is finite, the size of the left hand side must be strictly less than the sum of those on the right, i.e.

a contradiction. Therefore we must have z2Γ(L).

Now, consider some convex set C with L⇢C. Take z2 Γ(L). Suppose ♣E♣=n and impose some arbitrary ordering of its elements so that E=¶⇠i ♣i=1↪ ▷▷▷↪n♦. Since z2Γ(L) we have 8i2¶1↪ ▷▷▷↪n♦; 9xi2L s.t. z⇠i xi. For integer kn let Ek :=¶⇠i ♣i=1↪ ▷▷▷↪ k♦. By induction on these indexed subsets of E we will show that 8k 9ck2C s.t. 8⇠2Ek, ck⇠z.

We have thus shown by induction that 9c2C s.t. c⇠z 8⇠2E and since E covers X we must have c=z. We thus have that Γ(L)⇢C and hence is the smallest convex set containing L. ⌅

For k=1 take c1=x1 as defined above and the result holds. Suppose the inductive hypothesis holds for some Ek↪1k<n. We have ck↪xk+12C. Take ck+1 to be any member of the equivalence class formed by the intersection of equivalence classes of ck with repsect to ⇠1↪ ▷▷▷↪⇠k↪⇠k+2 ↪ ▷▷▷↪⇠n and of xk+1 with respect to ⇠k+1, which is nonempty since E is orthogonal. It should be plain to see that d(ck↪xk+1)=d(ck↪ck+1)+d(ck+1↪xk+1) and so ck+12C and ck+1⇠z 8⇠2Ek+1 as required.

We can further describe the geometry of convex sets through their extreme points. An extreme point of a convex set, C, is any x2C s.t. C∩¶x♦ is convex. Notice that when looking at extreme points it is more interesting to consider subsets of X , and not multisets.

Lemma 3.5 Let the conditions of Lemma 3.4 hold. Let C⇢ X be convex. Then x2C is an extreme point of C iff 8y2 C∩¶x♦ 9⇠2E s.t. x⇠0 y 8⇠02E ∩¶⇠♦.

Proof First suppose x is an extreme point of C. Suppose though that 9y 2C ∩¶x♦↪⇠1↪⇠22E↪⇠16=⇠2↪ with x6⇠1 y and x6⇠2 y. Since E is orthogonal 9w1↪w2 2X s.t. w1⇠1 y, w1⇠x 8⇠2E ∩¶⇠1♦ and w2⇠2 y, w2⇠x 8⇠2E ∩¶⇠2♦. By design w1 and w2 are d-between x and y and therefore w1↪w22C since C is convex. However, we have ¶⇠2E♣w1 6⇠w2♦=¶⇠1↪⇠2♦, and therefore d(w1↪w2)=2= d(w1↪x)+d(x↪w2), and hence x is d-between w1 and w2. Therefore C∩¶x♦ cannot be convex, a contradiction. Therefore 8y2C∩¶x♦ 9⇠2E s.t. x⇠0 y 8⇠02E ∩¶⇠♦.

Suppose in the converse that 8y2C∩¶x♦ 9⇠2E s.t. x⇠0 y 8⇠02E ∩¶⇠♦. If it were that C∩¶x♦ were not convex, then 9y↪z2C s.t. x is d-between y and z. Then 9⇠1↪⇠22 E↪⇠16=⇠2 with x6⇠1 y and x6⇠2 z. Notice that by assumption we have x⇠y 8⇠2E ∩¶⇠1♦ and x⇠z 8⇠2E ∩¶⇠2♦. Again, since E is orthogonal, 9w2X s.t. w⇠y 8⇠2E ∩¶⇠2 ♦ and w⇠2 z. So w is d-between y and z by design, and hence w2C, since C is convex. But w6⇠1x and w6⇠2x, a contradiction of the assumption. Therefore C∩¶x♦ is convex. ⌅

Convexity in genetic algorithms can also be used to describe exploitative search, as well as to investigate population convergence, as discussed in the sequel. To establish these connections, the definition of convexity is first extended to genetic operators.

Note that given an exploitative recombination operator, it is fairly straightforward to obtain an associated explorative operator as follows. If K is an arbitrary genetic operator mapping X ⇥X to X , then we may define an explorative operator Ke by Ke (x↪y)=K(K(x↪y)↪X), where X is a random variable on X. The degree of exploration can be controlled through the variability of the random variable X.

The converse of defining exploitative operators using only explorative ones, is not so straightforward. We therefore focus only on exploitation in the remainder, which we introduce through convex operators.

Definition A genetic operator K mapping X⇥X to X is convex iff whenever C⇢X is convex we have

We may also define this property for genetic operators mapping from PM(X) to PM(X) in the obvious way; A2 PM(C))Support(K(A))⇢PM(C), where PM(C) is now the collection of multisets arising from elements in C.

We may also think of recombination operators as being in some sense affine. In general we think of a function being affine if it restricted to some subspace of the space of solutions. A similar consideration can be made for recombination operators.

Definition A genetic operator K mapping X⇥X to X is called affine at x in the direction of y2X if 9⇠2E with Γ(¶x↪ y♦) 6=¶x↪ y♦ s.t.

Affine operators may be locally restricted to a subspace, e.g. [y]⇠ in the above definition. In addition, such operators may be viewed in the context of gene dominance, where in the above definition x is dominated by [y]⇠. Although the definition of affine does not provide a direct analogue for affine functions, it admits a natural definition of strict convexity.

Definition A genetic operator K mapping X⇥X to X is strictly convex iff K is convex and nowhere affine.

Such an operator is therefore convex, and cannot become stuck within some subspace of X. While it is clear that strict convexity is a desirable property for recombination operators, it is not sufficient for effective search of the overall GA. We therefore also define a stronger condition as follows.

Definition A genetic operator K mapping X⇥X to X is strongly non-affine if 8x↪y2X the following holds. For all z2Γ(¶x↪y♦) s.t. d(x↪z)=1↪9w2Support(K(x↪y)) s.t. z 2 Support(K(x↪ w)).

Definition A genetic operator K mapping X⇥X to X is strongly convex iff K is convex and strongly non-affine.

The definition of strong convexity does not lend itself immediately to operators mapping PM(X) to PM(X). In this context we define a genetic operator K to be strongly convex if it is convex and whenever A=¶x1↪ ▷▷▷↪xk♦2PM(X), for k>1, we have min¶P(xi 62K(A))↪P(xi2K(A))♦>0 8i2 ¶1↪ ▷▷▷↪ k♦.

These definitions of convexity, strict convexity and strong convexity have direct interpretations in the context of the desirable properties for recombination discussed by [Radcliffe, 1992], which are discussed below.

Lemma 3.6 Let E be a collection of equivalence relations on X and let K be a recombination operator from X ⇥X to X . Then K transmits genes iff it is convex.

Proof Suppose that K transmits genes. Observe that if for x↪y↪z2X we have 8⇠2E either z⇠y or z⇠x, then

Moreover, in the converse of the proof of Lemma 3.4

In all we have that the union of two sets which have empty intersection is contained in another set, and thus the sum of thier sizes must be less than or equal that of the size of the other. In other words

but since d is a pseudo metric, we must have

Thus gene transmissive operators generate children which are d-between their parents, and thus the children must lie in any convex set containing them.

In the converse, suppose that K is convex and take x↪y2X. Then Support(K(x↪y))⇢Γ(¶x↪y♦), since Γ(¶x↪y♦) is convex. For each ⇠2E we therefore have Support(K(x↪y))⇢[x]⇠[[y]⇠, and hence K transmits genes. ⌅

Lemma 3.7 Let E be a collection of equivalence relations on X and let K be a recombination operator mapping X ⇥X to X. If K transmits and assorts genes then it is strictly convex.

Proof We have seen that gene transmission implies convexity, which leaves us with showing that the addition of assortment gives us strict convexity. Suppose that K is a convex operator but is not strictly convex, i.e., it is affine at some x2X. Then 9y2X↪⇠2E with Γ(¶x↪y♦)6=¶x↪y♦ s.t. P(K(x↪z)⇠ x)=0 8z2[y]⇠. Notice that Γ(¶x↪y♦)6=¶x↪y♦)9⇠1↪⇠22 E with x6⇠1 y and x6⇠2 y. Now, since P(K(x↪y)⇠x)=0 we must have x6⇠y. Thus 9⇠02E with ⇠0 6=⇠ and x6⇠y and x6⇠0 y. Now, by definition we have [x]⇠\[y]⇠0 \Γ(¶x↪ y♦)6= ;, and this intersection contains neither x nor y. Because K is affine at x with respect to y and ⇠ we know that no future generations arising from x↪ y and their descendants can be related to x by ⇠, since x is dominated by [y]⇠, and thus no member of the above intersection can occur. However assortment guarantees such an individual can occur. Therefore if K is anywhere affine, it cannot assort, and the result follows. ⌅

Lemma 3.8 Let E be a finite, orthogonal and cover X and let K be a recombination operator mapping X⇥X to X. If K is strongly non-affine then it assorts genes.

Proof Take x↪y2X and⇠1↪⇠22G(E) s.t. [x]⇠1 \[y]⇠2 6=;. Let Ex⇢E be such that (\⇠2Ex ⇠)=⇠1. Assign an arbitrary ordering of the elements of Ex=¶⇠1x ↪ ▷▷▷↪⇠♣Ex♣ x ♦. Since E is orthogonal 9w12X s.t. w1⇠1x x and w⇠y 8⇠2E ∩¶⇠1x ♦. Therefore w12Γ(¶x↪y♦) and d(y↪w1)1. If d(y↪w1)=0 then since E covers X we know w1=y. Otherwise, since K is strongly non-affine 9z12 Support(K(x↪y)) s.t. w12 Support(K(y↪z1)). Therefore w1 can be made using only x↪y and their descendants. Now suppose that for 1k<♣Ex♣ there exists a wk2X satisfying wk⇠ix x for i=1↪ ▷▷▷↪k and wk ⇠y 8⇠2E ∩¶⇠1x ↪ ▷▷▷↪⇠kx ♦ which can be made using only x↪y and their descendants. Similar to above 9wk+12X s.t. wk+1 ⇠ix x 8i=1↪ ▷▷▷↪ k and wk+1 ⇠y 8⇠2E ∩¶⇠1x ↪ ▷▷▷↪⇠k+1 x ♦. Then wk+12Γ(¶wk↪y♦) and d(wk↪wk+1)1. As before we can conclude that wk+1 can be made using only x↪y and their descendants. By induction we can find a w12[x]⇠1 using only x↪y and their descendants. Similarly we can construct a w22[y]⇠2 which remains in [x]⇠1 . Notice that any overlap in the relations, ⇠, contributing to both ⇠1 and ⇠2, must satisfy x⇠y, and so these do not present a problem for the above argument. ⌅

Note that we do not have all recombination operators that assort genes being strongly non-affine. This is because the definition of assortment allows an arbitrary delay until a specific combination of genes can arise, while in the case of strongly non-affine operators an upper bound on the time by which any combination can be produced can easily be derived.

We can use these results to discuss exploitation and convergence in the context of the proposed framework. Convex genetic operators can be seen as exploitative in the sense that they exploit the genetic information present within the population, given by its dynastic potential.

Lemma 3.9 Let E be a finite collection of equivalence relations which is orthogonal and covers X. If all genetic operators are convex then the collection of descendants of a multiset L2PM(X) is contained within their dynastic potential.

Proof The result follows immediately from the fact that L⇢ Γ(L), and Γ(L) is convex. ⌅

Strongly convex operators also have the property of being able to access all elements of Γ(L), for any starting population L, through their gene assorting property. It is also this ability which leads to population convergence. Population convergence is an important consideration in GA methodology. Early convergence does not allow an adequate search of the associated problem domain, yet ultimately the strong gene combinations which have been discovered need to be exploited. Strongly convex operators may be seen as convergent operators, as follows.

Lemma 3.10 Let E be a finite collection of equivalence relations which is orthogonal and covers X. Let Li be the population present in a genetic algorithm at generation i and assume that ¶♣Li♣♦i2N is bounded. If a fixed and finite collection of strongly convex genetic operators are employed in each generation then with probability 1,

where Diam(A)=max¶d(x↪y)♣x↪y2A♦, A2PM(X). Moreover the expected time to convergence is finite.

Proof In the interest of space only an outline is provided here. Let Ci be the child solutions in generation i. By convexity of the operators we know Ci⇢Γ(Li))Li+1⇢ Γ(Li))Diam(Li+1)Diam(Li) with probability 1.

Since a fixed collection of operators is employed we know ♣Ci♣ is bounded and hence ♣Li[Ci♣ is bounded. Moreover, strong convexity of recombination operators and boundedness of ♣Li♣ ensures that P(Diam(Ci)< Diam(Li)) is bounded away from zero uniformly in i for which Diam(Li)>0. The number of pairs x↪y2Li[Ci s.t. d(x↪y)= Diam(Li) is therefore bounded and the probability that all such pairs come from Li (and none from Ci) is bounded away from zero uniformly in i for which Diam(Li)>0.

Suppose the number of pairs defining the diameter of the population is bounded above by M. Then since selection is strongly convex we have P(Diam(Li)< Diam(Li+M))>0 whenever Diam(Li)>0. By the finiteness of E and the boundedness of ♣Li♣ we know P(Diam(Li)< Diam(Li+M))>✏, uniformly in i for which Diam(Li)>0, for some ✏>0. Since the diameter is integer valued, the result follows. ⌅

Note that elitist selection, which is guaranteed to keep the fittest individual in the population, is not strongly convex. However, the above proof can easily be modified to allow elitism since it relies on pairs of individuals being separated by selection, rather than specific singletons being removed.

A practical corollary of the above, is that if the same conditions hold, except that only at least one operator taking values in X is strongly convex, then if the remaining operators taking values in X are applied in each generation with probabilities converging to zero, the diameter of the population converges to zero in probability. The result follows along similar lines, but relies on the fact that the number of generations between applications of the operators which are not strongly convex increases without bound with probability 1. Therefore between each such application, convergence as in Lemma 3.10 occurs. Moreover, the proportion of the generations between these applications which is required for convergence tends to zero with probability 1. Therefore, the proportion of generations in which the population is not converged tends to zero with probability 1.

4 Conclusions

Genetic algorithms are highly versatile search heuristics with broad applicablility in a number of difficult problems and problem types. The effectiveness of GAs has resulted in a number studies into their theoretical properties. The current work introduces a new theoretical perspective on GAs which is consistent with forma analysis. This new approach utilises the equivalence relation basis of forma analysis to generate a topology on the search space via uniformities. The topology is metrisable by a distance function which coincides with the hamming distance in the canonical binary GA described by [Holland, 1975].

The new framework is extremely general, yet provides in addition to the basic topology, a notion of convexity for the discrete context of GAs. Through convexity the concepts of exploitation and population convergence can be investigated.

We hope that this new perspective will permit the transfer of some existing theory from convex analysis to improve the theory and methodology of GAs in the future.

Acknowledgements

The author acknowledges support from the EPSRC funded EP/H023151/1 STOR-i centre for doctoral training.