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

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

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

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

מה ההבדל בין תכנות גנטי לבין אלגוריתם גנטי?

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

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

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

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

עקרונות פעולה ודרישות אלגוריתמיות

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

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

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

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

מה הפורמליזם המתמטי של תכנות גנטי?

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

הקבוצה הראשונה היא קבוצת הפונקציות

F = {f₁, f₂, ..., fₙ}

כאשר לכל פונקציה fᵢ יש ערכיות מוגדרת aᵢ המייצגת את מספר הארגומנטים שהיא מקבלת.

הקבוצה השנייה היא קבוצת הטרמינלים

T = {t₁, t₂, ..., tₘ}

שכוללת משתנים וקבועים שמהווים את עלי העץ.

מרחב כל התוכניות האפשריות, שמסומן ב-S, מוגדר רקורסיבית כך ש-

כל איבר ב-T שייך ל-S,

ואם f ∈ F וגם s₁, ..., sₐ ∈ S,

אז f(s₁, ..., sₐ) שייך ל-S.

כדי להעריך את איכות הפתרונות, מוגדרת פונקציית כשירות שמסומנת כ-Φ. פונקציה זו ממפה כל תוכנית s מתוך המרחב S לערך מספרי בשדה המספרים הממשיים ℝ, כלומר Φ: S → ℝ.

המטרה המתמטית היא למצוא תוכנית אופטימלית s* מתוך S כך שערך הכשירות שלה יהיה מקסימלי או מינימלי, בהתאם להגדרת הבעיה. במקרים רבים מוסיפים פונקציית עונש על מורכבות העץ כדי למנוע תופעה של ניפוח, שמוגדרת לרוב כפונקציה של מספר הצמתים בעץ, נסמנו כ-size(s).

הדינמיקה של האבולוציה מתוארת באמצעות אופרטורים הסתברותיים שמופעלים על אוכלוסיית התוכניות P בכל דור t. אופרטור הברירה בוחר תוכנית s מתוך P(t) בהסתברות p(s) היחסית לערך הכשירות Φ(s). אופרטור ההכלאה מבצע החלפה של תתי-עצים בין שני הורים ליצירת צאצאים חדשים, ואופרטור המוטציה מבצע שינוי אקראי בצומת מסוים. מבחינה תיאורטית, ניתוח ההתכנסות של התהליך מתבצע לעיתים באמצעות גרסה מותאמת של מִשְׁפַּט הַסְּכֵמָה, שבוחן את תוחלת מספר המופעים של תבניות קוד מוצלחות בדור הבא.

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

הפורמליזם המתמטי של אלגוריתם גנטי מתחיל בהגדרת מרחב החיפוש Ω שכולל את כל הפתרונות האפשריים לבעיה נתונה. כל פתרון אינדיבידואלי במרחב זה מיוצג בדרך כלל כווקטור x ששייך לקבוצה X, כאשר X היא קבוצת כל המחרוזות באורך קבוע L מעל אלפבית סופי Σ. ברוב המקרים האלפבית הוא בינארי כך ש-Σ = {0, 1} ומרחב הייצוג הוא X = {0, 1}ᴸ. פונקציית הכשירות f ממפה כל אינדיבידואל x מהמרחב X אל שדה המספרים הממשיים ℝ, כך שמתקיים f: X → ℝ. המטרה המתמטית היא למצוא אינדיבידואל x* ששייך ל-X שעבורו f(x*) הוא ערך קיצון.

הדינמיקה של האלגוריתם פועלת על אוכלוסייה P המוגדרת כרב-קבוצה של N אינדיבידואלים בדור t, ונסמנה P(t) = {x₁, x₂, ..., xₙ}. תהליך הבחירה של פרטים להתרבות מתבצע לפי התפלגות הסתברותית p שמבוססת על ערכי הכשירות של הפרטים באוכלוסייה. בשיטת הבחירה היחסית, ההסתברות pᵢ לבחירת פרט xᵢ מוגדרת כחלקו היחסי בערך הכשירות הכללי של האוכלוסייה, כלומר pᵢ = f(xᵢ) / ∑ f(xⱼ) עבור j מ-1 עד N.

לאחר הבחירה מופעלים אופרטורים וריאציוניים שהם אופרטור ההכלאה ואופרטור המוטציה. אופרטור ההכלאה מבצע פעולה סטוכסטית על שני פרטים ליצירת צאצאים חדשים, בעוד שאופרטור המוטציה מוגדר כפונקציה הסתברותית m: X → X שמשנה כל רכיב בווקטור x בהסתברות pₘ. הניתוח המתמטי של התפתחות האוכלוסייה לאורך זמן נעשה לעיתים קרובות באמצעות משפט הסכמה שמגדיר תבנית H מעל האלפבית {0, 1, *}. המשפט קובע שתוחלת מספר המופעים של סכמה H בדור הבא מקיימת אי שוויון שתלוי בכשירות הממוצעת של הסכמה ביחס לכשירות הממוצעת של כלל האוכלוסייה ובהסתברות להפרעת הסכמה על ידי האופרטורים.

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

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

דברו איתי:

שלמה יונה

מייסד ומדען ראשי, מתמטיקאי מחקר ופיתוח בע"מ

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

פודקאסט על החברה ועליי, שלמה יונה, ואופן העבודה שלנו ואיתנו: A technical deep dive about