אהלן

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

ה'לב' העיקרי באלגוריתם, הוא בחירת פונקציית הערכה (זו שנותנת ציון לכל קידוד).
ניסיתי מספר פונקציות: 1) מעבר על הטקסט לאחר שהפעלתי עליו את הקידוד שהצעתי וספירה כמה מילים הן 'חוקיות' ומופיעות במילון, 2) להחזיר את אורך המילה - כאשר מצאתי התאמה מושלמת למילה שבמילון. כשלא מצאתי התאמה מושלמת, החזרתי את מספר האותיות המקסימלי התואמות למילה במילון. נניח אם המילה באורך 5 ויש לה התאמה של 4 אותיות למילה בת 5 אותיות במילון, אז החזרתי 4.
זה לצערי לא עובד מספיק טוב.


אני אתן דוגמה:
נניח שהטקסט שקיבלתי הוא: "נחמ יזג".
עבור הקידוד: "מ=נ, ל=מ, ז=ח, ט=י, ו=ז, ב=ג, הטקסט המקורי המתקבל הוא מזל טוב.

מישהו יכול לעזור ?
תודה ~!

ציטוט:

זה לצערי לא עובד מספיק טוב.

איך זה מתבטא..?

תוכל להראות דוגמא כיצד זה עובד לא טוב?

ואם תוכל להראות גם את קוד המקור - יותר טוב

בעיות אפשריות:

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

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

האם אתה ממשיך ליצור קידודים רנדומים תוך כדי התהליך או שאתה מסיים עם הקידודים הראשוניים שבחרת?

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

תנסה בשלב ראשון להפעיל יותר 'לחץ אבולוציוני' - למשל, אל תחזיר את מספר האותיות הנכונות, אלא את מספרן בריבוע (1 עבור אות נכונה אחת, 4 עבור 2 אותיות, 9 עבור 3 וכו'). בצורה כזו, אתה מגביר את ההבדל בין משהו 'טוב' למשהו 'פחות טוב'.
ניסית גם להתייחס לכמה אותיות נכונות יש ברצף? למשל, 3 אותיות ברצף יותר טובות מ-3 אותיות שמופיעות בנפרד. כמו שכבר נאמר באשכול הזה, צריך לנסות הרבה אפשרויות שונות של פונקציית אנרגיה כדי להגיע לתוצאות טובות.
אגב, אתה משתמש גם במוטציות באלגוריתם שלך, או רק בהכלאות?

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

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

הפונקציה שיש לי כרגע (במידה והמילה חוקית ומופיעה במילון - הניקוד עליה שווה לאורכה, במילה ולא - אפס) מסייעת לי להגיע לפתרון המושלם לאחר כ-700 דורות (גודל הדור שלי הוא 100). שזה אומר שאני "מנסה" סה"כ כ-70,000 קידודים אפשריים.

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

הנה עוד מספר רעיונות אפשריים:

1. אתה יכול להעלות את אחוז המוטציות (קח בחשבון שזה יכול גם מאוד להרע ולא לעזור)
2. אם אני מבין נכון, אתה מבצע הכלאה בין 2 הורים בנקודה אחת - משמאל לאותה נקודה אתה לוקח את החלק של ההורה הראשון, מימין לה את ההורה השני. (מה שנקרא ONE-POINT). שווה אולי לנסות TWO-POINT או אפילו N-POINT (ז.א., לחלק את הכרומוזום ליותר משני חלקים בזמן ההכלאה).
3. איך אתה מבצע בחירה של הכרומוזומים להכלאה? רק את הטובים ביותר בכל דור? שווה לנסות לתת לכל כרומוזום הסתברות שהיא מקבילה לתוצאת פונקציית ההערכה ולבחור אותם לפי הסתברויות אלה - ככה תקבל לרוב הכלאות של טובים עם טובים, אבל גם לפעמים טובים עם רעים.
4. לבסוף, קח בחשבון שאופטימום מקומי זה חלק מהעניין. הגדולה של האלגוריתם הגנטי היא היכולת לצאת מזה - גם אם זה לוקח מספר דורות. כמו שאתה בטח יודע, אין הוכחת התכנסות לאלגוריתמים גנטים, ועצם העובדה שזה עובר היא המשמעותית.

לגבי סוג ההכלאה, אתה צודק, אני מבצע הכלאה one-point.
לגבי מי שאני מכליא, איכשהו בהיגיון המעוות (אליטסטי כנראה..) שלי יצרתי 3 סוגי הכלאות: טובים עם עצמם, טובים עם בינוניים וגרועים עם גרועים. בכל סוג הכלאה, אני מגריל מספר בהתאם לציון, באותו תחום שממנו אני מעוניין לבחור כרומוזום להכלאה.
אני לא פוסל אופטימום מקומי, רק מרגיז ומאכזב לראות בקובץ הפלט, שבמשך 30 ואפילו 50 דורות כל פעם, הציון של הפתרון הטוב ביותר לא השתפר כלל...

אחרי שניסיתי לא מעט דברים, כולל הגדלה זמנית של אחוז המוטציות (אפילו כך שיפעלו רק על הפתרונות הפחות טובים) וכל מיני קומבינציות אחרות, אני מבצע כרגע את הדבר הבא: אם זיהיתי מצב בו במשך מספר דורות רצופים הציון הטוב ביותר כמעט ולא השתנה (אני עדיין משחק עם הגדלים מספר_דורות_רצופים ו-אחוז_שיפור) - אני מוסיף עוד 10% פתרונות (גם עם הגודל הזה אני משחק עדיין), שהם תוצרי הכלאה של הטובים עם הגרועים. זה בהחלט מפחית ביותר מחצי את מספר הדורות עד להגעה לפתרון מושלם, אך מספר הפתרונות שאני בודק (סכימה של סה"כ הדורות) - גדל.