GSAT Enhanced with Learning Automata and Multilevel Paradigm
A large number of problems that occur in knowledge-representation, learning, very large scale integration technology (VLSI-design), and other areas of artificial intelligence, are essentially satisfiability problems. The satisfiability problem refers to the task of finding a satisfying assignment that makes a Boolean expression evaluate to True. The growing need for more efficient and scalable algorithms has led to the development of a large number of SAT solvers. This paper introduces two new techniques that combine finite learning automata and multilevel paradigm with the Greedy Satisfiability Algorithm (GSAT). We present a detailed comparative analysis of the new approaches using a benchmark set containing randomized and practical engineering applications from various domains.
Keywords: Satisfiability problem, learning automata, multilevel techniques, combinatorial optimization
Download Full-Text
ABOUT THE AUTHORS
Noureddine Bouhmala
Noureddine Bouhmala obtained his MSc from Federal Polytechnic of Lausanne 1994 and PhD from the University of Neuchatel in Switzerland. He is currently working at the Department of Maritime Technology and Innovation at Vestfold University College, Norway. His research interests include combinatorial optimization, data mining, and parallel computing.
Ole-Christoffer Granmo
Ole-Christoffer Granmo was born in Porsgrunn, Norway. He obtained his M.Sc. in 1999 and the Ph.D. degree in 2004, both from the University of Oslo, Norway. He is currently a Professor in the Department of ICT, University of Agder, Norway. His research interests include Intelligent Systems, Stochastic Modelling and Inference, Machine Learning, Pattern Recognition, Learning Automata, Distributed Computing, and Surveillance and Monitoring. He is the author of more than 55 refereed journal and conference publications.
Noureddine Bouhmala
Noureddine Bouhmala obtained his MSc from Federal Polytechnic of Lausanne 1994 and PhD from the University of Neuchatel in Switzerland. He is currently working at the Department of Maritime Technology and Innovation at Vestfold University College, Norway. His research interests include combinatorial optimization, data mining, and parallel computing.
Ole-Christoffer Granmo
Ole-Christoffer Granmo was born in Porsgrunn, Norway. He obtained his M.Sc. in 1999 and the Ph.D. degree in 2004, both from the University of Oslo, Norway. He is currently a Professor in the Department of ICT, University of Agder, Norway. His research interests include Intelligent Systems, Stochastic Modelling and Inference, Machine Learning, Pattern Recognition, Learning Automata, Distributed Computing, and Surveillance and Monitoring. He is the author of more than 55 refereed journal and conference publications.