Lecture 3B (2025-02-20): Multi-Objective Genetic Algorithms: Weight/Vector-Based Approaches

In this lecture, we review the Pareto perspective of multi-objective optimization, emphasizing Pareto efficiency and the Pareto front. We draw connections to a blend of population genetics/evolution as well as community ecology (related to niche spaces and co-existence). We introduce Age–Fitness Pareto Optimization (AFPO) as a motivational example, as it uses the diversity preserving aspects of multi-objective optimization to improve the evolvability of single-objective metaheuristics used in evolutionary robotics (although note that in the video, it is said that AFPO maximizes age/generations, but it actually minimizes age/generations; this is fixed in the notes linked below). From there, we describe several classical multi-objective genetic algorithm approaches that either explicitly incorporate weighted combinations of objectives or instead create sub-populations for different objectives and blend individuals from those subpopulations. This motivates the idea of Pareto ranking (a  more modern approach to multi-objective evolutionary algorithms), which we will introduce (along with other diversity-preserving and diversity-enhancing mechanisms) next time.

Whiteboard notes for this lecture can be found at:
https://www.dropbox.com/scl/fi/nwfytnxrlmqzvdoftdqtc/IEE598-Lecture3B-2025-02-20-Multi_Objective_Genetic_Algorithms-From_Weight_Based_Approaches_to_Pareto_Ranking-Notes.pdf?rlkey=pq81xpd5abfgikq6twsj73yys&dl=0

Lecture 3A (2025-02-18): Multi-Criteria Decision Making, Pareto Optimality, and an Introduction to Multi-Objective Evolutionary Algorithms (MOEA's)

In this lecture, we introduce multi-objective optimization as a subset of multi-criteria decision making, and we use a game-theoretic example to motivate the discussion (as game theory is a subset of multi-objective optimization). We define the Nash equilibrium concept and draw connections to multi-agent reinforcement learning. That then lets us pivot to other solution concepts for more general multi-objective problems, such as the knapsack problem. We discuss weighting/scalarization approaches (both convex combinations and Chebyshev scalarization), satisficing approaches (common in dynamic programming examples), and target approaches, and we highlight that each of these still has a subjective degree of freedom remaining. We then motivate Pareto-efficient sets and the Pareto frontier, which is an approach that minimizes all subjectivity by producing a set of possible outcomes (instead of a single "optimal" solution). We then close by introducing multi-objective evolutionary algorithms, whose population structure is naturally suited to solving for (samples of) set-based optima.

Whiteboard notes for this lecture can be found at:
https://www.dropbox.com/scl/fi/lpb8i4mp93iegdjyccly2/IEE598-Lecture3A-2025-02-18-Multi_Criteria_Decision_Making_Pareto_Optimality_and_Intro_to_Multi_Objective_Evolutionary_Algorithms-Notes.pdf?rlkey=hef5n0e77k3k7i0zqwg8cn0cs&dl=0

Lecture 2C (2025-02-13): Immunocomputing: Genetic Approaches for Diverse Solution Portfolio

In this lecture, we introduce the field of "Immunocomputing", which studies information-processing mechanisms within the vertebrate immune system that help to maintain a diverse array of solutions to detecting and handling threats. Such dynamical systems must be have low false negative rates (i.e., detect as many threats as possible) while also having low false positive rates (i.e., avoid classifying artifacts of normal operations as being anomalous). We discuss the innate immune system, which is a highly conserved immune system to respond to general threats, and the adaptive/acquired immune system, which has immunological memory of past threats that it can use to deploy highly specific responses to those threats if found in the future. Particularly this second system has inspired Artificial Immune Systems (AIS), including negative selection (inspired by "central tolerance" in the thymus) and clonal selection. Both of these two algorithmic approaches form and maintain a diverse portfolio of threat/anomaly classifiers as opposed to clustering around a single good solution, as is often the case in Genetic Algorithms. This sets us up for our next unit on multi-criteria decision making, and so we close with a basic introduction to game theory/multi-objective optimization and Nash equilibria. We will introduce Pareto equilibria in the next lecture.

Whiteboard notes for this lecture can be found at:
https://www.dropbox.com/scl/fi/ha6oe1rjwyzbwhnp4nsds/IEE598-Lecture2C-2025-02-13-Immunocomputing-Genetic_Approaches_for_Diverse_Solution_Portfolios-Notes.pdf?rlkey=qsljjcwafo03vrtoyc9u7de5d&dl=0

Lecture 2B (2025-02-11): Genetic Programming, Immunocomputing, and Artificial Immune Systems

In this lecture, we introduce Genetic Programming as an alternative to Evolutionary Programming that also is able to leverage the power of crossover (and thus the full Genetic Algorithm) when evolving executable structures, such as program code or decision trees. We start with a discussion of Linear Genetic Programming (LGP) on register-based languages (like assembly language) that can be represented as simple sequences of instructions. We then pivot to discuss tree-based Genetic Programming (GP) that operate on Abstract Syntax Tree (ASTs) representations of more traditional programming code (e.g., Python, C++, etc.). We discuss how crossover is implemented in these AST, and we identify several applications such as genprog which uses GP to do automated software repair and optimization. This sets us up to introduce immunocomputing in the next lecture (which we were unable to get to due to time constraints today) which will show how genetical methods from the immune system can be used to generate and maintain useful diversity for applications such as cyber-security and general anomaly detection.

Whiteboard notes for this lecture are available at:
https://www.dropbox.com/scl/fi/nonw19ergjmkk1vn3pf9g/IEE598-Lecture2B-2025-02-11-Genetic_Programming_Immunocomputing_and_Artificial_Immune_Systems-Notes.pdf?rlkey=bgt9guyhvu5qi79jnshxwycxa&dl=0

Lecture 2A (2025-02-06): Evolutionary Computing from Optimization to Programming (Mutation, CMA-ES, and Evolutionary Programming)

In this lecture, we transition from the Genetic Algorithm to alternative approaches in Evolutionary Computing, particularly Evolutionary Strategies and Evolutionary Programming. We start by highlighting that the Genetic Algorithm's typical mutation operators are a bit crude in that they use the same mutation policy for every decision variable. Motivated by this, we introduce Evolution Strategies, which are alternative approaches that allow for different mutation rates along different dimensions of the decision space. This lets us introduce the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), which is a popular global optimization approach that approximates the fitness objective with a multivariate normal sampling distribution. We then transition to more creative directions by showing how Evolutionary Programming, which removes crossover, allows for the evolution of Finite State Machines (FSM's) which are equivalent to computer programs that are automatically designed for a desired function. Next time, we will introduce Genetic Programming, which allows for evolving code directly using a more traditional GA (with crossover), and then we will transition to Immunocomputing, another genetically inspired approach to automated creativity.

Whiteboard notes for this lecture can be found at:
https://www.dropbox.com/scl/fi/cunoa5zqvx29uj3pm2n8j/IEE598-Lecture2A-2025-02-06-Evolutionary_Computing_from_Optimization_to_Programming-Notes.pdf?rlkey=tpqz2o3u36obp28xf4ipw7se2&dl=0

Lecture 1F (2025-02-04): GA Wrap Up – Options for Selection, Crossover, Mutation, and Extensions

In this lecture, we wrap up our discussion of the basic Genetic Algorithm (GA) and its hyper-parameters. We focusing on differences in implementation of the population structure as well as different genetic operators for selection and recombination and mutation (although we will have to finish the last few bits of our mutation discussion in the next lecture).  Throughout the lecture, we emphasize the different roles for selection (and selective pressure), genetic drift, mutation, and even migration to some extent. This emphasizes the "evolution in a drift field" diagram that we introduced several lectures ago. Too much selective pressure can lead to premature convergence on local suboptima, and too little selective pressure can lead to solutions favored randomly due to genetic drift. Too much mutation can eliminate the possibility of fine-tuning solutions, and too little mutation is not enough of a guard against drift and selection purging all diversity from the population. Dynamically altering some of these parameters during the execution of a GA can provide a compromise among these tradeoffs.

Whiteboard notes for this lecture can be found at:
https://www.dropbox.com/scl/fi/y3r7mum9hjcnr7elh4eww/IEE598-Lecture1F-2025-02-04-GA_Wrap_Up-Options_for_Selection_Crossover_Mutation_and_Extensions-Notes.pdf?rlkey=1uekaz5jwug5467yng4jlxgdi&dl=0

Lecture 1E (2024-01-30): The Basic Genetic Algorithm and Its Implementation

In this lecture, we reveal the basic architecture of the simple GA. We then start to introduce three common selection operators (fitness-proportionate selection, ranking selection, and tournament selection), crossover operators, and mutation operators, which we will finish in the next lecture. Throughout this lecture, the basic tension between natural/artificial selection and drift is emphasized -- there is a downside to having selection operators that have high selection pressure (because they get stuck in suboptimal traps), but very low selection pressure can cause small populations to stagnate due to drift.

Whiteboard notes for this lecture can be found at:
https://www.dropbox.com/scl/fi/wbvlvpj1wkft5903pg1ad/IEE598-Lecture1E-2024-01-30-The_Basic_Genetic_Algorithm_and_Its_Implementation-Notes.pdf?rlkey=x81e1h1lv42vkwt8lphcr7uqr&dl=0

Lecture 1D (2025-01-28): The Four Forces of Evolution and The Drift Barrier

In this lecture, we review the four forces of evolution -- mutation, migration/gene flow, genetic drift, and natural selection -- and the contribution that each one makes to either increasing or decreasing variance in a population over time. So a more complete picture of evolution is a tense combination of these forces, each of them leading to different kinds of effects on the distribution of alleles (strategies) in a population. We discuss how the tendency for natural selection to produce higher quality solutions is ultimately limited by genetic drift that dominates when populations have low fitness diversity (low selective pressure), and we discuss how this sets up a speed–accuracy tradeoff between mutation (which counteracts drift in a way  that does not require more time for convergence but makes it impossible to fine tune solutions) and population size (which can fine tune solutions but requires a longer time to converge to a good solution). Selection operators and evolutionary hyper-parameters should be chosen with these pressures and tradeoffs in mind.

Whiteboard notes for this lecture are archived at:
https://www.dropbox.com/scl/fi/09u3vd7l3m9h68pc5uyr9/IEE598-Lecture1D-2024-01-28-The_Four_Forces_of_Evolution_and_The_Drift_Barrier-Notes.pdf?rlkey=u4id8rcd9ou45og4eqxx5fu38&dl=0

Lecture 1C (2025-01-21): Population Genetics of Evolutionary Algorithms

In this lecture, we review the fundamentals of evolutionary (population-based) metaheuristic optimization algorithms (for engineering design optimization, EDO). This allows us to introduce the evolutionary notions of selective pressure and drift, two forces that independently drive changes in the frequency of strategies in populations over generations. Before getting into the concrete details of the basic Genetic Algorithm (GA) next time, we used the rest of this lecture to introduce terminology from evolutionary biology and population genetics in life sciences. These terms (chromosomes, genes, alleles, phenotype, characters, traits, fitness) will often be used in discussions of evolutionary algorithms (EA) as well, and so it is useful to have some background in them.

Whiteboard notes for this lecture can be found at:
https://www.dropbox.com/scl/fi/0v7cr220534e0fsivf803/IEE598-Lecture1C-2024-01-21-Population_Genetics_of_Evolutionary_Algorithms-Notes.pdf?rlkey=o87azad7gjivlbd1ylgzt8s26&dl=0

Lecture 1B (2025-01-16): Evolutionary Approach to Engineering Design Optimization

In this lecture, we formally introduce the Engineering Design Optimization (EDO) problem and several application spaces where it may apply. We then discuss classical approaches for using computational methods to solve this difficult optimization problem -- including both gradient-based and direct search methods. This allows us to introduce trajectory and local search methods (like tabu search and simulated annealing) and population-based methods (like the genetic algorithm, ant colony optimization, and particle swarm optimization). We then start down the path of exploring evolutionary algorithms, a special (but very large) set of population-based methods. In the next lecture, we will connect this discussion to population genetics and a basic Genetic Algorithm (GA).

The whiteboard notes taken during this lecture can be found at:
https://www.dropbox.com/scl/fi/ifkopelwknhhbj0wuz8ws/IEE598-Lecture1B-2024-01-16-Evolutionary_Approach_to_Engineering_Design_Optimization.pdf?rlkey=3xdr40xw5qjz62uqzrd373hh6&dl=0

Lecture 1A (2025-01-14): Introduction to the Course, Its Policies, and Its Motivation

In this first lecture of the semester, I introduce the course and its expectations and policies. After highlighting several sections of the syllabus, we pivot to discussing heuristics, metaheuristics, and hyperheuristics more broadly. This sets up for the next lecture which will introduce Evolutionary Algorithms, for use as metaheuristics.

The whiteboard notes for this lecture can be found at:
https://www.dropbox.com/scl/fi/7ojfu7w0d58yhsb2zfhjb/IEE598-Lecture1A-2025-01-14-Introduction_to_Course_Policiesi_and_Motivations-Notes.pdf?rlkey=uw6va7dybspd2cvqtq1bui5f6&dl=0