Summary

Proceedings of the 2012 International Symposium on Nonlinear Theory and its Applications

2012

Session Number:C1L-C

Session:

Number:586

Amoeba-inspired SAT Solver

Masashi Aono,  Song-Ju Kim,  Liping Zhu,  Makoto Naruse,  Motoichi Ohtsu,  Hirokazu Hori,  Masahiko Hara,  

pp.586-589

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.1.586

PDF download (310KB)

Summary:
We propose a biologically-inspired computing algorithm called “AmoebaSAT” for solving an NP-complete combinatorial optimization problem, the Boolean satisfiability problem (SAT). AmoebaSAT is a hybrid of two dynamics; chaotic oscillatory dynamics for exploring the state space are combined with spatiotemporal control dynamics for bouncing back logically-false state transitions. For the former, we employ the logistic map as a unit for generating chaotic fluctuation. The control principle of the latter that we call “bounceback control” is designed to stabilize a state only when it represents a solution, i.e., a satisfiable assignment. We show that, for some benchmark problem instances, AmoebaSAT finds a solution faster than a well-known algorithm called “WalkSAT”, which is considered to be one of the fastest algorithms.

References:

[1] R. Poli, J. Kennedy, T. Blackwell, “Particle swarm optimization. An overview,” Swarm Intelligence, vol.1(1), pp.33-57, 2007.

[2] M. Aono, M. Hara, K. Aihara, “Amoeba-based neurocomputing with chaotic dynamics,” Communications of the ACM, vol.50(9), pp.69-72, 2007.

[3] M. Aono, Y. Hirata, M. Hara, K. Aihara, “Amoebabased chaotic neurocomputing: Combinatorial optimization by coupled biological oscillators,” New Generation Computing, vol.27, pp.129-157, 2009.

[4] M. R. Garey, D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H. Freeman and co., New York, 1979.

[5] U. Schoning, “A probabilistic algorithm for k-SAT and constraint satisfaction problems,” Proc. 40th Symposium on Foundations of Computer Science, pp.410-414, 1999.

[6] H. H. Hoos, T. Stutzle, “SATLIB: An online resource for research on SAT,” Proc. SAT2000, pp.283-292, IOS Press, 2000. Benchmark instances are available online at http://www.cs.ubc.ca/hoos/SATLIB/benchm.html

[7] K. Aihara, T. Takabe, M. Toyoda, “Chaotic neural networks,” Phys. Lett. A, vol.144, pp.333-340, 1990.

[8] M. Hasegawa, T. Ikeguchi, K. Aihara, “Combination of chaotic neurodynamics with the 2-opt algorithm to solve traveling salesman problems,” Phys. Rev. Lett., vol.79(12), pp.2344-2347, 1997.

[9] M. Hasegawa, K. Umeno, “Solvable performance of optimization neural networks with chaotic noises and stochastic noise with negative correlation,” Lecture Notes in Computer Science, vol.4984, pp.693-702, Springer, 2008.

[10] K. Umeno, “Performance of chaotic Monte Carlo computation and chaos codes for communications: Theory and experiments,” AIP Conf. Proc., vol.1339, pp.197-209, 2011.

[11] M. Naruse, M. Aono, S. -J. Kim, T. Kawazoe, W. Nomura, H. Hori, M. Hara, M. Ohtsu, “Spatiotemporal dynamics in optical energy transfer on the nanoscale and its application to constraint satisfaction problems,” submitted.