HN Explorer

Ask HN: Which algorithms based on biological ideas do you know?

135 points by labarilem ↗ HN
Algorithms don't have to be state of the art.

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

85 comments

[ 5.5 ms ] story [ 160 ms ] thread
Bostonian
Neural networks, although it's debatable how much they are based on biological algorithms. Genetic algorithms for optimization.
itsthecourier
Breadth first search in a maze simulates a bacteria growing inside the maze
xaedes
Here are some keywords for further research. It is a rich and beautiful topic!

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.

blenderdt
L-systems

https://en.m.wikipedia.org/wiki/L-system

carapace
Yeah! It's not exactly "algorithms based on biological ideas", more like formal systems that mimic certain morphological aspects of plant life, but well worth a look: "The Algorithmic Beauty of Plants" http://algorithmicbotany.org/papers/#abop (It's mentioned in the Wikipedia article, but I feel it's worth "surfacing" here on it's own.)
beaconstudios
Basically any algorithm that uses heuristics and iterative fitting, like A*, bin packing algorithms, gradient descent. I like algorithms that don't just compute an answer, but iterate and approximate - usually to solve a problem that's NP-hard or otherwise fuzzy.
specialist
As a total noob, I got a lot out of the book Swarm Intelligence [2001] by Eberhart, Shi, and Kennedy. Terrific survey of optimization overall and then dives into bee colony inspired algorithms (particle swarm optimization). Lots of books with similar name, so here's the link:

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.

labarilem
Maybe you could find the Google Hashcode problems to be interesting for a weekend project
fivea
Oh I know a few. Evolution strategies, particle swarm optimization, ant colony optimization, etc, etc.

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.

pragmatic8
This should not have been downvoted; parent’s criticism is not unfounded. Take a look at the second section of this Wikipedia page:

https://en.m.wikipedia.org/wiki/List_of_metaphor-based_metah...

matsemann
Why not? OP asked for algorithms and explicitly said they didn't have to be state of the art. Then saying them not being state of the art is hardly relevant?

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".

labarilem
Yeah I know most of these algorithms are not state of the art. That's why I explicitly said that. Still, I find it interesting to read about them. It satisfies a curiosity of mine, hopefully shared with other people here too.
lukas099
HN comments aren't StackOverflow answers. They're allowed to go off on tangents. Personally, I like to see nuances that I didn't before and so appreciated and upvoted the comment.
mindcrime
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.

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."

ogogmad
I was under the impression that memetic algorithms for TSP (Travelling Salesman Problem) performed a lot better than expected: https://en.wikipedia.org/wiki/Memetic_algorithm

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.

SamBam
I wrote my MSc on improving certain Genetic Algorithms by incorporating biologists' ideas of "exaptation," or having features that were evolved for use in one context providing a jump in another context.

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.)

ailef
I've always loved genetic algorithms and similar ideas. Unfortunately, as you said, they are not that common now unless maybe in some niche use cases. It's very fun to use them for a weekend project, though.
tomrod
> 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.

fivea
>>I fully anticipate they will come back in fashion.

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.

nicoco
I usually use CMA-ES as a 'very easy to set and up and better than brute force' approach. Am I dumb to do that? (genuine question, no irony, optimization is not my field at all)
rusticpenn
I have used swarm optimization methods that have consistently provided better solutions than alternatives for optimizations of solution spaces in alterst 3 different domains. I am not sure what you are talking about.
fivea
> I have used swarm optimization methods that have consistently provided better solutions than alternatives for optimizations of solution spaces in alterst 3 different domains.

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.

rusticpenn
Unfortunately I don’t currently have access to this data. I can tell you that it’s leagues better than any Monte Carlo implementation as I have done this comparison as a litmus test for several population based algorithms in the past. I I’ll look into making a comparison with DIRECT when I have time (not anytime this month)
tomrod
To my understanding, they are coming back in vogue with neural architecture search. But hey, it's newish, so maybe you're one of today's lucky 10,000. https://xkcd.com/1053
api
IMHO genetic algorithms are waiting for their AlexNet paper:

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.

apl
An AlexNet/ResNet-type moment may be in the cards for GAs, but I wouldn't put any money on it. They're typically only one better than brute-force. This can be good enough (and is certainly easy to implement), but if you can get a gradient for your problem -- you should use that. And nowadays, you can typically get a gradient!

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.

api
If biological evolution wasn't much better than brute force we would not be here. There is no way you could randomly generate a functional genome for anything non-trivial in any reasonable multiple of the age of the universe even if you had a trillion Earths to work with.

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.

randomsearch
Speculative comments: evolving neural network architectures may be where EAs prove their worth.

Plenty of work on it but it’s early days and we need massive, massive, compute power.

apl
Neural architecture search (NAS) is a thing! But it's almost exclusively based on meta-gradients. Again, wouldn't put my money on GAs ever outperforming gradient-based methods again.
tomrod
Is the parameter space convex?
api
GAs follow gradients too. It's a different learning approach. All learning follows gradients in one form or another except brute force search, which is not feasible for anything larger than about 2^80 bits of state space. Evolution is not brute force.
sitkack
Can you combine NAS and GAs?
lol1lol
I'm interested to explore GA -- What are some cool GA papers published recently, which research labs focus on it?
steve_gh
Nice to see this sort of thing coming back - it was a problem I worked on for a couple of years during my MSc / PhD.

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...

amelius
How did wings evolve in insects?
Teever
I would imagine that the lift to mass ratio of a small animal like an insect would be more forgiving, allowing an organism that evolved those '1%' wings through random mutation to see sufficient benefit that a selective pressure could then produce larger and more articulatable '2%' and then '3%' wings and so on...
amelius
Wouldn't it make sense that bird-wings started also with small animals in evolution?
Teever
Yes but I don't think the smallest birds are all that comparable in size to the smallest insects.

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.

lukas099
> For example, it's quite difficult to imagine how wings evolved, since 1% of a wing seems to offer no fitness advantage

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.

leros
I always had an interest in studying ant colony behavior and seeing if I could use those concepts to program robot swarms. I never did but I'm sure it's being done.
arjun_krishna1
Epidemic/Gossip protocol (https://en.wikipedia.org/wiki/Gossip_protocol) Uses peer-to-peer communication to disseminate data to all members of a group A node starts with a piece of data, shares it with its neighbors. Then the neighbors repeat this. The spread of data is inspired by the spread of a disease or gossip among a group of organisms.