nach oben

Erschienen in:

2011 | OriginalPaper | Buchkapitel

What Is Autonomous Search?

verfasst von : Youssef Hamadi, Eric Monfroy, Frédéric Saubion

Erschienen in: Hybrid Optimization

Verlag: Springer New York

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Autonomous search is a particular case of adaptive systems that improve their solving performance by modifying and adjusting themselves to the problem at hand, either by self-adaptation or by supervised adaptation. We propose a general definition and a taxonomy of search processes with respect to their computation characteristics. For this purpose, we decompose solvers into components and their configurations. Some computation rules between computation stages are used to formalize the solver modifications and adaptations. Using these rules, we then sketch out and classify some well known solvers and try to answer the question: “What is Autonomous Search?”

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 Learning in Search

Nächstes Kapitel Software Tools Supporting Integration

Remark here that an optimal strategy would state the unsatisfiability of the problem from the analysis of the second subproblem.

Applegate D, Bixby R, Chvatal V, Cook W (2007) The traveling salesman problem: a computational study (Princeton Series in Applied Mathematics). Princeton University Press, Princeton

Aarts E, Lenstra JK (eds) (2003) Local search in combinatorial optimization. Princeton University Press, PrincetonMATH

Apt K (2003) Principles of constraint programming. Cambridge University Press, CambridgeMATH

Battiti R, Brunato M (eds) (2008) Learning and intelligent optimization second international conference, LION 2007 II, selected papers. Lecture Notes in Computer Science, vol 5313. Springer, Berlin

Battiti R, Brunato M (2009) Handbook of Metaheuristics, 2nd edn. chapter Reactive search optimization: learning while optimizing. Springer (in press)

Battiti R, Brunato M, Mascia F (2007) Reactive search and intelligent optimization. Technical report, Dipartimento di Informatica e Telecomunicazioni, Univerita di Tranto, ItalyMATH

Battiti R, Brunato M, Mascia F (2008) Reactive search and intelligent optimization. Operations research/computer science interfaces, vol 45. Springer, HeidelbergMATH

Bader-El-Den M, Poli R (2008) Generating sat local-search heuristics using a gp hyper-heuristic framework, artificial evolution. In: 8th International conference, Evolution Artificielle, EA 2007. Revised selected papers. Lecture notes in computer science, vol 4926. Springer, Berlin, pp 37–49

Benhamou F, Granvilliers L (2006) Continuous and interval constraints. In: Rossi F, van Beek P, Walsh T (eds) Handbook of constraint programming, chapter 16. Elsevier, AmsterdamMATH

10.

Burke EK, Kendall G, Newall J, Hart E, Ross P, Schulenburg S (2003) Handbook of meta-heuristics, chapter Hyper-heuristics: an emerging direction in modern search technology. Kluwer, Dordrecht, pp 457–474MATH

11.

Burke EK, Hyde M, Kendall G, Ochoa G, Ozcan E, Qu R (2009) A survey of hyper-heuristics. Technical Report No. NOTTCS-TR-SUB-0906241418-2747, School of Computer Science and Information Technology, University of Nottingham, Computer Science

12.

Burke EK, Hyde M, Kendall G, Ochoa G, Ozcan E, Woodward J (2010) Handbook of meta-heuristics, chapter A classification of hyper-heuristics approaches (in press).

13.

Boussemart F, Hemery F, Lecoutre C, Sais L (2004) Boosting systematic search by weighting constraints. In: López de Mántaras R, Saitta L (eds) Proceedings of the 16th European conference on artificial intelligence, ECAI’2004. IOS Press, Amsterdam, pp 146–150

14.

Biere A, Heule M, van Maaren H, Walsh T (eds) (2009) Handbook of satisfiability. Frontiers in artificial intelligence and applications, vol 185. IOS Press, Amsterdam

15.

Bordeaux L, Hamadi Y, Zhang L (2006) Propositional satisfiability and constraint programming: a comparative survey. ACM Comput Surv 9(2):135–196

16.

Boyan J, Moore A, Kaelbling P (2000) Learning evaluation functions to improve optimization by local search. J Mach Learn Res 1:1–2000

17.

Birattari M, Stützle T, Paquete L, Varrentrapp K (2002) A racing algorithm for configuring metaheuristics. In: GECCO ’02: Proceedings of the genetic and evolutionary computation conference. Morgan Kaufmann, San Francisco, CA, pp 11–18

18.

Battiti R, Tecchiolli G (1994) The reactive tabu search. INFORMS J Comput 6(2):126–140MATH

19.

Crispim J, Brandão J (2001) Reactive tabu search and variable neighbourhood descent applied to the vehicle routing problem with backhauls. In: Proceedings of the 4th metaheuristics international conference, Porto, MIC 2001, pp 631–636

20.

Crowston W, Glover F, Thompson G, Trawick J (1963) Probabilistic and parametric learning combinations of local job shop scheduling rules. Technical report, ONR Research Memorandum No. 117, GSIA, Carnegie-Mellon University, Pittsburg, PA, USA

21.

Cowling P, Kendall G, Soubeiga E (2002) Hyperheuristics: a tool for rapid prototyping in scheduling and optimisation. In: Applications of evolutionary computing, EvoWorkshops 2002: EvoCOP, EvoIASP, EvoSTIM/EvoPLAN. Lecture notes in computer science, vol 2279. Springer, London, pp 1–10MATH

22.

Cahon S, Melab N, Talbi E, Schoenauer M (2003) Paradiseo-based design of parallel and distributed evolutionary algorithms. In: Artificial evolution, 6th international conference, evolution artificielle, EA 2003. Lecture notes in computer science, vol 2936. Springer, Berlin, pp 216–228

23.

Cowling P, Soubeiga E (2000) Neighborhood structures for personnel scheduling: a summit meeting scheduling problem (abstract). In: Burke EK, Erben W (eds) Proceedings of the 3rd international conference on the practice and theory of automated timetabling, Constance, Germany

24.

De Jong K (2006) Evolutionary computation: a unified approach. The MIT Press, Cambridge, MAMATH

25.

De Jong K (2007) Parameter setting in EAs: a 30 year perspective. In: Lobo F, Lima C, Michalewicz Z (eds) Parameter setting in evolutionary algorithms. Studies in computational intelligence, vol 54. Springer, Berlin, pp 1–18

26.

Dechter R (2003) Constraint processing. Morgan Kaufmann, San Francisco, CAMATH

27.

Epstein S, Freuder E, Wallace R, Morozov A, Samuels B (2002) The adaptive constraint engine. In: Principles and practice of constraint programming – CP 2002, 8th international conference. Lecture notes in computer science, vol 2470. Springer, London, pp 525–542

28.

Epstein S, Freuder E, Wallace R (2005) Learning to support constraint programmers. Comput Intell 21(4):336–371MathSciNet

29.

Eiben AE, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evol Comput 3(2):124–141

30.

Eén N, Mishchenko A, Sörensson N (2007) Applying logic synthesis for speeding up sat. In: Theory and applications of satisfiability testing – SAT 2007. Lecture notes in computer science, vol 4501. Springer, Heidelberg, pp 272–286

31.

Eiben AE, Michalewicz Z, Schoenauer M, Smith JE (2007) Parameter control in evolutionary algorithms. In: Lobo F, Lima C, Michalewicz Z (eds) Parameter setting in evolutionary algorithms. Studies in computational intelligence, vol 54. Springer, Berlin, pp 19–46

32.

Eén N, Sörensson N (2003) An extensible sat-solver. In: Theory and applications of satisfiability testing, 6th international conference, SAT 2003. Lecture notes in computer science, vol 2919. Springer, Heidelberg, pp 502–518

33.

Eiben A, Smith JE (2003) Introduction to evolutionary computing. Natural computing series. Springer, HeidelbergMATH

34.

Fruewirth T, Abdennadher S (2003) Essentials of constraint programming. Springer, HeidelbergMATH

35.

Fialho A, Da Costa L, Schoenauer M, Sebag M (2008) Extreme value based adaptive operator selection. In: Rudolph G et al (ed) Parallel problem solving from nature - PPSN X, 10th international conference. Lecture notes in computer science, vol 5199. Springer, Berlin, pp 175–184

36.

Fisher H, Thompson L (1963) Industrial scheduling, chapter Probabilistic learning combinations of local job-shop scheduling rules. Prentice Hall, Englewood Cliffs, NJ

37.

Fukunaga A (2008) Automated discovery of local search heuristics for satisfiability testing. Evol Comput 16(1):31–61

38.

Gebruers C, Guerri A, Hnich B, Milano M (2004) Making choices using structure at the instance level within a case based reasoning framework. In: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, First international conference, CPAIOR. Lecture notes in computer science, vol 3011. Springer, Berlin, pp 380–386

39.

Goualard F, Jermann C (2008) A reinforcement learning approach to interval constraint propagation. Constraints 13(1–2):206–226MathSciNetMATH

40.

Glover F, Kochenberger G (2003) Handbook of metaheuristics (International series in operations research & management science). Springer, Berlin

41.

Glover F, Laguna M (1997) Tabu search. Kluwer Academic, DordrechtMATH

42.

Guerri A, Milano M (2004) Learning techniques for automatic algorithm portfolio selection. In: Proceedings of the 16th European conference on artificial intelligence, ECAI’2004. IOS Press, Amsterdam, pp 475–479

43.

Goldberg D (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Professional, BostonMATH

44.

Gagliolo M, Schmidhuber J (2008) Algorithm selection as a bandit problem with unbounded losses. Technical report, Tech. report IDSIA - 07 - 08

45.

Gomes C, Selman B, Crato N, Kautz H (2000) Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. J Autom Reason 24(1/2):67–100MathSciNetMATH

46.

Hamadi Y (2003) Disolver : a distributed constraint solver. Technical Report MSR-TR-2003-91, Microsoft Research

47.

Hansen N (2008) Adaptative encoding: how to render search coordinate system invariant. In: Parallel problem solving from nature – PPSN X, 10th international conference. Lecture notes in computer science, vol 5199. Springer, Berlin, pp 204–214

48.

Van Hentenryck P (1989) Constraint satisfaction in logic programming. The MIT Press, Cambridge, MA

49.

Hutter F, Hamadi Y (2005) Parameter adjustment based on performance prediction: towards an instance-aware problem solver. Technical Report MSR-TR-2005-125, Microsoft Research, Cambridge, UK

50.

Hutter F, Hamadi Y, Hoos H, Brown KL (2006) Performance prediction and automated tuning of randomized and parametric algorithms. In: 12th International conference on principles and practice of constraint programming (CP’06)MATH

51.

Hutter F, Hoos H, Stützle T (2007) Automatic algorithm configuration based on local search. In: Proceedings of the 22nd conference on artifical intelligence (AAAI ’07), pp 1152–1157

52.

Hamadi Y, Jabbour S, Sais L (2009) Control-based clause sharing in parallel SAT solving. In: IJCAI 2009, Proceedings of the 21st international joint conference on artificial intelligence, pp 499–504

53.

Van Hentenryck P, Michel L (2005) Constraint-based local search. The MIT Press, Cambridge, MA, USAMATH

54.

Hamadi Y, Monfroy E, Saubion F (2008) Special issue on autonomous search. In: Constraint programming letters, vol 4

55.

Hamadi Y, Monfroy E, Saubion F (2008) What is autonomous search? Technical Report MSR-TR-2008-80, Microsoft Research

56.

Holland J (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI

57.

Hoos H (1999) Sat-encodings, search space structure, and local search performance. In: Proceedings of the 16th international joint conference on artificial intelligence, IJCAI 99. Morgan Kaufmann, San Francisco, CA, pp 296–303

58.

Hoos H (2002) An adaptive noise mechanism for walksat. In: AAAI/IAAI, pp 655–660

59.

Hu B, Raidl G (2006) Variable neighborhood descent with self-adaptive neighborhood-ordering. In: Proceedings of the 7th EU meeting on adaptive, self-adaptive and multilevel metaheuristics

60.

Hoos H, Stuetzle T (2004) Stochastic local search: foundations & applications (The Morgan Kaufmann Series in Artificial Intelligence). Morgan Kaufmann, San Francisco, CA

61.

Hutter F (2009) Automating the configuration of algorithms for solving hard computational problems. PhD thesis, Department of Computer Science, University of British Columbia

62.

Ingber L (1989) Very fast simulated re-annealing. Math Comput Model 12(8):967–973MathSciNetMATH

63.

Janikow C, Michalewicz Z (1991) An experimental comparison of binary and floating point representations in genetic algorithms. In: 4th International conference on genetic algorithms, pp 3136

64.

Kjellstrm G (1991) On the efficiency of gaussian adaptation. J Optim Theory Appl 71(3)

65.

Koza J (1992) Genetic programming: on the programming of computers by means of natural selection. The MIT Press, Cambridge, MAMATH

66.

Kazarlis S, Petridis V (1998) Varying fitness functions in genetic algorithms: studying the rate of increase of the dynamic penalty terms. In: Parallel problem solving from nature – PPSN V, 5th international conference. Lecture notes in computer science, vol 1498, pp 211–220

67.

Kramer O (2008) Self-adaptive heuristics for evolutionary computation. Springer, BerlinMATH

68.

Lobo F, Lima C, Michalewicz Z (eds) (2007) Parameter setting in evolutionary algorithms. In: Studies in computational intelligence, vol 54. Springer, Berlin

69.

Monette J-N, Deville Y, Van Hentenryck P (2009) Operations research and cyber-infrastructure, chapter Aeon: synthesizing scheduling algorithms from high-level models. Springer, New York, pp 43–59

70.

Maturana J, Fialho A, Saubion F, Schoenauer M, Sebag M (2010) Compass and dynamic multi-armed bandits for adaptive operator selection. In: Proceedings of IEEE Congress on evolutionary computation CEC (in press)

71.

Mladenovic N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11):1097–1100MathSciNetMATH

72.

Michalewicz Z (1992) Genetic algorithms + data structures = evolution program. Artificial intelligence. Springer, BerlinMATH

73.

Maturana J, Lardeux F, Saubion F (2009) Autonomous operator management for evolutionnary algorithms. Under revision

74.

Morris P (1993) The breakout method for escaping from local minima. In: Proceedings of the 11th national conference on artificial intelligence (AAAI93). AAAI Press, Menlo Park, CA, pp 40–45

75.

Marriott K, Stuckey P (1998) Programming with constraints: an introduction. The MIT Press, Cambridge, MAMATH

76.

Maturana J, Saubion F (2008) A compass to guide genetic algorithms. In: Rudolph G et al (ed) Parallel problem solving from nature – PPSN X, 10th international conference. Lecture notes in computer science, vol 5199. Springer, Berlin, pp 256–265

77.

Mazure B, Sais L, Grégoire E (1997) Tabu search for sat. In: AAAI/IAAI, pp 281–285

78.

Mazure B, Sais L, Grégoire E (1998) Boosting complete techniques thanks to local search methods. Ann Math Artif Intell 22(3-4):319–331MathSciNetMATH

79.

Monfroy E, Saubion F, Lambert T (2004) On hybridization of local search and constraint propagation. In: Logic programming, 20th international conference, ICLP 2004. Lecture notes in computer science, vol 3132. Springer, Berlin, pp 299–313

80.

Nannen V, Eiben AE (2006) A method for parameter calibration and relevance estimation in evolutionary algorithms. In: Genetic and evolutionary computation conference, GECCO 2006, proceedings. ACM, New York, NY, pp 183–190

81.

Nannen V, Eiben AE (2007) Relevance estimation and value calibration of evolutionary algorithm parameters. In: IJCAI 2007, proceedings of the 20th international joint conference on artificial intelligence, pp 975–980

82.

Nannen V, Smit S, Eiben A (2008) Costs and benefits of tuning parameters of evolutionary algorithms. In: Parallel problem solving from nature – PPSN X, 10th international conference. Lecture notes in computer science, vol 5199. Springer, Berlin, pp 528–538

83.

Pullan WJ, Hoos HH (2006) Dynamic local search for the maximum clique problem. J Artif Intell Res (JAIR) 25:159–185MATH

84.

Patterson D, Kautz H (2001) Auto-walksat: a self-tuning implementation of walksat. Electron Notes Discrete Math 9:360–368MATH

85.

Puchinger J, Raidl G (2008) Bringing order into the neighborhoods: relaxation guided variable neighborhood search. J Heuristics 14(5):457–472MATH

86.

Ringwelski G, Hamadi Y (2005) Boosting distributed constraint satisfaction. In: Principles and practice of constraint programming – CP 2005, 11th international conference. Lecture notes in computer science, vol 3709. Springer, Berlin, pp 549–562MATH

87.

Rice J (1975) The algorithm selection problem. Technical Report CSD-TR 152, Computer science department, Purdue University

88.

Smit S, Eiben A (2010) Comparing parameter tuning methods for evolutionary algorithms. In: Proceedings of the 2009 IEEE Congress on evolutionary computation (CEC 2009). IEEE Press, Piscataway, NJ (in press).

89.

Selman B, Kautz H, Cohen B (1994) Noise strategies for improving local search. In: AAAI, pp 337–343

90.

Smith-Miles K (2008) Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput Surv 41(1):1–25

91.

Sywerda G (1989) Uniform crossover in genetic algorithms. In: Proceedings of the third international conference on genetic algorithms. Morgan Kaufmann, San Francisco, CA, pp 2–9

92.

Thierens D (2005) An adaptive pursuit strategy for allocating operator probabilities. In: Beyer H-G (ed) Proc. GECCO’05. ACM, New York, NY, pp 1539–1546

93.

Thierens D (2007) Adaptive strategies for operator allocation. In: Lobo FG, Lima CF, Michalewicz Z (eds) Parameter setting in evolutionary algorithms. Springer, Heidelberg, pp 77–90

94.

Thornton J (2000) Constraint weighting for constraint satisfaction. PhD thesis, School of Computing and Information Technology, Griffith University, Brisbane, Australia

95.

Tsang E (1993) Foundations of constraint satisfaction, 1st edn. Academic, London

96.

Walsh T (2000) SAT v CSP. In: Proceedings of CP 2000. Lecture notes in computer science, vol 1894. Springer, Berlin, pp 441–456

97.

Wong Y-Y, Lee K-H, Leung K-S, Ho C-W (2003) A novel approach in parameter adaptation and diversity maintenance for GAs. Soft Comput 7(8):506–515

98.

Whitacre J, Tuan Pham Q, Sarker R (2006) Credit assignment in adaptive evolutionary algorithms. In: Genetic and evolutionary computation conference, GECCO 2006. ACM, New York, NY, pp 1353–1360

99.

Whitacre J, Pham T, Sarker R (2006) Use of statistical outlier detection method in adaptive evolutionary algorithms. In: Proceedings of the genetic and evolutionary computation conference (GECCO). ACM, New York, NY, pp 1345–1352

100.

Xu L, Hutter F, Hoos HH, Leyton-Brown K (2008) Satzilla: portfolio-based algorithm selection for sat. J Artif Intell Res 32:565–606MATH

101.

Yuan B, Gallagher M (2004) Statistical racing techniques for improved empirical evaluation of evolutionary algorithms. In: Yao X et al (ed) Parallel problem solving from nature – PPSN VIII, 8th international conference. Lecture notes in computer science, vol 3242. Springer, Berlin, pp 172–181

102.

Yu-Hui Yeh F, Gallagher M (2005) An empirical study of hoeffding racing for model selection in k-nearest neighbor classification. In: Gallagher M, Hogan J, Maire F (eds) IDEAL. Lecture notes in computer science, vol 3578. Springer, Berlin, pp 220–227

103.

Yuan B, Gallagher M (2007) Combining meta-eas and racing for difficult EA parameter tuning tasks. In: Lobo F, Lima C, Michalewicz Z (eds) Parameter setting in evolutionary algorithms. Studies in computational intelligence, vol 54. Springer, Berlin, pp 121–142

Titel: What Is Autonomous Search?
verfasst von: Youssef Hamadi
Eric Monfroy
Frédéric Saubion
Verlag: Springer New York
Buch: Hybrid Optimization
Print ISBN: 978-1-4419-1643-3

Electronic ISBN: 978-1-4419-1644-0

Copyright-Jahr: 2011
DOI: https://doi.org/10.1007/978-1-4419-1644-0_11

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