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