Most search techniques for continuous search spaces use some type of gradient -- one solution is better than another, so solutions move in that direction. A specific example is the attraction vector in Particle Swarm Optimization.
Further, Particle Swarm Optimization begins with a cornfield vector/sphere function (see Section 3.2 in [J. Kennedy and R.C. Eberhart. (1995) “Particle swarm optimization,” IEEE ICNN, pp 1942-1948]), Differential Evolution builds its foundation from a simple unimodal cost function (see Figure 1 in [R. Storn and K. Price. (1997) “Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces.” J. Global Optimization, 11:341-359]), and Evolution Strategies (ES) also explains its functionality starting with a mutation cloud shown against a unimodal search space (see Figure 2(b) in [H.-G. Beyer and H.-P. Schwefel. (2002) “Evolution strategies: a comprehensive introduction.” Natural Computing, 1:3-52]).
Are there any exmaples of metaheuristics that are explicitly and initially designed for multi-modal search spaces?
How about Estimation of Distribution Algorithms? The idea of learning a probability distribution that generates optimal solutions is general enough to capture the multimodal case, although arguably multimodality isn't an explicit aim of many of these approaches. However, there are certainly a number of EDAs that attempt to solve multimodal problems, e.g.:
Pena et al, Globally Multimodal Problem Optimization Via an Estimation of Distribution Algorithm Based on Unsupervised Learning of Bayesian Networks
http://www.mitpressjournals.org/doi/abs/10.1162/1063656053583432#.VLaaTieUf74
Yang et al, Globally Multimodal Problem Optimization Via an Estimation of Distribution Algorithm Based on Unsupervised Learning of Bayesian Networks
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6899662
Also there seem to be quite a few swarm algorithms that are well suited to multimodal problems by merit of limiting communication between parts of the swarm - either explicitly via multiple swarms or implicitly via interactions that decay rapidly with distance (e.g. firefly, gravitational search). However, it's often unclear whether this is an explicit aim of the algorithm designer, or just a consequence of mimicking real world processes. You could also argue that these are derivatives of PSO, so 'initially designed' may also be up for debate.
Very interesting question. I haven't seen many multi-modal functions with many global optima. Usually, these functions have many local optima and only one global, that's why meta-heuristics are used. On the other hand, mathematically I can't see a method which can go in many directions at the same time but parallel version.
Just conjecture, and I don't know the specifics of your application, but what about "time", as in "neurons that fire together, wire together". So if you hear the word "jump" at the same time as you see a swimming pool, you would assume that there was some relation between the two purely on the basis of timing. So your multimodal representation of both the word "jump" and the scene "swimming pool" would have a certain amount of shared representation. So if I wanted to train a multimodal network, I'd want to do some unsupervised learning on data where each sample corresponded in time. Even mixing "text" into the picture, i'd think of it as "subtitles" and repeat it on each frame (sample) of the other inputs (vision and sound?).
You can take a look into the paper which is in the attached link. This is one of the best surveys I've ever read about the subject.
Also, I'd worked on this subject during my masters. You can take a look into my most recent publication. This is not the final publication of the proposed algorithm, but you will find some interesting results there. Such publication is also attached.
Conference Paper Weight based Fish School Search For continuous optimization ...
Article Real-parameter evolutionary multimodal optimization — A surv...
I don't know whether you wish to call it a "meta-heuristic" or not, but my work with "simple subpopulation schemes" is a simple modification to EAs designed for multi-modal search spaces. The nice feature is that a distance metric does not need to be defined. I believe my modifications could easily be applied to numerous population-based algorithms (hence possibly making it a meta-heuristic? Would be fun to see!). My code is at:
https://dl.dropboxusercontent.com/u/41759263/SSS.zip
For some descriptions of the modification see:
http://www.swarmotics.com/uploads/ecc7_5.pdf
http://www.swarmotics.com/uploads/ep94.pdf
Yes, there are a number of metaheuristics designed for multi-modal search spaces. In our lab we use a lot the so-called enhanced Scatter Search (eSS) metaheuristic, which performs very well with large-scale multi-modal problems. A recent implementation in Matlab and R, which includes a parallel version, is: https://www.researchgate.net/publication/258839750_MEIGO_an_open-source_software_suite_based_on_metaheuristics_for_global_optimization_in_systems_biology_and_bioinformatics
That said, the purpose of eSS is to try and find one solution, which hopefully will be the global optimum; it NOT to find the set of ALL local optima (which is a different problem).
Article MEIGO: An open-source software suite based on metaheuristics...
Island based genetic algorithm for multimodel. Also, you can check this link
Multi-swarm hybrid for multi-modal optimization by Antonio Bolufé Röhler and Stephen Chen, 2012
https://www.academia.edu/1840040/Multi-swarm_hybrid_for_multi-modal_optimization
Hi Everyone,
Thanks for your answers. Some quick comments...
EDAs definitely have some benefits in globally-convex multi-modal search spaces in that they can focus on the underlying base function (e.g. the parabola as opposed to the super-imposed sinusoid in a function like Rastrigin). I'm also looking for something that can handle non-globally convex search spaces, so EDAs are at most a partial solution.
I'm also looking for something that is more than multi-population/niching based. Any form of multi-start or parallel independent runs will of course produce more optima which can lead to better optima, but I'm unhappy with the efficiency/lack of synergy in most of these methods. I'll look at your suggestions, and get back to you with more detailed comments later.
Cheers,
Stephen
Lets say the answer is yes, or no, does it make any difference? The fact that a method was not designed initially for a "type" of problem (here, find as many local/global optima as you can) does not make that method effective/inefficient for that "type" of problems. So, if you want to propose a new one that is initially designed for say multi-modal search spaces (that I am not sure you mean niching or you mean dealing with multi-modal search spaces effectively) just make sure it is not an extension of ES or PSO or others with some fancy names. For example, I can design a new method based on my daily job and call it Reza method and claim it is specific to routing (as I go to work every day and try to minimize my way to work) because it was designed initially for routing problems, does not make Reza algorithm really unique or effective. I most probably give some names that most likely translatable to GA or Ant colony terminologies with some extensions if I am very generous. Another example, something called Cockoo search was designed for blah or blah does not make that a unique method for optimization. I encourage you to have a look at "the emperor is naked: evolutionary algorithms for real-world applications" or "Quo Vadis, Evolutionary Computation? - On a Growing Gap between Theory and Practice" by Z. Michalewicz.
Hi Mohammad,
I would say the answer is yes. As a consequence of "No Free Lunch", it is reasonable to expect that a metaheuristic designed initial for unimodal search spaces (and which performs specifically well in unimodal search spaces) will be less likely to have superlative performance in multi-modal search spaces.
I'm willing to specifically sacrifice performance in unimodal search spaces. In general, the differences aren't that much there, or hybrid systems can be used to make up the difference. I think that from this specific focus, there are interesting insights to be made.
This is open to debate of course, but I'd like to share with you my latest work in this area.
Cheers,
Stephen
Article A Review of Thresheld Convergence
That's an interesting paper Stephen. I like the argument that an algorithm that explicitly decouples exploitation and exploration is more likely to cover the modes of the search space, especially when they have varying objective values. Some years ago I was trying to solve a problem that required exactly this kind of coverage (see below if you're interested) and attempted to adapt an EA by using population-based clustering to prevent the lower fitness niches from dying out. Although moderately successful, it was a little unstable, mainly because it was trying to go against the wider dynamics of the EA. I look forward to seeing where your work leads.
Michael
PS: The second paper was a follow-up, and highlighted why for this application it is important to be able to discover niches in parallel, rather than for instance using multiple runs or a multi-start algorithm.
Article Regulatory Motif Discovery Using a Population Clustering Evo...
Conference Paper A co-evolutionary framework for regulatory motif discovery
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
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...
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling