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:
Genetic Algorithm Optimization for Type-2 Non-singleton Fuzzy Logic Controllers Read chapter Read first chapter

2014 | OriginalPaper | Chapter

Characterization of the Optimization Process

Authors : Marcela Quiroz, Laura Cruz-Reyes, Jose Torres-Jimenez, Claudia Gómez Santillán, Héctor J. Fraire Huacuja, Patricia Melin

Published in: Recent Advances on Hybrid Approaches for Designing Intelligent Systems

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Recent works in experimental analysis of algorithms have identified the need to explain the observed performance. To understand the behavior of an algorithm it is necessary to characterize and study the factors that affect it. This work provides a summary of the main works related to the characterization of heuristic algorithms, by comparing the works done in understanding how and why algorithms follow certain behavior. The main objective of this research is to promote the improvement of the existing characterization methods and contribute to the development of methodologies for robust analysis of heuristic algorithms performance. In particular, this work studies the characterization of the optimization process of the Bin Packing Problem, exploring existing results from the literature, showing the need for further performance analysis.

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 Generic Memetic Algorithm for Course Timetabling ITC2007
next chapter A New Integer Linear Programming Model for the Cutwidth Minimization Problem of a Connected Undirected Graph
Literature
1.
Wolpert, D., Macready, W.: No free lunch theorems for optimizations. IEEE Trans. Evol. Comput. 1, 67–82 (1997)CrossRef
2.
Smith-Miles, K., Lopes, L.: Measuring instance difficulty for combinatorial optimization problems. Comput. Oper. Res. 39(5), 875–889 (2012)CrossRefMATHMathSciNet
3.
Smyth, K.: Understanding stochastic local search algorithms: an empirical analysis of the relationship between search space structure and algorithm behaviour. The University of British Columbia, Ms. thesis (2004)
4.
Garey, M., Jonson, D.: Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman and Company, a classic introduction to the field (1979)
5.
Smith-Miles, K., James, R., Giffin, J., Tu, Y.: Understanding the relationship between scheduling problem structure and heuristic performance using knowledge discovery. In: Learning and Intelligent Optimization, LION 3 (2009)
6.
Leyton-Brown, K., Nudelman, E., Shoham, Y.: Learning the empirical hardness of optimization problems: The case of combinatorial auctions. Principles Pract. Constraint Program. 2470, 556–572 (2002)
7.
Nudelman, E., Devkar, A., Shoham, Y., Leyton-Brown, K.: Understanding random SAT: Beyond the clauses-to-variables ratio. Principles Pract. Constraint Program. 3258, 438–452 (2004)
8.
Gagliolo, M., Schmidhuber, J.: Learning dynamic algorithm portfolios. Spec. Issue Ann. Math. Artif. Intell. 47(3–4), 295–328 (2007)CrossRefMathSciNet
9.
Madani, O., Raghavan, H., Jones, R.: On the empirical complexity of text classification problems. SRI AI Center Technical Report (2009)
10.
Messelis, T., Haspeslagh, S., Bilgin, B., De Causmaecker, P., Vanden, G.: Towards prediction of algorithm performance in real world optimization problems. In: Proceedings of the 21st Benelux Conference on Artificial Intelligence, pp. 177–183. BNAIC, Eindhoven (2009)
11.
Hutter, F., Xu, L., Hoos, H.H., Leyton-Brown, K.: Algorithm runtime prediction: Methods and evaluation. Artif. Intell. 206, 79–111 (2014)CrossRefMathSciNet
12.
McKay, R., Abbass, H.: Anti-correlation measures in genetic programming. In: Proceedings of the Australasia-Japan Workshop on Intelligent and Evolutionary Systems, pp. 45–51 (2001)
13.
Burke, R., Gustafson, S., Kendall, G.: A survey and analysis of diversity measures in genetic programming. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 716–723 (2002)
14.
Thierens, D.: Predictive measures for problem representation and genetic operator design. Technical Report UU-CS-2002-055, Utrecht University: Information and Computing Sciences (2002)
15.
Hutter, F., Hamadi, Y., Hoos, H.H., Leyton-Brown, K.: Performance prediction and automated tuning of randomized and parametric algorithms. In: Principles and Practice of Constraint Programming-CP, pp. 213–228 (2006)
16.
Halim, S., Yap, R., Lau, H.: An integrated white + black box approach for designing and tuning stochastic local search. In: Principles and Practice of Constraint Programming–CP, pp. 332–347 (2007)
17.
Birattari, M.: Tuning Metaheuristics: A machine learning perspective. SCI 197. Springer, Berlin (2009)
18.
Akbaripour, H., Masehian, E.: Efficient and robust parameter tuning for heuristic algorithms. Int. J. Ind. Eng. 24(2), 143–150 (2013)
19.
Wright, S.: The roles of mutation, inbreeding, crossbreeding and selection in evolution. In: Proceedings of the Sixth International Genetics, vol. 1, pp. 356–366 (1932)
20.
Jones, T.: Evolutionary algorithms, fitness landscapes and search. Ph.D. thesis, The University of New Mexico (1995)
21.
Corne, D., Oates, M., Kell, D.: Landscape state machines: tools for evolutionary algorithm performance analyses and landscape/algorithm mapping. In: Applications of Evolutionary Computing, pp. 187–198 (2003)
22.
Mitchell, B., Mancoridis, S.: Modeling the search landscape of metaheuristic software clustering algorithms. Lecture notes in computer science. In: Proceedings of the 2003 International Conference on Genetic and Evolutionary Computation, vol. 2, pp. 2499–2510 (2003)
23.
Merz, P.: Advanced fitness landscape analysis and the performance of memetic algorithms. Evol. Comput. Spec. Issue Magn. Algorithms 12(3), 303–325 (2004)MathSciNet
24.
Ochoa, G., Qu, R., Burke, E.: Analyzing the landscape of a graph based hyper-heuristic for timetabling problems. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, pp. 341–348 (2009)
25.
Czogalla, J., Fink, A.: Fitness landscape analysis for the resource constrained project scheduling problem. In: Lecture Notes in Computer Science, Learning and Intelligent Optimization, vol. 5851, pp. 104–118 (2009)
26.
Verel, S., Liefooghe, A., Jourdan, L., Dhaenens, C.: On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives. Eur. J. Oper. Res. (2012)
27.
Merz, P., Freisleben, B.: Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning. Evol. Comput. 8(1), 61–91 (2000)CrossRef
28.
Merz, P., Freisleben, B.: Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans. Evol. Comput. 4(4), 337–352 (2000)CrossRef
29.
Borenstein, Y.: Information landscapes. In: Genetic and Evolutionary Computation Conference, pp. 1515–1522 (2005)
30.
Borgs, C., Chayes, J., Pittel, B.: Phase transition and finite-size scaling for the integer partitioning problem. Random Struct. Algorithms 19, 247–288 (2001)CrossRefMATHMathSciNet
31.
Béjar, R., Vetsikas, I., Gomes, C., Kautz, H., Selman, B.: Structure and phase transition phenomena in the VTC problem. In TASK PI Meeting Workshop (2001)
32.
Caramanis, C.: Survey propagation iterative solutions to constraint satisfaction problems. In: Expository Writing (2003)
33.
Achlioptas, D., Naor, A., Peres, Y.: Rigorous location of phase transitions in hard optimization problems. Nature 435(7043), 759–764 (2005)CrossRef
34.
Mertens, S.: The easiest hard problem: Number partitioning. Comput. Complex. Stat. Phys. 125(2), 125–140 (2006)MathSciNet
35.
Piñol, C.: CSP Problems as algorithmic benchmarks: Measures, methods and models. In: Universitat de Lleida, Departament d’Informàtica i Enginyeria Industrial (2008)
36.
Rangel-Valdez, N., Torres-Jimenez, J.: Phase transition in the bandwidth minimization problem. In: Lecture Notes in Computer Science 5845, MICAI 2009: Advances in Artificial Intelligence, pp. 372–383 (2009)
37.
Dewenter, T., Hartmann, A.: Phase transition for cutting-plane approach to vertex-cover problem. Phys. Rev. E 86(4), 041128 (2012)CrossRef
38.
Slaney, J., Walsh, T.: Backbones in optimization and approximation. In: Proceedings the 17th International Joint Conference on Artificial Intelligence (IJCAI-01), pp. 254–259 (2001)
39.
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic ‘phase transitions’. Nature 400(6740), 133–137 (1999)CrossRefMathSciNet
40.
Zeng, G., Lu, Y.: Survey on computational complexity with phase transitions and extremal optimization. In: Proceedings of 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference Shanghai, People’s Republic of China, 16–18 Dec 2009
41.
Singer, J., Gent, I.P., Smaill, A.: Backbone fragility and the local search cost peak. J. Artif. Intell. Res. (JAIR) 12, 235–270 (2000)MATHMathSciNet
42.
Watson, J., Beck, J., Howe, A., Whitley, L.: Problem difficulty for tabu search in job-shop scheduling. Artif. Intell. 143, 189–217 (2003)CrossRefMATHMathSciNet
43.
Schneider, J.: Searching for backbones—a high-performance parallel algorithm for solving combinatorial optimization problems. Future Gener. Comput. Syst. 19(1), 121–131 (2003)CrossRefMATH
44.
Zhang, W.: Configuration landscape analysis and backbone guided local search: Part I: Satisfiability and maximum satisfiability. Artif. Intell. 158(1), 1–26 (2004)CrossRefMATH
45.
Zhang, W., Looks, M.: A novel local search algorithm for the travelling salesman problem that exploits backbones. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence, pp. 343–350 (2005)
46.
Zeng, G., Lu, Y., Dai, Y., Wu, Z., Mao, W., Zhang, Z., Zheng, C.: Backbone guided extremal optimization for the hard maximum satisfiability problem. Int. J. Innovative Comput. Inf. Control 8(12), 8355–8366 (2012)
47.
Quiroz, M., Cruz-Reyes, L., Torres-Jiménez, J., Melin, P.: Improving the performance of heuristic algorithms based on exploratory data analysis. In: Recent Advances on Hybrid Intelligent Systems, pp. 361–375 (2013)
48.
Falkenauer, E.: A hybrid grouping genetic algorithm for bin packing. J. Heuristics 2, 5–30 (1996)CrossRef
49.
Alvim, A., Glover, F., Ribeiro, C., Aloise, D.: A hybrid improvement heuristic for the one-dimensional bin packing problem. J. Heuristics 10, 205–229 (2004)CrossRef
50.
Fleszar, K., Charalambous, C.: Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem. Eur. J. Oper. Res. 210(2), 176–184 (2011)CrossRefMATHMathSciNet
51.
Cruz-Reyes, L., Quiroz, M., Alvim, A., Fraire H., Gómez, C., Torres-Jiménez, J.: Heurísticas de agrupación híbridas eficientes para el problema. Computación y Sistemas 16(3) (2012)
52.
53.
54.
55.
56.
Scholl, A., Klein, R., Jürgens, C.: Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Comput. Oper. Res. 24(7), 627–645 (1997)CrossRefMATH
57.
Wäscher, G., Gau, T.: Heuristics for the one-dimensional cutting stock problem: A computational study. OR Spektrum 18(3), 131–144 (1996)CrossRefMATH
58.
Schwerin, P., Wäscher, G.: The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP. Int. Trans. Oper. Res. 4(5–6), 337–389 (1997)
59.
Schoenfield, J.E.: Fast exact solution of open bin packing problems without linear programming. In: Draft, US Army Space and Missile Defense Command, Huntsville, Alabama, USA (2002)
60.
Pérez, J., Pazos, R.A., Frausto, J., Rodríguez, G., Romero, D., Cruz, L.: A statistical approach for algorithm selection. In: Ribeiro C.C., Matins, S.L. (eds.) WEA 2004. LNCS, vol. 3059, pp. 417–431 (2004)
61.
Cruz-Reyes, L., Gómez-Santillán, C., Schaeffer, S.E., Quiroz-Castellanos, M., Alvarez-Hernández, V.M., Pérez-Rosas, V.: Enhancing accuracy of hybrid packing systems through general-purpose characterization. In: Hybrid Artificial Intelligent Systems, pp. 26–33 (2011)
62.
Loh, K., Golden, B., Wasil, E.: Solving the one-dimensional bin packing problem with a weight annealing heuristic. Comput. Oper. Res. 35(7), 2283–2291 (2008)CrossRefMATHMathSciNet
63.
Martello, S., Toth, P.: Knapsack problems: Algorithms and computer implementations. Wiley, New York (1990)MATH
64.
Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8(3), 272–314 (1974)CrossRefMATH
65.
Chiarandini, M., Paquete, L., Preuss, M., Ridge, E.: Experiments on metaheuristics: Methodological overview and open issues. In: Technical Report DMF-2007-03-003, The Danish Mathematical Society (2007)
Metadata
Title
Characterization of the Optimization Process
Authors
Marcela Quiroz
Laura Cruz-Reyes
Jose Torres-Jimenez
Claudia Gómez Santillán
Héctor J. Fraire Huacuja
Patricia Melin
Copyright Year
2014
Book
Recent Advances on Hybrid Approaches for Designing Intelligent Systems

Print ISBN: 978-3-319-05169-7

Electronic ISBN: 978-3-319-05170-3

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-05170-3_34

Premium Partner

    Image Credits