Travelling salesman problem genetic algorithm python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Travelling Salesmman Problem — Genetic Algorithm

lewis-morris/python-tsp-ga

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

readme.MD

A version of the «Travelling Salesman Problem» calculated with a genetic algorithm.

• Genetic algorithms mimic the reproductive traits of living organisms which, pass down genetic traits from two parents to their offspring.

My implementation uses a concept I’m coining «families». Workers are grouped into these families are interbred every generation and then random bred between families every n generations.

First navigate to a directory where you want to download it to.

git clone https://github.com/lewis-morris/python-tsp cd python-tsp pip install -r requirements.txt 

optional arguments: -h, --help show this help message and exit -c CITIES, --cities CITIES This is the amount of 'cities' to add to the map or the hardness of the calculation -w WORKERS, --workers WORKERS The amount of workers per family generation -f FAMILIES, --families FAMILIES The amount of families per generation -b BREED, --breed BREED Generation number to breed between families on . i.e every n times -r RANDOM, --random RANDOM Draw the cities randomly on the map or equally spaced. 0= equally (draws a perfect polygon of n sides, which is easy to determine when complete) 1= randomly (points are randomly selected in the 'map' space) -d DRAW, --draw DRAW Draw the output onscreen. 0= no 1= yes 

python tsp.py -c 50 -w 100 -f 10 -b 30 -r 1 -d 1 

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

A Python script that solves the traveling salesman problem using genetic algorithms. The cities and the distances are predetermined but can also be randomly generated.

License

PetePrattis/traveling-salesman-problem-with-genetic-algorithms

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

A Python and Artificial Intelligence Program / Project

This is a Python project from my early days as a Computer Science student

This programm was created for the sixth semester class Artificial Intelligence and is the final project for the class

Description of project

A Python script that solves the traveling salesman problem using genetic algorithms. The cities and the distances are predetermined but can also be randomly generated.

Impementation of project

1. I create a random sized initial population, with random routes (the first city is the last one)
2. The user selects how many generations to run and the genetic algorithm begins
3. At the end of each generation the population is twice the size by adding routes using crossover, mutations and random routes
4. Survival of the fittest means that at the end of the generation, only half best will continue to exist at next generation
5. At each generation random routes are created in order for the algorithm not to stuck in local minimum solution
6. At each generation routes through crossover genetic function are generated:

Mutation is also a simple process where a parent gives birth to a child. In my algorithm I have implemented two modes of mutation where they are randomly selected. The first way is to select a small part of the parent and shuffle the cities of that part to create a new route. The second way is to select a small part of the parent and move it to another part of the parent so that a new route is created.

About this project

• The comments to make the code understandable, are within the .py archive
• This project was written in IDLE, Python’s Integrated Development and Learning Environment.
• This program runs for Python version 2.7
• This repository was created to show the variety of the work I did and experience I gained as a student

About

A Python script that solves the traveling salesman problem using genetic algorithms. The cities and the distances are predetermined but can also be randomly generated.

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

A non object-oriented python approach for the TSP

ZisisFl/Travelling-Salesmans-Problem-Genetic-Algorithm-Python

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Travelling Salesmans Problem Genetic Algorithm Python

Our problem isn’t demanding in processing power because we have only 5 cities and it is really easy to calculate the length of all the possibly routes and then pick the best. So this is a toy example but the algorithm can be generalized by changing the variables(population_size and n_generartions) and the distance matrix. The number of diffrent paths is equal to the factorial of the number of the cities, in this case 5! = 120. It is pretty clear that as the number of cities increases the problem becomes more and more difficult and this is the reason that we choose a genetic algorithm to solve it.

This algorithm is based on the image below.

From this image results the distance matrix, but any distance matrix given to the algorithm can give us back a result.

The mutation method is swap mutation with probability 10% for every path in the population. Crossover method is PMX and it is considered as one of the best for this problem. Parents for the crossover are choosed with Fitness Proportionate Selection. We have selected Roulette Wheel Selection which is a way to give higher chance for best routes to be choosen as parents based on their fitness (1/route_length).

Источник