אופטימיות לגבי כלי האופטימיזציה

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

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

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

האופטימיזציה בסביבת MATLAB מתבצעת באמצעות שני כלים:

1) Optimization Toolbox – אוסף של אלגוריתמים איטרטיבים, נפוצים בתעשיה, המוצאים פתרונות אופטימליים באמצעות חישוב נגזרות (Steepest Descent). בין האלגוריתמים:

•  fmincon- אלגוריתם למציאת מינימום לבעיות בעלות פונקצית מטרה לא לינארית, תחת אילוצים שונים (לינאריים ולא לינאריים).
•  fminmax- אלגוריתם למציאת מינימום לבעיות MinMax, תחת אילוצים שונים.
•  Linear Programming- לפתרון בעיות בעלות פונקצית מטרה לינארית, תחת אילוצים שונים.
•  Quadratic Programming- לפתרון בעיות קוואדרטיות, תחת אילוצים שונים.

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

 2) Global Optimization Toolbox – אוסף של שיטות היוריסטיות למציאת פתרונות אופטימליים גלובלים (הכלי לא מבוסס על חישובי נגזרות). בין האלגוריתמים:

•  Simulated Annealing- אלגוריתם הממדל את הפיסיקה של תהליך קירור של מתכת. האלגוריתם עובד טוב במיוחד כאשר מרחב חיפוש הפתרון הוא גדול והבעיה היא ללא אילוצים.
•  Genetic Algorithm- אלגוריתם איטרטיבי זה ממדל תהליך אבולוציוני למציאת פתרונות אופטימליים, והינו נפוץ לביצוע אופטימיזציה גלובלית תחת אילוצים שונים. האלגוריתם מתאים במיוחד לפתרון בעיות אופטימיזציה קומבינטוריות (דוגמת בעית הסוכן הנוסע) בתוך מרחב חיפוש גדול .
•  Direct Search- אלגוריתם איטרטיבי אשר בכל איטרציה מחפש בסביבה הקרובה של נקודה כלשהי נקודות בהן ערך הפונקציה נמוך יותר, ואם מוצא אחת כזו - הוא בוחר בה כנקודת התחלה לאיטרציה הבאה. האלגוריתם מתאים במיוחד לבעיות בהן פונקצית המטרה איננה גזירה או אינה רציפה. 

היתרון של ה-Global Optimization Toolbox הוא באלגוריתמים המאפשרים למצוא פתרון גלובלי בתוך אוסף גדול של מינימות מקומיות ומאפשרים לפתור בעיות אופטימזיציה קומבינטוריות.

ועם שני כלי האופטימיזציה של MathWorks שפורטו לעיל, בטוח שמעתה פתרון בעיות האופטימיזציה שלכם יהיה אופטימלי ! אז אפשר להיות קצת יותר אופטימיים...

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