SFML

Genetic Algorithm and Simulated Anealing

Details


Programming Language: C++

Environment: Visual Studio 2017 with SFML

Project Type: University.

Technical Features


Genetic Algorithm

Two AI techniques were used for this project, the first being a genetic algorithm, a type of AI that is used to find the optimal solution to problem by evolving a population of solutions till the best or at least a vastly improved solution is left.

Simulated Annealing

Simulated annealing is also an optimization technique that is based of off what happens to metal when it is heated and slowly cooled. This can be achieved in code by using a temperature variable that lowers over time. this technique allows for a lot of good and bad solution initially but as the temperature is lowered more good and less bad solutions remain.

Traveling Salesman Problem

The traveling salesman problem is a very common optimization problem in which a salesman must find the most efficient route around several points. the two optimization techniques were picked for their ability to tackle this problem so their performance and effectiveness could be compared..

About


An application created for my 3rd year Artificial Intelligence module that uses either a Genetic algorithm or Simulated Annealing algorithm to solve the Travailing Salesman problem. This is possibly the most fun piece of course work I’ve worked on as learning about artificial intelligence and then creating an application from what I’ve learnt was incredibly interesting. We were given free reign as to what to research into and create as long as it was artificial intelligence based and genetic algorithms really peaked my interest as I found the way in which they worked fascinating.

The task itself was to create a problem and then choose two different AI techniques and compare how they differ in approaching the problem and how successful they were. After looking into genetic algorithms it seamed that the travelling salesman problem would be a good fit. Simulated annealing was chosen as the second algorithm because while I was creating the genetic algorithm I ran into local minima problems, while I employed several techniques to over come this I wanted to compare the genetic algorithm to an algorithm that didn’t encounter local minima or local maxima problems as much. After reading several papers and articles and papers I came across simulated annealing and found it possibly even more interesting than genetic algorithms. They worked similarly however instead of being based of off biology and genomes like genetic algorithms, simulated annealing is based of off the system for cooling metal in smelting. Both of these algorithms were very interesting and fun to learn about, research and develop and I am quite happy with the result as I got an A for this coursework.