برای اطلاع از آخرین مقالات علمی و اخبار کرونا(COVID-19) کلیک کنید

مشخصات مقاله

عنوان: 

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

نوع ارائه: پوستر
نویسنده: زارعي باقر,حنيفي عزيز,اصغري كيوان,ميبدي محمدرضا
 
 
 
عنوان همایش: كنفرانس ملي سالانه انجمن كامپيوتر ايران
نوع همایش:  انجمن هاي علمي
حامی:  انجمن کامپیوتر ایران، دانشگاه صنعتی شریف
زمان:  1386دوره 13
 
 
چکیده: 

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

 
کلید واژه: مساله فروشنده دوره گرد، آتوماتاي يادگير، الگوريتم ژنتيك، خوشه بندي
 
مقالات نشریه ای مرتبط: 
 
مقالات همایشی مرتبط: 
 
 
بازدید یکساله 170   pdf-file
 
آخرین های بلاگ
ورود به بلاگ مرکز اطلاعات علمی