%H> Links %/H>

GENETIC ALGORITHMS IN ALGEBRA
Open Projects

1. Genetic Tietze track.

General description: design a genetic algorithm to find a sequence of elementary Tietze transformations (moves) which transforms a given finite presentation of a group

P = < x_1, ..., x_n | r_1, ... , r_m >
into a presentation with given properties.

Here are some particular tasks.

1.1 Isomorphism test.

Let P and Q be two finite presentations:

P = < x_1, ..., x_n | r_1, ..., r_m >,

Q = < x_1, ..., x_k | s_1, ..., s_l >.

Find genetically a sequence of Tietze moves
T = (t_1, ..., t_q)
that transforms P into Q.

Sketch of the algorithm.

Population.
Let a generation of the population consists of finitely many, say 50, finite sequences T_1, ..., T_50 of Tietze moves.

Fitness function.
A sequence T = (t_1, ...,t_q) has a higher fitness if the presentation

P t_1 t_2 ... t_q = < x_1, ..., x_f | u_1, ..., u_h>
that results in applying moves t_1, ..., t_q to P, has the number of generators f closer to the given number k, and the set of relators u_1, ..., u_h more close to the set s_1, ..., s_l. To make it precise, one can use Hemming's distance for words.

Crossover.
To crossover two sequences

T_1 = (t_1, ... , t_q), T_2 = (t'_1, ...,t'_p)
one may use the standard one-point crossover, i.e., choose randomly numbers 0 < q_1 < q + 1, 0 < p_1 < p + 1 and make the sequences (children)
(t_1, ... , t_q_1, t'_p_1, ...,t'p),

(t'_1, ... , t'_p_1, t_q_1+1, ...,t_q).

For details see [AC].

Algorithms halts if for some sequence T the resulting presentation PT is equal to the presentation Q. In this event P and Q define isomorphic groups. If the groups given by the presentations P and Q are not isomorphic then the algorithm never stops.

1.2 Find a presentation which is equivalent to a given presentation P and has minimal number of generators.

Design is similar to the previous algorithm, only the fitness function is higher for presentations with the smaller number of generators.

1.3 Find a presentation which is equivalent to a given presentation P and has minimal total length of relators.

Again, setup is as above, only the fitness function is higher for presentations with smaller total length (the sum of lengths of relators) of relators.

2. Genetic coset enumerator.

3. One relator groups.

3.1 Word problem for one relator groups.

General description: design a genetic algorithm to find a sequence of elementary reductions (insert a conjugate of a relator into a word or delete a conjugate of a relator in the word) which transforms a given word w into empty word.

Design of the algorithm is similar to the design above. The fitness function is higher if the length of the word is smaller.

Algorithm stops when it finds a word of zero length. If the given word does not determine the trivial element in the group then the algorithm never stops.

3.2 Conjugacy problem for one-relator groups.

General description: design a genetic algorithm to find a sequence of elementary reductions (the same as above and conjugation) which transforms a given word u into a given word v.

Design is similar to the word problem, only the fitness function measures on how a word from the generation is close to the word v.

For one-relator groups with torsion one can try to design an algorithm using hyperbolicity of these groups. In this case it is easy to check whether two words define equal elements in the group or not. So one can use only conjugations as elementary reductions, and Dehns algorithm for computing the fitness function.