AI 20 credits

lec 1 updated

What are the 2 ways to solving a problem?

1. by systematically searching from paths to goals , e.g., tree/graph search, or finding a set of actions to move from initial given state to a goal state

2. optimisation - search for solutions (this is more general)

What is the single-objective optimisation problem?

It is a type of optimisation problem that involves maximizing or minimizing a single objective function under a given set of constraints.

• Min z = f(X)

• Where X = a vector of variables / decisions <x1, x2, .., xn>.

• Often subject to one or more constraints:

• 𝑋1 + 𝑋2 ≥ 0

• 2𝑋2 + 𝑋3 = 5

What is the difference between local & global optimum?

Local - better than all solutions in a given neighbourhood, N

Global - better than all other solutions

(most of the times, the average solution is starting at a random number, and either increasing or decreasing)

What are the 2 types of search spaces ?

1. Continuous e.g., finding the best angle for wings of a race car for best performance

2. Discrete e.g., assigning tourist groups to buses to produce optimum number of 70 seater tourist buses for groups of size n

What is Combinatorial Optimisation Problems?

Finding an optimal solution from a finite set of solutions.

• for NP-hard COPs, this finite set grows exponentially with the instance

What are the 2 approaches to optimisation / search problems?

1. exact / exhaustive methods

   • dynamic programming like B&B, constraint satisfaction

   • systematically traversing the SS

   • has optimal guarantees.

2. inexact/ approximate / local search methods

   • heuristics / MH / HH

   • sample the SS through neighbourhood operators

   • no optimality guaranteed.

Single-point (trajectory) vs Multi-point (population)

• single-point: an individual solution is used to explore the SS by modifying it

• multi-point: multiple solutions used simultaneously & may interact together to guide the search to a possible solution

Perturbative vs Constructive heuristics

• perturbative: modifies complete solution through neighbourhood ops to produce a new complete solution

• constructive: uses a heuristic on a partial solution (or no solution) to build it to a complete solution

deterministic vs stochastic

• deterministic: systematically approaches the search same way each time so the same solution is produced if same initial solution

• stochastic: random; explores SS differently each time so there is no guarantee for the same solution

systematic vs local search

• systematic: method to solve by exploring all available solutions exhaustively, such as fully parsing through a tree

• local search: sampling method, going from solution to next solution

sequential vs parallel

• sequential: one step at a time, where each step must be completed before the next begins.

• parallel: multiple steps are executed at the same time, allowing for simultaneous processing.

single-objective vs multi-objectivee

• single-objective: focused on optimising one criterion,

• multi-objective: considers multiple criteria simultaneously, often leading to trade-offs. usually for a cluster of problems

Exact Optimisation

• good for dynamic programming, B&B, Math programming, constraint satisfaction

• limitations: only works if it is a structured problem, so usually used for small problem instances, e.g., bin packing problem

  • usually used to solve sub-problems

• solution time increases substantially as problem size increases

Using a Heuristic Approach

A method of solving problems by practical and often approximate techniques, rather than through exact solutions. Heuristics can effectively manage complex problems where traditional optimization techniques may be infeasible.

What are some heuristics for TSP?

• Nearest Neighbour (NN) algorithm:

  • Constructive

  • Stochastic

  • Systematic

• Pairwise exchange (2-opt)

  • Perturbative

  • Stochastic

  • Local search

Step through a constructive stochastic local search algorithm for TSP

§ Step 1: Choose a random city.

§ Step 2: Apply NN to construct a complete solution.

§ Step 3: Compare the new solution to the best solution found so far and update if we improved.

§ Step 4: Repeat until some maximum number of iterations is reached by going back to Step 1.

§ Step 5: Return the best solution found.

What is 2-opt / pairwise exchange?

A local search algorithm used to improve a given tour in the Traveling Salesman Problem (TSP) by iteratively removing two edges and reconnecting them in a different way to reduce the overall tour length.

What are some limitations of heuristic search?

• No optimality guarantees (unlike exact methods)

• Usually require designing new heuristics for solving other problems

• Often parameterised & v sensitive to settings

• May result in poor quality solutions when:

  • Used for different problem instances

  • Applied a second time (stochastic methods)

What are pseudo-random numbers?

Numbers generated by a deterministic process that mimic the properties of random numbers, often used in algorithms and simulations where true randomness is not feasible.
- they are useful for experimentation as they explore a sample of algorithm performance

-and provide guaranteed repeatability of results

What is the main issue with pseudo-random numbers?

They may lack true randomness, leading to patterns that can bias results in simulations.

Period of a pseudo-random number generators refers to length of sqeuence before being repeated.
- example of how to combat is ‘‘ middle square method, which generates new numbers based on the squares of previous numbers.

name 3 world problems to be solved via optimisation/search techniques

timetabling, vehicle routing to reduce carbon emissions, supply-chain cost minimisation

difference between searching from paths to goals and searching for solutions (optimisation)?

• paths to goals: eg BFS, A* finds a sequence of actions to a goal state

• optimisation: encodes each path as a candidate solution & seeks best one by objective value

how to formulate a single-objective optimisation problem?

minimise (or maximise) an objective

z= f(X) over decision vector X= (x1..xn), subject to any constraints, e.g., x1+x2>=0

what defines a COP (combinatorial optimisation problem)?

finding the best solution from a finite- but exponentially large- set of candidates (eg TSP, bin-packing)

why are NP-Hard COPs intractable by exhaustive search?

their solution space (SS) grows exponentially with instance size, making ‘check-all’ options impossible in practice

difference between exact (systematic) vs inexact (approx) methods?

• exact (e.g, dynamic programming, B&B, constraint satisfaction) guarantees optimality but scale poorly

• inexact (heuristics/ metaheuristics) sample via neighbourhoods & trade optimality for speed// no optimality guarantees

what is single-point vs multi-point search paradigm?

• single-point (trajectory)- keeps 1 solution & modifies it to explore SS

• multi-point (population)- maintains multiple solutions to explore SS simultaneously (they interact with each other)

define perturbative vs constructive heuristics

• perturbative - starts from complete solution & applies moves (like local search) to improve it.

• constructive - builds a solution from scratch by adding components step by step. like nearest neighbour algorithm, greedy algorithms, or other similar methods.

what is difference between deterministic vs stochastic search methods?

• deterministic- always follows same steps (same output if same input)

• stochastic- uses randomness & can yield different results each run

difference between systematic & local search

• systematic - exploring entire space methodically (like using a search tree)

• local search- samples via neighbourhood moves , moving from sol to sol

what do ‘sequential v parallel’ & ‘single-objective vs multi-objective’ refer to?

• sequential/ parallel: whether the algorithm runs in one thread or many

  • single-objective: optimises one measure

  • multi-objective: handles several from a problem cluster (eg cost & time)

give an example of an exact method & why it may fail at scale

Branch & Bound solves bin-packing exactly, but takes 25 days (too long !!) on a 60 exam scheduling instance.

what is ‘largest item first-fit’ heuristic for bin packing?

sort items by descending size, then place each into the first bin with enough capacity

define the TSP (travelling salesman problem)

given N cities and pairwise distances, find the shortest tour visiting each city once & then returning to the start

outline the Nearest Neighbour heuristic to solve TSP

(constructive- acts on partial or no solution uses heuristic to build complete solution)

1) pick a random start city

2) repeatedly go to the nearest unvisited city

3) repeat from new starts and keep the best tour found (until iteration limit too)

outline the 2-opt heuristic for TSP

(perturbative - new sol with mutations each time)

1) start from a tour

2) swap two edges to get a new tour

3) accept if shorter

4) repeat until iteration limit

list 3 caveats of heuristic search methods

• no optimality guarantees

• often problem-specific

• performance is sensitive to parameter settings

what is the difference between open & closed decision support systems?

• open DSS: dependent on their environment, ingest live data & adapt models as they go along

• closed DSS: independent of their environment, run against a fixed dataset & rule-base→ produce repeatable outputs until manually reconfigured