In this lecture, we review Elementary Cellular Automata (ECA's) and some classic rules and how to interpret them. We then transition to a brief discussion of hardware-based cellular automata for things like the Ising model, which allows for hardware-based annealing machines that perform simulated annealing (SA) optimization very fast. That lets us transition to discussing stochastic CA's (SCA) and then conclude with an introduction to cellular evolutionary algorithms (cEA's) which put different selective pressures on the population based on the distribution of the individuals in a space (where CA-like neighborhoods define the subpopulations on which a GA is to act, as if the GA was the CA update rule). That concludes the class for Spring 2022.
In this lecture, we move on from generic Interacting Particle Systems (IPS) to the specific case of (deterministic) Cellular Automata (CA). We spend a lot of time on Elementary CA's (ECA) and the complex behaviors that they can generate, as cataloged by Wolfram's _A New Kind of Science_ (NKS). We discuss density classification, pattern recognition, and the mapping from CA's to (recurrent) neural networks (RNNs/ANNs). By showing that certain ECA rules (like "Rule 110" in particular) are Turing complete, we effectively show that Recurrent Neural Networks/Time Delay Neural Networks (TDNNs) are themselves Turing complete (i.e., they can execute any computable function). We also discuss a few basic 2D CA's. Throughout the lecture, NetLogo (Web) is used to demonstrate the CA's, which allows us to introduce agent-based modeling a bit (including a Particle Swarm Optimization (PSO) empirical example).
In this lecture, we introduce a short unit on complex systems approaches that intersect with computation and algorithms. We start with Interacting Particle Systems (IPS), which are a class of mathematical models describing systems that interact based on location or contact with each other. There are "Self-Organizing Particle Systems (SOPS)" that describe hypothetical agents that might be designed to build or maintain structures in engineered systems. Or there are more generic IPS models meant to understand phenomena in population dynamics or community ecology. We focus on the "Voter Model", which can be viewed as a model of consensus in agents that randomly trade opinions or (equivalently) fixation in evolutionary systems that are not under selection. We analyze the Voter Model as a non-ergodic Markov chain with absorbing states and then show how a dual process that represents a sort of "contact tracing" of consensus backward in time is ergodic and can thus be analyzed with a suite of mathematical tools. One of those tools helps us prove the possibly counterintuitive result that when the voter model operates in fewer than two dimensions, it will reach consensus/fixation with probability one but will have non-zero probability of never reaching consensus/fixation in three or more dimensions. Thus, the dimensionality of the (translation invariant) neighborhoods matters. We then prepare for our next lecture, where we'll introduce Cellular Automata (CA), a deterministic interacting particle system that nevertheless can produce fascinating patterns that help demonstrate how computation can be embodied in space.
This 20-minute segment provides an overview of the format and expectations for the final exam for the Spring 2022 section of IEE/CSE 598 (Bio-Inspired AI and Optimization). It also covers questions about the final project.
In this lecture, we continue our discussion of neuromorphic engineering, with a focus on spiking neural network (SNN) architectures. We review the basic dynamics of an "action potential" and mention a few ODE models (Hodgkin–Huxley, integrate-and-fire, etc.) of such dynamics. Modern SNN platforms, such as SpiNNaker and more modern IBM TrueNorth and Intel Loihi hardware/"chip" solutions, implement hardware and software emulations of these dynamics in an effort to simulate large networks of spiking neurons (as opposed to mathematical abstractions, as in more traditional ANNs). We also discuss "neuromemristive" platforms that make use of hysteretic "memristors" as very simple artificial spiking neurons and mention an example from Boyn et al. (2017, Nature Communications) of a crossbar architecture of such memristors that can accomplish unsupervised learning for pattern recognition/classification. We then move on to discussing how backpropagation (gradient descent) can now be used for supervised learning on spiking neural networks (to simplify training significantly). That brings us to discuss state-of-the-art and beyond-state-of-the-art nature-inspired directions, such as using neural network "sleep" to improve continual learning and introducing "neuromodulation" to add further richness to artificial neural networks.
This lecture starts with a basic psychological and neurophysiological introduction to learning -- non-associative and associative. Most of the focus is on associative learning, broken into classical conditioning (Pavlov) and operant conditioning (Skinner). Psychology–Machine-Learning Analogies are made between classical conditioning and unsupervised learning as well as between operant conditioning and supervised and reinforcement learning. In principle, with the right hardware, a mechanism for associative learning can underly all other learning frameworks within machine learning. With that in mind, spike-timing-dependent plasticity (STDP) is introduced as a neuronal mechanism for associative learning. In particular, we introduce Hebbian learning ("fire together, wire together") in the spiking sense and then conceptualize it in the neuronal weights case (going from temporal coding to spatial/value coding). We then discuss a simple unsupervised pattern recognition/classification example using Hebbian updating on the weights. We then pivot to introducing true spiking neural networks (SNNs) and modern versions, such as SpiNNaker, IBM TrueNorth, and Intel Loihi. Next time, we will end our unit on Artificial Neural Networks/Spiking Neural Networks with a discussion of an example of an analog SNN (built with memristors) that does unsupervised pattern recognition as well as some more advanced directions with SNNs.
In this lecture, we introduce applications of ANN outside of conventional supervised learning. In particular, we briefly discuss reinforcement learning (RL and "deep Q-learning") and then introduce unsupervised learning. As examples of unsupervised learning, we discuss clustering, autoencoders, and multidimensional scaling (MDS). We end with a brief introduction to Hebbian/associative learning, which will be picked up next time as we start talking about spiking neural networks (and spike-timing-dependent plasticity, STDP).
This lecture continues our introduction of Recurrent Neural Networks (RNNs), starting with a quick refresher on time-delay neural networks (TDNNs). From TDNNs, we discuss basic RNNs and then a process of backpropagation through time (BPTT) that can (in principle) be used to train RNN's in supervised learning tasks. We then discuss how Long Short Term Memory (LSTM) is a regularized RNN structure that is easier to train and has been very successful in many domains, such as Natural Language Processing (NLP). We then pivot to discussing another regularized RNN, the Echo State Machine/Reservoir Machine. Reservoir computing builds a randomized RNN as a kind of encoder that converts temporal signals to spatiotemporal representations that can then be treated as features for an input to a simple feed-forward, single-layer neural network decoder. We then close our discussion of supervised learning with a discussion of training methodology (train, validate, and test) and then open a discussion of reinforcement and unsupervised learning that we will continue next time.
In this lecture, we complete our discussion of how backpropagation allows for gradient descent to train deep neural networks (feed-forward, multi-layer perceptrons in general). We then pivot to talking about more regularized feed-forward neural networks, like convolutional neural networks (CNNs) that combine convolutional layers with pooling layers and thereby simplify training while producing a low-dimensional feature set (relative to the dimensions of the input). After a brief discussion of the feed-forward architecture of the insect/pancrustacean brain, we shift to discussing time-delay neural networks (TDNNs) as an entry point into discussing recurrent neural networks (RNNs) and reservoir machines, which we will pick up on next time.
In this lecture, we start our discussion by transitioning from thinking about a Radial Basis Function Neural Network as a kind of modification of a single neuron/perceptron (for better separability) to a whole neural network itself, with input, hidden (latent variable), and output layers. That lets us introduce Universal Approximation Theorems (UAT), like the one from Cybenko that say that virtually any function can be approximated by a neural network with an (arbitrarily large) single hidden layer so long as the activation functions are non-polynomial. We use the elusiveness of finding such a hypothetical neural network to motivate a more pragmatic "deep" architecture (i.e., with more than 1 hidden layer) with simpler activation functions that are more amenable to generic training approaches. That lets us introduce the Multi-Layer Perceptron (MLP) feed-forward neural network and the corresponding backpropagation method (gradient descent) used to optimize it relative to a differentiable (sum-of-squares in this case) loss function. Backpropagation is basically the "chain rule" unrolled over a neural network, allowing for errors in supervised learning to be "propagated backwards" to update gradients and then new values (after a gradient-descent step) to propagate forwards to calculate the new errors (starting the process again). We will pick up on backpropagation in the next lecture (and introduce CNN's and other architectures, some of which will not be purely feed forward).
In this lecture, we continue to discuss the basic artificial neuron as a generalized linear model for statistical inference. We start with the problem of binary classification from a (single-layer) perceptron (SLP), which can use a threshold activation function to accurately predict membership among two classes so long as those classes are linearly separable. In the lecture, we introduce the geometric interpretation of the classification process as thresholding the level of agreement between the neural-network weight vector and the feature vector. From there, we consider radial basis function neural networks (RBFNN's) which transform the feature space to allow for more sophisticated inferences (e.g., classification for problems that are not linearly separable, function approximation, time-series prediction, etc.). The RBFNN is our first example of a single-hidden-layer neural network, which is our entry point to multi-layer perceptrons (MLP's) that we will discuss next time.
In this lecture, we introduce artificial neural networks (ANN's) and the neurobiological foundations that inspired them. We start with a description of the multipolar neuron, with many synapses and one axon, and focus on chemical synapses between axons and dendrites. We cover resting potential, synaptic potentials, and (traveling/propagating) action potentials. We then transition to the simple artificial neuron model (the basis of modern ANN's) as a function of a weighted sum of inputs and a bias term. The artificial neuron is portrayed as an alternative representation of generalized linear modeling (GLM) from statistics, with the activation function playing a similar role to the link function in GLM. We then discuss several common activation functions -- Heaviside (threshold), linear, rectified linear (ReLU), logistic (sinusoid), and hyberbolic tangent (tanh). We will pick up next time seeing how the single artificial neuron can be used for binary classification in linearly separable feature spaces, with a geometric interpretation of the weight vector as a line separating two classes of feature vectors.
In this lecture, we cover the canonical Particle Swarm Optimization (PSO). We start with its functional motivations from the metaheuristic optimization of artificial neural networks and the mechanistic motivations from flocking graphics models ("boids") and related collective motion models from physics (Vicsek model). We then describe the motion rules for PSO and then briefly discuss more modern variants of PSO that have adaptive parameters (as in adaptive inertia) and use network effects to balance exploration and exploitation (e.g., "LBEST" versions of PSO).
This lecture outlines the structure of the Bacterial Foraging Optimization (BFO) metaheuristic for engineering design optimization (EDO) problems. BFO shares some features with other Swarm Intelligence/Distributed AI algorithms, such as Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO), while also borrowing ideas from population-based evolutionary metaheuristics (such as the Genetic Algorithm (GA)). BFO is based on the "run" and "tumble" chemotactic movement of E. coli bacteria, which sense local nutrient concentration gradients as well as chemical communication from other E. coli. After we cover BFO, we pivot to introducing Particle Swarm Optimization (PSO), a more popular swarm-based optimization metaheuristic that moves in virtual space (similar to BFO) but has an inertial component that allows each particle to build up momentum and thus be resistant to sudden changes. We will discuss PSO in more detail in the next lecture.
After a few brief comments about student mini-projects related to multi-objective evolutionary algorithms, this lecture covers Ant Colony Optimization (ACO), with a particular focus on the Ant System (AS) prototype that came before it. This optimization metaheuristic was built originally to solve combinatorial (discrete) optimization problems mimicking how some ants lay pheromonal foraging trails, reinforcing good subgraphs through a network of possible solution candidates to a design problem. The class closes with an introduction to Bacterial Foraging Optimization (BFO), which is inspired by "running and tumbling" flagellated bacteria that can climb local concentration gradients and get out of local traps by using social information. During the class, we also introduce the concept of "stigmergy" (i.e., coordination through modification of the surrounding environment).
In this lecture, we wrap up our introduction of Simulated Annealing and then move on to an introduction to Distributed Artificial Intelligence and Swarm/Collective Intelligence. We start with some clarifications about entropy related to why the logarithm is used. We then revisit basic Monte Carlo integration, based on the Law of Large Numbers, and how it motivates the need for a Boltzmann distribution sampler. We then outline the Metropolis–Hastings algorithm (for Markov Chain Monte Carlo (MCMC) methods). This allows us to finally describe the Simulated Annealing (SA) algorithm, which combines the Metropolis algorithm with a temperature annealing schedule. After wrapping up the discussion of SA, we move on to introducing Distributed AI and Swarm Intelligence. This discussion starts with a description of "Ant System (AS)", the prototype version of what eventually became Ant Colony Optimization (ACO). We will pick up with more details of AS/ACO for combinatorial optimization in the next lecture.
In this lecture, we continue our march toward the basic algorithm for simulated annealing (a popular optimization metaheuristic). We start with the Metropolis algorithm, which was one of the first Markov Chain Monte Carlo approaches for numerical integration. We then generalize the Metropolis algorithm to the Metropolis–Hastings algorithm, which replaces the Boltzmann distribution with any desired probability distribution to sample from. That gives us an opportunity to talk about Markov Chain Monte Carlo (MCMC) in general and discuss its pros and cons. We then start to introduce the simulated annealing algorithm, which will make use of the Metropolis algorithm. We will finish off simulated annealing (SA) in the next lecture.
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).
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.
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).
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.
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.
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.
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.
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.
In this lecture, we finish our discussion of (a simple version of) the Genetic Algorithm (GA), focusing on different genetic operators for recombination and mutation. We then close our discussion of the GA (for now) emphasizing that selection of these operators and other hyperparameters reflects the delicate balance between natural selection and drift -- with too much selective pressure leading to premature convergence on local suboptima and too little selective pressure leading to drift taking over and a random strategy becoming fixed in the population. At the end of this lecture, we pivot to introducing immunocomputing and artificial immune systems. We will pick up with the AIS discussion next lecture.
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.
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."
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.
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).
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.
