יישום אלגוריתם הטיפוס של ההר ב-Python

Python

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

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

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

מהו אלגוריתם טיפוס עלייה בסלע ב- AI?

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

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

הנה איך זה עובד בצעדים פשוטים:

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

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

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

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

סוגי אלגוריתמי טיפוס ההר

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

1. טיפוס ההר פשוט

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

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

2. עליית גבעה בשיפוע הכי תלול

גרסה זו היא יותר מעמיקה מאשר עליית גבעה פשוטה:

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

3. טיפוס לגבה סטוכסטי

סוג זה מוסיף מעט רעננות כדי לשדרג את החיפוש:

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

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

איך פועל אלגוריתם טיפוס הר עולה

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

1. התחלה

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

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

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

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

2. הסתכלות על פתרונות קרובים

כאשר האלגוריתם מתחיל את חיפושו, הוא מעריך פתרונות שסמוכים לעמדת הנוכחית. תארו לעצמכם את זה כאילו מבצעים חקירה בסביבת הסביבה בצעדים קטנים. לדוגמה, אם אתם מנסים למקסם מסלול משלוח בין ערים, והמסלול הנוכחי שלכם הוא [A -> B -> C -> D], האלגוריתם יבחן מסלולים דומים כמו [A -> B -> D -> C] או [A -> C -> B -> D] על מנת לראות האם הם מפחיתים את המרחק הכולל שנסע. כל שינוי קטן במסלול מייצג פתרון "שכן" שייתכן שיהיה יותר טוב מהנוכחי.

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

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

אז אם מסלול X נוסע 100 מייל ומסלול Z נוסע 90 מייל, מסלול B יהיה לו ציון טוב יותר (נמוך). האלגוריתם ידע להמשיך בכיוון של פתרונות דומים למסלול B. הפונקציה המטרה בעצם מהפכת את הבעיה המורכבת של אופטימיזצית מסלול למספר פשוט שניתן להשוות ולמזער.

3. בחירת הצעד הבא

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

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

4. לדעת מתי לעצור

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

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

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

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

יתרונות ומגבלות של טיפוס הגבעה בבינה מלאכותית

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

יתרונות

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

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

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

הגבלות

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

1. תקוע על גבעולות קטנים

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

2. בעיה של קרקע שטוחה

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

3. בעיה של סניפון

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

4. הנקודת ההתחלה חשובה מאוד

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

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

אסטרטגיות לגבור על המגבלות

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

טיפוס גבעות באמצעות הפעלה מחדש אקראית

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

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

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

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

קירור מדומה

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

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

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

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

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

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

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

יישום אלגוריתם טיפוסי על סלע פשוט בפייתון

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

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

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

כאשר בונים תיק תעריפים, עלינו להבין שלוש דברים עיקריים:

כמה כסף אנו מצפים להרוויח (תשואה מצופה)
כמה סיכונים יש בהשקעות (סיכון בתיק ההשקעות)
האם הרווחים הפוטנציאליים שווים את הסיכון (התאמת תשואה לסיכון)

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

כדי למצוא תיק ייעודי טוב באמצעות טכניקת "טיפוס על הגבעה", נעשה את הבא:

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

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

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

def objective_function(state):
   """
   Portfolio optimization objective function that maximizes expected returns while minimizing risk.
   The state represents portfolio weights for different assets.

   Args:
       state (list): List of portfolio weights for different assets (should sum to 1)

   Returns:
       float: Portfolio score combining returns and risk
   """
   # תשואות שנתיות צפויות עבור נכסים (ערכים מדגם)
   expected_returns = [0.1, 0.12, 0.18, 0.1, 0.15]  # 8%, 12%, וכו'

   # סיכון (וולטיליות) עבור כל נכס
   volatilities = [0.1, 0.2, 0.3, 0.2, 0.2]  # 10%, 20%, וכו'

   # לאימות אורך הקלט תואם לתשואות צפויות/וולטיליות
   if len(state) != len(expected_returns):
       return float("-inf")  # להחזיר ציון גרוע ביותר עבור מצבים לא תקינים

   # לחשב את התשואה הצפויה של תיק השקעות
   portfolio_return = sum(w * r for w, r in zip(state, expected_returns))

   # לחשב את הסיכון של תיק השקעות (מפושט, לא באמצעות מטריצת קוברנסיה)
   portfolio_risk = sum(w * v for w, v in zip(state, volatilities))

   # להעניש אם המשקלות אינן סוכמות ל-1 (תיק שקע לא תקין)
   weight_sum_penalty = abs(sum(state) - 1) * 100

   # להעניש משקלות שליליים (אין מכירה קצרה)
   negative_weight_penalty = sum(abs(min(0, w)) for w in state) * 100

   # לשלב בין תשואה וסיכון עם גורם אי-ניאות של 2
   # ציון גבוה יותר הוא טוב יותר: למקסם תשואה, למזער סיכון והענשים
   score = (
       portfolio_return
       - 2 * portfolio_risk
       - weight_sum_penalty
       - negative_weight_penalty
   )

   return score

הַפּוּנְקְצִיָה objective_function לְעִיל עוֹזֶרֶת לָנוּ לְהַעֲרִיך כֵּיצַד נָכוֹן פּוֹרְטְפּוֹלְיוֹ לִינָוּחַ מַסָּוֵי. בואו נִפְרַט כֵּיצַד זֶה עוֹבֵד:

רִאשׁוֹן, הִיא לוֹקַחַת רְשִׁימָה שֶׁל מִסְפָּרִים שֶׁמַּיְצִגִים אֶת אֲחֻזַּת הַכֶּסֶף שֶׁאָנוּ רוֹצִים לְהַשְקִיע בְּנִכְסִים שׁוֹנִים (כְּגוֹן מַנְיָעוּת אוֹ אִגוּדִים). לְדֵי־דוּגְמָא, אִם יֵשׁ לָנוּ חֲמִישָׁה נִכְסִים, אוֹתָם נַשְׁקִיע בְּ-20% בַּכָּל אֶחָד.

הַפּוֹנְקְצִיָה מַשְׁתִּמָּשֶׁת בִּשְׁתֵּי פְּרָטִים מַרְכְּזִיִּים:

הַהַחֲזָרִים הַצְפוּיִים: כַּמָּה כֶּסֶף אֲנַחְנוּ מְצַפְּיִים לְהַרוֹת מֵאִגוּד מְנָיָע (כְּמוֹ 8% אוֹ 12% לְשָׁנָה)
הַנְפָּילוּת: כַּמָּה סַכִּין כָּל אִגוּד הוּא – מַסְפֵּרִים גְּבוֹהִים מַשְׁמַעוּיִים שֶהַתְּמוּנָה שֶּׁל הַנֶכֶס מַשְׁתַּנֶה בְּאוֹפֶן יוֹתֵר שֶׁאֵין אוֹתוֹ (כְּמוֹ בִּטְקוֹ)

הַפּוֹנְקְצִיָה אָז:

יוֹצֵר אֶת סְכוּם הַהַחֲזָרִים הַצְפוּיִים שֶל פּוֹרְטְפּוֹלְיוֹ שֶלָּנוּ עַל יְדֵי כְּפִילַת הַהַחֲזָר הַצְפוּי שֶל כָּל אִגוּד בְּכַמָּה שֶהַשְקַעְנוּ בוֹ
מְבַקֵּר בַּסְּכוּם הַסִּיכּוּן עַל יְדֵי הַסְתָּכֵלוֹת בְּנֶפֶלַת כָּל אִגוּד
בוֹדֵק שֶׁהַאֲחֻזוֹת שֶׁלָּנוּ מוֹצְרוֹת לְ-100% (הֵן צָרִיכוֹת לְהַצְטַרֵף!)
וּמַבֵּן שֶׁאֵינוֹ מְנַסֶּה לִמְכּוֹר אִגוּדִים שֶׁאֵינּוּ בַעַל (אֵין נְגָטִיבִי סְהֵ״נ)

לבָּסוֹף, הִיא מֵצִיבָה אֶת כָּל הַמֵּידָע הַזֶּה לְתוֹך צּוּרָה אֶחָת. צַּיֵּד גָּבוֹה פּוֹרְטְפּוֹלְיוֹ. הַצַּיֵּד עוֹלֶה עִם הַהַחֲזָרִים הַגְּבוֹהִים אַךְ יוֹרֵד עִם הַסִּיכּוּן הַגָּבוֹהִי. הוּא גַּם נִפְגַּע הַרְבֵּה יוֹתֵר אִם הַאֲחֻזוֹת שֶׁלָּנוּ אֵינָן סוֹכְמוֹת לְ-100% או אִם אֲנַחְנוּ מְנַסִּים לִשְׁמוֹשׁ אֲחֻזוֹת שֶׁלָּנוּ.

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

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

def get_neighbors(state):
   """
   Generates neighboring states by making small adjustments to portfolio weights

   Args:
       state (list): Current portfolio weights

   Returns:
       list: List of neighboring portfolio weight configurations
   """
   neighbors = []
   step_size = 0.01  # עריכה קטנה במשקלים (1%)

   for i in range(len(state)):
       for j in range(len(state)):
           if i != j:
               # העברת משקל מנכס i לנכס j
               neighbor = state.copy()
               if neighbor[i] >= step_size:  # העברה רק אם קיימת מספיק משקל זמין
                   neighbor[i] -= step_size
                   neighbor[j] += step_size
                   neighbors.append(neighbor)

   return neighbors

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

עבור כל זוג נכסים בתיק שלנו, היא יוצרת הקצאת תיק חדשה על ידי העברת כמות קטנה (1%) מנכס אחד לנכס אחר. לדוגמה, אם יש לנו חמישה נכסים, היא תנסה:

העברת 1% מנכס 1 לנכס 2
העברת 1% מנכס 1 לנכס 3
העברת 1% מנכס 1 לנכס 4
העברת 1% מנכס 1 לנכס 5
העברת 1% מנכס 2 לנכס 1 וכן הלאה עבור כל הזוגות האפשריים.

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

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

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

כעת, בואו נממש סופסוף אלגוריתם עם עיקרון טיפוס קטן:

def simple_hill_climbing(initial_state, max_iterations=1000):
   """
   Implements Simple Hill Climbing algorithm
  
   Args:
       initial_state (list): Starting point for the algorithm
       max_iterations (int): Maximum number of iterations to prevent infinite loops
  
   Returns:
       tuple: (best_state, best_value) found by the algorithm
   """
   current_state = initial_state
   current_value = objective_function(current_state)
  
   for _ in range(max_iterations):
       # קבל שכנים
       neighbors = get_neighbors(current_state)
      
       # דגל לבדיקה האם מצאנו שכן טוב יותר
       found_better = False
      
       # בדוק אחר שכנים אחד אחרי השני (טיפוס קטן)
       for neighbor in neighbors:
           neighbor_value = objective_function(neighbor)
          
           # אם מצאנו שכן טוב יותר, זוז אליו מיידית
           if neighbor_value > current_value:
               current_state = neighbor
               current_value = neighbor_value
               found_better = True
               break
      
       # אם לא מצאנו שכן טוב יותר, הגענו לפסגה
       if not found_better:
           break
  
   return current_state, current_value

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

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

initial_state: נקודת התחלה לאופטימיזציה, מיוצגת כרשימת ערכים
max_iterations: פרמטר בטיחות כדי למנוע לולאות אינסופיות, ברירת מחדל ל-1000 איטרציות

האלגוריתם עובד כדלקמן:

הוא מתחיל ב-initial_state ומחשב את ערך הפונקציה המטרה שלו
בכל איטרציה, זה:

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

הפונקציה מחזירה טייפל הכולל:

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

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

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

בואו לבדוק אותו על תיק דוגמה:

# שימוש דוגמתי
initial_state = [0.15, 0.25, 0.1, 0.3, 0.2]
best_state, best_value = simple_hill_climbing(initial_state)
print(f"Initial State: {initial_state}")
print(f"Best State Found: {best_state}")
print(f"Best Value: {best_value}")

[OUT]:

Initial State: [0.15, 0.25, 0.1, 0.3, 0.2]
Best State Found: [0.9700000000000006, 0.009999999999999913, 1.0408340855860843e-17, 0.009999999999999858, 0.009999999999999969]
Best Value: -0.1053000000000444

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

יישומים של טיפוס הר בבינה מלאכותית

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

1. אופטימיזציה של מודלי למידת מכונה

טכניקת עליה בהר

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

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

2. רובוטיקה ותכנון מסלול

בתחום הרובוטיקה, טכניקת Hill Climbing מסייעת עם:

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

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

3. עיבוד שפה טבעי

NLP היישומים כוללים:

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

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

4. ראיית מחשב בעיבוד תמונה וראיית מחשב

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

A מערכת זיהוי פנים עשויה להשתמש בטכניקת "טיפול בגבעות" על מנת לייעל את היישום של תכונות הפנים במהלך הטיפול הקדמי.

5. הבנת משחקים וקבלת החלטות

הטיפול בגבעות מסייע ב:

אופטימיזצית אסטרטגיות משחק: מציאת מסעים מנצחים במשחקי לוח
הקצאת משאבים: מיטוב הפצת משאבים במשחקי אסטרטגיה
התנהגות NPC: שיפור קבלת ההחלטות של דמויות לא-שחקניות
יצירת שלבים: יצירת שלבי משחק מאוזנים ומעניינים

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

6. עסקים ופעולות

יישומים עסקיים מעשיים כוללים:

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

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

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

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

מסקנה

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

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

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

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

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

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

Source:
https://www.datacamp.com/tutorial/hill-climbing-algorithm-for-ai-in-python