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:
General Type-2 Fuzzy Edge Detection in the Preprocessing of a Face Recognition System Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Solving the Cut Width Optimization Problem with a Genetic Algorithm Approach

Authors : Hector Joaquín Fraire-Huacuja, Mario César López-Locés, Norberto Castillo García, Johnatan E. Pecero, Rodolfo Pazos Rangel

Published in: Nature-Inspired Design of Hybrid Intelligent Systems

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

The Cut width Minimization Problem is a NP-Hard problem that is found in the VLSI design, graph drawing, design of compilers and linguistics. Developing solutions that could solve it efficiently is important due to its impact in areas that are critical for society. It consists in finding the linear array of an undirected graph that minimizes the maximum number of edges that are cut. In this paper we propose a genetic algorithm applied to the Cut width Minimization Problem. As the configuration of a metaheuristic has a great impact on the performance, we also propose a Fuzzy Logic controller that is used to adjust the parameters of the GA during execution time to guide it during the exploration process.

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 Increase Methodology of Design of Course Timetabling Problem for Students, Classrooms, and Teachers
next chapter A Dialogue Interaction Module for a Decision Support System Based on Argumentation Schemes to Public Project Portfolio
Literature
1.
M. R. Garey, D. S. Johnson, and others, Computers and Intractability: A Guide to the Theory of NP-completeness. WH freeman San Francisco, 1979.
2.
E. Korach and N. Solel, “Tree-width, path-width, and cutwidth,” Discret. Appl. Math., vol. 43, no. 1, pp. 97–101, 1993.
3.
T. Ohtsuki, H. Mori, E. Kuh, T. Kashiwabara, and T. Fujisawa, “One-dimensional logic gate assignment and interval graphs,” Circuits Syst. IEEE Trans., vol. 26, no. 9, pp. 675–684, 1979.
4.
M. Suderman, “Pathwidth and layered drawings of trees,” Int. J. Comput. Geom. Appl., vol. 14, no. 03, pp. 203–225, 2004.
5.
H. Bodlaender, J. Gustedt, and J. A. Telle, “Linear-time register allocation for a fixed number of registers,” in Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, 1998, pp. 574–583.
6.
Z. Tuza, “Narrowness, Path-width, and their Application in Natural Language Processing.”
7.
E. Pardo, N. Mladenović, J. Pantrigo, and A. Duarte, “Variable formulation search for the cutwidth minimization problem,” Appl. Soft Comput., vol. 13, pp. 2242–2252, 2013.
8.
D. Andrade and M. Resende, “GRASP with path-relinking for network migration scheduling,” … Int. Netw. …, pp. 1–7, 2007.
9.
D. Andrade and M. Resende, “GRASP with evolutionary path-relinking,” Proc. Seventh Metaheuristics …, pp. 6–9, 2007.
10.
J. J. Pantrigo, R. Martí, A. Duarte, and E. G. Pardo, “Scatter search for the cutwidth minimization problem,” Ann. Oper. Res., vol. 199, no. 1, pp. 285–304, 2012.
11.
V. Campos, E. Piñana, and R. Martí, “Adaptive memory programming for matrix bandwidth minimization,” Ann. Oper. Res., pp. 1–17, 2006.
12.
J. H. Holland, Adaptation in Natural and Artificial Systems, vol. Ann Arbor. 1975.
13.
L. A. Zadeh, “Fuzzy sets,” Inf. Control, vol. 8, no. 3, pp. 338–353, Jun. 1965.
14.
A. Michael and H. Takagi, “Dynamic control of genetic algorithms using fuzzy logic techniques,” in Proceedings of the Fifth International Conference on Genetic Algorithms, 1993, pp. 76–83.
15.
F. Valdez, P. Melin, and O. Castillo, “Fuzzy control of parameters to dynamically adapt the {PSO} and {GA} Algorithms,” in {FUZZ-IEEE} 2010, {IEEE} International Conference on Fuzzy Systems, Barcelona, Spain, 18-23 July, 2010, Proceedings, 2010, pp. 1–8.
16.
F. Valdez and P. Melin, “A New Evolutionary Method with Particle Swarm Optimization and Genetic Algorithms Using Fuzzy Systems to Dynamically Parameter Adaptation,” in Soft Computing for Recognition Based on Biometrics, 2010, pp. 225–243.
17.
R. Martí, J. Pantrigo, A. Duarte, and E. Pardo, “Branch and bound for the cutwidth minimization problem,” Comput. Oper. …, vol. 40, pp. 137–149, 2013.
18.
L. Rutkowski, Flexible neuro-fuzzy systems: structures, learning and performance evaluation, vol. 771. Springer Science & Business Media, 2006.
19.
D. A. Martí R. Pantrigo J.J. and P. E.G., “Optsicom Project.” 2010.
Metadata
Title
Solving the Cut Width Optimization Problem with a Genetic Algorithm Approach
Authors
Hector Joaquín Fraire-Huacuja
Mario César López-Locés
Norberto Castillo García
Johnatan E. Pecero
Rodolfo Pazos Rangel
Copyright Year
2017
Book
Nature-Inspired Design of Hybrid Intelligent Systems

Print ISBN: 978-3-319-47053-5

Electronic ISBN: 978-3-319-47054-2

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-47054-2_48

Premium Partner

    Image Credits