Solving NP - hard problems by using fuzzy sets-based heuristics

• Autorzy: Verdegay J. , Vergara-Moreno E.

Warianty tytułu

PL

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 situation. Fuzzy sets-based heuristics for Linear Programming problems are considered. To show the practical realizations 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.

PL

Głównym celem artykułu jest zaprezentowani, 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 programu 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 zagadnienia plecakowe. Na zakończenie przedstawiono wyniki eksperymentów ukazujących nieprzeciętne możliwości proponowanych algorytmów.

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2003
• Tom: nr 4
• Strony: 167--183
• Opis fizyczny: Bibliogr. 19 poz., tab.

Twórcy

autor

Verdegay J.

• Department of Computer Sciences and Artificial Intelligence, University of Granada, Daniel Saucedo Aranda s/n, 180071 Granada, Spain

autor

Vergara-Moreno E.

• Department of Mathematics, National University of Trujillo, Av. Juan Pablo II s/n , Trujillo, Peru

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 Espanol sobre Tecnologias y Logica Fuzzy (1999 EUSFLAT-ESTYLF Joint Conference), Palma dc 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).