November 25, 2012 at 21:48Search for a Hamiltonian cycle in a large graph (traveling salesman problem). Part 2
In continuation to my first article, I decided to write this one, in which I will talk about more advanced algorithms for finding the Hamiltonian cycle in a large, full column. I
recommend that those who have not read the first article read it because it is a continuation, and by no means an independent article.
The idea of this algorithm first occurred to Marco Dorigo, who proposed this algorithm in 1992.
The algorithm is referred to as metaheuristic optimizations.
Watched ants in childhood? Well, at least once? Ants usually go for food. Long away. But how do they tell each other where to go for food? After all, it is not profitable to search again every time if somewhere somewhere yesterday some ant found, for example, an apple. Here is the ant that found the apple that marks the way with pheromones on the way home. So, a little bit, he's just one. The next day, n ants will go there, everyone will find food, and mark the path. There are more pheromones on the track, and the likelihood that the next ants will follow it is increasing, but the pheromones evaporate, and after a few days there will be no trace left on the track. And the longer the track, the faster it will collapse. Based on this fact, this algorithm is built from ant life.
An example of the fact that more ants will run along the shortest path per unit of time, and in the end, all the other pheromones will evaporate, but on this one, it will become the path for the entire colony.
How to apply this to the traveling salesman problem?
We take the branch and bound method, which I described in the first article, and make the following changes:
1) If we in the selection tree to take / not to take an edge go along one of the paths, “put” on the path from the root to this vertex a certain number of pheromones.
2) On each edge, pheromones of all paths through this edge add up.
3) At each iteration of the algorithm, the number of pheromones on each path decreases by a certain percentage.
4) When choosing the next peak, we are guided not only by its cost estimate, but also by the number of pheromones on the way to it.
The algorithm is considered one of the most effective polynomial algorithms for the posic of the Hamiltonian cycle on large graphs.
Having the written method of branches and borders, it is quite simple to fasten the simplest version of the ant colony to it, the difficulty is only in the correct selection of constants for the evaporation rate, how many pheromones to put if we passed, etc.
The greedy’s gain is ~ 17%, the work time is about an hour.
The main source of ideas for this algorithm is biological evolution.
The main emphasis in this algorithm is placed on the so-called crossover operator, which produces recombination of candidate solutions.
1) The main requirement is that we store the solution as a vector of something (bits, numbers, symbols).
In our problem, we will store in the i-th cell the number of the vertex to which we are going from this i-th cell.
2) New solutions from which we will choose from solutions for crossbreeding will be obtained as a result of mutations of old solutions and crossbreeding.
3) A mutation is defined as a function that randomly changes some genes (array cells in our case), and the result is embedded in many solutions.
4) Crossbreeding is defined as a combination (random) of the genes of several of the best solutions from the previous iteration.
5) At each stage, we must throw out unsuitable solutions — those that are not trivial Hamiltonian cycles. (For example, they contain two cycles of size 250)
6) Solutions for mutations are chosen randomly with some probability.
7) Cross-breeding solutions are again chosen randomly, but the best solutions obtained for this iteration (for which the cycle weight is less) should be more likely.
If you feel sorry for the memory at each stage, you can throw out the worst of the adapted solutions.
The easiest way to run such an algorithm is to first provide it with some many correct solutions, for example, given to us by a greedy woman running from different vertices.
Stop state - some parameters of the algorithm that say it is time to finish counting and you need to display the answer (the best solution at the moment)
In my case, the stop parameter was time limit.
The simplest implementation worked in 2 hours and won only ~ 4% of the greedy one.
It is worth noting that this is due largely to the simplest implementation, many sources claim that the genetic algorithm is one of the best, if not the best.
There are a lot of problems with this, as half of the sources say that the record holder is ACO at the moment, half - that genetics.
ps the continuation was written largely thanks to the comments on the first article, which encouraged me to try to write at least the simplest implementations of these algorithms, for which thanks mephistopheies andDiversus
recommend that those who have not read the first article read it because it is a continuation, and by no means an independent article.
1.Ant algorithm, aka Ant Colony Optimization (ACO)
The idea of this algorithm first occurred to Marco Dorigo, who proposed this algorithm in 1992.
The algorithm is referred to as metaheuristic optimizations.
Idea of the algorithm
Watched ants in childhood? Well, at least once? Ants usually go for food. Long away. But how do they tell each other where to go for food? After all, it is not profitable to search again every time if somewhere somewhere yesterday some ant found, for example, an apple. Here is the ant that found the apple that marks the way with pheromones on the way home. So, a little bit, he's just one. The next day, n ants will go there, everyone will find food, and mark the path. There are more pheromones on the track, and the likelihood that the next ants will follow it is increasing, but the pheromones evaporate, and after a few days there will be no trace left on the track. And the longer the track, the faster it will collapse. Based on this fact, this algorithm is built from ant life.
An example of the fact that more ants will run along the shortest path per unit of time, and in the end, all the other pheromones will evaporate, but on this one, it will become the path for the entire colony.
How to apply this to the traveling salesman problem?
We take the branch and bound method, which I described in the first article, and make the following changes:
1) If we in the selection tree to take / not to take an edge go along one of the paths, “put” on the path from the root to this vertex a certain number of pheromones.
2) On each edge, pheromones of all paths through this edge add up.
3) At each iteration of the algorithm, the number of pheromones on each path decreases by a certain percentage.
4) When choosing the next peak, we are guided not only by its cost estimate, but also by the number of pheromones on the way to it.
The algorithm is considered one of the most effective polynomial algorithms for the posic of the Hamiltonian cycle on large graphs.
Having the written method of branches and borders, it is quite simple to fasten the simplest version of the ant colony to it, the difficulty is only in the correct selection of constants for the evaporation rate, how many pheromones to put if we passed, etc.
The greedy’s gain is ~ 17%, the work time is about an hour.
Genetic algorithm
Idea of the algorithm
The main source of ideas for this algorithm is biological evolution.
The main emphasis in this algorithm is placed on the so-called crossover operator, which produces recombination of candidate solutions.
1) The main requirement is that we store the solution as a vector of something (bits, numbers, symbols).
In our problem, we will store in the i-th cell the number of the vertex to which we are going from this i-th cell.
2) New solutions from which we will choose from solutions for crossbreeding will be obtained as a result of mutations of old solutions and crossbreeding.
3) A mutation is defined as a function that randomly changes some genes (array cells in our case), and the result is embedded in many solutions.
4) Crossbreeding is defined as a combination (random) of the genes of several of the best solutions from the previous iteration.
5) At each stage, we must throw out unsuitable solutions — those that are not trivial Hamiltonian cycles. (For example, they contain two cycles of size 250)
6) Solutions for mutations are chosen randomly with some probability.
7) Cross-breeding solutions are again chosen randomly, but the best solutions obtained for this iteration (for which the cycle weight is less) should be more likely.
If you feel sorry for the memory at each stage, you can throw out the worst of the adapted solutions.
The easiest way to run such an algorithm is to first provide it with some many correct solutions, for example, given to us by a greedy woman running from different vertices.
Stop state - some parameters of the algorithm that say it is time to finish counting and you need to display the answer (the best solution at the moment)
In my case, the stop parameter was time limit.
The simplest implementation worked in 2 hours and won only ~ 4% of the greedy one.
It is worth noting that this is due largely to the simplest implementation, many sources claim that the genetic algorithm is one of the best, if not the best.
There are a lot of problems with this, as half of the sources say that the record holder is ACO at the moment, half - that genetics.
ps the continuation was written largely thanks to the comments on the first article, which encouraged me to try to write at least the simplest implementations of these algorithms, for which thanks mephistopheies andDiversus