COMP-2024/2039

Artificial Intelligence
Methods

Lecture 1
Introductory
 Learning Outcomes

WHAT
• Module Content
• Artificial Intelligence Method ?
1. Basic terminologies
2. Stages of decision making
3. What a model is
IDENTIFY 4. The need for heuristic search/optimisation techniques in decision
support
5. The different heuristic search paradigms and be able to identify
topology of a given heuristics

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 2

Module Content

SECRETs Revealed!
 Educational Aims

YOU will have a sound YOU will understand the YOU will be acquainted
understanding of the methods and techniques with a number of
selected modern that are available as an applications and will
(heuristic) search aid in automated understand how software
techniques in Artificial decision tools are designed to
Intelligence. making/optimisation. solve them.

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 4

 Summary of Content

▪ The main aim of this module is to provide a sound understanding of a wide

range of fundamental concepts and techniques of Artificial Intelligence,
focusing on
✓modern heuristic search/optimisation techniques, including:
- Metaheuristics, such as Iterated Local Search, Simulated Annealing,
Tabu Search and Evolutionary Algorithms and hyper-heuristics
✓and other relevant topics including:
- Learning from Observation, Knowledge and Reasoning, Modelling and
Simulation.

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 5

 Module Details

• COMP2024 (20cr)/COMP2039 (10Cr):

- 2 hours lecture
• COMP2024 (20cr):
- 2 hours computing
- COMP2039 (10Cr) welcome to join

Module

• 2000 word report/programming • 1.5 hour exam

- Answer ALL questions
assignment (COMP 2024 – 50%)
- COMP2024 – 50%; COMP 2039 – 100%
Coursework Exam
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 6

 Resources

1. Search methodologies: introductory tutorials in optimization and decision support techniques -

Edmund Burke, Graham Kendall c2014 [link]
2. Stochastic local search: foundations and applications - Holger H. Hoos, Thomas Stützle 2005 [link]
3. Automated scheduling and planning: from theory to practice - A. Şima Etaner-Uyar, Ender Özcan,
Neil Urquhart 2013 [link]
4. Scheduling: theory, algorithms, and systems - Michael Pinedo 2016 [link]
5. Metaheuristics: From Design to Implementation, El-Ghazali Talbi, DOI: 10.1002/9780470496916,
John Wiley, ISBN: 9780470278581 [link]

IMPORTANT!
• Lecture notes can be reached from the module Moodle web page
• Link to relevant papers will be provided.

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 7

WHY WHY WHY…

Is Artificial Intelligence so IMPORTANT?

 Because…

Modern Heuristic Optimisation/

Search Techniques can…

• do automated timetabling
• decrease carbon emissions and other costs of routing
• reduce operational cost of supply chains
• increase energy production via drawing wind-farm layouts
• improve packing and scheduling workflow for additive manufacturing
• optimise multifunctional structures combining composite and porous layers

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 9

 Nurse Roaster
Wind-farms

Supply Additive Manufacturing

Chains (3D Printing)

Agricultural Lands

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 10

 Engineering Design

Exam Timetabling

Routing

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 11

 Introduction

Let’s get STARTED!

 Definition

A decision is defined as the choice of one among a

Decision number of alternatives.

The process of choosing among alternative courses of

action for the purpose of attaining a goal or goals.
- Turban and Aronson, 1998

Decision Making
Every decision-making process produces a final choice.
The output can be an action or an opinion of choice.
- wikipedia
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 13

 Decision Support

▪ This term is used often and in a variety of contexts related to

decision making.
▪ Multidisciplinary:
- Artificial Intelligence,
- Operations Research,
- Decision Theory,
- Decision Analysis,
- Statistics,...
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 14

 Definition - System

(Wikipedia) “A system is a set of interacting or interdependent

REMEMBER component parts forming a complex or intricate whole.”

▪ Degree of independence of systems

- Closed systems are totally independent
- Open systems are dependent on their environment
▪ Evaluations of systems
- System effectiveness: the degree to which goals are achieved,
i.e., result, output
- System efficiency: a measure of the use of inputs (or resources)
to achieve outputs, e.g., speed. Usually consider space and time.
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 15

 Definition - Models

▪ Major characteristic of decision support systems is that it includes

at least one model
▪ A model is a simplified representation or abstraction of reality
- Reality is usually too complex
- Much of complexity is irrelevant to solving the problem

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 16

 Definition – Types of Models

▪ Iconic Models
- Least abstract - a physical replica of a system: e.g., 3D car.
▪ Analog models
- More abstract - a symbolic representation of reality
- Behaves like the real system but does not look like it: e.g., cardboard cutouts, 2D charts.
▪ Mathematical Models
- Most abstract - mathematical relationships in the problem
- Easier to model than manipulate real systems
- Low cost of the analysis
- Cost of making mistakes is less than mistakes on real system
- Can model risk and uncertainty
- A very large number of solutions can be analysed
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 17

 Solving Problems by Searching

- efficiently finding a set of actions that will move from a given initial
state to a given goal
Search for
- central to many AI problems (e.g., game playing, path finding)
paths to goals
- typical algorithms are the depth first search, breadth * first search,
uniform cost search, branch and bound, A*

- more general class than searching for paths to goals.

Search for - efficiently finding a solution to a problem in a large space of
solutions candidate solutions
(optimisation) - subsumes the first type, since a path through a search tree can be
encoded as a candidate solution

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 18

 Definition – Global Optimisation

• Global optimisation is the task of finding the absolutely best set of

admissible conditions to achieve your objective, formulated in mathematical
terms.
• Fundamental problem of optimisation is to arrive at the best possible
(optimal) decision/solution in any given set of circumstances.
• In most cases “the best” (optimal) is unattainable

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 19

 Global vs. Local Optimum

• Global Optimum: better than

all other solutions (best)
• Local Optimum: better than
all solutions in a certain
neighbourhood, 𝓝

COMP2024 / COMP2039 Introduction 20

 Solving an Optimisation Problem

“Consider everything. Keep the good. Avoid evil whenever you notice it.''

Solving a mathematical optimisation problem:

▪ First choose a quantity (typically a function of several variables – objective
function) to be maximized or minimized, which might be subject to one or more
constraints (constraint optimization).

maximize/minimize 𝑧 = 𝑓(𝑿)
given one or more equality (𝑔𝑖(𝑿) = 𝑐𝑖) or inequality constraints (ℎ𝑗(𝑿) 𝑑𝑗)

▪ Next choose a mathematical method to solve the optimisation problem (searching

the space of solutions & detecting absolutely the best/optimal solution)
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 21

 Search in Continuous vs Discrete Space

Organise the optimum

Find the optimum setting for
(minimum) number of tour
the angle of the wings of a
busses for groups of 30, 10,
race car providing the best
60, 40, 50, 20,..., 35 tourists
performance
(a tour bus has 70 seats)

Vs.

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 22

 Search in Continuous vs Discrete Space

Vs.

Real-valued (parameter)/
Continuous Optimisation
Organising tour busses
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 23

 Search in Continuous vs Discrete Space

Example goal:
pack all items into minimum number of bins

Bins

Vs.
Items

minimum

Function Optimisation
Bin Packing
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 24

 Definition – Problem and Problem Instance

• Problem refers to the high level question or optimisation issue to be solved.

• An instance of this problem is the concrete expression, which represents the
input for a decision or optimisation problem.
• Example: Optimal assignment of groups to busses is an optimisation problem
- Optimal assignment of 3 groups of 10, 15, 43 to busses, each with 45 seats and
company having 10 busses at max is an instance of this problem
- Optimal assignment of 5 groups of 19, 25, 30, 30, 45 to busses, each with 60
seats and company having 10 busses at max is another instance of this problem

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 25

 Analysis of of
Algorithms
Algorithms101:
(Wikipedia): “NP-hard problems are those at

Analysis 101: least as hard as NP problems (…) NP-hard

problems need not be in NP, i.e., they need not
Problem
Problem Classes
Classes have solutions verifiable in polynomial time. E.g. Subset sum problem

Many real-world
problems are in
here

(from [1] and [2]): “NP-complete

problems are the most
difficult NP problems,
if we can solve an NP-complete
problem efficiently, we can solve
all NP problems efficiently”

Solutions can be verified in

polynomial time

Problems can be solved in

polynomial time

[1] http://cs.stackexchange.com/questions/9556/what-is-the-definition-of-p-np-np-complete-and-np-hard
[2] http://cs.stackexchange.com/questions/9556/what-is-the-definition-of-p-np-np-complete-and-np-hard/18666#18666

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 26

 Combinatorial Optimisation Problems

▪ Require finding an optimal object from a finite set of objects

▪ For NP-hard COPs, the time complexity of finding solutions can grow
exponentially with instance size.
▪ Mostly NP-hard (many application areas)
- Determining the optimal way to deliver packages
- Optimal scheduling of shifts/jobs subject to various constraints
- Optimal packing of items
- and more...

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 27

 Example I – Truck Loading

Which truck to load?

Produced from: http://www.beachsideproduce.com/pdf/guidetotruckloading.pdf

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 28

 Example I – Truck Loading

Which truck to load,

• Trucks may have different capacities, and in which order to pick up
different numbers of compartments.
• Trucks may be in different locations.
an item minimising
• Products may have different sizes and
weights.
warehouse travel. • Different versions of the
truck loading problem.
• Products may be in different locations. E.g. destination could be
taken into account.

Produced from: http://www.beachsideproduce.com/pdf/guidetotruckloading.pdf

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 29

 Example II – Soft Drink Bottling
▪ single machine
▪ 4 flavours (f1, f2, f3 and f4)
▪ each flavour has its own filling time
▪ cleaning and changeover time between the bottling of successive
flavours Find the best sequence in
order to minimize the total
aim: to minimise the total changeover time changeover time.
Read as: changeover time when going from f1 to f3.

f1 f2 f3 f4 f1→f2→f3→f4 →f1 f3→f4→f2→f1→f3

2+3+2+50 = 57 2+5+6+70 = 83
f1  − 2 70 50 
  f2→f3→f4→f1→f2 f4→f2→f3→f1→f4
f2  6 − 3 4
3+2+50+2 = 57 5+3+8+50 = 66
f3  8 3 − 2
  f1→f2→f4→f3→f1
f 4  50 5 6 − 
optimal:
2+4+6+8 = 20
Different numbers in here
represent different instances
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM
of this “soft drink bottling”
problem.
COMP2024 / COMP2039 Introduction 30
 Optimisation/Search Methods

Broadly classified
as:

• Exact/Exhaustive/Systematic
• Inexact/Approximate/Local Search
Methods
Methods
- E.g., Dynamic Programming,
- E.g., heuristics, metaheuristics,
Branch & Bound, Constraint
hyper- heuristics,...
Satisfaction,...

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 31

 Search Paradigms I

▪ Single point (trajectory) based search vs.

Multi-point (population) based search

▪ Constructive
- partial solutions

▪ Perturbative
- complete solutions

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 32

 Search Paradigms II

systematic ←→ local search

deterministic ←→ stochastic

sequential ←→ parallel

single objective ←→ multi-objective

[See http://www.cs.ubc.ca/~hoos/SLS-Internal/ch1.pdf pp.23-30]

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 33

 Some Optimisation Techniques – Exact/Exhaustive Methods

▪ Dynamic Programming
◼ Branch & Bound

▪ Constraint Satisfaction
▪ Math programming
- ILP
- MILP
Limitations:
• Only work if the problem is structured and deterministic
– in many cases for small problem instances
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM
• Quite often used to solve sub-problems
COMP2024 / COMP2039 Introduction 34
 Example – Bin Packing Problem

▪ Given bins with the same capacity/size (V)

and a set of items (n) with various sizes
(a1,..,an), pack all items into minimum
number of bins such that the capacity of
each bin is not exceeded.

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 35

 Example – Bin Packing Problem Instance

▪ V=524
▪ n=33
▪ Item sizes (33 items to pack): 85, 442, 10,
10, 10, 10, 10, 10, 252, 252, 252, 252, 252,
252, 252, 9, 9 , 127, 127, 127, 127, 127,
106, 106, 106, 106, 12, 12, 12, 84, 46, 37
How can we solve this problem using
an exact method?
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 36

 Example – Math Programming Solution

Number of bins used

Model
Total volume of bin

Item j can only be

placed in 1 bin
i can’t exceed V

aj is the size of item j

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM itemSize = #[ 1: 85, 2: 442, 3: 10, 4: 10, …, 32: 37, 33: 37 ]#;
binCapacity = #[ 1: 524, 2: 524, 3: 524, …, 33: 524 ]#;
COMP2024 / COMP2039 Introduction 37
 Example

Performance Comparison of Different Branch & Bound Algorithms for Optimal Bin Packing

▪ Details not important

right now. Just an
illustration of how
computational
complexity (e.g. time)
scales with problem
size (i.e. N).
▪ The solution time
increases with the size
of the problem
instance substantially

25 days
See http://www.aaai.org/Papers/AAAI/2002/AAAI02-110.pdf

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 38

 Some Optimisation Techniques – Heuristic Search Methods

utilising modern optimisation/search

techniques in particular heuristics,
metaheuristics and hyper-heuristics to
Our solve “discrete” combinatorial optimisation
Focus
problems effectively and efficiently,
facilitating the use of data, models, and
structured decision processes for decision
support.
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 39

Break
 Heuristic
Search/Optimisation
 Heuristic Search Methods

Heuristic A rule of thumb method derived from human intuition.

▪ A heuristic is a search method which seeks good, i.e., near-

optimal solutions, at a reasonable cost without being able to
guarantee optimality.
▪ Good for solving ill-structured problems, or complex well-
structured problems (large-scale combinatorial problems that
have many potential solutions to explore)

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 42

 Example – Bin Packing Problem Instance (revisited)

▪ V=524
▪ n=33
▪ Item sizes (33 items to pack): 85, 442, 10,
10, 10, 10, 10, 10, 252, 252, 252, 252, 252,
252, 252, 9, 9 , 127, 127, 127, 127, 127,
106, 106, 106, 106, 12, 12, 12, 84, 46, 37

How would you do it?

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 43

 Example – A Heuristic Solution
The problem with heuristics?

442 252 127 106 37 10 10

252 252 127 106 37 10 9

sorted items 252 252 127 85 12 10 9

252 127 106 84 12 10

252 127 106 46 12 10

[A Deterministic Local Search/Greedy

Largest item first fit Constructive Heuristic Algorithm]
Sort the items by its size in decreasing order, then place each
item into the first bin that will accommodate that object. The
bins are also sorted in the order they came into use.
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 44

 Bin1 Bin2 Bin3 Bin4 Bin5 Bin6 Bin7 Bin1 Bin2 Bin3 Bin4 Bin5 Bin6 Bin7 Bin8
442 442 442
252 252 252
Example of heuristic
252 252 252 weakness: removing an item,
252 252 252 leads to a solution with more
252 252 252 bins (i.e. 8 bins instead of 7).

252 252 252

252 252 252
252 252 252
127 127 127
127 127 127
127 127 127
127 127 127
127 127 127
Largest 106
106
106
106
106
106
106
item first fit 106
106
106
106 106
85
85 85
rule 84
46 46 and so on , according
84
46 – removed
84

37 to first fit ... 37 37

37 37 37
12 12 12
12 12 12
12 12 12
10 10 10
10 10 Instance #2 is the same as
10
10 10 instance #1 except that it does 10
not have item 46. 10
10 10
10 10 10
10 10 10
ACK: Prof. Ender Özcan, 9 9 9
UNUK, Dr Tomas Maul &
ACK: Prof. Ender Özcan,
Dr Chen UNUK,UNM
ZhiYuan, 9
Dr Tomas Maul & Dr Chen ZhiYuan, UNM 9 9
524 524 524 524 524 524 524 516 516 516 516 516 517 516 9
COMP2024 / COMP2039 Introduction
Instance#1 Instance#2 45
Example

Travelling Salesman Problem

 Travelling Salesman Problem (TSP)

• “Given a list of cities and the distances between each pair of

cities, what is the shortest possible route that visits each city
and returns to the origin city?” – NP hard.
• Underpins many real world problems: Planning, logistics,
vehicle routing, telecommunication, manufacturing of
microchips, genome sequencing, clustering of data arrays,
scheduling, cutting & packing and more...

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 47

 Need for Search Methodologies – Example
(e.g., Heuristics, Metaheuristics)

▪ Travelling salesman problem (N = number of cities)

▪ Number of configurations to search from is N!
▪ N=4, 24 (4*3*2*1=24)
▪ N=5, 120
▪ N=7, 5 040
▪ N=10, 3 628 800
▪ N=81, 5.797 x 10120
▪ Number of particles in the universe is in between 1072 – 1087
- Tianhe-2: 30.65 petaflops (1015 floating-point operations per second) – ~6 x 1096 years (for
N=81; exhaustive search; divide the number of configurations by the number of seconds in a
year; several rough assumptions, but you get the idea)
We need heuristics.
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 48

 Examples – Heuristics for TSP

▪ The nearest neighbour (NN) algorithm

- Constructive (Deterministic and Systematic)
▪ Pairwise exchange (2-opt), or Lin–Kernighan heuristics
- Perturbative (Stochastic and Local Search)

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 49

 The Nearest Neighbour (NN) Algorithm

city2
4
city1
10
11
5 6
city4 city3
7

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 50

 The Nearest Neighbour (NN) Algorithm

<city2>
city2
Select a starting city randomly

city1

city4 city3

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 51

 The Nearest Neighbour (NN) Algorithm

<city2, >
choose the nearest
city2 unvisited city as the next
4 move
city1
10

6
city4 city3

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 52

 The Nearest Neighbour (NN) Algorithm

<city2, city1, >

choose the nearest
city2 unvisited city as the next
4 move
city1
11
5
city4 city3

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 53

 The Nearest Neighbour (NN) Algorithm

<city2, city1, city4, >

choose the nearest
city2 unvisited city as the next
4 move
city1

5
city4 city3
7

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 54

 The Nearest Neighbour (NN) Algorithm

<city2, city1, city4, city3> : 26

After the choice of the last city,
city2 algorithm terminates
4
city1
10
5
city4 city3
7

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 55

 Constructive Stochastic Local Search Algorithm for TSP

• Step 1: Choose a random city

• Step 2: Apply nearest neighbour to construct a
complete solution
• Step 3: Compare the new solution to the best found so
far and update the best solution as appropriate
• Step 4: Go-to Step 1 and repeat while the maximum
number of iterations is not exceeded (parameter)
• Step 5: Return the best solution

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 56

 Exercise

▪ How can we turn this approach into a stochastic

and local search heuristic searching even further
configurations?
▪ Parameters?

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 57

 Pairwise exchange (2-opt)

<city2, city1, city3, city4> : 28

city2 Remove two edges and
replace them with two different
4 edges, reconnecting the
city1
fragments into a new and
11 shorter tour.
6
city4 city3
7

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 58

 Pairwise exchange (2-opt)

<city2, city1, city3, city4> : 28

city2 Remove two edges and
replace them with two different
4 edges, reconnecting the
city1
fragments into a new and
11 shorter tour.
6
city4 city3
7

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 59

 Pairwise exchange (2-opt)

<city1, city2, city3, city4> : 26

city2 Remove two edges and
replace them with two different
4 edges, reconnecting the
city1 10 fragments into a new and
11 shorter tour.
6
city4 city3
7

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 60

 Pairwise exchange (2-opt)

<city1, city2, city3, city4> : 26

city2
4
city1 10

city4 city3
7

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 61

 A Perturbative Stochastic Local Search Algorithm for TSP

• Step 1: Create a random current solution (build a

permutation array and shuffle its content)
• Step 2: Apply 2-opt: swap two randomly chosen cities
forming a new solution
• Step 3: Compare the new solution to the current
solution and if there is improvement make the new
solution current solution, otherwise continue
• Step 4: Go-to Step 2 and repeat while the maximum
number of iterations is not exceeded (parameter)
• Step 5: Return the current solution
ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 62

 More on Euclidean/Symmetric TSP

• Other Heuristics
• Christofides' algorithm (1976)
• Match Twice and Stitch [doi:10.1016/j.orl.2004.04.001]
• Lin–Kernighan [doi:10.1016/S0377-2217(99)00284-2]
• Exact algorithm – Concorde:
http://www.math.uwaterloo.ca/tsp/concorde/index.html
• TSP benchmark data: [University of Waterloo]

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 63

 Drawbacks of Heuristic Search

▪ There is no guarantee for the optimality of the obtained

solutions.
▪ Usually can be used only for the specific situation for
which they are designed.
▪ Often, heuristics have some parameters
- Performance of a heuristic could be sensitive to the
setting of those parameters
▪ May give a poor solution.

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 64

Pseudo-random
numbers
 Deterministic vs Stochastic Heuristic Search

• Deterministic heuristic search algorithms provide the same solution

when run on the given problem instance regardless of how many times.
• Stochastic algorithms contain a random component and may return a
different solution at each time they are run on the same instance
- Multiple trials/runs should be performed for the experiments/simulations
- Being able to repeat/replicate those multiple trials/runs in the
experiments/simulations is crucial in science, and
- This also enables average performance comparison of different stochastic
heuristic search algorithms applying statistical tests

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 66

 Pseudo-random numbers

• A long sequence of numbers that is produced using a

deterministic process but which appear to be random.
• Note that most computers and programming languages have
support to produce pseudo- random numbers, and often with
seeding
- E.g., assume a pseudo-random number generator producing values with
lower limit: 0.00, upper limit: 1.00
seed(12345): <0.19, 0.03, 0.87, 0.54, ...>
seed(4927): <0.48, 0.91, 0.02, 0.26, ...>

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 67

 Some problems with pseudo random numbers

• Shorter than expected periods for some seed states; such seed
states may be called 'weak' in this context.
1000th entry
E.g., 1000th entry
seed(12345): <0.19, 0.03, ..., 0.19, 0.03 ...>
• Lack of uniformity of distribution. E.g., 0.17 appears 100 times in
10000 successive numbers while 0.29 appears 5 times more
• Correlation of successive values.
• The distances between where certain values occur are distributed
differently from those in a random sequence distribution

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 68

 Example:
Middle Square Method, an early pseudo-random number generator

• Presented by John Von Neumann in 1949

• To generate a sequence of n-digit pseudorandom numbers
• Example: 4-digit case
- Starts with an initial value (seed) (2156)
- Takes its square (21562 = 04648336)
- Middle digits are used as a random number 6483
- Then this process is repeated (64832 = 42029289)
• Problem: all sequences eventually repeat themselves

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 69

 Notice the difference – Exercise 1

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 70

 Notice the difference – Exercise 2

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 71

 Notice the difference – Exercise 3

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 72

 Notice the difference – Exercise 4

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 73

 Summary

2
1 1. Basic terminologies
2. Stages of decision making
• Module Content 3. What a model is
• Artificial Intelligence Method 4. The need for heuristic search/optimisation
techniques in decision support
5. The different heuristic search paradigms and be
able to identify topology of a given heuristics

ACK: Prof. Ender Özcan, UNUK, Dr Tomas Maul & Dr Chen ZhiYuan, UNM

COMP2024 / COMP2039 Introduction 74

Questions
 NEXT:

Components of Heuristics
Search Methods and Hill
Climbing