מה הוא אלגוריתם גנטי?

20 ביולי 2014

תגיות: ,
אין תגובות

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

  • תכנון מערכת שעות לבית-ספר (תוך התחשבות בגורמים שיכולים להיות סותרים זה לזה)
  • תכנון לוח משמרות למסעדות, מרכזי שירות וכו' (תוך התחשבות בהעדפות העובדים)
  • חלוקת משימות חישוב למערכת מחשוב מקבילית (תוך הקפדה על ניצולת מקסימלית במקביל לצמצום סך כל הזמן)
  • ועוד…

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

אלגוריתמים גנטים הם סוג אחד של אלגוריתם אבולוציוני (Evolutionary Algorithm או EA), שהם משפחה של אלגוריתמים שמקבלים השראה מתחום הביולוגיה ומדמים תהליכים שקורים בטבע.

רכיבים של אלגוריתם גנטי

כל אלגוריתם גנטי כולל מספר מרכיבים קבועים:

1. אוכלוסיה (population) של כרומוזומים (chromosomes). כל כרומוזום הוא למעשה הצעה לפתרון אפשרי לבעייה המוצגת, ומכאן שיש חשיבות רבה לדרך שבה כרומוזום מייצג את הבעיה. ניתן אף לומר שייצוג לא נכון מקשה מאוד על מציאת פיתרון בזמן סביר. האוכלוסיה היא מספר קבוע של כרומוזומים (המתעדכנים בכל דור) והיא מאגר הפתרונות האפשריים לבעייה המוכרים כרגע.

2. פונקציית התאמה (fitness function). זוהי פונקציה שמעניקה לכל כרומוזום ערך מספרי בהתאם לאיכות הפיתרון המקודד. כרומוזום טוב == פיתרון טוב == ערך התאמה גבוה יותר.

3. אופרטור מוטציה (mutation operator). זהו אופרטור המקבל כרומוזום בודד, ומבצע בו שינוי כלשהוא. חלק מהשינויים יובילו לערך התאמה נמוך יותר (כלומר, פתרון גרוע יותר) וחלק ערך התאמה גבוה יותר. הרעיון המנחה הוא שאם הכרומוזום הנוכחי הוא טוב, ייתכן ששינוי קטן יכול לייצר פתרון טוב אף יותר. כמו בטבע, גם כאן מוטציה יכולה לעיתים לפגוע בכרומוזום.

4. אופרטור שחלוף (crossover operator). זהו אופרטור המקבל שני כרומוזומים קיימים, ומייצר מהם שני כרומוזומים חדשים ע"י כך שהוא מבצע 'ערבוב' בין התוכן של שני הכרומוזומים 'ההורים'. הרעיון המנחה הוא שאם שני ההורים הם פתרונות טובים, הילדים יקבלו את התכונות הטובות משניהם ובכך יהיו גם הם פתרונות טובים יותר לבעייה.

אופן פעולת האלגוריתם הגנטי

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

בכל דור מבוצעים השלבים הבאים:

1. מוטציה. לכל כרומוזום באוכלוסיה הנוכחית יש סיכוי כלשהוא לעבור מוטציה. ההסתברות למוטציה היא אחד מהפרמטרים לאלגוריתם.

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

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

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

את האלגוריתם נבחר לעצור כאשר מתקיימים אחד או יותר מהתנאים הבאים:

· עברנו את מספר הדורות המקסימלי האפשרי

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

בעייה לדוגמא – מפת ישיבה לאירוע

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

מאפיינים טכניים בפיתרון

מחלקת Invitee – מייצג קבוצת אנשים המוזמנים לאירוע. כולל את שם הקבוצה ואת כמות האנשים בה. בפיתרון שלנו לא נאפשר פירוק של קבוצה – כלומר, Invitee בעל n אנשים יתפוס n מקומות באותו שולחן. (מכך משתמע גם שכמות המושבים בשולחן >= כמות האנשים המקסימלית באובייקט Invitee אחד.)

· מחלקת Acquaintance – מייצג רמת הכרות בין Invitee אחד לאחר. נקבע ש-0 משמעותו הוא עוינות קיצונית בעוד ש-10 משמעותו חיבה רבה. ברירת המחדל היא 5 ומשמעותה היא חוסר הכרות מוקדם (באמצע הדרך בין 0 ל-10).

· את הנתונים עצמם נשמור בקובץ XML באופן הבא:

1

כאן אנו מגדירים את המוזמנים השונים לארוע,

1

וכאן את את סוג הקשרים בין מוזמנים שונים. במקרה זה, ערך closeness של 0 פירושו עוינות רבה.

· מחלקת Planner – הגדרת האלגוריתם הגנטי עצמו. כאן נקבע את גודל האוכלוסיה, מספר הדורות שנרצה להריץ, את השימוש בכרומוזום מסוג ShortArrayChromosome ואת פונקציית ההתאמה.

· למימוש הפתרון נשתמש בספריית קוד פתוח בשם AForge.Net, הניתנת להורדה מכאן (https://code.google.com/p/aforge) או באמצעות NuGet.

· מבנה כרומוזום – כל כרומוזום יכיל מערך בגודל n (0 עד n-1, n הוא מספר ה-invitees הכולל), כאשר מספר התא מייצג את ה-id של ה-invitee. תוכנו של כל תא יכיל את מספר השולחן אליו משוייך ה-invitee. מספרי השולחנות הינם בין 0 למספר השלם הראשון שגדול מ-n/k, כאשר k הוא מספר האנשים המקסימלי בשולחן). סוג כזה של כרומוזום כבר מובנה בתוך AForge וביכולתנו להשתמש בו ישירות.

· פונקציית ההתאמה – הפונקציה שלנו ממומשת במחלקה AcquaintanceFitnessFunction ותבדוק לכל כרומוזום את הפרטים הבאים:

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

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

מאפייני הדוגמא

בדוגמא המצורפת אנו קובעים את הפרמטרים הבאים:

· מספר אנשים מקסימלי בשולחן – 6

· מספר דורות לריצה – 75

· גודל האוכלוסיה – 50

· 7 מופעים של מחלקת invitee, הכוללים סה'כ 15 אנשים (ומכאן שנדרש ל-3 שולחנות)

ונקבל את התוצאה הבאה (או תוצאה דומה לה):

1

ניתן בקלות לראות שהאלגוריתם אכן מצא סידור שתואם את אופי הקשרים שהזנו לו!

סיכום

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

את הקוד לדוגמא ניתן להוריד מכאן: http://1drv.ms/1zw1EeC.

 

יש

Yuval Mazorהפוסט נכתב על ידי יובל מזור, יועץ בכיר בקבוצת סלע ומרצה. מתמחה בנושאי ALM.

הוסף תגובה
facebook linkedin twitter email

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *