Quick Options

NSFW Content:
Listing Mode:
Coloring Style:
Animations:

◀ Quick Options    Login    Register
X Greetings! You are not currently logged in, but please don't let that stop you from voting up any videos you like. :)

3D,computer science,fundamental problem,graph theory Genetic Algorithm solves Traveling Salesman problem

Genetic Algorithm solves Traveling Salesman problem

posted by oxdottir 1 year 9 months 1 week ago • 1371 views
tags: 
embed
email

The Travelling Salesman problem is stated as: "Given a number of cities and the costs of travelling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once?"

Ryan Bateman used the open source classes listed at heatonresearch.com to create a Processing program that would solve the 3D Travelling saleman problem using Genetic algorithms. Re-used paths (corresponding to Chromosomes) increase in visibility as they're re-used, fading otherwise,
meaning the paths 'emerge' as certain chromosomes become more dominant.

The problem is considered 'solved' when a hundred generations have passed without a more optimal solution having been found. This is really a philosophical position because this definiton of "solved" is not conventional, and if it really is "solved," this solution can be used to do all sorts of exciting things like break cryptographic algorithms, and such.

For more on genetic algorithms used to produce art (including a fair amount of math), see http://www.videosift.com/video/Google-talks-Scott-Draves-on-technical-details-for-art.

GREAT DESIGNS FROM VIDEOSIFT'S T-SHIRT STORE
Support VideoSift - Buy a Shirt! Use coupon code SIFTFALL09 at checkout to save an additional 20% now!
Power Turns Me On T-Shirt
Power Turns Me On
Happy Rabbit With Teddy T-Shirt
Happy Rabbit With Teddy
Factorials T-Shirt
Factorials

Comments subscribe to this feed
Upvote purely because this is very close to how routers perform route fowarding decisions. Ie. This is how the internet would work if you could see routers calculating least cost paths to each destination in their route table.


written by charliem  | 1 year 9 months 1 week ago | CH
 1  | flag spam (0)
Connect the dots. la lala lala
Connect the dots. la lala lala


written by Doc_M  | 1 year 9 months 1 week ago | CH
 0  | flag spam (0)
NO, NO, NO! GOD DID IT!


written by Smugglarn  | 1 year 9 months 1 week ago | CH
 -1  | flag spam (0)
That's pretty slick for an NP-hard problem.


written by HaricotVert  | 1 year 9 months 1 week ago | CH
 1  | flag spam (0)
Submit Comment

Connect with Facebook
          - OR -
log in or register to submit new comment


playlists with this video
So cool! by gwiz665  • So interesting by gwiz665

who voted for this video
oxdottir  - Fjnbk  - siftbot x21 - gwiz665  - Lann

who has this post bookmarked
gwiz665  - jonny  - Fjnbk

Genetic Algorithm Solves Traveling Salesman Problem Related Videos

Ivy League Computer Science parody of Minority Report

Obama Knows His Computer Science

Evolution of a Virtual creature: 1070 generations

Watch this Video Next

Friends O' the Sift
Top 15 Sifters of All Time
1. Zifnab  (55060 votes)
2. arvana  (45622 votes)
3. dystopianfuturetoday  (43986 votes)
4. kronosposeidon  (40961 votes)
5. NetRunner  (39965 votes)
6. blankfist  (37415 votes)
7. ant  (35464 votes)
8. mintbbb  (31854 votes)
9. Farhad2000  (31827 votes)
10. eric3579  (30588 votes)
11. rasch187  (30550 votes)
12. Issykitty  (27319 votes)
13. mlx  (21763 votes)
14. deputydog  (21130 votes)
15. Fedquip  (20926 votes)
Top 15 Sifters of the Past Week
1. EndAll  (363 votes)
2. brycewi19  (352 votes)
3. MikesHL13  (345 votes)
4. demon_ix  (318 votes)
5. kronosposeidon  (257 votes)
6. arvana  (257 votes)
7. Sagemind  (241 votes)
8. dystopianfuturetoday  (240 votes)
9. lovelynotes  (213 votes)
10. marinara  (213 votes)
11. reiwan  (204 votes)
12. ant  (172 votes)
13. dan00108  (171 votes)
14. BoneyD  (162 votes)
15. Hybrid  (158 votes)