ÇOK AMAÇLI TAMSAYI PROGRAMLAMA PROBLEMLERİ İÇİN TEMSİLİ ÇÖZÜM ÜRETEN YAKLAŞIMLARIN VE KALİTE ÖLÇÜLERİNİN İNCELENMESİ

Yıl 2017, Cilt: 28 Sayı: 1, 19 - 39, 31.05.2017

Banu Lokman

Öz

Çok amaçlı tamsayı programlama problemlerinde baskın noktaların sayısı problemin büyüklüğüne bağlı olarak üssel bir büyüme gösterir. Bu nedenle, bu problemler için tüm baskın noktaları bulmak zordur ve karar verici için pratik bir yaklaşım da değildir. Tüm baskın noktalar yerine, bu noktaları belirli kalite ölçülerine göre iyi temsil eden noktalar bulmak önemlidir. Bu çalışmamızda, temsili kümenin değerlendirilmesinde kullanılan kalite ölçülerini ve bu kalite ölçülerine göre tüm baskın nokta kümesini iyi temsil eden noktalar bulan yaklaşımları inceleyeceğiz.

Anahtar Kelimeler

Baskın nokta, temsili baskın nokta, kalite ölçüleri, çok amaçlı tamsayı programlama

A SURVEY ON FINDING REPRESENTATIVE POINTS FOR MULTI-OBJECTIVE INTEGER PROGRAMS AND QUALITY MEASURES

Öz

The number of nondominated points of multi-objective integer programming problems increases exponentially with the problem size. Therefore, finding all nondominated points is computationally hard and not practical for the decision maker. Instead of generating all nondominated points, it is reasonable to generate a set of points that represents the nondominated set with a desired quality level. In this study, we review the quality measures used to evaluate the representative sets and the approaches that generate representative points.

Anahtar Kelimeler

Nondominated point, representative point, quality measures, multi-objective integer programming

Kaynakça

• 1. Aktaş, E., Özaydın, Ö., Ülengin, F., Önsel, Ş., Ağaran, B. 2011. “İstanbul’da İtfaiye İstasyonu Yerlerinin Seçimi İçin Yeni Bir Model,” Endüstri Mühendisliği Dergisi, sayı 22 (4), s. 2-12.
• 2. Armann, R. 1987. “Solving Multiobjective Programming Problems by Discrete Representation,” Optimization, vol. 20, p. 483-492.
• 3. Aytuğ, H., Sayın, S. 2009. “Using Support Vector Machines to Learn the Efficient Set in Multiple Objective Discrete Optimization,” European Journal of Operational Research, vol. 193, p. 510-519.
• 4. Bazgan, C., Jamain, F., Vanderpooten, D. 2015. “Approximate Pareto Sets of Minimal Size for Multi-Objective Optimization Problems,” Operation Research Letters, vol. 43, p. 1-6.
• 5. Boland, N., Charkhgard, H., Savelsbergh, M. 2015. “A Criterion Space Search Algorithm for Biobjective Integer Programming: The Balanced Box Method,” INFORMS Journal on Computing, vol. 27 (4), p. 735-754.
• 6. Boland, N., Charkhgard, H., Savelsbergh, M. 2016. “The L-Shape Search Method for Triobjective Integer Programming,” Mathematical Programming Computation, vol. 8 (2), p. 217-251.
• 7. Burkard, R. E., Hamacher, H., Rote, G. 1991. “Sandwich Approximation of Univariate Convex Functions with an Application to Separable Convex Programming,” Naval Research Logistics, vol. 38 (6), p. 911-924.
• 8. Ceyhan, G. 2014. “Generating Representative Nondominated Point Subsets in Multiobjective Integer Programs,” Yüksek Lisans Tezi, Orta Doğu Teknik Üniversitesi, Fen Bilimleri Enstitüsü, Ankara.
• 9. Chen, J., Li, J., Xin, B. 2017. “DMOEA-εC: Decomposition-Based Multi-Objective Evolutionary Algorithm with the ε-Constraint Framework,” IEEE Transactions on Evolutionary Computation, DOI 10.1109/TEVC.2017.2671462.
• 10. Czyzżak, P., Jaszkiweicz, A. 1998. “Pareto Simulated Annealing - a Metaheuristic Technique for Multiple-Objective Combinatorial Optimization,” Journal of Multi-Criteria Decision Analysis, vol. 7, p. 34-47.
• 11. Dächert, K., Klamroth, K. 2015. “A Linear Bound on the Number of Scalarizations Needed to Solve Discrete Tricriteria Optimization Problems,” Journal of Global Optimization, vol. 61 (4), p. 643-676.
• 12. Deb, K. 2001. Multiobjective Optimization Using Evolutionary Algorithms, Chichester, Wiley, U. K.
• 13. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T. 2002. “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, p. 182-197.
• 14. Diakonikolas, I., Yannakakis, M. 2009. “Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems,” SIAM Journal on Computing, vol. 39 (4), p. 1340-1371.
• 15. Ehrgott, M., Gandibleux, X. 2000. “A Survey and Annotated Bibliography of Multiobjective Combinatorial Optimization,” OR Spectrum, vol. 22 (4), p. 425-460.
• 16. Ehrgott, M., Gandibleux, X. 2004. “Approximative Solution Methods for Multiobjective Combinatorial Optimization,” Sociedad de Estadística E Investigación Operativa, vol. 12 (1), p. 1-89.
• 17. Ehrgott, M., X. Gandibleux. 2008. “Hybrid Metaheuristics for Multi-Objective Combinatorial Optimization,” Studies in Computational Intelligence (SCI), vol. 114, p. 221-259.
• 18. Eusébio, A., Figueira, J. R., Ehrgott, M. 2014. “On Finding Representative Non-Dominated Points for Bi-Objective Integer Network Flow Problems,” Computers & Operations Research, vol. 48, p. 1-10.
• 19. Faulkenberg, S. L., Wiecek, M. M. 2010. “On the Quality of Discrete Representations in Multiple Objective Programming,” Optimization and Engineering, vol. 11 (3), p. 423-440.
• 20. Faulkenberg, S. L., Wiecek, M. M. 2012. “Generating Equidistant Representations in Biobjective Programming,” Computational Optimization and Applications, vol. 51, p. 1173-1210.
• 21. Filippi, C., Stevanato, E. 2013. “Approximation Schemes for Bi-Objective Combinatorial Optimization and Their Application to the TSP with Profits,” Computers & Operations Research, vol. 40, p. 2418-2428.
• 22. Goldberg, D. E. 1989. Genetic Algorithm in Search, Optimisation, and Machine Learning, Addison-Wesley, Boston.
• 23. Goldberg, D. E., Richardson, J. 1987. “Genetic Algorithms with Sharing for Multimodal Function Optimization,” In Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, J. J. Grefenstette, Ed. Hillsdale, NJ: Lawrence, Erlbaum, 1987, p. 41-49.
• 24. Hamacher, H. W., Pedersen, C. R., Ruzika, S. 2007. “Finding Representative Systems for Discrete Bicriterion Problems,” Operations Research Letters, vol. 35, p. 336-344.
• 25. Ishibuchi, H., Murata, T. 1998. “Multi-Objective Genetic Local Search Algorithm and its Application to Flowshop Scheduling,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 28 (3), p. 392-403.
• 26. Jorge, J. M. 2009. “An Algorithm for Optimizing a Linear Function over an Integer Efficient Set,” European Journal of Operational Research, vol. 195, p. 98-103.
• 27. Kamışlı Öztürk, Z., Kasımbeyli, N., Sağır Özdemir, M., Soyuöz Acar, M., Özçetin, E., Alegöz, M., Ceylan, G. 2016. “Kullanıcı Tercihlerinin Dikkate Alınması Durumunda Üniversite Ders Çizelgeleme Problemi,” Endüstri Mühendisliği Dergisi, sayı 27 (1), s. 2-16.
• 28. Karasakal, E., Köksalan, M. 2009. “Generating a Representative Subset of the Nondominated Frontier in Multiple Criteria Decision Making,” Operations Research, vol. 57 (1), p. 187-199.
• 29. Kırlık, G., Sayın, S. 2014. “A New Algorithm for Generating all Nondominated Solutions of Multiobjective Discrete Optimization Problems,” European Journal of Operational Research, vol. 232 (3), p. 479-488.
• 30. Kırlık, G., Sayın, S. 2015. “Computing the Nadir Point for Multiobjective Discrete Optimization Problems,” Journal of Global Optimization, vol. 62 (1), p. 79-99.
• 31. Koçanlı, M. M., Aydınbeyli, Y. E., Saraç, T. 2012. “Eti Şirketler Grubu’nda Üretim Çizelgeleme Problemi İçin Bir Hedef Programlama Modeli ve Genetik Algoritma,” Endüstri Mühendisliği Dergisi, sayı 23 (3), p. 4-21.
• 32. Kohonen, T. 1998. “The self-Organizing Map,” Neurocomputing, vol. 21 (1-3), p. 1-6.
• 33. Kouvelis, P., Sayın, S. 2006. “Algorithm Robust for the Bicriteria Discrete Optimization Problem: Heuristic Variations and Computational Evidence,” Annals of Operation Research, vol. 147, p. 71-85.
• 34. Köksalan, M. 1999. “A Heuristic Approach to Bicriteria Scheduling,” Naval Research Logistics, vol. 46 (7), p. 777-789.
• 35. Köksalan, M., Lokman, B. 2009. “Approximating the Nondominated Frontiers of Multi-Objective Combinatorial Optimization Problems,” Naval Research Logistics, vol. 56, p. 191-198.
• 36. Köksalan, M., Lokman, B. 2015. “Finding Nadir Points for Multi-Objective Integer Programs,” Journal of Global Optimization, vol. 62, p. 55-77.
• 37. Lokman, B., Köksalan, M. 2013. “Finding all Nondominated Points of Multi-Objective Integer Programs,” Journal of Global Optimization, vol. 57, p. 347-365.
• 38. Masin, M., Bukchin, Y. 2008. “Diversity Maximization Approach for Multiobjective Optimization,” Operations Research, vol. 56 (2), p. 411-424.
• 39. Mavrotas, G., Florios, K. 2013. “An Improved Version of the Augmented e-Constraint Method (AUGMECON2) for Finding the Exact Pareto Set in Multi-Objective Integer Programming Problems,” Applied Mathematics and Computation, vol. 219, p. 9652-9669.
• 40. Miettinen, K., Eskelinen, P., Ruiz, F., Luque, M. 2010. “NAUTILUS Method: An Interactive Technique in Multi-Objective Optimization Based on the Nadir Point,” European Journal of Operational Research, vol. 206 (2), p. 426-434.
• 41. Osman, I., Laporte, G. 1996. “Metaheuristics: A Bibliography,” Annals of Operations Research, vol. 63, p. 513-623.
• 42. Özçelik, F., Saraç, T. 2011. “Sıra Bağımlı Hazırlık Süreli İki Ölçütlü Tek Makine Çizelgeleme Problemi İçin Sezgisel Bir Çözüm Yöntemi,” Endüstri Mühendisliği Dergisi, sayı 22 (4), s. 48-57.
• 43. Özlen, M., Burton B. A., MacRae, C. A. G. 2014. “Multi-Objective Integer Programming: An Improved Recursive Algorithm,” Journal of Optimization Theory and Applications, vol. 160 (2), p. 470-482.
• 44. Papadimitriou, C. H., Yannakakis, M. 2000. “On the Approximability of Trade-Offs and Optimal Access of Web Sources,” In: Proceedings of the 41st IEEE FOCS, IEEE Computer Society Press, p. 86-92.
• 45. Ponte, A., Paquete, L., Figueira J. 2012. “On Beam Search for Multicriteria Combinatorial Optimization Problems,” In: Beldiceanu N, Jussien N, Pinson E, editors. Proceedings of the 9th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2012, May 28-June 1, 2012, Nantes, France; Lecture Notes in Computer Science, Springer, Berlin, Germany, p. 307-321.
• 46. Pospelov, A. 2009. “Approximating the Convex Edgeworth-Pareto Hull in Integer Multi-Objective Problems with Monotone Criteria,” Computational Mathematics and Mathematical Physics, vol. 49 (10), p. 1686-1699.
• 47. Ruhe, G., Fruhwirth, B. 1990. “ε-Optimality for Bicriteria Programs and its Application to Minimum Cost Flows,” Computing, vol. 44 (1), p. 21-34.
• 48. Ruzika, S., Wiecek, M. M. 2005. “Survey Paper: Approximation Methods in Multi-Objective Programming,” Journal of Optimization Theory and Applications, vol. 126 (3), p. 473-501.
• 49. Sayın, S. 2000. “Measuring the Quality of Discrete Representations of Efficient Sets in Multiple Objective Mathematical Programming,” Mathematical Programming, vol. 87 (3), p. 543-560.
• 50. Sayın, S., Kouvelis, P. 2005. “The Multi-Objective Discrete Optimization Problem: A Weighted Min-Max Two-Stage Optimization Approach and a Bicriteria Algorithm,” Management Science, vol. 51 (10), p. 1572-1581.
• 51. Schaffer, J. D. 1984. “Multiple Objective Optimization with Vector Evaluated Genetic Algorithms,” Ph. D. Dissertation, Vanderbilt University, Nashville, TN. 52. Schott, J. R. 1995. “Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization,” Master’s Thesis, Massachusetts Institute of Technology.
• 53. Shukla, P. K., Deb, K. 2007. “On Finding Multiple Pareto-Optimal Solutions Using Classical and Evolutionary Generating Methods,” European Journal of Operational Research, vol. 181, p. 1630-1652.
• 54. Silverman, B. W. 1986. Density Estimation for Statistics and Data Analysis, Chapman and Hall, London.
• 55. Sipahioğlu, A., Saraç, T. 2010. “Çok Amaçlı Sırt Çantası Probleminin Çözümüne Yeni Bir Yaklaşım: Konik Skalerleştirme,” Endüstri Mühendisliği Dergisi, sayı 21 (4) s. 2-12.
• 56. Srinivas, N., Deb, K. 1995. “Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms,” Evolutionary Computation, vol. 2 (3), p. 221-248.
• 57. Steiner, S., Radzik, T. 2008. “Computing all Efficient Solutions of the Biobjective Minimum Spanning Tree Problem,” Computers & Operations Research, vol. 35 (1), p. 198-211.
• 58. Steuer, R. E. 1986. Multiple Criteria Optimization: Theory, Computation, and Application, John Wiley & Sons, Inc., New York, NY.
• 59. Sylva, J., Crema, A. 2007. “A Method for Finding Well-Dispersed Subsets of Non-Dominated Vectors for Multiple Objective Mixed Integer Linear Programs,” European Journal of Operational Research, vol. 180 (3), p. 1011-1027.
• 60. Tuyttens, D., Teghem, J., Fortemps, P., Nieuwenhuyze, K. V. 2000. “Performance of the Mosa Method for the Bicriteria Assignment Problem,” Journal of Heuristics, vol. 6 (3), p. 295-310.
• 61. Ulungu, E. L., Teghem, J. 1995. “The Two-Phases Method: An Efficient Procedure to Solve Bi-Objective Combinatorial Optimization Problems,” Foundations of Computing and Decision Sciences, vol. 20 (2), p. 149-165.
• 62. Ulungu, E. L., Teghem, J., Fortemps, P. H., Tuyttens, D. 1999. “MOSA Method: A Tool for Solving Multiobjective Combinatorial Optimization Problems,” Journal of Multi-Criteria Decision Analysis, vol. 8, p. 221-236.
• 63. Van Veldhuizen, D. A. 1999. “Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations,” Ph. D. Thesis, Department of Electrical and Computer Engineering, Graduate School of Engineering, Air Force Institute of Technology, Wright-Patterson AFB, Ohio.
• 64. Vassilvitskii, S., Yannakakis, M. 2005. “Efficiently Computing Succinct Trade-off Curves,” Theoretical Computer Science, vol. 348 (2-3), p. 334-356.
• 65. Vaz, D., Paquete, L., Fonseca, C. M., Klamroth, K., Stiglmayr, M. 2015. “Representation of the Nondominated Set in Bi-Objective Discrete Optimization,” Computers & Operations Research, vol. 63, p. 172-186.
• 66. Visee, M., Teghem, J., Pirlot, M., Ulungu, E. L. 1998. “Two-Phases Method and Branch and Bound Procedures to Solve the Bi-Objective Knapsack Problem,” Journal of Global Optimization, vol. 12, p.139-155.
• 67. Wang, H. 2015. “Direct Zigzag Search for Discrete Multi-Objective Optimization,” Computers & Operations Research, vol. 61, p. 100-109.
• 68. Wierzbicki, A. P. 1980. “The Use of Reference Objective in Multiobjective Optimization,” G. Fandel, T. Gal, eds. Multiple Criteria Decision Making, Theory and Application, Springer-Verlag, Berlin, p. 468-486.
• 69. Wu, J., Azarm, S. 2001. “Metrics for Quality Assessment of a Multiobjective Design Optimization Solution Set,” Journal of Mechanical Design, Transactions of the ASME, vol. 123 (1), p. 18-25.
• 70. Zhang, Q., Li, H. 2007. “MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition,” IEEE Transactions on Evolutionary Computation, vol. 11 (6), p. 712-731.
• 71. Zhang, H., Zhou, A., Song, S., Zhang, Q., Gao, X., Zhang, J. 2016. “A Self Organizing Multiobjective Evolutionary Algorithm,” IEEE Transactions on Evolutionary Computation, vol. 20 (5), p. 792-806.
• 72. Zhou, A., Qu, B.-Y., Li, H., Zhao, S-Z., Suganthan, P. N., Zhang, Q. 2011. “Multiobjective Evolutionary Algorithms: A Survey of the State of the Art,” Swarm and Evolutionary Computation, vol. 1, p. 32-49.
• 73. Zitzler, E. 1999. “Evolutionary Algorithms for Multi-Objective Optimization: Methods and Applications,” Ph. D., Swiss Federal Institute of Technology, Zurich.
• 74. Zitzler, E., Laumanns, M., Thiele, L. 2002. “SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization,” In: Giannakoglou, K., et al. (eds.) Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001), p. 95-100. International Center for Numerical Methods in Engineering, Spain.
• 75. Zitzler, E., Thiele, L. 1998. “Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study,” In: Parallel Problem Solving from Nature - PPSN V, volume 1498 of the series Lecture Notes in Computer Science, Springer, Berlin, p. 292-301.
• 76. Zitzler, E., Thiele, L. 1999. “Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach,” IEEE Transactions on Evolutionary Computation, vol. 3 (4), p. 257-271.
• 77. Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., Grunert da Fonseca, V. 2003. “Performance Assessment of Multiobjective Optimizers: An Analysis and Review,” IEEE Transactions on Evolutionary Computation, vol. 7 (2), p. 117-132.