One of my favorites is a prime number generator based on a predator-prey models of cicadas: http://www.j-npcs.org/online/vol2000/v3no2/v3no2p208.pdf
For example, it's quite difficult to imagine how wings evolved, since 1% of a wing seems to offer no fitness advantage, and yet you can't evolve 10% of a wing without evolving 1%. One idea from biology is that feathers probably evolved first as thermoregulators (basically good fur for dinosaurs), and small wing flaps may have evolved similarly to keep animals warm, and only once they had evolved large enough could they be used in a "flying squirrel" way to get from tree to tree, and at that point you're in a different fitness landscape and can start evolving for wings proper.
It turns out such an idea may be useful for evolving hard-to-evolve neural networks and the like. (Although this was 15 years ago, and genetic algorithms have fallen out of fashion.)
I fully anticipate they will come back in fashion. NN were out of fashion for a long time.
https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6...
The approach is clearly valid but I feel like there's some missing pieces in making it work effectively in a digital context. I played around with this stuff a lot in college and my take was that the evolvable encoding problem (a form of representation problem) is fairly major and not really solved. There are also some unsolved issues around evolutionary dynamics and evolutionary game theory, which means how to structure the population and the "game" for best results. Not sure how much progress has been made since then on these, but my impression is not much.
The main area where GAs have seen use in the field so far is optimization problems with a lot of parameters related in unknown or hard to model ways or where a closed form solution is unknown or computationally too expensive (NP). These include shipping and air travel routing (traveling salesman with multiple optimization goals like distance + time + fuel + depreciation), circuit board and IC layout, antenna design for exotic RF modulations, drug discovery, materials science, etc. Problems like these are fairly easy to map to a GA, and current GAs are pretty good at finding local maxima in these functions.
Still those are a far cry from "design ex nihilo," which is really the promise that evolutionary computation carries. Those applications are using GAs as a bigger brother to things like Monte Carlo and simulated annealing.
One area that I'd look into if I were doing this now would be a hybrid approach where a GA is used to design deep learning architectures and their associated parameters. Seems like it could be very powerful but damn would that ever take a lot of computing power. The fitness function of the GA would consist of N deep learning runs for each candidate. Luckily GAs are parallelizable to an almost unlimited degree.
Most recent advances in the fields you mentioned were driven by gradient-based optimization (e.g., drug design, routing, or chip design: https://www.nature.com/articles/s41586-021-03544-w).
Nature can't SGD through genomes but has a metric ton of time, so evolution might be near-ideal for sexual reproduction. We typically don't have billions of generations, trillions of instantiations, and complex environments to play with when optimizing functions... It's telling that the fastest-evolving biological system (our brain!) certainly doesn't employ large-scale GA; if anything, it probably approximates gradients via funky distributed rules.
EDIT: The most modern application I can think of was some stuff from OpenAI (https://openai.com/blog/evolution-strategies/). But the point here is one of computational feasibility -- if they could backprop through the same workload, they would.
But ... GAs are not biological evolution. I think the real issue is that present day GAs only approximate some aspects of biological evolution, but they're very "chunky" in the same way that primitive neural network models are. They get generation and selection but actual biological evolution involves much deeper processes than that. Evolutionary theory is rich and quite fascinating.
I think that there is probably a lot of scope for this type of approach. IIRC a key issue is around tuning the Genotype -> Phenotype mapping algorithm so that you start covering the space of potential network architectures reasonably efficiently while maintaining an ordered enough fitness landscape to enable the genetic algorithm to search reasonably efficiently.
I really should try and find the time to think a bit about this again...
Plenty of work on it but it’s early days and we need massive, massive, compute power.
It's not possible to predict fashions, but I seriously doubt that the whole evolutionary algorithms field will see a resurgence based on anything other than buzzword-driven fads.
In general evolutionary algorithms perform terribly poorly in any optimization problem, and at best are effective (but not efficient) in exploring problems involving the arbitrary addition/removal of dimensions/parameters, including high-dimensional discrete optimization problems.
Given there are already techniques to convert discrete optimization problems to non-discrete ones and to add/remove arbitrary parameters, and there are already global optimization techniques which are far more efficient and, more importantly, deterministic, genetic algorithms don't really offer any relevant advantage over even brute-force techniques.
Benchmark your PSO implementation against a) a naive Monte Carlo implementation with an uniform distribution, b) low-discrepancy sequence, c) a global optimization algorithm such as DIRECT, and compare convergence rates.
I'd be surprised if your PSO implementation did not competed for the last place in terms of function evaluations.
Not to nitpick, and I agree with your overall point, but couldn't 1% of a wing be useful for any tree-climbing animal that falls/jumps occasionally? It would allow them to fall/jump a little further without injury by acting as a little bit of a parachute or glider.
Keep in mind that for many insects their terminal velocity isn't sufficient to kill them on landing. So an ant can be dropped from an airplane, fall for thousands of feet, hit the ground, and the walk on like nothing happened.
https://github.com/fcampelo/EC-Bestiary
EDIT: updated link.
https://github.com/clever-algorithms/CleverAlgorithms
Also, not sure if they're in this book or not, going from memory (I haven't looked at it in a while) but a few other things that might be relevant here, that I haven't seen mentioned yet:
https://en.wikipedia.org/wiki/Flocking_(behavior) -- simulations of animal flocking behavior have found some applications
https://en.wikipedia.org/wiki/Artificial_life - ALife in general may be thought of as slightly "nature inspired", or at least certain approaches to it
https://en.wikipedia.org/wiki/Boids - Boids specifically is an ALife approach that heavily uses Flocking
The OP might also find something of interest in "chemical computing" and/or "DNA computing".
They are a treasure trove of easily publishable papers, but frankly the whole field feels like a fraud. Each paper is formulaic and consists of coming up with a metaphor to add minor twists to established heuristics, and in the end they all fare slightly better than Monte Carlo.
The gravy train is provided by the No Free Lunch theorem, which is just a convenient copout to justify why an heuristics isn't good except on a single convenient realization.
My understanding is that this problem got so bad that many (most?) of the top journals in the field have declared recently(ish) that they will no longer publish EvoComp papers of that nature. That is, the ones that amount to no more than "here's a new metaphor based algorithm that doesn't really contribute anything new to our understanding of anything and represent only an incremental improvement over existing algorithms."
https://en.m.wikipedia.org/wiki/List_of_metaphor-based_metah...
And an algorithm can be based on a metaphor and still be useful, one should just take care to judge it own its own merits and not give it some greater value for being "natural".
I was told this by a professor in graph theory who co-authored a book on TSP. But he had no hand in the implementation or the testing AFAICT.
https://en.wikipedia.org/wiki/Ant_colony_optimization_algori...
https://en.wikipedia.org/wiki/The_Chemical_Basis_of_Morphoge...
[1]: https://mitpress.mit.edu/books/bio-inspired-artificial-intel...
A moth has a small number of nerves on its wings that inform its motion. The neuronal circuitry is relatively sparse, and so the location of these nerves is quite important (see [0] at 12:44). This inspired the development of an algorithm to optimize the positioning of a small number of pixel sensors to classify an image. For example, this can be used to train a model for the cat/dog classification problem using only 20 pixels.
Evolutionary Algorithms, Genetic Programming, Cellular Automata, Neural Networks, Self-Organisation, other Self-X properties like Self-Healing. Methods from Swarm Intelligence, for example Ant Colony Optimization or Particle Swarm Optimization.
The algorithm itself is somewhat limited but the visual representation is mesmerizing :)
--------
There's a bunch of methods that come out of casting an optimization or search problem into a thermal system with an artificial energy and corresponding conjugate (artificial) temperature.
Most people are familiar with (Gibbs-ish) Monte Carlo methods, for example. Then there's simulated annealing, tempering, parallel tempering, etc. Simulated annealing is universal optimizer with remarkable richness coming from the "energy landscape" perspective. Recent work by Riccardo zecchina has studied neural nets from this perspective, and the whole (largely) Italian gang of glassy landscape people have done really cool stuff with it including fundamental CS stuff like K-SAT.
Lots of optimization algos use tricks that exploit analogies to thermal systems, given a sufficiently clever "Hamiltonion".
I'm not up to date with the latest and greatest in NN training stuff, but I know a few of the preferred optimization algorithms used some form of gradient descent often with some artificial "momentum". Can't remember what it was called, maybe Adam or something? I know Michael Jordan at Berkeley does a lot cool stuff with along these lines.
Very rambly message I see now, so I'll stop and just give some references/recs and maybe polish up later.
A few recommendations--
Nature of computation - Cris Moore I think
Information and physics(?) - Mezard and montanari
Computational beauty of nature -Flack(?)
Newish book from SFI from a conference I was at a few years ago may interest you, The Energetics of Computing in Life and Machines https://www.amazon.com/dp/1947864076/ref=cm_sw_r_apan_i_JQXY...
And most emphatically, Information, inference, and learning - Mackay
Originally used to model the growth of stable populations. I found that it is perfect for things like spam/abuse timeouts. The function has a couple of tunable parameters for things like the amplitude and steepness of the curve and the x-offset. Once those are dialed in as you like, you get a really nice function for measuring and responding to abuse.
https://www.amazon.com/Intelligence-Morgan-Kaufmann-Evolutio...
I'm happy to see their website is still up:
http://www.swarmintelligence.org
I ended up using ACO for a manufacturing optimization problem. Once you reframe your problem into one of the classics, traveling salesperson in my case, you can feed it to a bunch of different strategies. I suppose I could have used genetic programming or taboo search, but didn't have the gumption to play around more.
I haven't done any optimization or OR work since, so haven't kept up. All this machine learning stuff as made me wistful for the good old days. I'm on the lookout for a hobby problem or project which will give me an excuse to circle back to optimization stuff.
https://en.wikipedia.org/wiki/Reaction%E2%80%93diffusion_sys...
> "The Smith–Waterman algorithm performs local sequence alignment; that is, for determining similar regions between two strings of nucleic acid sequences or protein sequences. Instead of looking at the entire sequence, the Smith–Waterman algorithm compares segments of all possible lengths and optimizes the similarity measure. (wiki)"
Mandelbrot's fractal set certainly looks like a biological structure but I dont think it originated due to thinking about it.
"...what was doubled is reduced by the amount of the predecessor."
You can do it in an excel spreadsheet with one particle and watch it solve it - spooky effective.
[1] https://scholar.google.com/scholar?hl=en&as_sdt=0%2C5&q=ant+...
It happens that we have not associated an explanatory biological understanding to it.
This is a very interesting question, and even though I can't answer from personal experience, here is a paper[0] that listed the following:
>Genetic Bee Colony (GBC) Algorithm
This appears to combine genetic algorithms with "swarm intelligence" - several agents, which model the behavior of bees - some scout and share information, others only go for the nearest food source. It's used to predict gene expression for cancer classification.
3 minute video visualization - https://www.youtube.com/watch?v=3qQr1eZwz5E
>Fish Swarm Algorithm (FSA)
Also known as Particle Swarm Optimization. Here the agents behave like individual fish in a school of fish. I.e. every agent tries to be in the center of the school, to avoid a hypothetical predator, and balances that behavior with the desire to eat food.
Vis - https://www.youtube.com/watch?v=OUHAypWn1Ro
>Cat Swarm Optimization (CSO)
From another paper: "The original cat swarm optimization is a continuous and single-objective algorithm. It is inspired by resting and tracing behaviours of cats. Cats seem to be lazy and spend most of their time resting. However, during their rests, their consciousness is very high and they are very aware of what is happening around them. So, they are constantly observing the surroundings intelligently and deliberately and when they see a target, they start moving towards it quickly. Therefore, CSO algorithm is modeled based on combining these two main deportments of cats.
CSO algorithm is composed of two modes, namely, tracing and seeking modes. Each cat represents a solution set, which has its own position, a fitness value, and a flag. The position is made up of M dimensions in the search space, and each dimension has its own velocity; the fitness value depicts how well the solution set (cat) is; finally, the flag is to classify the cats into either seeking or tracing mode. Thus, we should first specify how many cats should be engaged in the iteration and run them through the algorithm. The best cat in each iteration is saved into memory, and the one at the final iteration will represent the final solution."
>Whale Optimization Algorithm (WOA)
WOA mimics the social behavior of humpback whales. The algorithm is inspired by the bubble-net hunting strategy.
10 minute explanation - https://www.youtube.com/watch?v=f7hvvDkLoHs
>Artificial Algae Algorithm (AAA)
>Elephant Search Algorithm (ESA)
>Chicken Swarm Optimization Algorithm (CSOA)
>Moth flame optimization (MFO)
>Grey Wolf Optimization (GWO) algorithm, which mimic the hunting technique and social leadership of grey wolves
>Social Spider Optimization (SSO) Algorithm
>Lion Optimization Algorithm (LOA) that mimics the behavior of lions and their characteristics of cooperation.
Other algorithms that I found:
> Ant swarm algorithm
An approximate solution to the travelling salesman problem. Say you have many agents that have to visit hundreds of thousands of locations, and each day some are added and removed. It is prohibitively expensive to calculate anew each day, so instead you do like ants. Each agent chooses a path somewhat at random, but also leaves a "pheromone trail" that decays with time. More efficient paths take less time, are traversed more times per day, and thus have heavier scent. Next time an agent considers two paths, it will be biased towards the path with a heavier scent. So you arrive at an approximately efficient solution.
>firefly algorithm https://www.youtube.com/watch?v=LPKg_luHxpc
>eagle strategy https://www.youtube.com/watch?v=cNEi_P6mUnY
[0] https://www.sciencedirect.com/science/article/pii/S231472881...