Travelling Salesman Problem

Implementation of a Genetic Algorithm using Clojure. See the literate programming page: Docs

"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?"

Wikipedia

This implementations uses a genetic algorithm to find the shortest route between cities.

Installation

Clone this repo:

git clone https://github.com/vascoferreira25/travelling-salesman-problem

Run the program

First make the project folder your working directory:

cd travelling-salesman-problem

And then, either run it directly with:

lein run

or use the REPL and execute the main function:

lein repl

uncomment the last line

(-main)

and execute the function.

Docs and Literate Programming

This project has a literate programming page that walks the entire code to explain everything that is done at each step.

Check it at: Docs

Purpose

Find the best possible route for a list of cities. The cities are represented in the following chart:

Results

With the following parameters, the algorithm reached the result of 565.685424949238:

Generations: 200,
Population Size: 500,
Mutation Rate: 0.02.

Evolution

Solution

License

This program and the accompanying materials are made available under the terms of the Eclipse Public License 2.0 which is available at http://www.eclipse.org/legal/epl-2.0.

This Source Code may also be made available under the following Secondary Licenses when the conditions for such availability set forth in the Eclipse Public License, v. 2.0 are satisfied: GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version, with the GNU Classpath Exception which is available at https://www.gnu.org/software/classpath/license.html.