الگوریتمهای هیوریستیک چیستند ؟

سیستم‌های پیچیده اجتماعی تعداد زیادی از مسائل دارای طبیعت تركیباتی را پیش روی ما قرار می‌دهند . مسیر كامیونهای حمل‌ونقل باید تعیین شود ، انبارها یا نقاط فروش محصولات باید جایابی شوند ، شبكه‌های ارتباطی باید طراحی شوند ، كانتینرها باید بارگیری شوند ، رابط‌های رادیویی می‌بایست دارای فركانس مناسب باشند ، مواد اولیه چوب ، فلز ، شیشه و چرم باید به اندازه‌های لازم بریده شوند ؛ از این دست مسائل بی‌شمارند . تئوری پیچیدگی به ما می گوید كه مسائل تركیباتی اغلب پلی‌نومیال(Polynomial) نیستند . این مسائل در اندازه‌های كاربردی و عملی خود به قدری بزرگ هستند كه نمی‌توان جواب بهینه آنها را در مدت زمان قابل پذیرش به دست آورد . با این وجود ، این مسائل باید حل شوند و بنابراین چاره‌ای نیست كه به جوابهای زیر بهینه بسنده نمود ؛ به گونه‌ای كه دارای كیفیت قابل پذیرش بوده و در مدت زمان قابل پذیرش به دست آیند .
چندین رویكرد برای طراحی جوابهای با كیفیت قابل پذیرش تحت محدودیت زمانی قابل پذیرش پیشنهاد شده است . الگوریتم‌هایی هستند كه می‌توانند یافتن جوابهای خوب در فاصله مشخصی از جواب بهینه را تضمین كنند كه به آنها الگوریتم‌های تقریبی می‌گویند . الگوریتم‌های دیگری هستند كه تضمین می‌دهند با احتمال بالا جواب نزدیك بهینه تولید كنند كه به آنها الگوریتم‌های احتمالی گفته می‌شود . جدای از این دو دسته ، می‌توان الگوریتم‌هایی را پذیرفت كه هیچ تضمینی در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتایج آنها ، به طور متوسط بهترین تقابل كیفیت و زمان حل برای مسئله مورد بررسی را به همراه داشته‌اند ؛ به این الگوریتم‌ها، الگوریتم‌های هیوریستیك گفته می‌شود .
●هیوریستیك‌ها چیستند ؟
هیوریستیك‌ها عبارتند از معیارها ، روشها یا اصولی برای تصمیم‌گیری بین چندین خط‌مشی و انتخاب اثربخش‌ترین برای دستیابی به اهداف موردنظر . هیوریستیك‌ها نتیجه برقراری اعتدال بین دو نیاز هستند : نیاز به ساخت معیار‌های ساده و در همان زمان توانایی تمایز درست بین انتخاب‌های خوب و بد .
یك هیوریستیك می‌تواند حسابی سرانگشتی باشد كه برای هدایت یك دسته از اقدامات به كار می‌رود . برای مثال ، یك روش مشهور برای انتخاب طالبی رسیده عبارتست از فشار دادن محل اتصال به ریشه از یك طالبی نامزد انتخاب و سپس بو كردن آن محل ؛ اگر بوی آن محل مانند بوی داخل طالبی باشد آن طالبی به احتمال زیاد رسیده است . این قاعده سرانگشتی نه تضمین می‌كند كه تنها طالبی‌های رسیده به عنوان نامزد انتخاب شوند و نه تضمین می‌كند كه طالبی‌های رسیده آزمایش‌شده ، رسیده تشخیص داده شوند اما به هر حال این روش ، اثربخش‌ترین روش شناخته شده است .
به عنوان مثالی دیگر از استفاده هیوریستیك‌ها ، یك استاد بزرگ شطرنج را در نظر بگیرید كه با انتخاب بین چندین حركت ممكن روبرو شده است . وی ممكن است تصمیم بگیرد كه یك حركت خاص ، اثربخش‌ترین حركت خواهد بود زیرا موقعیتی فراهم می‌آورد كه به نظر می‌رسد بهتر از موقعیت‌های حاصل از حركت‌های دیگر باشد . به كارگیری معیار به نظر می‌رسد خیلی ساده‌تر از تعیین دقیق حركت یا حركاتی خواهد بود كه حریف را مجبور به مات كند . این واقعیت كه اساتید بزرگ شطرنج همواره پیروز بازی نخواهند بود نشان دهنده این است كه هیوریستیك‌های آنها انتخاب اثربخش‌ترین حركت را تضمین نمی‌كنند . نهایتا‏ً وقتی از آنها خواسته ‌می‌شود كه هیوریستیك خود را تشریح نمایند آنها فقط توصیفی ناقص از قواعدی ارائه می‌دهند و به نظر خود آنها ، انجام آن قواعد از توصیف آنان ساده‌تر است .
خاصیت هیوریستیك‌های خوب این است كه ابزار ساده‌ای برای تشخیص خط‌مشی‌های بهتر ارائه دهند و در حالی كه به صورت شرطی لازم ، تشخیص خط‌مشی‌های اثربخش را تضمین نمی‌كنند اما اغلب به صورت شرط كافی این تضمین را فراهم ‌آورند . بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت‌های ممكن برای تعیین یك جواب دقیق می‌باشند . زمان لازم برای یافتن یك جواب دقیق اغلب بیشتر از یك طول عمر است . هیوریستیك‌ها با استفاده از روش‌هایی كه نیازمند ارزیابی‌های كمتر هستند و جوابهایی در محدودیت‌های زمانی قابل قبول ارایه می‌نمایند ، دارای نقشی اثربخش در حل چنین مسائلی خواهند بود .
●انواع الگوریتم‌های هیوریستیك كدامند ؟
در حالت كلی سه دسته از الگوریتم‌های هیوریستیك قابل تشخیص است:
۱- الگوریتم‌هایی كه بر ویژگی‌های ساختاری مساله و ساختار جواب متمركز می‌شوند و با استفاده از آنها الگوریتم‌های سازنده یا جستجوی محلی تعریف می‌كنند .
۲- الگوریتم‌هایی كه بر هدایت هیوریستیك یك الگوریتم سازنده یا جستجوی محلی متمركز می‌شوند به گونه‌ای كه آن الگوریتم بتواند بر شرایط حساس (مانند فرار از بهینه محلی) غلبه كند . به این الگوریتم‌ها ، متاهیوریستیك گفته می‌شود .
۳-الگوریتم‌هایی كه بر تركیب یك چارچوب یا مفهوم هیوریستیك با گونه‌هایی از برنامه‌ریزی ریاضی (معمولا روشهای دقیق) متمركز می‌شوند .
هیوریستیك‌های نوع اول می‌توانند خیلی خوب عمل كنند (گاهی اوقات تا حد بهینگی) اما ممكن است در جواب‌های دارای كیفیت پایین گیر كنند . همان طور كه اشاره شد یكی از مشكلات مهمی كه این الگوریتم‌ها با آن روبرو می‌شوند افتادن در بهینه‌های محلی است ، بدون اینكه هیچ شانسی برای فرار از آنها داشته باشند . برای بهبود این الگوریتم‌ها از اواسط دهه هفتاد ، موج تازه‌ای از رویكردها آغاز گردید . این رویكردها شامل الگوریتم‌هایی است كه صریحا یا به صورت ضمنی تقابل بین ایجاد تنوع جستجو (وقتی علائمی وجود دارد كه جستجو به سمت مناطق بد فضای جستجو می‌رود) و تشدید جستجو (با این هدف كه بهترین جواب در منطقه مورد بررسی را پیدا كند) را مدیریت می‌كنند .
این الگوریتم‌ها متاهیوریستیك نامیده می‌شوند . از بین این الگوریتم‌ها می‌توان به موارد زیر اشاره كرد:
بازپخت شبیه‌سازی شده .
جستجوی ممنوع .
الگوریتم‌های ژنتیك .
شبكه‌های عصبی مصنوعی .
بهینه‌سازی مورچه‌ای یا الگوریتم‌های مورچه .