Algorithms and Data Structures: Mike Swanson - Genetic Session Scheduler
- Posted: May 21, 2008 at 4:46 PM
- 28,439 Views
- 12 Comments
Mike Swanson is at it
again. You've seen Mike on Channel 9 before and you've probably used his
SWF to XAML converter that he wrote a while back. His
latest side project promises to be quite useful for conference owners who have the complex task of planning sessions for big technical events like PDC or TechED. In fact, Mike is the PDC08 content owner and this task falls squarely on his shoulders. Instead
of littering his office with Post-It notes that represent sessions, speakers, session times and locations, he decided to write an algorithm to solve his problem, specifically a genetic algorithm.
This is the first epsiode of a new series on Channel 9, Data Structures and Algorithms, that will focus on, well, data structures and algorithms
Each episode will feature an engineer at a whiteboard discussing solutions to algorithms that they invented or
improved upon. There are many clever people who write code for Microsoft and Channel 9 will continue to highlight them and their work. This new series is an attempt to really focus the conversation to one problem and it's algorithmic solution (which will often
involve the advent of new data structures).
Enjoy. Mike is as much an engineer as he is a technical evangelist. His genetic session scheduler is an innovative approach to solving a problem rife with tediousness. Well done, Mike!
LOW RES FILE
MP4
This is the first epsiode of a new series on Channel 9, Data Structures and Algorithms, that will focus on, well, data structures and algorithms
Each episode will feature an engineer at a whiteboard discussing solutions to algorithms that they invented or
improved upon. There are many clever people who write code for Microsoft and Channel 9 will continue to highlight them and their work. This new series is an attempt to really focus the conversation to one problem and it's algorithmic solution (which will often
involve the advent of new data structures).Enjoy. Mike is as much an engineer as he is a technical evangelist. His genetic session scheduler is an innovative approach to solving a problem rife with tediousness. Well done, Mike!
LOW RES FILE
MP4
Comments Closed
Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation,
please create a new thread in our Forums,
or
Contact Us and let us know.
More posts in this blog
-
Tandy Trower: Robotics Update
-
Algorithms and Data Structures: Mike Swanson -…
-
MSDN Social Platform: Social Bookmarking, User…
Follow the Discussion
Oops, something didn't work.
What does this mean?
Following an item on Channel 9 allows you to watch for new content and comments that you are interested in. You need to be signed in to Channel 9 to use this feature.What does this mean?
Following an item on Channel 9 allows you to watch for new content and comments that you are interested in and view them all on your notifications page.sign up for email notifications?
Intreasting Video. One of the first real life programs I wrote was an attempt to write a genetic sort for scheduling production across injection molding machines about 13 years ago so found this really intreasting!
The term "genetic algorithm" seems to intrigue almost everyone (including me, when I first heard about them years ago). The reality is that it's a relatively straightforward optimization technique wrapped in a fancy name. The word "genetic" makes it sound like the algorithm is doing something biological in nature and many people then assume that it's an artificial intelligence technique...which it's not.
Charles recorded this interview a couple of hours after he read my blog post (gotta love Channel 9!), and my brain hadn't had a chance to think about how I might actually diagram or whiteboard genetic algorithms. I hope it was understandable.
If you'd like a very approachable introduction to optimization techniques like this, I'd highly recommend the book Programming Collective Intelligence by Toby Segaran. It isn't only about optimization problems, but if you like algorithms, and you don't want/need to fully appreciate all of the theory, it's an extremely practical and useful book.
The algorithm has a "biological" name because it is an almost element for element match for a very real bioloical process. Namely evolution.
The processes of mutation and crosover are not synthetic or allegorical. The chromosomes actually line up and exchange analagous segments of genetic material; this is called crossover. Chromosomes actually are subject to errors in copying that actually result in infreuent, but random mutations.
Perhaps the most interesting point of this is that computerized genetic algorithms have fed back into biology. A number of years ago a probabalistic arguement was made that the time required to evolved from an ameoba to a human being was many times the (currently believed) geologic age of the earth. The success of synthetic genetic algorithms causes some, including me, to re-examine that argument.
You know when somebody understands something when they say that it's easy. I especially enjoyed the stories behind the algorithm; makes it more interesting.
Keep them coming! I've made a C9 account just for this, so I hope it counts for something in your fitness function
I love geeky algorithms, and I've used them for a lot of fun projects. Most recently, you may have heard about SEAMonster, my C#-based implementation of the seam carving algorithm. There's no C9 video on that algorithm, though I'd be happy to talk about it if asked.
I also worked with some Bayesian inference algorithms for the NxOpinion project awhile back. It used Naive Bayes to take signs, symptoms, and laboratory measurements to infer possible diseases and afflictions. Most interesingly, it would "reverse" the process to determine what other sign, symptom, or measurement would be most useful in discriminating between results. It'd literally tell you to check something like "does the patient have diarrhea."
Last, I spent a lot of time years and years ago writing encrytion and data compression libraries. I particularly enjoyed data compression, though it's pretty much assumed and built into most frameworks today. Those were the days.
++
I didn't really 'get' (or Grok) the evolutionary mechanism until I read about genetic algorithms (in the introduction of Koza's 'Genetic Programming' book), which is kind of embarrassing for an evolutionary biologist
Evolutionary algorithms are good for this kind of 'fuzzy optimisation' work for which there is no single perfect answer, just a group of 'good' answers.
If you think genetics algorithms are 'relatively straightforward' then you've just managed the hardest part of understanding evolution: it's not mystical or complex just because it's biological, it 'relatively straightforward'
Herbie
http://pages.cs.wisc.edu/~dyer/cs540/notes/geneticAlgorithms-4up.pdf
gives a summary on genetic algorithms
As I have said in other posts, I don't have too much experience with algorithms but I really hope I get the chance to learn about some at least. This was a very cool presentation and very, very informative in a relatively short time slot. The explanations were clear and easily understandable.
Hope to see more in the future.
I wish I can go to the PDC, but I need a job first
Keep 'em coming Charles!
~sparky
Remove this comment
Remove this thread
close