نام فایل : لگوريتمهاي هيوريستيكها

فرمت : .doc

تعداد صفحه/اسلاید : 9

حجم : 53 کیلوبایت

لگوريتمهاي
هيوريستيكها
چكيده
در اين مقاله مفهوم هيوريستيك شرح داده ميشود و انواع الگوريتمهاي هيوريستيك دستهبندي ميشوند.
1-مقدمه
سيستمهاي پيچيده اجتماعي تعداد زيادي از مسائل داراي طبيعت تركيباتي
1
را پيش روي ما قرار ميدهند. مسير كاميونهاي حمل و نقل بايد تعيين شود، انبارها يا نقاط فروش محصولات بايد جايابي شوند، شبكههاي ارتباطي بايد طراحي شوند، كانتينرها بايد بارگيري شوند، رابطهاي راديويي ميبايست داراي فركانس مناسب باشند، مواد اوليه چوب، فلز، شيشه و چرم بايد به اندازههاي لازم بريده شوند؛ از اين دست مسائل بيشمارند. تئوري پيچيدگي به ما مي گويد كه مسائل تركيباتي اغلب پلينوميال
2
 نيستند. اين مسائل در اندازههاي كاربردي و عملي خود به قدري بزرگ هستند كه نميتوان جواب بهينه آنها را در مدت زمان قابل پذيرش به دست آورد. با اين وجود، اين مسائل بايد حل شوند و بنابراين چارهاي نيست كه به جوابهاي زير بهينه
3
بسنده نمود به گونهاي كه داراي كيفيت قابل پذيرش بوده و در مدت زمان قابل پذيرش به دست آيند.
چندين رويكرد براي طراحي جوابهاي با كيفيت قابل پذيرش تحت محدوديت زماني قابل پذيرش پيشنهاد شده است. الگوريتمهايي هستند كه ميتوانند يافتن جوابهاي خوب در فاصله مشخصي از جواب بهينه را تضمين كنند كه به آنها الگوريتمهاي تقريبي ميگويند. الگوريتمهاي ديگري هستند كه تضمين ميدهند با احتمال بالا جواب نزديك بهينه توليد كنند كه به آنها الگوريتمهاي احتمالي گفته ميشود. جداي از اين دو دسته، ميتوان الگوريتمهايي را پذيرفت كه هيچ تضميني در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتايج آنها، به طور متوسط بهترين تقابل كيفيت و زمان حل براي مسئله مورد بررسي را به همراه داشتهاند. به اين الگوريتمها، الگوريتمهاي هيوريستيك گفته ميشود.
2- هيوريستيكها
هيوريستيكها عبارتند از معيارها، روشها يا اصولي براي تصميمگيري بين چند گزينه خطمشي و انتخاب اثربخشترين براي دستيابي به اهداف مورد نظر. هيوريستيكها نتيجه برقراري اعتدال بين دو نياز هستند: نياز به ساخت معيارهاي ساده و در همان زمان توانايي تمايز درست بين انتخابهاي خوب و بد.
يك هيوريستيك ميتواند حسابي سرانگشتي باشد كه براي هدايت يك دسته از اقدامات به كار ميرود. براي مثال، يك روش مشهور براي انتخاب طالبي رسيده عبارتست از فشار دادن محل اتصال به ريشه از يك طالبي نامزد انتخاب و سپس بو كردن آن محل. اگر بوي آن محل مانند بوي داخل طالبي باشد آن طالبي به احتمال زياد رسيده است. اين قاعده سرانگشتي نه تضمين ميكند كه تنها طالبيهاي رسيده به عنوان نامزد انتخاب شوند و نه تضمين ميكند كه طالبيهاي رسيده آزمايش شده، رسيده تشخيص داده شوند اما به هر حال اين روش، اثربخشترين روش شناخته شده است.
به عنوان مثالي ديگر از استفاده هيوريستيكها، يك استاد بزرگ شطرنج را در نظر بگيريد كه با انتخاب بين چندين حركت ممكن روبرو شده است. وي ممكن است تصميم بگيرد كه يك حركت خاص، اثربخشترين حركت خواهد بود زيرا موقعيتي فراهم ميآورد كه «به نظر ميرسد» بهتر از موقعيتهاي حاصل از حركتهاي ديگر باشد. به كارگيري معيار «به نظر ميرسد» خيلي سادهتر از تعيين دقيق حركت يا حركاتي خواهد بود كه حريف را مجبور به مات كند. اين واقعيت كه اساتيد بزرگ شطرنج همواره پيروز بازي نخواهند بود نشان دهنده اين است كه هيوريستيكهاي آنها انتخاب اثربخشترين حركت را تضمين نميكنند. نهايتاً وقتي از آنها خواسته ميشود كه هيوريستيك خود را تشريح نمايند آنها فقط توصيفي ناقص از قواعدي ارائه ميدهند و به نظر خود آنها، انجام آن قواعد از توصيف آنان سادهتر است.
خاصيت هيوريستيكهاي خوب اين است كه ابزار سادهاي براي تشخيص خطمشيهاي بهتر ارائه دهند و در حالي كه به صورت شرطي لازم، تشخيص خطمشيهاي اثربخش را تضمين نميكنند اما اغلب به صورت شرط كافي اين تضمين را فراهم آورند. بيشتر مسائل پيچيده نيازمند ارزيابي تعداد انبوهي از حالتهاي ممكن براي تعيين يك جواب دقيق ميباشند. زمان لازم براي يافتن يك جواب دقيق اغلب بيشتر از يك طول عمر است. هيوريستيكها با استفاده از روشهاي نيازمند ارزيابيهاي كمتر و ارائه جوابهايي در محدوديتهاي زماني قابل قبول داراي نقشي اثربخش در حل چنين مسائل خواهند بود (پيرل
4
  1984، 1-10).
3- انواع الگوريتمهاي هيوريستيك
در حالت كلي سه دسته از الگوريتمهاي هيوريستيك قابل تشخيص است:
(1)الگوريتمهايي كه بر ويژگيهاي ساختاري مسئله و ساختار جواب متمركز ميشوند و با استفاده از آنها الگوريتمهاي سازنده يا جستجوي محلي تعريف ميكنند.
(2)الگوريتمهايي كه بر هدايت هيوريستيك يك الگوريتم سازنده يا جستجوي محلي متمركز ميشوند به گونهاي كه آن الگوريتم بتواند بر شرايط حساس (مانند فرار از بهينه محلي) غلبه كند. به اين الگوريتمها، متاهيوريستيك گفته ميشود.
(3)الگوريتمهايي كه بر تركيب يك چارچوب يا مفهوم هيوريستيك با گونههايي از برنامهريزي رياضي (معمولاً روشهاي دقيق) متمركز ميشوند.
...