How Genetic Algorithms Mimic Evolution to Solve Complex Optimization Problems

1. Genetic Algorithm Biological Concepts

Genetic algorithms are inspired by evolution and genetics, using concepts such as individual, population, chromosome, gene, allele, fitness, etc., mapped to optimization terms.

Individual – the basic object to be processed, corresponds to a feasible solution.

Population – a set of individuals, i.e., a selected group of feasible solutions.

Chromosome – the representation of an individual, i.e., the encoding of a feasible solution.

Gene – an element of a chromosome, i.e., an element of the encoding.

Allele (gene position) – the position of a gene in a chromosome, i.e., the element’s position in the encoding.

Fitness – the degree of adaptation of an individual to the environment, i.e., the value of the objective function for a feasible solution.

Species – a selected set of chromosomes or individuals, i.e., a selected set of feasible solutions.

Selection – choosing superior individuals from the population, i.e., retaining or copying individuals with high fitness.

Crossover – exchanging gene segments between two chromosomes, i.e., generating new solutions according to crossover rules.

Crossover probability – the probability of exchanging gene segments, typically 0.65–0.90.

Mutation – changes in genes at the chromosome level, i.e., altering some elements of the encoding.

Mutation probability – the probability of gene mutation, typically 0.001–0.01.

Evolution (survival of the fittest) – the process of selecting the best individuals, i.e., the optimal feasible solution with the best objective value.

Genetic Algorithm Steps

The algorithm mimics biological evolution through three basic operators: selection, crossover, and mutation.

Step 1: Choose an encoding strategy to represent feasible solutions as chromosomes.

Step 2: Define a fitness function to evaluate individuals.

Step 3: Set genetic parameters (population size, crossover probability, mutation probability, etc.).

Step 4: Randomly generate or construct an initial population.

Step 5: Apply selection, crossover, and mutation to produce the next generation based on fitness values.

Step 6: Check whether termination criteria (e.g., performance threshold or maximum generations) are met; if not, return to Step 5.

Case Study

Problem

Given the longitude and latitude of 100 targets and a base at (70, 40) with a plane speed of 1000 km/h, determine the total time for the plane to depart from the base, visit all targets (inspection time ignored), and return to the base.

This is a traveling‑salesman problem. The base is labeled 0, the targets are labeled 1–100, and the return to the base is labeled 101, forming a symmetric distance matrix. The goal is to find the shortest tour starting at 0, visiting all intermediate points, and ending at 101.

The geographic coordinates must be converted to actual distances using the great‑circle (spherical) formula based on Earth’s radius.

Model and Algorithm

Genetic‑algorithm parameters: population size = 50, maximum generations = 10, crossover rate = 1 (ensuring sufficient evolution), mutation rate = 0.1 (low probability).

(1) Encoding strategy – decimal encoding; a random sequence represents a chromosome, where each position indicates the order of a target.

(2) Initial population – generate an initial population using an improved classic heuristic (e.g., a refined nearest‑neighbor tour) and random permutations.

(3) Objective function – total path length of the tour; the fitness function is the same as the objective.

(4) Crossover operation – single‑point crossover; two parent chromosomes exchange gene segments at a randomly chosen point to create offspring.

(5) Mutation operation – select three indices u < v < w, then move the gene segment between u and v to after position w.

(6) Selection – deterministic selection of the best individuals (lowest tour length) from the combined parent and offspring populations.

Code

<code>import numpy as np
from numpy.random import randint, rand, shuffle
from matplotlib.pyplot import plot, show, rc

a = np.loadtxt("data/generic.txt")
xy, d = a[:, :2], a[:, 2:]  # d is the distance matrix
N = len(xy)
w = 50  # population size
g = 10  # number of generations
J = []
for i in np.arange(w):
    c = np.arange(1, N-1)
    shuffle(c)
    c1 = np.r_[0, c, 101]
    flag = 1
    while flag > 0:
        flag = 0
        for m in np.arange(1, N-3):
            for n in np.arange(m+1, N-2):
                if d[c1[m], c1[n]] + d[c1[m+1], c1[n+1]] < d[c1[m], c1[m+1]] + d[c1[n], c1[n+1]]:
                    c1[m+1:n+1] = c1[n:m:-1]
                    flag = 1
    c1[c1] = np.arange(N)
    J.append(c1)
J = np.array(J) / (N-1)
for k in np.arange(g):
    A = J.copy()
    c1 = np.arange(w)
    shuffle(c1)
    c2 = randint(2, 100, w)
    for i in np.arange(0, w, 2):
        temp = A[c1[i], c2[i]:N-1]
        A[c1[i], c2[i]:N-1] = A[c1[i+1], c2[i]:N-1]
        A[c1[i+1], c2[i]:N-1] = temp
    B = A.copy()
    by = []
    while len(by) < 1:
        by = np.where(rand(w) < 0.1)
    by = by[0]
    B = B[by, :]
    G = np.r_[J, A, B]
    ind = np.argsort(G, axis=1)
    NN = G.shape[0]
    L = np.zeros(NN)
    for j in np.arange(NN):
        for i in np.arange(101):
            L[j] += d[ind[j, i], ind[j, i+1]]
    ind2 = np.argsort(L)
    J = G[ind2, :]
path = ind[ind2[0], :]
zL = L[ind2[0]]
xx = xy[path, 0]
yy = xy[path, 1]
rc('font', size=16)
plot(xx, yy, '-*')
show()
print("所求的巡航路径长度为：", zL)
</code>

Reference

Python数学实验与建模 / 司守奎, 孙玺菁, 科学出版社