Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
השם אלגוריתמים גנטיים מתאר משפחה של אלגוריתמים לחיפוש, מידול ומיטוב (אופטימיזציה), שבהם משלבים זה בזה אלמנטים של פתרונות אפשריים לבעיה, ומפעילים הליכים של ברירה מלאכותית כדי לבחור את המועמדים שיעברו לשלבים הבאים. רעיון תכנותי בסיסי זה מושפע מההצלחה של האבולוציה בפתרון בעיות אמיתיות.
יש לשכתב ערך זה. הסיבה היא: ניסוחים לא אנציקלופדיים. | |
בשנות ה-50 וה-60 של המאה ה-20 ניסו מספר מדענים בתחומי המחשב לבחון מערכות אבולוציוניות (התפתחותיות), כאשר הם האמינו שאבולוציה תשמש ככלי לאופטימיזציה של בעיות הנדסיות ומדעיות.[1] הרעיון הכללי אליו כיוונו המדענים הוא לנסות לפתח אוכלוסייה של פתרונות אקראיים לבעיה נתונה, על ידי שימוש באופרטורים שמושפעים משינויים גנטיים טבעיים ובחירה טבעית. התורה עליה התבססו מדענים אלה היא בעצם תורת האבולוציה של דרווין, כלומר פתרון לכל בעיה יעשה בתהליך גנטי על בסיס תורת האבולוציה. בין המדענים החלוצים בתחום האלגוריתמים הגנטיים ניתן למנות את אלכס פרייזר[2] והנס-יואכים ברמרמן[3].
האלגוריתם הגנטי הומצא על ידי ג'ון הנרי הולנד החל משנות ה-60 המוקדמות ואליך במהלך עבודתו באוניברסיטת מישיגן. מטרתו העיקרית של הולנד, בניגוד למדענים אחרים אשר ניסו לכתוב תוכניות אבולוציוניות ונקטו בגישה אבולוציונית למציאת פתרון ספציפי, הייתה להבין בעצם את עקרון האדפטיביות כפי שהוא בא לידי ביטוי בטבע, כלומר יכולת ההסתגלות לתנאים משתנים. הולנד ניסה לייבא תכונות אלה של אדפטיביות לתוך מערכות ממוחשבות.
אלגוריתמים גנטיים משמשים בעיקר כדי לפתור בעיות אופטימיזציה שלא ידוע עבורן פתרון דטרמיניסטי או הסתברותי העובד בזמן סביר.
העיקרון של אלגוריתם גנטי הוא שכמו כל יצור בטבע רק המתאימים שורדים. הבעיה שעימה כל זן צריך להתמודד היא התאמה לסביבה והשינויים שחלים בה. שילוב אלמנטים של פתרונות אפשריים לבעיה, הפעלת הליכים של ברירה מלאכותית כדי לבחור את המועמדים שיעברו לשלבים הבאים. רעיון תכנותי בסיסי זה מושפע מההצלחה של האבולוציה בפתרון בעיות אמיתיות. לכן אם ניקח אוכלוסייה של פתרונות ונבחר מתוכם רק את המתאימים ביותר לפתרון בעיה, נערבב אותם אחד עם השני ונוסיף קצת רעש, נקבל דור חדש של פתרונות הקרוב צעד נוסף לפתרון הבעיה הנתונה. נחזור על התהליך מספר רב של פעמים (דורות) ולבסוף נגיע לפתרון הקרוב ביותר.
ייצוג בינארי של שני כרומוזומים
1101111000011110
1101100100110110
כל ביט במחרוזת מייצג אופין מסוים של הפתרון. אפשרות נוספת היא שכל מחרוזת תיוצג על ידי מספר. קיימים דרכים רבות לייצוג, הייצוג תלוי בעיקר בפתרון הבעיה.
במודל תכנותי זה יוצרים קהילה של פרטים אשר מאופיינים בכרומוזומים, ומעבירים אותם "תהליך אבולוציוני". האלגוריתם עוסק במעבר בין אוכלוסייה של כרומוזומים (רצף של סיביות 0 ו-1 ) לרצף חדש של סיביות ("אוכלוסייה חדשה") על ידי שימוש בבחירה הטבעית ואופרטורים כמו crossover. לאחר יצירת קהילת הפרטים הראשונה, מדרגים כל פרט על מנת למצוא את הפרטים הטובים ביותר. לאחר מכן, עורכים מיזוג (זיווג) בין פרטים אלה על מנת ליצור קהילה חדשה, טובה במקצת מקודמתה, ומעבירים אותה את אותו התהליך. ההנחה כאן היא שמיזוג בין שני פתרונות טובים לבעיה עשוי להניב פתרון טוב יותר. כמו בגנטיקה ביולוגית, שני הורים בעלי סט גנים טובים יוצרים צאצא שגם הוא עליון מבחינה גנטית. לאחר מספר חזרות על הפעולה, הפרטים ישתפרו דרמטית ויציגו את הפתרון הטוב ביותר, או פתרון טוב באופן יחסי לבעיה הנתונה.
בכתיבת אלגוריתם גנטי יש לממש:
כשם שבתורת האבולוציה של דרווין ישנו שימוש ניכר במוטציות ובשינויים גנטיים, גם במודל תכנותי זה יש חשיבות רבה למוטציות הגנטיות. בכל זיווג של 2 פרטים ניתן לשלב "שגיאות" אקראיות שיאפשרו יצירה של מידע חדש, שאותו אין לאף פריט אחר באוכלוסייה (קהילה) הנוכחית. אם שגיאה זו תוכר כהצלחה, הפריט ימוזג שוב, ולכן ה"שגיאה" תמשיך להתקיים; אם לא, היא תיעלם כלא הייתה. הסיבה לשימוש במוטציות כחלק מהאלגוריתם הגנטי הוא שישנה סכנה שאוכלוסיית הפתרונות תקלע למינימום מקומי במרחב הפתרון. השימוש במוטציות נותן אפשרות לצאת ממינימום מקומי ובכך להגיע לפתרון טוב יותר לבעיה.
מטרת פונקציית ההערכה היא להגדיר סדר על הפרטים. ההערכה מאפשרת לבחור את הפרטים המוצלחים ביותר מתוך הקהילה. לעיתים ההערכה תתבסס על פונקציה פשוטה המקבלת מספר פרמטרים ומחזירה דירוג (כאשר הבעיה היא דטרמיניסטית), ולעיתים תמומש סימולציה מלאה של חיי הפרט בתוך הקהילה (כאשר הבעיה היא סטוכסטית).
אלגוריתמים גנטיים שייכים לקבוצה גדולה של אלגוריתמי חיפוש ואופטימיזציה. כיום הם נחשבים על פי רוב למוצלחים פחות מאלגוריתמים המבוססים על טיפוס בהר. עם זאת אלגוריתמים גנטיים מתאימים לבעיות של בחירת תתי-קבוצות אופטימליות (subset-selection), וכן לבעיות של מציאת מערכת שעות ולוחות זמנים.
כלכלה- באלגוריתם הגנטי עושים שימוש עבור יצירות מודלים של תהליכי חדשנות, אסטרטגיה של מיקוח, חדשנות והתמתחות שווקים כלכליים.
אקולוגיה- נעשה שימוש באלגוריתמיקה גנטית לשם הגעה למודלים של תופעות אקולוגיות.
בראייה מתמטית, אלגוריתם גנטי מאפשר למצוא נקודות קיצון של פונקציה ב-n משתנים.
תהי פונקציית הכשירות, בה רוצים למצוא נקודות קיצון גלובליות, אזי:
אלגוריתמים קו-אבולוציוניים (Co-evolutionary Algorithms) הם תת-משפחה של אלגוריתמים גנטיים שבם פונקציית הכשירות נקבעת על פי יחס בין אוכלוסיות ולא אבסולוטית, קרי, טיב פתרון מאוכלוסיית פתרונות אחת נקבע ביחס כלשהו לאינטראקציה שלו עם קבוצת פתרונות של אוכלוסייה אחרת שמשתתפת באלגוריתם. היחס המדובר יכול להיות שיתופי (כל אוכלוסייה מייצגת חלק מן הפתרון הכולל לבעיה) או תחרותי (כל אוכלוסייה מיצגת חלק אחר של הבעיה, או מתחרה על פתרונות לבעיה).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.