אלגוריתמים אבולוציוניים, שאלה לSilentMike

Wolverchenus

New member
אלגוריתמים אבולוציוניים, שאלה לSilentMike

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

SilentMike

New member
אז ככה.

אני מניח שמה שאתה שואל הוא איך ניגשים לבעיה כזו בגישה של אלגוריתמים אבולוציוניים. אפשר אולי לגשת אליה בדרכים אלגוריתמיות אחרות. אז נניח שיש לך בעיה הנדסית (כמו הבעיה שבכתבה) שאתה רוצה לפתור באמצעות אלגוריתם אבולוציוני. מה שאתה צריך לעשות זה (בערך) ככה: שלב 1: אתה לומד את הבעיה ולומד איך נראה פתרון לבעיה. שלב 2: אתה בוחר דרך לקודד את מרחב הפתרונות של הבעיה. שלב 3: אתה מוצא דרך יעילה ומהירה ככל האפשר (עדיף במחשב) להעריך את הפיטנס של פתרון. שלב 4: אתה בוחר את האופרטורים הגנטיים ואת האלגוריתם האבולוציוני. שלב 5: אתה מריץ. שלב 1 הוא חיוני בגלל שאתה צריך להבין מה אתה מנסה לעשות. בשלב 2 צריך לבחור יצוג שבו פתרונות טובים נמצאים קרוב האחד לשני ובלוקים מתוך פתרונות טובים צפויים להיות אבני בנין טובות לפתרונות אחרים (בעצם צריך שיווצרו "בלוקים" שמטפלים בתת-בעיות). שלב 3 הוא מובן מאליו. עדיף בהרבה לבדוק דברים במחשב פשוט כי זה חוסך בעבודה ובזמן. שלב 4 הוא המקום שבו אתה יכול לעשות את האלגוריתם שלך קצת יותר טוב בעזרת הבחירות הנכונות (אבל רק עם היצוג שבחרת בשלב 2 הוא טוב). ובשלב 5 אתה מחזיק אצבעות שלא תצטרך לחזור להתחלה אלא רק לשלב 4 בשביל מקצה שיפורים. התת-תחום הכי בולט של אלגוריתמים אבולוציוניים שמשמש בד"כ לבעיות "אמיתיות" עם פרטים "אמיתיים" (כלומר לא כאלה שנבררים בתוך המחשב) הוא Evolution Strategies הנפוץ במחקר ובתעשיה הגרמנית בעשורים האחרונים. היתרון שלו הוא שהוא יכול לעבוד גם על אוכלוסיות קטנות מאוד (כולל אוכלוסיה של 1).
 

Wolverchenus

New member
אוקיי סבבה

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

SilentMike

New member
תראה.

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

Wolverchenus

New member
כלומר,

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

SilentMike

New member
לא. זה לא מה שהתכוונתי.

זה גם לא מה שכתבתי. ניסיתי להבהיר את הנקודה שאפילו בחיים האמיתיים לפעמים מגיעים לקיצון מקומי. בוא אני אנסה להציג לך אנלוגיה לבעיות אופטימיזציה. תחשוב על משטח עם קווי מתאר של גבעות ועמקים. באנלוגיה יש לך שלושה מימדים. שניים של מרחב החיפוש (במציאות זה בד"כ יותר אבל קשה "לראות" את זה בראש) ואחד של הפיטנס. מה שאתה רוצה הוא למצוא מקסימום גובה ומה שאתה יכול לעשות זה "לדגום" את הפיטנס בכל מיני מקומות (תחשוב על זה כלשלוח צנחנים למטה אל המשטח). יכולות להיות לך כמה שיטות לזה: http://www.ami.ac.uk/courses/ami4622_dsp/u03/images/im_fig43.gif 1. אקראי: אתה שולח צנחנים לנקודות אקראיות, ומקווה שלפחות אחת מהן תהיה גבוהה. אתה כנראה לא תגיע למקסימום. לא מקומי ולא גלובלי. אבל כנראה שתעבור את הגובה הממוצע (כמה קרוב תגיע לאופטימום זה כבר תלוי באופי המשטח). 2. Hill climb: זו אסטרטגיה קלאסית של חיפוש שתמיד מוצאת אופטימום מקומי. אתה דוגם נקודה באקראי ואח"כ עולה מהנקודה הזו בשיטה מתמטית שנקראת Gradient descent אתה מתקדם בהדרגה לנקודה עם פיטנס טוב יותר. תחשוב שאתה שולח צנחן שיודע, אחרי שהוא נחת, לטפס על הגבעה שהוא במקרה נחת עליה. וככה אפשר להגיע לקיצון מקומי, בלי אלגוריתמים גנטיים ובלי נעליים (משתמשים בזה הרבה בלימוד של רשתות עצביות). 3. Hill climb עם ריבוי סוכנים: כמו 2, רק עם אוכלוסיה (עדיין בלי אבולוציה אבל). אתה שולח כמה עשרות/מאות/אלפי צנחנים טפסנים ומתמקד בסוף על הגבעה הכי גבוהה שמצאת. כמו במקרה האקראי יש פה את פקטור הזמן. אבל לפחות כאן זו תחרות בין מקסימומים. 4. כל מיני שיטות של בינה מלאכותית. יש כל מיני שיטות נוספות לנסות להגיע למקסימום (simulated annealing למשל) אבל אני לא אכנס אליהן. אף-אחת מהן לא עובדת תמיד. 5. אלגוריתם גנטי: גם פה אתה שולח אוכלוסיה של צנחנים. אבל פה הם עושים משהו מוזר. הם מתרבים. קודם כל הם מתרבים בשכפול עצמי עם מוטציות אקראיות. זה עוד הגיוני. ביחד עם ברירה טבעית זה יוביל אותם (את הצאצאים שלהם בכל מקרה) לכיוון הנכון. אבל הם עושים עוד משהו. הם מתרבים מינית. זאת אומרת שצנחן על גבעה אחת וצנחן על גבעה שניה יוצרים צאצא שהוא "איפהשהו" באמצע. זה מבטיח קודם כל בגלל שזה מאפשר לאוכלוסיה לצאת מהגבעות שהיא "תקועה" עליהן. אבל בעצם למה שתהיה שם גבעה? אז בשביל זה המרצה שלי ניג'ס לנו ואני מנג'ס לך על יצוג כל הזמן. במציאות לא מדובר בשני מימדים אלא במאות מימדים. והרעיון הוא שאם היצוג הוא כמו שצריך אז חלק של רעיון טוב למדי שיש לך ביד הוא גם חלק של הרעיון הכי טוב בהסתברות הרבה יותר גבוהה מאשר סתם ניחוש אקראי. ולכן crossover שבו אתה לוקח את הערכים של חלק מהמימדים מהורה אחד, וחלק מההורה השני, אמור בהסתברות לא רעה לשים אותךמ על גבעה שלישית, כי "יש דמיון בין פתרונות טובים". לכן, הרבה מהעבודה באלגוריתם גנטי נועדה לשמור על אוכלוסיה מגוונת (כי אם כולם על אותה גבעה גם כל הצאצאים יהיו עליה) בלי לפגוע יותר מדי בפרטים המוצלחים (כי אחרת גם כשתמצא את הגבעה הנכונה תעוף ממנה). אין לזה פתרון מושלם וזה לא תמיד מצליח. צריך לבחור יצוג טוב, צריך לבחור אופרטורים נכונים, צריך מספיק כוח חישוב ואוכלוסיה גדולה מספיק, צריך להריץ כמה עשרות פעמים (לא יזיק) ואז בשאיפה יוצאת תוצאה "מספיק טובה". זה לא חייב להיות אופטימום. אם אני מצליח באלגוריתם גנטי להביא קירוב יותר טוב לבעית NP-Hard מאשר אלגוריתמי הקירוב המקובלים, זה שווה מאמר. מעבר למה שהזכרתי יש גם שיטות שמשנות את הסביבה. אחת מהם היא "קו-אבולוציה". במקום מין אחד שניים (או יותר). יש קו-אבולוציה קואופרטיבית (כל מין מתמחה בלעשות את העבודה "בהתאמה" עם המין האחר), ויש תחרותית (מפתחים מין של "טפילים" שמציב קשיים הולכים ומתגברים למין של פותרי הבעיות). יש גם שיטות נוספות כמו מוטציה אדפטיבית שהשיעור שלה קטן ככל שמתקדם התהליך. ב-Evolution Strategies שכתבתי עליו קודם נהוג שאופטור המוטציה עובר מוטציה. יש מקרים בהם מנסים לשלוט בעזרת וקטור מיוחד בנקודות ה-"חמות" ל-Crossover (כמובן שגם הוקטורים האלה עוברים ברירה עקיפה מפני שהם עוברים לצאצאים). יש מיליון ורבע שיטות מכל מין וסוג. חלקן פשוטות, חלקן מסובכות; חלקן מקובלות יותר, חלקן איזוטריות. אבל אף-אחת מהן לא מבטיחה הצלחה ואף-אחת לא עובדת תמיד. זה קשה. אם זה היה קל לא היה מה לחקור (לצערי, זה לא בדיוק הנושא שלי. יחסית למה שאני אמור לעבוד עליו זה באמת פשוט. הנושא שלי הוא GP שזה תחום עם כל אותן בעיות ועם עוד כמה מיוחדות משל עצמו).
 

Wolverchenus

New member
אוקיי עכשיו זה הרבה יותר ברור

ממש מעניין,
 
אני אוסיף כמה דברים ל silent mike

למרות שנראה כי הוא מבין קצת יותר ממני בנושא… אני חושב שדוגמה ספציפית תמחיש את העניין יותר טוב. דוגמה לאלגוריתם גנטי, שמשמש בהנדסת תעשייה: הבעיה: במפעל רוצים לייצר מספר רב של מוצרים, על מספר רב של מכונות. לכל מוצר יש זמן עיבוד שונה לכל מכונה. לדוגמה – נעל נייק מדגם 1 צריכה חמש דקות עיבוד במכונה שעושה את הסולייה, שלוש דקות עיבוד במכונה שעושה צ'ופצ'יקים לשרוכים, וכך הלאה. נעל מדגם 2 צריכה זמנים אחרים על כל אחת מהמכונות כי זה דגם אחר. יש נגיד חמישה מכונות, וכל נעל עוברת את כל החמישה באותו הסדר, רק עם זמנים אחרים על כל מכונה. הבעיה היא איך לשבץ את המוצרים למכונות כל שזמן הייצור הכולל יהיה מינימלי – האם כדאי לייצר נעל מדגם 1, אחרי זה דגם 5, דגם 8, או האם כדאי לעשות סדר אחר? לכל סדר יהיה זמן סיום כולל אחר, איך נמצא את הסדר הכי טוב? אז קודם כל – אם היה אפשרות לפתור את הבעיה באופן אופטימלי, מבלי לעבור על כל הסידורים האפשריים (כשיש מאה מוצרים על מאה מכונות זה לוקח למחשב הכי מהיר בעולם יותר ממיליון שנים…), לא היה שום צורך באלגוריתם גנטי. הבעיה הזו שייכת לקבוצת הבעיות שלא ניתן לפתור אותן בצורה כזו. אז נתחיל מעניין הקידוד ש silentmike הזכיר: הקידוד של הבעיה הוא פשוט – נותנים לכל מוצר אות, והקידוד הוא סדר המוצרים. נגיד אם נייצר את מוצר a, אחרי זה מוצר b, ואחרי זה מוצר c, אז הקידוד הוא abc. הקידוד cba ייצג סדר הפוך. השלב הבא הוא יצירת אוכלוסייה ראשונית – יוצרים באקראיות אוכלוסיות ראשוניות של סידורים של מוצרים, למשל: abcd,dbca,cbda,cdab. לאחר מכן צריך לחשב עבור כל פרט באוכלוסייה את הזמן הכולל לייצור כל המוצרים על כל המכונות.( כל קוד כזה הוא פרט). השלב הבא הוא crossover – אני לא אלאה אותכם בפרטים, אבל על פי הזמנים הכוללים יש לכל אחד מהסידורים באוכלוסייה הראשונית סיכוי מסויים להיבחר כהורה. לפתרונות עם זמנים יותר טובים יש יותר סיכוי כמובן. מאוכלוסייה של עשר פרטים, למשל, בוחרים על פי ההסתברויות עשרה זוגות, כל אחד מהם יוצר פרט חדש בזיווג. בשלב הבא, יש הסתברות נמוכה למוטציה עבור כל אחד מהפרטים החדשים באוכלוסייה. לאחר מכן, לוקחים את כל הפרטים, ועושים עוד פעם crossover עם הסתברויות. ככה ממשיכים עד שנמאס לנו... בסופו של דבר האלגוריתם מייצר סידורים שפותרים את הבעיה הזו באופן לא רע בכלל. בהודעות הבאות אני אתן דוגמה ל crossover ומוטציה.
 
דוגמה ל crossover

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

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

SilentMike

New member
מוטציה חזקה.

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

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

SilentMike

New member
כן אני רואה.

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

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

SilentMike

New member
אל תעשה את זה ידנית.

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

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

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