Please enable JavaScript.
Coggle requires JavaScript to display documents.
TSP - Coggle Diagram
TSP
Initialization Parameters
How many chromosomes will there be in a population?
An initial population with randomly determined DNA are created. "Create a population of N elements, each with randomly generated DNA."
The initial population must be large enough that there is enough diversity, It also should not be too large as it will increase computational time
Fitness
Each chromosome is given a fitness value based on how well they solve the problem at hand. The higher the fitness value the more likely the chromosome is to be selected into the mating pool
Fitness values are given to chromosomes for enabling selection methods to function and choose chromosomes on how well they solve the problem.
Fitness landscape
Fitness function
A fitness function is a function that evaluates each chromosome and gives it a fitness value based on how well it solves the problem.
Diversity of the chromosomes
Methods to ensure diversity
Novelty Search
Novelty search is a search algorithm that aims to explore the current population and select the chromosomes that are the most different from the current population.
It is a method to ensure genetic diversity and to make sure chromosomes with novel properties are always kept in the gene pool as their properties may prove to be useful after multiple processes of crossover. It is because of this that novelty search prevents our result from converging at a local maxima.
Crossover
Mutation Rate
Exploration
Possible problems
Too much diversity
Advantages/Disadvantages compared to Alternative Approaches
Brute Force Approach
Disadvantages
Time complexity increases immensely as problem gets more complex
Takes too long to reach the best solution
Advantages
Always eventually reaches the best solution
Neural Networks
Advantages
Neural networks perform better on continuous data sets when compared to genetic algorithms
Disadvantages
In the TSP, the data examined is discrete, which makes genetic algorithms a more appropriate way of finding a solution
Challenges Faced
Exploitation
Fitness Scale
Hill Climbing
Elitism
Elitism is the process of ensuring that the best chromosomes in a population are selected for the mating pool. This means that they are not open for mutation. A small selection % would mean less variety and would lead into our answers converging, so a relatively sizeable % of the population must be selected with the elitist method.
Choosing a Selection Method
tournament selection
stochastic universal sampling
roulette wheel selection
truncation selection
Exploitation is the process of refining the current solutions in the current population. The theory is that by only selecting the best chromosomes in a population to the mating pool, the off springs produced by those chromosomes will be even better solutions to the problem.
Exploitation can be done through selection methods that aim to select the best chromosomes in the current population, these can be Elitism, tournament selection, truncation selection etc.
Simulated Annealing
Simulating annealing is a process of finding the global optimum
in a given population.
It works by randomly selecting a point on the fitness landscape and setting it as the base point. It uses a concept called "temperature" and the the value of temperature begins at Tmax and slowly decreases to the value of Tmin. Exploration is made at high Temperature values and through this process of exploring random points and selecting points that improve the solution the algorithm is expected to converge at a global maximum
Evaluating Heuristics
Allow options that make the search for a good solution more efficient.
One big limitation is that the solution that is found for the problem may not be the best.
They sacrifice accuracy for time and money
Ensuring Crossover
Crossover methods:
Single Point Crossover
how they preserve the parental traits
Crossover is the process of crossing over the properties of the chromosomes in a population to create new chrosomes.
Failure in Simple Crossover
City visits may be repeated as a result of standard crossover methods (e.g. one point or two point)
Solving the Problem
Alternative methods, such as partially mapped crossover, may be used
Convergence
Premature Convergence
Diversity
Convergence limits diversity as more and more solutions become alike as time passes
Exploration
Exploration is the process of exploring the problem space and the solutions within it, it can be done through the use of crossover operators, mutation and search methods that search for genetically novel chromosomes in a population and select them into the mating pool(Like novelty search).
Through the use of exploitation methods such as elitism genetic diversity will be lost and exploration methods are needed to restore genetic diversity otherwise our solutions maybe converge at a local maxima. Too much exploration could result in our population being too diverse to a point that no valuable result will be obtained through exploitation.
It is done to ensure that there is genetic diversity between the chromosomes in each population, maintaining genetic diversity is a vital factor in finding an optimal solution as it will make it less likely that our population will converge at a local maxima.