TSP
Diversity of the chromosomes
Challenges Faced
Advantages/Disadvantages compared to Alternative Approaches
click to edit
Exploitation
Evaluating Heuristics
Ensuring Crossover
Convergence
Fitness Scale
Crossover methods:
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
Premature Convergence
Diversity
Hill Climbing
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.
Elitism
Choosing a Selection Method
Failure in Simple Crossover
City visits may be repeated as a result of standard crossover methods (e.g. one point or two point)
Brute Force Approach
Neural Networks
Methods to ensure diversity
Novelty Search
Crossover
Mutation Rate
Exploration
Possible problems
click to edit
Too much diversity
Initialization Parameters
tournament selection
stochastic universal sampling
roulette wheel selection
truncation selection
Fitness
Advantages
Disadvantages
Disadvantages
Advantages
Time complexity increases immensely as problem gets more complex
Takes too long to reach the best solution
Always eventually reaches the best solution
click to edit
Solving the Problem
Neural networks perform better on continuous data sets when compared to genetic algorithms
Convergence limits diversity as more and more solutions become alike as time passes
In the TSP, the data examined is discrete, which makes genetic algorithms a more appropriate way of finding a solution
Alternative methods, such as partially mapped crossover, may be used
click to edit
Single Point Crossover
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.
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.
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.
click to edit
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.
click to edit
Fitness landscape
Fitness function
click to edit
A fitness function is a function that evaluates each chromosome and gives it a fitness value based on how well it solves the problem.
click to edit
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
How many chromosomes will there be in a population?
click to edit
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
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.