Page 180 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes

Notes Algorithms for these problems include the basic brute-force search (also called
“naïve” or “uninformed” search), and a variety of heuristics that try to exploit partial
knowledge about structure of the space, such as linear relaxation, constraint generation,
and constraint propagation.

This class also includes various tree search algorithms, that view the elements as vertices of a
tree, and traverse that tree in some special order. Examples of the latter include the exhaustive
methods such as depth-first search and breadth-first search, as well as various heuristic-based
search tree pruning methods such as backtracking and branch and bound. Unlike general
metaheuristics, which at best work only in a probabilistic sense, many of these tree-search
methods are guaranteed to find the exact or optimal solution, if given enough time. Another
important sub-class consists of algorithms for exploring the game tree of multiple-player games,
such as chess or backgammon, whose nodes consist of all possible game situations that could
result from the current situation. The goal in these problems is to find the move that provides
the best chance of a win, taking into account all possible moves of the opponent(s). Similar
problems occur when humans or machines have to make successive decisions whose outcomes
are not entirely under one’s control, such as in robot guidance or in marketing, financial or
military strategy planning. This kind of problem – combinatorial search – has been extensively
studied in the context of artificial intelligence. Examples of algorithms for this class are the
minimax algorithm, alpha-beta pruning, and the A* algorithm.

9.4.1 Hill Climbing Methods

Hill climbing is a mathematical optimization technique which belongs to the family of local
search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then
attempts to find a better solution by incrementally changing a single element of the solution. If
the change produces a better solution, an incremental change is made to the new solution,
repeating until no further improvements can be found.

Example: Hill climbing can be applied to the travelling salesman problem. It is easy to
find an initial solution that visits all the cities but will be very poor compared to the optimal
solution. The algorithm starts with such a solution and makes small improvements to it, such as
switching the order in which two cities are visited. Eventually, a much shorter route is likely to
be obtained. One of the problems with hill climbing is getting stuck at the local minima and this
is what happens when you reach F. An improved version of hill climbing (which is actually used
practically) is to restart the whole process by selecting a random node in the search tree and
again continue towards finding an optimal solution. If once again you get stuck at some local
minima you have to restart again with some other random node.
Generally, there is a limit on the no. of time you can re-do this process of finding the optimal
solution. After you reach this limit, you select the least amongst all the local minima’s you
reached during the process. Though, it is still not complete but this one has better chances of
finding the global optimal solution. Hill climbing has no guarantee against getting stuck in a
local minima/maxima. However, only the purest form of hill climbing doesn’t allow you to
either backtrack. A simple riff on hill climbing that will avoid the local minima issue (at the
expense of more time and memory) is a tabu search, where you remember previous bad results
and purposefully avoid them.

174 LOVELY PROFESSIONAL UNIVERSITY