//
you're reading...
Algorithms & Heuristics

Introduction to Algorithms, Heuristics and Meta-heuristics

At school I was always confused between Algorithms and Logarithms…Anagrams were meaningful later. Then I encountered heuristics and lately meta-heuristics. I tried to differentiate algorithms, heuristics and meta-heuristics. Additional words such as methods, steps and instructions also joined the fray.

A simple definition of algorithm – Wikipedia defines it as – “it is an effective method expressed as a finite list of well-defined instructions for calculating a function”. See here

Some key characteristics emerges

  • Finite list – a stricter opinion requires algorithm to have a finite set of actions.
  • Stopping criteria – An algorithm is expected to elegantly stop and not go on forever. There is also a debate on what an effective method means and lot has been written on this in terms of evaluation of an algorithm.
  • Solution Guarantee – A solution is always guaranteed and is the correct one.

Heuristic on the other hand, while not an algorithm, is nonetheless a very interesting concept. Wikipedia defines it as – “experience-based techniques for problem solving, learning, and discovery”. See here

There is a concept of “admissible heuristic” that assumes the data set used for arriving at the heuristic is really representative of the real data.
There could be many stopping criteria and also there may not be a guarantee of any result.

While meta-heuristics can be simply seen as a higher level heuristics, it is not a very clear formal difference between them. However there are two definitions that may help the reader.

  • I. H. Osman and G. Laporte “An iterative generation process which guides a subordinate heuristic by combining intelligently different concepts for exploring and exploiting the search space”.
  • S. Voss et al. “is an iterative master process that guides and modifies the operations of subordinate heuristics to efficiently produce high quality solutions”.

Wikipedia has an interesting diagram which attempts to classify the same. See here

Why not algorithms?
The primary reason many resort to a heuristic or a meta-heuristic is due the long time taken by algorithms. This is true when the problem is complex and the search space for the solution is very large and grows exponentially.

In business applications it is not often required to arrive at the true optimal solution. In practice there is always a concept of acceptable solutions. This is due the valuation of time that the computer or the person takes to arrive at the solution. If someone is interested in a job shop scheduling problem, it may not be feasible to wait even couple of hours to get the best solution. On the other hand it may be okay to get an acceptable solution within minutes which meets some critical business conditions.

I intend to add a follow up blog on some interesting meta-heuristics such as Ant Colony Optimisation & Genetic Algorithms.

Advertisements

Discussion

One thought on “Introduction to Algorithms, Heuristics and Meta-heuristics

  1. Thanks for posting…by making it as simple as possible ….pointing it out these two should be compared( 😦 i dont rememeber me co-relating heuristic and algorithm)

    Posted by Mahadevan.p | February 13, 2012, 10:23 am

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 66 other followers

%d bloggers like this: