حل مسیله فروشنده دوره گرد با الگوریتم مبتنی بر اجتماع

حل بسیاری از مسایل پیچیده بدون استفاده از روشهای بهینه سازی اگر غیرممکن نباشد امری دشوار و پرهزینه است. هدف بهینهاز سازی یافتن بهترین جواب قابلقبول با توجه به محدودیتها و نیازهای مساله است. امروزه محققین سعی دارند تا با استفاده از روشهای نوین در کمترین زمان ممکن مسایل بهینه سازی را حل نمایند. بسیاری از این روشها منجر به تولید الگوریتمهای فرایافتاریی میشود که الهام گرفته از طبیعت یا رفتار انسان بوده و بر اساس یکی از شیوه های گوناگون جستجوی تصادفی عمل می کنن د.یکی از مهمترین و کاربردیترین مسایل بهینهسازی ترکیباتی که از لحاظ سخت بودن همیشه مورد اشاره قرار میگیرد، مساله فروشنده دوره گرد است. این مساله حتی در ابعاد متوسط نیز نمی تواند توسط روشهای معمولی بهینهسازی حل شود، بنابراین نیاز به الگوریتمهایی است که بتوانند با استفاده از روشهای نوین به حل اینگونه مسایل بپردازند. یکی از الگوریتمهای نوظهوری که در بهینه سازی چنین مسایل پیچیده تواند مورای می د استفاده قرار گیرد الگوریتم مبتنی بر اجتماع است که از دو علم ریاضی و رفتار اجتماعی انسان برای حل مسایل کمک می گیرد .از آن جهت که الگوریتم مبتنی بر اجتماع از ترکیب الگوریتم ژنتیک و الگوریتم رقابت استعماری تشکیل شده که در هر تکرار الگوریتم، خود را بهینهسازی میکند و معیار آن کاهش هزینه به وسیله جابه جایی افراد است، لذا به دلیل تشابه با مساله فروشنده دوره گرد که معیار بهینگی آن نیز کاهش هزینه تور به وسیله جابهجایی شهرها میباشد، الگوریتم مبتنی بر اجتماع ، جهت حل این مساله انتخاب شده است . در این مقاله سعی شده است با پیاده سازی این الگوریتم و استفاده از آن در حل مساله فروشنده دوره گرد و همچنین مقایسه آن با الگوریتمهای فرایافتاری دیگری که در حل مساله فروشنده دوره گرد به کار گرفته شده است، کارایی این الگوریتم در حل مساله فروشنده دوره گرد را نسبت به روشهای موجود نشان دهد . نتایج حاصل از پیادهسازی الگوریتم مبتنی بر اجتماع نسبت به سایر الگوریتم های مشابه، نشان دهنده کارایی مناسب این الگوریتم در حل ابعاد بزرگ مساله فروشنده دوره گرد است .

Keywords:

بهینهسازی , فروشنده دوره گرد , الگوریتم مبتنی براجتماع , الگوریتم رقابت استعماری