نمايش پست تنها
قديمي ۱۰-۱۱-۱۳۸۸, ۰۳:۳۰ بعد از ظهر   #3 (لینک دائم)
Astaraki Female
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,306 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink يك روش تركيبي مبتني بر خوشه بندي براي حل مساله فروشنده دوره گرد با مقياس بزرگ

يك روش تركيبي مبتني بر خوشه بندي براي حل مساله فروشنده دوره گرد با مقياس بزرگ


خلاصه مقاله:

يكي از مسائل بسيار مهم در تئوري گراف ها، مساله فروشنده دوره گرد مي باشد كه يك مساله NP-Complete است. اكثر مسائلي كه مي توان انها را با مساله فروشنده دوره گرد مدل كرد، داراي مقياس خيلي بزرگ هستند كه الگوريتم هاي موجود قادر به حل انها در يك زمان قابل قبول نيستند. آتوماتاهاي يادگير و الگوريتم هاي ژنتيكي هر دو از ابزارهاي جستجو مي باشند كه براي حل بسياري از مسائل NP-Complete بكار برده ميشوند. در اين مقاله يك الگوريتم تركيبي (الگوريتم ژنتيك + آتوماتاي يادگير) مبتني بر خوشه چيني براي حل مساله فروشنده دوره گرد با مقياس بزرگ پيشنهاد شده است. اين الگوريتم ابتدا با استفاده از تكنيك خوشه بندي، مساله اصلي را به چند زير مساله با مقياس كوچك افراز كرده و سپس از دو روش الگوريتم هاي ژنتيكي و اتوماتاي يادگيري بطور همزمان براي جستجو در فضاي حالت و حل هر زير مساله استفاده مي نمايد، نشان داده شده است كه با استفاده همزمان از آتوماتاي يادگير و الگوريتم ژنتيك در فرايند جستجو، سرعت رسيدن به جواب افزايش چشمگيري پيدا ميكند و همچنين از بدام افتادن الگوريتم در حداقل هاي محلي جلوگيري مي نمايد. نتايج آزمايش ها، برتري الگوريتم تركيبي را نسبت به الگوريتم ژنتيكي و آتوماتاهاي يادگير نشان ميدهد و همچنين با استفاده از تكنيك خوشه بندي و اجراي الگوريتم تركيبي بطور همزمان بر روي هر خوشه – با يك سيستم چند پردازنده اي – مي توان زمان لازم براي حل مساله را به حداقل مقدار ممكن كاهش داد.

كلمات كليدي:

مساله فروشنده دوره گرد ، آتوماتاي يادگير ، الگوريتم ژنتيك ، خوشه بندي
فايل ضميمه
نوع فايل: pdf 461.pdf (492.0 كيلو بايت, 1630 نمايش)
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
850041503 (۰۳-۳۱-۱۳۸۹), Faa916 (۰۱-۹-۱۳۹۶), sam1983 (۰۲-۲۴-۱۳۹۵), Solsal (۰۵-۱-۱۳۹۰), ناشناس (۰۳-۲۱-۱۳۹۲), |مريم (۰۱-۱۶-۱۳۹۱)