Dışbükey Çok Amaçlı Eniyileme Problemleri için Yaklaşıklama Algoritma Varyantları

Dışbükey çok amaçlı eniyileme problemlerini Pareto kümeye iç ve dış yaklaşık kümeler bulmak anlamında ‘çözen’ bir Benson tipi algoritma ele alınmıştır. Algoritma her yinelemede o anki dış yaklaşık kümenin herhangi bir köşesi için Pascoletti-Serafini skalerizasyon modeli çözer. Bu şekilde bu köşenin Pareto kümeye yeterince yakın olup olmadığı anlaşılır. Eğer yeterince yakın değilse o anki dış yaklaşık küme bir kesit eklenerek güncellenir. Bu uygulama tüm köşeler Pareto kümeye yeterince yakın oluncaya kadar tekrarlanır. Dış yaklaşık kümenin güncellemesi işlemi, Pareto kümeye yeterince yakın olmayan ilk köşe bulunduktan sonra yapılabileceği gibi tüm köşeler kontrol edildikten sonra da yapılabilmektedir. Bu seçim algoritmanın çalışma performansını etkilemektedir. Bu çalışma ile algoritmaya bu iki uç varyanta ek olarak farklı varyantlar önerilmiş ve tüm varyantların performansları bilgisayımsal testler yolu ile karşılaştırılmıştır.

Anahtar Kelimeler:

Çok amaçlı eniyileme, algoritmalar, dışbükey eniyileme, doğrusal programlama

PDF

___

[1] Armand,P.: Finding all maximal efficient faces in multiobjective linear programming. Mathematical Programming 61, 357 – 375 (1993)
[2] Armand, P. and Malivert, C.; Determination of the efficient set in multiobjective linear programming. Journal of Optimization Theory and Applications 70, 467-489 (1991)
[3] Benson, H.P.: An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. Journal of Global Optimization 13, 1-24 (1998)
[4] Csirmaz, L.: Using multiobjective optimization to map the entropy region. Computational Optimization and Applications, 63(1):45 – 67, 2016.
[5] Eichfelder, G.: Adaptive Scalarization Methods in Multiobjective Optimization (Springer, Berlin, 2008).
[6] Ehrgott, M., Löhne, A., Shao, L.: A dual variant of Benson’s outer approximation algorithm. Journal of Global Optimization 52(4), 757–778 (2012)
[7] Ehrgott, M., Shao, L., Schöbel, A.: An approximation algorithm for convex multi-objective programming problems. Journal of Global Optimization 50(3), 397–416 (2011)
[8] Ehrgott, M., Wiecek, M. M.: Multiobjective programming. In: Figueira, J., Greco, S., Ehrgott, M., (eds.) Multiple Criteria Decision Analysis: State of the Art Surveys. Springer Science + Business Media, Berlin, 667–722 (2005)
[9] Evans, J.P., Steuer, R.E.: A revised simplex method for multiple objective programs. Mathematical Programming 5(1), 54–72 (1973)
[10] Grant, M. and Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.0 beta. http://cvxr.com/cvx (September 2013)
[11] Grant, M. and Boyd, S.: Graph implementations for nonsmooth convex programs, Recent Advances in Learning and Control (a tribute to M. Vidyasagar), Blondel, V., Boyd, S. and Kimura, H. editors, 95-110, Lecture Notes in Control and Information Sciences, Springer (2008).
[12] Hamel, A.H., Löhne, A., Rudloff, B.: Benson type algorithms for linear vector optimization and applications. Journal of Global Optimization 59(4), 811–836 (2014)
[13] Jahn, J.: Vector Optimization: Theory, Applications, and Extensions. Springer, Berlin (2004)
[14] Löhne, A.: Vector Optimization with Infimum and Supremum. Springer, Berlin (2011)
[15] Löhne, A., Rudloff, B., Ulus, F.: Primal and dual approximation algorithms for convex vector optimization problems. Journal of Global Optimization 60(4), 713–736 (2014)
[16] Löhne, A., Weißing, B.: The vector linear program solver Bensolve -- notes on theoretical background, European Journal of Operational Research 260(3), 807-813 (2017)
[17] Löhne, A., Weißing, B.: BENSOLVE: A free VLP solver, version 2.0.0.alpha (2014)
[18] Pascoletti, A., Serafini, P.: Scalarizing vector optimization problems. Journal of Optimization Theory and Applications, 42(4), 499–524 (1984)
[19] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
[20] Rockafellar, R.T., Wets, R. J-B.: Variational Analysis. Springer, Berlin (2009)
[21] Shao, L., Ehrgott, M.: Approximately solving multiobjective linear programmes in objective space and an application in radiotherapy treatment planning. Mathematical Methods of Operations Research 68(2), 257–276 (2008)