Genetic Algorithm Definition

A Genetic Algorithm (GA) is a subset of Evolutionary Algorithms that models biological processes, such as genetics and evolution, to optimize highly complex functions. These functions are often difficult to model mathematically, involve NP-hard problems (which are computationally expensive to solve), or include a large number of parameters that make traditional optimization techniques infeasible.

Background of Genetic Algorithm (GA)

• Introduced by Prof. John Holland from the University of Michigan, USA, in 1965.
• The first detailed article on Genetic Algorithms was published in 1975 in his book "Adaptation in Natural and Artificial Systems".
• GA is based on two fundamental biological processes:
  1. Genetics: A concept introduced by Gregor Johann Mendel in 1865, which is the branch of biology that studies genes, genetic variation, and heredity in living organisms.
  2. Evolution: A theory proposed by Charles Darwin in 1859 in his book "On the Origin of Species". Evolution describes how populations of organisms change over generations through processes like natural selection and survival of the fittest.
• Genetics: Focuses on the transmission of genetic material (DNA) and how variations occur in populations through mechanisms like mutation and recombination.
• Evolution: Refers to the gradual process by which organisms develop and diversify from earlier forms through natural selection, genetic drift, and adaptation.

Genetic Algorithm Working Principles

Until now, we have understood that Genetic Algorithms (GA) are inspired by genetics and evolution. Now, we will dive deeper into these concepts to explore more terminologies and understand their relevance to GAs.

• Genetics
  1. Cells: Cells are the basic building blocks of living organisms. Whether it is an animal, a human, or any other living organism, cells form the foundational structure of their bodies.
  2. Chromosomes in Cells: Every cell in an organism contains the same set of chromosomes. For example:
     • Humans: 46 chromosomes
     • Frogs: 36 chromosomes
     • Mosquitoes: 6 chromosomes
  3. Chromosomes: Chromosomes are long strings of DNA (Deoxyribonucleic Acid) that carry genetic information essential for the development and functioning of living organisms.
  4. Genes: Chromosomes are made up of smaller segments called genes, which are the basic units of heredity.
  5. Blocks of DNA: Genes are specific sequences within DNA that encode instructions for particular traits or characteristics.
  6. Encoded Traits: Each gene is responsible for encoding specific traits, such as hair color, eye color, or height.
• Evolution
  1. Heredity: The process by which genetic information is passed from one generation to the next, ensuring that offspring inherit traits from their parents.
  2. Diversity: The variety of genetic combinations within a population, which is essential for adaptation and survival in changing environments.
  3. Selection: The process where individuals with favorable traits are more likely to survive and reproduce, passing on those advantageous traits to the next generation.
  4. Ranking: A method of prioritizing or ordering individuals within a population based on their fitness or adaptability to the environment.

Intuition Behind Genetic Algorithm:

To understand the intuition behind Genetic Algorithms (GA), let us consider a hypothetical scenario. Suppose we want to improve the overall population of a country by ensuring that only the best individuals contribute to future generations. The process might work as follows:

1. Select all the good people in the population based on specific criteria (e.g., honesty, intelligence, or productivity) and allow only them to reproduce, extending their lineage to the next generation.
2. Repeat this process over several generations, where only the individuals meeting the desired criteria are allowed to pass on their traits.
3. Over time, the population evolves, and eventually, we end up with an entire generation of "good" individuals who meet the desired standards.
4. The fundamental idea is to introduce changes in the input (in this case, the population) to achieve an improved output (a better society or country).

Similarly, in a Genetic Algorithm, the "population" refers to a set of candidate solutions, and "good individuals" represent the solutions with higher fitness. By iteratively selecting, reproducing, and improving these solutions, GAs aim to optimize results and achieve the best possible outcome for complex problems.

Now that we have a better understanding of Genetic Algorithms, we can refine our definition as follows:

Genetic Algorithm Definition: A Genetic Algorithm (GA) is an optimization technique that aims to determine the best possible input values to achieve the most optimal output or results for highly complex problems. It does this by simulating natural biological processes such as genetics and evolution.

GAs are particularly effective for problems that:

• Are computationally expensive to solve using traditional methods.
• Involve a large number of parameters or variables.
• Cannot be modeled mathematically with ease (e.g., NP-hard problems).

By mimicking natural selection and reproduction, GAs iteratively improve potential solutions to reach an optimal or near-optimal result.

Selection

• The main purpose of the selection operator is to prioritize better solutions (higher fitness scores) and eliminate weaker solutions, ensuring only the fittest individuals contribute to the next generation.
• The population size remains constant after selection, maintaining a balanced pool of solutions.
• Different methods are used to select the best solutions, such as:
  • Fitness Proportionate Selection (Roulette Wheel Selection)
  • Tournament Selection
  • Rank-Based Selection

Crossover

• Crossover involves combining genetic material from two or more parent solutions (chromosomes) to produce a child solution. This process helps the algorithm create new, potentially better solutions by merging the strengths of the parents.
• Example:
  Parent 1: A B C D E F G H
  Parent 2: E G B C D H A F
  Offspring: A B C D D H A F
  The offspring inherits the first half from Parent 1 and the second half from Parent 2.

Mutation

• The mutation operator promotes genetic diversity among solutions, ensuring that the Genetic Algorithm does not converge prematurely to suboptimal solutions.
• During mutation, a solution may undergo small, random changes, potentially leading to significant improvements in the overall population.
• Example:
  Before Mutation: A B C D E F G
  After Mutation: A B C X E F G
  Here, a single gene (D) has been replaced with a random value (X).

Types of Encoding

1. Binary Encoding:

• Binary encoding is the most common method of encoding, where each chromosome is represented as a binary string (sequence of 0s and 1s).
• Example:
  Chromosome 1: 1 0 1 1 0 1 1 0 0 1
  Chromosome 2: 0 1 1 0 0 0 1 0 1 1
• Each chromosome consists of a binary string where each bit represents a characteristic of the solution. Every string represents a solution, but not necessarily the optimal one.

2. Octal Encoding:

• In octal encoding, chromosomes are represented using octal numbers (base-8).
• Example:
  Chromosome 1: 7 3 1 4
  Chromosome 2: 6 5 2 0
• Each digit in the octal number represents a specific property or parameter of the solution.

3. Hexadecimal Encoding:

• Hexadecimal encoding uses hexadecimal numbers (base-16) to represent chromosomes. This encoding allows for compact representation of larger values.
• Example:
  Chromosome 1: A F 2 9
  Chromosome 2: B 4 D 3
• Each hexadecimal digit can encode values from 0 to 15, making it useful for specific problems requiring high compactness.

4. Permutation Encoding:

• Permutation encoding is used for problems where the solution involves an ordered sequence of items, such as the Traveling Salesman Problem (TSP).
• Example:
  Chromosome 1: [3, 5, 1, 4, 2]
  Chromosome 2: [2, 4, 3, 5, 1]
• Each number in the sequence represents a specific item, task, or city in the solution.

5. Value Encoding:

• In value encoding, chromosomes are represented as sequences of real numbers or other data types suitable for the problem.
• Example:
  Chromosome 1: [12.5, 18.2, 7.8, 15.4]
  Chromosome 2: [10.0, 20.5, 8.1, 14.9]
• This type of encoding is ideal for problems involving continuous variables or real-valued solutions, such as neural network weights or optimization of physical systems.

Fitness Proportionate Selection

• In this method, every individual has a chance of being selected as a parent, with a probability proportional to its fitness.
• Fitter individuals are more likely to be selected, increasing the likelihood of propagating their traits to the next generation.
• Types of fitness proportionate selection:
  1. Roulette Wheel Selection
  2. Stochastic Universal Sampling

Roulette Wheel Selection

• In this technique, the selection probability for each individual is represented as a segment on a circular wheel, where the size of the segment is proportional to the fitness value of the individual.
• Example:
  - Individual A (Fitness: 50) → Segment size: 50%
  - Individual B (Fitness: 30) → Segment size: 30%
  - Individual C (Fitness: 20) → Segment size: 20%
  A random spin of the wheel determines which individual is selected.

Types of Crossover

1: One-Point Crossover

• In one-point crossover, a single crossover point is selected on the parent chromosomes. The segments of the parents' chromosomes before and after the crossover point are swapped to produce offspring.
• Example:
  - Parent 1: A B | C D E F G H
  - Parent 2: X Y | Z W Q R S T
  - Offspring 1: A B | Z W Q R S T
  - Offspring 2: X Y | C D E F G H
  (Crossover occurs at position 2)

2: Two-Point Crossover

• In two-point crossover, two crossover points are selected on the parent chromosomes. The segments between the two points are swapped to create offspring.
• Example:
  - Parent 1: A B C | D E | F G H
  - Parent 2: X Y Z | W Q | R S T
  - Offspring 1: A B C | W Q | F G H
  - Offspring 2: X Y Z | D E | R S T
  (Crossover points are at positions 3 and 5)

3: Uniform Crossover

• In uniform crossover, each gene (bit) from the parents is independently chosen with equal probability to be part of the offspring. This allows for more random combinations of traits.
• Example:
  - Parent 1: A B C D E F G H
  - Parent 2: X Y Z W Q R S T
  - Offspring: A Y C W E R G T
  (Randomly selected genes from each parent form the offspring)

4: Half-Uniform Crossover (HUX)

• In HUX, exactly half of the differing genes between the two parents are swapped to produce offspring. This method focuses on diversity while retaining half of the parental characteristics.
• Example:
  - Parent 1: A B C D E F G H
  - Parent 2: X Y Z W Q R S T
  - Genes differing: All genes
  - Offspring 1: A Y C D Q F S H
  - Offspring 2: X B Z W E R G T

5: Three-Point Crossover

• In three-point crossover, three crossover points are selected, and segments between alternate points are swapped between the parents.
• Example:
  - Parent 1: A B | C D | E F | G H
  - Parent 2: X Y | Z W | Q R | S T
  - Offspring 1: A B | Z W | E F | S T
  - Offspring 2: X Y | C D | Q R | G H
  (Crossover points are at positions 2, 4, and 6)

6: Shuffle Crossover

• In shuffle crossover, the genes in the parent chromosomes are randomly shuffled before crossover, and then the one-point or two-point crossover is applied. Afterward, the offspring genes are unshuffled back to the original order.
• Example:
  - Original Parent 1: A B C D E F G H
  - Original Parent 2: X Y Z W Q R S T
  - Shuffled Parent 1: D C A E B H F G
  - Shuffled Parent 2: W Z Y Q X S R T
  - One-point crossover produces:
    Offspring 1: D C A | Q X S R T
    Offspring 2: W Z Y | E B H F G
  - Unshuffled Offspring 1: A B C Q E F R H
  - Unshuffled Offspring 2: X Y Z D B G S T