Dear Stephen,

This is a very good question because it has been increasingly difficult to find novel research in metaheuristics without recurring to inspirations of any kind. Attempts of unifying the various flavors of metaphor-based metaheuristics into an unique framework have appeared e.g. in Taillard et al. (2001).

On the other hand, I think many researchers have turned on improving metaheuristics for a vast range of domains, by integrating concepts that do not rely on metaphors.

One example of this are indicator-based metaheuristics for Multi-Objective Optimization (MOO), whose main challenge is on designing efficient ways of measuring the quality of sets of mutually non-inferior solutions in order to approximate the Pareto Frontier. Although many indicator-based MOO algorithms are still grounded in evolutionary-inspired frameworks, the focus is entirely on how to design heuristic operators that take advantage of the information provided by such indicators. See e.g. Bader and Zitzler (2008).

Now, to answer your question, I can point out a few interesting modern metaheuristics not entirely focused on metaphors:

- Natural evolution strategies: these are methods that update candidate solutions in continous search spaces in the direction of the natural gradient (a more general gradient estimation based on differential geometry, see Amari and Douglas (1998)). A recent example can be found in Sun et al. (2009) for numerical optimization problems and a non-markovian double pole balancing application.

- Cross entropy methods: given a parametric family of distributions and an adaptive threshold on the objective function values sampled so far, these methods can be viewed as the higher-level strategy of finding the distribution representing the elite solutions by minimizing the relative entropy. Rubinstein (1999) applied CE both for continuous and combinatorial optimization (TSP, shortest path). In my opinion, CE could also be viewed as an Estimation of Distribution Algorithm (EDA).

- Particle Filter methods: these were presented as a "reformulation of stochastic global optimization as a filtering problem" and have been applied for parametric density estimation. See Stinis (2009). Again, IMO, these are closely related to EDAs, although having a much more formal flavor and convergence guarantees.

- Quantum annealing: these methods can be considered as the quantum counterpart to simulated annealing, one of the most popular and well-succeeded metaheuristics. Now, these are interesting because they can be implemented in a quantum device for actually physically performing the steps required to achieve a configuration of minimal potential energy. That's the approach the canadian company D-Wave claims to have implemented by using an adiabatic quantum computation processor. See e.g. Finnila et al. (1994).

A very good recent survey on metaheuristics for optimization appeared in Boussaïd, Lepagnot, and Siarry (2013), where you can find several examples not mentioned in your question but that came out long ago (the following references can be found in the original paper):

- Greedy Randomized Adaptive Search Procedure (GRASP) after Feo and Resende (1989) who designed such methods mainly for "set covering problems that arise from Steiner triple systems"

- Noising Method (NM) after Charon and Hudry (1993) that applied it for "the clique partitioning of a graph"

- Variable Neighborhood Search (VNS) after Hansen and Mladenovic (1997) for the traveling salesman problem

- Guided local search (GLS) after C. Voudouris, E. Tsang (1999) also for TSP

- Iterated local search (ITL) after Stützle (1998) for TSP, quadratic assignment problems, and flow shop problems

- Scatter Search (SS) and Path Relinking (PR) after Glover (1997) are methods closely-related with evolutionary-inspired algorithms, the difference being that principled heuristics are provided for combining multiple candidate solutions to produce novel ones.

Hope that helps.

Article Quantum Annealing: A New Method for Minimizing Multidimensio...

Article The Cross-Entropy Method for Combinatorial and Continuous Optimization

Article HypE: An Algorithm for Fast Hypervolume-Based Many-Objective...

Article Stochastic global optimization as a filtering problem

Conference Paper Stochastic search using the natural gradient

Article Adaptive memory programming: A unified view of metaheuristics

Conference Paper Why natural gradient?

Article A survey on optimization metaheuristics

Also check out "matheuristics", that combine exact methods with metaheuristics:

http://iwi.econ.uni-hamburg.de/mh14/

Dear Stephen Chen,

using this opportunity, I want to focus your attention on two very important problems. Here I will quote myself from the discussions on the links:

https://www.researchgate.net/post/How_to_ensure_fair_comparison_between_optimization_methods

https://www.researchgate.net/post/Is_there_really_a_significant_difference_between_the_performance_of_the_different_meta-heuristics_other_than_e2

https://www.researchgate.net/post/The_purpose_of_our_research_is_insight_not_numbers-but_does_anyone_care_anymore

https://www.researchgate.net/post/Does_anyone_know_any_recent_papers_on_Statistical_Optimum_Estimation_Techniques

https://www.researchgate.net/post/How_should_I_select_the_Benchmark_Problems_to_be_included_in_the_benchmark_set_for_testing_the_performance_of_a_metaheuristic

The first important problem is the following:

"Currently, developing any approximation algorithm "A" is not a big problem usually. Therefore, there are very many different approximation algorithms "A" to find any apparoximate solution A(D), where D is input data. Looking through any paper, I don't read description of approximation algorithm "A" in detail. I is not interested never know about this approximation algorithm in detail, absolutely is not interested. I know that I could develop always my personal approximation algorithm "B" if it would be necessary to me. Therefore I want to ask: if you think that you developed effective approximation algorithm, then please place your algorithm in the Internet as an Online Tool to be accepted for any users to use your algorithm for personal input data. In my opinion, currently, development of any approximation algorithm (heuristics, metaheuristics, an so on) IS CRAFT BUT NOT SCIENCE ITSELF. In contrast to approximate algorithms, development of quality Lower Bounds LB(D) has huge value in order to evaluate quality of A(D) by a formula p = 100% * (A(D) - LB(D)) / LB(D) . From this point of view, in my opinion development of any quality LB(D) IS ONLY SCIENCE BUT NOT CRAFT. Thus, please concentrate your attention on finding quality lower bounds. Now that would be a million times more meaningful for science."

The second important problem is the following:

"In my view, the best way "to ensure fair comparison between optimization methods "A" and "B" is the development of Online Tool "A" (Site "A") and Online Tool "B" (Site "B") in the Internet to be accepted for any users to compare "A" and "B" for their personal input data. Then you will get a huge statistics that would be the best way to justify that "A" is better than "B" or vice versa. This way would be the best solution for all people as scientists, researchers, practitioners, and usual users without any special knowledge."

"In my opinion, the 21st century must be the century of developments. From this point of view, at least in Computer Science, A PAPER MUST BE PRESENTED AS A FUNCTIONAL SITE. In order wors, need to move from the Traditional Paper (e.g. in .pdf) to the Online Tool (e.g. in ASP.NET) in the Internet. This tool should be available to all people (researchers, practitioners, users) to solve their tasks (for personal data) just by clicking the link. Thus, your question can be solved completely by presenting functional sites that will solve the all problems you mentioned.

Let's assume you presented your functional site in the Internet. Then

1. If I'm a researcher and I'm interested to know about your Theory (Methodology, Solution Approach, Algorithm, and so on) in detail, then I will read your paper (e.g. in .pdf) from your site.

2. If I'm a practitioner and I'm interested to use your program in order to solve my task (for personal data), then I will use your tool.

3. If I'm a researcher and I'm interested to compare your output to my output for the same input data, then I will use your tool."

"Thus, in my view, there are two very important problems in the future to be solved: FINDING QUALITY LOWER BOUNDS and DEVELOPING ACCEPTED ONLINE TOOLS".

Thank you 

In addition to the most excellent answer by Carlos (congratulations for the most thorough answer I've seen in a long time!!!), I would like to add the following favorites of mine:

1. Nested Partitions method for global optimization (Shi & Olaffson, Operations Research 48(3), 2000): general method for global optimization with convergence guarantees, developed in my alma-matter school :-).

2. Multi-level optimization methods, originally developed for graph-partitioning by Hendrickson and Leland (if I remember correctly), but made really the best partitioning technique for the last 20 years or so by George Karypis. These methods do not come with strong theory (as far as I know) but work beautifully well in very large-scale problems. Primary application is in VLSI physical design.

3. Finally, why not include the recent CMA-ES (Covariance Matrix Adaptation Evolutionary Strategy), together with the old but proven Conjugate Gradient method (with your pick of step-size choice method)? the first is definitely a meta-heuristic, the second has strong theory behind it, so I'm not exactly sure to what degree it counts as meta-HEURISTIC, but it's great nonetheless :-)

I would say the family of LK-opt ( http://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic ), 2-opt ( http://en.wikipedia.org/wiki/2-opt ), and the like for TSP or other combinatorial optimization problems.

Hi dear Stephen,

I'm absolutely in agreement with you. Actually, the most important thing about metaheuristics is not their nature-inspiration, but we should know their mechanism, whether thy are metaphor-based or not. 

All metaheuristics have used two structures inside of them: 1) intensification and 2) diversification. Intensification tool tries to guide the algorithm to the possible fittest solution by highlighting best solutions in terms of objective function. Contrarily, diversification tool tries to create purely random changes in solutions in hope of more exploring solution space and escaping local optimums.

For example, in GA, using Roulette Wheel and crossover operator, better solutions are given more chance to  to be selected and produce the next generation's children (which are similar to their parents) (See genetic principle: better individuals have more chance to survive and reproduce). While GA uses mutation operator to make random changes in the solutions  to search other regions of the solution space.

Consider SA, at the beginning of the algorithm, chance of selecting worse neighbors is high (using Boltzmann function) and it makes  the worse solutions have a chance to be selected (this mechanism acts as a diversification tool). As the algorithm goes on, this probability reduces and finally SA turns out to be a simple local search or hill-climbing algorithm (only when a neighbor is better than the current solution is selected that it is ). 

In my opinion most of metaheuristics perform a balance between these two tasks (intensification and diversification).

Best regards

I find this question hard to answer, as it implies a definition of metaphor. Actually, it requires a definition of what is not a metaphor.

For example, I think that Estimation of Distribution Algorithms are a great example of non-metaphor metaheuristic, if you dont consider statistics as a metaphor, of course.

Best,

I believe I have a non-metaphor metaheuristic; I call it Problem Dependent Optimization (PDO); it can be used in wide range of problems; in a sense, its metaphor is the problem itself:

http://web.unbc.ca/~bluskovi/pdo.pdf

Journal of Combinatorial Optimization, 2015, DOI 10.1007/s10878-014-9826-x.

The final publication is available at link.springer.com; more precisely, here:

http://link.springer.com/article/10.1007/s10878-014-9826-x

Hi,

I suggest Ant-Q algorithm for handling NP-hard problem. The  Ant-Q algorithm is an agent based algorithm that combines Ant colony based methods  with the

reinforcement learning technique.

Personnaly I have used the Ant-Q as hyperheuristic for solving the cutting stock problem and I have reached good results.

https://www.researchgate.net/publication/224247371_Ant-Q_hyper-heuristic_approach_for_solving_2-dimensional_Cutting_Stock_Problem

Good luck. 

Conference Paper Ant-Q hyper-heuristic approach for solving 2-dimensional Cut...

Variable mesh optimization (VMO) is another non-metaphor inspired optimization method. It was initially designed for numerical optimization but it has since been extended to tackle combinatorial and multimodal optimization problems too.

Conference Paper Niche-Clearing-based Variable Mesh Optimization for Multimod...

Article Variable mesh optimization for continuous optimization problems

The "Generalized normal distribution optimization algorithm" is an interesting non-metaphor based optimizer that I found recently.

https://www.sciencedirect.com/science/article/abs/pii/S0196890420308402