Difference between heuristic function and evaluation function

Question

I'm reading about searching algorithms and heuristic search and I am slightly confused about heuristic and evaluation functions. People seem to use them quite freely to describe seemingly same things. What am I missing?

Answer 1

A heuristic function simply determines the next node to expand based on the least cost, it does not see if the expanded frontier leads to a goal state. Hence, it may sometimes lead to an infinite loop or a longer path(because it may lead to a dead end). On the other hand, the evaluation function is a more robust estimation function that estimates the next node to expand that actually leads to a goal state with the least cost. The heuristic function is a part of the evaluation function.

Answer 2

There can be confusion around this issue because heuristics mean different things in different contexts. So, let me talk about the different meaning of heuristics. Then we can return to evaluation functions.

Single Agent Heuristic Search

In single-agent heuristic search (eg A*, IDA*) heuristics are usually qualified with the words admissible or consistent. In this context heuristics are lower bounds on the cost to reach the goal. That is, they are the result of a function which returns a numerical value. If the heuristic is admissible, the value returned does not overestimate the true distance to the goal. If the heuristic is consistent, the heuristic between adjacent states never changes more than the edge cost. Consistent heuristics are admissible if the goal has a heuristic of 0, but not all admissible heuristics are consistent.

There are many properties proven on the combinations of heuristics and algorithms. A* and IDA* will find optimal paths with a consistent heuristic. A* is optimal in necessary node expansions with a consistent heuristic, but with a inconsistent heuristic A* can perform 2^N expansions of N states. (See this demo for an example of where this occurs.)

Game Playing

In game playing programs using algorithms like alpha-beta or Monte Carlo tree search (MCTS), heuristics represent approximations of the win/loss value of a game. For instance, the value might be scaled between -1 (loss) and +1 (win), with values in between representing uncertainty about the true value. Here there are no guarantees on underestimate or overestimation, but the better ordering of values (wins > draws > losses) the better the performance of the algorithms. Alpha-beta pruning will return the same result even if an affine transform is applied to the heuristic, because alpha-beta uses the relative ordering of values to search. See, this paper for an example of heuristics in MCTS. Note that in this context a heuristic still has a numerical value.

Optimization

In search for optimization problems like SAT (satisfiability problems) or CSP (constraint satisfaction problems), algorithms are much more efficient if they can find good solutions quickly. Thus, instead of searching in a naive manner, they order their search in a way that is expected to be more efficient. If the ordering is good the search might be able to terminate earlier, but this isn't guaranteed. In this context a heuristic is a way of ordering choices that is likely to end up with finding a solution more quickly. (A satisfying assignment of variables in SAT or in a CSP.) Here is an example of work that explores different ordering heuristics for these problems.

In this context a heuristic is used for ordering, so it doesn't have to be numerically based. If it is numerically based, the numbers would not necessarily have global meaning as heuristics do in other types of search. There are many, many variants of optimizations problems besides SAT and CSP where heuristics are used in this manner.

Evaluation Function

So, then, what is an evaluation function? It is probably most commonly used in the second context of games, where heuristic and evaluation function can be interchanged, but it is more generally referring to the numerical evaluation of a state. The primary point would be that an evaluation function is more specific than a heuristic function, as a heuristic has broad use in wider contexts.

Answer 3

Simply saying, an evaluation function will provide you values which will be needed to solve a problem. But it won't tell you which branch to expend first in tie cases. So in worse cases you may need to expand the whole search tree which is quite time consuming.

Again heuristic function can be compared with a "hint". When added with or used along with an evaluation function it will help you decide where to expand the branch first to reach to the solution soon. Although they may not work well in some cases but in most cases it will significantly decrease the run-time by guiding you which branch to expand first because that branch is supposed to be more promising to give you the result soon or the branch has more probability to have the solution.

Answer 4

A heuristic function is a component of the evaluation function. An evaluation function estimates the cost of the cheapest solution through the given node, possibly taking into account more information about the node than just the state. A heuristic function also takes a node as input, however it's value only depends on the state at that node.

Using the example of A* search, the evaluation function estimates the cost of the cheapest solution through node n, written as:

f(n) = g(n) + h(n)

Where g(n) is the cost to reach the node n, and h(n) is the estimated cost of the cheapest path from n to the goal.

In other cases, the evaluation function may not utilize any additional information other than the heuristic function. I.e. f(n) = h(n).

Answer 5

the heuristic function is problem specific and encodes the distance to the nearest goal node. whereas the evaluation function is not problem specific and is used by the algorithm to determine which node to expand next.

Answer 6

An evaluation function (or score function) checks if a solution is feasible and how good it is. By comparing the score of 2 solutions, you can see which one is better (if they are both feasible). For example: if you go from Brussels to Madrid through Paris, Lyon and Marseille the distance is 1000 km (= the actual road distance).

A heuristic function also returns something like a score, but it works on a partial solution and it doesn't need to be accurate. For A* search it needs to be admissible (= underestimating). For example: If you go from Brussels to Madrid through Paris (and the rest you don't know yet), the distance is 800km (= the actual road distance from Brussels to Paris plus the as-the-crow-flighs distance from Paris to Madrid).