What is the process of Local Search optimization and what is its main limitation?

Conditions

• Requires an initial feasible solution.
• Requires a defined neighborhood of solutions (e.g., all solutions reachable by one 2-Opt swap).
• Iteratively moves to a better solution in the neighborhood until a local optimum is reached.

Reasoning, step by step

1. Start with an initial solution (e.g., a random route).
2. Apply a local change (e.g., a 2-Opt swap).
3. If the change improves the solution, keep it; otherwise, discard it.
4. Repeat the process until no further immediate improvements can be found.
5. Recognize that the final solution is a local minimum, not necessarily the global optimum.

Example

The video demonstrates Local Search on a map with approximately 30 cities, starting from a random route of 44668 km and iteratively improving it to 16592 km, but notes that a better route of 14167 km exists, illustrating the local minimum limitation.

Common misconceptions

• Believing that Local Search always finds the global optimum.
• Assuming that if no immediate improvement can be found, the current solution is the best possible one.

Watch the explanation

Explore next

• How does Simulated Annealing help avoid getting stuck in a local minimum?
• What is a local minimum in the context of optimization?
• How does a 2-Opt swap work to improve a route?