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

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

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

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

## Εισαγωγή

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


\begin{align}
\min_{x} &\left[\mu_1(x), \mu_2(x),\dots, \mu_n(x) \right]^T & \\
s.t. & \\
g(x) & \le 0 \\
h(x) & = 0 \\
x_l \le & x  \le x_u 
\end{align}


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

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

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

### Κατασκευάζοντας ένα συνάθροισμα αντικειμενικών συναρτήσεων (aggregate objective function - AOF)
Αυτή είναι ίσως η πιο διαισθητική προσέγγιση για την επίλυση προβλημάτων με πολλαπλά κριτήρια. Η βασική ιδέα είναι να συνδυαστούν όλες οι αντικειμενικές συναρτήσεις σε μια μόνο συναρτησιακή μορφή, η οποία ονομάζεται AOF. Ένας γνωστός συνδυασμός είναι το σταθμισμένο γραμμικό άθροισμα των κριτηρίων. Ορίζουμε βαθμωτά σταθμά για το κάθε προς βελτιστοποίηση κριτήριο, και στη συνέχεια τα συνδυάζουμε σε μια συνάρτηση που μπορεί να επιλυθεί από έναν βελτιστοποιητή μονού κριτηρίου (όπως  ο τρόπος SQP κ.τ.λ.). Ξεκάθαρα, η λύση που θα προκύψει θα βασίζεται στις τιμές (πιο συγκεκριμένα, τις σχετικές τιμές) των σταθμών που καθορίστηκαν. Για παράδειγμα, αν προσπαθούμε να μεγιστοποιήσουμε  την δύναμη ενός εξαρτήματος μιας μηχανής και να ελαχιστοποιήσουμε το κριτήριο του κόστους και αν έχει οριστεί υψηλότερο σταθμικό για το κριτήριο κόστους έναντι αυτού της δύναμης, η λύση μας θα  ικανοποιεί τα κριτήρια της μείωσης του κόστους έναντι στην αύξηση της δύναμης. Παρόλα αυτά, μπορεί να παρατηρηθεί ότι η μέθοδος αυτή είναι κατά βάση υποκειμενική, καθώς πρέπει ένας υπεύθυνος λήψης αποφάσεων ( Decision Manager -DM) να παρέχει τα σταθμά. Πέραν τούτου, αυτή η προσέγγιση δεν μπορεί να αναγνωρίσει όλες τις μη επικρατούσες λύσεις (μόνο λύσεις που βρίσκονται στο κυρτό  μέτωπο του συστήματος Pareto μπορούν να βρεθούν). Ο αντικειμενικός τρόπος επίλυσης προβλημάτων βελτιστοποίησης με πολλαπλά κριτήρια χρειάζεται μια συμβατή με το σύστημα Pareto μέθοδο βαθμολόγησης, ευνοώντας τις μη επικρατούσες λύσεις, όπως φαίνεται σε πρόσφατες πολύ-κριτηριακές προσεγγίσεις όπως η NSGA-II   και  SPEA2. Εδώ, δεν χρειάζονται σταθμά οπότε δεν χρειάζονται και προηγούμενες πληροφορίες για το πρόβλημα. 
### Μέθοδοι NBI, NC, SPO
Οι μέθοδοι  NBI (Λογικής Οριακής  Διατομής, Normal Boundary Intersection), NC (Λογική Σύγχυση, Normal Constraint) και SPO (Διαδοχικής  Pareto Βελτιστοποίησης, Successive Pareto Optimization) επιλύουν προβλήματα βελτιστοποίησης πολλαπλών κριτηρίων κατασκευάζοντας διάφορα 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)
*Δημιουργία επιφάνειας Pareto για κυρτά  πολυκριτηριακά βήματα (PGEN  - Pareto surface generation for convex multiobjective instances)
*Έμμεση βελτιστοποίηση στη βάση της αυτόνομης οργάνωσης (Indirect Optimization on the basis of Self-Organization)

## Παραπομπές


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

Κατηγορία:Βελτιστοποίηση