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