Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

Search:

CA216      CA249      CA318

CA400      CA651      CA668


Search


AI

The field of Artificial Intelligence (AI) can be defined in many ways (e.g. trying to model human intelligence, or trying to solve human-level problems by any means even if quite unlike how humans do it).

But one definition is:

Obviously the programmer must do something to get this discovery process started.


Search

The standard way of achieving this is to frame the AI problem as a search problem:
  1. Define a "space" of all possible solutions.
  2. Define an algorithm to search that space for a good solution.
If the "space" is small enough, it may be searched exhaustively until we are sure we have the best solution.



Heuristic

The interesting (and common) scenario is when the space is too big to search exhaustively. That is, in any finite experiment (and all experiments are finite) we can only ever search part of the space. In this case, we usually have to give up any guarantee of finding the best solution. Instead the standard strategy is:
  1. Define a "heuristic" rule to search the space. This is a "rule of thumb" that does a smart search of the space in the finite time available. Gives a good answer most of the time, but no guarantee it won't fail in some situations.

  2. Needs an Evaluation function of how good a solution is.
    1. This may be well-defined (the solution solves the problem and receives some score).
    2. Or the evaluation function itself may be a heuristic. (e.g. The "solution" generated is the next move in a chess game, that is, a mere step on the way to the ultimate win-lose score. How "good" is it to reach one given half-way position in chess versus another?)


Types of heuristic

So we may have:
  1. Heuristic search algorithm.

  2. Heuristic evaluation function.
These are different types of thing!


Example of a heuristic search algorithm

  1. Initialise with 20 random solutions.
  2. Repeat:
    1. Pick the best 10.
    2. Make small changes in them, and generate a new pool of 20 candidate solutions.
    3. Loop.
Is this a good heuristic? Consider if an apparently good (better than its local neighbours), but sub-optimal (compared with the global best) solution is easy to find at the start. This could easily converge on 10 similar variants of it.



Local and Global Optima



An easy-to-find local maximum and a harder-to-find global maximum.
X-axis - The solution.
Y-axis - The fitness of the solution.
Find solution with max fitness.

Consider starting with a random x and then trying to improve it.
It is easy to get (by chance) onto the slopes of the local maximum, and then repeatedly make changes in x looking for an improvement, until you get to the local maximum. The local maximum is very "visible".
Whereas unless you start (by chance) near the global maximum you may never find out it is there.

Many heuristics might find the local maximum but not the global one.
In fact, anything other than exhaustive search would be at risk of finding the local maximum but not the global one.


The global maximum could be arbitrarily hard to find:




Heuristics in a computer problem: Chess


Deep Blue




Heuristics in life

While it seems bad to have a rule that may deliver a sub-optimal solution and cannot guarantee finding the optimal one, this is just normal in human (and animal) life.



Sample heuristic: Mate choice




Mate choice heuristic in birds: Mating dances.



Mr. Darcy explains to Elizabeth that she is in at least the top 100 million people for him worldwide.
Maybe even the top 10 million.
Image from here.




Sample heuristic: Packing your car for holiday


It is proven that these problems need to be solved by heuristics



Heuristic Search as a general-purpose, useful, computer algorithm

Even if one is not interested in AI or classic AI problems, the concept of defining a solution space and using a smart heuristic to search it is just a general-purpose useful addition to the toolkit of any computer software developer.


Metaheuristics



Continuum

More domain-specific tweaking
More work for human



Domain-specific heuristic
Non-random search of the space
Guided by domain-specific knowledge
|
|
Metaheuristic
Non-random search of the space
But no domain-specific knowledge
|
|
Random search
Random search of the space
Works ok if space small



Less domain-specific
Less work for human


Feeds      w2mind.org

On Internet since 1987.