If the algorithm is very greedy (e.g. local search), then restarts of that algorithm might resemble a memetic algorithm. Let's consider a memetic algorithm with a very expensive local optimization technique -- we would like to run the local optimizer less often, so we might want to filter the starting points. This can be difficult since a start point with a good fitness evaluation might not have that much more room for improvement. So, what we need are ways to estimate the room for improvement for a given (e.g. completely random or somewhat random) solution.
I'm primarily interested in continuous search spaces. Given two solutions x1 and x2, is there a way to find out/estimate the probability that the (local) optimum near x1 is better than the local optimum near x2 when f(x1) is worse than f(x2)?
1) In reference to the restarts, I understand you make reference a multi-start methods. In this case, I can tell you that my previous experience says that multi-start strategies are particularly interesting when applying meta-heuristics with a single solution, while this strategy is not so good when applying population-based approaches. The reason is that if, for example, you apply Simulated Annealing, the search process could be performed during a given number of iterations, after which you could store the best solution found, and execute again Simulated Annealing with a different initial solution. Other option, would be re-start the parameters of Simulated Annealing and continue the search process from the point at which finished the previous execution of Simulated Annealing. On the contrary, if you apply a population-based meta-heuristic (e.g. an evolutionary algorithm, memetic algorithm, etc.) the use of different initial solutions in each individual would be almost equivalent to appliy a multi-start / re-start strategy.
2) In reference to the last question, and supposing that the problem to be solved is NP-hard, I would answer no.
If you have two solutions (x1, and x2) of an optimization problem, and their fitness values are f(x1) and f(x2), I consider that it is not possible to determine whether or not a local optimum close x1 is better than that one close to x2 if the unique information you have is both fitness values. In fact, small changes in the solutions (e.g. the application of the mutation operator) could involve important changes in the fitness value of that solution, i.e. in those hard problems in which the neighbourhood structure is not known in detail, it is not possible to determine the best solutions areas. In other words, in NP-hard problems, it is not trivial to determine the effect in the objective space after a change in the search (or solution) space.
Finally, as you are interested in this question, I suggest to read the papers of Alberto Moraglio, who has investigated in detail the concept of "distance" over the solution space.
http://eden.dei.uc.pt/~moraglio/
In particular, you can read: http://eden.dei.uc.pt/~moraglio/gecco2004fin.PDF
I did not get why you prefer this restart approach ..
idea of Opposition based learning is good in this regards
Moreover have a look at PSO which can be perform better in your case as I get you want to analyse neighborhood of current population ...
For your Question 2 within the description.
Try with Surrogate model (an RBFN) that can evaluate neighborhood points (y1, y2) of Sample points (x1 and x2) based on a distance of y1 and y2 to the x1 and x2...
The efficiency of multi-start methods depends on the distribution of the initial solutions. Choosing well-scattering initial points gives a more powerful search strategy to multi-start methods.
Dear Stephen,
I completely agree with Raul, particularly concerning his point N°2 where my answer is also no.
However, if you already have some prior knowledge/statistics then you might be able to estimate the probability of improvement of a given solution. One way to achieve this goal would be to use a restarting strategy coupled with a so-called "surface response" methodology.
Hope this helps .
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling