Βελτιστοποίηση με πολλαπλά κριτήρια

Βελτιστοποίηση με πολλαπλά κριτήρια (ή προγραμματισμός),^[1][2] επίσης γνωστή και ως βελτιστοποίηση με πολλαπλά αντικείμενα ή χαρακτηριστικά , είναι η διαδικασία της ταυτόχρονης βελτιστοποίησης δυο ή περισσότερων αντικρουόμενων ζητημάτων με διαφόρους περιορισμούς.

Προβλήματα βελτιστοποίησης με πολλαπλά κριτήρια μπορούν να βρεθούν σε διαφόρους τομείς : παράγωγη και σχεδιασμός διαδικασιών, οικονομικά, σχεδιασμό αεροσκαφών, πετρελαϊκές βιομηχανίες, σχεδιασμό αυτοκίνητων, ή οπουδήποτε χρειάζεται να παρθεί η καταλληλότερη απόφαση για την εξισορρόπηση όλων των παραγόντων μεταξύ δυο η περισσότερων αντικρουόμενων στόχων. Μεγιστοποιώντας το κέρδος και ελαχιστοποιώντας το κόστος ενός προϊόντος, μεγιστοποιώντας την απόδοση και ελαχιστοποιώντας την κατανάλωση καυσίμου σε ένα όχημα και ελαχιστοποιώντας το βάρος καθώς μεγιστοποιείται η αντοχή κάποιου εξαρτήματος είναι παραδείγματα προβλημάτων βελτιστοποίηση με πολλαπλά κριτήρια.

Εάν ένα πρόβλημα βελτιστοποίησης με πολλαπλά κριτήρια είναι καλώς ορισμένο, τότε δεν θα υπάρχει μοναδική λύση η οποία ταυτόχρονα να ελαχιστοποιεί τον κάθε στόχο στο ελάχιστο δυνατό. Σε κάθε περίπτωση ένα κριτήριο πρέπει να έχει φτάσει ένα σημείο τέτοιο ώστε κάθε προσπάθεια επιπλέον βελτιστοποίησής του να έχει ως αποτέλεσμα την υποβάθμιση άλλων κριτηρίων. Το να βρεθεί μια τέτοια λύση, και να πιστοποιηθεί το πόσο καλύτερη είναι συγκριτικά με άλλες (γενικά θα υπάρχουν πολλές) είναι ο σκοπός όταν συντίθεται και λύνεται ένα πρόβλημα βελτιστοποίησης με πολλαπλά κριτήρια.

Εισαγωγή

Με μαθηματικούς όρους, το πρόβλημα βελτιστοποίησης με πολλαπλά κριτήρια μπορεί να διατυπωθεί και ως:

${\displaystyle {\begin{aligned}\min _{x}&\left[\mu _{1}(x),\mu _{2}(x),\dots ,\mu _{n}(x)\right]^{T}&\\s.t.&\\g(x)&\leq 0\\h(x)&=0\\x_{l}\leq &x\leq x_{u}\end{aligned}}}$

όπου ${\displaystyle \mu _{i}}$ είναι η αντικειμενική συνάρτηση του ${\displaystyle i}$ κριτηρίου, τα ${\displaystyle g}$ και ${\displaystyle h}$ είναι οι περιορισμοί ανισότητας και ισότητας αντίστοιχα, και το ${\displaystyle x}$ είναι το διάνυσμα των μεταβλητών βελτιστοποίησης ή απόφασης. Η λύση για το ανωτέρω πρόβλημα είναι ένα σύνολο από σημεία Pareto. Οι λύσεις Pareto είναι εκείνες για της όποιες η βελτιστοποίηση ενός κριτηρίου μπορεί να επέλθει μόνο με την χειροτέρευση ενός τουλάχιστον κριτηρίου. Παρόλα αυτά, αντί για μια μόνο λύση στο πρόβλημα (κάτι το οποίο είναι τυπικά η περίπτωση του παραδοσιακού μαθηματικού προγραμματισμού), η λύση σε ένα πρόβλημα πολλαπλών κριτηρίων είναι μια σειρά (πιθανότατα άπειρων) σημείων Pareto.

Ένα σημείο σχεδιασμού στον αντικειμενικό χώρο ${\displaystyle \mu ^{*}}$ ορίζεται ως βέλτιστο Pareto αν δεν υπάρχει κανένα άλλο εφικτό διάνυσμα ${\displaystyle \mu }$ τέτοιο ώστε ${\displaystyle \mu _{i}\leq \mu _{i}^{*}}$ για όλα τα ${\displaystyle i\in \left\{{1,2,...,n}\right\}}$, και ${\displaystyle \mu _{j}<\mu _{j}^{*}}$ για τουλάχιστον έναν δείκτη ${\displaystyle j}$, ${\displaystyle j\in \left\{{1,2,...,n}\right\}}$.

Μέθοδοι Επίλυσης

Κατασκευάζοντας ένα συνάθροισμα αντικειμενικών συναρτήσεων (aggregate objective function - AOF)

Αυτή είναι ίσως η πιο διαισθητική προσέγγιση για την επίλυση προβλημάτων με πολλαπλά κριτήρια. Η βασική ιδέα είναι να συνδυαστούν όλες οι αντικειμενικές συναρτήσεις σε μια μόνο συναρτησιακή μορφή, η οποία ονομάζεται AOF. Ένας γνωστός συνδυασμός είναι το σταθμισμένο γραμμικό άθροισμα των κριτηρίων. Ορίζουμε βαθμωτά σταθμά για το κάθε προς βελτιστοποίηση κριτήριο, και στη συνέχεια τα συνδυάζουμε σε μια συνάρτηση που μπορεί να επιλυθεί από έναν βελτιστοποιητή μονού κριτηρίου (όπως ο τρόπος SQP κ.τ.λ.). Ξεκάθαρα, η λύση που θα προκύψει θα βασίζεται στις τιμές (πιο συγκεκριμένα, τις σχετικές τιμές) των σταθμών που καθορίστηκαν. Για παράδειγμα, αν προσπαθούμε να μεγιστοποιήσουμε την δύναμη ενός εξαρτήματος μιας μηχανής και να ελαχιστοποιήσουμε το κριτήριο του κόστους και αν έχει οριστεί υψηλότερο σταθμικό για το κριτήριο κόστους έναντι αυτού της δύναμης, η λύση μας θα ικανοποιεί τα κριτήρια της μείωσης του κόστους έναντι στην αύξηση της δύναμης. Παρόλα αυτά, μπορεί να παρατηρηθεί ότι η μέθοδος αυτή είναι κατά βάση υποκειμενική, καθώς πρέπει ένας υπεύθυνος λήψης αποφάσεων ( Decision Manager -DM) να παρέχει τα σταθμά. Πέραν τούτου, αυτή η προσέγγιση δεν μπορεί να αναγνωρίσει όλες τις μη επικρατούσες λύσεις (μόνο λύσεις που βρίσκονται στο κυρτό μέτωπο του συστήματος Pareto μπορούν να βρεθούν). Ο αντικειμενικός τρόπος επίλυσης προβλημάτων βελτιστοποίησης με πολλαπλά κριτήρια χρειάζεται μια συμβατή με το σύστημα Pareto μέθοδο βαθμολόγησης, ευνοώντας τις μη επικρατούσες λύσεις, όπως φαίνεται σε πρόσφατες πολύ-κριτηριακές προσεγγίσεις όπως η NSGA-II ^[3] και SPEA2. Εδώ, δεν χρειάζονται σταθμά οπότε δεν χρειάζονται και προηγούμενες πληροφορίες για το πρόβλημα. ^[4]

Μέθοδοι NBI, NC, SPO

Οι μέθοδοι NBI (Λογικής Οριακής Διατομής, Normal Boundary Intersection)^[5][6], NC (Λογική Σύγχυση, Normal Constraint)^[7][8] και SPO (Διαδοχικής Pareto Βελτιστοποίησης, Successive Pareto Optimization)^[9] επιλύουν προβλήματα βελτιστοποίησης πολλαπλών κριτηρίων κατασκευάζοντας διάφορα AOF. Η επίλυση του κάθε AOF αποδίδει ένα σημείο Pareto κάτω από κάποιες υποθέσεις. Εάν οι υποθέσεις δεν ισχύουν, τότε η μέθοδος NC προτείνει την αφαίρεση τον μη-Pareto σημείων διαδοχικά με ένα φίλτρο Pareto. Τα AOF κατασκευάζονται με σκοπό να αποκτήσουν εν τέλη διανεμημένα σημεία Pareto τα οποία δίνουν μια καλή εντύπωση (διαδικασία προσέγγισης) του πραγματικού συνόλου των σημείων Pareto. Οι μέθοδος NC και SPO δημιουργούν λύσεις που αναπαριστούν μερικές περιφερειακές περιοχές του συνόλου τον σημείων Pareto για περισσότερα από 2 κριτήρια τα οποία είναι γνωστό πως δεν αναπαρίστανται από τις λύσεις που δημιουργούνται από την μέθοδο NBI .

Εξελικτικοί Αλγόριθμοι

Οι εξελικτικοί αλγόριθμοι είναι πολύ δημοφιλείς προσεγγίσεις στις πολυκριτηριακές βελτιστοποιήσεις. Την σημερινή εποχή, οι περισσότεροι εξελικτικοί βελτιστοποιητές εφαρμόζουν βασισμένα στο Pareto σχήματα βαθμολόγησης. Οι γενετικοί αλγόριθμοι όπως ο Non-dominated Sorting Genetic Algorithm-II (NSGA-II) και Strength Pareto Evolutionary Approach 2 (SPEA-2) έχουν γίνει κλασσικές προσεγγίσεις, παρόλο που μερικά σχήματα βασισμένα σε βελτιστοποιήσεις σμήνους σωματιδίων και σε προσομοιωμένη ισχυροποίηση είναι σημαντικά.

Άλλες μέθοδοι

• Πολυκριτηριακοί Βελτιστοποιητικοί Εξελικτικοί Αλγόριθμοι (Multiobjective Optimization Evolutionary Algorithms - MOEA)^[10][11][12]
• Δημιουργία επιφάνειας Pareto για κυρτά πολυκριτηριακά βήματα (PGEN - Pareto surface generation for convex multiobjective instances)^[13]
• Έμμεση βελτιστοποίηση στη βάση της αυτόνομης οργάνωσης (Indirect Optimization on the basis of Self-Organization)

Παραπομπές

1. Steuer, R.E. (1986). Πολλαπλά κριτήρια βελτιστοποίησης: Θεωρία, Υπολογισμοί, και Εφαρμογή. New York: John Wiley & Sons, Inc. ISBN 047188846X.
2. Sawaragi, Y. (1985). Θεωρία βελτιστοποίησης με πολλαπλά κριτήρια (τόμος 176 από Μαθηματικά στην Επιστήμη και Μηχανική). Orlando, FL: Academic Press Inc. ISBN 0126203709. Unknown parameter |coauthors= ignored (|author= suggested) (βοήθεια)
3. Deb, K., Pratap. A, Agarwal, S., and Meyarivan, T.: Ένας γρήγορος και εκλεπτυσμένος πολύ-κριτηριακός γενετικός: NSGA-II. IEEE Διεκπεραίωση σε Εξελικτικό Υπολογισμό , τόμος. 6, no2, pp. 181-197, 2002.
4. Deb, K.: Βελτιστοποίηση με πολλαπλά κριτήρια χρησιμοποιώντας εξελικτικούς αλγορίθμους. Wiley, 2002.
5. I. Das and J. E. Dennis. Normal-Boundary Intersection: Μια νέα μέθοδος για την δημιουργία της επιφανείς Pareto σε μη γραμμικά προβλήματα βελτιστοποίησης. SIAM Journal on Optimization, 8:631–657, 1998.
6. Normal-Boundary Intersection: An Alternate Method For Generating Pareto Optimal Points In Multicriteria Optimization Problems
7. A. Messac and A. Ismail-Yahaya and C.A. Mattson: Η μέθοδος κοινωνικοποιημένης λογικής σύγχυσης για την δημιουργία του συνόρου Pareto . Structural and multidisciplinary optimization, τόμος. 25, no2, pp. 86-98, 2003.
8. A. Messac and C. A. Mattson: Μέθοδος λογικής σύγχυσης με εγγύηση ακόμη και της αναπαράστασης ολοκλήρου του Pareto . AIAA journal, τόμος. 42, no10, pp. 2101-2111, 2004.
9. Daniel Mueller-Gritschneder, Helmut Graeb and Ulf Schlichtmann: Μια διαδοχική προσέγγιση για τον υπολογισμό του υποχρεωτικού συνόρου Pareto σε πρακτικά προβλήματα πολλαπλών κριτήριων. SIAM Journal on Optimization, Volume 20, Issue 2, pp. 915-934, 2009.
10. Deb, K. Multi-Objective Optimization using Evolutionary Algorithms John Wiley & Sons, 2001.
11. Coello Coello, C. A.; Lamont, G. B. & Van Veldhuizen, D. A. Evolutionary Algorithms for Solving Multi-Objective Problems Springer, 2007.
12. Das, S.; Panigrahi, B. K. Multi-objective Evolutionary Algorithms, Encyclopedia of Artificial Intelligence, (Eds. J. R. Rabuñal, J. Dorado & A. Pazos), Idea Group Publishing, 3:1145 – 1151, 2008.
13. D. Craft, T. Halabi, H. Shih, and T. Bortfeld. Approximating convex Pareto surfaces in multiobjective radiotherapy planning. Medical Physics, 33(9):3399–3407, 2006.

Πηγές

• M.Ehrgott. Multicriteria optimization. Springer 2005. ISBN 978-3-540-21398-7
• Ανάρτηση από φοιτητή του τμήματος Μάρκετινγκ και Διοίκησης Λειτουργιών του πανεπιστήμιου Μακεδονίας στα πλαίσια του μαθήματος Διοίκησης Διεργασιών