MetaHeuristic Search

From Algorithmist
Jump to navigation Jump to search
This is a stub or unfinished. Contribute by editing me.

Metaheuristic Search[edit]

A metaheuristic search is a non-exhaustive search algorithm with an internal heuristic

Look to heuristics for examples of heuristics.

The problem with exhaustive searches is that they take up so much time. An exhaustive search has to compare the search term with every entry in the search list. This means that the minimal time for the Search is 2N where N is the number of entries to search times the number of clock cycles per command, divided by the number of clock cycles per second. Few searchs can reach anywhere near this performance performance being more likely to be somewhere around N2 or logN2

But, what if data tended to come in bunches of similar values separated by large areas of different values? Does it really make sense to search the broad areas of values that can't possibly be the right value?

If we could wouldn't we be happier only searching the similar values, and not searching the values that aren't anywhere near similar?

Well that might be an ideal, which is impossible to meet if only because we don't know anything much more than were to look for the data, and what to search for. But we might be able to cheat a little and get almost that effect, if we used a strategy called a heuristic that explored for neighborhoods in which values similar to the search term can be found, and then did a more intensive search in the neighborhoods that were most likely to contain the search term.

Metaheuristic searches are therefore often hibrid searches where the first search identifies neighborhoods that might be valid locations for the search term, and the second search intensifies the search in order to find the exact right answer. There is only one problem with this search technique, and that is that it might skip over the right answer, simply because it wasn't in any of the neighborhoods it searched.

Given an intensive search of the complete list, we will almost always get the right answer. Given a metaheuristic search, in much less time we will get an answer that while not the correct answer, is correct enough that little difference can be seen. So a meta-heuristic search is an inexact search that gives us approximately the right answer. Obviously they can only be substituted for each other, when time is not a factor, and accuracy is less important. Otherwise use the intensive search where accuracy is more important and the metaheuristic where time is more important.