This is a follow up thread to https://www.researchgate.net/post/What_is_the_optimal_number_of_restarts_for_a_fixed_number_of_function_evaluations?
The goal is to develop general guidelines that can lead to the improved performance of (population-based) metaheuristics on (continuous domain) multi-modal fitness functions. Assuming a fixed or constrained number of function evaluations, our plan is to use multiple restarts of a metaheuristic tuned to converge relatively fast.
Our current focus is to identify and restart at the "critical" search scale. In general, on (benchmark) multi-modal fitness functions, there are rapid improvements in fitness at the beginning (as the search scale is larger than the attraction basins of the local optima and the search process rapidly explores the overall global structure of the search space), an "elbow" (which we believe could be around the "critical" search scale), and then slow improvement as mostly local search occurs to find a local optimum.
We are looking for features that we can identify in real-time that indicate this "elbow" so that we can restart at it and thus have the new metaheuristic procedure spend more time and effort at this "critical" search scale. We believe that this transition from coarse global search to the specific selection of an attraction basin to exploit will heavily affect the performance of metaheuristics on multi-modal fitness functions.
Any ideas?
I assume that the meta-heuristic approach you are going to consider is locally convergent at the first place to at least be able to locate the local optima in the basins of attractions. Also, theoretically, the number of restarts should be infinite to guarantee convergence to global optima. Thus, you should not be after guaranteeing convergence to global optima (as the answer is already clear, the number is infinite). Now, if you want to improve the performance of an algorithm for a set of benchmarks, and the algorithm is locally convergent, then you need to first locate a good basin of attraction and then of course locate the local optima in that. But, to restart, you need to find a way to avoid keep converging to the same basin of attraction. You can take a look at function stretching ideas (there are some papers, google them or let me know and I can provide some for you) to make sure this avoidance.
Also, another idea can be having several independent populations while the populations can repel each other. Yet another way is to just say: if we are on that "elbow", the population is going to be (most likely) stagnated. Then, store the found points and restart the population. After doing this several times, you will have some stored points (and, assuming stagnation happens, the ones that were found at the same stage of restart are in the same basin), and it comes to the "potential" of the points (or in fact the basin that the point is its representative) and how good they can be. Then, you can just use a fast local search method to just see what is the quality of the found basin and see if it deserves more resources for the searching purposes. You can think of many other ways, but, the general question is "how can you estimate the quality of a basin by having a couple of points in that basin as fast as possible with small amount of resources (individuals or FEs)". One way as I mentioned is to just test them by fast local optimizers.
In some thing like PSO, you can do this the other way around. In fact, start with a lot of particles but in distinct sub-populations (hey make sure you have fixed the local convergence issue of PSO first) with small number of particles in each (so called non-overlapping topology), then run the method and during the time, change the shape of the topology to become more similar to the global best topology (the most concentrated topology) to assign more resources to better basins (I have submitted a paper in this regard but the idea there is to find best feasible region within a space which contain a lot of disjoint feasible regions, see A hybrid linear particle swarm with niching for constraint optimization).
https://www.researchgate.net/publication/280244004_A_comparative_study_of_metaheuristic_optimization_approaches_for_directional_overcurrent_relays_coordination
Article A comparative study of metaheuristic optimization approaches...
https://www.researchgate.net/publication/297245624_Particle_Swarm_Optimization_Algorithm_and_its_Codes_in_MATLAB
Research Particle Swarm Optimization: Algorithm and its Codes in MATLAB
https://www.researchgate.net/publication/296636431_Codes_in_MATLAB_for_Particle_Swarm_Optimization
Code Codes in MATLAB for Particle Swarm Optimization
Normaly, the benchmark functions are classified with the challenge that they established. Therefore, they are multi-modal, uni-modal, rotated, hybrid, etc.
- Badges
- Science topic
- Similar topics
- Linguistics
- Composition Studies
- Publication