Procedura metaheurystyczna Pareto-SA dla realnych i wielokryterialnych problemów optymalizacji kombinatorycznej

• Autorzy: Piotr Czyżak , Andrzej Jaszkiewicz
• Języki publikacji: PL

Abstrakty

Wiele rzeczywistych problemów decyzyjnych ma charakter kombina- toryczny, tj. polega na wybraniu jednego rozwiązania ze skończonego, lecz bardzo dużego zbioru dopuszczalnych decyzji. Jednocześnie, w praktycznych sytuacjach, wzięcie pod uwagę tylko jednego kryterium do wyboru końcowego rozwiązania jest często niewystarczające. Konieczne jest zatem uwzględnienie wielu, często wzajemnie sprzecznych, punktów widzenia opisanych przez różne funkcje kryterialne. Tego typu sytuacje decyzyjne określa się mianem problemów wielokryterialnej optymalizacji kombinatorycznej (WOK). Problemy WOK pojawiają się w rozmaitych dziedzinach, np. zarządzaniu, ochronie środowiska oraz inżynierii. Jako przykłady w artykule omawiane są problemy: wielokryterialnej optymalizacji systemu komunikacji miejskiej, wielokryterialnego harmonogramowania przedsięwzięć, wielokryterialnej optymalizacji systemu oczyszczania ścieków w zlewisku rzecznym oraz wielokryterialnego grupowania obiektów (zastosowanego w projektowaniu układów scalonych). Wszystkie te problemy, chociaż dotyczą bardzo różnych dziedzin, można sformułować matematycznie jako problemy WOK. Problemy kombinatoryczne są trudne już w wersji jednokryterialnej. Wiąże się to z dużą, często wykładniczą złożonością obliczeniową, dokładnych metod ich rozwiązywania. (fragment tekstu)

Słowa kluczowe

PL

Kombinatoryka; Optymalizacja wielokryterialna; Analiza wielokryterialna; Zasada Pareto

EN

Combinatorial analysis; Multiple criteria optimization; Multicriteria analysis; Pareto principle

• Czasopismo: Prace Naukowe / Akademia Ekonomiczna w Katowicach
• Rocznik: 1994
• Tom: Podejmowanie decyzji w warunkach niepełnej informacji - systemy wspomagania decyzji
• Strony: 21--34

Twórcy

autor

Piotr Czyżak

autor

Andrzej Jaszkiewicz

Bibliografia

• M.Garey, D.Johnson: Computers and Intractability: A Guide to the Theory of NP-compIeteness, San Francisco 1979
• E.L.Ulungu, J.Teghem: "Multi-objective Combinatorial Optimization Problems: A Survey. "Journal of Multi-Criteria Decision Analysis" 1994, No 3, p.83-104
• D.J. White: A Bibliography on the Applications of Mathematical Programming Multiple- Objective Methods. "Journal OpI Res. Soc." 1990, No 41, p.669-691
• P.J.M. van Laarhoven, E.H.L. Aarts: Simulated Annealing; Theory and Applications. Dordrecht 1987
• F. Glover: Tabu search - part I. "ORSA Journal on Computing" 1989, No. 1/3, p.190-206
• D.E. Goldberg: Genetic Algorithms in Search, Optimization and Machine Learning. New York 1987
• P.Czyżak, A. Jaszkiewicz: Procedura metaheurystyczna dla zadań wielokryterialnej optymalizacji kombinatorycznej. Materiały Konferencji nt. Analizy Decyzyjnej, Systemów Eksperckich i Zastosowań Systemów Komputerowych. Warszawa 25-27.05.1994
• SR.E.Steuer: Mulliple Criteria Optimization - Theory, Computation and Application. New York 1986
• P.Serafini: Simulated Annealing for Multiple Objective Optimization Problems. Proceedings of the Tenth International Conference on Multiple Criteria Decision Making. Taipei 19-24.07.1992, Vol. 1, p.87-96
• H P.Czyżak, M.Hapke, A. Jaszkiewicz: Application of the Pareto-Simulated Annealing to the Multiple Criteria Shortest Path Problem