BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Verdegay Jose Luis, Vergara-Moreno Edmundo
Tytuł
Solving NP-Hard Problems by Using Fuzzy Sets-Based Heuristics
Rozwiązywanie NP-trudnych problemów przy użyciu heurystyk opartych na zbiorach rozmytych
Źródło
Badania Operacyjne i Decyzje, 2003, nr 4, s. 167-183, bibliogr. 19 poz.
Operations Research and Decisions
Słowa kluczowe
Zbiory rozmyte, Systemy rozmyte, Programowanie liniowe, Algorytmy, Teoria podejmowania decyzji
Fuzzy sets, Fuzzy systems, Linear programming, Algorithms, Decision making theory
Abstrakt
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.
Dostępne w
Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie
Biblioteka Szkoły Głównej Handlowej
Biblioteka Główna Uniwersytetu Ekonomicznego w Katowicach
Biblioteka Główna Uniwersytetu Ekonomicznego w Poznaniu
Biblioteka Główna Uniwersytetu Ekonomicznego we Wrocławiu
Bibliografia
Pokaż
  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).
Cytowane przez
Pokaż
ISSN
1230-1868
Język
eng
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu