Skip to content
Implementation of a Genetic Algorithm using Clojure. Check the docs:
Clojure
Branch: master
Clone or download
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
docs Fixed mutation and selection functions Nov 13, 2019
ga_output
resources Fixed mutation and selection functions Nov 13, 2019
src/travelling_salesman_problem Fixed mutation and selection functions Nov 13, 2019
test/travelling_salesman_problem Init Oct 28, 2019
.gitignore Init Oct 28, 2019
CHANGELOG.md Fixed version in changelog Nov 13, 2019
LICENSE Init Oct 28, 2019
README.md Fixed mutation and selection functions Nov 13, 2019
project.clj Fixed mutation and selection functions Nov 13, 2019

README.md

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?"

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

Installation

  1. 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:

cities_map

Results

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

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

Evolution

evolution_chart

Solution

solution

License

Copyright © 2019

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.

You can’t perform that action at this time.