آموزش مسأله فروشنده دوره گرد با الگوریتم ژنتیک

در دنیای امروز، مسأله بهینه‌سازی در انواع کسب و کار‌ها و به خصوص صنعت، کاربرد گسترده‌ای پیدا کرده است. بهینه‌سازی در واقع به مجموع فعالیت‌ها و راه کار‌هایی گفته می‌شود که با انجام آن‌ها، هزینه کلی فرآیند مورد نظر به کم‌ترین حالت ممکن کاهش و بازدهی به بیشترین حالت ممکن افزایش می‌یابد. توجه کنید که هزینه کلی یک پروسه یا فرآیند، به چیز‌های زیادی اطلاق می‌شود؛ مانند نیروی کار انسانی، دستگاه‌های مورد استفاده و هزینه کار آن‌ها و….

برای بهینه‌سازی پروژه‌های مختلف روش‌های بسیار زیادی طراحی و عرضه شده‌اند که می‌توان از آن‌ها استفاده کرد. یکی از این روش‌ها، الگوریتم‌هایی هستند که انواع مختلفی دارند. یکی از این الگوریتم‌ها، الگوریتم مسأله فروشنده دوره گرد با الگوریتم ژنتیک است که کاربرد‌های فراوانی نیز دارد. در ادامه این مطلب به توضیح و تفسیر این الگو خواهیم پرداخت.

تاریخچه مسأله فروشنده دوره گرد با الگوریتم ژنتیک چیست؟

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

کاربرد مسأله فروشنده دوره گرد با الگوریتم ژنتیک در کجا است؟

همان طور که گفتیم مسأله فروشنده دوره گرد با الگوریتم ژنتیک یک روش حل مسأله است که باعث بهینه‌سازی می‌شود. بنابراین در هر جایی که بحث مدیریت کار‌ها در میان باشد، مسأله فروشنده دوره گرد نیز کارآمد خواهد بود. از انواع کسب و کار‌ها و مواردی که مسأله فروشنده دوره گرد در آن‌ها به درد خواهد خورد، می‌توان به کارمندان برج‌های مراقبت، معماران، پروژه‌های بزرگ ساختمانی یا بیمارستانی و حتی شرکت‌ها و سازمان‌های دولتی مانند ثبت احوال هم اشاره کرد.

مثلاً فرض کنید که شهرداری سعی دارد، با انجام یک سری از فعالیت‌ها و اعمال یک سری تغییرات در جمع‌آوری زباله‌ها از سطح شهر در پاکسازی بهتر سطح شهر تلاش کند و هزینه‌های کلی را نیز کاهش دهد. در این جا یکی از روش‌هایی که می‌توان از آن‌ها استفاده کرد مسأله فروشنده دوره گرد با الگوریتم ژنتیک است؛ یا مثلاً یک شرکت ارتباطی می‌خواهد با انجام بهینه‌سازی ترافیک، کاربران خود را کاهش دهد و در صورت امکان به صفر برساند.

انجام پروژه الگوریتم ژنتیک

طرح کلی مسأله فروشنده دوره گرد با الگوریتم ژنتیک چگونه است؟

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

قوانین اصلی در مسأله فروشنده دوره گرد با الگوریتم ژنتیک چیستند؟

دو قانون اصلی و مهم در بحث مسأله فروشنده دوره گرد با الگوریتم ژنتیک وجود دارد که حتماً باید رعایت شوند:

۱- قانون اول این است که فروشنده حتماً باید از شهر‌های مورد نظر دقیقاً یک بار دیدن کند. در واقع به هیچ عنوان نباید از حتی یکی از این شهر‌ها چشم پوشی کرد، هم چنین نمی‌توان از هرکدام از این شهر‌ها بیش از یک بار نیز دیدن کرد.

۲- قانون دوم این است که در نهایت باید فروشنده را به شهر مبدأ که از آن شروع کرده است برگردانیم و در واقع مسافت کل بر این اساس محاسبه می‌شود.

مطلب پیشنهادی: الگوریتم کروسکال چیست؟

اصطلاحات رایح در الگوریتم ژنتیک در مسأله فروشنده دوره گرد چیستند؟

برای مسأله فروشنده دوره گرد، اصطلاحاتی توسط الگوریتم ژنتیک ایجاد شده‌اند که بعضی از رایج‌ترین آن‌ها را در ادامه توضیح خواهیم داد:

1. ژن: به هر کدام از شهر‌های مورد نظر مسأله یک ژن یا فرد گفته می‌شود که می‌توان آن‌ها را با متغیر‌هایی مانند x یا y نشان داد.
2. کروموزوم: به مسیر موجود بین دو شهر مشخص یک کروموزوم گفته می‌شود که همراه با مشخص کردن مختصات دو شهر مورد نظرنشان داده می‌شود.
3. جمعیت: به مجموعه‌ای از مسیر‌های ممکن، جمعیت گفته می‌شود.
4. والدین: گاهی نیاز به یک مسیر جدید وجود دارد که با استفاده از ترکیب دو مسیر موجود قبلی این مسیر ساخته می‌شود. در واقع این عمل در ژنتیک، تحت عنوان آمیزش شناخته می‌شود.
5. فیتنس یا تناسب: قطعاً مسیر‌های مختلفی برای فروشنده دوره گرد وجود دارد که ما با کمک تابع‌های مختلف می‌توانیم دریابیم که هر کدام از مسیر‌ها تا چه اندازه بهینه هستند و کدام یک از این مسیر‌ها بهینه‌تر هستند. در مسأله فروشنده دوره گرد در واقع بهینه‌ترین مسیر برای ما همان کوتاه‌ترین مسیر است که فرشنده می‌تواند در کمترین تایم ممکن آن را طی کند.
6. جهش: تعریف جهش در جمعیت به این صورت است که با انجام شدن یک تغییر تصادفی، یک تنوع غنی در جمعیت حاصل می‌شود. در مسأله فروشنده دوره گرد نیز، جهش تعریف مشابهی دارد به این صورت که با تغییر تصادفی دو شهر با یکدیگر، تنوع در مسیر‌های ممکن برای فروشنده دوره گرد به وجود می‌آید.
7. نخبه گرایی: نخبه گرایی همان طور که از نام آن مشخص است، یعنی تلاش برای منتقل کردن افراد نخبه و برتر یک جمعیت به نسل بعدی.

رویکرد الگوریتم ژنتیک برای حل مسأله فروشنده دوره گرد چگونه است؟

الگوریتم ژنتیک برای حل مسأله فروشنده دوره گرد اقداماتی را با ترتیبی خاص انجام می‌دهد:

۱- ایجاد جمعیت:

در اولین قدم، الگوریتم ژنتیک سعی می‌کند تا جمعیت مناسبی را به عنوان جمعیت اولیه یا نسل اول ایجاد کند که برای این کار طبق قوانین مسأله تابعی می‌سازد که بتواند این جمعیت اولیه را ایجاد کند. نکته قابل توجه در این مسأله این است که باید برای ایجاد ژن، به طور تصادفی ترتیب بازدید از هر شهر را انتخاب کنیم. در واقع این روش فقط برای ایجاد جمعیت اولیه و نسل یک به کار می‌رود و جمعیت‌های دیگری که در طی کار به آن‌ها احتیاج خواهیم داشت، توسط اصلاح نژاد و جهش تولید خواهند شد.

۲- ایجاد تابع برازندگی:

تابع برازندگی یا فیتنس، همان طور که از نام آن مشخص است به ما کمک می‌کند تا بین افراد جمعیت تولید شده، تمایز قائل شویم و آن‌ها را رتبه‌بندی کنیم در واقع این تابع به شبیه‌سازی (بقای بهترین‌ها) کمک خواهد کرد. در نهایت پس از انجام مرحله دوم، ما یک لیست مرتب شده از‌شناسه مسیر‌ها همراه با امتیاز‌های تابع برازندگی مرتبط با آن‌ها را در اختیار خواهیم داشت. نکته قابل توجه در این مرحله این است که تابع برازندگی که از آن استفاده می‌کنیم، باید سریع کار کند و اگر کند باشد در پروسه انجام کار، مشکل ایجاد می‌کند و حتی ممکن است که الگوریتم را از کار بیندازد.

مطلب پیشنهادی: الگوریتم گله اسب چیست؟

۳- تعیین فضای ترکیب:

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

4- تولید اولین نژاد جمعیت:

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

۵- انجام عملیات تولید مثل:

در این مرحله در واقع انتخاب‌هایی که کرده‌ایم در کنار یکدیگر قرار داده می‌شوند و نسل بعدی را ایجاد می‌کنند.

۶- پیاده‌سازی و اعمال جهش:

بدون اغراق می‌توان گفت که یکی از مهم‌ترین و اصلی‌ترین مراحل الگوریتم ژنتیک برای حل مسأله فروشنده دوره گرد، مرحله پیاده‌سازی و اعمال جهش است. اعمال جهش چندین نتیجه و پیامد مهم برای ما به دنبال می‌آورد که به صورت زیر هستند:

با اعمال عملیات جهش ما به مسیر‌های جدیدی دست پیدا می‌کنیم که با استفاده از این مسیر‌های جدید می‌توانیم سایر بخش‌های فضای راه حل را کشف کنیم. اعمال جهش از ایجاد همگرایی محلی در مسأله جلوگیری می‌کند و در واقع به مسیر‌های پیشنهادی، تنوع ویژه‌ای می‌بخشد.

۷– تکرار الگوریتم:

در این مرحله نوبت به این می‌رسد که تمام دست یافته‌های خود را در مراحل قبلی کنار هم بچینیم و یک نتیجه نهایی به دست بیاوریم. در این مرحله ما باید تکه کد‌های گفته‌شده را کنار هم بچینیم و عملکردی ایجاد کنیم که نسل جدیدی تولید کند. ابتدا با استفاده از RankRoutes مسیر‌ها را در نسل فعلی رتبه‌بندی کرده و سپس با اجرای تابع انتخاب، والدین بالقوه خود را تعیین می‌کنیم.

مطلب پیشنهادی: الگوریتم بهینه‌سازی فاخته چیست؟

مسأله فروشنده دوره گرد چند هدفه چیست؟

مسأله فروشنده دوره گرد چند هدفه در واقع نوع تعمیم یافته و پیچیده‌تری از مسأله فروشنده دوره گرد تک هدفه است. همان طور که از نام آن مشخص است، در مسأله فروشنده دوره گرد چند هدفه چند هدف به صورت هم زمان مد نظر هستند که همه آن‌ها باید ارزیابی و بهینه‌سازی شوند.

خلاصه:

بهینه‌سازی در دنیای امروز یک مسأله حیاتی است و همه از عوام گرفته تا مؤسسه‌ها و شرکت‌های بزرگ صنعتی و غیر صنعتی به دنبال آن هستند که کیفیت کار‌های خود را ارتقا ببخشند، هزینه‌های صرف شده خود را کم کنند و در زمان و نیروی کار صرفه‌جویی کنند. دست‌یابی به این اهداف به صورت هم زمان تقریباً تمامی کسب و کار‌ها از کوچک تا بزرگ را به سمت خود سوق داده است. در مبحث بهینه‌سازی، انواع مختلفی از روش‌ها وجود دارد که توسط متخصصان این رشته‌ها برای بهینه‌سازی یک پروسه به کار گرفته می‌شود.

یکی از انواع این روش‌ها که کارایی و محبوبیت زیادی نیز دارد، روش حل مسأله فروشنده دوره گرد با الگوریتم ژنیک است، در این روش در واقع فروشنده دوره گردی در نظر گرفته می‌شود که باید از تعداد مشخصی از شهر‌ها دیدن کند و محصولات خود را در آن‌ها بفروشد و در پایان به شهر مبدأ خود باز گردد. در واقع تلاش ما در این است که با پبدا کردن بهترین و بهینه‌ترین مسیر بین شهر‌های مختلف به فروشنده دوره گرد کمک کنیم تا در سریع‌ترین زمان ممکن و با صرف کم‌ترین هزینه و انرژی از این شهر‌ها عبور کند، به طوری که از هرکدام از شهر‌ها فقط و دقیقاً یک بار عبور کند.

الگوریتم ژنتیک برای حل مسأله فروشنده دوره گرد، مراحلی را طی می‌کند که در بالا به تفسیر آن‌ها را توضیح دادیم. همچنین جالب است بدانید که مسأله فروشنده دوره گرد به دو صورت تک هدفه و چند هدفه وجود دارد که در نوع چند هدفه هدف ما بهینه‌سازی چند هدف به صورت هم زمان است که البته برای حل این نوع مسأله فروشنده دوره گرد نیز می‌توان از الگوریتم ژنتیک کمک گرفت.