Genetic Algorithms

Solving Traveling Salesman Problem using Genetic Algorithms to show how it actually works. Below are some descriptions of different types of mutations and crossovers. Also I performed a few experiments applying different crossovers, mutations and variety of parameters while solving the TSP.

Crossover Examples

Crossover is one of the most important things in Genetic Algorithms. This part of GA itself could be considered as an "evolution performer". There are several examples of crossovers with a portion of pseudocode and the pictures illustrating the process.

Multi-Point Crossover

Brief Description

One of the common crossover types is Multi-Point Crossover or N-Point Crossover. Firstly we randomly separate parents into N+1 parts with N separators. Then carry genes from the first parent's odd parts, and from even parts of the second one.

Pseudocode

SET old_separator TO 0
SET offspring TO empty sequence

FOR from 0 to the separators_count-1:
    SET new_separator TO random number from old_separator+1 to parents_length-separators_count+current_separator_number
    
    IF current_separator_number is odd:
        CONCATENATE offspring WITH slice of the second parent from old_separator to new_separator-1
    ELSE:
        CONCATENATE offspring WITH slice of the first parent from old_separator to new_separator-1
    
    SET old_separator TO new_separator
 
IF separators_count is odd:
    CONCATENATE offspring WITH slice of the second parent from old_separator
ELSE:
    CONCATENATE offspring WITH slice of the first parent from old_separator

Single-Point Crossover

Brief Description

Single-Point Crossover is just a special case of the previous crossover.

Pseudocode

Uses the function of Multi-Point Crossover

Uniform Crossover

Brief Description

Carrying genes by literally tossing a coin. There is also a special case of Uniform Crossover named "Parameterized Uniform Crossover" with chances for every gene to be chosen.

Pseudocode

SET mask TO random sequence of numbers from 0 to 1 with length equals the parents length
SET offspring TO empty sequence

FOR each element of the mask:
    IF mask_element is 1:
        APPEND element of the second parent with a mask_element's index TO offspring
    ELSE:
        APPEND element of the second parent with a mask_element's index TO offspring

Cycle Crossover

Brief Description

This kind of crossover makes possible to work with chromosomes consisting of ordered genes (that mustn't be repeated). Good for solving problems with graphs such as Traveling Salesman Problem, Graph Coloring Problem, Vehicle Routing Problem, etc. The working principle is illustrated below.

Pseudocode

SET used_genes TO empty sequence
SET cycles TO empty sequence
SET offspring TO empty sequence

FOR each element of the parent one:
    IF parent's element is not in the used_genes:
        SET cycle TO sequence of two elements: parent_one_element with current index, parent_two_element with current index
        
        WHILE first cycle's element is not equal to the last cycle's element:
            APPEND element of the second parent with an index of the last cycle's element in the first parent TO cycle
            
        SET cycle TO cycle without the last element
        APPEND cycle TO cycles
        CONCATENATE used_genes WITH cycle
        
FOR each element of the both parents:
    IF an element of the parent one is in an odd cycle:
        APPEND second parent's element TO offspring
    ELSE IF an element of the parent one is in an even cycle:
        APPEND first parent's element TO offspring

Partially Mapped Crossover

Brief Description

Has the same purpose as the previous one, even though works different. Firstly we are taking a random slice from the parents. Then carrying this part from the first parent to the offspring. After, from the parent two, all genes that are not in the both slices have to go to the offspring, too. And the most complicated part is to find indexes for the remaining genes that are ONLY in the SECOND parent's slice. The process is demonstrated on the picture below.

Pseudocode

SET subset TO randomly chosen slice of the parents
SET offspring TO sequence (the length equals parents length) with carried subset from the first parent; remaining elements are all equal to 0's

FOR each element of the parent two:
    SET new_index TO current_index
    
    IF the second parent's element is not in the offspring:
        IF the second parent's element is in the subset:
            WHILE new_index is in the subset:
                SET new_index TO index of the element in the second parent that is equal to the same element in the first parent at new_index
                
    SET offspring's element at new_index TO current element of the parent two

Mutation Examples

Unlike crossovers, mutations are "avoidable". In other words, theoretically a genetic algorithm can still work without them. But the results are going to be far worse. As without an entropy (that every single mutation brings) the algorithm will stuck in a local optima. Mutations usually have a low chance to be used on an offspring to keep some stability. Below are pictures illustrating the mutations I used while implementing the TSP solver (since it's pretty easy without pseudocode).

Replacement Mutation

Inversion Mutation

Additional Info

What My Implementation Can Solve

The algorithm I created (genetic_algorithm.py, mutation.py and crossover.py are universal) can only solve minimization problems with ordered genes (TSP, GCP, VRP, etc).

Parents Selection

There are different ways to select parents such as: Roulette Wheel Selection, Stochastic Universal Sampling, Tournament Selection, etc. In my implementation I use the first one - Roulette Wheel Selection. According to the name, it functions like a roulette wheel where a probability for every chromosome has following formula:

Where N is a total population size, and is a fitting score of a chromosome from the whole population. And since we have a minimization problem, it's important to raise the fitting score to -1.

How to use

TSP module

The TSP module's main class is NodesGenerator. It provides a few tools for working with the problem:

• __init__
  Has one required argument count and one optional saved_axis. The first one is just a nodes count (makes sense only if saved_axis is False or is not provided). And the second one is a boolean value that defines whether you already generated nodes or not. If False, it generates new nodes according to the count and saves their distances and axis to the data folder for subsequent use. If True, it uses already mentioned files.
• get_nodes_list
  Just returns a list consisting of the Node objects (a Node object simply has handy methods such as finding a distance between two nodes, and so on). String representation of each node is just a number of a node.
• total_cost
  Requires a list of the Node objects as an argument. Returns total cost of the way.
• draw_path
  Requires a list of the Node objects as an argument. Draws a graph with connected nodes in accordance with a nodes order.

GA module

• CrossoverType
  Contains different types of a crossover:
  • MULTI_POINT
  • SINGLE_POINT
  • UNIFORM
  • CYCLE
  • PMX
• MutationType
  Contains different types of a mutation:
  • REPLACEMENT
  • INVERSION
• Crossover
  
  • __init__
    Requires one argument - crossover_type.
  • preform
    Has two required arguments: parent1 (list), parent2 (list), and one optional - points (should be provided only while performing a MULTI_POINT crossover). Returns an offspring from both parents.
  • set_type
    Exists as a setter for a new type, requires one argument new_type.
• Mutation
  
  • __init__
    Requires two arguments: chance (a chance of the mutation, from 0 to 1) and mutation_type.
  • preform
    Has one required argument offspring (list). Returns mutated (with some chance) offspring.
  • set_type
    Exists as a setter for a new type, requires one argument new_type.
• GeneticAlgorithm
  
  • __init__
    Requires four arguments: mutation_chance, crossover_type, mutation_type, and fitness_function (a function that returns a score of a single chromosome, in our case it is total_score from NodesGenerator)
  • init_population
    Requires two arguments: k (a size of the population) and initial_chromosome (some chromosome that will be shuffled to create different population members). Don't need to be called if you want to continue a life of the population.
  • start
    Requires two arguments: k (time of the population's living / an amount of evolutional steps) and selector (how many chromosomes will die and be replaces by offsprings during the selection process). Starts an evolution, prints a process of the evolution, fills a history. Returns a chromosome with the best result.
  • history
    A @property method that returns a history of the evolving (gotten after the start was successfully executed).

Experiments

Experiment 1

GAs with two different mutation chances (one has 100%, another has only 10%).

Replacement

• Initial parameters
  

• An outcome
  

• Conclusion
  The plot with 100% chance is extremely spiky, unlike the one with a mutation chance of 8% which is pretty stable. The best result from the first algorithm is 155, and from the second one is 136. I think it is obvious which GA evaluates better. Additionaly you can see some kind of "stairs" on the second plot. And, on other hand, the plot with 100% chance is like a slide.

Inversion

• Initial parameters
  

• An outcome
  

• Conclusion
  An outcome gotten by using Inversion is way more smooth comparing to the replacement method. In other words Replacement brings more chaos to our data. The conclusion is similar as the previos one has.

Experiment 2

GA with a 0% mutation chance.

• Initial parameters
  

• An outcome
  

• Conclusion
  As you can see the blue line is descending as fast as the orange one, but suddenly starts going straight. It means that we gotten stuck in a local optima due to the lack of entropy in the population. The answer won't change anymore, respectively it won't become better.

Experiment 3

Comparing Partially Mapped Crossover and Cycle Crossover.

• Initial parameters
  

• An outcome
  

• Conclusion
  Firstly I've noticed the amount of spikes the orange graph has. Cycle Crossover is not as stable as PMX, and also produces worse results. I'm not sure whether it is a problem of my implementation or this crossover just isn't good at solving TSP. Although the answers are still good enough, PMX is more suitable for the Traveling Salesman Problem.

Experiment 4

Extremely small population vs huge population.

• Initial parameters
  

• An outcome
  

• Conclusion
  As you can see the large population is obviously better... I would say so, but not really. I was waiting for about a minute to get a result. And, on other hand, an answer from the small population I got in a few seconds.