Why does the design of heuristics require considerable domain knowledge?

Question

I am from a machine learning (ML) background and am interested in how ML is applied to Combinatorial Optimisation. As such, as I have been reading around the area and have come across the statement that essentially states 'designing heuristics requires considerable domain knowledge'.

For instance, in this paper they make the statement "Nonetheless, the design process of such heuristic methods requires specialized domain knowledge and involves trial-and-error as well as tuning".

Further, in this paper they say "However, the effectiveness of general algorithms is dependent on the problem being considered, and high levels of performance often require extensive tailoring and domain-specific knowledge".

Neither of these papers provide references to support such a statement so I am wondering what kind of domain knowledge they are referring to? Based on the papers that I have read where new CO heuristics are introduced, it seems that the 'domain knowledge' is a good understanding of the problem (e.g. TSP) and being good at the math required to prove bounds on the solution qualities, search strategies, etc.

Also, it doesn't seem like any extra requirement on domain knowledge is required compared to if you were developing an algorithm for some other field (e.g. an ML algorithm!); in general I would argue that to develop an algorithm to solve a problem you would have to have pretty good knowledge of the area you're developing the algorithm for, that shouldn't be specific to CO.

I was wondering if anyone could provide some insight into these comments, please.

Answer 1

The following is largely opinion/conjecture on my part. Many (though not all) heuristics involve neighborhood search. For that type of heuristic to be effective, you need "neighborhood" to be defined in a way that is both computationally convenient (moving from one solution to a "neighboring" solution is straightforward and does not involve solving an NP-nasty subproblem) and meaningful in terms of the objective. The latter boils down to defining neighborhoods so that a neighborhood of a good solution is likely to contain a better solution. If good and bad solutions are uniformly scattered around neighborhoods, neighborhood search is no better than random search. The ability to figure out a good definition of "neighborhood" may require some domain knowledge (understanding of the particular problem).

Similarly, the efficacy of evolutionary metaheuristics such as genetic algorithms depends on how solutions are encoded (the "chromosome" in a GA), and possibly on how crossover, mutation and other operators are defined. You want crossover of two "good" solutions to be likely to produce a better solution, and mutation of a "good" solution to have a decent chance of producing a better solution. Otherwise, again, the metaheuristic just turns into an overengineered version of random search. Finding an effective encoding can require some understanding of how the objective value depends on "chunks" of the solution, which again is a form of domain knowledge.

Answer 2

tl;dr– Having relevant knowledge can help folks come up with better techniques, including heuristic techniques.

---

Relevant knowledge can be useful in problem-solving.

Heuristic techniques are those that're somehow fuzzy/approximate/unreliable. The term "heuristic" is basically a disclaimer, qualifying that a technique isn't ideal.

Relevant knowledge (domain-knowledge) can help folks come up with better problem-solving techniques, including heuristic problem-solving techniques.

---

Example: Heuristic for video-games.

Say you're playing a video-game that you really like and a newbie asks you for advice. Without considering their exact situation, could provide them with some general advice that'd help guide in the right direction?

That'd be a heuristic, and presumably having known about the video-game helped enable you to provide a better one. The more you know about what's possible, various benefits/costs, gains/risks, etc., the more tools you have to help craft better heuristics (better advice).

Unless it's a solved game, where you can recommend a perfect strategy. Then you'd be giving them a non-heuristic solution rather than a heuristic solution.

Answer 3

Heuristics are "rules of thumb" that in some cases try to estimate some quantity without explicitly computing it. The better the estimate, the better the algorithmic performance, so good heuristics are important. Domain knowledge can help to improve estimates by understanding what is possible or reasonable. Take A* search, for example, which can be used to find a minimum-length path between two points, which requires a heuristic estimate of the remaining distance to the goal. The closer the estimate is the true remaining distance, the faster the algorithm will run, but the heuristic should not overestimate. A decent place to start with the heuristic is the straight-line Euclidean distance between two points. But if you know the agent can only move along a grid, one can use that domain knowledge to instead use the Manhattan distance for a more accurate estimate. Maybe there are spots on the grid that are hard to traverse and come with extra cost, further allowing you to tune the heuristic. The more you know about your domain, the closer the heuristic will reflect the situation it actually describes.

Other simple heuristics come from knowing where to look in the first place. Machine learning in high-dimensional data is often difficult, can be prone to overfitting, and can have issues with multiple hypothesis testing. But if your domain knowledge allows you to exclude many features as irrelevant, the problem becomes muh simpler. Poor prior knowledge will have you eliminate truly meaningful features, but good domain knowledge will allow you to reduce the features space to a smaller number of useful dimensions.