<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Eric Stoltz on Medium]]></title>
        <description><![CDATA[Stories by Eric Stoltz on Medium]]></description>
        <link>https://medium.com/@estoltz?source=rss-1056c764b0a1------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*H9cIpBhq6r7WSuCWoysyeA.jpeg</url>
            <title>Stories by Eric Stoltz on Medium</title>
            <link>https://medium.com/@estoltz?source=rss-1056c764b0a1------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 11:08:24 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@estoltz/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Scheduling with ease: Cost optimization tutorial for Python]]></title>
            <link>https://medium.com/data-science/scheduling-with-ease-cost-optimization-tutorial-for-python-c05a5910ee0d?source=rss-1056c764b0a1------2</link>
            <guid isPermaLink="false">https://medium.com/p/c05a5910ee0d</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[towards-data-science]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[optimization]]></category>
            <dc:creator><![CDATA[Eric Stoltz]]></dc:creator>
            <pubDate>Thu, 08 Nov 2018 15:11:29 GMT</pubDate>
            <atom:updated>2018-11-08T15:11:29.274Z</atom:updated>
            <content:encoded><![CDATA[<h4>Learn how to quickly solve optimization problems with linear programming in Python</h4><h3>Introduction</h3><h4>Context</h4><p>Congratulations! You’re the proud new owner of the coolest store in town. To keep the operation running, you need to ensure that you have the correct number of workers scheduled for each shift. In this tutorial, we’ll design the lowest cost schedule for the upcoming week.</p><h4>Considerations</h4><p>For the coming week, each day has two shifts of 8 hours. You currently have ten employees, four of which are considered managers. For any shifts beyond 40 hours in a given week (5 total shifts), you pay your employees overtime. To be fair to your employees, you decide that everyone has to work at least 3 shifts, but no more than 7 shifts. And to ensure that the shop runs smoothly, each shift requires at least one manager.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*T0f968N-VlrV6mzw" /></figure><h3>Structuring the problem</h3><p>Before diving into the code, let’s add structure to our task by defining our objective, variables, and constraints.</p><h4>Objective function</h4><p>In simple words, we want to design the lowest cost schedule, accounting for both regular time and overtime. We can define this mathematically as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/889/1*tSA2mnPSgAQFt_oohNU82w.png" /></figure><p>Where <em>w</em> is our list of workers, RegCost and OTCost are the dollar costs of a regular and overtime shift for each worker, respectively, and RegShifts and OTShifts are the total number of regular and overtime shifts for each worker, respectively.</p><h4>Variables</h4><p>We will create a list of variables for every worker/shift combination (e.g. [‘Employee1’,‘Monday1&#39;], [‘Employee2’,‘Monday1’], etc.). Each of these variables will be a binary value to signify if a worker is scheduled (1) or not (0). We’ll also need to deal with the split of regular time and overtime, which we’ll handle as a hybrid of variable and constraint.</p><h4>Constraints</h4><p>From the problem statement above, we know that there are a number of special considerations that we need to follow. To make sure that our optimized schedule is acceptable, we’ll create specific constraints:</p><ul><li>Total number of workers staffed equals total number of workers required for each shift</li><li>Workers must stay between global minimum and maximum number of shifts</li><li>Workers can only be scheduled when they are available (handled in decision variable ‘x’)</li><li>At least one manager staffed per shift</li></ul><h3>Creating our model in Python</h3><h4>Preparing the data</h4><p>Before diving into the the optimization model, we need some (illustrative) data to work with. Since loading data into Python is out of the scope of this tutorial, we’ll move through this part quickly.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d36dfba496106adc18f590a61644057e/href">https://medium.com/media/d36dfba496106adc18f590a61644057e/href</a></iframe><p>Here’s a recap of what we now have:</p><ul><li>A list of our 14 shifts (two shifts per day for one week) and our 10 employees (lines 7–9)</li><li>The number of workers needed for each shift (lines 12–13)</li><li>The availability of each worker for each shift (lines 17–23)</li><li>A list of who are managers and a list of who are not managers (lines 26–27)</li><li>The cost of a shift for each worker, both regular and overtime (lines 31–36)</li><li>A few global assumptions for min and max shifts and how many shifts are allowed before triggering overtime (lines 40–43)</li></ul><h4>Initialize the model</h4><p><em>Note: As can be seen in the above code, we are using a package called </em><a href="http://www.gurobi.com/"><em>Gurobi</em></a><em>. Gurobi is an optimization solver that is available for a number of programming languages. While the full version of Gurobi requires a commercial license, you can get an academic or online course license to run a limited version for free.</em></p><p>We first need to create the shell of our model. We do this with the following code:</p><pre>model = Model(“Workers Scheduling”)</pre><h4>Add decision variables</h4><p>Let’s turn our structured variables into code:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ef04c48968fc05f74d3345edbc84085a/href">https://medium.com/media/ef04c48968fc05f74d3345edbc84085a/href</a></iframe><p>First, we need to create binary variables for each worker/shift combination. We can do this with Gurobi’s addVars function (<em>Note: if only adding one variable, use </em>addVar<em> instead</em>). We specify that the variable is binary and we also read in the avail dictionary that we created before as a ub (“upper bound”). Each Gurobi variable has an upper and lower bound. Since we are using binary variables, naturally our variables must equal 0 or 1. By setting the upper bound equal to the values in avail , we are able to embed the constraint that certain worker/shift combinations must equal 0 (i.e. when that worker is unavailable).</p><p>Next, we have to create variables to handle the regular and overtime hours. As was mentioned before, we’ll handle this split as a combination of variable and constraint. For now, we simply create the variables for each worker without further specification. The one exception is that we set overtimeTrigger to be a binary variable (0 when there is no overtime for a given worker this week and 1 when there is overtime).</p><h4>Add constraints</h4><p>Similarly, let’s turn each constraint outlined above into code, using the addConstrs (adding multiple constraints at a time) and addConstr (adding one constraint at a time) functions.</p><p>First, we specify that the sum of assigned workers (1 for each scheduled worker, 0 for each non-scheduled worker) for each shift equals the total shift requirement:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0a23dad70a516f9956a326c0029d6631/href">https://medium.com/media/0a23dad70a516f9956a326c0029d6631/href</a></iframe><p>Next, we deal with the split between regular time and overtime. To capture this correctly, we take a conservative approach. First, we specify that the number of regular shifts plus the number of overtime shifts is equal to the total number of shifts for each worker. Then, we ensure that the number of regular shifts is less than or equal to the number of shifts specified as our overtime trigger. We do this to ensure that regular shifts are accounted for before overtime shifts. To double down on this, we add the final constraint that says that if the number of regular shifts for a worker is less than 5 (OTTrigger), then the binary trigger for overtime is set to 0.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/888805cc4851746b9ff0739319353986/href">https://medium.com/media/888805cc4851746b9ff0739319353986/href</a></iframe><p>With this in place, we can finish our final constraints. Similar to above, we calculate the total number of assigned shifts for each worker. We specify that this must be greater than or equal to the global input for minimum number of shifts and less than or equal to the global maximum number of shifts. Finally, we handle the requirement for each shift needs at least one manager to be staffed.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/99cda9486a4be52417ec4449faf3c143/href">https://medium.com/media/99cda9486a4be52417ec4449faf3c143/href</a></iframe><h4>Define the objective function</h4><p>Our objective is to minimize the total cost of the workers scheduled. We can handle this quite simply by defining a cost function that sums the total number of regular shifts times the cost of a regular shift for each worker and the total number of overtime shifts times the cost of an overtime shift for each worker. We tell Gurobi that the goal is to minimize this using ModelSense. Finally, we use setObjective to specify that Cost is the objective function.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fa09f256e73f2babba1a93421275aa17/href">https://medium.com/media/fa09f256e73f2babba1a93421275aa17/href</a></iframe><h4>Running the optimization</h4><p>Before running the optimization, it can be helpful to inspect the model. A great way to do this is:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/014ea81456706ff5899ddde36fdf8f23/href">https://medium.com/media/014ea81456706ff5899ddde36fdf8f23/href</a></iframe><p>With this code, you’ll be able to see the objective function, variables, constraints, etc. listed as formulas, which can be particularly helpful to ensure that the code is producing the functions that you intended.</p><p>After you are happy with the model, we can solve the optimization with a simple line:</p><pre>model.optimize()</pre><h4>Outputs</h4><p>The optimize function produces an output that is fairly helpful, but doesn’t give us a ton to work with. In the following steps, we’ll extract more meaningful information from the model.</p><p>First, we want to know the total cost of the proposed schedule. We find out that the cost is $7535 by running the following:</p><pre>print(&#39;Total cost = $&#39; + str(model.ObjVal))</pre><p>Now, let’s see a dashboard of the schedule using the following:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/83eff29ecc86a24072e7c5169e292aa4/href">https://medium.com/media/83eff29ecc86a24072e7c5169e292aa4/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oNZUtEz-gHgkzcZLd5ettQ.png" /><figcaption>Output of the dashboard</figcaption></figure><p>Finally, let’s create an alternative view of the dashboard by simply printing out the names of each employee assigned to each shift:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/55b0cedecf53e0e177db3a0142eaa074/href">https://medium.com/media/55b0cedecf53e0e177db3a0142eaa074/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HUMvobyE5aKEdaPpAVdnxw.png" /><figcaption>Output of the shift assignments</figcaption></figure><h3>Conclusion</h3><p>Through this tutorial, we produced an end-to-end solution to an optimization problem using Python. If this piqued your interest, play around with an example of your own. Try handling continuous decision variables, multi-objective problems, quadratic optimization, infeasible models- the possibilities are endless. And if you’re curious about creating your own optimization algorithms, check out my <a href="https://towardsdatascience.com/evolution-of-a-salesman-a-complete-genetic-algorithm-tutorial-for-python-6fe5d2b3ca35">tutorial </a>on building a genetic algorithm using Python!</p><h4>End notes</h4><p>You can find a consolidated notebook <a href="https://github.com/ezstoltz/optimization">here</a>.</p><h4>References:</h4><ul><li><a href="https://en.wikipedia.org/wiki/Gurobi">https://en.wikipedia.org/wiki/Gurobi</a></li><li><a href="https://www.sciencedirect.com/science/article/pii/S111001681730282X">https://www.sciencedirect.com/science/article/pii/S111001681730282X</a></li><li><a href="http://www.gurobi.com/documentation/8.0/examples/workforce5_py.html">http://www.gurobi.com/documentation/8.0/examples/workforce5_py.html</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c05a5910ee0d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/scheduling-with-ease-cost-optimization-tutorial-for-python-c05a5910ee0d">Scheduling with ease: Cost optimization tutorial for Python</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Evolution of a salesman: A complete genetic algorithm tutorial for Python]]></title>
            <link>https://medium.com/data-science/evolution-of-a-salesman-a-complete-genetic-algorithm-tutorial-for-python-6fe5d2b3ca35?source=rss-1056c764b0a1------2</link>
            <guid isPermaLink="false">https://medium.com/p/6fe5d2b3ca35</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[towards-data-science]]></category>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Eric Stoltz]]></dc:creator>
            <pubDate>Tue, 17 Jul 2018 16:28:25 GMT</pubDate>
            <atom:updated>2021-03-18T21:26:15.724Z</atom:updated>
            <content:encoded><![CDATA[<p>Drawing inspiration from natural selection, genetic algorithms (GA) are a fascinating approach to solving search and optimization problems. While much has been written about GA (see: <a href="https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3">here</a> and <a href="https://towardsdatascience.com/introduction-to-optimization-with-genetic-algorithm-2f5001d9964b">here</a>), little has been done to show a step-by-step implementation of a GA in Python for more sophisticated problems. That’s where this tutorial comes in! Follow along and, by the end, you’ll have a complete understanding of how to deploy a GA from scratch.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*tUKgy2w9Xvo6sPL2" /><figcaption>Photo by chuttersnap on Unsplash</figcaption></figure><h3>Introduction</h3><h4>The problem</h4><p>In this tutorial, we’ll be using a GA to find a solution to the traveling salesman problem (TSP). The TSP is described as follows:</p><blockquote>“Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?”</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*DwB6K0KKNug7-y59Uowhsg.png" /><figcaption>Illustration of a potential solution to the TSP (By Xypron [Public domain], from Wikimedia Commons)</figcaption></figure><p>Given this, there are two important rules to keep in mind:</p><ol><li>Each city needs to be visited exactly one time</li><li>We must return to the starting city, so our total distance needs to be calculated accordingly</li></ol><h4>The approach</h4><p>Let’s start with a few definitions, rephrased in the context of the TSP:</p><ul><li><strong>Gene: </strong>a city (represented as (x, y) coordinates)</li><li><strong>Individual (aka “chromosome”): </strong>a single route satisfying the conditions above</li><li><strong>Population:</strong> a collection of possible routes (i.e., collection of individuals)</li><li><strong>Parents:</strong> two routes that are combined to create a new route</li><li><strong>Mating pool:</strong> a collection of parents that are used to create our next population (thus creating the next generation of routes)</li><li><strong>Fitness:</strong> a function that tells us how good each route is (in our case, how short the distance is)</li><li><strong>Mutation:</strong> a way to introduce variation in our population by randomly swapping two cities in a route</li><li><strong>Elitism:</strong> a way to carry the best individuals into the next generation</li></ul><p>Our GA will proceed in the following steps:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*l7DaDIaCONsdHDnb" /><figcaption><a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Photo by Raw Pixel/Unsplash</a></figcaption></figure><p>1. Create the population</p><p>2. Determine fitness</p><p>3. Select the mating pool</p><p>4. Breed</p><p>5. Mutate</p><p>6. <em>Repeat</em></p><p>Now, let’s see this in action.</p><h3>Building our genetic algorithm</h3><p>While each part of our GA is built from scratch, we’ll use a few standard packages to make things easier:</p><pre>import numpy as np, random, operator, pandas as pd, matplotlib.pyplot as plt</pre><h4>Create two classes: City and Fitness</h4><p>We first create a City class that will allow us to create and handle our cities. These are simply our (x, y) coordinates. Within the City class, we add a distance calculation (making use of the Pythagorean theorem) in line 6 and a cleaner way to output the cities as coordinates with __repr__ in line 12.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/48a59510a0d9425819f4823d26d99796/href">https://medium.com/media/48a59510a0d9425819f4823d26d99796/href</a></iframe><p>We’ll also create a Fitness class. In our case, we’ll treat the fitness as the inverse of the route distance. We want to minimize route distance, so a larger fitness score is better. Based on Rule #2, we need to start and end at the same place, so this extra calculation is accounted for in line 13 of the distance calculation.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/53a6ba5530b88daed0e670c35826cea2/href">https://medium.com/media/53a6ba5530b88daed0e670c35826cea2/href</a></iframe><h4>Create the population</h4><p>We now can make our initial population (aka first generation). To do so, we need a way to create a function that produces routes that satisfy our conditions (<em>Note: we’ll create our list of cities when we actually run the GA at the end of the tutorial</em>). To create an individual, we randomly select the order in which we visit each city:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d455bf3d201c08cd92641b9607f21ac3/href">https://medium.com/media/d455bf3d201c08cd92641b9607f21ac3/href</a></iframe><p>This produces one individual, but we want a full population, so let’s do that in our next function. This is as simple as looping through the createRoute function until we have as many routes as we want for our population.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/150f85eb4ce1983dca514f33cbf23776/href">https://medium.com/media/150f85eb4ce1983dca514f33cbf23776/href</a></iframe><p><em>Note: we only have to use these functions to create the initial population. Subsequent generations will be produced through breeding and mutation.</em></p><h4>Determine fitness</h4><p>Next, the evolutionary fun begins. To simulate our “survival of the fittest”, we can make use of Fitness to rank each individual in the population. Our output will be an ordered list with the route IDs and each associated fitness score.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cfe59cdeeab0a03e40ab844c1bde7b8a/href">https://medium.com/media/cfe59cdeeab0a03e40ab844c1bde7b8a/href</a></iframe><h4>Select the mating pool</h4><p>There are a few options for how to select the parents that will be used to create the next generation. The most common approaches are either <strong>fitness proportionate selection</strong> (aka “roulette wheel selection”) or <strong>tournament selection</strong>:</p><ul><li><strong>Fitness proportionate selection</strong> (the version implemented below): The fitness of each individual relative to the population is used to assign a probability of selection. Think of this as the fitness-weighted probability of being selected.</li><li><strong>Tournament selection</strong>: A set number of individuals are randomly selected from the population and the one with the highest fitness in the group is chosen as the first parent. This is repeated to chose the second parent.</li></ul><p>Another design feature to consider is the use of <strong>elitism</strong>. With elitism, the best performing individuals from the population will automatically carry over to the next generation, ensuring that the most successful individuals persist.</p><p>For the purpose of clarity, we’ll create the mating pool in two steps. First, we’ll use the output from rankRoutes to determine which routes to select in our selection function. In lines 3–5, we set up the roulette wheel by calculating a relative fitness weight for each individual. In line 9, we compare a randomly drawn number to these weights to select our mating pool. We’ll also want to hold on to our best routes, so we introduce elitism in line 7. Ultimately, the selection function returns a list of route IDs, which we can use to create the mating pool in the matingPool function.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9612460d6ee97cfe5f01fd5f758c5076/href">https://medium.com/media/9612460d6ee97cfe5f01fd5f758c5076/href</a></iframe><p>Now that we have the IDs of the routes that will make up our mating pool from the selection function, we can create the mating pool. We’re simply extracting the selected individuals from our population.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/955cf771a1c2735e37798cff2fe76da7/href">https://medium.com/media/955cf771a1c2735e37798cff2fe76da7/href</a></iframe><h4>Breed</h4><p>With our mating pool created, we can create the next generation in a process called <strong>crossover </strong>(aka “breeding”). If our individuals were strings of 0s and 1s and our two rules didn’t apply (e.g., imagine we were deciding whether or not to include a stock in a portfolio), we could simply pick a crossover point and splice the two strings together to produce an offspring.</p><p>However, the TSP is unique in that we need to include all locations exactly one time. To abide by this rule, we can use a special breeding function called <strong>ordered crossover</strong>. In ordered crossover, we randomly select a subset of the first parent string (see line 12 in breed function below) and then fill the remainder of the route with the genes from the second parent in the order in which they appear, without duplicating any genes in the selected subset from the first parent (see line 15 in breed function below).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/729/1*YhmzBBCyAG3rtEBbI0gz4w.jpeg" /><figcaption>Illustration of ordered crossover (credit: <a href="http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5">Lee Jacobson</a>)</figcaption></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a4876cd4fdc8cff8400a7d3ecf4415ed/href">https://medium.com/media/a4876cd4fdc8cff8400a7d3ecf4415ed/href</a></iframe><p>Next, we’ll generalize this to create our offspring population. In line 5, we use elitism to retain the best routes from the current population. Then, in line 8, we use the breed function to fill out the rest of the next generation.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a279d3accf737b1519ec4cec00e964df/href">https://medium.com/media/a279d3accf737b1519ec4cec00e964df/href</a></iframe><h4>Mutate</h4><p>Mutation serves an important function in GA, as it helps to avoid local convergence by introducing novel routes that will allow us to explore other parts of the solution space. Similar to crossover, the TSP has a special consideration when it comes to mutation. Again, if we had a chromosome of 0s and 1s, mutation would simply mean assigning a low probability of a gene changing from 0 to 1, or vice versa (to continue the example from before, a stock that was included in the offspring portfolio is now excluded).</p><p>However, since we need to abide by our rules, we can’t drop cities. Instead, we’ll use <strong>swap mutation</strong>. This means that, with specified low probability, two cities will swap places in our route. We’ll do this for one individual in our mutate function:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cd335e790f82aeafb682fc7a416d558b/href">https://medium.com/media/cd335e790f82aeafb682fc7a416d558b/href</a></iframe><p>Next, we can extend the mutate function to run through the new population.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7ed89ed3c6dcfcad73f7dafa07667ce3/href">https://medium.com/media/7ed89ed3c6dcfcad73f7dafa07667ce3/href</a></iframe><h4>Repeat</h4><p>We’re almost there. Let’s pull these pieces together to create a function that produces a new generation. First, we rank the routes in the current generation using rankRoutes. We then determine our potential parents by running the selection function, which allows us to create the mating pool using the matingPool function. Finally, we then create our new generation using the breedPopulation function and then applying mutation using the mutatePopulation function.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9346260c1f58cac541c02eed016399b9/href">https://medium.com/media/9346260c1f58cac541c02eed016399b9/href</a></iframe><h4>Evolution in motion</h4><p>We finally have all the pieces in place to create our GA! All we need to do is create the initial population, and then we can loop through as many generations as we desire. Of course we also want to see the best route and how much we’ve improved, so we capture the initial distance in line 3 (remember, distance is the inverse of the fitness), the final distance in line 8, and the best route in line 9.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d5dc664438f19d2f775253899f04445a/href">https://medium.com/media/d5dc664438f19d2f775253899f04445a/href</a></iframe><h3>Running the genetic algorithm</h3><p>With everything in place, solving the TSP is as easy as two steps:</p><p>First, we need a list of cities to travel between. For this demonstration, we’ll create a list of 25 random cities (a seemingly small number of cities, but brute force would have to test over 300 sextillion routes!):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/02f707a79630c1afe870070e8a59dda4/href">https://medium.com/media/02f707a79630c1afe870070e8a59dda4/href</a></iframe><p>Then, running the genetic algorithm is one simple line of code. This is where art meets science; you should see which assumptions work best for you. In this example, we have 100 individuals in each generation, keep 20 elite individuals, use a 1% mutation rate for a given gene, and run through 500 generations:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/78567465f3031a2400313d7aceacee6c/href">https://medium.com/media/78567465f3031a2400313d7aceacee6c/href</a></iframe><h4>Bonus feature: Plot the improvement</h4><p>It’s great to know our starting and ending distance and the proposed route, but we would be remiss not to see how our distance improved over time. With a simple tweak to our geneticAlgorithm function, we can store the shortest distance from each generation in a progress list and then plot the results.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4d304a5c4f32879b4e37408a6366837f/href">https://medium.com/media/4d304a5c4f32879b4e37408a6366837f/href</a></iframe><p>Run the GA in the same way as before, but now using the newly created geneticAlgorithmPlot function:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b486e1bfb5db5a76616e76268cc2597d/href">https://medium.com/media/b486e1bfb5db5a76616e76268cc2597d/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/727/1*qM7fKNJfuKQiyYRA6QB2OA.jpeg" /><figcaption>Sample output from the geneticAlgorithmPlot function</figcaption></figure><h3>Conclusion</h3><p>I hope this was a fun, hands-on way to learn how to build your own GA. Try it for yourself and see how short of a route you can get. Or go further and try to implement a GA on another problem set; see how you would change the breed and mutate functions to handle other types of chromosomes. We’re just scratching the surface here!</p><h4>End notes</h4><p>You can find a consolidated notebook <a href="https://github.com/ezstoltz/genetic-algorithm/blob/master/genetic_algorithm_TSP.ipynb">here</a>.</p><p><strong>References:</strong></p><ul><li><a href="http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5">http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5</a></li><li><a href="https://gist.github.com/turbofart/3428880">https://gist.github.com/turbofart/3428880</a></li><li><a href="https://gist.github.com/NicolleLouis/d4f88d5bd566298d4279bcb69934f51d">https://gist.github.com/NicolleLouis/d4f88d5bd566298d4279bcb69934f51d</a></li><li><a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">https://en.wikipedia.org/wiki/Travelling_salesman_problem</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6fe5d2b3ca35" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/evolution-of-a-salesman-a-complete-genetic-algorithm-tutorial-for-python-6fe5d2b3ca35">Evolution of a salesman: A complete genetic algorithm tutorial for Python</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>