Random-Hill-Climbing(problem):

current_point = make_node( initial_state( problem ))

while

True

:

neighborhood = current_point.get_neighbors( )

good_neighbors = neighborhood.take_all_nodes_with_value_greater( current_point.value )

if

good_neighbors is not empty:

current_point = good_neighbors.get_random_item( )

else

:

return

current_point

def

Hill-Climbing-With-Sidesteps(problem, sidesteps_limit):

sidesteps_counter = 0

current_point = make_node( initial_state( problem ))

while

True

:

neighborhood = current_point.get_neighbors( )

best_neighbor = neighborhood.find_the_best_neighbor( )

if

best_neighbor.value > current_point.value:

current_point = best_neighbor

sidesteps_counter = 0

elif

best_neighbor.value == current_point.value:

sidesteps_counter += 1

if

sidesteps_counter > sidesteps_limit:

return

current_point

else

:

return

current_point

Completeness ?

Optimality ?

Memory usage ?

Working time ?

**Search Heuristics Course**

**Searching paradigm**

**Informed search**

How do we define a problem?

Problem domain (what are we talking about?)

Input (what do we have?)

Output (what do we want?)

Example: shortest path

Problem domain: cities, countries, roads

Input: starting and finishing points

Output: shortest route from start to finish

From Skopje, Macedonia to Kyiv, Ukraine

Searching paradigm ( 3-S definition)

searching

State

searching

Space

searching

Strategy

State is a "one-time snapshot" of all valuable data from the problem domain (e.g. in which city are we now?)

Searching space is a set of all possible states for the current problem domain (e.g. all possible cities on the Earth)

Strategy describes how do we travel from one city to another

History analogies

Who are the most ancient "searchers", or search agents?

Wandering for 40 years in the desert with his people

Moses

quite enough time for an algorithm to get a solution

Searching for a shortest path from Troy to Ithaca for 10 years

Odysseus

Course plan

Uninformed strategies (Day 1)

BFS, DFS, LDFS, ...

Informed strategies (Day 2)

Greedy, A*, ...

Local search and metaheuristics (Day 3)

Hill climbing, Beam, Tabu, ...

Search paradigm applications (Day 4)

Planning in AI, competitive games

Types of problems

1. It's essential to know the whole path from an initial state to a goal state

2. We don't care about path. The only valuable thing is a goal state as it is.

Examples: shortest path, planning in AI, puzzles

Examples: traveling salesman problems, scheduling, competitive games

**Uninformed**

search

search

Main idea

The uninformed algorithms are simply walking through the whole search space

They are the basis for more complicated methods

You may be familiar with them already:

Breadth First Search

Depth First Search

Recall search space and states

Problem domain (graph)

Search space (tree)

states

neighborhood

Breadth First Search (BFS)

Depth First Search (DFS)

function Tree-Search(problem, strategy)

initialize current node with initial state of problem

loop do

if there are no candidates for expansion then return failure

choose a leaf node for expansion according to strategy

if the node contains a goal state then return the corresponding solution

else expand the node and add the resulting nodes to search tree

state

node

parent node

action

Each node has a "path-cost", i.e. cost of the path (length) from an initial node to the cureent one

Strategy properties

Completeness

Strategy is complete if it guarantees to find a solution

Optimality

Strategy is optimal if it guarantees to find an optimal solution

Memory usage

Number of nodes stored in memory during work

Working time

BFS properties

Completeness ?

Optimality ?

Memory usage ?

Working time ?

DFS properties

Yes

Yes

Exponential

Exponential

Completeness ?

Optimality ?

Memory usage ?

Working time ?

No

No

Linear

Exponential

BFS: Implementations details

Data structure: queue (First In First Out)

DFS: Implementations details

Data structure: stack (List In First Out)

DFS modifications

How to avoid this infinity loop?

Limited depth first search

Includes a limit - maximum depth of a searching tree

No

No

Linear

Exponential

LDFS properties

Completeness ?

Optimality ?

Memory usage ?

Working time ?

Iterative depth first search

Sequentially calls a limited DFS method while incremenating a limit iteratively

Yes

Yes

Linear

Exponential

IDFS properties

So which algorithm is better to use?..

BFS

DFS

LDFS

IDFS

Recall our shortest path problem

Goal: find the path

from Kyiv to Remsfeld

Information is significant!

What have we learned so far?

Main idea

Enable more intelligent wandering through a search space.

Our algorithms need somehow to guess a preferred direction where a goal state may lie.

Heuristics

experience-based techniques for problem solving, learning, and discovery that gives a solution which is not guaranteed to be optimal

a mental shortcut that allows people to solve problems and make judgments quickly and efficiently

strategies using readily accessible, though loosely applicable, information to control problem solving in human beings and machines

**Heuristic functions**

Short path problem

How to define which city is closer to our goal?

Lviv, 1050 km to Remsfeld

Odessa, 1630 km to Remsfeld

**Search Heuristics**

**VIII Summer School**

Achievements and Applications of Contemporary Informatics, Mathematics and Physics

Achievements and Applications of Contemporary Informatics, Mathematics and Physics

**Kyiv, Ukraine**

2013

2013

**by Oleksii Molchanovskyi**

**Local search**

**Metaheuristics**

Khrakiv, 1900 km to Remsfeld

For instance, you may use geographical coordinates to calculate the distances.

Which way is better to go from Kyiv to Remsfeld?

15-Puzzle

Is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing.

The object is to place the tiles in order by making sliding moves that use the empty space.

Amount of tiles that are not

on the proper places.

Total Manhattan distance:

sum of coordinate differences

between tile current position and

its goal position.

Possible heuristics

Eight Queens

Place 8 chess queens on an 8×8 chessboard so that no two queens attack each other

Possible heuristic

Amount of pairs of queens that attack each other

Best first search approach

A cost function F(x) is used to make an estimation of each node in the search tree (or search graph in general)

Generally heuristic function H(x) is a part of a cost function F(x)

H(x) estimates how close a particular state is to a goal state

General search algorithm

def

Best-First-Search

( problem, cost-function ):

queue = PriorityQueue( )

start_point = make_node( initial_state( problem ))

queue.insert( start_point )

while

True:

if

queue is empty:

return

Fail

node = queue.pop( )

if

node.state( ) is a goal state:

return

node

neighborhood = node.state( ).get_neighbors( )

for each

neighbor_node in neighborhood:

neighbor_estmate_cost = cost_function( neighbor_node )

queue.insert( [neighbor_node, neighbor_estmate_cost] )

Place where heuristics is used

Greedy search

Uses only heuristic function: F(x) = H(x)

Greedy algorithm expands a node that seems to be closest to a goal

Advantage: may be very fast

Disadvantage: may stuck in a dead end

Greedy method properties

Completeness ?

Optimality ?

Memory usage ?

Working time ?

No (remember dead ends)

No

Exponential

Exponential, but good

heuristics significantly

improve the result

Imagine yourself on a horse...

...a very fast one...

...and a little bit crazy.

So how to prevent such cases?

Use breaks!.. Even a simple rope works!

A* (A-star) method

Main idea: avoid the paths that are too costly

Cost function: F(x) = H(x) + G(x)

H(x) - a heuristic estimate of how close is a goal

G(x) - a cost of already passed path, i.e. from initial state to a current state x

G(x) is a rope for a crazy "greedy" horse.

So simple but so powerful!

Advantage: will always find the road

Properties of A*

Completeness ? Yes

Optimality ? Yes

Moreover A* is optimally efficient for any given heuristic function!

That is, no other optimal algorithm is guaranteed to expand fewer nodes than A*.

Memory usage ? Exponential

Running time ? Exponentially depends on a solution length

Unfortunately A* is not a "silver bullet".

Recall the Best-First-Search function

def

Greedy-Search

(problem):

return

Best-First-Search( problem, H )

def

Astar

-Search

(problem):

return

Best-First-Search( problem, H + G )

VS

Recursive Best First Search

It is a standard BFS algorithm but which uses only linear memory.

On each iteration it stores in memory only one branch of a search tree

To avoid duplicate expanding of non-useful tree nodes it checks a best second state every time

When a current node will became unpromising it switches to the stored alternative and deletes whole current branch

Properties of RBFS

Completeness ? Yes

Optimality ? Yes

Memory usage ? Linear

Working time ? Exponential in general case

RBFS theoretically is as good as A*.

But it can spend too much time for "jumping" between alternative nodes in a search tree.

To minimize this side-effect and to optimize memory usage the memory-bounded A* modifications are used: MA* and SMA*.

SMA*: Simplified Memory-Bounded A*

Works similar to A* untill all memory is used.

When there is no enough memory it deletes the worst node from a search tree.

But stores deleted node cost in its parent node.

Methods comparison

Compare uninformed (BFS, LDFS, IDFS) and informed (Greedy, A*, RBFS) algorithms for various sizes of the N-queens problem

Overall amount of generated nodes and maximum amount of nodes in memory

- Unsolved instances of problem

Recall heuristic functions

Which heuristic function is a good one?

To answer this question we need to introduce an admissible heuristic.

A heuristic function H(x) is called an admissible if it never overestimates the cost to reach the goal.

Admissible heuristics are by nature optimistic, because they think the cost of solving the problem is less than it actually is.

But too much optimism is not good either.

Heuristic function H1(x) dominates another function H2(x) if H1(x) > H2(x) for all x

H3(x) > H2(x)

Heuristics comparison

Compare two heuristics for N-queens problem using RBFS method

How to create a good heuristics?

On a basis of the relaxed problems.

A problem with less restrictions on the operators is called a relaxed problem.

Formal rule: a tile can move from square A to square B if A is adjacent to B and B is blank

Three relaxed problems:

(a) A tile can move from square A to square B if A is adjacent to B

(b) A tile can move from square A to square B if B is blank

(c) A tile can move from square A to square B

Wrong place tiles

Manhattan distance

Initial state

Goal state

By solving a simpler task

How to get a best heuristics?

Get several admissible heuristics: H1(x), H2(x), ..., Hn(x)

Calculate a best one: H(x) = max( H1(x), H2(x), ..., Hn(x) )

Conclusions

Heuristics is a great and valuable idea!

Search strategy =

method + neighborhood + heuristics

Real life

For real life problems (NP-hard problems like TSP, knapsack, scheduling) even A* and its modifications will work too long.

So we need something else...

P.S. But don't forget about heuristics!

H2. Amount of pairs of queens that attack each other with the cases when two queens do not see each other

excluded

H1. Amount of pairs of queens that attack each other with the cases when two queens do not see each other

included

H1. Pairs of queens that do not see each other are

included

H2. Pairs of queens that do not see each other are

excluded

Running time limit: 60 sec

Heuristics is a great and valuable idea!

Search strategy =

method + neighborhood + heuristics

For real life problems (NP-hard problems like TSP, knapsack, scheduling) even A* and its modifications will work too long.

So we need something else...

Type of problems for today's section

We don't care about path. The only valuable thing is a goal state as it is.

Examples: traveling salesman problems, scheduling, competitive games

Main idea

Forget about search history.

Just use a current state and look for a best neighbor state hoping that it will lead you closer to your goal

Hill climbing

The simplest local search algorithm.

Select a best neighbor state in whole neighborhood to proceed with.

Optimization problems

Moreover we will talk about optimization problems, i.e. when we need to find an optimal solution (state).

For instance, take a TSP problem. Any state is admissible but only a few are optimal (compare with N-Queens problem).

Later we will clarify that it's OK to find a non-optimal but rather good solution.

The algorithm may not find a solution

Why "Hill climbing" ?

def

Hill-Climbing(problem):

current_point = make_node( initial_state( problem ))

while

True

:

neighborhood = current_point.get_neighbors( )

best_neighbor = neighborhood.find_the_best_neighbor( )

if

best_neighbor.value > current_point.value:

current_point = best_neighbor

else

:

return

current_point

It's for maximization problems

Who is the winner?

For minimization problem go to the southern hemisphere

Imagine you're a blindfolded alpinist (mountain climber) having serious troubles with remembering where you were at past. And you try to get on a highest Ukrainian mountain, Hoverla.

With such restrictions you'll probably find yourself in a nearest local hill (somewhere nearby our campus)

searching landscape

Solution cost

How can we avoid getting stuck in a local optimum?

There are several modification of Hill Climbing.

About more sophisticated approaches - after break.

Sidesteps

Allow the possibility to walk on "a plateau" making sidesteps hoping there will be another uphill.

Random walks

Do not select the best neighbor in the neighborhood but just good one - simply better than a current state

def

Hill-Climbing-With-Restarts(problem, number_of_restarts):

restart_number = 0

best_ever_found_node = current_point

while

True

:

current_point = make_node( problem.generate_state() )

while

True

:

neighborhood = current_point.get_neighbors( )

best_neighbor = neighborhood.find_the_best_neighbor( )

if

best_neighbor.value > current_point.value:

current_point = best_neighbor

else

:

break

if

current_point.value > best_ever_found_node.value:

best_ever_found_node = current_point

if

restart_number < number_of_restarts:

restart_number += 1

else

:

return

best_ever_found_node

Restarts

If we stuck in a local optimum try to restart the search from another initial solution. You need to memorize the best ever found optimum.

Hybrid local search

You can create any combination of these approaches:

Sidesteps

Random neighbor

Restarts

...

Beam search

Multiprocessing Hill Climbing.

Instead of enjoying one "blindfolded alpinist" use many of them!

def

Beam-Search(problem, number_of_beams):

for

i

from

1

to

number_of_beams:

current_point_list[i] = make_node( problem.generate_state( ) )

while

True

:

neighborhood = []

for

current_point in current_point_list:

neighborhood += current_point.get_neighbors( )

new_best_neighbors = neighborhood.select_best_nodes( number_of_nodes = number_of_beams )

if

new_best_neighbors is not empty:

current_point_list = new_best_neighbors

else

:

best_ever_found_node = new_best_neighbors.find_the_best_node( )

return

best_ever_found_node

Local search conclusions

Advantages

Disadvantages

Very fast

Almost doesn't use memory

Far from optimality

We cannot use a "magic rope" like with A*, right?

**Motivation**

Most of real life problems are very complicated (NP-hard or NP-complete):

Scheduling, Traveling Salesman, Knapsack...

So there are no algorithms for them that solve these problems efficiently (in polynomial time).

But for most of these problems it's OK to find a not optimal solution but a quite good one.

Why exponential time (memory) is so bad?

Take Traveling Salesman Problem

Optimal methods (branch-and-bound, branch-and-cut etc.) are working in exponential time

In worst case for TSP that are solved in acceptable amount of time the largest size is about 100-200 cities

To solve the problem with one more city you need to wait for a doubled amount of time

We call it a combinatorial explosion

Moore's law

The number of transistors on integrated circuits doubles approximately every two years. So does processing power.

If you are not developing new algorithms then you should wait for two years to add one more city to your problem.

What is a metaheuristic?

Compared to simpler heuristics, metaheuristics are more abstract procedures that use low-level heuristics or search algorithms.

They are the rules of how to “jump” from one solution to another in a searching space; how to accept the worse solutions in some way.

Metaheuristics' boom

1963 – Random Search

1965 – Evolutionary Strategy

1975 – Genetic Algorithms

1983 – Simulated Annealing

1986 – Tabu Search

1989 – Mimetic Algorithms

1992 – Ant Colony Optimization

2004 – Bee Colony Optimization

2007 – Intelligent Water Drops

2009 – Cuckoo Search

2011 – Galaxies Optimization

Tabu search

Main idea: memorize a number of previously visited states to deny immediate coming backs.

Denied states are stored in one tabu list or several lists (short-term, middle-term, long-term).

Tabued states

def

Tabu-Search( problem, tabu_list_limit ):

current_point = make_node( initial_state( problem ))

tabu_list = [ current_point ]

while

True

:

neighborhood = current_point.get_neighbors( )

best_node = EmptyState( )

for

neighbor

in

neighborhood:

if

neighbor.value < best_node.value

and

neighbor

is not in

tabu_list:

best_node = neighbor

if

best_node

is

EmptyState( ):

break

current_point = best_node

tabu_list.append( current_point )

if

tabu_list.length( ) == tabu_list_limit:

tabu_list.remove_oldest_node_from_list( )

return

current_point

Simulated annealing

The name and inspiration come from annealing in metallurgy - heating and controlled cooling of a material to increase the size of its crystals and reduce their defects.

This notion of slow cooling is implemented in the method as a slow decrease in the probability of accepting worse solutions as it explores the solution space.

It's like a shaking pinball table while hoping that ball will jump to a better place

Or like a quaking of a searching landscape hoping to accelerate our blindfolded alpinist.

Metaheuristics could be very efficient

Overall amount of generated nodes and maximum amount of nodes in memory

- Unsolved instances of problem

Running time limit: 60 sec

Running time of Tabu search for N-queens problem

Other methods gave up at size < 20

50-queens by Tabu search

But their tuning is a true science

Metaheuristic's parameters

Neighborhood strategy

Take a TSP tour. What are the possible neighborhood rules?

Tabu list length limit for Tabu Search

Probability function that depends on temperature for Simulated Annealing

One-Point rule

Take a city and change its position in a tour

5 - 1 - 3 - 4 - 2 - 5

5 - 3 - 4 - 1 - 2 - 5

Two-Point rule

Take two cities and swap their positions in a tour

5 - 1 - 3 - 4 - 2 - 5

5 - 2 - 3 - 4 - 1 - 5

Two-Opt rule

Take two edges and replace them with two new edges in a tour

5 - 2 - 3 - 4 - 1 - 5

1 - 2 - 3 - 4 - 5 - 1

And you can use them in different combinations

Many different metaheuristics are copying nature:

Ant colony optimization

Bee colony optimization

Genetic algorithms

Natural Water Drops algorithm

etc.

So go to talk to people from Neuro Science stream

Conclusions

Creating and using the metaheuristics is true science and art.

They are one of the several mechanisms that can help us with really hard problems

But beware!

"Enormously many metaheuristic methods have been published with claims of novelty and practical efficacy. Unfortunately, many of the publications have been of poor quality; flaws include vagueness, lack of conceptual elaboration, poor experiments, and ignorance of previous literature."

en.wikipedia.org/wiki/Metaheuristic

Talk about this things with people from OR strem

def

Simulated-Annealing(problem, temperature_function, probability_function):

current_point = make_node( initial_state( problem ))

for

time = 1

to

infinity:

temperature = temperature_function( time )

neighborhood = shuffle( current_point.get_neighbors( ) )

new_node = EmptyState( )

for

neighbor

in

neighborhood:

delta = neighbor.value - current_point.value

if

delta < 0:

current_point = neighbor

continue to new temperature

probability = probability_function(delta, temperature)

if

probability > random_probability( ):

current_point = neighbor

continue to new temperature

if

no new_node was found:

return

current_point

Probability = F( Temperature )

**Search paradigm applications**

What is planning?

Planning is the process of thinking about and organizing the activities required to achieve a desired goal.

We can describe a planning task in terms of searching problems. How?

Missionaries and cannibals problem

Three missionaries and three cannibals must cross a river using a boat which can carry at most two people.

For both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals.

If they were, the cannibals would eat the missionaries.

The boat cannot cross the river by itself with no people on board.

The Dock-Worker Robots

There is a seaport with different sites (locations), ships, pallets, containers, cranes, trucks. The object is to find a plan of loading/unloading cargo containers from ships to pallets, and from pallets to trucks.

Planning in robotics

In the field of robotics planning

is a critical issue.

Shakey the robot

Shakey the robot was the first general-purpose mobile robot to be able to reason about its own actions.

Created during 1966-1972

Planning everywhere

Solve planning tasks via searching

State is some snapshot of the problem domain.

Neighbors are obtained with different possible actions (moving, turning, etc.)

Then a plan is a path in this space from an initial state to a goal state.

State is some plan that includes a sequence of actions that change behavior of the problem domain.

In this case you need to find an overall plan (some goal state in searching space) without storing the path through states.

Neighbors are obtained by actions on a partial plans.

Recover two types of searching problems

You can use any proper searching method we've studied (BFS, DFS, A*, Greedy, ...)

But special algorithms are existed for this purposes. Especially when working with partially created plans (GraphPlan, Partial-Order Planning etc.)

Competitive games

You can imagine a game like a problem of finding a plan that will lead you to your victory.

Can you use any of the previously presented algorithms for games (uninformed, informed, local)?

No, because we do not control the whole process. There are opponents that can ruin our optimal path (plan).

We need to take into account their possible reactions.

Game as a search problem

State is a description of some situation on a board.

Neighbor is another situation that is obtained by some allowed move in a game.

To build a plan that will allow you to win you need to think instead of your opponent as well.

Tic-tac-toe

Min-Max (minimax) algorithm

Introducing two players: MAX (you) and MIN (opponent).

MAX wins if the game is over and overall score is greater than 0. MIN wins if the score is less than 0.

We need to find an optimal strategy. That is when our opponent doesn't do mistakes we still win.

Main idea

Everytime choose a move with best minimax value that is the score you gain while your opponent doesn't mistake.

MAX

MIN

3

12

8

2

4

6

14

5

2

3

2

2

3

def

Minimax-Value( node ):

if

terminal-test( node ):

return

utility( n )

elif

node

is

MAX-player:

successors = node.get_successors( node )

return

max

( Minimax-Value(s)

for

s

in

successors )

elif

node

is

MIN-player:

successors = node.get_successors( node )

return

min

( Minimax-Value(s)

for

s

in

successors )

def

Minimax-Decision( state ):

neighborhood = state.get_all_neighbors( )

best_value, best_neighbor = -float('inf'), None

for

neighbor

in

neighborhood:

neighbor_value = min_value( neighbor.get_state( ) )

if

best_value < neighbor_value :

best_value, best_neighbor = neighbor_value, neighbor

return

best_neighbor.action( )

Main function

def

Max-Value( state ):

if

Terminal-Test( state ):

return

Utility( state )

max_value = -float('inf')

neighborhood = state.get_all_neighbors( )

for

neighbor

in

neighborhood:

max_value =

max

( max_value, Min-Value( neighbor ) )

return

max_value

Function for MAX-player

def

Min-Value( state ):

if

Terminal-Test( state ):

return

Utility( state )

min_value = float('inf')

neighborhood = state.get_all_neighbors( )

for

neighbor

in

neighborhood:

min_value =

min

( min_value, Max-Value( neighbor ) )

return

min_value

Function for MIN-player

from kalah/methods/minmax.py

from kalah/methods/minmax.py

from kalah/methods/minmax.py

Problems with Minimax

Behaves like DFS-BFS, i.e. builds whole "decision" tree.

For real games (chess etc.) is not acceptable because of size of the tree.

We should use heuristics for...

...Terminal-Test function to decide whether to stop tree expanding or not

...Utility function to be able to calculate utility values for non-finished nodes

Heuristic attack

These are the most critical parts of all gaming algorithms

Alpha-Beta Pruning is used to cut-off some unpromising branches of the searching (decision) tree.

In theory it could speed up the whole method run in two times

Recommended books

by Stuart Russell & Peter Norvig

aima.cs.berkeley.edu

Artificial Intelligence

A Modern Approach

Essentials of

Metaheuristics

by Sean Luke

cs.gmu.edu/~sean/book/metaheuristics/

Available online for free

Handbook of

Metaheuristics

Edited by

Michel Gendreau,

Jean-Yves Potvin

olexiim @ gmail . com

Congratulations!

Thank you for your attention!