20-01-2015، 01:25 AM
(آخرین ویرایش: 20-01-2015، 01:26 AM، توسط Mohsen Omidvar.)
هیوریستیك‌ها چیستند ؟
هیوریستیك‌ها عبارتند از معیارها ، روشها یا اصولی برای تصمیم‌گیری بین چندین خط‌مشی و انتخاب اثربخش‌ترین برای دستیابی به اهداف موردنظر . هیوریستیك‌ها نتیجه برقراری اعتدال بین دو نیاز هستند : نیاز به ساخت معیار‌های ساده و در همان زمان توانایی تمایز درست بین انتخاب‌های خوب و بد .
یك هیوریستیك می‌تواند حسابی سرانگشتی باشد كه برای هدایت یك دسته از اقدامات به كار می‌رود . برای مثال ، یك روش مشهور برای انتخاب طالبی رسیده عبارتست از فشار دادن محل اتصال به ریشه از یك طالبی نامزد انتخاب و سپس بو كردن آن محل ؛ اگر بوی آن محل مانند بوی داخل طالبی باشد آن طالبی به احتمال زیاد رسیده است . این قاعده سرانگشتی نه تضمین می‌كند كه تنها طالبی‌های رسیده به عنوان نامزد انتخاب شوند و نه تضمین می‌كند كه طالبی‌های رسیده آزمایش‌شده ، رسیده تشخیص داده شوند اما به هر حال این روش ، اثربخش‌ترین روش شناخته شده است .
به عنوان مثالی دیگر از استفاده هیوریستیك‌ها ، یك استاد بزرگ شطرنج را در نظر بگیرید كه با انتخاب بین چندین حركت ممكن روبرو شده است . وی ممكن است تصمیم بگیرد كه یك حركت خاص ، اثربخش‌ترین حركت خواهد بود زیرا موقعیتی فراهم می‌آورد كه به نظر می‌رسد بهتر از موقعیت‌های حاصل از حركت‌های دیگر باشد . به كارگیری معیار به نظر می‌رسد خیلی ساده‌تر از تعیین دقیق حركت یا حركاتی خواهد بود كه حریف را مجبور به مات كند . این واقعیت كه اساتید بزرگ شطرنج همواره پیروز بازی نخواهند بود نشان دهنده این است كه هیوریستیك‌های آنها انتخاب اثربخش‌ترین حركت را تضمین نمی‌كنند . نهایتاً وقتی از آنها خواسته می‌شود كه هیوریستیك خود را تشریح نمایند آنها فقط توصیفی ناقص از قواعدی ارائه می‌دهند و به نظر خود آنها ، انجام آن قواعد از توصیف آنان ساده‌تر است .
خاصیت هیوریستیك‌های خوب این است كه ابزار ساده‌ای برای تشخیص خط‌مشی‌های بهتر ارائه دهند و در حالی كه به صورت شرطی لازم ، تشخیص خط‌مشی‌های اثربخش را تضمین نمی‌كنند اما اغلب به صورت شرط كافی این تضمین را فراهم آورند . بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت‌های ممكن برای تعیین یك جواب دقیق می‌باشند . زمان لازم برای یافتن یك جواب دقیق اغلب بیشتر از یك طول عمر است . هیوریستیك‌ها با استفاده از روش‌هایی كه نیازمند ارزیابی‌های كمتر هستند و جوابهایی در محدودیت‌های زمانی قابل قبول ارایه می‌نمایند ، دارای نقشی اثربخش در حل چنین مسائلی خواهند بود .
●انواع الگوریتم‌های هیوریستیك كدامند ؟
در حالت كلی سه دسته از الگوریتم‌های هیوریستیك قابل تشخیص است:
۱- الگوریتم‌هایی كه بر ویژگی‌های ساختاری مساله و ساختار جواب متمركز می‌شوند و با استفاده از آنها الگوریتم‌های سازنده یا جستجوی محلی تعریف می‌كنند .
۲- الگوریتم‌هایی كه بر هدایت هیوریستیك یك الگوریتم سازنده یا جستجوی محلی متمركز می‌شوند به گونه‌ای كه آن الگوریتم بتواند بر شرایط حساس (مانند فرار از بهینه محلی) غلبه كند . به این الگوریتم‌ها ، متاهیوریستیك گفته می‌شود .
۳-الگوریتم‌هایی كه بر تركیب یك چارچوب یا مفهوم هیوریستیك با گونه‌هایی از برنامه‌ریزی ریاضی (معمولا روشهای دقیق) متمركز می‌شوند .
هیوریستیك‌های نوع اول می‌توانند خیلی خوب عمل كنند (گاهی اوقات تا حد بهینگی) اما ممكن است در جواب‌های دارای كیفیت پایین گیر كنند . همان طور كه اشاره شد یكی از مشكلات مهمی كه این الگوریتم‌ها با آن روبرو می‌شوند افتادن در بهینه‌های محلی است ، بدون اینكه هیچ شانسی برای فرار از آنها داشته باشند . برای بهبود این الگوریتم‌ها از اواسط دهه هفتاد ، موج تازه‌ای از رویكردها آغاز گردید . این رویكردها شامل الگوریتم‌هایی است كه صریحا یا به صورت ضمنی تقابل بین ایجاد تنوع جستجو (وقتی علائمی وجود دارد كه جستجو به سمت مناطق بد فضای جستجو می‌رود) و تشدید جستجو (با این هدف كه بهترین جواب در منطقه مورد بررسی را پیدا كند) را مدیریت می‌كنند .
این الگوریتم‌ها متاهیوریستیك نامیده می‌شوند . از بین این الگوریتم‌ها می‌توان به موارد زیر اشاره كرد:
بازپخت شبیه‌سازی شده .
جستجوی ممنوع .
الگوریتم‌های ژنتیك .
شبكه‌های عصبی مصنوعی .
بهینه‌سازی مورچه‌ای یا الگوریتم‌های مورچه .
هیوریستیك‌ها عبارتند از معیارها ، روشها یا اصولی برای تصمیم‌گیری بین چندین خط‌مشی و انتخاب اثربخش‌ترین برای دستیابی به اهداف موردنظر . هیوریستیك‌ها نتیجه برقراری اعتدال بین دو نیاز هستند : نیاز به ساخت معیار‌های ساده و در همان زمان توانایی تمایز درست بین انتخاب‌های خوب و بد .
یك هیوریستیك می‌تواند حسابی سرانگشتی باشد كه برای هدایت یك دسته از اقدامات به كار می‌رود . برای مثال ، یك روش مشهور برای انتخاب طالبی رسیده عبارتست از فشار دادن محل اتصال به ریشه از یك طالبی نامزد انتخاب و سپس بو كردن آن محل ؛ اگر بوی آن محل مانند بوی داخل طالبی باشد آن طالبی به احتمال زیاد رسیده است . این قاعده سرانگشتی نه تضمین می‌كند كه تنها طالبی‌های رسیده به عنوان نامزد انتخاب شوند و نه تضمین می‌كند كه طالبی‌های رسیده آزمایش‌شده ، رسیده تشخیص داده شوند اما به هر حال این روش ، اثربخش‌ترین روش شناخته شده است .
به عنوان مثالی دیگر از استفاده هیوریستیك‌ها ، یك استاد بزرگ شطرنج را در نظر بگیرید كه با انتخاب بین چندین حركت ممكن روبرو شده است . وی ممكن است تصمیم بگیرد كه یك حركت خاص ، اثربخش‌ترین حركت خواهد بود زیرا موقعیتی فراهم می‌آورد كه به نظر می‌رسد بهتر از موقعیت‌های حاصل از حركت‌های دیگر باشد . به كارگیری معیار به نظر می‌رسد خیلی ساده‌تر از تعیین دقیق حركت یا حركاتی خواهد بود كه حریف را مجبور به مات كند . این واقعیت كه اساتید بزرگ شطرنج همواره پیروز بازی نخواهند بود نشان دهنده این است كه هیوریستیك‌های آنها انتخاب اثربخش‌ترین حركت را تضمین نمی‌كنند . نهایتاً وقتی از آنها خواسته می‌شود كه هیوریستیك خود را تشریح نمایند آنها فقط توصیفی ناقص از قواعدی ارائه می‌دهند و به نظر خود آنها ، انجام آن قواعد از توصیف آنان ساده‌تر است .
خاصیت هیوریستیك‌های خوب این است كه ابزار ساده‌ای برای تشخیص خط‌مشی‌های بهتر ارائه دهند و در حالی كه به صورت شرطی لازم ، تشخیص خط‌مشی‌های اثربخش را تضمین نمی‌كنند اما اغلب به صورت شرط كافی این تضمین را فراهم آورند . بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت‌های ممكن برای تعیین یك جواب دقیق می‌باشند . زمان لازم برای یافتن یك جواب دقیق اغلب بیشتر از یك طول عمر است . هیوریستیك‌ها با استفاده از روش‌هایی كه نیازمند ارزیابی‌های كمتر هستند و جوابهایی در محدودیت‌های زمانی قابل قبول ارایه می‌نمایند ، دارای نقشی اثربخش در حل چنین مسائلی خواهند بود .
●انواع الگوریتم‌های هیوریستیك كدامند ؟
در حالت كلی سه دسته از الگوریتم‌های هیوریستیك قابل تشخیص است:
۱- الگوریتم‌هایی كه بر ویژگی‌های ساختاری مساله و ساختار جواب متمركز می‌شوند و با استفاده از آنها الگوریتم‌های سازنده یا جستجوی محلی تعریف می‌كنند .
۲- الگوریتم‌هایی كه بر هدایت هیوریستیك یك الگوریتم سازنده یا جستجوی محلی متمركز می‌شوند به گونه‌ای كه آن الگوریتم بتواند بر شرایط حساس (مانند فرار از بهینه محلی) غلبه كند . به این الگوریتم‌ها ، متاهیوریستیك گفته می‌شود .
۳-الگوریتم‌هایی كه بر تركیب یك چارچوب یا مفهوم هیوریستیك با گونه‌هایی از برنامه‌ریزی ریاضی (معمولا روشهای دقیق) متمركز می‌شوند .
هیوریستیك‌های نوع اول می‌توانند خیلی خوب عمل كنند (گاهی اوقات تا حد بهینگی) اما ممكن است در جواب‌های دارای كیفیت پایین گیر كنند . همان طور كه اشاره شد یكی از مشكلات مهمی كه این الگوریتم‌ها با آن روبرو می‌شوند افتادن در بهینه‌های محلی است ، بدون اینكه هیچ شانسی برای فرار از آنها داشته باشند . برای بهبود این الگوریتم‌ها از اواسط دهه هفتاد ، موج تازه‌ای از رویكردها آغاز گردید . این رویكردها شامل الگوریتم‌هایی است كه صریحا یا به صورت ضمنی تقابل بین ایجاد تنوع جستجو (وقتی علائمی وجود دارد كه جستجو به سمت مناطق بد فضای جستجو می‌رود) و تشدید جستجو (با این هدف كه بهترین جواب در منطقه مورد بررسی را پیدا كند) را مدیریت می‌كنند .
این الگوریتم‌ها متاهیوریستیك نامیده می‌شوند . از بین این الگوریتم‌ها می‌توان به موارد زیر اشاره كرد:
بازپخت شبیه‌سازی شده .
جستجوی ممنوع .
الگوریتم‌های ژنتیك .
شبكه‌های عصبی مصنوعی .
بهینه‌سازی مورچه‌ای یا الگوریتم‌های مورچه .
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
خورشید باش که اگر خواستی بر کسی نتابی نتوانی.