nach oben

Neural Computing and Applications

Erschienen in:

01.11.2010 | AIS

A graph-based immune-inspired constraint satisfaction search

verfasst von: María-Cristina Riff, Marcos Zúñiga, Elizabeth Montero

Erschienen in: Neural Computing and Applications | Ausgabe 8/2010

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We propose an artificial immune algorithm to solve constraint satisfaction problems (CSPs). Recently, bio-inspired algorithms have been proposed to solve CSPs. They have shown to be efficient in solving hard problem instances. Given that recent publications indicate that immune-inspired algorithms offer advantages to solve complex problems, our main goal is to propose an efficient immune algorithm which can solve CSPs. We have calibrated our algorithm using relevance estimation and value calibration (REVAC), which is a new technique recently introduced to find the parameter values for evolutionary algorithms. The tests were carried out using randomly generated binary constraint satisfaction problems and instances of the three-colouring problem with different constraint networks. The results suggest that the technique may be successfully applied to solve CSPs.

Vorheriger Artikel An immune-inspired multi-objective approach to the reconstruction of phylogenetic trees

Nächster Artikel Immunocomputing for intelligent signal processing

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

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

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+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

http://www.web.cs.ualberta.ca/joe/.

http://www.sop.inria.fr/orion/personnel/Marcos.Zuniga/CSPsolver.zip.

Cheeseman P, Kanefsky B, Taylor W (1991) Where the really hard problems are. In: proceedings of the international joint conferences on artificial intelligence (IJCAI91), pp 163–169

Craenen BGW, Eiben AE, van Hemert JI (2003) Comparing evolutionary algorithms on binary constraint satisfaction problems. IEEE Trans Evol Comput 7(5):424–444CrossRef

de Castro LN, Timmis J (eds) (2002) Artificial immune systems: a new computational intelligence approach. Springer, London, UKMATH

Brelaz D (1979) New methods to color the vertices of a graph. Commun ACM 22:251–256

Dasgupta D. (eds) (2000) Artificial immune systems and their applications. Springer, Berlin

Dozier G, Bowen J, Homaifar A (1998) Solving constraint satisfaction problems using hybrid evolutionary search. IEEE Trans Evol Comput 2(1):23–33CrossRef

Eiben AE, van Hemert JI, Marchiori E, Steenbeek AG (1998) Solving binary constraint satisfaction problems using evolutionary algorithms with an adaptive fitness function. In: Proceedings of the 5th international conference on parallel problem solving from nature (PPSN-V), LNCS 1498, pp 196–205

Garrett SM (2004) Parameter-free, adaptive clonal selection. In: Proceedings of the IEEE congress on evolutionary computation (CEC04), vol 1, pp 1052–1058

Mackworth AK (1977) Consistency in network of relations. Artificial Intelligence 8:99–118MATHCrossRef

10.

Marchiori E (1977) Combining constraint processing and genetic algorithms for constraint satisfaction problems. In: Proceedings of the 7th international conference on genetic algorithms (ICGA97), pp 330–337

11.

Nannen V, Eiben A (2007) Relevance estimation and value calibration of evolutionary algorithm parameters. Proceedings of the joint international conference for artificial intelligence (IJCAI), pp 975–980 (2007)

12.

Riff MC (1998) A network-based adaptive evolutionary algorithm for csp. In: metaheuristics: advances and trends in local search paradigms for optimisation, chap 22. Kluwer Academic Publisher, Dordecht, pp 325–339

13.

Riff MC, Zuniga M (2007) Towards an immune system to solve csp. Proceedings of the IEEE congress on evolutionary computation Singapur(In Press.)

14.

Smith BM, Dyer ME (1996) Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence 81(1–2):155–181CrossRefMathSciNet

15.

Solnon C (2002) Ants can solve constraint satisfaction problems. IEEE Trans Evol Comput 6(4):347–357CrossRef

16.

Tsang EPK, Wang CJ, Davenport A, Voudouris C, Lau TL (1999) A family of stochastic methods for constraint satisfaction and optimization. In: Proceedings of the 1st international conference on the practical application of constraint technologies and logic programming (PACLP), London, pp 359–383

Titel: A graph-based immune-inspired constraint satisfaction search
verfasst von: María-Cristina Riff
Marcos Zúñiga
Elizabeth Montero
Publikationsdatum: 01.11.2010
Verlag: Springer-Verlag
Erschienen in: Neural Computing and Applications / Ausgabe 8/2010
Print ISSN: 0941-0643
Elektronische ISSN: 1433-3058
DOI: https://doi.org/10.1007/s00521-010-0390-8

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"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 8/2010

A comparative survey of artificial intelligence applications in finance: artificial neural networks, expert system and hybrid intelligent systems

Pose invariant face recognition based on hybrid-global linear regression

Self-tuning output recurrent cerebellar model articulation controller for a wheeled inverted pendulum control

Genetic algorithm–based training for semi-supervised SVM

The effect of mid-term estimation on back propagation for time series prediction

Analysis of international debt problem using artificial neural networks and statistical methods

Premium Partner