Practical Evolutionary Computing
NatureInspired Algorithms for Optimization Problems
Evolutionary computing is a natural framework for addressing multiobjective optimization problems where the quality of a particular solution is evaluated on multiple metrics. Evolutionary computing uses the basic principles of random variance and survival of the fittest to gradually evolve a population of solutions to a problem. For example, in a factory floor environment, evolutionary computing has been used to optimize machine scheduling, inventory management, and transportation logistics aimed at minimizing costs while maximizing ontime delivery and customer satisfaction. Or, imagine a couple trying to plan a wedding and needing to seat their guests at various tables. Their goal is to minimize constraint violations (avoid seating Uncle Joe with Aunt Mary), minimize age variance (don’t seat your friend from college at the kids’ table), and perhaps make sure that certain people sit together (your book club should all sit at the same table). These two problems, despite their differences, can be tackled with the same general problemsolving framework.
This course will teach learners how to identify optimization problems and solve them with evolutionary computing. We will work on two different problems: the NQueens Problem and a variant of the Traveling Salesperson Problem with multiple objectives. Learners will get a chance to work handson and implement their own generic evolutionary computing system. We will explore some of the possible extensions to this system, including parallelizing the system and building a metasystem that optimizes how our first system works. Learners will leave this course with a clearer understanding of optimization problems and a new tool to apply in optimization situations.
What you'll learnand how you can apply it
By the end of this live, handson, online course, you’ll understand:
 The definition of an optimization problem, and how to identify them in the real world.
 The design of evolutionary computing systems, and how to improve their performance.
And you’ll be able to:
 Use evolutionary computing to solve optimization problems.
 Use evolutionary computing to approximate solutions to hard (NPcomplete) problems.
This training course is for you because...
 You’re a software engineer who wants to be able to solve problems that don’t have known algorithms, or where the known algorithms are too slow.
 You are often faced with problems with more potential solutions than you have time to try, and you want an algorithm to produce a reasonably good solution for you.
Prerequisites
 Basic or intermediate familiarity with Python
 Comfort with highschool level algebra
Recommended preparation:
 Examples and exercises will be provided as notebooks in JupyterHub during class
Recommended followup:
About your instructor

Julian Zucker is a software engineer at Pivotal where he works on opensource protocol for monitoring cloud computing workloads. Previously, he worked at PayPal as a Business Intelligence Engineer, creating largescale data processing systems for analytics. He is a core developer on Evvo, an opensource distributed evolutionary computing framework. He has published work on simulations of the evolution of intergroup social interactions, and parallelized the simulations to run a thousand times faster, allowing the exploration of ideas that were never before able to be simulated.
Schedule
The timeframes are only estimates and may vary according to how the class is progressing
Optimization Problems (10 minutes)
 Euclidean optimization
 What is an optimization problem?
 Optimizing onedimensional Euclidean functions (like f(x) = …)
 Optimization methods: grid search optimization, random search, gradient descent
 Optimizing twodimensional Euclidean functions (like f(x,y) = …)
 How those optimization methods look in multiple dimensions
 Discussion
 Why are some functions harder to optimize than others?
 Is it possible to find the optimum of every function?
 How good is grid search/gradient descent guaranteed to get?
 Can you think of any other algorithms than the ones we proposed to solve these problems?
 Presentation: NonEuclidean optimization
 Optimizing vectors of floats
 Example – evolved antennas
 Example – Nqueens solutions
 Q&A
Introduction to Evolutionary Computing (25 minutes)
 How does natural selection work?
 What is evolutionary computing?
 Requirements: fitness function, initial population, mutator
 When do you stop?
 Main loop pseudocode
 Different representations for the Nqueens problem
 Discussion
 What are some up/downsides of evolutionary computing over the previous optimization approaches?
 What are the effects of population size on optimization speed?
 Is it better to have “smarter” mutators? What if it takes longer for them to run?
 Exercise
 Implement the main loop! Use your fitness functions from before, and a provided simple operator that swaps two points.
 Find a solution to the 8queens problem, using the code you just wrote.
 Q&A
 Break (5 minutes)
Solving the NQueens Problem (20 minutes)
 Three different representations for the Nqueens problem
 How to benchmark? Speed to perfect solution works here, but not always
 Explain the API of the provided benchmarking function
 Exercise: Benchmark your solution, using the provided library functions
 Presentation: Performance comparisons
 Q&A
MultiObjective Optimization (30 minutes)
 When is an optimization problem multiobjective?
 How do you define the objectives?
 Why can’t you just add the objectives/combine them?
 How do you delete solutions? Can’t just take “best” now
 False negative rate/false positive rate/fairness in ML
 Discussion
 Discuss some examples of multiobjective problems in real world
 Is it ever reasonable to combine these different objectives?
 When might you want to convert a single objective into multiple?
 Exercise: Fill in the missing elements of the multiobjective optimizer skeleton code
 Q&A
 Break (5 minutes)
BiObjective Traveling Salesperson Problem (50 Minutes)
 Regular, oneobjective traveling salesperson problem
 Famously NPHard
 But good algorithms exist – not a good place to use evolutionary computing
 The biobjective traveling salesperson problem
 Introduction of the second objective
 Similar to time/cost of deliveries
 Solution representation (tour)
 How to create initial population
 Random, greedy, and hybrid approaches
 Mutation operators
 Crossover operators
 Examples of problems that can be converted to Biobjective traveling salesperson problem, and their applications
 Introduction to the scaffolding I provide – the fitness functions are predefined, as well as a “safety checker” that ensures a tour is valid.
 Exercise
 Implement a mutation operator that swaps two random cities in the tour
 Implement a crossover operator for onepoint crossover
 Apply those to the main loop to evolve TSP solutions.
 Q&A
Extensions (15 Minutes)
 Parallelism
 Constraints on solutions
 Dynamically create new solutions, instead of initial population
 Vary population size to maximize diversity when stagnating
 Logging/tracing to identify good mutation operators
 Evolving which operators are used (“metaevolutionary systems”)
 Other problems
 Q&A
Final Q&A (5 minutes)