Skip to content
Home » Physics & Bio Inspired Computing

Physics & Bio Inspired Computing

With Moore’s law coming to an end, and, with it, the digital age, alternative novel computing systems have to be explored. Physical systems and processes, just like biological ones, can inspire the design of computer algorithms. We actively research a range of physical phenomena and have implemented a range of algorithms which draw inspiration from aspects of these phenomena. This section provides an overview of some of our work in the area of bio-inspired as well as physics-inspired computing.

Early Ideas

The ideas behind biological computing trace back to 1936 and the first description of an abstract computer, which is now known as a Turing machine. Turing firstly described the abstract construct using a biological specimen. Turing imagined a mathematician that has three important attributes. He always has a pencil with an eraser, an unlimited number of papers and a working set of eyes. The eyes allow the mathematician to see and perceive any symbols written on the paper while the pencil allows him to write and erase any symbols that he wants. Lastly, the unlimited paper allows him to store anything he wants memory. Using these ideas he was able to describe an abstraction of the modern digital computer. However Turing mentioned that anything that can perform these functions can be considered such a machine and he even said that even electricity should not be required to describe digital computation and machine thinking in general.

Bio-Inspired Computing

In recent years, the research community has witnessed an explosion of literature dealing with the adaptation of behavioural patterns and social phenomena observed in nature towards efficiently solving complex computational tasks. This trend has been especially dramatic in what relates to optimisation problems, mainly due to the unprecedented complexity of problem instances, arising from a diverse spectrum of domains such as transportation, logistics, energy, climate, social networks, health and industry 4.0, among many others. Notwithstanding this upsurge of activity, research in this vibrant topic should be steered towards certain areas that, despite their eventual value and impact on the field of bio-inspired computation, still remain insufficiently explored to date. Some areas of study in biologically inspired computing, and their biological counterparts:

Verilog (FPGA) implementation of the paper “A Circuit-Level Amoeba-Inspired SAT Solver” from N. Takeuchi, Member, IEEE, M. Aono, Y. Hara-Azumi, and C. L. Ayala, Member, IEEE. The proposed solver is a biologically-inspired stochastic local search (SLS) solver to explore solutions to the Boolean satisfiability problem (SAT). It updates multiple variables in parallel at every iteration step, and thus it can find solutions with a fewer number of iteration steps than some other conventional SLS solvers for a specific set of SAT instances. However, the parallelism of the solver is not compatible with general-purpose microprocessors in that many clock cycles are required to execute each iteration; thus, it requires special hardware that can exploit the parallelism to quickly find solutions.

In their paper, they propose a circuit model (hardware-friendly algorithm) that explores solutions to SAT, which they call circuit-level AmbSAT (CLAmbSAT). The authors conducted numerical simulation to evaluate the search performance of CL-AmbSAT for a set of randomly generated SAT instances that was designed to estimate the scalability of their approach. Simulation results showed that CLAmbSAT finds solutions with a fewer iteration number than a powerful SLS solver, ProbSAT, and outperforms even AmbSAT. Since CL-AmbSAT uses simple combinational logic to update variables, CL-AmbSAT can be easily implemented in various hardware.

Read also Using Bio-Inspired Computing to Efficiently Solve SAT problems with more details about the implementation.

Source code repository on GitHub:
https://github.com/daniel009988/Circuit-Level-Amoeba-Inspired-SAT-Solver
Research paper:
https://arxiv.org/pdf/1812.11792.pdf

Physics-Inspired Computing

Computationally challenging optimisation problems have always been of special interest by various researchers around
the globe. This is primarily due to them often having a very high dimensional search space, or having highly complex
and non-linear objective functions at their core, which classical gradient-based methods fail to tackle efficiently. This
has been the main reason for the development of metaheuristic algorithms that take inspiration from our surroundings
(nature, swarms and physical processes) and can provide a computationally cheap yet robust optimisation procedure
for such hard problems at hand. Parallely, researchers have also noticed the undeniable success of modeling physics’
processes to study highly complex phenomena, both in real-world and computer science. For instance, resource
allocation problem has been well tackled by statistical mechanics models, while certain aspects of statistical
thermodynamics have been employed to explain micro-evolution of species, and so on. As a result, in spite of
swarm-inspired algorithms being in the forefront as robust optimisers, researchers have shown keen interest in
adapting principles and theories of physics and applying them to solve real-world optimisation problems.
Recently, the world of metaheuristics has seen the advent of several novel search mechanisms based on various
non-linear physics processes. The novelty of these approaches lies in the fact that the non-linear physical phenomena
are leveraged as backbones to be modeled upon in order to formulate efficient search algorithms, whose mechanism is
quite different from the conventional swarm and evolutionary algorithms. Such physics-inspired algorithms have shown
great promise and robustness as global optimisation strategies. For a good overview of the different approaches we refer to:

A Brief Overview of Physics-inspired Metaheuristic Optimization Techniques
Soumitri Chattopadhyay, Aritra Marik, Rishav Pramanik (2022)

In “Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states“, Memcomputing is introduced as a novel non-Turing paradigm of computation that uses interacting memory cells (memprocessors for short) to store and process information on the same physical platform. It is claimed that it was recently proven mathematically that memcomputing machines have the same computational power of nondeterministic Turing machines. Therefore, they should solve NP-complete problems in polynomial time and, using the appropriate architecture, with resources that only grow polynomially with the input size. Our implementation reproduces the results as shown in the paper.

This repository is an implementation of the Digital Memcomputing Machine (DMM) described in the paper with the goal to verify if the results of the paper can be reproduced as well as to investigate if the performance extends to other SAT problem classes. Based on the boost library, it supports multiple ODE integration schemes and has a few parameter tuning options.

Read also Physics Inspired Computation — Solving Constraint Satisfaction Problems with Physics with details about the implementation.

Source code repository on GitHub:
https://github.com/daniel009988/Digital-Memcomputing-Sat-Solver
Research paper:
https://www.science.org/doi/10.1126/sciadv.1500031