Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

Algorithms and Data Structures: Mike Swanson - Genetic Session Scheduler

Download

Right click “Save as…”

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 Smiley 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

Tags:

Follow the Discussion

  • PerfectPhasePerfectPhase "This is not war, this is pest control!" - Dalek to Cyberman

    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!

  • Joshua RossJoshRoss Niner since 2004
    It would be cool if you could have us niners throw combinations into the fitness tester, to be evaluated. Then you could have a bunch of different mothers to work with for your genetic algorithm.
  • 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.

  • This almost sounds like a smart bruteforce. This problem sounds like a perfect situation for the classic A* algorithm for optimal problem solving often use in chess programs or pathfinding.
  • umer_aumer_a Mario be on XBOX one day.
    The first part of the problem is more like a taguchi's orthognal array sort,  which can be best solved by global optimization methods, although a greedy algorithm can be sufficient for an almost-optimal solution.
  • John Melville-- MDJohn Melville-- MD Equality Through Technology
    mswanson wrote:
    

    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.



    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.

  • pbzpbz
    Good job Mike Swanson; you have a rare talent to put relatively complex ideas into words (mainly by breaking everything down). This is the reason I enjoy watching Anders as well. Please make more videos on various other algorithms or concepts.

    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 Wink
  • Thank you for the fantastic compliment, pbz. I very much appreciate the feedback, and I'm glad that my explanation made sense.

    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.
  • Herbie SmithDr Herbie Horses for courses
    John Melville, MD wrote:
    
    mswanson wrote:
    

    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.



    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.



    ++

    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 Embarassed

    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' Smiley


    Herbie
  • Few lecture notes from my class in school
    http://pages.cs.wisc.edu/~dyer/cs540/notes/geneticAlgorithms-4up.pdf
    gives a summary on genetic algorithms
  • Hey, everyone! In case you hadn't noticed, the public PDC2008 web site is now live. I hope to see many of you at the event.
  • Sparkywil2300 Super #
    I wanna be like Mike!

    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 Smiley
    Keep 'em coming Charles!
    ~sparky

Remove this comment

Remove this thread

close

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.