Mesmerizing visualizations of genetic algorithms
March 24, 2013 5:04 PM Subscribe
Genetic algorithms are useful for solving all kinds of problems and their implementations can be quite mesmerizing to watch. Re-producing Mona Lisa, a human face or bull cave painting. Playing Super Mario, Tetris and more Tetris. Simulating a soccer team, fishes, ant colony or Santa's flight path. A documentary about using genetic algorithms in design, e.g. deciding the optimal antenna placement on a Humvee, creating search and destroy behavior for UAVs and designing more efficient wind turbine blades. Should probably learn how to stand and jump and stand again before driving.
Long long time ago I worked for BBN, the company that created the hardware of the Arpanet. The C-30 packet switch was the foundation of the system. Switches talked to each other through 56K modem links (I said it was a long time ago) and routing from one user to another could take several hops.
When a new customer wanted to create a network (say, an airline wanted to create a network to support computerized booking for travel agents) BBN would design one. The obvious question was, where should the nodes be placed and how should they be interconnected. That was solved using a genetic algorithm. There was a room full of Sun 3/50 (I said this was a long time ago) workstations all running the algorithm. A human would take their best shot at manually designing a solution, and that was the starting point for the algorithm, which usually was allowed to run for several days.
The guys who worked on that told me that there were two things that were invariably true about the result: first, it was always far better than anything a human could design. And second, it was always bizarre, a pattern no human could have conceived of. Both, of course, were because the genetic algorithm didn't have human preconceptions.
posted by Chocolate Pickle at 5:51 PM on March 24, 2013 [7 favorites]
When a new customer wanted to create a network (say, an airline wanted to create a network to support computerized booking for travel agents) BBN would design one. The obvious question was, where should the nodes be placed and how should they be interconnected. That was solved using a genetic algorithm. There was a room full of Sun 3/50 (I said this was a long time ago) workstations all running the algorithm. A human would take their best shot at manually designing a solution, and that was the starting point for the algorithm, which usually was allowed to run for several days.
The guys who worked on that told me that there were two things that were invariably true about the result: first, it was always far better than anything a human could design. And second, it was always bizarre, a pattern no human could have conceived of. Both, of course, were because the genetic algorithm didn't have human preconceptions.
posted by Chocolate Pickle at 5:51 PM on March 24, 2013 [7 favorites]
Looks like BBN is still at it, Chocolate Pickle. Can you remember the name of the GA system that ran on all those Suns (16 MHz 68020s - I had to look it up, in both senses)?
posted by Devonian at 6:36 PM on March 24, 2013
posted by Devonian at 6:36 PM on March 24, 2013
I used to have a video I saw at Genetic Programming 1997 of using GP to reproduce the iconic movement of the Luxo lamp from Pixar. This was work done by Gritz and Hahn.
The video showed the best individual of generation 0 where Luxo shivered spasmodically and happened to go slightly forward). The median of gen 0 stayed in place and the worst fell backwards. By Gen 10, there was a somewhat coordinated, but still spasmodic hop forward from the best individual. By gen 50, Luxo collected itself and hopped forward in a coordinated fashion.
After that Larry set Luxo the task of doing the limbo. Luxo learned how to "lie back" on its springs to go under the bar until Larry lowered the bar too low for that to work. Luxo then learned to go up the the bar, reach forward with its hood and pull himself under the bar. This was the best example of evolutionary algorithms I've ever seen.
Unfortunately I lost the video when a bunch of old videos were thrown out.
posted by BillW at 7:00 PM on March 24, 2013 [1 favorite]
The video showed the best individual of generation 0 where Luxo shivered spasmodically and happened to go slightly forward). The median of gen 0 stayed in place and the worst fell backwards. By Gen 10, there was a somewhat coordinated, but still spasmodic hop forward from the best individual. By gen 50, Luxo collected itself and hopped forward in a coordinated fashion.
After that Larry set Luxo the task of doing the limbo. Luxo learned how to "lie back" on its springs to go under the bar until Larry lowered the bar too low for that to work. Luxo then learned to go up the the bar, reach forward with its hood and pull himself under the bar. This was the best example of evolutionary algorithms I've ever seen.
Unfortunately I lost the video when a bunch of old videos were thrown out.
posted by BillW at 7:00 PM on March 24, 2013 [1 favorite]
They were actually 50 MHz 68030's.
I'm not surprised that BBN is still in that business, but anything they might be doing now is surely unrelated to what I worked on. (Man, the C-30 was a piece of junk. Amazing that it worked at all. All the code was written in absolute assembler; no linker, no relocation. There was a secretary who was responsible for maintaining the memory map, and if you needed memory for code you had to go to her to get it assigned.)
I could tell you more stories but it would be a major derail. Maybe some other time. I think that was close to being the worst job I ever had; I was miserable there.
As to the GA software, it was homebrew.
posted by Chocolate Pickle at 7:55 PM on March 24, 2013 [1 favorite]
I'm not surprised that BBN is still in that business, but anything they might be doing now is surely unrelated to what I worked on. (Man, the C-30 was a piece of junk. Amazing that it worked at all. All the code was written in absolute assembler; no linker, no relocation. There was a secretary who was responsible for maintaining the memory map, and if you needed memory for code you had to go to her to get it assigned.)
I could tell you more stories but it would be a major derail. Maybe some other time. I think that was close to being the worst job I ever had; I was miserable there.
As to the GA software, it was homebrew.
posted by Chocolate Pickle at 7:55 PM on March 24, 2013 [1 favorite]
Ah, yes, anything I can think to ask would be a major derail indeed. But I like the malloc secretary.
posted by Devonian at 8:04 PM on March 24, 2013
posted by Devonian at 8:04 PM on March 24, 2013
« Older Admit That Byron Was No Good | Adventures in Gay. Newer »
This thread has been archived and is closed to new comments
posted by TheNewWazoo at 5:47 PM on March 24, 2013 [3 favorites]