PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2003 | nr 4 | 167--183
Tytuł artykułu

Solving NP-Hard Problems by Using Fuzzy Sets-Based Heuristics

Warianty tytułu
Rozwiązywanie NP-trudnych problemów przy użyciu heurystyk opartych na zbiorach rozmytych
Języki publikacji
EN
Abstrakty
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.
EN
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.
Rocznik
Numer
Strony
167--183
Opis fizyczny
Bibliografia
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000000121961

Zgłoszenie zostało wysłane

Zgłoszenie zostało wysłane

Musisz być zalogowany aby pisać komentarze.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.