8 Genetic Algorithm Variants

This chapter surveys practical variants of genetic algorithms and how to deploy them across continuous and discrete optimization tasks. Building on the standard GA workflow, it contrasts encoding choices and operator design, explains how to balance exploration and exploitation, and demonstrates end-to-end solutions on real problems such as traveling salesman routing, PID controller tuning, and political districting. Throughout, it emphasizes fit-for-purpose representations, operator selection, and decision-making for single- and multi-objective goals.

Key variants include Gray-coded GA, which replaces standard binary encoding to mitigate the Hamming cliff by ensuring adjacent values differ in only one bit—improving locality at the cost of problem-dependent gains. For continuous variables, real-valued GA is recommended due to higher precision, efficiency, and smoother search, using arithmetic and simulated binary crossover (SBX) with mutations such as Gaussian, Cauchy, boundary, and polynomial. For ordering problems, permutation-based GA preserves feasibility with specialized crossovers—PMX, edge, order-1, and cycle—and mutations including insert, swap, inversion, and scramble, enabling effective search on problems like the traveling salesman.

Multi-objective optimization is addressed via Pareto concepts and algorithms such as NSGA-II, using non-dominated sorting, population diversity, and post hoc decision-making aided by ideal/nadir points and scalarization (e.g., ASF). The chapter also covers adaptive GAs that tune parameters during the run—adjusting population size and mutation step sizes deterministically, via success rules (e.g., the 1/5 rule), or through self-adaptation. Case studies tie these ideas together: permutation operators and repair for TSP, real-valued GA to minimize time-domain error criteria in PID tuning, and a constrained districting model that enforces population balance and contiguity—illustrating how encoding, operators, and adaptation jointly drive robust solutions.

Gray coding and binary-to-Gray conversion

Single arithmetic crossover in real-valued GA

Simple arithmetic crossover in real-valued GA

Whole arithmetic crossover in real-valued GA

Equation 8.1

Partially Mapped Crossover (PMX). During step 1, two random crossover points are chosen and the cities between these two points are copied from parent P1 to child C1 and from the second parent P2 to the second child C2. Later, we follow steps 2-6 to complete the other cities that are not included. For the first city in C1, which is 3, we need to find the corresponding city in the P2's segment, which is 7. City 7 is not already included in the C1, so we need to place city 7 in the place that city 3 appears in P2, which is the last position from left to right as shown by the solid black line.

PMX results

Edge Crossover

Order 1 Crossover (OX1). The numbers in circles show the sequence of adding elements from Parent 2 to Child 1.

Cycle Crossover (CX)

Mutation methods in permutation-based GA

Inversion mutation result

Acceleration time vs driving range of 19 electric vehicles as per September 2021.

Manufacturing problem solution. The point with X represents the selected Pareto optimal or the best tradeoff.

Equation 8.2

Equation 8.3

Rechenberg’s ‘1/5 success rule. Following this rule, Gaussian distribution standard deviation is updated by a constant. The higher the standard deviation/variance, the higher the value of x (i.e., larger step size), the higher deviation from the current solution (more exploration), and vice versa.

The 20 major US cities TSP

The 20 major US cities TSP solution

Equation 8.4

PID-based Closed-loop Control System. The PID controller takes the error signal and produces a control signal to reduce the error to zero.

Step response of a system. Rise time is the time required for the response to rise from 10% to 90% of its final value. Peak overshoot (aka maximum overshoot) is the deviation of the response at peak time from the final value of the response. Settling time is the time required for the response to reach the steady state and stay within the specified tolerance bands (e.g., 2%-5%) around the final value. Steady-state error is the difference between the desired value and the actual value of a system output. The heater is turned ON/OFF according to the difference between the actual temperature and the desired value.

Closed loop control system

Equation 8.5

Equation 8.6

Equation 8.7

Step response

The given 16 neighborhoods in Toronto East with their population and median household income

The 3 political districts that combine the 16 neighborhoods

• The Hamming Cliff Problem due to the inherent nature of binary representation negatively affects binary-coded GAs by disrupting the search space's smoothness, causing poor convergence, and leading to inefficient exploration and exploitation. To address the Hamming Cliff Problem, alternative representations like Gray code or real-valued encoding can be used, as they offer better locality and smoother search spaces, minimizing the effects of small changes on decoded values.
• Real-valued GA is well-suited for optimization problems involving continuous variables or real-valued parameters. It offers benefits such as better representation precision, faster convergence, diverse crossover and mutation operations, and reduced complexity, making it an attractive choice for many continuous optimization problems.
• Permutation-based GA is a class of genetic algorithms specifically designed to handle combinatorial optimization problems where the solutions can be represented as ordered sequences, or permutations, of elements.
• Multi-objective optimization problems can be tackled using either a preference-based multi-objective optimization method or a Pareto optimization approach. In the preference-based method, the multiple objectives are combined into a single or overall objective function by using a weighting scheme. On the other hand, the Pareto optimization approach focuses on identifying multiple trade-off optimal solutions known as Pareto-optimal solutions. These solutions can be further refined using higher-level information or decision-making processes.
• Crossover is primarily exploitative as it combines genetic material of two parent individuals to produce offspring, promoting the exchange of beneficial traits between solutions. However, depending on the implementation, crossover can also have some explorative properties as it can produce offspring with new combinations of genes, leading to the discovery of new solutions.
• Mutation can act as an explorative or exploitative operator depending on influencing factors such as the mutation rate and the mutation step size.
• In general terms, the crossover rate should be relatively high, as it promotes the exchange of genetic information between parent chromosomes. On the other hand, mutation is typically applied with a low probability, as its main purpose is to introduce random variations into the population.

FAQ