Apr. 7, 2014
Solution search computer inspired from slime mold
RIKEN No.: 08028, 08093
Masashi Aono, Masahiko Hara et al.
[Solution search computer utilizing slime mold]
In contrast to the conventional Neumann-type digital computers, information is processed among large groups of biological molecules in autonomously distributed ways in biological tissues. If we can learn from such information processing by massively parallel molecular computing systems and establish a methodology for its control, there will be possibilities to develop non-Neumann-type computers that can search for the solution efficiently and at a high speed with low energy consumption or autonomously adapt to unexpected environmental changes through utilization of physical properties and dynamics of materials different from silicon devices. Based on these expectations, we have been working on research and development of BioComputers capable of searching for the solutions to various combinational optimization problems by controlling the deformation behaviors by an amoeba-like single-celled organism, the true slime mold Physarum Polycephalum, by optical stimulation.
Fig.1: Experiment setup for slime mold computer (bounceback control)
Fig.2: Slime mold computer to search for a solution to the traveling salesman problem
[Solution search computer utilizing quantum dot]
It is possible to solve the “Satisfiability Problem (SAT),” which is known to be a NP complete problem that leads combinational explosion, by introducing the optical “bounceback control” inspired from slime mold computer and utilizing the spatiotemporal dynamics of exciton migration in quantum dot (with nanostructures such as InGaAs, ZnO and CdSe) network. The systems capable of search for the solution to SAT can be applied to extremely large area of applications including automatic inference related to the development of artificial intelligence, software/hardware verification, information security and protein structure prediction in association to bioinformatics. Furthermore, it is possible to address highly versatile computers capable of searching for solutions with high speed, efficiency, and low energy consumption since the energy consumption of exciton migration which is the operation unit is approximately 1/10,000 that of operation unit (bit flip circuit) for the conventional electronic devices. (* This study has been conducted as a joint study between NICT and The University of Tokyo.)
Fig.3: Exciton transfer dynamics similar to slime mold protoplasm streaming
All "migration" should be replaced with "transfer".
All "level occupation" should be replaced with "stage filling"
Fig.4: Bounceback control for search for a solution to Satisfiability Problem (SAT)
[Solution search computer utilizing electronic circuits]
We have learned from the solution search dynamics of slime mold computer and formulated “AmoebaSAT,” SAT solution search model which extracts the essential qualities. AmoebaSAT delivers an excellent performance as an algorithm that also runs on the conventional digital computers and is capable of searching for the solution in a short time with a dramatically smaller number of iterations than “WalkSAT,” a conventionally well-known algorithm. Furthermore, AmoebaSAT is expressed in a dynamical system model format that describes physical motions unlike normal algorithms which are expressed in program formats, and thus can be mounted on various different physical systems including electronic circuit (such as FPGA).
Fig.5: Slime mold algorithm AmoebaSAT
Fig.6: Efficient and high-speed SAT solution search capability of slime mold algorithm
- 1.Japanese patent No.45725
- 2.Japanese patent application No.2012-116725, US patent application No.13/898335
- 3.Japanese patent application No.2012-232402