40.018 Heuristics and Systems Theory

Iterative methods are mathematical procedures that use an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the current approximation is derived from the previous ones. This course introduces two important types of iterative methodologies often encountered in the analysis and design of engineering systems: 1) metaheuristic optimisation algorithms; and 2) model-based analysis and design tools for dynamical systems.

The first part of the course focuses on metaheuristics optimisation algorithms — artificial intelligence search methods used to find approximate solutions to complex optimisation problems (potentially) under incomplete information and/or limited computation power. The course will describe a variety of metaheuristic search methods including simulated annealing, tabu search, evolutionary algorithms, swarm optimisation, and multi-objective methods.

The second part of the course introduces basic models for dynamical systems (discrete-time state space representations), core system properties, and model-based design methods for estimation and control. State space models characterize the time evolution of dynamical systems, from particular initial conditions, in response to driving external inputs. In this part of the course, we will introduce important system-theoretic properties (equilibria, stability, observability, and controllability) that characterize the behaviour and evolution of system trajectories and enable analysis and design for estimation and control.

Learning objectives

• Learn the basic principles of metaheuristic optimisation.
• Understand how decision-making problems can be modelled and solved using metaheuristics.
• Understand, implement, and evaluate modern metaheuristic algorithms (annealing, tabu, evolutionary, swarm, and multi-objective) to address large-scaled high-dimensional optimisation problems.
• Learn state space model representations of dynamical systems, and core system properties (equilibria, stability, observability, and controllability).
• Examine nonlinear state-space models to find equilibria (fixed-points), assess their stability, and linearize the system.
• Apply model-based tests to assess, stability, observability, and controllability of linear dynamical systems.
• Design state observers and feedback controllers for linear systems using pole-placement techniques.

Measurable outcomes

• Be able to explain and differentiate the principles of various metaheuristic algorithms, such as simulated annealing, evolutionary algorithms, swarm/tabu optimisation, and multi-objective methods.
• Write and execute Python implementations of these metaheuristic algorithms and apply them to solve optimisation problems.
• Compare the performance and assess advantages and limitations of different metaheuristic algorithms by evaluating convergence rates, solution quality, and computational efficiency.
• Be able to explain the structure of state-space representations for discrete-time dynamical systems, including state variables, inputs, outputs, and transition functions and matrices.
• Compute equilibrium points of nonlinear state-space models, determine their stability using, and derive linearized approximations around equilibrium points.
• Determine system properties such as stability, controllability, and observability of dynamical systems from (linear) state-space representations.
• Be able to design linear state feedback controllers and Luenberger observers to modify system behaviour and estimate states from available outputs, respectively.
• Implement and analyse state-space models, feedback controllers, and observers using MATLAB/Python and interpret the results.

Prerequisites

• 10.018 Modelling Space and Systems
• 40.002 Optimisation
• 40.017 Probability and Statistics

Number of credits: 12