Since the creation of Genetic Algorithms a number of people have created all sorts of optimisation algorithm inspired by nature and a variety of living creatures. Many of these algorithms are classified as swarm intelligence in opposition to genetic or evolutionary algorithms.
Over the years, my impression, is that people have lost the sense of why developing bio-inspired optimisation and rapidly diverged towards developing bio-inspired optimisation for the sake of it.
The insane proliferation of these algorithms has been accompanied by an equal proliferation of journal papers. The impression is that, as long as a new living thing is used as paradigm, one can publish an unbounded quantity of journal papers.
My impression is that, if one looks at the working principles of all these algorithms, the truth of the matter is that all these algorithms are fundamentally the same algorithm with some differences in the implementation details.
We now have: ant colonies, bee colonies, cuckoo birds (!!!?!!!), pigeons algorithms, fish schools, krill heads, bat algorithms, firefly algorithm, invasive weeds (scary), whale optimisation, grey wolf optimisation (wonder if by changing the colour of the wolf I can publish a new bunch of papers), etc. Try to randomly enter names of living things and add optimisation in Google.
Now my question is: does it make any sense? apart from allowing many grad students to graduate with some journal publications?
Or is it really the name that you give to an algorithm that does it?
Given the millions of species, each one with their own behaviour and ecosystem, I expect more algorithms and papers in the years to come but again: does it make any sense?
What I was referring to was optimisation algorithms to solve real valued or combinatorial problems. Not really anything that affect nature or the ecosystems.
The question is if it makes sense to find creative bio-inspired names and paradigms when developing optimisation algorithms that, in the end, all work on the same principle.
Hi Massimiliano, I entirely agree with you. All these bio-inspired algorithms are very similar in fact and it is not necessary to develop new ones. In addition, these algorithms remain all heuristic in the sense that there is no convergence proof to a local minimum and even less to the global minimum. We can add to this that each algorithm is associated with a set of setting parameters. Thus, depending on the values of these parameters the behavior of the algorithm is different. As a consequence, it is very difficult to compare these algorithms in practice (number of iterations, ability to converge to a better solution, ...).
Indeed. There is a theorem that explains that in practice, for real-valued continuous problems, it is impossible to prove global convergence in the general case although theoretical convergence proofs for some classes of algorithms exist.
The reasonable approach, in my view, is to understand which mechanisms are useful and for what.
I would start from the difference between population-based methods and a non population-based methods. The former use a sampling scheme as key underlying mechanism. All bio-inspired algorithms, as far as I can tell, are population-based and that is one of the key strengths.
Then, I would avoid the distinction between evolutionary and swarming because these two terms have an unclear meaning, computationally speaking. More meaningful is the difference between agent-based and non-agent based.
The latter store the information on the distribution of the values of the objective function in the population itself while the former use a different mechanism. This makes a huge difference in the way the sampling scheme is constructed.
All population-based non-agent algorithms update a distribution of samples with some form of Markovian process. All population-based agent algorithms do something else...to be continued.
If it is indeed the same principle, maybe there is some homotopy of hyper-parameters that characterize the whole spectrum of different evolutionary methods in a unified way. And perhaps it's the case that, for a given problem topology, there is an optimal configuration of such hyper-parameters. And if these parameters exist, then maybe they can be learnt.
I think that’s re-iteration of an existing knowledge in another term and terminology, which is not a novelty. Actually, the computer science society is running out of insects and creatures, as so many evolutionary algorithms with various names have been emerged! Like any other fields and research lines, spacecraft trajectory optimization witnessed some issues regarding the articles published in recent years. As you know, since a few decades, every year has seen the publication of several papers claiming to present an innovative concept, approach or method for spacecraft trajectory optimization. Some of these “so called novel” approaches lead the area of spacecraft trajectory optimization away from scientific contribution since they do not represents a truly novel approach. The question would rightfully be asked whether any new contribution had been made other than a re-iteration of existing knowledge. Some examples of such so called novel approaches are the applications of meta-heuristics, more specifically evolutionary algorithms, in spacecraft trajectory optimization. I think authors should realize and accept the fact that just using evolutionary algorithms in solving a spacecraft trajectory optimization problem does not create novelty in the research. Also, one approach cannot be considered as novel just because some parameters in an optimization algorithm are tuned for a specific space mission. However, in my opinion, the development of hybrid approaches which creates and study the connection between the nature of the spacecraft trajectory optimization problem and the characteristics of evolutionary algorithms is interesting if it is carefully justified. I think such researches should answer the question “why does a specific evolutionary algorithm works well in a specific trajectory optimization problem?” If we can find out this connection, we can successfully contribute to the field, I would say. Otherwise, it is just re-iteration of an existing knowledge.
Kenneth Sörensen discussed this issue in:
Article Metaheuristics -- the metaphor exposed
Regards
The short answer, as often is, is: it depends on how it is used.
It can make sense if the natural phenomenon is a source of inspiration (e.g. the idea for artificial ants was inspired by the foraging behaviour of real ants) and/or it makes it easy to explain how the algorithm works, and no more than this. In this regard, this is no different from artificial neural networks. For this to happen, it should always be possible to describe the algorithm in mathematical terms, without referring to animals or natural/social phenomena; it should be clear where the connection between the algorithm and the metaphor stops; the novel algorithmic contribution should be made explicit, related to already proposed ideas, and it should be clear what issue the new idea actually addresses; the contribution should be useful in practice, in terms of performance and/or understanding. Clearly, for this to happen, the focus has to be on the algorithm, not on the metaphor.
It does not make sense if the metaphor is the main novelty in the algorithm, especially when the "natural source of inspiration" does not perform any optimization; see e.g. a large part of the list at https://github.com/fcampelo/EC-Bestiary/
It becomes indeed difficult to separate substantially novel ideas from smaller variations.
The paper of Sorensen linked in the previous answer is a good article on the topic. I would also add the two papers of Dennis Weyland vs the harmony search:
Article A Rigorous Analysis of the Harmony Search Algorithm: How the...
Article A critical analysis of the harmony search algorithm—How not ...
(The answers from the author of harmony search are an interesting read too)
Another paper discussing how a metaphor can be misleading in understanding (and thus judging the novelty of) an algorithm is Article The intelligent water drops algorithm: why it cannot be cons...
On the other hand, there is no real way of telling when two algorithms are variations of the same idea, or two different ones. Clearly a genetic algorithm is different from an ant colony one, just like a variable neighbourhood search is different from a tabu search, but whether (e.g.) max-min ant system and ant colony system are two variants of ant system, or can be considered different algorithms, is just an opinion. This makes it very difficult to draw a clear line that separates incremental works from substantially new ones. Anyway, some journals have started taking action about this, for example, the Swarm Intelligence journal ("Additional submission instructions" at https://www.springer.com/computer/ai/journal/11721) and the Journal of Heuristics (PDF: https://bit.ly/2Q4gBCx).
This touches another point raised in the question: many (bio-inspired) algorithm are similar to each other, but between classes of algorithms there is something more than just implementation details or parameter values. For example, ant colony optimization uses agents (the artificial ants) to build solutions, while in the particle swarm optimization algorithm each particle represents a solution, which is mutated at every iteration, so there is some fundamental difference between them. Similarly, the difference between evolutionary and swarm intelligence algorithms lies in how the population is used: in evolutionary algorithms the solutions are mutated and combined, while in swarm algorithms there is some information exchange between agents. That said, as the papers linked above show, in some cases the difference between two algorithms can just be considered implementation details.
I agree that not all the algorithms are the same but I would argue that the biological analogy is not sufficient to distinguish the underpinning working principles. The papers that Alberto mentioned are very interesting and worth reading indeed.
In my view the reason why ant colonies systems/optimisation etc. make sense is not the analogy with the foraging mechanisms of ants but the fact that ACO incrementally build a probability distribution over the possible solutions. This working principle is clearly different from an EA in which the distribution of the solutions is maintained by the population itself. On this point we agree.
On the other hand I do not see much difference between a cross over operator and many existing bio-inspired mechanisms to exchange information among individuals or agents.
In fact if we look at this in more general terms I do not see much difference between cross over, mutation and any other mechanisms that is used to generate a new sample. Not because they are not different but because we can group all of them under a single pseudo-code line: generate a sample.
I understand that this is a bit radical but in my view we need to consider the actual working principle and not the metaphor at every level of the algorithm.
I am actually back from the CEC2019 where I had the chance to attend the talk of a lady that is actually evolving algorithms. My conjecture is that if you tried to have a generic algorithm for a broad class of problems you might end up always with the same fundamental building blocks, whether they look like a pigeon, a wolf and sea bass or something else.
The main difference between mutation and crossover is that mutation acts on a single solution, while crossover on pairs of solutions. Thus, crossover requires a population, and mutation happens independently from a population; tabu search, simulated annealing, etc are mutation-based algorithms from this point of view, but we cannot apply crossover in them. In the end I think it just boils down to the granularity one is considering.
On everything else we agree, in particular "the biological analogy is not sufficient to distinguish the underpinning working principles" and "you might end up always with the same fundamental building blocks".
Yes I am familiar with crossover and mutation but maybe I was not clear. My argument was that the end result of both is to generate a sample starting from a distribution. A very good example is Differential Evolution a good heuristics that is neither globally nor locally convergent (see for example my paper Article (Non) convergence results for the differential evolution method
) but still very effective. In DE what is called crossover and what is called mutation have very little to do with what is called crossover and mutation in other EA but still they accomplish the same goal.
My short answer is: no, it does not make any sense. Maybe understanding a particular mechanism, inspired from a given species could be interesting, both from the biological or optimization point of view. But even this seems to be lacking.
To respond to Abolfazl, the word of space trajectory optimisation has indeed experience a sort of similar inflation (though to a lesser extent) and I feel partially responsible for it.
When I started using GA for trajectory optimisation back in 1998 there was very little research on global trajectory optimisation and even less on evolutionary optimisation for space trajectories. When I initiated this stream of research in ESA, as part of my role in the Advanced Concept Team back in 2001, I was not expecting the GTOC and what followed. My intent was only to find an automatic way to generate globally optimal trajectories given that optimising space trajectories is often an NP-hard problem.
Now I believe that we are still far from complete automation, although a lot of steps forward have been made. The main problem is that if now one tries to publish anything that contains some trajectory optimisation, they might receive reviews that question how 'new' the method is. Not how appropriate or effective but how new. As an editor of the AIAA JGCD my message to all reviewers out there is: "guys, not all the papers that contain some trajectory optimisation are about a new method for trajectory optimisation and a lot of practical problems can be solved very effectively with very simple methods, thus please assess the appropriateness and effectiveness of the method not the inventiveness of the authors".
The world of space trajectory optimisation is also drifting towards another mega-hype: big data and machine learning. This is maybe the topic for another, parallel, conversation.
By the way, if you are interested in anything that is Computational Intelligence applied to space, I am the chairman of a task force of the IEEE Computational Intelligence Society: http://utopiae.eu/2-2/utopiae-training/research/ieee-computational-intelligence-in-aerospace-sciences/
Next year the World Congress on Computational Intelligence will be here in Glasgow and I will organise a special session on Computational Intelligence in Aerospace.
While this year, you might want to attend the ESA workshop Optimisation in Space Engineering: http://icelab.uk/ose5/
Indeed. I totally agree with you. Thank you very much for information about the opportunities and upcoming events. I will be glad to collaborate.
Totally agreed with your opinions and insights.
"the appropriateness and effectiveness of the method not the inventiveness"
This could never be too much emphasized, especially when dealing with machine learning algorithms. Many good results cannot be explained, reproduced or very sensitive to initial conditions. And many problems that can be solved efficiently by conventional methods are again solved by machine learning methods with no better results for most cases.
Anyway, it's still far away from real AI, we still need to depend on human intelligence for centuries maybe.
Totally agree, this is a shame but researchers are publishing a tons of "novel" algorithm with fancy (sometime ridiculous) names. rather than trying to understand the working principles of most important metaheuristics . Most of these papers are also cited because they are new schemes but at the end have similar working mechanisms and are plagued by the same exploration/exploitation conundrum. To me, it looks like that people really like to be the first at inventing something new but, apart from rare cases, there is no novelty if not in the name itself.
I keep updating an endless list of novel algorithm with strange names every time a see one. Among the funniest I have, Anarchic Society Optimization, Imperialist Competitive Algorithm, Invasive Weed Optimization, Mushroom Reproduction Optimization, Marriage in Honey Bees Colony Optimization, Emperor Penguins Colony, Bat /Squirrel/Japanise Tree Frog/Egyptyan Volture Searches/Swarm or Optimization algorithms,and many others... We should stop this trend as this research field is very interesting but it is now saturated with repetitive adn redundant articles.
There are two overlapping problems.
One is that bio-inspired things have had a lot of success in the past two decades. In particular when we talk about computing stuff.
Bio-inspired computing is a well established stream of research and one cannot deny the success of evolutionary computation.
I am not against bio-inspired. On the contrary it is an interesting area of research but I think that too often we end up being self-involved and fascinated by the beauty of it rather then its real necessity.
I think it is important to remind everybody that natural evolution is a frickin' SLOW process with a lot of mistakes that can lead to extinction. Hence it is not suitable for everything and anything. Besides we only see a snapshot of the process and it is not necessarily an optimal solution.
The other problem is the publish or perish mantra. I think that in many cases the researcher survives but science perishes. Too often I have seen papers referring to outrageously bad papers published in top journals.
If you are a reviewer please be careful of what you do and if you are an editor be even more careful.
Going along with my previous reply that the spectrum of evolutionary methods may be described the same underlying method, parameterised by some hyperparameters. There is has been some research into learning the optimal evolutionary operator: Preprint Learning to Evolve
Massimiliano Vasile I agree with your points which are raised on the name changing of an algorithm just from a different color of species and publishing a bunch of papers. The behavior should be unique that can form a new mathematical model. There are already many algorithms exist from different behaviors. We should think to use the new strategy (like apply the behavior on some artificial facts) where these behaviors can be fitted. This approach can improve the original model and solve the single, multi, or many objectives from my perspective.
What about Estimation of Distribution Algorithms (EDA)? Is this approach an attempt to generalise main techniques in bio-inspired and evolutionary algorithms?
If we look at the research that compares various nature-inspired algorithms for a particular application, we can see the obvious difference; we can find the sense and understand the purpose behind the research being conducted in this area. Different algorithms have different performance when used for a particular application. Progress and improvement should always be encouraged.
Actually Ahmed, the type of "difference"in results you describe, can usually be seen by simply doing different hyper-parametrizations of the same algorithm, so for example using crossover B or crossover A in a genetic algorithm, it is the nature of real-world black box optimisation and machine learning, there are always going to be these performance differences between methods, so pointing them out is not really useful, unless we can start to identify WHY crossover B is better than crossover A on a particular set of problems or problem instances.
Leonardo Trujillo I agree with your opinion that improvement can be seen when you modify the parameters of an algorithm for a particular problem; however, it is also possible that by using a different algo and modifying its parameters, the margin of improvement you obtain is comparatively larger for the same problem. The usefulness of various algorithms needs to be analyzed; for example, you are interested to know why crossover B is better than crossover A on a particular set of problems. Similarly, such comparisons can also be performed among algorithms. The perspective from which you analyze is important. It is also true that two algorithms with different names can give similar results and performance; however, this can not be made the basis for discouraging progress.
The core methods can be utilized in different application domains, sometimes these methods works for one domain but may not be suitable in other domain. Therefore, sometimes we have to analyze the impact of prebuilt methods in the problem in hand, and identify some conclusion. For example, trajectory classification based on gps data and based on accelerometer data sensors seems same problem, but both these problems have different properties. The methods used for classifying trajectories on accelerometer data may or may not be used in classifying gps trajectories.
This question and discussion are very important and interesting simultaneously. While reading the answers, an idea arrived, which can somehow help us to better understand the crux of this matter.
One of my current interests is the theory of computation of biological systems. When we compare it to our standard methodology applied to computation, we end up with a Turing machine, von Neumann architecture, and their variants.
The problem is—which was von Neumann very aware of—that biology is computing in massive-parallel ways. Let us take the John H. Conway’s 'Game of Life' (GoL) cellular automaton that is a perfect example of massive-parallel computations.
We found out that in the GoL we can create AND, OR, and NOT gates from glider guns emitting gliders. So far good. BUT! The concern is why we do not study the true information processing withing massive-parallel environments without defining our, human, computer-based logic, and do not explore and exploit 'emergent logic' and information processing in its natural form?
Details of what is just explained here is present in the paper dealing with robust (error-resilient) massive-parallel emergent structures observed in the generalized r-GoL.
Going back to our question. What I do propose to focus our attention on is to go back to biology and study its minute computations in greater detail and depth. From this point, we can try to work towards an emergent, self-adjusting computational approaches applied to optimization.
I do see a clear parallels in the r-GoL research and search of emergent optimization methodologies. It might be a way to avoid endless numbers of optimization techniques originating in a common ancestor.
Was it a sufficiently clearly put idea? Let me know.
In 2019 I asked the question: Bio-inspired optimisaton: does it make any sense?
Since then the number of "bio-inspired metaheuristics" has increased by a lot. Every new paper lists all the previous animals and related algorithms creating an eco-system on its own. Every paper proclaims that their bio-inspired algorithm ranks first in many standard benchmarks and solve the intrinsic problems of all preceding ones.
In the last 6 months only I found at least 5 different new algorithms published in scientific reports: Pair barracuda swarm optimization, Hippopotamus optimization, Enhanced gorilla troops optimizer, marine predator algorithm, and the best of all, rhinopithecus swarm optimization.
But in the reference list of some of these papers I read: Dung Beetle Optimizer (DBO), Beluga Whale Optimization (BWO), Salp Swarm Algorithm (SSA), African Vultures Optimization Algorithm (AVOA), Whale Optimization Algorithm (WOA), Atomic Retrospective Learning Bare Bone Particle Swarm Optimization (ARBBPSO), Artificial Gorilla Troops Optimizer (GTO), and Harris Hawks Optimization (HHO).
Now that ChatGPT is too often used to write paper I really thought that some algorithms were actually a joke produced by the generative creativity of ChatGPT.
Sadly my prediction on the proliferation of these algorithms, given the number of existing species on the planet, is turning into reality.
Since some of these papers immediately attract citations at an impressive rate, probably because every new metaheuristic has to cite all the previous ones, is this a new way to secure citations?
I am seriously puzzled.