נגישות       נגישות
שינוי גודל טקסט:
א א א
שינוי צבעי האתר:
? מקשי קיצור:

לחיצה חוזרת ונשנית על המקש Tab תעביר אתכם בין הקישורים והאזורים השונים בעמוד.

הפעלת מקשי הקיצור תלויה בדפדפן שבו אתם משתמשים.

Internet Explorer, Chrome ובגרסאות ישנות של Firefox: לחצו על מקש Alt ועל מקש המספר או האות על-פי הרשימה. ב Firefox 3 ומעלה: לחצו על המקשים Alt + Shift + המספר או האות.

S - עבור לתוכן הדף
L - חיפוש
1- עמוד הבית
2 - פרוייקטים
3 - מדריכים
4 - אודות
5 - צרו קשר
6 - הצהרת נגישות
 

תכנות אתרים ומדריכים

שימוש באלגוריתם גנטי להתמודדות עם בעיה חישובית קשה במיוחד ממחלקת NP

21.12.2023 | מדריך למידת מכונה | יוסי בן הרוש

אין דבר מהנה יותר ממציאת פתרון אלגנטי לבעיות תכנותיות. במיוחד אם הם קשות ומסובכות ופתרונם מצריך מאמץ רב. אולם קיימות בעיות תכנותיות שהם כל כך מורכבות עד שגם המחשבים החזקים ביותר מתקשים למצוא להם פתרונות בזמן סביר. בעיות אלו שייכות למחלקה NP - בעיות שאין להם פתרון דטרמיניסטי בזמן פולינומי. דוגמה לבעיה מסוג NP היא בעיית התרמיל 0/1 - אשר נחשבת לאתגר אופטימיזציה קלאסי. הבעיה דורשת למקסם את הערך הכולל תחת מגבלות משקל, והיא הולכת ומסתבכת ככל שגדל מספר הפריטים. הסיבוכיות נובעת מכך שככל שגדל מספר הפריטים אותם ניתן לבחור להכניס לתרמיל, גדל מספר השילובים האפשריים באופן אקספוננציאלי כיוון שכל פריט מוסיף שתי אפשרויות (להכניס או להוציא), מה שמוביל ל-2^n שילובים פוטנציאליים עבור n פריטים. מורכבות אקספוננציאלית זו מאפיינת בעיות רבות השייכות למחלקה NP. כיוון שפתרון מיטבי של מקרים מרובי פריטים של בעיית התרמיל לא קיים למעשה, מומחי התכנות פונים לשימוש באלגוריתמים מקורבים שאף שאינם מבטיחים פתרונות מיטביים, הם כן מצליחים לספק תוצאות טובות למדי במסגרת טווחי זמן סבירים. דוגמה אחת היא שימוש באלגוריתם גנטי לצורך מציאת פתרונות מקורבים לבעיה. אלגוריתמים גנטיים, אשר שואבים השראה מתחומי האבולוציה והגנטיקה, עושים שימוש במנגנונים של ברירה, שחלוף, ומוטציה כדי לאפשר לאוכלוסייה של פתרונות פוטנציאליים להתפתח לאורך דורות. בעוד שפתרון האופטימלי אינו מובטח, אלגוריתמים אילה חוקרים ביעילות מרחבי פתרונות עצומים. היישום במדריך של האלגוריתם הגנטי לבעיית התרמיל מדמה את האבולוציה של אוכלוסיות. הוא משלב אסטרטגיות כגון יצירה ושמירה על שונות, ברירת פרטים לפי מידת כשירות, יישום של שחלוף לצירוף חומר גנטי, והכנסת מוטציות לשיפור השונות. אסטרטגיות אילו, בדומה לתהליכים טבעיים, מנווטות במרחב החיפוש, ומתכנסות לפתרונות העומדים בדרישות הבעיה או לפחות מתקרבות לפתרון אופטימלי. שיפורים נוספים, הכוללים אליטיזם והתאמה דינמית של שיעורי השחלוף, נועדו לשפר את ביצועי האלגוריתם. בנוסף, המדריך ידגים קריטריוני התכנסות כדי לקבוע מתי האלגוריתם הגנטי צריך לסיים לחקור עקב תשואה פוחתת של השיפור במידת הכשירות במעבר בין הדורות.

שימוש באלגוריתם גנטי להתמודדות עם בעיה חישובית קשה במיוחד ממחלקת NP

יש לי חור בלב בצורה שלך ישראל האהובה