الگوریتمی جدید برای پیدا کردن نقاط بهینه پارتو در مسائل بهینه‌سازی چندهدفه

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری-دانشکده ریاضی و علوم کامیپوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران

2 استاد تمام-دانشکده ریاضی و علوم کامیپوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران

3 استاد یار، دانشکده علوم ریاضی، دانشگاه صنعتی شاهرود، شاهرود، ایران

چکیده

DOR : 20.1001.1.24766291.1399.5.1.6.7
در این مقاله یک روش اسکالرسازی اصلاح‌شده برای بدست آوردن مجموعه نقاط پارتو در مسائل بهینه‌سازی چندهدفه مورد بررسی قرار می‌گیرد. روش پیشنهادی، تعمیمی از روش‌های تقاطع مرزی نرمال محدودشده و روش پاسکلوتی-سرافینی می‌باشد. در ابتدا، مساله بهینه‌سازی مربوط به روش اصلاح‌شده را بررسی می‌کنیم و سپس الگوریتمی برای بدست آوردن مجموعه نقاط بهینه پارتو ارایه می‌دهیم. در ادامه، روابط بین جواب‌های بهینه مساله اسکالرسازی و جواب‌های کارا (ضعیف، سره) مسائل بهینه‌سازی چندهدفه را بررسی می‌کنیم. در واقع شرایط لازم برای جواب‌های کارا (ضعیف، سره) مسائل بهینه‌سازی چندهدفه را بدست می‌آوریم. نتایج حاصل شده بدون شرط تحدب ناحیه شدنی مساله چندهدفه برقرار می‌باشند. در ادامه یک الگوریتم جدید برای تقریب زدن مرز پارتوی مسائل چندهدفه ارایه می دهیم. چندین مثال را به کمک الگوریتم ارایه شده حل و نتایج را با روشهای موجود مقایسه می کنیم. نتایج حاصله نشان از کارایی رویکرد پیشنهاد شده نسبت به روشهای معروف موجود دارد.

کلیدواژه‌ها


عنوان مقاله [English]

A new algorithm for finding Pareto optimal points of multiobjective optimization problems

نویسندگان [English]

  • Fereshteh Akbari 1
  • Esmaile Khorram 2
  • Mehrdad Ghaznavi 3
1 Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran.
2 Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
3 Assistant Professor-Shahrood University of Technology
چکیده [English]

In this paper, a modified scalarization technique for finding Pareto optimal points of multiobjective optimization problems is provided. The proposed method is a combination of the normal constraint and elastic constraint method. First, we introduce the optimization problem of the modified method and then we present an algorithm for obtaining the set of Pareto points. Thereafter, the relationship between optimal solutions of this scalarization problem and (weakly, properly) efficient solutions of the multiobjective optimization problems are analyzed. Indeed, some necessary conditions for (weak, proper) efficiency are presented. All the provided results are established without any convexity assumption. Furthermore, we propose a new algorithm for approximating the Pareto front of multiobjective optimization problems. We solve some test problems by applying the suggested algorithm and compare the results with some existing methods, including the epsilon-constraint method, the Pascolleti-Serafini method and the NBI method. The obtained results highlight the efficiency of our approach in comparison with examined methods.

کلیدواژه‌ها [English]

  • Multiobjective optimization problem
  • Scalarization
  • Normalization
  • Pareto points
  • Properly efficient solutions
Amiri, M., Taghavi Fard, M.T., Aghaei, M. (2016). Development of three-objective model for the location – allocation of assistance centers in a probabilistic condition of availability to emergency vehicles,  Modern Research in Decision Making, 1(2), 1-27 (In Persian).
Rasouli, N., Marandi, F., Nahavandi, N. (2018). An integrated approach based on MADM and MODM for supplier selection and assembler selection in supply chain management, Modern Research in Decision Making, 3(1), 159-185  (In Persian).
Niusha, A., Azar, A., Moazzez, H., Heydari, K. (2019). A multi-objective optimization model for iran's renewable power portfolio. Management Research in Iran, 23(1), 171-191 (In Persian).
Mohebbi, N., Rad, A., Motameni, A. (2018). Developing sustainable recovery model of end-life products (case study: end-of life vehicle). Management Research in Iran, 22(2) 227-249 (In Persian).
Eichfelder, G. (2009).  An adaptive Scalarization Methods in Multiobjective Optimization. Springer-Verlag, Berlin, Heidelberg.
Hwang, C.L., Masud, A.S. (1979). Multiple objective decision making, methods and applications. Springer-Verlag.
Pareto, V. (1964). Course Economics Politique. Libraire Droze, Geven.
Akbari, F., Ghaznavi, M., Khorram, E. (2018). A Revised Pascoletti-Serafini scalarization
method for multiobjective optimization problems. J. Optim. Theory Appl, 178, 560-590.
Ehrgott, M. (2005). Multicriteria Optimization. Berlin: Springer.
Ghaznavi, M., Akbari, F. and Khorram, E. (2019). Optimality conditions via a unified direction approach for (approximate) efficiency in multiobjective optimization. Optim. Methods Softw. DOI 10.1080/10556788.2019.1571589 (In press).
Ghaznavi, M., Azizi, Z. (2017). An algorithm for approximating nondominated points of convex multiobjective optimization problems, Bulletin of the Iranian Mathematical Society 43 (5), 1399-1415.
Ghaznavi, M. (2017). Optimality conditions via scalarization for approximate quasi efficiency in multiobjective optimization, Filomat, 31 (3), 671-680.
Ghaznavi-ghosoni, B.A., Khorram, E., Soleimani-damaneh, M. (2013). Scalarization for characterization of approximate strong/weak/proper efficiency in multi-objective optimization. Optimization, 62 (6), 703-720.
Dolatnezhadsomarin, A., Khorram, E. (2019). Two efficient algorithms for constructing almost even approximations of the Pareto front in multi-objective optimization problems. Engineering Optimization, 51(4), 567-589.
Chankong, V., Haimes, Y. (1983). Multiobjective Decision Making: Theory and Methodology. Elsevier Science Publishing Company New York, NY.
Haimes, Y.Y., Lasdon, L.S., Wismer, D.A. (1971). On a bicriterion formulation of the problems of intergrated system identification and system optimization. IEEE Trans. Syst. Man Cybern, 1, 296-297.
Pascoletti, A., Serafini, P. (1984). Scalarizing vector optimization problem. J. Optimization Theory Apple, 42(4), 499-524.
Ehrgott, M., Ryan, D. (2002). Constructing robust crew schedules with bicriteria optimization. Journal of Multi-Criteria Decision Analysis, 11(3), 139-150.
Das, I., Dennis, J.E. (1998). Normal-Boundary Intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM Journal on Optimization, 8, 631-657.
Messac, A., Mattson, C.A. (2004). Normal constraint method with guarantee of even representation of complete Pareto frontier. AIAA Journal 42(10), 2101-2111.
Siddiqui, S., Azarm, S., (2012). Gabriel On improving normal boundary intersection method for generation of Pareto frontier. Structural and Multidisciplinary Optimization, 46, 839-852.
Burachik, R.S., Kaya, C.Y., Rizvi, M.M. (2013). A new scalarization technique to approximate Pareto fronts of problems with disconnected feasible sets. Journal of Optimization Theory and Application, 162(2), 428-446.
Ghosh, D., Chakraborty, D. (2014). A direction based classical method to obtain complete Pareto set of multi-criteria optimization problems. OPSEARCH 52(2), 340-366.
Ghane-Kanafi, A., Khorram, E. (2015). A new scalarization method for finding the efficient frontier in non-convex multi-objective problems. Applied Mathematical Modelling.
Benson, H. (1979). An improved definition of proper efficiency for vector maximization with respect to cones. Journal of Optimization Theory and Applications, 71, 232-241.
Borwein, J.M. (1977). Proper efficient points for maximization with respect to cones. SIAM Journal on Control and Optimization 15, 57-63.
Geoffrion, A. (1968). Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl, 22,618–630.
Rizvi, M.M. (2013). New optimality conditions for non-linear multiobjective optimization problems and new scalarization techniques for constructing pathological Pareto fronts, PhD
Thesis, University of South Australia.
Kim, Y.I. and Weck, O.De. (2006). Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation. Structural and Multidisciplinary Optimization, 31, 105-116.