BazEkon - The Main Library of the Cracow University of Economics

BazEkon home page

Main menu

Author
Verdegay Jose Luis, Vergara-Moreno Edmundo
Title
Solving NP-Hard Problems by Using Fuzzy Sets-Based Heuristics
Rozwiązywanie NP-trudnych problemów przy użyciu heurystyk opartych na zbiorach rozmytych
Source
Badania Operacyjne i Decyzje, 2003, nr 4, s. 167-183, bibliogr. 19 poz.
Operations Research and Decisions
Keyword
Zbiory rozmyte, Systemy rozmyte, Programowanie liniowe, Algorytmy, Teoria podejmowania decyzji
Fuzzy sets, Fuzzy systems, Linear programming, Algorithms, Decision making theory
Abstract
Głównym celem artykułu jest zaprezentowanie, jak zbiory i systemy rozmyte mogą być użyte w algorytmach optymalizacyjnych, stosowanych w praktycznych problemach. Rozpatrywane są, oparte na zbiorach rozmytych, heurystyki dla zagadnienia programowania liniowego. Dla zaprezentowania praktycznych realizacji zaproponowanego podejścia przedstawiono metaheurystykę, potwierdzającą efektywność stosowania rozmytych reguł jako kryterium zakończenia obliczeń. Za pomocą metaheurystyki rozwiązano takie zagadnienia, jak problem komiwojażera i zagadnienie plecakowe. Na zakończenie przedstawiono wyniki eksperymentów ukazujących nieprzeciętne możliwości proponowanych algorytmów.

The main aim of this paper is to show how fuzzy sets and systems can be used to produce optimization algorithms able of being applied in a variety of practical situations. Fuzzy sets-based heuristics for Linear Programming problems are considered. To show the practical realisations of the approach proposed a metaheuristic proving the efficiency of using fuzzy rules as termination criteria is shown. Then the Travelling Salesman Problem and the Knapsack Problem are assumed and solved by means of this metaheuristic giving rise in this way to new heuristic algorithms solving these problems. Finally, as an illustration, some practical results showing the outstanding potential of these algorithms are shown.
Accessibility
The Main Library of the Cracow University of Economics
The Library of Warsaw School of Economics
The Library of University of Economics in Katowice
The Main Library of Poznań University of Economics and Business
The Main Library of the Wroclaw University of Economics
Bibliography
Show
  1. CADENAS J.M., PELTA D.A., PELTA H.R., VERDEGAY J.L., Application of Fuzzy Optimization to Diet Problems in Argentinian Farms, Eur. J. of Oper. Res., 2003, in press.
  2. CADENAS J.M., VERDEGAY J.L., Optimisation Models with Imprecise Data, SPUM, 1999, in Spanish.
  3. DELGADO M., KACPRZYK J., VERDEGAY J.L., VILA M.A. (eds.), Fuzzy Optimisation: Recent Advances, Physica-Verlag, 1994.
  4. DIAZ A., GLOVER F., GHAZIRI H., GONZALEZ J., LAGUNA M., MOSCATO P., TSENG F., Heuristic Optimization and Neural Nets, Ed. Paraninfo, 1996, in Spanish.
  5. HERRERA F., VERDEGAY J.L., Fuzzy Control Rules in Optimisation Problems, Scientia Iranica, 1996, 3, 89-96.
  6. HERRERA F., VERDEGAY J.L., Fuzzy Sets and Operations Research: Perspectives, Fuzzy Sets and Systems, 1997, 90, 207-218.
  7. HOROWITZ E., SAHNI S., Computing partitions with applications to the knapsack problem, Journal of ACM, 1974, 21, 277-292.
  8. LITTLE J.D.C., MURTY K.G., SWEENEY D.W., KAREL C., An algorithm for the travelling salesman problem, Operations Research, 1963, 11, 972-989.
  9. MARTELLO S., TOTH P., Knapsack Problems, John Wiley and Sons, 1990.
  10. ROSENKRANTZ D.J., STEARNS R.E., LEWIS P.M. II, An analysis of several heuristics for the travelling salesman problem, SIAM J. Computing, 1977, 6, 563-581.
  11. SAHNI S., Approximate algorithms for the 0-1 knapsack problem, Journal of ACM, 1975,22, 115-124.
  12. SALKIN H.M., MATHUR K., Foundations of integer programming, North-Holland, New York 1989.
  13. SANCHO-ROYO A., VERDEGAY J.L., VERGARA-MORENO E., Some Practical Problems in Fuzzy Sets-based Decision Support Systems, Mathware and Soft Computing, 1999, VI, 2-3, 173-187.
  14. VERDEGAY J.L., Fuzzy Sets Based Heuristics for Optimization, Springer Verlag, Studies in Fuzziness and Soft Computing Series, 2003.
  15. VERDEGAY J.L., VERGARA-MORENO E., Fuzzy Termination Criteria in Knapsack Problem Algorithms, Mathware and Soft Computing, 2000, VII, No. 2-3, 89-97.
  16. VERDEGAY J.L., VERGARA E., Fuzzy Stop Criteria for Knapsack Problems, Proceedings of the I Congress of the European Association of Fuzzy Logic and Technologies and del IX Congreso Espafiol sobre Tecnologias y Logica Fuzzy (1999 EUSFLAT-ESTYLF Joint Conference), Palma de Mallorca, 267-270, (in Spanish).
  17. VERDEGAY J.L., VERGARA-MORENO E., Fuzzy Termination Criteria in Knapsack Problem Algorithms, Mathware and Soft Computing, 2000, VII, No. 2-3, 89-97.
  18. VERDEGAY J.L., VERGARA-MORENO E., Fuzzy Sets-based Control Rules for Terminating Algorithms, Computer Science Journal of Moldova, 2002, 10, 1, 9-27.
  19. VERGARA E.R., New Termination Criteria for Optimization Algorithms, Ph.D. Dissertation. Universidad de Granada, 1990 (in Spanish).
Cited by
Show
ISSN
1230-1868
Language
eng
Share on Facebook Share on Twitter Share on Google+ Share on Pinterest Share on LinkedIn Wyślij znajomemu