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