9 ms·

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

• Bostonian 5y ago
  Neural networks, although it's debatable how much they are based on biological algorithms. Genetic algorithms for optimization.
• itsthecourier 5y ago
  Breadth first search in a maze simulates a bacteria growing inside the maze
  • labarilem 5y ago
    So simple yet so complex
• kken 5y ago
  The chemical Basis of Morphogenesis - Alan Turing https://en.wikipedia.org/wiki/The_Chemical_Basis_of_Morphogenesis https://en.wikipedia.org/wiki/The_Chemical_Basis_of_Morphoge...
• loudmax 5y ago
  Lateral inhibition enhances the contrast at the visible borders between objects: https://en.wikipedia.org/wiki/Lateral_inhibition https://en.wikipedia.org/wiki/Lateral_inhibition
• amboo7 5y ago
  https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life?wprov=sfla1 https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life?wprov=...
• xaedes 5y ago
  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.
• cupofpython 5y ago
  Ant Colony Optimization is a type of graph search algorithm based on the way ants use pheromones https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms https://en.wikipedia.org/wiki/Ant_colony_optimization_algori...
• blenderdt 5y ago
  L-systems https://en.m.wikipedia.org/wiki/L-system https://en.m.wikipedia.org/wiki/L-system
  • carapace 5y ago
    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 http://algorithmicbotany.org/papers/#abop (It's mentioned in the Wikipedia article, but I feel it's worth "surfacing" here on it's own.)
    • dpflan 5y ago
      This books shows up every now and then on HN. Here are top search results for it that may have comments worthy of adding to this post's disccussion: - https://hn.algolia.com/?q=algorithmic+botany https://hn.algolia.com/?q=algorithmic+botany
• fellerts 5y ago
  The simple rules that govern Conway's Game of life have similarities to biological life (crowded cells die, etc.) https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
• tlarkworthy 5y ago
  Reactive robots inspired by insects (Braitenberg vehicle) https://en.m.wikipedia.org/wiki/Braitenberg_vehicle https://en.m.wikipedia.org/wiki/Braitenberg_vehicle
• pfdietz 5y ago
  Evolutionary search.
• c4py 5y ago
  Artificial bee colony optimization https://en.wikipedia.org/wiki/Artificial_bee_colony_algorithm https://en.wikipedia.org/wiki/Artificial_bee_colony_algorith...
• beaconstudios 5y ago
  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.
• nemetroid 5y ago
  Far too many. https://github.com/fcampelo/EC-Bestiary https://github.com/fcampelo/EC-Bestiary EDIT: updated link.
  • junon 5y ago
    https://github.com/fcampelo/EC-Bestiary https://github.com/fcampelo/EC-Bestiary Here's the updated repository.
• loloquwowndueo 5y ago
  Gravity sort: https://en.m.wikipedia.org/wiki/Bead_sort https://en.m.wikipedia.org/wiki/Bead_sort The algorithm itself is somewhat limited but the visual representation is mesmerizing :) https://m.youtube.com/watch?v=MneHbUXyKHg https://m.youtube.com/watch?v=MneHbUXyKHg
• specialist 5y ago
  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-Evolutionary-Computation/dp/1558605959 https://www.amazon.com/Intelligence-Morgan-Kaufmann-Evolutio... I'm happy to see their website is still up: http://www.swarmintelligence.org 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 5y ago
    Maybe you could find the Google Hashcode problems to be interesting for a weekend project
• fivea 5y ago
  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 5y ago
    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_metaheuristics https://en.m.wikipedia.org/wiki/List_of_metaphor-based_metah...
    • matsemann 5y ago
      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 5y ago
        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 5y ago
        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.
  • 5y ago
• shiado 5y ago
  https://en.wikiversity.org/wiki/Slime_Mould_Algorithm https://en.wikiversity.org/wiki/Slime_Mould_Algorithm
• stevofolife 5y ago
  Genetic feature selection
• SamBam 5y ago
  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 5y ago
    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 5y ago
    > 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 5y ago
      >>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.
• leros 5y ago
  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.
  • troymc 5y ago
    Your suspicion is correct. An example is Ant Colony Optimization [1], a general-purpose optimization technique. [1] https://scholar.google.com/scholar?hl=en&as_sdt=0%2C5&q=ant+colony+optimization&btnG= https://scholar.google.com/scholar?hl=en&as_sdt=0%2C5&q=ant+...
  • gteton12 5y ago
    I had an internship doing this, using https://wyss.harvard.edu/media-post/kilobots-a-thousand-robot-swarm/ https://wyss.harvard.edu/media-post/kilobots-a-thousand-robo...
• jamessb 5y ago
  The book "Bio-Inspired Artificial Intelligence" is a good introduction [1,2 ] to a range of techniques. [1]: https://mitpress.mit.edu/books/bio-inspired-artificial-intelligence https://mitpress.mit.edu/books/bio-inspired-artificial-intel... [2]: https://baibook.epfl.ch/contents.html https://baibook.epfl.ch/contents.html
• arjun_krishna1 5y ago
  Epidemic/Gossip protocol (https://en.wikipedia.org/wiki/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.
• intunderflow 5y ago
  Neuroevolution of Augmenting Topologies is a classic genetic algorithm, as a teenager it was my first genetic algorithm I implemented after watching a Youtube video of an implementation of it - https://www.youtube.com/watch?v=qv6UVOQ0F44 https://www.youtube.com/watch?v=qv6UVOQ0F44
• moeny 5y ago
  Just counting https://www.ouruboroi.com/ https://www.ouruboroi.com/ "...what was doubled is reduced by the amount of the predecessor."
• istinetz 5y ago
  The obvious one is neural networks :) 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 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 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 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 https://www.youtube.com/watch?v=LPKg_luHxpc >eagle strategy https://www.youtube.com/watch?v=cNEi_P6mUnY https://www.youtube.com/watch?v=cNEi_P6mUnY [0] https://www.sciencedirect.com/science/article/pii/S2314728818300631 https://www.sciencedirect.com/science/article/pii/S231472881...
• cosmic_quanta 5y ago
  There are so many optimization algorithms based on nature: https://arxiv.org/abs/2106.04775 https://arxiv.org/abs/2106.04775
• WithinReason 5y ago
  Neural networks
  • bannedbybros 5y ago
• mindcrime 5y ago
  There's a lot of them. Here's one interesting book that catalogs many, with implementations. https://github.com/clever-algorithms/CleverAlgorithms 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) https://en.wikipedia.org/wiki/Flocking_(behavior) -- simulations of animal flocking behavior have found some applications https://en.wikipedia.org/wiki/Artificial_life 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 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". https://en.wikipedia.org/wiki/Chemical_computer https://en.wikipedia.org/wiki/Chemical_computer https://en.wikipedia.org/wiki/DNA_computing https://en.wikipedia.org/wiki/DNA_computing
• ganzuul 5y ago
  Reaction–diffusion system https://en.wikipedia.org/wiki/Reaction%E2%80%93diffusion_system https://en.wikipedia.org/wiki/Reaction%E2%80%93diffusion_sys...
• jwally 5y ago
  Particle Swarm Optimization is a simple 2 function algorithm that is fun to play with and watch. You can do it in an excel spreadsheet with one particle and watch it solve it - spooky effective.
• egberts1 5y ago
  My favorite is the geological S-shaped river bends that is used toward network fast-path algorithm.
• voldacar 5y ago
  Not sure if this counts, but you can use slime molds to optimize road networks https://arxiv.org/pdf/0912.3967.pdf https://arxiv.org/pdf/0912.3967.pdf
• martingoodson 5y ago
  Geoff hinton’s dropout was based on neuronal stochasticity. Convolutional neural networks were based on the processing in the V1 visual cortex.
• technocratius 5y ago
  Boids https://en.m.wikipedia.org/wiki/Boids https://en.m.wikipedia.org/wiki/Boids
• thaumaturgy 5y ago
  Not fashionable, but Gompertz curves: https://en.wikipedia.org/wiki/Gompertz_function https://en.wikipedia.org/wiki/Gompertz_function 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.
• andbberger 5y ago
  sparse coding
• bashinator 5y ago
  The TCP window sizing algorithm happens to also be used by some ant colonies - https://biomimicry.org/introducing-the-anternet/ https://biomimicry.org/introducing-the-anternet/ - it wasn't based on the ants' behavior, but it's a nifty example of some kind of convergent evolution.
• meatsock 5y ago
  here[1] are some artists using algorithms based on biological organisims to create some stuff that's just visually fantastic. in this example they've created a nice looking objects based on reaction diffusion wrt brain coral growth. [1]: https://n-e-r-v-o-u-s.com/ https://n-e-r-v-o-u-s.com/
• vermarish 5y ago
  Sparse Sensor Placement Optimization for Classification 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. [0]: https://youtu.be/zJ2z__5mepA?t=744 https://youtu.be/zJ2z__5mepA?t=744
• chermi 5y ago
  Edit -- I'm an idiot and misread OP. I read "inspired by nature", rather than specifically "biology". Keeping everything below here just for goofs. I think the only thing that applies is the Computational Beauty of Nature book recc. -------- 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_JQXYJZNWM1MBQ779JSCF https://www.amazon.com/dp/1947864076/ref=cm_sw_r_apan_i_JQXY... And most emphatically, Information, inference, and learning - Mackay
• syngrog66 5y ago
  Conway's Game of Life was my 1st thought, and cellular automata in general Mandelbrot's fractal set certainly looks like a biological structure but I dont think it originated due to thinking about it.
• photochemsyn 5y ago
  Smith-Waterman is one of the core algorithms used to align DNA sequences and describe similarity. It's worth taking a look at: > "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)"
• riwsky 5y ago
  Bogosort
• adamcrow64 5y ago
  I used a genetic algorithm back in 1993 to calibrate a commercial 3D freight laser scanner. The problem we had was that the triangulation equations for the laser angle, camera pixel map, and distance between the camera and the laser axis were very difficult to solve using standard equation solving. In the end we created a calibration 'box' that we scanned. Without ANY hints our genetic algorithm found an optimal calibration set within 45 generations. Fantastic!
• kaskakokos 5y ago
  All, we cannot invent an algorithm outside of biological world. It happens that we have not associated an explanatory biological understanding to it.