Similar articles

Abstract: Based on our recent study on probability distributions for evolution in extremal optimization (EO), we propose a modified framework called EOSAT to approximate ground states of the hard maximum satisfiability (MAXSAT) problem, a generalized version of the satisfiability (SAT) problem. The basic idea behind EOSAT is to generalize the evolutionary probability distribution in the Bose-Einstein-EO (BE-EO) algorithm, competing with other popular algorithms such as simulated annealing and WALKSAT. Experimental results on the hard MAXSAT instances from SATLIB show that the modified algorithms are superior to the original BE-EO algorithm.

[1]Alava, M., Ardelius, J., Aurell, E., Kaski, P., Krishnamurthy, S., Orponen, P., Seitz, S., 2008. Circumspect descent prevails in solving random constraint satisfaction problems. PNAS, 105(40):15253-15257.

[2]Altarelli, F., Monasson, R., Smerjian, G., Zamponi, F., 2009. A Review of the Statistical Mechanics Approach to Random Optimization Problems. Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, Vol. 185. IOS Press, the Netherlands.

[3]Bak, P., Sneppen, K., 1993. Punctuated equilibrium and criticality in a simple model of evolution. Phys. Rev. Lett., 71(24):4083-4086.

[4]Bak, P., Tang, C., Wiesenfeld, K., 1987. Self-organized criticality: an explanation of the 1/f noise. Phys. Rev. Lett., 59(4):381-384.

[5]Barthel, W., Hartmann, A.K., Weigt, M., 2003. Solving satisfiability problems by fluctuations: the dynamics of stochastic local search algorithms. Phys. Rev. E, 67(6):066104.

[6]Biere, A., Heule, M., Maaren, H., Walsh, T., 2009. Handbook of Satisfiability. IOS Press, the Netherlands.

[7]Biroli, G., Cocco, S., Monasson, R., 2002. Phase transitions and complexity in computer science: an overview of the statistical physics approach to the random satisfiability problem. Phys. A, 306:381-394.

[8]Boettcher, S., Percus, A.G., 2000. Nature’s way of optimizing. Artif. Intell., 119(1-2):275-286.

[9]Boettcher, S., Percus, A.G., 2001a. Optimization with extremal dynamics. Phys. Rev. Lett., 86(23):5211-5214.

[10]Boettcher, S., Percus, A.G., 2001b. Extremal optimization for graph partitioning. Phys. Rev. E, 64(2):026114.

[11]Boettcher, S., Percus, A.G., 2004. Extremal optimization at the phase transition for the three-coloring problem. Phys. Rev. E, 69(6):066703.

[12]Cheeseman, P., Kanefsky, B., Taylor, W.M., 1991. Where the Really Hard Problems Are. Proc. 12th Int. Joint Conf. on Artificial Intelligence, p.331-337.

[13]Garey, M.R., Johnson, D.S., 1979. Computers and Intractability: a Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York.

[14]Glover, F., 1989. Tabu search: part I. ORSA J. Comp., 1(3):190-206.

[15]Gomes, C., Selman, B., 2002. Satisfied with physics. Science, 297(5582):784-785.

[16]Haken, H., Wolf, H.C., 1996. The Physics of Atoms and Quanta (5th Ed.). Springer-Verlag, Berlin.

[17]Hamacher, K., 2007. Adaptive extremal optimization by detrended fluctuation analysis. J. Comput. Phys., 227(2):1500-1509.

[18]Hansen, P., Jaumard, B., 1990. Algorithms for maximum satisfiability problems. Computing, 44(4):279-303.

[19]Hartmann, A.K., Weigt, M., 2005. Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics. Wiley-VCH Verlag GmbH & Co. KGaA.

[20]Heilmann, F., Hoffmann, K.H., Salamon, P., 2004. Best possible probability distribution over extremal optimization ranks. Europhys. Lett., 66(3):305-310.

[21]Hoffmann, K.H., Heilmann, F., Salamon, P., 2004. Fitness threshold accepting over extremal optimization ranks. Phys. Rev. E, 70(4):046704.

[22]Hoos, H.H., Stuzle, T., 1999. SATLIB—the Satisfiability Library. Available from http://www.cs.ubc.ca/~hoos/SATLIB/benchm.html [Accessed on Mar. 18, 2010].

[23]Kirkpatrick, S., Gelatt, C.D.Jr., Vecchi, M.P., 1983. Optimization by simulated annealing. Science, 220(4598):671-680.

[24]Menaï, M.B., Batouche, M., 2006. An effective heuristic algorithm for the maximum satisfiability problem. Appl. Intell., 24(3):227-239.

[25]Mézard, M., Parisi, G., Zecchina, R., 2002. Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812-815.

[26]Middleton, A.A., 2004. Improved extremal optimization for the Ising spin glass. Phys. Rev. E, 69(5):055701.

[27]Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L., 1999. Determining computational complexity from characteristic ‘phase transition’. Nature, 400:133-137.

[28]Seitz, S., Alava, M., Orponen, P., 2005. Focused local search for random 3-satisfiability. J. Statist. Mech. Theor. Exp., 2005(6):P06006.

[29]Selman, B., 2008. Computational science: a hard statistical view. Nature, 451(7179):639-640.

[30]Selman, B., Kautz, H.A., 1993. An Empirical Study of Greedy Local Search for Satisfiability Testing. Proc. 11th National Conf. on Artificial Intelligence, p.46-51.

[31]Selman, B., Kautz, H.A., Cohen, B., 1994. Noise Strategies for Improving Local Search. Proc. 12th National Conf. on Artificial Intelligence, p.337-343.

[32]Semerjian, G., Monasson, R., 2003. Relaxation and metastability in a local search procedure for random satisfiability problem. Phys. Rev. E, 67(6):066103.

[33]Szedmak, S., 2001. How to Find More Efficient Initial Solution for Searching. RUTCOR Research Report 49-2001, Rutgers Center for Operations Research, Rutgers University, Piscataway, New Jersey, USA.

[34]Zeng, G.Q., Lu, Y.Z., 2009. Survey on Computational Complexity with Phase Transitions and Extremal Optimization. Proc. 48th IEEE Conf. on Control and Decision & 28th Chinese Control Conf., p.4352-4359.

[35]Zeng, G.Q., Lu, Y.Z., Mao, W.J., Chu, J., 2010. Study on probability distributions for evolution in modified extremal optimization. Phys. A, 389(9):1922-1930.

[36]Zhang, W.X., 2001. Phase transitions and backbones of 3-SAT and maximum 3-SAT. LNCS, 2239:153-167.

[37]Zhang, W.X., 2004. Configuration landscape analysis and backbone guided local search. Part I: satisfiability and maximum satisfiability. Artif. Intell., 158(1):1-26.

[38]Zhou, T., Bai, W.J., Cheng, L.L., Wang, B.H., 2005. Continuous extremal optimization for Lennard-Jones clusters. Phys. Rev. E, 72(1):016702.