Travelling Salesman Problem Using Genetic Algorithms
Problem Definition
-The traveling salesman problem consists of a salesman and a
set of cities.
-The salesman has to visit each one of the cities
starting from a certain one (e.g. the hometown) and returning
to the same city.
-The challenge of the problem is that the
traveling salesman wants to minimize the total length of the
trip
Method Used
• We have a set of cities (points) in 2d plane.
Each city has
road to each city.
We need to find loop-path that will be in
each city only one time and path length is minimal.
• The genetic algorithm is sequence of following operations
that repeated in generations loop:
1) Generate random population and finding path length.
2) find probabilities for selection. f(x)= 1/d
3) prepare to crossover according probabilities. pi=1/di / Ī£ 1/di
4) crossover, parents replaced with children.
5) mutations.(Swap,Flip,Random)
Similarly
Internet Search Technique
- Searching using Links
- Application Starts from Set of Documents
- Indexing Web Bages
- Storing Information into DB
No comments:
Post a Comment