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

• Autorzy: Jose Luis Verdegay , Edmundo Vergara-Moreno

Warianty tytułu

Rozwiązywanie NP-trudnych problemów przy użyciu heurystyk opartych na zbiorach rozmytych

• Języki publikacji: EN

Abstrakty

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.

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.

Słowa kluczowe

EN

Fuzzy sets; Fuzzy systems; Linear programming; Algorithms; Decision making theory; Heuristics

PL

Zbiory rozmyte; Systemy rozmyte; Programowanie liniowe; Algorytmy; Teoria podejmowania decyzji; Heurystyka

• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2003
• Numer: nr 4
• Strony: 167--183

Twórcy

autor

Jose Luis Verdegay

autor

Edmundo Vergara-Moreno

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).