Multi-objective optimization — Πολυκριτηριακή Βελτιστοποίηση

Πολυκριτηριακή βελτιστοποίηση (επίσης πολυκριτηριακός προγραμματισμός, αγγλ. multi-objective optimization, multi-criteria optimization) — είναι ένας κλάδος της μαθηματικής βελτιστοποίησης που μελετά προβλήματα ταυτόχρονης βελτιστοποίησης ως προς δύο ή περισσότερες αντικειμενικές συναρτήσεις (κριτήρια), οι οποίες, κατά κανόνα, έρχονται σε σύγκρουση μεταξύ τους. Τυπικά, το πρόβλημα διατυπώνεται ως ελαχιστοποίηση διανυσματικής αντικειμενικής συνάρτησης επί του συνόλου των αποδεκτών λύσεων.

Ορισμός και ορολογία

Το πρόβλημα πολυκριτηριακής βελτιστοποίησης στη γενική του μορφή διατυπώνεται ως εξής: $\underset{x\in S}{\min }\{f_1(x),f_2(x),\dots ,f_k(x)\}$ όπου $S\subseteq {\mathbb{ℝ}}^n$ — μη κενό σύνολο αποδεκτών λύσεων, και $f_i:S\to \mathbb{ℝ}$ — αντικειμενικές συναρτήσεις ($k\ge 2$). Το διάνυσμα $f(x)=(f_1(x),\dots ,f_k(x))$ ονομάζεται διάνυσμα στόχων.

Σε αντίθεση με τη βελτιστοποίηση βαθμωτής συνάρτησης, στη διατύπωση πολλαπλών κριτηρίων συνήθως δεν υπάρχει μία και μοναδική λύση που να βελτιώνει ταυτόχρονα όλα τα κριτήρια. Γι' αυτό η κλασική έννοια του βέλτιστου γενικεύεται με τη χρήση της έννοιας της βελτιστότητας κατά Pareto.

• Λύση Pareto (βέλτιστη κατά Pareto ή αποδοτική λύση): αποδεκτή λύση $x^{*}\in S$, για την οποία δεν υπάρχει άλλη λύση $x\in S$ τέτοια ώστε $f_i(x)\le f_i(x^{*})$ για όλα τα $i=1,\dots ,k$, και ταυτόχρονα $f_j(x)<f_j(x^{*})$ για τουλάχιστον έναν δείκτη $j$. Με άλλα λόγια, μια λύση είναι βέλτιστη κατά Pareto εάν κανένα κριτήριο δεν μπορεί να βελτιωθεί χωρίς να επιδεινωθεί τουλάχιστον ένα άλλο κριτήριο.
• Μέτωπο Pareto (ή σύνολο Pareto): το σύνολο όλων των διανυσμάτων στόχων που αντιστοιχούν σε βέλτιστες κατά Pareto λύσεις.
• Ασθενώς βέλτιστη κατά Pareto λύση: λύση $x^{*}\in S$, για την οποία δεν υπάρχει άλλη λύση $x\in S$ τέτοια ώστε $f_i(x)<f_i(x^{*})$ για όλα τα $i$.

Βασικές ιδιότητες και θεωρήματα

• Θεώρημα σταθμισμένου αθροίσματος: Σε κυρτά προβλήματα (όπου όλες οι συναρτήσεις $f_i(x)$ και το σύνολο $S$ είναι κυρτά) κάθε βέλτιστη κατά Pareto λύση $x^{*}$ είναι λύση του βαθμωτού προβλήματος ελαχιστοποίησης του σταθμισμένου αθροίσματος κριτηρίων $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$ για κάποιο σύνολο μη αρνητικών βαρών $w_i\ge 0$. Ωστόσο, σε μη κυρτά προβλήματα, αυτή η μέθοδος ενδέχεται να μην εντοπίσει ορισμένα τμήματα του μετώπου Pareto.

• Συνθήκες βελτιστότητας Karush-Kuhn-Tucker (KKT): Οι αναγκαίες συνθήκες βελτιστότητας για λεία προβλήματα γενικεύονται στην πολυκριτηριακή περίπτωση. Στο σημείο βέλτιστου κατά Pareto υπάρχει μη μηδενικό σύνολο μη αρνητικών πολλαπλασιαστών (βαρών), για τα οποία οι κλίσεις των αντικειμενικών συναρτήσεων και των ενεργών περιορισμών είναι γραμμικά εξαρτημένες.

• Ιδιότητες του συνόλου λύσεων: Το μέτωπο Pareto διαθέτει μια σειρά σημαντικών ποιοτικών χαρακτηριστικών. Το όριό του οριοθετείται από το ιδανικό σημείο (που αποτελείται από τα στοιχειακά ελάχιστα όλων των κριτηρίων) και το σημείο ναδίρ (από τα στοιχειακά μέγιστα στο μέτωπο).

Παραδείγματα

• Γραμμικό πρόβλημα: Ελαχιστοποίηση $f_1(x)=-x_1$ και $f_2(x)=-x_2$ υπό τον περιορισμό $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Εδώ η βελτίωση ενός κριτηρίου (π.χ. αύξηση του $x_1$) οδηγεί αναπόφευκτα στην επιδείνωση του άλλου (μείωση του $x_2$). Το σύνολο των βέλτιστων κατά Pareto λύσεων είναι το τμήμα της ευθείας $x_1+x_2=1$.
• Μη κυρτό πρόβλημα: Ελαχιστοποίηση $f_1(x)=x^2$ και $f_2(x)=(x-2{)}^2$ στο διάστημα $[0,2]$. Το μέτωπο Pareto είναι μη κυρτό. Η μέθοδος σταθμισμένων αθροισμάτων με θετικά βάρη δεν θα μπορέσει να βρει λύσεις στο εσωτερικό αυτού του διαστήματος (π.χ. στο σημείο $x=1$), καθώς ο γραμμικός συνδυασμός των κριτηρίων θα επιτυγχάνει ελάχιστο μόνο στα ακραία σημεία $x=0$ ή $x=2$.

Συναφείς έννοιες και εφαρμογές

Η πολυκριτηριακή βελτιστοποίηση συνδέεται στενά με τη λήψη αποφάσεων πολλαπλών κριτηρίων (MCDM), η οποία μελετά την επιλογή της καλύτερης εναλλακτικής λαμβάνοντας υπόψη τις προτιμήσεις του υπεύθυνου λήψης αποφάσεων. Οι κύριες μέθοδοι μετατροπής πολυκριτηριακού προβλήματος σε βαθμωτό (βαθμωτοποίηση) περιλαμβάνουν:

• Μέθοδος σταθμισμένων αθροισμάτων.
• Μέθοδος περιορισμών $\epsilon$: Βελτιστοποιείται ένα κριτήριο, ενώ τα υπόλοιπα μετατρέπονται σε περιορισμούς της μορφής $f_i(x)\le {\epsilon }_i$. Αυτή η μέθοδος είναι ικανή να εντοπίζει λύσεις σε μη κυρτά τμήματα του μετώπου.

Η πολυκριτηριακή βελτιστοποίηση βρίσκει ευρεία εφαρμογή στον μηχανολογικό σχεδιασμό, στην οικονομία (π.χ. βελτιστοποίηση χαρτοφυλακίου), στη διοίκηση και στην οικολογία.

Δείτε επίσης

• Βελτιστότητα κατά Pareto
• Διανυσματική βελτιστοποίηση
• Θεωρία λήψης αποφάσεων
• Συστήματα υποστήριξης λήψης αποφάσεων
• Επιχειρησιακή έρευνα