How Genetic Algorithms Mimic Evolution to Solve Complex Optimization Problems

Genetic Algorithm (GA) is a computational model simulating Darwinian selection and natural elimination, first proposed by J. Holland in 1975. As a global optimization method it is simple, robust, parallelizable, and widely applicable, making it a key intelligent computing technique of the 21st century.

The basic idea imitates biological genetics: problem parameters are represented by genes, solutions by chromosomes, forming a population of individuals. The population competes in an environment; fitter individuals survive and reproduce, passing advantageous genes to offspring, leading the population to evolve toward optimal solutions.

Biological Concepts Used in Genetic Algorithms

The algorithm maps biological concepts to optimization terms:

Individual → basic object to be processed → feasible solution

Population → set of individuals → set of feasible solutions

Chromosome → representation of an individual → encoding of a feasible solution

Gene → element of a chromosome → element of the encoding

Locus → position of a gene in a chromosome → position of an element in the encoding

Fitness value → degree of adaptation of an individual → value of the objective function for a feasible solution

Species → selected group of chromosomes/individuals → selected set of feasible solutions

Selection → choosing superior individuals from the population → retaining or copying individuals with high fitness

Crossover → exchange of gene segments between chromosomes → generating new solutions according to crossover rules

Crossover probability → probability of exchanging gene segments → typically 0.65–0.90

Mutation → change of genes at the chromosome level → alteration of some encoding elements

Mutation probability → probability of gene change → typically 0.001–0.01

Evolution, survival of the fittest → process of eliminating weaker individuals → solution with the best objective‑function value

Steps of a Genetic Algorithm

The optimization process mirrors biological evolution and mainly involves three operators: selection, crossover, and mutation.

The basic workflow is: encode the problem’s solution as a chromosome (binary or decimal string), generate an initial population of chromosomes, evaluate their fitness, select the fittest individuals, apply crossover and mutation to produce a new generation, and repeat until convergence to the optimal chromosome.

Algorithm Procedure

Step 1: Choose an encoding strategy to transform the feasible‑solution set into chromosome structures.

Step 2: Define a fitness function to compute fitness values.

Step 3: Set genetic parameters such as population size, selection method, crossover and mutation operators, and their probabilities.

Step 4: Randomly or specially generate the initial population.

Step 5: Apply selection, crossover, and mutation according to the fitness function to form the next generation.

Step 6: Check whether performance criteria or a maximum number of generations are met; if not, return to step 5.

The algorithm runs until a satisfactory optimal solution is found.

Case Study: Traveling Salesman Problem

Problem Description

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

This is a traveling‑salesman problem. The base is indexed as 0, the targets as 1–100, and the return to the base as 101, forming a distance matrix where each entry represents the geodesic distance between two points on the Earth’s surface.

The geodesic distance between two points with coordinates (λ₁, φ₁) and (λ₂, φ₂) is computed by converting them to 3‑D Cartesian coordinates using the Earth’s radius and then calculating the chord length.

Model and Algorithm

GA parameters: population size = 50, maximum generations = 10, crossover probability = 1, mutation probability = 0.1.

Encoding: decimal encoding; each chromosome is a random permutation of the target indices, with 0 at the start and 101 at the end.

Initial population: generated using a refined nearest‑neighbor heuristic to obtain a good starting set of routes.

Fitness function: total tour length; the objective is to minimize this value.

Crossover: single‑point crossover exchanging gene segments between two parent chromosomes.

Mutation: for a selected individual, three integers u < v < w are chosen (1 ≤ u < v < w ≤ 100); the segment between u and v is moved after position w.

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

The following Python code implements the described GA.

<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; g=10  # w: population size, g: 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]=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 Mathematics Experiment and Modeling / Si Shoukui, Sun Xijing, Science Press.