Lecture 1E (2022-01-25): The Genetic Algorithm and its Implementation, Part 2

In this lecture, we reveal the basic architecture of the simple GA. We then introduce three common selection operators (fitness-proportionate selection, ranking selection, and tournament selection). We then start to discuss crossover operators; we will finish with mutation operators 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/s/vobploq2iclraln/IEE598-Lecture1E-2022-01-25-The_Genetic_Algorithm_and_its_Implementation-Part_2.pdf?dl=0

Lecture 1D (2022-01-20): The Genetic Algorithm and its Implementation, Part 1

In this lecture, we review the two major evolutionary forces of natural selection and genetic drift and how they tend to reduce variance in a population over time. We then introduce mutation and recombination, which add diversity to populations. 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. This allows us to introduce a concrete example of an evolutionary algorithm -- the genetic algorithm (GA). We start to define its key components and sequence of operation. In Part 2 (the next lecture), we will go into detail about the selection, mutation, and recombination "genetic operators."

Whiteboard notes for this lecture are archived at: https://www.dropbox.com/s/arz17hcpiw4wacy/IEE598-Lecture1D-2022-01-20-The_Genetic_Algorithm_and_its_Implementation-Part_1.pdf?dl=0

Lecture 1C (2022-01-18): 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/s/9z2lc4y0om6kwxy/IEE598-Lecture1C-2022-01-18-Population_Genetics_of_Evolutionary_Algorithms.pdf?dl=0

Lecture 1B (2022-01-13): The 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/s/st88vx87y6tv0xo/IEE598-Lecture1B-2022-01-13-The_Evolutionary_Approach_to_Engineering_Design_Optimization.pdf?dl=0

Lecture 1A (2022-01-11): Introduction to Course, Metaheuristics, and Evolutionary Algorithms

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/s/n1nrlk9k38tlgcx/IEE598-Lecture1A-2022-01-11-Introduction_to_Course_Metaheuristics_EA-Notes.pdf?dl=0

Lecture 8C: Elementary Cellular Automata, Stochastic Cellular Automata, Ising models, and Cellular Evolutionary Algorithms (2020-04-29)

In this lecture, we close out the semester's technical content with some final words about cellular automata (CA) and interacting particle systems (IPS). We keep the focus from the previous lecture on Elementary CA's (ECA's), reminding of the naming convention and a mention of some popular rules (such as rule 30, rule 110, rule 184, rule 232). We then pivot to stochastic/probabilistic CA's, with a focus on 1-D stochastic ECA and show how probabilistic rules do not only generate "fuzzy patterns." This allowed us to talk about Ising models and physical/hardware implementations of annealing machines for high-speed combinatorial optimization by metaheuristics. That closes some of the loop between the end of this class and earlier in the class. To fully close that loop, we close with an introduction to Cellular Evolutionary Algorithms (cEA's), which define genetic operators on spatially defined neighborhoods in a way clearly inspired by CA's (and these evolutionary algorithms can certainly be viewed as a kind of CA).

Whiteboard notes for this lecture can be found at:
https://www.dropbox.com/s/iwrwe59u5xt2y0v/IEE598-Lecture8C-Notes.pdf?dl=0

Lecture 8B: Elementary Cellular Automata, Computation, and Experimentation (2020-04-27)

In this lecture, we continue discussing Interacting Particle Systems (IPS) and complex systems approaches for understanding adaptive properties of distributed systems, such as neural networks. We specifically focus on cellular automata (CA), starting with 2D cases (such as models of fire spread, the Game of Life, and "Brian's Brain" from NetLogo) and then moving to Elementary Cellular Automata (ECA). We discuss some popular ECA rules, such as the traffic rule (184) and the majority rule (rule 232) and how they can be combined to do density classification. We also discuss how rule 110 is Turing complete and thus can do much more.

Whiteboard notes for this lecture can be found at:

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