Skip to content

Explore Courses | Elder Research | Contact | LMS Login

Statistics.com Logo
  • Courses
    • See All Courses
    • Calendar
    • Intro stats for college credit
    • Faculty
    • Group training
    • Credit & Credentialing
    • Teach With Us
  • Programs/Degrees
    • Certificates
      • Analytics for Data Science
      • Biostatistics
      • Programming For Data Science – Python (Experienced)
      • Programming For Data Science – Python (Novice)
      • Programming For Data Science – R (Experienced)
      • Programming For Data Science – R (Novice)
      • Social Science
    • Undergraduate Degree Programs
    • Graduate Degree Programs
    • Massive Open Online Courses (MOOC)
  • Partnerships
    • Higher Education
    • Enterprise
  • Resources
    • About Us
    • Blog
    • Word Of The Week
    • News and Announcements
    • Newsletter signup
    • Glossary
    • Statistical Symbols
    • FAQs & Knowledge Base
    • Testimonials
    • Test Yourself
Menu
  • Courses
    • See All Courses
    • Calendar
    • Intro stats for college credit
    • Faculty
    • Group training
    • Credit & Credentialing
    • Teach With Us
  • Programs/Degrees
    • Certificates
      • Analytics for Data Science
      • Biostatistics
      • Programming For Data Science – Python (Experienced)
      • Programming For Data Science – Python (Novice)
      • Programming For Data Science – R (Experienced)
      • Programming For Data Science – R (Novice)
      • Social Science
    • Undergraduate Degree Programs
    • Graduate Degree Programs
    • Massive Open Online Courses (MOOC)
  • Partnerships
    • Higher Education
    • Enterprise
  • Resources
    • About Us
    • Blog
    • Word Of The Week
    • News and Announcements
    • Newsletter signup
    • Glossary
    • Statistical Symbols
    • FAQs & Knowledge Base
    • Testimonials
    • Test Yourself
Student Login

Blog

Home Blog Evolutionary Algorithms

Evolutionary Algorithms

It was 150 years ago when Darwin first used the term “evolution” in his writing (in his book The Descent of Man).  Two months ago, in The Normal Share of Paupers, I briefly discussed the unfortunate eugenics baggage that the discipline of statistics inherited from Charles Darwin, baggage that left a taint (at least to modern eyes) on the founding fathers of statistics.  A later, less toxic, statistical inheritance from Darwin is the evolutionary algorithm, used to solve optimization problems where there are too many potential solutions to examine them all exhaustively.

Traveling Salesman

Consider the traveling salesman problem (TSP), a classic in operations research.  A salesman must visit n clients, all in different locations.  How should the salesman travel to minimize travel time?  To guarantee an optimal solution, all the routes must be examined.  With a small number of routes, the problem is tractable.
Traveling Salesman Problem

For example, with 4 clients, starting with the client in location 1, there are (n-1)!, or six ways to complete the journey:

1 > 2 > 3 > 4

1 > 2 > 4 > 3

1 > 3 > 2 > 4

1 > 3 > 4 > 2

1 > 4 > 2 > 3

1 > 4 > 3 > 2

With more destinations, though, the task of examining all solutions balloons out of control.  With 17 locations, there are nearly 21 trillion routes.  An evolutionary algorithm takes the following approach:

  1. Start with an arbitrary (often random) set of possible solutions, and score each for their “fitness” (i.e. the time to complete the route).
  2. Modify a few of the solutions by “crossover” – exchange route elements between solutions (for example, if one route solution goes … 7 > 3 > 4 … and another goes … 3 > 4 > 7 then swap those segments).
  3. Modify a few other solutions by randomly changing elements (“mutation”).
  4. Assess this new “population” of solutions, drop the poor performers and replace them with more crossovers and mutations (“survival of the fittest”).
  5. Keep repeating.

This process, considering only a small subset of solutions at a time, gradually discovers better and better solutions, just as the genetic processes of crossover and mutation improve the fitness and survivability of species.  The random component helps avoid a common problem in non-exhaustive optimization – getting stuck in local optima.  

Other Applications

Dr. Cliff Ragsdale The traveling salesman is an evocative, if somewhat anachronistic image, that stands in for a whole range of problems.  Cliff Ragsdale, instructor for our three optimization courses (see the Mastery Series in Optimization), and author of the best selling text Spreadsheet Modeling and Decision Analysis, describes one such problem:

The Wolverine Manufacturing Company operates machines that can be programmed to automatically perform precise drilling and machining operations.  The current job requirement is for nine holes to be drilled in precise locations on a flat fiberglass panel that is used in the production of a popular automobile. After each hole is drilled, the machine retracts the drill bit and moves it (somewhat slowly) to the next location until all nine holes have been completed.  Because this process must be repeated for millions of panels, Wolverine wants to make sure it programs the machine to move from hole to hole in the most efficient manner – minimizing the total distance the drill must travel.

In this problem the drill bit is the salesman, and the path it follows from hole to hole is the salesman’s route.

Instacart

Instacart Logo Instacart is a grocery delivery service using the gig model – individuals “shoppers” use the Instacart app to secure assignments to shop at a grocery store on behalf of someone, and then deliver the items to that person.  The service has soared in popularity as a result of the Covid-19 lockdown.  

Instacart needs to solve the Traveling Salesman Problem to efficiently route its shoppers.  Actually, it needs to solve a more general (harder) version of the TSP known as the Vehicle Routing Problem (VRP) because it must make decisions about how to route not just one shopper and one batch of orders, but numerous shoppers with numerous order batches.  Plus, it has to meet a time constraint, to get the orders delivered in time.  Jeremy Stanley, former VP of Data Science at Instacart, has written a highly readable summary about these and further refinements of the TSP that Instacart must deal with to route its shoppers.

History of Julia Robinson in 1983 The Traveling Salesman Problem was given its name by the American Mathematician Julia Robinson in 1948, but its antecedents go back to the 1800’s.  It served as the catalyst for a number of the puzzle-style challenges that are so popular in the mathematical and statistical communities, and contributed to the development of a number of different algorithms to approximate the optimal solution, of which the evolutionary approach outlined above is just one.

Recent Posts

  • Oct 6: Ethical AI: Darth Vader and the Cowardly Lion
    /
    0 Comments
  • Oct 19: Data Literacy – The Chainsaw Case
    /
    0 Comments
  • Data Literacy – The Chainsaw Case
    /
    0 Comments

About Statistics.com

Statistics.com offers academic and professional education in statistics, analytics, and data science at beginner, intermediate, and advanced levels of instruction. Statistics.com is a part of Elder Research, a data science consultancy with 25 years of experience in data analytics.

 The Institute for Statistics Education is certified to operate by the State Council of Higher Education for Virginia (SCHEV)

Our Links

  • Contact Us
  • Site Map
  • Explore Courses
  • About Us
  • Management Team
  • Contact Us
  • Site Map
  • Explore Courses
  • About Us
  • Management Team

Social Networks

Facebook Twitter Youtube Linkedin

Contact

The Institute for Statistics Education
2107 Wilson Blvd
Suite 850 
Arlington, VA 22201
(571) 281-8817

ourcourses@statistics.com

  • Contact Us
  • Site Map
  • Explore Courses
  • About Us
  • Management Team

© Copyright 2023 - Statistics.com, LLC | All Rights Reserved | Privacy Policy | Terms of Use

By continuing to use this website, you consent to the use of cookies in accordance with our Cookie Policy.

Accept