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

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