اگه بخواهیم پیچیدگی زمانی یک الگوریتم جستجوی متاهیوریستیک را کم کنیم،باید چیکار کنیم؟
سوالتون بیش از حد کلی هستش. چه الگوریتمی مد نظر شماست؟
الگوریتم جستجوی گرانشی
تا جائیکه میدونم کاهش پیچیدگی متاهیوریستیکها تقریبا معنای علمی نداره؛
یکی از دلایلش اینه که پیچیدگی این الگوریتم ها به شکل تئوریک قابل اندازه گیری نیست و مبنای سنجش کارایی رو بر اساس مصرف زمان و حافظه (به شکل experiment) قرار میدن؛ و از جهتی میزان مصرف زمان و حافظه را مسئله ای که باید حل بشه تعیین میکنه نه الگوریتم متاهیوریستیک؛
اگه مدت زمان اجرای یه الگوریتم متاهیوریستیک (مثلا GA یا همون GSA که گفتید) برای حل مسئله ای زیاد باشه تنها به کمک برخی تکنیک ها ممکنه کارایی (کاهش زمان و حافظه یا افزایش دقت) بهتر بشه؛ یکیش موازی سازی واقعیه که هم سخت افزار میخاد (که اغلب نداریم) و هم مهارت موازی سازی (که به خودتون بر میگرده)؛ راه دیگه اینه که کدینگ مسئله تون رو کارامدتر کنید (خود این میتونه در حد ایده یه مقاله باشه)؛ مثلا chromosome representation در الگوریتم GA کاملا بر زمان مصرفی اپراتورهای ترکیب و جهش و همینطور تابع ارزیاب اثرگذاره؛ و راه مرسوم تر اینکه که با شناخت ریز و دقیق عملکرد الگوریتمی که نوشتید نقطه ضعفهاشو در بیارید و با بکاربردن یه هیوریستیک دیگه در جهت برقراری بهتر تِـرید آف exploitation-exploration به یک رویکرد ترکیبی بهتر برسید؛ این هیوریستیک کمکی میتونه یه الگوریتم تکاملی مثل HS باشه یا لوکال سرچهایی مثل گرادیان افزایشی یا SA یا ... که انتخاب مناسبش برمیگرده به نوع مسئله تون؛
(۰۶ تیر ۱۳۹۲ ۱۲:۴۸ ب.ظ)Ghiasoddin نوشته شده توسط: راه مرسوم تر اینکه که با شناخت ریز و دقیق عملکرد الگوریتمی که نوشتید نقطه ضعفهاشو در بیارید و با بکاربردن یه هیوریستیک دیگه در جهت برقراری بهتر تِـرید آف exploitation-exploration به یک رویکرد ترکیبی بهتر برسید؛ این هیوریستیک کمکی میتونه یه الگوریتم تکاملی مثل HS باشه یا لوکال سرچهایی مثل گرادیان افزایشی یا SA یا ... که انتخاب مناسبش برمیگرده به نوع مسئله تون؛یه مصداق واقعی از این نوع کارها می تونید ارائه کنید.یه مقاله یا پایان نامه؟ متشکرم
مقاله با ایده های ترکیبی بسیار زیاده؛ میتونید هر کدوم از لوکال سرچ ها رو با اسم تکاملی ها سرچ کنید؛ مثلا GA+TS یا PSO+HS یا ACO+SA ...؛ یا اینکه به سراغ ژورنالهای تخصصی soft computing برید و کلمه ای مثل hybrid رو سرچ کنید؛ مثلا با همین کلیدواژه در ژورنال Applied Soft Computing میتونید نمونه های تازه بسیار خوبی رو پیدا کنید؛ چند نمونه:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
همین کلیدواژه ها رو با عبارت thesis در گوگل سرچ کنید پایان نامه هم میتونید پیدا کنید؛ مثل این دو تا:
krex.k-state.edu/dspace/bitstream/handle/2097/1492/xinyecai2009.pdf?sequence=1
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۰۶ تیر ۱۳۹۲ ۱۲:۴۸ ب.ظ)Ghiasoddin نوشته شده توسط: راه دیگه اینه که کدینگ مسئله تون رو کارامدتر کنید (خود این میتونه در حد ایده یه مقاله باشه)؛ مثلا chromosome representation در الگوریتم GA کاملا بر زمان مصرفی اپراتورهای ترکیب و جهش و همینطور تابع ارزیاب اثرگذاره؛
و راه مرسوم تر اینکه که با شناخت ریز و دقیق عملکرد الگوریتمی که نوشتید نقطه ضعفهاشو در بیارید و با بکاربردن یه هیوریستیک دیگه در جهت برقراری بهتر تِـرید آف exploitation-exploration به یک رویکرد ترکیبی بهتر برسید؛ این هیوریستیک کمکی میتونه یه الگوریتم تکاملی مثل HS باشه یا لوکال سرچهایی مثل گرادیان افزایشی یا SA یا ... که انتخاب مناسبش برمیگرده به نوع مسئله تون؛
شما تا حالا مقاله معتبری دیدین که تاثیر تغییر نحوه نمایش پاسخ رو بر روی کارآیی الگوریتم بررسی کنه؟حالا هر متاهیوریستیکی باشه،فرق نداره. من یه مدتی این مسئله برام جالب شده بود، سرچ زدم در موردش چیز خوبی پیدا نکردم.
چیزی که من بیشتر دیدم این هست که با هیبرید کردن الگوریتم ها کیفیت پاسخ یعنی دقت رو بالا میبرن و نه سرعت رو.
مثلا توی متاهیوریستیک های population-based گفته میشه چون بعد از چند تا تکرار در گیر بهینه محلی یا رکود میشن برای خروجشون از این وضعیت و بهتر شدن کیفیت پاسخ اونا را با لوکال سرچها یا تکنیکهای دیگه ترکیب میکنن.
(۰۹ شهریور ۱۳۹۲ ۱۱:۲۹ ب.ظ)sepid نوشته شده توسط: شما تا حالا مقاله معتبری دیدین که تاثیر تغییر نحوه نمایش پاسخ رو بر روی کارآیی الگوریتم بررسی کنه؟ حالا هر متاهیوریستیکی باشه، فرق نداره. من یه مدتی این مسئله برام جالب شده بود، سرچ زدم در موردش چیز خوبی پیدا نکردم.
چیزی که من بیشتر دیدم این هست که با هیبرید کردن الگوریتم ها کیفیت پاسخ یعنی دقت رو بالا میبرن و نه سرعت رو.
مثلا توی متاهیوریستیک های population-based گفته میشه چون بعد از چند تا تکرار در گیر بهینه محلی یا رکود میشن برای خروجشون از این وضعیت و بهتر شدن کیفیت پاسخ اونا را با لوکال سرچها یا تکنیکهای دیگه ترکیب میکنن.
عبارتی مثل new chromosome representation رو سرچ کنید؛ دو سه تا نمونه خوب:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ولی اغلب ایده پردازی ها در رویکردهای تکاملی همونطوری هست که شما اشاره کردید؛ بهمین دلیل هم در مقالات تکاملی experiment سنگینی باید انجام بشه تا داورها موثر بودن الگوریتم ارائه شده رو بپذیرن؛