2
$\begingroup$

I have investigated the literature, but I could not find proper explanations. As we know, (meta-)heuristics try to explore promising regions of optimality. The regions are then exploited.

What is the definition of the promising regions in (meta-)heuristic optimization? How can we determine whether the algorithm is in the promising region or not, especially for the problems with unknown optima?

My idea is only that if the algorithm shows continuous improvement, we can say that the region is found. But I am not sure if my idea is totally correct.

$\endgroup$
3
  • $\begingroup$ a region is promising if the objective function is decreasing in this area (if you are minimizing). As an analogy, if you are looking for the lowest point in a mountain range, a valley is a promising area. $\endgroup$
    – Kuifje
    Oct 21 at 6:55
  • $\begingroup$ But the same definition can be applicable to the condition of local minima(LM): the algorithm converges to a point, which is LM, that is, the fitness value decreases, but it can get stuck in the LM. If we do not know what the optimal value is, we can consider the candidate solution of the algorithm in the LM as the optimal, but the fact is that this is not a promising region. Because both when the optimal solution is reached and when the LM is trapped, the fitness function will not decrease further. So I think we need more than the term "decreasing" for the explanation. $\endgroup$
    – YcK
    Oct 21 at 7:23
  • $\begingroup$ Well, thats what meta-heuristics are all about: finding promising regions but not getting stuck there. $\endgroup$
    – Kuifje
    Oct 21 at 8:11
4
$\begingroup$

The concept of promising regions (unlike many other concepts in optimization) doesn't have a mathematical definition. It is more an analogy people use to justify why exploring some¹ neighborhood of good solutions leads in practice to other good solutions in particular in derivative free optimization.

Different algorithms that exploit promising regions also exploit different things. The crossover heuristic in evolutionary algorithms which combines components of two solutions finds the result promising because assuming the objective is separable in those variables the new assignment is going to have a low value in the separate objectives². Particle Swarm Optimization instead suggest that the space between the best know and the current position of a particle is likely to yield improvements but the local optima close to the particle it knows about also should be exploited.

¹by some I mean it doesn't have to be close with regards to $\|\cdot\|_2$ or a similar metric as the crossover example shows

²Assume we minimize $f(x,y)=g(x)+h(y)$ if $x_1,y_1$ and $x_2,y_2$ are good but $g(x_1)<g(x_2)$ but $h(y_1)>h(y_2)$ then $x_1,y_2$ is going to be better. In practice this separability is not known by evolutionary algorithm but if $x_1,y_1$ and $x_2,y_2$ stay successful in the next generation because the worse $x_2,y_1$ was generated there is again a 50% chance of $x_1,y_2$ being generated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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