nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Enhanced Metaheuristics with the Multilevel Paradigm for MAX-CSPs

verfasst von : Noureddine Bouhmala, Mikkel Syse Groesland, Vetle Volden-Freberg

Erschienen in: Computational Science and Its Applications -- ICCSA 2016

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

As many real-world optimization problems become increasingly complex and hard to solve, better optimization algorithms are always needed. Nature inspired algorithms such as genetic algorithms and simulated annealing which belongs to the class of evolutionary algorithms are regarded as highly successful algorithms when applied to a broad range of discrete as well continuous optimization problems. This paper introduces the multilevel paradigm combined with genetic algorithm and simulated annealing 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

Vorheriges Kapitel Trusted Social Node: Evaluating the Effect of Trust and Trust Variance to Maximize Social Influence in a Multilevel Social Node Influential Diffusion Model

Nächstes Kapitel Processing of a New Task in Conditions of the Agile Management with Using of Programmable Queues

Bacanin, N., Tuba, M.: Artificial Bee Colony (ABC) algorithm for constrained optimization improved with genetic operators. Stud. Inf. Control 21(2), 137–146 (2012)

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

Bouhmala, N.: A variable depth search algorithm for binary constraint satisfaction problems. Math. Probl. Eng. 2015 (2015). doi:10.1155/2015/637809, Article ID 637809

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)

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)

Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artif. Intell. 38, 353–366 (1989)MathSciNetCrossRefMATH

Gent, I.P., MacIntyre, E., Prosser, P., Walsh, T.: The constrainedness of search. In: Proceedings of the AAAI-96, pp. 246–252 (1996)

Fang, Z., Chu, Y., Qiao, K., Feng, X., Xu, K.: Combining edge weight and vertex weight for minimum vertex cover problem. In: Chen, J., Hopcroft, J.E., Wang, J. (eds.) FAW 2014. LNCS, vol. 8497, pp. 71–81. Springer, Heidelberg (2014)CrossRef

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: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 233–248. Springer, Heidelberg (2002)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.

Kirkpatrick, S., Gelatt, C., Vecci, M.: Optimization by simulated annealing. Science 220(4589), 671–680 (1983)MathSciNetCrossRefMATH

13.

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, vol. 5549, pp. 229–232. Springer, Heidelberg (2009)CrossRef

14.

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)

15.

Minton, S., Johnson, M., Philips, A., Laird, P.: Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artif. Intell. 58, 161–205 (1992)MathSciNetCrossRefMATH

16.

Pullan, W., Mascia, F., Brunato, M.: Cooperating local search for the maximum clique problems. J. Heuristics 17, 181–199 (2011)CrossRef

17.

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)

18.

Stützle, T.: Local Search Algorithms for Combinatorial Problems Analysis, Improvements, and New Applications. Ph.D. thesis, TU Darmstadt, FB Informatics, Darmstadt, Germany (1998)

19.

Wallace, R.J., Freuder, E.C.: Heuristic methods for over-constrained constraint satisfaction problems. In: Jampel, M., Maher, M.J., Freuder, E.C. (eds.) CP-WS 1995. LNCS, vol. 1106, pp. 207–216. Springer, Heidelberg (1996)CrossRef

20.

Xu, W.: Satisfiability transition and experiments on a random constraint satisfaction problem model. Int. J. Hybrid Inf. Technol. 7(2), 191–202 (2014)CrossRef

21.

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

Titel: Enhanced Metaheuristics with the Multilevel Paradigm for MAX-CSPs
verfasst von: Noureddine Bouhmala
Mikkel Syse Groesland
Vetle Volden-Freberg
Verlag: Springer International Publishing
Buch: Computational Science and Its Applications -- ICCSA 2016
Print ISBN: 978-3-319-42088-2

Electronic ISBN: 978-3-319-42089-9

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-42089-9_38

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner