Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Multilevel Genetic Algorithm for the Maximum Constraint Satisfaction Problem Read chapter Read first chapter

2017 | OriginalPaper | Chapter

WalkSAT Based-Learning Automata for MAX-SAT

Authors : N. Bouhmala, M. Oseland, Ø. Brådland

Published in: Recent Advances in Soft Computing

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Researchers in artificial intelligence usually adopt the Satisfiability paradigm as their preferred methods when solving various real worlds decision making problems. Local search algorithms used to tackle different optimization problems that arise in various fields aim at finding a tactical interplay between diversification and intensification to overcome local optimality while the time consumption should remain acceptable. The WalkSAT algorithm for the Maximum Satisfiability Problem (MAX-SAT) is considered to be the main skeleton underlying almost all local search algorithms for MAX-SAT. This paper introduces an enhanced variant of WalkSAT using Finite Learning Automata. A benchmark composed of industrial and random instances is used to compare the effectiveness of the proposed algorithm against state-of-the-art algorithms.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Geometric Particle Swarm Optimization and Reservoir Computing for Solar Power Forecasting
next chapter A Self-adaptive Artificial Bee Colony Algorithm with Incremental Population Size for Large Scale Optimization
Literature
1.
Audemard, G., Simon, L.: Predicting learnt clauses quality in modern SAT solvers. In: Twenty-First International Joint Conference on Artificial Intelligence (IJCAI 2009), July 2009
2.
Bouhmala, N.: A variable neighborhood search structure based-genetic algorithm for combinatorial optimization problems. Int. J. Hybrid Intell. Syst. Theor. Appl. 15(2), 127–146 (2016)
3.
Bouhmala, N.: Variable neighborhood walksat-based algorithm for MAX-SAT problems. Sci. World J. 2014, 11 (2014). Article ID 798323CrossRef
4.
Frank, J.: Learning short-term clause weights for GSAT. In: Proceedings of IJCAI 1997, pp. 384–389. Morgan Kaufmann Publishers (1997)
5.
Cai, S., Luo, C., Su, K.: CCASat: solver description. In: Proceedings of SAT Challenge 2012: Solver and Benchmark Descriptions, pp. 13–14 (2012)
6.
Cook, S.: The complexity of theorem-proving procedures. In: Proceedings of the Third ACM Symposium on Theory of Computing, pp. 151–158 (1971)
7.
Granmo, O.C., Bouhmala, N.: Solving the satisfiability problem using finite learning automata. Int. J. Comput. Sci. Appl. 4(3), 15–29 (2007). Special Issue on Natural Inspired Computation
8.
Granmo, O.C., Oommen, B.J., Myrer, S.A., Olsen, M.-G.: Learning automata-based solutions to the nonlinear fractional Knapsack problem with applications to optimal resource allocation. IEEE Trans. Syst. Man Cybern. SMC–37(B), 166–175 (2007)CrossRef
9.
Hansen, P., Jaumard, B., Mladenovic, N., Parreira, A.D.: Variable neighborhood search for maximum weighted satisfiability problem. Technical report G-2000-62, Les Cahiers du GERAD, Group for Research in Decision Analysis (2000)
10.
Hoos, H.: On the run-time behavior of stochastic local search algorithms for SAT. In: Proceedings of AAAI 1999, pp. 661–666 (1999)
11.
KhudaBukhsh, A.R., Xu, L., Hoos, H.H., Leyton-Brown, K.: SATenstein: automatically building local search SAT solvers from components. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2009) (2009)
12.
Li, C.M., Wei, W., Zhang, H.: Combining adaptive noise and look-ahead in local search for SAT. In: Marques-Silva, J., Sakallah, K.A. (eds.) SAT 2007. LNCS, vol. 4501, pp. 121–133. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-72788-0_​15 CrossRef
13.
McAllester, D., Selman, B., Kautz, H.: Evidence for invariants in local search. In: Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI 1997), pp. 321–326 (1997)
14.
Narendra, K.S., Thathachar, M.A.L.: Learning Automata: An Introduction. Prentice Hall, Upper Saddle River (1989)MATH
15.
Selman, B., Kautz, H.A., Cohen, B.: Noise strategies for improving local search. In: Proceedings of AAAI 1994, pp. 337–343. MIT Press (1994)
16.
Smyth, K., Hoos, H., \(St\ddot{u}tzle\), T.: Iterated robust tabu search for MAX-SAT. Lecture Notes in Artificial Intelligence, vol. 2671, pp. 129–144 (2003)
17.
Thathachar, M.A.L., Sastry, P.S.: Network of Learning Automata: Techniques for on Line Stochastic Optimization. Kluwer Academic Publishers, Boston (2004)CrossRef
18.
Tsetlin, M.L.: Automaton Theory and Modeling of Biological Systems. Academic Press, New York (1973)MATH
19.
Yagiura, M., Ibaraki, T.: Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: experimental evaluation. J. Heuristics 7(5), 423–442 (2001)CrossRefMATH
20.
Zhipeng, L., Jin-Kao, H.: Adaptive memory-based local search for MAX-SAT. Appl. Soft Comput. 12(8), 2063–2071 (2012)CrossRef
Metadata
Title
WalkSAT Based-Learning Automata for MAX-SAT
Authors
N. Bouhmala
M. Oseland
Ø. Brådland
Copyright Year
2017
Book
Recent Advances in Soft Computing

Print ISBN: 978-3-319-58087-6

Electronic ISBN: 978-3-319-58088-3

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-58088-3_10

Premium Partner

    Image Credits