Lecture 5B (2022-02-24): From MaxEnt Methods to MCMC Sampling

In this lecture, we continue our discussion of computational/numerical methods inspired by statistical mechanics (i.e., physics). We start with a reminder of our ultimate goal to develop a method of simulated annealing that can be used as an optimization metaheuristic. That brings us back to entropy, where we ended last time, and lets us introduce maximum entropy (MaxEnt) methods. Maximum Entropy distributions are used in a wide variety of application areas (consider uniform distributions, exponential distributions, and normal distributions), and "MaxEnt methods" became popularized as a tool by computer scientists working in Natural Language Processing (NLP) and are now popular in archaeology and ecology (among other places). Equipped with an understanding of entropy and maximum-entropy distributions, we move on to discussing the Boltzmann distribution across microstates and how it relates to the exponential distribution (over energy). This lets us setup a likelihood ratio that will be at the core of the "Metropolis algorithm" for MCMC sampling to solve numerical integration problems (i.e., to solve high-dimensional "equations of state" in physical chemistry). We will pick up with MCMC and the Metropolis algorithm next time and then swing through Metropolis–Hastings and eventually reach Simulated Annealing (SA).

Whiteboard notes for this lecture can be found at: https://www.dropbox.com/s/mrpmqd6msvvycml/IEE598-Lecture5B-2022-02-24-From_MaxEnt_Methods_to_MCMC_Sampling.pdf?dl=0

Lecture 5A (2022-02-22): Introduction to Simulated Annealing and Maximum Entropy (MaxEnt) Methods

In this lecture, we introduce the optimization metaheuristic "Simulated Annealing" (SA) and setup the fundamentals required to understand its operation, which provides an opportunity to also introduce Maximum Entropy (MaxEnt) methods.

Whiteboard notes for this lecture can be found at: https://www.dropbox.com/s/heq7t98n0w4d18p/IEE598-Lecture5A-2022-02-22-Introduction_to_Simulated_Annealing.pdf?dl=0

Lecture 4B (2022-02-17): Niching Methods for Multimodal Optimization

This lecture concludes our coverage of genetic algorithms for multi-modal optimization, with a particular focus on niche-preserving methods within multi-modal genetic algorithms. We cover generalized fitness sharing approaches, clearing approaches, clustering approaches, crowding and tournament selection approaches (including restricted tournament selection, RTS), as well as conservation based approaches (like the species preserving GA, SPGA). Each of these methods helps to maximize diversity over large scales in genotypic space while still providing optimization/selective pressure at smaller scales -- providing both exploration and exploitation. They are inspired by ideas from conservation biology and community ecology, with some approaches borrowing from machine learning (as in K-means clustering).

Whiteboard lecture notes for this lecture can be found at: https://www.dropbox.com/s/kemycgsjb0t2hoc/IEE598-Lecture4B-2022-02-17-Niching_Methods_for_Multimodal_Optimization.pdf?dl=0

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

Finishing off our discussion of multi-objective optimization in evolutionary algorithms, we review Pareto ranking approaches and how they differ in selective pressure and how to use "fitness scaling" to tune that selective pressure. Selective pressure must be controlled in multi-objective genetic algorithms (MOGA's) to prevent significant loss of diversity while the set of candidate solutions moves toward the frontier. We then revisit fitness sharing and clearing approaches that help increase diversity (not just maintain it) along the frontier.

This gives us an opportunity to pivot back to the one-objective case to discuss possible enhancements based on lessons learned in the multi-objective case. We start by discussing parallel GA (PGA) in contrast with distributed GA (DGA). In the latter case, the population is split among multiple "demes" that have infrequent (but guaranteed) migration among them. We discuss how metapopulation effects increase the role of drift in each subpopulation, which leads to a new source of novel variation (aside from mutation). This effect is closely tied to the "shifting-balance theory" of Sewall Wright (from population genetics). This strength allows DGA to out-perform (in terms of finding global optima) simpler GA architectures (even PGA). 

We then turn back to single-objective optimization on a single processor and introduce multi-modal optimization -- where the goal is to find all local optima (including the global optima) instead of only the global optima. This is a sort of "peak finder" for optimization objectives. A good multi-modal optimizer will need to maintain diversity using mechanisms similar to those used in multi-objective optimization, where now each "niche" will correspond to a different local peak as opposed to a different tradeoff among multiple objectives. We will go into multi-modal optimization techniques in the next lecture.

Whiteboard notes for this lecture can be found at: https://www.dropbox.com/s/xuij7chgk4axqoe/IEE598-Lecture4A-2022-02-10-From_Multiobj_Genetic_Algorithms_to_DGA_PGA_and_Multimodal_Opt.pdf?dl=0

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

In this lecture, we finish our introduction to multi-objective genetic algorithms (MOGA) by reviewing weighted sum approaches (like RWGA), alternating objective approaches (like VEGA), and then introducing Pareto-ranking approaches (like MOGA and NSGA-2). We discuss how Pareto-ranking approaches use a ranking selection approach where fitness is tied to how many other solutions either dominate the focal solution or are dominated by it. That also allows us to introduce basic fitness sharing (which will be revisited as we move forward to discuss multi-modal optimization in the next section). Whereas Pareto ranking ensures population movement toward the Pareto frontier, fitness sharing (and related measures) help ensure movement along the frontier to sample a larger fraction of it in the terminal population.

Whiteboard notes for this lecture can be found at: https://www.dropbox.com/s/2tvix28ylq9gmiw/IEE598-Lecture3C-2022-02-10-MultiObjective_Genetic_Algorithms_MOGA_and_Friends-Part_2.pdf?dl=0

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

In this lecture, we continue to discuss multi-criteria decision making (specifically multi-objective optimization), with a shift in focus from the "Nash equilibrium" solution concept to the "Pareto equilibrium" concept. We define the "Pareto efficient set" as well as the "Pareto frontier" (and synonyms to these -- "Pareto optimal", etc.). The fundamental concept underlying Pareto efficiency is the so-called "Pareto movement", which is a topic we describe as a different way of finding decision vectors to EXCLUDE in a decision-making problem (leaving only the efficient solutions left over for the subjective consideration of a decision maker). We then pivot to describing multi-objective genetic algorithms that can be used to find the Pareto frontier/Pareto-efficient set. These algorithms adjust the notion of fitness or selection to help maintain diversity while moving a population of candidate solutions closer and closer to the Pareto frontier. Our discussion stops after introducing weighted sum methods. We will start next time with randomly weighted genetic algorithms, heading toward more modern MOGA and Pareto ranking.

Whiteboard notes for this lecture can be found at: https://www.dropbox.com/s/uxitg4gddq99dys/IEE598-Lecture3B-2022-02-08-MultiObjective_Genetic_Algorithms_MOGA_and_Friends-Part_1.pdf?dl=0

Lecture 3A (2022-02-03): Genetic Programming and Intro. to Multi-criteria Decision-making and Pareto Optimality

In this lecture, we wrap up our brief discussion of evolutionary and genetic programming, with examples going from evolving finite state machines (FSMs) to evolving abstract syntax trees (ASTs) to medical decision trees, with a few comments about genetic programming (GP, GenProg) using One Instruction Set Computer (OISC) languages. We then pivot to introducing multi-criteria decision making (MCDM), with our initial focus on the Nash equilibrium solution concept (at least in continuous games). We will introduce another important solution concept -- Pareto optimality -- starting in the next lecture.

Whiteboard notes for this lecture can be found at: https://www.dropbox.com/s/iqhma6rxgrlphqw/IEE598-Lecture3A-2022-02-03-GenProg_and_Intro_to_MCDM_and_Pareto_Optimality.pdf?dl=0

Lecture 2B (2022-02-01): GA Approaches Beyond Optimization - AIS and Intro to Evolutionary Programming

In this lecture, we complete our introduction to Artificial Immune Systems (AIS), including both negative selection (central tolerance inspired) and clonal selection. We discuss applications in cybersecurity and anomaly detection in industrial spaces. We close with a brief introduction to evolutionary programming, which we will pick up next time.

Whiteboard lecture notes can be found at: https://www.dropbox.com/s/97zvo3s2gbovyss/IEE598-Lecture2B-2022-02-01-Beyond_Genetic_Optimization-AIS_and_GenProg.pdf?dl=0