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 {ℝ}^n$ — קבוצה לא ריקה של פתרונות אפשריים, ו-$f_i:S\to ℝ$ — פונקציות המטרה ($k\ge 2$). הווקטור $f(x)=(f_1(x),\dots ,f_k(x))$ נקרא וקטור המטרה.

בניגוד לאופטימיזציה סקלרית, בניסוח הרב-קריטריוני בדרך כלל אין פתרון יחיד המשפר את ערכי כל הקריטריונים בו-זמנית. לכן, המושג הקלאסי של אופטימום מוכלל באמצעות מושג האופטימליות לפי פארטו.

• פתרון פארטו (פתרון אופטימלי לפי פארטו, או פתרון יעיל): פתרון אפשרי $x^{\ast }\in S$ שלא קיים פתרון אחר $x\in S$ כך ש-$f_i(x)\le f_i(x^{\ast })$ לכל $i=1,\dots ,k$, ובנוסף $f_j(x)<f_j(x^{\ast })$ לפחות למדד אחד $j$. במילים אחרות, פתרון הוא אופטימלי לפי פארטו אם אי אפשר לשפר ערך של קריטריון כלשהו מבלי להרע לפחות קריטריון אחד אחר.
• חזית פארטו (או קבוצת פארטו): קבוצת כל וקטורי המטרה המתאימים לפתרונות האופטימליים לפי פארטו.
• פתרון אופטימלי חלש לפי פארטו: פתרון $x^{\ast }\in S$ שלא קיים פתרון אחר $x\in S$ כך ש-$f_i(x)<f_i(x^{\ast })$ לכל $i$.

תכונות מרכזיות ומשפטים

• משפט הסכום המשוקלל: בבעיות קמורות (שבהן כל הפונקציות $f_i(x)$ והקבוצה $S$ קמורות), כל פתרון אופטימלי לפי פארטו $x^{\ast }$ הוא פתרון של בעיית מינימיזציה סקלרית של הסכום המשוקלל של הקריטריונים $\underset{x\in S}{min}\sum _{i=1}^k{w}_i{f}_i(x)$ עבור קבוצה כלשהי של משקלות אי-שליליות $w_i\ge 0$. עם זאת, בבעיות לא-קמורות שיטה זו עשויה שלא למצוא חלקים מסוימים של חזית פארטו.

• תנאי האופטימליות של Karush–Kuhn–Tucker (KKT): תנאים הכרחיים לאופטימליות בבעיות חלקות מוכללים לפתרון הרב-קריטריוני. בנקודת אופטימום פארטו קיימת קבוצה לא-אפסית של מכפילים (משקלות) אי-שליליים, שעבורם גרדיאנטי פונקציות המטרה והאילוצים הפעילים תלויים לינארית.

• תכונות קבוצת הפתרונות: לחזית פארטו ישנן מספר מאפיינים איכותיים חשובים. גבולה תחום על ידי הנקודה האידיאלית (המורכבת מהמינימומים האיבריים של כל הקריטריונים) ונקודת הנאדיר (מהמקסימומים האיבריים על החזית).

דוגמאות

• בעיה לינארית: מינימיזציה של $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$). קבוצת הפתרונות האופטימליים לפי פארטו היא קטע הישר $x_1+x_2=1$.
• בעיה לא-קמורה: מינימיזציה של $f_1(x)=x^2$ ו-$f_2(x)=(x-2{)}^2$ על הקטע $[0,2]$. חזית פארטו היא לא-קמורה. שיטת הסכומים המשוקללים עם משקלות חיוביות לא תוכל למצוא פתרונות בתוך קטע זה (לדוגמה, בנקודה $x=1$), מכיוון שהצירוף הלינארי של הקריטריונים יגיע למינימום רק בנקודות הקצה $x=0$ או $x=2$.

מושגים קשורים ויישומים

אופטימיזציה רב-קריטריונית קשורה קשר הדוק לקבלת החלטות רב-קריטריונית (MCDM), העוסקת בבחירת החלופה הטובה ביותר תוך התחשבות בהעדפות מקבל ההחלטות. השיטות העיקריות להמרת בעיה רב-קריטריונית לסקלרית (סקלריזציה) כוללות:

• שיטת הסכום המשוקלל.
• שיטת אילוצי $\epsilon$: מבוצעת אופטימיזציה של קריטריון אחד, בעוד שהשאר הופכים לאילוצים מהצורה $f_i(x)\le {\epsilon }_i$. שיטה זו מסוגלת למצוא פתרונות בחלקים לא-קמורים של החזית.

אופטימיזציה רב-קריטריונית נמצאת בשימוש נרחב בתכנון הנדסי, בכלכלה (לדוגמה, אופטימיזציה של תיק השקעות), בניהול ובאקולוגיה.

ראו גם

• אופטימליות לפי פארטו
• אופטימיזציה וקטורית
• תורת קבלת ההחלטות
• מערכות תמיכה בקבלת החלטות
• חקר ביצועים