الگوريتمهاي هيوريستيك چيستند ؟

[Borna66]

سيستم‌هاي پيچيده اجتماعي تعداد زيادي از مسائل داراي طبيعت تركيباتي را پيش روي ما قرار مي‌دهند . مسير كاميونهاي حمل‌ونقل بايد تعيين شود ، انبارها يا نقاط فروش محصولات بايد جايابي شوند ، شبكه‌هاي ارتباطي بايد طراحي شوند ، كانتينرها بايد بارگيري شوند ، رابط‌هاي راديويي مي‌بايست داراي فركانس مناسب باشند ، مواد اوليه چوب ، فلز ، شيشه و چرم بايد به اندازه‌هاي لازم بريده شوند ؛ از اين دست مسائل بي‌شمارند . تئوري پيچيدگي به ما مي گويد كه مسائل تركيباتي اغلب پلي‌نوميال(Polynomial) نيستند . اين مسائل در اندازه‌هاي كاربردي و عملي خود به قدري بزرگ هستند كه نمي‌توان جواب بهينه آنها را در مدت زمان قابل پذيرش به دست آورد . با اين وجود ، اين مسائل بايد حل شوند و بنابراين چاره‌اي نيست كه به جوابهاي زير بهينه بسنده نمود ؛ به گونه‌اي كه داراي كيفيت قابل پذيرش بوده و در مدت زمان قابل پذيرش به دست آيند .

[Borna66]

چندين رويكرد براي طراحي جوابهاي با كيفيت قابل پذيرش تحت محدوديت زماني قابل پذيرش پيشنهاد شده است . الگوريتم‌هايي هستند كه مي‌توانند يافتن جوابهاي خوب در فاصله مشخصي از جواب بهينه را تضمين كنند كه به آنها الگوريتم‌هاي تقريبي مي‌گويند . الگوريتم‌هاي ديگري هستند كه تضمين مي‌دهند با احتمال بالا جواب نزديك بهينه توليد كنند كه به آنها الگوريتم‌هاي احتمالي گفته مي‌شود . جداي از اين دو دسته ، مي‌توان الگوريتم‌هايي را پذيرفت كه هيچ تضميني در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتايج آنها ، به طور متوسط بهترين تقابل كيفيت و زمان حل براي مسئله مورد بررسي را به همراه داشته‌اند ؛ به اين الگوريتم‌ها، الگوريتم‌هاي هيوريستيك گفته مي‌شود .

در گام آتي هيوريستيكها را تعريف خواهيم نمود ...

[Borna66]

گام يكصد و بيستم



هيوريستيك‌ها چيستند ؟

هيوريستيك‌ها عبارتند از معيارها ، روشها يا اصولي براي تصميم‌گيري بين چندين خط‌مشي و انتخاب اثربخش‌ترين براي دستيابي به اهداف موردنظر . هيوريستيك‌ها نتيجه برقراري اعتدال بين دو نياز هستند : نياز به ساخت معيار‌هاي ساده و در همان زمان توانايي تمايز درست بين انتخاب‌هاي خوب و بد .

يك هيوريستيك مي‌تواند حسابي سرانگشتي باشد كه براي هدايت يك دسته از اقدامات به كار مي‌رود . براي مثال ، يك روش مشهور براي انتخاب طالبي رسيده عبارتست از فشار دادن محل اتصال به ريشه از يك طالبي نامزد انتخاب و سپس بو كردن آن محل ؛ اگر بوي آن محل مانند بوي داخل طالبي باشد آن طالبي به احتمال زياد رسيده است . اين قاعده سرانگشتي نه تضمين مي‌كند كه تنها طالبي‌هاي رسيده به عنوان نامزد انتخاب شوند و نه تضمين مي‌كند كه طالبي‌هاي رسيده آزمايش‌شده ، رسيده تشخيص داده شوند اما به هر حال اين روش ، اثربخش‌ترين روش شناخته شده است .

به عنوان مثالي ديگر از استفاده هيوريستيك‌ها ، يك استاد بزرگ شطرنج را در نظر بگيريد كه با انتخاب بين چندين حركت ممكن روبرو شده است . وي ممكن است تصميم بگيرد كه يك حركت خاص ، اثربخش‌ترين حركت خواهد بود زيرا موقعيتي فراهم مي‌آورد كه به نظر مي‌رسد بهتر از موقعيت‌هاي حاصل از حركت‌هاي ديگر باشد . به كارگيري معيار به نظر مي‌رسد خيلي ساده‌تر از تعيين دقيق حركت يا حركاتي خواهد بود كه حريف را مجبور به مات كند . اين واقعيت كه اساتيد بزرگ شطرنج همواره پيروز بازي نخواهند بود نشان دهنده اين است كه هيوريستيك‌هاي آنها انتخاب اثربخش‌ترين حركت را تضمين نمي‌كنند . نهايتا‏ً وقتي از آنها خواسته ‌مي‌شود كه هيوريستيك خود را تشريح نمايند آنها فقط توصيفي ناقص از قواعدي ارائه مي‌دهند و به نظر خود آنها ، انجام آن قواعد از توصيف آنان ساده‌تر است .

خاصيت هيوريستيك‌هاي خوب اين است كه ابزار ساده‌اي براي تشخيص خط‌مشي‌هاي بهتر ارائه دهند و در حالي كه به صورت شرطي لازم ، تشخيص خط‌مشي‌هاي اثربخش را تضمين نمي‌كنند اما اغلب به صورت شرط كافي اين تضمين را فراهم ‌آورند . بيشتر مسائل پيچيده نيازمند ارزيابي تعداد انبوهي از حالت‌هاي ممكن براي تعيين يك جواب دقيق مي‌باشند . زمان لازم براي يافتن يك جواب دقيق اغلب بيشتر از يك طول عمر است . هيوريستيك‌ها با استفاده از روش‌هايي كه نيازمند ارزيابي‌هاي كمتر هستند و جوابهايي در محدوديت‌هاي زماني قابل قبول ارايه مي‌نمايند ، داراي نقشي اثربخش در حل چنين مسائلي خواهند بود .

در گام آتي انواع الگوريتم‌هاي هيوريستيك را بيان خواهيم نمود ...

[Borna66]

گام يكصد و بيست و يكم



انواع الگوريتم‌هاي هيوريستيك كدامند ؟

در حالت كلي سه دسته از الگوريتم‌هاي هيوريستيك قابل تشخيص است:

1- الگوريتم‌هايي كه بر ويژگي‌هاي ساختاري مساله و ساختار جواب متمركز مي‌شوند و با استفاده از آنها الگوريتم‌هاي سازنده يا جستجوي محلي تعريف مي‌كنند .

2- الگوريتم‌هايي كه بر هدايت هيوريستيك يك الگوريتم سازنده يا جستجوي محلي متمركز مي‌شوند به گونه‌اي كه آن الگوريتم بتواند بر شرايط حساس (مانند فرار از بهينه محلي) غلبه كند . به اين الگوريتم‌ها ، متاهيوريستيك گفته مي‌شود .

3- الگوريتم‌هايي كه بر تركيب يك چارچوب يا مفهوم هيوريستيك با گونه‌هايي از برنامه‌ريزي رياضي (معمولا روشهاي دقيق) متمركز مي‌شوند .

هيوريستيك‌هاي نوع اول مي‌توانند خيلي خوب عمل كنند (گاهي اوقات تا حد بهينگي) اما ممكن است در جواب‌هاي داراي كيفيت پايين گير كنند . همان طور كه اشاره شد يكي از مشكلات مهمي كه اين الگوريتم‌ها با آن روبرو مي‌شوند افتادن در بهينه‌هاي محلي است ، بدون اينكه هيچ شانسي براي فرار از آنها داشته باشند . براي بهبود اين الگوريتم‌ها از اواسط دهه هفتاد ، موج تازه‌اي از رويكردها آغاز گرديد . اين رويكردها شامل الگوريتم‌هايي است كه صريحا يا به صورت ضمني تقابل بين ايجاد تنوع جستجو (وقتي علائمي وجود دارد كه جستجو به سمت مناطق بد فضاي جستجو مي‌رود) و تشديد جستجو (با اين هدف كه بهترين جواب در منطقه مورد بررسي را پيدا كند) را مديريت مي‌كنند .

اين الگوريتم‌ها متاهيوريستيك ناميده مي‌شوند . از بين اين الگوريتم‌ها مي‌توان به موارد زير اشاره كرد:

* بازپخت شبيه‌سازي شده .
* جستجوي ممنوع .
* الگوريتم‌هاي ژنتيك .
* شبكه‌هاي عصبي مصنوعي .
* بهينه‌سازي مورچه‌اي يا الگوريتم‌هاي مورچه .