Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2017 | OriginalPaper | Buchkapitel

A Multilevel Genetic Algorithm for the Maximum Constraint Satisfaction Problem

verfasst von : Noureddine Bouhmala, Halvard Sanness Helgen, Knut Morten Mathisen

Erschienen in: Recent Advances in Soft Computing

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The constraint satisfaction problem is a useful and well-studied framework for the modeling of many problems rising in Artificial Intelligence and other areas of Computer Science. As many real-world optimization problems become increasingly complex and hard to solve, better optimization algorithms are always needed. Genetic algorithms (GA) which belongs to the class of evolutionary algorithms is regarded as a highly successful algorithm when applied to a broad range of discrete as well continuous optimization problems. This paper introduces a hybrid approach combining a genetic algorithm with the multilevel paradigm for solving the maximum constraint satisfaction problem. The promising performances achieved by the proposed approach is demonstrated by comparisons made to solve conventional random benchmark problems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Nächstes Kapitel Models and Simulations of Queueing Systems
Literatur
1.
Bacanin, N., Tuba, M.: Artificial bee colony (ABC) algorithm for constrained optimization improved with genetic operators. Stud. Inf. Control 21(2), 137–146 (2012)
2.
Bonyadi, M., Li, X., Michalewicz, Z.: A hybrid particle swarm with velocity mutation for constraint optimization problems. In: Genetic and Evolutionary Computation Conference, pp. 1–8. ACM, New York (2013). ISBN 978-1-4503-1963-8
3.
4.
Curran, D., Freuder, E., Jansen., T.: Incremental evolution of local search heuristics. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, GECCO 2010, pp. 981–982. ACM, New York (2010)
5.
Davenport, A., Tsang, E., Wang, C.J., Zhu, K.: Genet: a connectionist architecture for solving constraint satisfaction problems by iterative improvement. In: Proceedings of the Twelfth National Conference on Artificial Intelligence (1994)
6.
7.
Gent, I.P., MacIntyre, E., Prosser, P., Walsh, T.: The constrainedness of search. In: Proceedings of the AAAI 1996, pp. 246–252 (1996)
8.
Fang, S., Chu, Y., Qiao, K., Feng, X., Xu, K.: Combining edge weight and vertex weight for minimum vertex cover problem. FAW 2014, 71–81 (2014)MATH
9.
Holland, J.H.: Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor (1975)
10.
Hutter, F., Tompkins, D.A.D., Hoos, H.H.: Scaling and probabilistic smoothing: efficient dynamic local search for SAT. In: Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 233–248. Springer, Heidelberg (2002). doi:10.​1007/​3-540-46135-3_​16 CrossRef
11.
Karim, M.R.: A new approach to constraint weight learning for variable ordering in CSPs. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2014), Beijing, China, pp. 2716–2723 (2014)
12.
Lee, H.-J., Cha, S.-J., Yu, Y.-H., Jo, G.-S.: Large neighborhood search using constraint satisfaction techniques in vehicle routing problem. In: Gao, Y., Japkowicz, N. (eds.) AI 2009. LNCS (LNAI), vol. 5549, pp. 229–232. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-01818-3_​30 CrossRef
13.
Morris, P.: The breakout method for escaping from local minima. In: Proceeding AAAI 1993 Proceedings of the Eleventh National Conference on Artificial Intelligence, pp. 40–45 (1993)
14.
Minton, S., Johnson, M., Philips, A., Laird, P.: Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling scheduling problems. Artif. Intell. 58, 161–205 (1992)MathSciNetCrossRefMATH
15.
Pullan, W., Mascia, F., Brunato, M.: Cooperating local search for the maximum clique problems. J. Heuristics 17, 181–199 (2011)CrossRef
16.
Schuurmans, D., Southey, F., Holte, R.: The exponentiated subgradient algorithm for heuristic Boolean programming. In: 17th International Joint Conference on Artificial Intelligence, pp. 334–341. Morgan Kaufmann Publishers, San Francisco (2001)
17.
Stützle., T.: Local search algorithms for combinatorial problems - analysis, improvements, and new applications. Ph.D. thesis, TU Darmstadt, FB Informatics, Darmstadt, Germany (1998)
18.
Wallace, R.J., Freuder, E.C.: Heuristic methods for over-constrained constraint satisfaction problems. In: Jampel, M., Freuder, E., Maher, M. (eds.) OCS 1995. LNCS, vol. 1106, pp. 207–216. Springer, Heidelberg (1996). doi:10.​1007/​3-540-61479-6_​23 CrossRef
19.
Xu, W.: Satisfiability transition and experiments on a random constraint satisfaction problem model. Int. J. Hybrid Inf. Technol. 7(2), 191–202 (2014)CrossRef
20.
Zhou, Y., Zhou, G., Zhang, J.: A hybrid glowworm swarm optimization algorithm for constrained engineering design problems. Appl. Math. Inf. Sci. 7(1), 379–388 (2013)CrossRef
Metadaten
Titel
A Multilevel Genetic Algorithm for the Maximum Constraint Satisfaction Problem
verfasst von
Noureddine Bouhmala
Halvard Sanness Helgen
Knut Morten Mathisen
Copyright-Jahr
2017
Buch
Recent Advances in Soft Computing

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

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

Copyright-Jahr: 2017

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