حل یک مساله فاصله‌گذاری اجتماعی با استفاده از الگوریتم ژنتیک

منتشرشده در towardsdatascience به تاریخ ۲۶ سپتامبر ۲۰۲۰
لینک مقاله اصلی: Solving a Social Distancing Problem using Genetic Algorithms

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

مسئله

تابستان امسال (آگوست ۲۰۲۰) ، مردم Neo4j (پایگاه‌داده نمودار) چالش‌های هفتگی را پیشنهاد کردند تا با گراف حل شوند. چالش‌های پیش رو در هفته اول شامل یک فاصله‌گذاری اجتماعی است که قوانین آن به شرح زیر است:

• ۲۰ مهمان از ۱۱ خانواده دعوت می‌شوند تا در یک میهمانی شرکت کنند. داده‌ها یک فایل CSV با این قالب است:

شما می‌توانید آن‌ها را روی ۶ میز که هر کدام ۶ صندلی دارند قرار دهید؛ که در آن‌ها دو صندلی متوالی به فاصله یک متر از هم قرار دارند (ما میزها را دایره‌ای در نظر می‌گیریم)

• هر میز باید شامل مهمانانی از حداقل دو خانواده مختلف باشد.
• هر میز نباید بیش از دو مهمان از یک خانواده داشته باشد.
• مهمانان خانواده‌های مختلف باید حداقل دو متر از یکدیگر فاصله داشته باشند.

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

برای استفاده از الگوریتم‌های ژنتیک، بیایید بر روی اصول اصلی پشت این تکنیک تمرکز کنیم و ببینیم که چگونه این نوع الگوریتم ها می‌توانند به حل مسئله بالا کمک کنند.

اصول الگوریتم ژنتیک به طور خلاصه

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

برای هر فرد در جمعیت، یک تابع تناسب تعیین می‌کند که فرد چقدر به راه‌حل نزدیک است

یک فرآیند انتخاب برای ایجاد نسل بعدی راه‌حل‌های ممکن، با گرایش به سمت «بهترین افراد»، به معنی افرادی با بالاترین تناسب صورت می‌گیرد.

افراد تغییر می‌کنند، به این معنی که راه‌حل‌ها براساس برخی قوانین تغییر می‌کنند (به عنوان مثال: تعویض دو موقعیت) و اتفاق متقاطع رخ می‌دهد که اساسا برخی از بخش‌های یک فرد را با دیگری عوض می‌کند.

فرآیند تکراری دوباره از مرحله ۱ شروع می‌شود، تا زمانی که معیار توقف برآورده شود (تعداد تکرارها، تابع تناسب به آستانه داده‌شده می‌رسد …)

حال بیایید به مسئله فاصله‌گذاری اجتماعی بازگردیم.

فرمولاسیون مساله

یک راه‌حل برای ما لیستی با صندلی اختصاص‌یافته به هر مهمان خواهد بود. صندلی یک عدد صحیح است که مقدار آن برابر است با

برای مثال، صندلی ۲ در جدول ۴ متناظر با عدد صحیح ۴۲ است.

این کار تا زمانی که ما کم‌تر از ۱۰ صندلی در هر میز داشته باشیم خوب عمل می‌کند.

در نتیجه یک راه‌حل می‌تواند به شکل زیر نوشته شود:

مهمان با شاخص ۰ (میزبان) به میز ۱ (بر مبنای ۰ شاخص دهی شده) و صندلی ۴ اختصاص داده می‌شود. جداول معادل مانند زیر باز تولید می‌شوند:

• ۱ مقدار پیش‌فرض برای صندلی‌های خالی است.

حالا که ما یک نماینده برای هر راه‌حل داریم، بیایید تناسب آن را تعریف کنیم؛ یعنی «نزدیکی» آن به یک راه‌حل رضایت‌بخش.

تعریف تناسب

برای تعریف تناسب، ما باید هر یک از سه محدودیت تعریف‌شده در بخش تعریف مسئله را در نظر بگیریم، به علاوه این واقعیت که هر صندلی باید تنها یک‌بار اختصاص داده شود. هر بار که محدودیت نقض می‌شود، تناسب نیز متناسب با آن افزایش می‌یابد.

به هر صندلی یک مهمان اختصاص داده می‌شود

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

بعد از آن، می‌توانیم میزها را ایجاد کنیم، یک ماتریس دو بعدی که عناصر ij آن شامل خانواده مهمان برای صندلی j از میز i است. برای مثال:

هر میز باید حداقل از دو خانواده مهمان داشته باشد

برای هر میز(سطر)، ما می‌توانیم تعداد خانواده‌هایی که نشان داده می‌شوند را بشماریم و اگر کمتر از دو خانواده برروی آن میز وجود داشته باشد، تخلفات این جدول را تا ۱ افزایش دهیم:

هر میز نباید بیش از ۲ مهمان از یک خانواده داشته باشد

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

در نهایت پیچیده‌ترین بخش می‌آید: فاصله اجتماعی بین مهمانان از خانواده‌های مختلف.

افراد خانواده‌های مختلف باید حداقل ۲ صندلی جدا از هم نشسته باشند

برای محاسبه این محدودیت، می‌خواهیم از آبجکت‌های collections.deque استفاده کنیم که با یک متد عملی .rotate() همراه می‌شود. این روش عملی است چرا که ما یک شرایط مرزی برای مهمانانی که در صندلی‌های ۰ و ۵ در یک میز نشسته‌اند داریم؛ فاصله این دو صندلی ۱ متر است و نه ۵ متر. اول، ما ردیف (deque) را ایجاد می‌کنیم:

سپس، یک نمونه دیگر با همان فهرست ورودی ایجاد می‌کنیم، اما این ردیف سپس چرخانده می‌شود:

برای مثال، از جدول زیر شروع می‌کنیم:

متغیرهای td و tdr شامل موارد زیر خواهند بود:

از آنجا، ما می‌توانیم هر دو مورد ردیف را تکرار کنیم. اگر دو مقدار برابر با منفی ۱ باشند (یعنی هیچ مهمانی به آن صندلی اختصاص داده نمی‌شود) ، ما هیچ کاری انجام نمی‌دهیم. در غیر این صورت، بررسی می‌کنیم که دو مهمان که کنار هم نشسته‌اند از یک خانواده هستند، در غیر این صورت ما تناسب را افزایش می‌دهیم:

و تمام، تابع تناسب ما بالاخره آماده است!

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

کد و راه‌حل کامل

به منظور پیاده‌سازی بخش الگوریتم ژنتیک از مسئله، ما بر روی پکیج DEAP (الگوریتم های توزیع‌شده تکاملی در پایتون) پایتون تکیه می‌کنیم.

گام‌های اصلی در زیر باز تولید می‌شوند:

جزئیات بیشتر:

تولید اولیه جمعیت، از یک انتخاب تصادفی صندلی‌های NB_GUESTS (بین ۰ و NUM_TABLES * NUM_SEATS_PER_TABLE )

محاسبه تناسب با استفاده از تابع تعریف‌شده بالا

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

همانطور که در تصویر زیر نشان‌داده شده‌است:

تعیین: mutShuffleIndexes: آشفتگی شاخص‌ها را در هر راه‌حل با احتمال P_MUTATION قرار دهید.

سپس هسته الگوریتم به شکل زیر باز می‌شود:

تالار شهرت، بدون توجه به نسلی که به آن تعلق دارند، حاوی بهترین افراد از نظر عملکرد است. آن‌ها راه‌حل‌هایی هستند که ما به آن‌ها علاقه داریم.

پس از اجرای کد کامل (در دسترس در GitHub) ، ما می‌توانیم ببینیم که ۱۰ نفر از بهترین افراد از نظر عملکرد در سالن شهرت همگی دارای تناسب ۰ هستند؛ به معنی عدم نقض محدودیت. یکی از آن‌ها در اینجا باز تولید شده‌است:

می‌توانید ببینید که:

میز ۱ شامل مهمانانی از سه خانواده است، تنها یک مهمان از هر خانواده و همه آن‌ها با حداقل یک صندلی خالی از هم جدا شده‌اند.

همان مشاهده برای میز ۲، ۳ و ۶

میز ۴ شامل دو مهمان از دو خانواده (C و D) ، دو مهمان از هر خانواده است. جون و الیور کنار هم نشسته‌اند اما آن‌ها از یک خانواده هستند (C) بنابراین مشکلی ندارد، همین موضوع برای میلان و میا از خانواده D هم وجود دارد. هیچ مهمانی از خانواده C مستقیما نزدیک یک مهمان از خانواده D نشسته‌است، بنابراین آخرین محدودیت نیز برآورده می‌شود.

همین امر برای میز ۵ با اعضای خانواده K و J نیز صادق است.

در اینجا ما یک مسئله فاصله‌گذاری اجتماعی را با استفاده از قدرت الگوریتم های ژنتیک حل کرده‌ایم. شما می‌توانید دوستان خود را در یک مهمانی ملاقات کنید در حالی که خطرات مربوط به COVID19 را محدود می‌کنید!

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