AI Explained

Evolutionary algorithms (EAs) can be used to solve plenty of tasks using the power of evolutionary optimization. They belong to the family of biologically inspired meta-heuristics and adopt principles from biological evolution to modify, select and iteratively improve a set of candidate solutions (also called a population) to an optimization problem. While many types of EAs exist, this work will focus on genetic algorithms (GA) as the most common representative of EAs. Most commonly, they consist of:

Representation: identification and encoding of decision variables as an individual that represents a candidate solution to the given optimization problem.
Population: a set of candidate solutions. Each iteration of the algorithm will produce a new generation of the population.
Fitness Evaluation: a function measuring the quality of any candidate solution for the given optimization problem.
Selection: a method for selecting well-performing candidate solutions as the input for genetic operators. Selected candidate solutions are called parents.
Genetic Operators: methods that produce a new candidate solution by either modifying an existing candidate solution (mutation) or combining elements from multiple candidate solutions (crossover), thereby producing a population of children.
Reproduction: a method that creates a new population of individuals given the previous population and the children population created by the genetic operators.

One of the key tasks in the algorithm design process is the choice of representation for a candidate solution. Given an optimization task, multiple decision variables can be identified in finding an optimal solution. For example, when optimizing a car for speed we can modify its components, i.e. motor, tires, the size of its tank, etc. A solution candidate can be described by its phenotype and its genotype. The former is represented by the chosen car's components (a specific motor, a set of tires, and a tank's volume), while the latter represents an indirect representation of the car's configuration in a digital format (e.g., indices for each of the choices made). During optimization, a candidate's genotype will be modified. Based on a mapping between genotype and phenotype, a phenotype description of a candidate solution can be created, which in this case allows us to build a car according to the made choices. This also allows us to test the described configuration.

The mapping between genotype and phenotype plays an important part in the algorithm's design. This article presents design concepts based on a discussion on the 8-Queens problem. This seemingly simple puzzle requires placing eight queens on an $$8\times8$$ chessboard so that no two queens threaten each other. Thus, no two queens share the same row, column, or diagonal. The figure below shows positions in which two queens threaten each other.

To solve the 8-Queen problem using a genetic algorithm, the problem needs to be transformed into an optimization problem. A simple function to be optimized would answer the question if the candidate solution solves the puzzle. This function would return the value 1 (yes) in case the puzzle is solved and 0 (no) in case the current board position is invalid. However, this would not give the algorithm much information to select promising candidate solutions. Instead, the number of unthreatened queens placed on the board can be counted, returning values in the range from $$\lbrace 0, 1, ..., 8\rbrace$$. Therefore, the GA will search for board positions that maximize the number of unthreatened queens and a value of 8 signifies that a solution to the puzzle is found.

Do you think you are up to the task of solving the puzzle on your own? Go ahead and try it yourself to find a solution:

Figure 3: Introducing the 8-Queens problem. Drag and drop queens to change their position. Try to position all queens such that no two queens share the same row, column, or diagonal. Queens that threaten each other will be highlighted in red. In case you found a solution all queens will be highlighted in green.

Representation

An individual needs to represent the solution that can be applied to the problem. Here, it needs to encode the positions of queens on a chessboard. Let's first think, about the basic properties of our task and its likely solutions:

Such requirements can be used to further constrain the optimization task. Each added constraint will make some of the unconstrained solution candidates invalid (since they violate the constraint) and therefore directly impact the size of the search space. In the following, a set of optimization tasks constructed by considering combinations of the above constraints will be considered. For each of those, we will be able to identify different decision variables (phenotype) and search for suitable encodings (genotype). Overall, this results in different representations that can be constructed for solving the 8-Queens problem, which allows their comparison with each other.

Based on the requirements, we are ready to start defining our first representation. Just considering the first requirement may spawn some ideas already. Let's consider a chessboard to be an $$8\times8$$ binary matrix in which a 0 encodes an empty field and a 1 a field with a queen on it. You can test this encoding below.

This encoding can produce any possible queen placement of 0 to 64 queens on a regular chessboard. Hence, the solution to this puzzle is included in the set of encodable phenotypes. Sadly, it also creates many candidates that violate the other requirements. Using this representation, it can produce a lot of different candidates. In total there are:

This might be a bit much to find one of the 92 solutions (including 12 unique solutions and all their rotations and reflections). But it can easily be improved by adding the second property to constrain the encoding, namely that no solution can have more or less than 8 queens. Therefore, it limits the number of queens in the matrix to exactly 8. This time, our genotype corresponds to moving a queen on the board because they can neither be spawned nor removed from the board. In case you tried to find a solution yourself at the beginning of this article, you have already used a similar phenotype representation above.

While this seems to be a small but intuitive change, it has a massive impact on the number of possible solutions. Instead of $$2^{64}$$, it produces only: $$\binom{64}{8} = 4\,426\,165\,368$$ combinations.

So far, the first two requirements have been incorporated in the constrained matrix encoding. This can be further improved by adding the constraints on rows, columns, and diagonals to it. Let us consider an even more compressed representation by adding the third property, according to which each row can contain only a single queen. Therefore, a vector of size 8 can be used to encode the column in which each queen is located.

Row Vector Representation

Figure 6: Pheno- and genotype row vector representation of the 8-Queens problem. Click on any cell of the vector to randomly move the respective queen to a new column. Alternatively, you can drag and drop queens on the board along the x-axis. Note that queens cannot be moved to another row since this is forbidden in this encoding.

This might reduce usability for a human user, but the computer will have fewer problems with this. In fact, the reduction to even fewer candidate solutions can drastically speed up the time until a solution is found. Implementing a row vector encoding results in even fewer candidate solutions: $$8^8 = 16\,777\,216$$

An interesting feature of the 8-Queens problem is its symmetry. This means a valid solution may be mirrored and rotated to produce new solutions. The same symmetry can be found in the two properties three and four. Hence, a column vector encoding can be used in place of a row vector.

Column Vector Representation

Figure 7: Pheno- and genotype column vector representation of the 8-Queens problem. Click on any cell of the vector to randomly move the respective queen to a new row. Alternatively, you can drag and drop queens on the board, but only place a queen on another row of the same column. Note that due to the genotype's constraints, queens cannot be moved to another column.

Until now, either property 3 or 4 has been used. Including both of them at the same time makes the representation slightly more complicated, but once again it helps to reduce the number of candidate solutions. In terms of a column vector, each row index can only be included once. Hence, each column vector is effectively a permutation of row indices. This results in a small number of $$8! = 40320$$ candidate solutions. The same can be done for a row vector, which would include a permutation of the letters from $$a$$ to $$h$$.

Up to now, five representations for the 8-queens problem have been introduced. Before discussing their respective mutation and crossover operators, we shortly summarize what we have learned so far.

As stated above, the representation defines the search space of the optimization problem. By including a larger number of requirements in the optimization task and adapting a representation to match these constraints, the search space can be reduced to a feasible size, and therefore, speed up the optimization process. So far, only representations that can produce all solutions to the problem have been used. It is also possible to use a more restrictive search space, but this can come at the cost of solutions becoming impossible to be found. Below is an overview of the introduced representations, their individual size, and their search spaces.

Table 1: Comparison of genotype representations and their resulting size of the search space.

Representation	Size of an Individual	Size of the Search Space
Binary Matrix	$$8 \times 8 = 64$$	$$2^{64} = 18\,446\,744\,073\,709\,551\,616$$
Constrained Matrix	$$8\times 8 = 64$$	$$\binom{64}{8} = 4\,426\,165\,368$$
Row Vector	$$8$$	$$8^8 = 16\,777\,216$$
Column Vector	$$8$$	$$8^8 = 16\,777\,216$$
Permutation	$$8$$	$$8! = 40320$$

We have already seen the different representations in action. Below, a comparison of representations and the individuals they can encode is presented.

Row Vector

Permutation Vector

Column Vector

Constrained Matrix

Figure 9: Comparison of genotype representations of the 8-Queens problem. Drag and drop queens on the board and see how the representations change. In case the current board position cannot be represented using a vector representation, the vector will turn red and be marked with an x.

Mutation

Mutation is an evolutionary operator that modifies a single individual of the population. It is often used for a local exploration of the search space to further exploit a promising solution. This is achieved by making small changes to a candidate solution so that the resulting individual is similar to its parent.

A simple mutation operator is the bit mutation. For any individual that is represented by a collection of bits, bit mutation randomly flips one of them, i.e., turning a $$1$$ to a $$0$$ or vice versa.

Leaving the realm of binary operators behind, we explore how the same concepts can be applied to other value ranges. For this purpose, a sampling method for the mutation needs to be selected. The simplest choice is a uniform distribution that randomly selects one among all the possible values. See below for some examples for various sample spaces and how to mutate them.

The same concept can be used for row and column vectors. A row vector's value space consists of the column names $$\{a, \ldots, h\}$$ while a column vector's values include the row numbers $$[1, \ldots, 8]$$. Both can be tested below:

Finally, the permutation vector needs some special attention. Since each value of the vector can only be used once, it cannot simply replace a value with a random new one. A new class of mutations, suitable for permutations is introduced below.

Binary and value mutation operators do not work for the constrained matrix representation. A single bit-flip would either add another one or remove one of the many zeros. Thus, it violates the constraint of having exactly 8 queens on the board. Similarly, any singular value mutation to a permutation representation will cause an invalid vector. Therefore, another class of mutations called the transposition and swap mutation is introduced. Instead of choosing a single position to be randomly changed, it requires at least two positions to be rearranged. Below, you can try out a swap mutation for the constrained matrix representation already featured above.

More interesting versions of a transposition mutation include the inversion mutation and shuffle mutation. Each operates on a subsequence of the original vector. Similar to the swap mutation, they just reposition existing values but cannot introduce new values to the vector. An inversion mutation inverts the values of a chosen subsequence without moving the subsequence. In contrast, the shuffle mutation randomly reorders the values of a chosen subsequence but keeps the remainder of the vector as it is. Both of these operators keep a permutation vector intact and can be applied to less restrictive genotypes.

Inversion Mutation

Shuffle Mutation

Figure 16: Inversion and shuffle mutation for vector-based representations of the 8-Queens problems. Use the sliders to set the range to which the mutation should be applied. The updated subsequence will be highlighted in red. Note how the shuffle mutation can produce different outcomes for the same subsequence.

Inversion and shuffle mutations can also be implemented for matrix representations and other types of encodings. In the case of a matrix, the mutation inverts or shuffles a set of cells to rearrange the board.

Many more mutation operators can be found, but those discussed above will suffice in the context of the 8-Queens problem. The following table presents a comparison of discussed mutation operators in terms of their determinism after the target index/indices have been selected and their ability to preserve a permutation.

Table 2: Comparison of mutation operators based on determinism and their ability to preserve permutations.

Mutation Operator	Deterministic Result	Permutation Preserving
Binary Mutation	$$\checkmark$$	$$\times$$
Value Mutation	$$\times$$	$$\times$$
Swap Mutation	$$\checkmark$$	$$\checkmark$$
Inversion Mutation	$$\checkmark$$	$$\checkmark$$
Shuffle Mutation	$$\times$$	$$\checkmark$$

Despite that, the mutation operator is one component to locally search the space around promising candidate solutions. The next section will discuss another type of genetic operator that is often used in conjunction with mutation.

Crossover

Crossover is an evolutionary operator that uses two or more candidate solutions to create a new one. The original candidate solutions are called parents, and the resulting individuals are called children. Similar to the mutation operator, a crossover needs to fit the underlying representation of an individual. So far, we have learned about matrix and vector representations and here we will learn some common crossover techniques.

The first and most basic variant is the single-point crossover. It chooses a single cutoff point. Elements to the left of this cutoff point will be filled with information from parent 1, whereas elements to the right will be filled with information from parent 2.

The same concept can be applied to vector representations. See below, the single-point crossover for the column vector representation.

The two-point crossover uses not just one but two cutoff points. Elements in between both points are selected from parent 2, whereas elements outside will be picked from parent 1.

The concept can further be generalized by selecting even more cutoff points. A more variable approach is the uniform crossover, which randomly picks the parent to sample the next element from. Consider throwing a coin for each child element: if the head turns up, uniform crossover samples the element from parent 1; for the tail it samples the element from parent 2.

Many crossover operators are not limited to two parents but can be extended to multiple parents. Below a three-parent uniform crossover is displayed.

The above operators can be applied to matrix and vector representations. However, they are not suitable for permutations. The cycle crossover is a specialized crossover method that keeps permutations intact.

Given the vectors of two parents, it first identifies the so-called cycles. The cycle crossover starts with the first value of parent 1 and searches for its occurrence in parent 2. Once finding the value in parent 2, it uses the value of parent 1 at the same index to once again search for it in parent 2. This process is repeated until the process gets back to the first index of parent 1 representing a complete cycle. All indices visited will be added to this first cycle. This process repeats with the next value not yet sorted into a cycle until all cycles have been identified. Any two vectors can be split into one or multiple such cycles. The figure below shows the process of identifying all cycles in a given permutation.

To produce the child vector, the crossover copies the values of all odd cycles from parent 1 to their respective indices in the child vector. Thereafter, the values of all even cycles from parent 2 are copied into the child vector. The figure below shows the result from the example above.

Similar to mutation operators, many specialized crossover operators have been proposed in the literature. Nevertheless, the presented selection suffices to efficiently solve the 8-Queens problem. To summarize the discussed crossover operators, the following table takes a look at each operator's determinism (after selecting the respective cutoff-points or intervals) and preservation of permutations.

Table 3: Comparison of crossover operators based on their determinism and their ability to preserve permutations.

Crossover Operator	Deterministic Result	Permutation Preserving
1-Point Crossover	$$\checkmark$$	$$\times$$
2-Point Crossover	$$\checkmark$$	$$\times$$
Uniform Crossover	$$\times$$	$$\times$$
Cycle Crossover	$$\checkmark$$	$$\checkmark$$

From Theory to Practice

In the following, we will set up a complete genetic algorithm to solve the 8-Queens problem using the reviewed representations, mutation, and crossover operators. Therefore, the remaining components of the genetic algorithm as introduced at the beginning of this article need to be defined.

Given a combination of representation, mutation, and crossover, the GA runs for a maximum of 1000 generations or terminates early in case a solution has been found. We want to point out, that this GA is designed with simplicity in mind. In general, many choices can be made for each of the building blocks, but for our illustrative example, such a simple configuration will suffice to observe a difference among representations. The following interactive example fills the gaps in representation, mutation, and crossover, and allows running your chosen combination.

Select a Representation

Select a Mutation

Select a Crossover

Figure 24: Test a combination of representation, mutation, and crossover of your choice. First, select a representation in the dropdown menu at the top. Mutation and crossover choices will be updated to match their applicability to the chosen representation. After having selected all three, you can click the button to run a genetic algorithm for 1000 generations. In case a solution has been found, the algorithm will terminate early and show the number of generations spent to find the result. In any case, the best candidate solution of the final population will be shown on the board.

We have run the experiments on our own by repeating the GA 1000 runs for each valid combination of representation, mutation, and crossover. The combinations are ranked by their success rates (finding a valid solution in 1000 generations). In case of a tie, the combination with the lower number of average generations for finding a solution is reported. The following table shows the best combination of mutation and crossover for each of the introduced representations.

Table 4: Comparison of representation mutation and crossover choices based on 1000 runs of each combination. The table shows the best performing combination for each representation as well as the average number of generations that it takes to find a result (capped at 1000 generations).

Representation	Mutation	Crossover	Times Solved	Average Generations
Constrained Matrix	Swap Mutation	1-Point Crossover	$$0$$	$$1000$$
Row Vector	Value Mutation	Uniform Crossover (p=0.5)	$$874$$	$$293$$
Column Vector	Value Mutation	Uniform Crossover (p=0.5)	$$890$$	$$290$$
Permutation Vector	Swap Mutation	Cycle Crossover	$$1000$$	$$23$$

From this example, it can be seen that the permutation vector is the most reliable representation for solving the 8-Queens problem with the lowest number of average generations until finding a solution. Both the row vector and the column vector representations show very similar results since they are based on two symmetric constraints. The constrained matrix performed the worst, which does not mean that it is unable to find a solution. The much larger size of the search space can produce many bad candidate solutions. For this reason, finding a true solution to the 8-Queens problem becomes a daunting task and requires much more than just 1000 generations.

Conclusion

This paper introduced several representations and their respective mutation and crossover operators for solving the 8-Queens Puzzle. It has been shown how the choice of representation impacts the size of the search space and imposes constraints on the choice of genetic operators. Special attention has been given to permutation-preserving mutation and crossover operators.

This overview has not covered all aspects of the algorithm's design process. Further elements such as initialization of the first population, fitness evaluation, selection, and reproduction should be well thought of when implementing an EA. For this purpose, please refer to introductory literature on EAs as well as more detailed selections of mutation and crossover operators, which can help to better understand the EA design process.

For the interested readers, there are many more aspects that can be taken into account for the choice of a representation, including the relationship of a representation and the genetic operators, the feasibility of a representation's genotype, and that feasible solutions should be preferred over infeasible ones. The list could be continued for quite a while and it seems impossible to summarize a whole research field in such a short article, but we hope the work at hand serves as a valuable introduction for readers who are new to the field.

Finally, please find below the set of unique solutions of the 8-Queens problem (considering symmetries of rotation and reflection).