9
$\begingroup$

Improvement heuristics for the TSP like 2-Opt need construction heuristics (also called constructive heuristics) like the Nearest Neighbour to start. Intuitively, I would say that a better construction heuristic leads on average to better results for the improvement heuristic. I think this is difficult to prove because a worse initial solution could nevertheless lead to the global optimum. Is there a prove or anything else that makes a statement about the dependency of the quality of improvement heuristics and construction heuristics?

Or more generally speaking: Do better-starting solutions lead to better performances of improvement heuristics?

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ I would say that no relation can be established between the two. In fact your statement 'better construction heuristics' depends on the instance. One can artificially build an instance such that nearest neighbor may perform better. Your question is maybe 'is a better initial solution leads to better performance by the improvement heuristic'? $\endgroup$
    – MarcM
    Commented Sep 3, 2021 at 10:56
  • $\begingroup$ I think that for a special instance Nearest Neigbour performs better than e.g. Christofides. Nevertheless, Christofides performs on average on a big number of instances that are not manipulated "better"than Nearest Neighbour. Overall, it is true that the question that follows is: "Do better starting solutions lead to better performances of improvement heuristics" I add this to my question. $\endgroup$
    – maxmitz
    Commented Sep 3, 2021 at 11:49

5 Answers 5

Reset to default
8
$\begingroup$

There are some proofs of the contrary: whatever the starting point, your local search can be stuck in solutions far away from the optimum. Here "local" means that each iteration must be done in polynomial time. Check the seminal paper "On the Complexity of Local Search for the Traveling Salesman Problem" by Papadimitriou and Steiglitz on this topic.

As usual, in practice, things are much different than in theoretical worst-case analysis. Initial solutions can have a huge impact on the quality of the solutions reached by neighborhood search. In particular, a general practical observation is: the more your neighborhoods are small, the more your diversification strategy is poor, the more the combinatorial landscape is rugged, then the more initial solutions are critical in reaching high-quality solutions.

Improve this answer
$\endgroup$
3
$\begingroup$

I am not aware of such proof. I think your question may be meaningful given a specific improvement heuristic. For example, I worked on solving large scale VRP problems using genetic algorithms as the meta-heuristic and doing local search to improve solutions. In this case, randomly generated initial solutions performed much better for me than using well-crafted construction heuristics. However, when using Large Neighborhood search, good quality initial solution gave better results. So I personally like to think that the construction + improvement heuristic are different parts of the same algorithm. And in this case, benchmarking multiple construction heuristics as suggest by @worldsmithhelper is the way to go.

Improve this answer
$\endgroup$
2
$\begingroup$

Because most of the answers state that construction heuristics do not improve the quality of improvement heuristics, I want to share a paper that contradicts.

The paper "First vs. best improvement: An empirical study" observes in its experiments for the TSP that "starting with 'greedy' or 'nearest neighbor' constructive heuristics, the best improvement is better and faster on average".

Improve this answer
$\endgroup$
1
$\begingroup$

There is a mathematically justified way of saying is better than the other. The expected time to solve over all problems. When the expected value can't be computed over the distribution of problems you care about you can sample that space and run both approaches for both. This is called benchmarking and with sufficient samples the benchmark numbers will converge against the expectation values.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Different from continuous problems or solving by exact methods. In improvement heuristics, local optima are defined w.r.t the neighborhoods exploited by the heuristic. That means depending on the type of operators used in the improvement heuristic, a solution can, or cannot be local optimum. Hence, an initial solution can or cannot be better for the heuristic. So the general case is hard to prove. However, picking a specific improvement heuristic and benchmarking multiple construction heuristic can be meaningful in this case. $\endgroup$
    – MarcM
    Commented Sep 3, 2021 at 12:23
  • $\begingroup$ @MarcM You should have written an answer as you clearly know more than me. $\endgroup$
    – worldsmithhelper
    Commented Sep 3, 2021 at 13:05
1
$\begingroup$

Adding to the answer of @MarcM, there is the reason, in addition to specific heuristics, which is the given problem type, especially real-world scenario whose search space is so huge or unknown. Besides, the No Free Lunch theorem says that there is no universal optimization algorithm to solve every kind of optimization problem. In other words, the better initial solution cannot show the same percentage of the improvement for each heuristics. This means if the knowledge of the problem is not available a priori, there is still a lack of an answer to which improvement method most accurately affects which types of problems. Even if there are some studies in the literature, the studies generally have used a limited number of problems and also algorithms. I thought that it can be an answer for only specific problems and algorithms. I also think that without implementation, no one says the 2-opt heuristic is better than sweep, saving, 2-opt*... initializations to NN for TSP.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ The No Free Luch theorem holds for every kind of optimisation problem. I asked especially for the TSP. The TSP is one specific optimisation algorithm. I think at this point the argument is not conclusive. $\endgroup$
    – maxmitz
    Commented Sep 22, 2021 at 10:37
  • $\begingroup$ NFL is the part of the explanation which refers that 2-opt heuristic cannot achieve the optimal solution for each kind of TSP, also does not give the guarantee that " better initial solution always a better final solution" for all TSP instances, the algorithm can have stagnation or can convergence to the same point with or without 2-opt for one of the TSP instances. $\endgroup$
    – YcK
    Commented Sep 22, 2021 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.