שְׁאֵלָה:
האם נמלים באמת מוצאות את הדרך הקצרה ביותר למקור מזון?
Nav
2017-08-04 10:51:52 UTC
view on stackexchange narkive permalink

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

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

חפשו בוויקיפדיה "טחנת נמלים", או ביוטיוב "ספירלת מוות של נמלים" ותגלו שהם יוצרים שבילים שהם לא רק תת אופטימליים, אלא הם למעשה נתיבים לא חוקיים לחלוטין.
אחד תשובה:
Remi.b
2017-08-04 11:09:06 UTC
view on stackexchange narkive permalink

תשובה קצרה

האם נמלים באמת מוצאות את הדרך הקצרה ביותר למקור מזון?

לא! אך הם יכולים למצוא נתיב הגון

תשובה ארוכה יותר

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

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

אם איננו יודעים כמה טוב הפתרון שנמצא בהשוואה לטוב ביותר, אז כיצד נדע שהוא מספיק טוב?
@Ooker איך אתה שופט באיזו דרך ללכת למקומות? אני חושב שתגלה שאתה לא מתייחס לדרך "הטובה ביותר" (שאולי אתה לא מכיר) אלא למצב במקום, כמו "האם זה בסדר לבזבז זמן זה".
באופן דומה, כשאתה לוקח את המכונית שלך ללכת למקום כלשהו, ​​בדרך כלל אתה בדרך "מספיק טוב" ולא הכי טוב. זה מספיק טוב כי לוקח זמן סביר להגיע ליעד ...
@Remi.b "אלגוריתמים כאלה מנסים למצוא פיתרון מספיק טוב בדרך כלל מבלי לדעת עד כמה" טוב "הפיתרון שנמצא לפיתרון הטוב ביותר." - בעיות אופטימיזציה * יודעות * למעשה (באופן כללי) מהו הפיתרון האמיתי, אולם לא תמיד יכולות להשיג את זה * באמצעות חישוב *. כאשר מיישמים פונקציית אופטימיזציה, בדרך כלל יש אפסילון שמוגדר, לאן אם השגיאה של הפתרון המחושב נמוכה מאפסילון, אז הפיתרון של אלגוריתם האופטימיזציה יתקבל כ"קרוב מספיק ".
@Remi.b אם אלגוריתם אופטימיזציה אינו מודע לפיתרון האמיתי שהוא מנסה להשיג, אין לו שום דרך לאמת פתרון פוטנציאלי. אני מודה, בהחלט * ישנם * מקרים רבים שבהם לא ידוע על שום פיתרון אמיתי, אולם זה הרבה יותר נפוץ בעבודה תיאורטית, כפי שמתייחס לגישות החישוב היישומיות הרבה יותר.
@Charles תודה, הבאתי שינוי קטן כדי להימנע מהצהרה שאלגוריתם אופטימיזציה לעולם לא יודע מה הפיתרון הטוב ביותר.
@Charles אני לא מסכים. אתה יכול לבדוק את חוזקו של פתרון מול פתרונות אפשריים אחרים. אינך צריך לדעת את המרחק של המסלול הטוב ביותר האפשרי למיקום, אם אתה עובד על 1,000 מסלולים פוטנציאליים ואז לוקח את הקצר ביותר מאלה.
@Tom.Bowen89 אם יש לך אוסף של פתרונות ואתה רק בודק פיתרון אחד מול אחרים, איך אתה יכול להיות בטוח שכל אחד מהפתרונות האלה נמצא בכל מקום קרוב לפלט הדרוש? יש להגדיר סוג של "תפוקה הכי רצויה", אחרת אינך יכול "לראות את היער מתוך העצים". כלומר, יש להגדיר * פתרון אידיאלי, או סובלנות מינימאלית לשגיאות. אם לא, לא יכול להיות אמון עד כמה האלגוריתם שלך מדויק והתפוקות שהוא מייצר.
@Tom.Bowen89 אוסיף גם כי בבעיות אופטימיזציה רבות, הם נוקטים גישה הסתברותית, כך שיש להתקיים * מספר רב של מקרים (אוספים של פתרונות הנובעים ממצבים התחלתיים שונים). כלומר, כל מופע של האלגוריתם הפועל יפיק קבוצות פתרונות שונות לחלוטין. עם זאת, שוב, יש להגדיר איזושהי תוצאה רצויה על מנת להעריך את הדיוק של פתרונות אלה.
@Tom.Bowen89 אז, כדי לצאת מהדוגמה שלך לדרך הקצרה ביותר .. מה אם הנתיב הקצר ביותר האמיתי הוא 10 מייל, אולם הפיתרון הטוב ביותר שהאלגוריתם שלך מייצר הוא 50 מייל? כיצד תוכל להעריך את הדיוק אם אין לך מושג לגבי הדרך הקצרה ביותר? זה חשוב מכיוון שכאמור בתגובה הקודמת ביותר שלי, אם הפיתרון הטוב ביותר עדיין רחוק מאוד מהפתרון האמיתי, יהיה צורך להריץ את האלגוריתם שוב על מנת להשיג פתרונות פוטנציאליים שונים. חייבת * להיות הערכה "חיצונית" כלשהי לגבי ביצועי ודיוק האלגוריתם שלך.
@Tom.Bowen89 אני ממליץ לך לבחון אלגוריתמי חישול מדומים, מכיוון שזו פלטפורמה נפוצה במדעי המחשב להכנסת הדינמיקה של אלגוריתמי אופטימיזציה וקירוב. https://en.wikipedia.org/wiki/Simulated_annealing
@Charles האם יש דרך לחשב את ביטחון הדיוק של הנתיב המחושב? תקן אותי אם אני טועה, אבל האם לא בסטטיסטיקה ניתן לחשב את הביטחון של ניחוש באופן עצמאי עם הערך הנכון?
@ooker אתה לא יכול לחשב את הביטחון אם יש לך את הדרך הטובה ביותר רק מדגימה (ניסיון לפתרונות ולראות אילו עובדים עובדים) אלא אם כן אתה יכול להכריע את כל שטח המדינה. עם זאת, אם אתה יודע משהו על מרחב המדינה שלך, אתה יכול להשתמש במידע הספציפי לבעיה כדי לקבוע כמה טוב הפתרון שלך. לדוגמא, אם אתה יודע שהחלל נבדל, אתה יכול להשתמש בכל מידע שאתה עשוי לדעת על הנגזרות המקסימליות כדי ליצור גבול עליון / תחתון.
@Charles: "אם אלגוריתם אופטימיזציה אינו מודע לפיתרון האמיתי שהוא מנסה להשיג, אין לו שום דרך לאמת פיתרון פוטנציאלי." - זה לא נכון - לעתים קרובות בחיים האמיתיים הקריטריון הוא "פתרון חייב לעלות פחות מ- X". אם נמצא פיתרון בעלות נמוכה מ- X, הוא "מספיק טוב", ומכאן שהוא תקף. אם זה הרבה פחות מ- X, כל כך הרבה יותר טוב. אין צורך לדעת את הערך המוחלט הטוב ביותר. ערך ה- X תלוי באילוצים (החיצוניים) של הפרויקט, ולא בפרמטרים של בעיית האופטימיזציה עצמה.
זה בדיוק מה שאמרתי בתגובה קודמת, חחח. אנא קרא את כל התגובות לפני שתנסה לתקן מישהו. "כאשר מיישמים פונקציית אופטימיזציה, בדרך כלל יש אפסילון שמוגדר, לאן אם השגיאה של הפתרון המחושב קטנה מאפסילון, אז הפיתרון של אלגוריתם האופטימיזציה יתקבל כ"קרוב מספיק".
@Charles: קראתי את ההערה, והיא שונה ממה שאני אומר. אני לא אומר שאתה מגדיר אפסילון שנותן הבדל מקובל (פרופורציונלי או מוחלט) בין הערך האופטימלי האמיתי לבין הטוב ביותר שנמצא - זה עדיין דורש * אפריורי * ידע של הערך האופטימלי. במקום זאת אני אומר שאתה מגדיר סף X שהוא * בלתי תלוי * בערך האופטימלי - כלומר בכלל לא אכפת לך כמה אתה קרוב לאופטימום האמיתי, רק אם אתה מוצא פתרון ש"עובד "בכל מה הקשר שאתה פועל בו.
@psmears איך אתה מגדיר את היוריסטיקה הוא לא תמיד עקבי וקשה מדי להכליל, ולכן ההצהרות שלך אינן תקפות. זה שונה מאלגוריתם לאלגוריתם, שמבוסס בסופו של דבר על מידע שכבר השגת על התפתחות האלגוריתם.
ההערות אינן מיועדות לדיונים מורחבים. אנא עקוב אחר כך בצ'אט (ובסופו של דבר באתר CS SE כלשהו).
@Charles: אתה מבלבל את האלגוריתם עם תחום הבעיה, ובמיוחד את קריטריון הקבלה של הבעיה (עבור הנמלים, אולי: האם האנרגיה במזון בסוף הדרך הזו חורגת מהאנרגיה המושקעת בדרך בדרך בכדי להבטיח הישרדות? ) עם קריטריון העצירה / היוריסטיקה של אלגוריתם מסוים ("בסדר השקענו מספיק זמן ואנרגיה בבדיקת מסלולים, עכשיו בואו נמשיך ונאכל."). הראשון ישפיע ככל הנראה על הבחירה באחרונים, אך חשוב להיות מודע להבחנה. בהצלחה בלימודים, פרויקט החלבונים שלך נשמע מגניב :)
@Pimgd https: // xkcd.com / 85 /


ⓘ
שאלה ותשובה זו תורגמה אוטומטית מהשפה האנגלית.התוכן המקורי זמין ב- stackexchange, ואנו מודים לו על רישיון cc by-sa 3.0 עליו הוא מופץ.
Loading...