Algorithms and Data Structures: Mike Swanson - Genetic Session Scheduler

The Discussion

• 

  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!

• 

  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.

• 

  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.

• 

  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.

• 

  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
  

• 

  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.
  

• 

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

• 

  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.

• 

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