Introduction to
Artificial Intelligence
with Python
Optimization
optimization
choosing the best option from a set
of options
local
search
search algorithms that maintain a
single node and searches by moving
to a neighboring node
Cost:
17
state-space landscape
objective global maximum
function
cost global minimum
function
current state
neighbors
Hill Climbing
Hill Climbing
function HILL-CLIMB(problem):
current = initial state of
problem repeat:
neighbor = highest
valued neighbor of current
if neighbor not better than current:
return current
current = neighbor
Cost:
17
Cost:
17
Cost:
17
Cost:
15
Cost:
13
Cost:
11
Cost: 9
Hill Climbing Variants
Variant Definition
steepest-ascent choose the highest-valued neighbor
choose randomly from higher-
stochastic
valued neighbors
first-choice choose the first higher-valued neighbor
random-restart conduct hill climbing multiple times
local beam search chooses the k highest-valued neighbors
Simulated Annealing
Simulated Annealing
• Early on, higher "temperature": more likely to
accept neighbors that are worse than current state
• Later on, lower "temperature": less likely to accept
neighbors that are worse than current state
Simulated Annealing
function SIMULATED-ANNEALING(problem, max):
current = initial state of problem
for t = 1 to max:
T = TEMPERATURE(t)
neighbor = random neighbor of current
ΔE = how much better neighbor is than
current
if ΔE > 0:
current = neighbor
with probability eΔE/T set current =
Traveling Salesman Problem
Linear Programming
Linear Programming
• Minimize a cost function c1x1 + c2x2 + ... + cnxn
• With constraints of form a1x1 + a2x2 + ... + anxn ≤ b
or of form a1x1 + a2x2 + ... + anxn = b
• With bounds for each variable li ≤ xi ≤ ui
Linear Programming Example
• Two machines X1 and X2. X1 costs $50/hour to run,
X2
costs $80/hour to run. Goal is to minimize cost.
• X1 requires 5 units of labor per hour. X2 requires
2 units of labor per hour. Total of 20 units of labor
to spend.
• X1 produces 10 units of output per hour. X2 produces
12 units of output per hour. Company needs 9 0
units of output.
Linear Programming Example
• Cost
Two Function: 50xX12+
machines X1 and . X80x
1 costs
2 $50/hour to run,
X2
costs $80/hour to run.
• X1 requires 5 units of labor per hour. X2 requires
2 units of labor per hour. Total of 20 units of labor
to spend.
• X1 produces 10 units of output per hour. X2 produces
12 units of output per hour. Company needs 9 0
units of output.
Linear Programming Example
Cost Function: 50x1 + 80x2
Const raint: 5x1 + 2x2 ≤ 20
Linear Programming Example
Cost Function: 50x1 + 80x2
Const raint: 5x1 + 2x2 ≤ 20
Const raint: 10x1 + 12x2 ≥ 90
Linear Programming Example
• Cost
Two Function: 50xX12+
machines X1 and . X80x
1 costs
2 $50/hour to run,
X2
costs $80/hour to run.
• Const
X1 requires 5x1labor
raint: 5 units of + 2x2per
≤ hour.
20 X2 requires 2
units of labor per hour. Total of 20 units of labor to
spend.
X1 produces
• Const raint: (−10x1) + (−12x2) ≤ − 90
10 units of output per hour. X 2 produces
12 units of output per hour. Company needs 9 0
units of output.
Linear Programming Algorithms
• Simplex
• Interior-Point
Constraint Satisfaction
Student:
4
Student: Taking classes:
1 A B
C
2 B D E
3 C E F
4 E F G
Student: Taking classes: Exam slots:
1 A B
C Monday
Tuesday
2 B D E Wednesday
3 C E F
4 E F G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
Constraint Satisfaction Problem
• Set of variables {X1, X2, ..., Xn}
• Set of domains for each variable {D1, D2, ..., Dn}
• Set of constraints C
5 3 7 Variables
6 1 9 5
9 8 6 • {(0, 2), (1, 1), (1, 2), (2, 0), ...}
8 6 3
4 8 3 1 • Domains
7 2 6 • {1, 2, 3, 4, 5, 6, 7, 8, 9}
6 2 8 • for each variable
4 1 9 5
8 7 9 • Constraints
• {(0, 2) ≠ (1, 1) ≠ (1, 2) ≠ (2, 0), ...}
A Variables
{A, B, C, D, E, F, G}
B C
• Domains
• {Monday, Tuesday, Wednesday}
• for each variable
D F
Constraints
E {A≠B, A≠C, B≠C, B≠D, B≠E, C≠E,
G
C≠F, D≠E, E≠F, E≠G, F≠G}
hard
constraints
constraints that must be satisfied in
a correct solution
soft
constraints
constraints that express some notion of
which solutions are preferred over
others
unary
constraint
constraint involving only one
variable
unary
constraint
{A ≠ Monday}
binary
constraint
constraint involving t w o variables
binary
constraint
{A ≠ B}
node
consistency
when all the values in a variable's
domain satisfy the variable's unary
constraints
A B
{Mon, Tue, Wed} {Mon, Tue, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Mon, Tue, Wed} {Mon, Tue, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Mon, Tue, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Mon, Tue, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Mon, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Mon, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Wed
}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Wed
}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
arc
consistency
when all the values in a variable's
domain satisfy the variable's binary
constraints
arc
consistency
To make X arc-consistent with respect to Y,
remove elements from X's domain until
every choice for X has a possible choice for
Y
A B
{Tue, Wed} {Wed
}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Wed
}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue {Wed
} }
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue {Wed
} }
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
Search Problems
• initial state
• actions
• transition model
• goal test
• path cost function
CSPs as Search Problems
• initial state: empty assignment (no variables)
• actions: add a {variable = value} to assignment
• transition model: shows how adding an
assignment changes the assignment
• goal test: check if all variables assigned
and constraints all satisfied
• path cost function: all paths have same
cost
Backtracking Search
Backtracking Search
function BACKTRACK(assignment, csp):
if assignment complete: return assignment
var = SELECT-UNASSIGNED-VAR(assignment, csp)
for value in DOMAIN-VALUES(var, assignment, csp):
if value consistent with assignment:
add {var = value} to assignment
result = BACKTRACK(assignment, csp)
if result ≠ failure: return result
remove {var = value} from assignment
return failure
Example