The Genetic Algorithms

The Genetic algorithms (GAs), which simulate stochastic evolutionary dynamics, are powerful tools used across various interdisciplinary research fields. However, the computational complexity of GAs increases significantly when the evolutionary dynamics become complex. Therefore, I aim to try to apply the TN approach to GAs in order to reduce this computational complexity. This is a brief note for the GAs.


A Simple Model for Geneic Algorithm

In this section, I will detail the construction of the genetic algorithm and explain how to achieve the animation results. The genetic algorithm is an iterative method that allows us to repeat the process until a specific condition is met. The steps are as follows:

Step 0: Generate Random Chromosomes

Initially, we create a set of chromosomes of equal length, generated randomly. Typically represented as sequences of numbers. The more chromosomes generated and the longer their lengths, the better the potential results.

Step 1: Perform Crossover (Mating)

This step simulates the mating process found in evolution. We randomly select two chromosomes and exchange several genes—specific numbers at corresponding positions—to create a new pair of chromosomes. This crossover can occur multiple times. It's important to balance the number of exchanged genes; too few or too many can negatively impact the results.

Step 2: Apply Mutation

In this phase, we introduce genetic mutation. We randomly select some chromosomes and modify a few of their genes, resulting in new chromosomes. After this step, we will have double the number of chromosomes compared to the beginning.

Step 3: Evaluate Fitness

Here, we define an evolutionary function that assigns a real number to each chromosome, indicating its fitness. We then select the top half of the chromosomes based on this evaluation, returning to the same number of chromosomes as in Step 1.

We can repeat step 1 to step 3 until a certain condition is satisfied.

Here is an simple model. I randomly generate a perfect chromosome, the most optimized chromosome, at the beginning. The fitness function is defined as the number of genes different to the perfect chromosome. We can perform the geneic algorithm to see how the evolution looks like.
The concrete steps are as follows:

Step 0: Generate Random Chromosomes

Arrange all the chromosomes in pairs and choose several entries of them (genes) pairwise. Pairwise exchange these entries.

\( |\phi_1\rangle,\cdots,|\phi_N\rangle \in \{0,1\}^N.\)

Step 1: Perform Crossover (Mating)

Randomly select some chromosomes and change several entries of them.
\(|\phi_i\rangle =\begin{pmatrix} \vdots\\ 0\\ \vdots \end{pmatrix}\leftrightarrow \begin{pmatrix} \vdots\\ 1\\ \vdots \end{pmatrix}=|\phi_j\rangle.\)

Step 2: Apply Mutation

In this phase, we introduce genetic mutation. We randomly select some chromosomes and modify a few of their genes, resulting in new chromosomes. After this step, we will have double the number of chromosomes compared to the beginning.

\( |\phi_i\rangle=\begin{pmatrix} \vdots\\ 0\\ \vdots \end{pmatrix}\xrightarrow{}\begin{pmatrix} \vdots\\ 1\\ \vdots \end{pmatrix}\)

Step 3: Evaluate Fitness

Define a perfect chromosome \( |\phi_0\rangle \), it is natural to define the evolutionary function

\(f:\{0,1\}^N\xrightarrow{}\{0,\cdots,N\},\;|\phi_i\rangle\mapsto ||\;|\phi_i\rangle-|\phi_0\rangle\;||_1.\)
Select the top half of the chromosomes based on the evolutionary function.

The simulation result is as the following animation demonstrates: