אלגוריתם גנטי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הוספתי היסטוריה לנושא וכן תיאור מפורט יותר לטובת הכלל.. |
|||
שורה 1:
השם '''אלגוריתמים גנטיים''' מתאר משפחה של [[אלגוריתם|אלגוריתמים]] לחיפוש ו[[אופטימיזציה (מתמטיקה)|מיטוב]] (אופטימיזציה), שבהם משלבים זה בזה אלמנטים של פתרונות אפשריים לבעיה, ומפעילים הליכים של [[ברירה מלאכותית]] כדי לבחור את המועמדים שיעברו לשלבים הבאים. רעיון [[תכנות]]י בסיסי זה מושפע מההצלחה של ה[[תורת האבולוציה|אבולוציה]] בפתרון בעיות אמיתיות.
== היסטוריה ==
בשנות ה50 וה60 ניסו מספר מדענים בתחומי המחשב לבחון מערכות אבולוציוניות (התפתחותיות), כאשר הם האמינו שאבולוציה תשמש ככלי לאופטימיזציה של בעיות הנדסיות ומדעיות. הרעיון הכללי אליו כיוונו המדענים הוא לנסות לפתח אוכלוסיה של פתרונות אקראיים לבעיה נתונה, ע"י שימוש באופרטורים שמושפעים משינויים גנטיים טבעיים ובחירה טבעית. התורה עליה התבססו מדענים אלה היא בעצם תורת האבולוציה של דרווין, כלומר פתרון לכל בעיה יעשה בתהליך גנטי על בסיס תורת האבולוציה.
האלגוריתם הגנטי הומצא ע"י ג'ון הנרי הולנד החל משנות ה-60 המוקדמות ואליך במהלך עבודתו ב University of Mishigan . מטרתו העיקרית של הולנד, בניגוד למדענים אחרים אשר ניסו לכתוב תוכניות אבולציוניות ונקטו בגישה אבולוציונית למציאת פתרון ספציפי, הייתה להבין בעצם את עקרון האדפטיביות כפי שהוא בא לידי ביטוי בטבע, כלומר יכולת ההסתגלות לתנאים משתנים.
הולנד ניסה בעצם לייבא תכונות אלה של אדפטיביות לתוך מערכות ממוחשבות.
== מתודולוגיה ==
אלגוריתמים גנטיים משמשים בעיקר
כדי לפתור בעיות אופטימיזציה שלא ידוע עבורן פתרון דטרמיניסטי או הסתברותי העובד
בזמן סביר.
אלגוריתמים גנטיים הינם משפחה
של מודלים חישוביים בהשראת האבולוציה, אלגוריתמים המיועדים לחיפוש ומיטוב במטרה למצוא את הפתרון האופטימלי.
העיקרון של <strong>אלגוריתם גנטי</strong>
הינו פשוט מאוד – כמו כל יצור בטבע רק המתאימים שורדים. הבעיה שעימה כל זן צריך להתמודד היא התאמה לסביבה והשינויים שחלים בה. שילוב אלמנטים של פתרונות אפשריים לבעיה, הפעלת הליכים שלברירה מלאכותית בכדי לבחור את המועמדים שיעברו לשלבים הבאים. רעיון תכנותי בסיסי זה מושפע מההצלחה של האבולוציה בפתרון בעיות אמתיות.
<nowiki> </nowiki>לכן אם ניקח אוכלוסייה של פתרונות ונבחר מתוכם רק את המתאימים ביותר לפתרון בעיה,
<nowiki> </nowiki>נערבב אותם אחד עם השני ונוסיף קצת רעש, נקבל דור חדש של פתרונות הקרוב צעד נוסף לפתרון הבעיה הנתונה. נחזור על התהליך מספר רב של פעמים (דורות) ולבסוף נגיע לפתרון הקרוב ביותר.
קל לזכור את העיקרון המנחה את האבולוציה בכלל ואת האלגוריתם הגנטי בפרט באופן הבא:
1. הטוב – לכל זוג פרטים יש את היכולת לייצר צאצא ולהעביר לו את המטען הגנטי שלהם.
2. הרע – רק המתאימים ביותר שורדים ע"י העלאת סיכויי ההתרבות שלהם.
3. המכוער – יש צאצאים עם מוטציות.
ייצוג בינארי של שני
כרומוזומים
1101111000011110
1101100100110110
כל ביט במחרוזת מייצג אופין מסויים של הפתרון. אפשרות נוספת היא שכל מחרוזת תיוצג ע"י מספר. קיימים דרכים רבות לייצוג, הייצוג תלוי בעיקר בפתרון הבעיה.
במודל תכנותי זה יוצרים קהילה של פרטים אשר מאופיינים בכרומוזומים, ומעבירים אותם "תהליך אבולוציוני".האלוגריתם עוסק במעבר בין אוכלוסיה של כרומוזומים (רצף של סיביות 0 ו-1 ) לרצף חדש של סיביות ("אוכלוסיה חדשה") ע"י שימוש בבחירה הטבעית ואופרטורים כמו crossover. לאחר יצירת קהילת הפרטים הראשונה, מדרגים כל פרט על מנת למצוא את הפרטים הטובים ביותר. לאחר מכן, עורכים מיזוג (זיווג) בין פרטים אלה על מנת ליצור קהילה חדשה, טובה במקצת מקודמתה, ומעבירים אותה את אותו התהליך. ההנחה כאן היא שמיזוג בין שני פתרונות טובים לבעיה עשוי להניב פתרון טוב יותר. כמו בגנטיקה ביולוגית, שני הורים בעלי סט גנים טובים יוצרים צאצא שגם הוא עליון מבחינה גנטית. לאחר מספר חזרות על הפעולה, הפרטים ישתפרו דרמטית ויציגו את הפתרון הטוב ביותר, או פתרון טוב באופן יחסי לבעיה הנתונה.
בכתיבת אלגוריתם גנטי יש לממש:
* · '''זיווג''' crossover של שני פרטים שמחזיר שני צאצאים או יותר. הצאצאים נושאים מטען גנטי שהוא שילוב של הפרטים שזווגו. פועל על גנים נבחרים מהכרומוזומים של ההורים ויוצר צאצא חדש. הדרך
הפשוטה ביותר לביצוע היא לבחור באופן אקראי נקודה לזיווג, להעתיק את כל הביטים שלפני הנקודה מהורה אחד ולהעתיק את כל הביטים שאחרי הנקודה מההורה השני.
אם crossover לא מבוצע למעשה הצאצא יהיה העתק מושלם של ההורים. הפעולה מבוצעת במטרה להכיל את החלקים הטובים של הכרומוזומים הישנים ולכן הכרומוזומים החדשים יהיו טובים יותר. למרות זאת, חשוב להשאיר חלק של האוכלוסיה הישנה לדור הבא.
* · '''מוטציה''' Mutation על פרט בודד שמשנה את התכונות שלו. המטרה היא לבצע שינוי בהעתקות שנוצרו ע"י הזיווג, זאת בכדי למנוע חזרה של חלקים שלמים במחרוזת הביטים. אם לא נבצע את פעולת המוטציה הצאצא יווצר מידית לאחר פעולת הזיווג או שיועתק ישר מההורים ללא כל שינוי. כאשר מבצעים מוטציה חלק אחד או יותר מהכרומוזומים משתנים. מוטציות מתרחשות לרוב בהסתברות נמוכה כלשהי (בין 0.1% ל-0.01%) וזאת מכיוון שאם ההסתברות תיהיה גבוהה האלוגריתם הגנטי יהפוך להיות אלוגריתם של חיפוש אקראי (האלוגריתם יצא משליטה).
* · '''שיערוך''' (Evaluation) בו בוחרים את הפרטים שישתתפו בתהליך הזיווג לפי רמת התאמה, בעזרת "פונקציית כשירות" (fitness function). לפונקצית השערוך יש מרכיבים רבים שיכולים להחליש או לחזק את ביצועי האלגוריתם הגנטי. ביצועי האלגוריתם הגנטי רגיש מאוד לטכניקה של תהליך הנרמול, כך למשל אם נ דרוש שיפור יתר הדבר יכול
להוביל לקבלת חומר גנטי אלטרנטיבי באוכלוסיה ויקדם שליטה של צאצא יחיד. כאשר דבר כזה קורה לפעולת ה crossover אין השפעה והאלוגריתם מרכז את מירב החיפושים אחר הפתרון הנדרש סביב הכרומוזום הטוב האחרון שמצא. לעומת זאת אם תהליך הנרמול לא יפעל כראוי האלגוריתם
יכשל במציאת פתרון בזמן סביר וקרוב לודאי שפתרונות טובים מקרב האוכלוסייה יאבדו.
מאפיין חשוב נוסף של פונקצית השערוך הוא החוזק והחולשה של האלגוריתם הגנטי. ביישום האלגוריתם בדרך כלל לוקחים ערך יחיד שחוזר ע"י פונקית השערוך ומשתמש בערך כדי לקבוע התאמה יעילה.
בקביעת פונקצית השערוך
יש להתייחס לאילוצים של היישומים.
=== אלגוריתם (פסאודו-קוד) ===
שורה 33 ⟵ 74:
אלגוריתמים גנטיים שייכים לקבוצה גדולה של אלגוריתמי חיפוש ואופטימיזציה. כיום הם נחשבים על פי רוב למוצלחים פחות מאלגוריתמים המבוססים על [[טיפוס בהר]]. עם זאת אלגוריתמים גנטיים מתאימים לבעיות של בחירת תתי-קבוצות אופטימליות (subset-selection), וכן לבעיות של מציאת מערכת שעות ולוחות זמנים.
כלכלה- באלגוריתם הגנטי עושים שימוש עבור יצירות מודלים של תהליכי חדשנות, אסטרטגיה של מיקוח,חדשנות והתמתחות שווקים כלכליים.
אקולוגיה- עושים שימוש שם בהגעה למודלים של תופעות אקולוגיות.
== ניסוח מתמטי ==
בראייה מתמטית, אלגוריתם גנטי מאפשר למצוא [[נקודת קיצון|נקודות קיצון]] של פונקציה <math>\ f</math> ב-n משתנים.
| |||