Lecture 5B: Physics-Inspired Algorithms and Simulated Annealing (2020-02-26)

In this lecture, we continue to discuss nature-inspired algorithms that come from the non-biological, physics realm. Maximum entropy (MaxEnt) is portrayed through a number of more concrete examples as a modeling framework that generates a probability distribution that is constrained by what information is formally known and is otherwise maximal in its degrees of freedom (thereby not introducing additional biases). It is applied to a simple Natural Language Processing (NLP) example, and then we pivot to talking about MaxEnt in terms of physical systems and how the Boltzmann–Gibbs distribution results. We then use the Boltzmann–Gibbs distribution as a motivation for the Metropolis (and then Metropolis–Hastings) Markov Chain Monte Carlo (MCMC) algorithm and predict how we will change the MH algorithm into the Simulated Annealing (SA) algorithm from Kirkpatrick et al. (1983). We will cover the SA more concretely in the next lecture.

Whiteboard notes for this lecture can be found at: 

https://www.dropbox.com/s/nbtbiptl0sldm05/IEE598-Lecture5B-Notes.pdf?dl=0

Lecture 5A: Introduction to Simulated Annealing (2020-02-24)

In this lecture, we dive into the history behind simulated annealing and how it intersects with other tools such as MaxEnt (maximum entropy) methods used in NLP and Markov Chain Monte Carlo (MCMC) sampling. We go back to the original article by Metropolis et al. on using random sampling methods to estimate the mean properties of materials at equilibrium. This allows us to introduce the Boltzmann distribution and discuss its relationship to the exponential distribution and maximum entropy justifications for using Poisson process models. We then hint at the likelihood ratio generalization by Hastings and the ultimate co-opting of these methods for optimization later by Kirkpatrick et al.

Whiteboard notes for this lecture can be found at:

https://www.dropbox.com/s/gqij9e21xf3cke2/IEE598-Lecture5A-Notes.pdf?dl=0

Lecture 4B: Niching Methods for Multi-modal Optimization [audio only] (2020-02-19)

In this lecture (which unfortunately does not have a video captured due to technical problems in the room), we cover several different niching methods that evolutionary (population-based) multi-modal optimization techniques use to stabilize populations across all of the different peaks of an optimization function. We motivate why peak finding is a potentially useful optimization objective and describe how each approach (which are primarily designed to integrate into genetic algorithms but could be used in other evolutionary algorithms) differs not only in its performance but its computational cost. Ultimately, we would like to distribute very many individuals across the many peaks, which means that we seek algorithms that scale manageably as we scale up the number of individuals. By the end of the lecture, restricted tournament selection (RTS) is discussed as being very useful in multi-modal optimization both in terms of its good performance and hyperparameters that allow for trading off speed and accuracy.

Whiteboard notes for this lecture can be found at:

https://www.dropbox.com/s/ff2ptyupyd0nxpz/IEE598-Lecture4B-Notes.pdf?dl=0

Lecture 4A: From Multiobjective Genetic Algorithms to DGA, PGA, and Multimodal Optimization (2020-02-17)

In this lecture, we move from talking about multi-objective genetic algorithms to distributed and parallel genetic algorithms. The discussion of distributed genetic algorithms (DGA) as a metapopulation shows us how, in principle, small populations undergoing evolutionary processes can collectively move through "adaptive valleys" to explore much better than a monolithic population. This idea that distributed subpopulations that each make use of genetic drift as a mechanism for exploration is precisely the shifting-balance theory of Sewall Wright, a theory which has not been extremely useful in biology but may be a perfect fit for evolutionary computing in a distributed setting. We then discuss how our insights from multiobjective and distributed GA's can be used to reinvigorate approaches for single-objective, single-processor GA's and so-called "multimodal optimization" (which will be described in the next lecture).

Whiteboard notes for this lecture can be found at:

https://www.dropbox.com/s/0c07tnsz8zc1hj5/IEE598-Lecture4A-Notes.pdf?dl=0

Lecture 3C: Multi-Objective Genetic Algorithms (MOGA and Friends), Part 2 (2020-02-12)

In this lecture, we expand upon the first two classes of multi-objective genetic algorithms (i.e., those based on random weights and those based on alternating fitness objectives) and add the third and most modern class of approaches – Pareto-ranking approaches. After reviewing the first two classes, we discuss how a new "fitness" can be used that represents how many other solutions a focal solution dominates. By selecting according to this fitness, solutions are driven toward a Pareto frontier without collapsing to any particular region of that frontier. To further improve diversity, "fitness sharing" is introduced. We close with a brief introduction to distributed GA's and multi-modal optimization and hint at a connection to Sewall Wright's "shifting-balance theory" from population genetics.

Whiteboard notes for this lecture can be found at:

https://www.dropbox.com/s/8dn24mzkx0wedoj/IEE598-Lecture3C-Notes.pdf?dl=0

Lecture 3B: Multi-Objective Genetic Algorithms (MOGA and Friends), Part 1 (2020-02-10)

This lecture briefly re-introduces the Pareto-efficient set and Pareto frontier and then describes different early GA-inspired approaches to find the Pareto-efficient set among a set of conflicting objectives. The key conceptual framework used throughout the lecture is that of a "community" of organisms, selected to live in similar environments, that inhabit different regions of niche space. The entire continuum of niche space is the Pareto frontier, and particular solutions along the frontier (different ways in which objectives can be balanced against each other) are like different species living in the community of optimizers that balance objectives differently.

This lecture also includes some comments about population size and its effect on evolution as well as how phenotypic variance can enhance evolvability.

Whiteboard notes for this lecture can be found at:

https://www.dropbox.com/s/wij2wrv9i7b0451/IEE598-Lecture3B-Notes.pdf?dl=0

Lecture 3A: Introduction to Multi-criteria Decision Making and Pareto Optimality (2020-02-05)

In this lecture, we introduce the general topic of multi-criteria decision making and, more specifically, multi-objective optimization. The lecture starts with a discussion of Nash optimality (and Variational Inequalities), as formulated for the continuous variable case. We then conclude with an introduction of Pareto-efficient sets and Pareto optimality and how these set-based approaches may be more practically superior to more traditional point-based optimization approaches. This lecture sets up the background we will use in upcoming lectures to build evolutionary algorithms for discovering Pareto-efficient sets.

The whiteboard notes for this lecture can be found at:
https://www.dropbox.com/s/opseeleih8aakfk/IEE598-Lecture3A-Notes.pdf?dl=0

Lecture 2B: GA Approaches Beyond Optimization - Evolutionary Programming (2020-02-03)

In this lecture, we continue to describe applications outside of typical numerical optimization that have been greatly influenced by the field of evolutionary computing. We focus here on evolutionary programming (in general) and genetic programming (specifically).

The whiteboard for this lecture was captured in PDF form at: https://www.dropbox.com/s/5b4vqjms9196z2o/IEE598-Lecture2B-Notes.pdf?dl=0