عنوان
حل مسئله‌ي فروشنده دوره‌گرد با استفاده از يکپارچه سازي تکنيک‌هاي بهينه‌سازي هوشمند و الگوريتم ژنتيک اکتشافي
نویسنده (گان)
عامري شهرابي,بهروز;نکوئي,سيد محمد
چکیده مقاله
روش¬هاي مختلفي براي حل مسئله¬ي فروشنده دوره‌گرد ارائه شده است، از جمله راه حلي مبتني بر الگوريتم ژنتيک، ولي در حالت کلي الگوريتم ژنتيک در حل مسئله¬هاي ترکيبي غالباً با همگرايي زودرس مواجه هستند، که ما در اين مقاله با بررسي و معرفي روش¬ها و عملگرهاي جديد به رفع اين مشکل پرداخته‌ايم. ايده¬ي ما مبني بر الگوريتم ژنتيک ترکيبي براي حل مسئله¬ي فروشنده دوره‌گرد مي‌باشد. روند اجراي الگوريتم ما چنين است که روش¬هاي مختلفي که در هر مرحله از الگوريتم، اعم از ايجاد جمعيت اوليه با الگوريتم¬هاي نزديک¬ترين همسايگي، حريصانه و ترکيب آن‌ها با الگوريتم ژنتيک و نيز استفاده از روش¬هاي اکتشافي براي عملگرهاي ترکيب و ¬جهش مورد بررسي قرار گرفته است. با افزودن و ترکيب الگوريتم جداساز و تکامل اين روش در دو جهت ساعتگرد و پاد ساعتگرد به الگوريتم ژنتيک سعي در بهبود جامعه داشته و در زمان¬هاي کاهش گوناگوني جمعيت، کروموزوم¬هاي مصنوعي با گوناگوني بالا ايجاد مي‌گردند، براي افزايش سطح گوناگوني به سيستم وارد نموده‌ايم. در طي اجراي برنامه گوناگوني کروموزوم‌هاي موجود مورد بررسي قرار گرفته و کروموزوم‌هاي يکسان با کروموزوم‌هاي مصنوعي جايگزين مي‌گردند. پياده سازي-ها، نتيجه¬ي بهبود الگوريتم ترکيبي بهينه شده را نسبت به الگوريتم¬هاي ژنتيک معمولي و ژنتيک ترکيبي اوليه و ثانويه نشان مي¬دهد.

متن کامل مقاله