{"id":562929,"date":"2017-07-24T00:00:03","date_gmt":"2017-07-24T07:00:03","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?p=562929"},"modified":"2019-01-31T17:14:05","modified_gmt":"2019-02-01T01:14:05","slug":"genetic-algorithm-in-reverse-mode","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/blog\/genetic-algorithm-in-reverse-mode\/","title":{"rendered":"Genetic Algorithm, in Reverse Mode"},"content":{"rendered":"<p>Today I would like to discuss running <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/en.wikipedia.org\/wiki\/Genetic_algorithm\" target=\"_blank\" rel=\"noopener noreferrer\">genetic algorithm<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>\u2026 backwards.<\/p>\n<p>Yes, this is possible. Occasionally it is practical, when you need not the best, but the worst solution to a problem.<\/p>\n<p>And I think there are more uses for it. It seems to be helpful with maintaining genetic pool diversity, with avoiding being stuck in local maximum \u2013 and therefore with finding <strong>better<\/strong> solutions to problems.<\/p>\n<p>Some variations of this idea are apparently known, but not widely. And there is certain bridging between this method and simulated annealing. So I figured it is worth sharing my observations &#8212; and <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/msdnshared.blob.core.windows.net\/media\/2017\/07\/Code.zip\" target=\"_blank\" rel=\"noopener noreferrer\">the code accompanying them<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>.<\/p>\n<p style=\"text-align: center;\">***<\/p>\n<p><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/en.wikipedia.org\/wiki\/Genetic_algorithm\" target=\"_blank\" rel=\"noopener noreferrer\">Genetic (or evolutionary) algorithms<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> are not first class citizens in the world of optimization methods. The primary reason for that is their ability to make tough problems look deceivingly simple. A basic implementation of a genetic algorithm needs less than a screen of code; the idea behind it is obvious and intuition-friendly. With that, it is very tempting to ignore nature and inherent complexity of a problem being solved and let the CPU cycle, hoping it would eventually crank out a solution.<\/p>\n<p>Only when it fails after millions of seconds one realizes that subtle details rule everything here. How is a solution represented as a vector? What are crossbreeding and mutation strategies? How do you choose the winner and how (or if) do you run a tournament? What do you do to avoid convergence to a sub-optimal maximum? These hyper-parameters are difficult to quantify to enable a systematic search within their space. Yet wrong choices slow things down by orders of magnitude. That\u2019s why genetic algorithms often remain an art (if not a magic) to a large degree &#8212; larger than many alternatives.<\/p>\n<p>Yet they aren&#8217;t useless. They tolerate poorly defined or implicit fitness functions. They are somewhat less inhibited by the curse of dimensionality. People do solve real problems with them, sometimes quite productively:<\/p>\n<ul>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/en.wikipedia.org\/wiki\/Evolved_antenna\" target=\"_blank\" rel=\"noopener noreferrer\">Classic \u201cNASA antenna\u201d case<span class=\"sr-only\"> (opens in new tab)<\/span><\/a><\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/www.researchgate.net\/publication\/257925221_Fuzz_in_the_Dark_Genetic_Algorithm_for_Black-Box_Fuzzing\" target=\"_blank\" rel=\"noopener noreferrer\">Genetic algorithm driven fuzzer<span class=\"sr-only\"> (opens in new tab)<\/span><\/a><\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.clbme.bas.bg\/bioautomation\/2014\/vol_18.3\/files\/18.3_03.pdf\" target=\"_blank\" rel=\"noopener noreferrer\">Prosthetic operations optimization<span class=\"sr-only\"> (opens in new tab)<\/span><\/a><\/li>\n<\/ul>\n<p>They do have their uses, and they are fun to play with.<\/p>\n<p>And one fun aspect is that you can run them backwards.<\/p>\n<p>That\u2019s it, you can replace \u201cgood\u201d with \u201cbad\u201d \u2013 and run not for the best, but for the worst solution. Besides interesting philosophical implications, this also offers a strategy of dealing with local optima convergence.<\/p>\n<p style=\"text-align: center;\">***<\/p>\n<p>This issue \u2013 converging not to a global, but to a local sub-optimal solution \u2013 is inherent to many optimization methods. When a problem has multiple solutions, an algorithm can arrive to *<strong>a<\/strong>* solution, and then sit there forever, despite a better solution possibly existing couple valleys away. Steven Skiena described that situation very vividly:<\/p>\n<blockquote><p>\u201cSuppose you wake up in a ski lodge, eager to reach the top of the neighboring peak. Your first transition to gain altitude might be to go upstairs to the top of the building. And then you are trapped. To reach the top of the mountain, you must go downstairs and walk outside, but this violates the requirement that each step has to increase your score.\u201d<\/p><\/blockquote>\n<p>Genetic algorithms are not immune against this. Large body of scientific research addressing it is developed, to name a few examples:<\/p>\n<ul>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.ijetae.com\/files\/Volume2Issue5\/IJETAE_0512_10.pdf\" target=\"_blank\" rel=\"noopener noreferrer\">An Overview of methods maintaining Diversity in Genetic Algorithms<span class=\"sr-only\"> (opens in new tab)<\/span><\/a><\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/lazytoad.com\/lti\/pub\/aaai84.html\" target=\"_blank\" rel=\"noopener noreferrer\">Maintaining Diversity in Genetic Search <span class=\"sr-only\"> (opens in new tab)<\/span><\/a><\/li>\n<\/ul>\n<p>Sometimes the strategy is to run the algorithm multiple times from new random seeds, hoping to converge to a different solution each time. Sometimes people introduce artificial &#8220;species pressure&#8221; whereas solutions too similar to each other can&#8217;t cross-breed and converge\u00a0to the same point. Or they artificially separate the search space into isolated zones. Or punish for staying too close to an already learned local maxima.<\/p>\n<p style=\"text-align: center;\">***<\/p>\n<p>So how does running algorithm in a \u201creverse mode\u201d may help with avoiding local maxima?<\/p>\n<p>To illustrate, let\u2019s pretend we are looking for the highest point on the US elevation map:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565149\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map0.jpg\" alt=\"\" width=\"615\" height=\"385\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map0.jpg 615w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map0-300x188.jpg 300w\" sizes=\"auto, (max-width: 615px) 100vw, 615px\" \/><\/p>\n<p>Assume, for a moment, that somehow (maybe because of an unlucky initial placements, maybe because the map is more complex than this) all genetic pool solutions congregated around a wrong local maximum of Appalachian Mountains:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565152\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map20.jpg\" alt=\"\" width=\"615\" height=\"385\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map20.jpg 615w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map20-300x188.jpg 300w\" sizes=\"auto, (max-width: 615px) 100vw, 615px\" \/><\/p>\n<p>[Important: the arrows do not imply continuous movement. Genetic algorithm does not work like a gradient descent. The arrows serve purely illustrational purposes of indicating (most likely discontinuous) state transitions]<\/p>\n<p>What happens if you switch the evolution sign at this moment? When the least fit wins, and the worst solution is rewarded, the genetic pool starts running away from the local maximum, initially in all directions:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565155\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map30.jpg\" alt=\"\" width=\"615\" height=\"385\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map30.jpg 615w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map30-300x188.jpg 300w\" sizes=\"auto, (max-width: 615px) 100vw, 615px\" \/><\/p>\n<p>That <strong>diversifies<\/strong> it. Soon, the pool may have very little in common with the solution it initially described. After a while, it may even converge to a local minimum, which I would guess is near the Mississippi delta (though there is no point necessarily in keeping the evolution \u201cin reverse\u201d that long enough):<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565158\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map40.jpg\" alt=\"\" width=\"615\" height=\"385\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map40.jpg 615w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map40-300x188.jpg 300w\" sizes=\"auto, (max-width: 615px) 100vw, 615px\" \/><\/p>\n<p>Now let\u2019s flip the sign of the evolution back to normal. Again, the solutions will start scattering away in all direction from the local minima:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565161\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map50.jpg\" alt=\"\" width=\"615\" height=\"385\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map50.jpg 615w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map50-300x188.jpg 300w\" sizes=\"auto, (max-width: 615px) 100vw, 615px\" \/><\/p>\n<p>And, if some of them arrives to a point elevated enough, eventually everyone would re-converge there:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565164\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map60.jpg\" alt=\"\" width=\"615\" height=\"385\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map60.jpg 615w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/Map60-300x188.jpg 300w\" sizes=\"auto, (max-width: 615px) 100vw, 615px\" \/><\/p>\n<p>In a two-dimensional case, this is almost trivial. But in higher dimensionality, where mountains are more difficult to discover, these fourth-and-back cycles may need to continue until you are happy with the solution. Or at least happier than in the beginning &#8212; I&#8217;m not promising miracles here :))<\/p>\n<p>Why would this work better than restarting each time from a random seed?<\/p>\n<p>It may not always do, though my testing suggests that sometimes it does. The main benefit here is in having the control over the degree of the digression. If\u00a0other maximum is expected far away or nearby, the backwards-evolution can run for longer or shorter period, as needed. In that respect, this approach is similar to simulated annealing which is able to adjust annealing schedule to throw just the right degree of chaos into the computation.<\/p>\n<p>But all the above are just my expectations. Would they work in practice?<\/p>\n<p>Let&#8217;s find out by playing it against a toy problem that is easy to visualize.<\/p>\n<p>Welcome the <strong>Scary Parking Lot Problem.<\/strong><\/p>\n<p style=\"text-align: center;\">***<\/p>\n<p>Imagine that this is a map of a parking lot at night. There are a few lights producing illuminated patches here and there, and the rest of it is mostly dark:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565170\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9.Parking.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9.Parking.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9.Parking-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9.Parking-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>The darker the area, the scarier it is in it. Our goal is to find the least scary path from the top left to the bottom right. To be precise, we want to minimize the integral of Fear = 1\/(1 + Brightness) along the path. If asked, I would\u2019ve probably charted\u00a0it like this:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565173\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9.Parking-Human.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9.Parking-Human.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9.Parking-Human-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9.Parking-Human-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>This problem is well suited for genetic algorithm. Encode a path as a sequence of <<strong>x<\/strong>, <strong>y<\/strong>> points. A genome is represented then as a sequence <<strong>x<\/strong><strong><sub>0<\/sub><\/strong>, <strong>y<\/strong><strong><sub>0<\/sub><\/strong>, <strong>x<\/strong><strong><sub>1<\/sub><\/strong>, <strong>y<\/strong><strong><sub>1<\/sub><\/strong>, &#8230;, <strong>x<\/strong><strong><sub>N<\/sub><\/strong>, <strong>y<\/strong><strong><sub>N<\/sub><\/strong>> (I used <strong>N<\/strong> = <strong>20<\/strong>). Initialize the pool randomly with <strong>K<\/strong> =<strong>16<\/strong> instances colored in green (blue shows the best solution found so far), and kick off the algorithm.<\/p>\n<p>Iteration 0:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565176\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration0.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration0.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration0-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration0-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>In just 500 iterations, the algorithm already hints at a decent approximation:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565179\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration500.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration500.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration500-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration500-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>1000 iterations:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565182\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration1000.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration1000.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration1000-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration1000-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>4000:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565185\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration4000.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration4000.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration4000-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration4000-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>By 9000, it is mostly straightening out small knots:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565188\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration9000.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration9000.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration9000-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration9000-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>18000 generations \u2013 final or nearly final:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565191\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration18000.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration18000.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration18000-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/9-Iteration18000-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>[The red figure at the bottom left is the &#8220;cost&#8221;, or the total fear factor,\u00a0of the solution &#8212; the smaller, the better].<\/p>\n<p style=\"text-align: center;\">***<\/p>\n<p>I tried it on a few dozen randomly generated \u201cparking lots\u201d and discovered that genetic algorithm solves this problem so well that it is actually difficult to find a field that would produce a grossly imperfect result. It took quite many experiments until I discovered this \u201cfoam bubbles\u201d setup with intentionally harsh contrast and narrow illuminated zones. Constantly forced to make difficult right-or-left choices, and having no gradient feedback, the algorithm responded with some mistakes here.<\/p>\n<p>Start:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565194\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration0.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration0.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration0-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration0-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>500 iterations:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565197\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration500.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration500.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration500-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration500-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>2000:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565200\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration2000.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration2000.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration2000-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration2000-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>7000:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565203\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration70001.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration70001.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration70001-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration70001-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>18000 (final):<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565206\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration180002.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration180002.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration180002-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration180002-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>The solution is stuck. Wrapped around a bubble, it won&#8217;t change to anything better no matter how long you run it. Not coincidentally, it has also lost its genetic diversity.<\/p>\n<p style=\"text-align: center;\">***<\/p>\n<p>Now let\u2019s try to untangle it by enabling the reversals. Every 6000 iterations we will put the evolution in the \u201cbackwards mode\u201d for 210 steps.<\/p>\n<p>For the first 6000 generations it is the same game, converging to the already familiar solution:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565212\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6000-1.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6000-1.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6000-1-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6000-1-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>But then, at 6000, the reversal begins. \u201cBad\u201d solutions are in favor now. Lets\u2019 watch how they develop, spreading away from the original path.<\/p>\n<p>6100:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565215\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6100.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6100.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6100-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6100-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>6200:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565218\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6200.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6200.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6200-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration6200-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>At 6210 the sign changes back to normal and we start re-converging \u2013 to a different maximum this time!<\/p>\n<p>At 1200:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565221\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration12000.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration12000.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration12000-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration12000-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>After 12000, another reversal cycle follows, ending up with the 3rd solution at 18K:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565224\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration180001.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration180001.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration180001-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-Iteration180001-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>Of all three, the 2<sup>nd<\/sup> is the best:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565227\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-TheBest.png\" alt=\"\" width=\"240\" height=\"240\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-TheBest.png 240w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-TheBest-150x150.png 150w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/1-TheBest-180x180.png 180w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>Its cost is 63279.6. It is still not perfect, but the control (without reversals) was 79896.5. The new solution is 20.8% cheaper!<\/p>\n<p style=\"text-align: center;\">***<\/p>\n<p>But maybe this works just for this one parking lot?<\/p>\n<p>Let\u2019s repeat the experiment 40 times with different \u201cbubble sets\u201d, each randomly generated:<\/p>\n<table>\n<tbody>\n<tr>\n<td><\/td>\n<td><strong>Control (18K iterations)<\/strong><\/td>\n<td><strong>Experiment (18K iterations, with 2 reversals 210 steps each)<\/strong><\/td>\n<\/tr>\n<tr>\n<td>Average cost of the best solution relative to a random path<\/td>\n<td>0.13448<\/td>\n<td>0.11605<\/td>\n<\/tr>\n<tr>\n<td>Standard deviation<\/td>\n<td>0.034179<\/td>\n<td>0.024659<\/td>\n<\/tr>\n<tr>\n<td>Student t-score of the improvement<\/td>\n<td>N\/A<\/td>\n<td>2.76637863954974<\/td>\n<\/tr>\n<tr>\n<td>How many times the solution found was better than control?<\/td>\n<td>N\/A<\/td>\n<td>30 (out of 40)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p>A one-sided t-score of 2.77 with 40 degrees of freedom corresponds (<a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/en.wikipedia.org\/wiki\/Student%27s_t-distribution#Table_of_selected_values\" target=\"_blank\" rel=\"noopener noreferrer\">https:\/\/en.wikipedia.org\/wiki\/Student%27s_t-distribution#Table_of_selected_values<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>) to roughly 99.5% chance that the difference is not accidental. In other words, that the experiment with reversals indeed performed better than the same 18K iterations straight. And for 30 parking lots (out of 40), the solution found was better than the control.<\/p>\n<p>How does it compare to simply doing three runs with 6K steps, each starting from a random seed, and then selecting the best solution? It is about the same, or maybe very slightly better. Restarts from the scratch produced an improvement t-score of 2.5538656109400, with 24 runs out of 40 doing better than control.<\/p>\n<p style=\"text-align: center;\">***<\/p>\n<p>Finally, why 210 reversal steps? Why not more or less?<\/p>\n<p>This is where the power of the idea materializes. Reversals let you <strong>control<\/strong> their duration \u2013 and adjust it as needed for the task being solved. By playing with those durations, I produced the following plot of improvement t-score (relative to the control):<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565230\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/t-Score.png\" alt=\"\" width=\"480\" height=\"289\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/t-Score.png 480w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/t-Score-300x181.png 300w\" sizes=\"auto, (max-width: 480px) 100vw, 480px\" \/><\/p>\n<p>Blue curve are the results with reversals, orange is the result of random reset (for fixed RNG seeding). Obviously, there is fluctuation here, so I can\u2019t strictly say that reversals are better than random resets. But it does not take away the fact that reversals produced <strong>some<\/strong> solutions better than anything else tried did.<\/p>\n<p>Finally, here is another plot, showing the number of \u201cparking lots\u201d where solutions with\u00a0reversals or random reset were better than control:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-565233\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/SolutionsCount.png\" alt=\"\" width=\"480\" height=\"289\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/SolutionsCount.png 480w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/07\/SolutionsCount-300x181.png 300w\" sizes=\"auto, (max-width: 480px) 100vw, 480px\" \/><\/p>\n<p style=\"text-align: center;\">***<\/p>\n<p>So, is this method a magic bullet? Probably not.\u00a0It is just a tool, among many other invented by people to deal with practical problems. But maybe it would be helpful for some.<\/p>\n<p>To summarize:<\/p>\n<ul>\n<li>Reversing genetic algorithm during its run is possible<\/li>\n<li>\u2026at least, for finding deliberately bad \u201canti-solutions\u201d to a problem<\/li>\n<li>\u2026or simply for fun<\/li>\n<li>More importantly, sometimes\u00a0it can help combat the loss of pool\u2019s genetic diversity<\/li>\n<li>Short controlled reversals can produce solutions notably better than those from simple uninterrupted runs of the same duration<\/li>\n<li>They are at least comparable in quality to solutions achieved by restarting the algorithm from scratch the same number of times as the number of reversals<\/li>\n<li>Duration and frequency of reversal cycles are controllable numeric parameters that could be adjusted to suit a problem at hands<\/li>\n<\/ul>\n<p><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/msdnshared.blob.core.windows.net\/media\/2017\/07\/Code.zip\" target=\"_blank\" rel=\"noopener noreferrer\">Link to the code.<span class=\"sr-only\"> (opens in new tab)<\/span><\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Today I would like to discuss running genetic algorithm\u2026 backwards. Yes, this is possible. Occasionally it is practical, when you need not the best, but the worst solution to a problem. And I think there are more uses for it. It seems to be helpful with maintaining genetic pool diversity, with avoiding being stuck in [&hellip;]<\/p>\n","protected":false},"author":39507,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_hide_image_in_river":0,"footnotes":""},"categories":[1],"tags":[187057,243492],"research-area":[13561],"msr-region":[],"msr-event-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-impact-theme":[],"msr-promo-type":[],"msr-podcast-series":[],"class_list":["post-562929","post","type-post","status-publish","format-standard","hentry","category-research-blog","tag-data-science","tag-genetic-algorithms","msr-research-area-algorithms","msr-locale-en_us"],"msr_event_details":{"start":"","end":"","location":""},"podcast_url":"","podcast_episode":"","msr_research_lab":[],"msr_impact_theme":[],"related-publications":[],"related-downloads":[],"related-videos":[],"related-academic-programs":[],"related-groups":[],"related-projects":[],"related-events":[],"related-researchers":[{"type":"guest","value":"eugene-bobukh","user_id":"562986","display_name":"Eugene Bobukh","author_link":"<a href=\"https:\/\/www.linkedin.com\/in\/eugenebo\/\" aria-label=\"Visit the profile page for Eugene Bobukh\">Eugene Bobukh<\/a>","is_active":true,"last_first":"Bobukh, Eugene","people_section":0,"alias":"eugene-bobukh"}],"msr_type":"Post","byline":"<a href=\"https:\/\/www.linkedin.com\/in\/eugenebo\/\" title=\"Go to researcher profile for Eugene Bobukh\" aria-label=\"Go to researcher profile for Eugene Bobukh\" data-bi-type=\"byline author\" data-bi-cN=\"Eugene Bobukh\">Eugene Bobukh<\/a>","formattedDate":"July 24, 2017","formattedExcerpt":"Today I would like to discuss running genetic algorithm\u2026 backwards. Yes, this is possible. Occasionally it is practical, when you need not the best, but the worst solution to a problem. And I think there are more uses for it. It seems to be helpful&hellip;","locale":{"slug":"en_us","name":"English","native":"","english":"English"},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/562929","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/users\/39507"}],"replies":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/comments?post=562929"}],"version-history":[{"count":5,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/562929\/revisions"}],"predecessor-version":[{"id":565236,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/562929\/revisions\/565236"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=562929"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/categories?post=562929"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/tags?post=562929"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=562929"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=562929"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=562929"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=562929"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=562929"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=562929"},{"taxonomy":"msr-promo-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-promo-type?post=562929"},{"taxonomy":"msr-podcast-series","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-podcast-series?post=562929"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}