الگوریتم ژنتیک در مسیریابی وسایل نقلیه

  1. معرفی الگوریتم ژنتیک و مفاهیم اولیه آن
  2. بررسی مسئله مسیریابی وسیله نقلیه با الگوریتم ژنتیک

محققان با مشاهده خصوصیات سیستم های طبیعی و تامل در این که طبیعت چگونه مشکلات خود را حل می کند به فکر تقلید از روش های طبیعی در حل مسایل پیچیده و طراحی سیستمها افتادند.
ایده اصلی الگوریتم ژنتیک بر پایه نظریه تکامل داروین در سال ۱۸۵۹ شکل گرفت.

در سال دانشمندی در دانشگاه میشیگان به نام Holland John ایده استفاده از الگوریتم ژنتیک را در بهینه سازی مهندسی مطرح کرد.

مفاهیم اولیه

 ژن: عناصر تشکیل دهنده یک کروموزوم که معمولا عدد یا کلمه یا حتی دستورات برنامه نویسی می باشد. ژن یکی از متغیرهای تصمیم یا یک قسمتی از متغیرهای تصمیم است.
کروموزوم: به رمز درآمده یا کد شده یک جواب یا قسمتی از جواب را کروموزوم می گویند.به عنوان مثال، یک کروموزوم باn ژن می تواند به شکل زیر باشد:

b1b2b3… bn

مکان: موقعیت هر ژن در کروموزوم
جامعه (population): به مجموعه ای از کروموزوم ها که از بین آنها selection صورت می گیرد جامعه گفته می شود.
نسل (generation): هر جایگزینی از جامعه قدیمی با جامعه جدید هر تکرار الگوریتم

مراحل الگوریتم ژنتیک

  • تعیین روش کدگذاری encoding توسط برنامه نویس
  • تولید جامعه اولیه به اندازه N
  • محاسبه ی تابع برازندگی function fitness هر کروموزوم در جامعه
  • ایجاد جامعه جدید (عمل تولید نسل (reproduction )): N بار قدم های زیر را انجام دهید:
  •          انتخاب دو کروموزوم والد (یا بیشتر) از جامعه فعلی با استفاده از عملگر انتخاب (selection)
  •          اعمال عملگر تقاطع (crossover) روی والدین با احتمال وقوع pc)crossover of probability( و ایجاد فرزند
  •          اعمال عملگر جهش (mutation) روی فرزندان با احتمال وقوع( pm (mutation of probability
  •          اضافه کردن فرزند جدید به جامعه
  • انتخاب جامعه جدید و جایگذاری جامعه جدید با جامعه فعلی با استفاده از عملگر انتخاب
  •  آزمودن شرایط توقف و برگرداندن بهترین جواب در صورت توقف
     
  • بازگشت به قدم ۳

untitled-1

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

  • ایجاد جمعیت توسط گروهی از کروموزوم ها
  • ارزیابی کروموزوم ها
  • انتخاب دو کروموزوم بر اساس مقدار برازندگی
  • تولیدمثل یک فرزند یا بیشتر
  • جهش دادن فرزندان به صورت تصادفی
  • تکرار این مراحل تا رسیدن به معیار توقف (بسته به خواست برنامه نویس)

کد گذاری Encoding
الگوریتم ژنتیک به جای کار بر روی متغیرهای مساله، با کد شده جواب ها یعنی کروموزوم ها سر و کار دارد. سایر گام ها شدیدا تحت تاثیر گام کدگذاری می باشند.

انواع روشهای نشان دادن کروموزوم ها:

unti5563tled-1

مفهوم Representation (تبدیل متغیرها به کروموزوم ها)

un818181titled-1

روش های ایجاد جامعه اولیه

  • روند برای ایجاد جامعه اولیه
  • روش های ابتکاری

عملگرهای الگوریتم ژنتیک (operators GA):

  • عملگر انتخاب (selection): انتخاب کروموزوم های والد برای ادغام
  • عملگر تقاطع (crossover): ادغام کروموزوم های انتخاب شده
  • عملگر جهش (mutation): تغییر ژنتیکی فرزندان

عملگر انتخاب (selection)

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

برخی از انواع عملگرهای انتخاب

  • انتخاب برترین ها (Elitist): مناسب ترین کروموزوم هر جامعه انتخاب می شود.
  • انتخاب چرخ رولت (wheel Roulette): کروموزومی که مقدار تابع برازندگی بیشتری داشته باشد شانس بیشتری برای انتخاب شدن دارد.
  • انتخاب رقابتی (Tournament): زیر مجموعه هایی از یک جامعه انتخاب می شود و اعضای آن زیر مجموعه ها با هم رقابت می کنند و سرانجام فقط یک عضو از هر زیر  گروه برای تولید انتخاب می شود.

unt99999itled-1

عملگرتقاطع یک نقطه برش crossover point-1

  • انتخاب تصادفی یا غیر تصادفی یک نقطه روی کروموزوم والدین
  • شکستن والدین از این نقطه
  • فرزندان، سر را از یک والد و دم را از دیگری به ارث می برند.

untitl555555ed-1

عملگرتقاطع با دو نقطه برش crossover point-2

un77777titled-1

تقاطع مطابقت جزئی (PMX) Crossover Matched Partially

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

اگر دو رشته مقابل را داشته باشیم :

un959595titled-1

که بطور بدیهی غیر مجاز (legal not) هستند چون V1 شهر ۵ یا ۷ را بازدید نمی کند و شهرهای ۳ و ۴ را دوبار بازدید می کند. بطور مشابه V2 شهرهای ۳ و ۴ را نمی بیند و شهرهای ۵ و ۷ را دوبار می بیند.

ادامه تقاطع مطابقت جزئی

u10101010ntitled-1

ژن های ۳ و ۴ و ۵ و ۶ و ۷ بین دو نقطه تقاطع واقع شده اند.
انتخاب دوتایی ژن ها بر مبنای صعودی بودن شماره و عدم واقع شدن هر دو ژن در یکی از سه منطقه برش داده شده است.

جهش

 

  • هر فرزند ممکن است دچار جهش ژنتیکی شود.
  • جهش ژنتیکی با احتمال مساوی روی تمام ژن های هر کروموزوم نوزاد رخ می دهد.
  • احتمال وقوع جهش روی یک ژن را نرخ جهش نامند.
  • نرخ جهش را با pm نشان می دهند که در بازه [۲٫۰,۰۱٫۰] قرار می گیرد.

un77777744455itled-1

معیارهای مختلف توقف الگوریتم ژنتیک

– بهترین جواب را بعد از اجرای تعداد مشخصی تکرار تغییر ندهد .
– میانگین برازندگی جوابهای موجود در جمعیت جاری همان برازندگی بهترین جواب یا بسیار نزدیک به آن باشد.
– می توانیم از پیش قرارداد کنیم که الگوریتم به تعداد بار مشخصی اجرا شود.

نکته: معمولا روتین های توقف مختلف است و بستگی به پیچیدگی و چگونگی مساله دارد.

نقاط قوت الگوریتم ژنتیک

  • موازی بودن:
    از آنجایی که الگوریتم ژنتیک چندین نقطه شروع دارد، در یک لحظه می تواند
    فضای مسئله را از چند جهت مختلف جستجو کند. اگر یکی به نتیجه نرسید سایر راه ها را ادامه می دهیم.
  • الگوریتم های دقیق در حل مسایل بزرگ بسیار کند عمل می کنند.
  • در مسایل hard-NP گاه نمی توان از راه های دقیق به جواب بهینه رسید.

نقاط ضعف الگوریتم ژنتیک

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

برای انتخاب تابع مناسب برای برازندگی پارامترهای زیر دخیلند:
۱) اندازه جامعه
۲) نرخ جهش و تقاطع
۳) قدرت و نوع انتخاب

نارس بودن

  • اگر یک کروموزوم فاصله اش با سایر کروموزوم های نسل اش زیاد باشد (خیلی بهتر از بقیه باشد) و خیلی زود دیده شود (ایجاد شود) ممکن است محدودیت ایجاد کند و راه حل را به سوی جواب بهینه محلی سوق دهد.
  • این اتفاق معمولاً در جمعیت های کم اتفاق می افتد.
  • روش انتخاب رقابتی بر این مشکل غلبه می کند.

الگوریتم ژنتیک در مسیریابی وسیله نقلیه

  • الگوریتم ژنتیک به عنوان یکی از پرکاربردترین روشهای حل VRP مطرح بوده است.
  • اولین کار صورت گرفته در زمینه بررسی VRP با الگوریتم GA توسط تانگیا و همکاران (۱۹۹۱) صورت گرفت که مسئله VRPTW را با الگوریتم GA بررسی کردند. مدل ارائه شده آنها GIDEON نام داشت.
  • برگر و همکاران (۲۰۰۳)، GA را برای حل VRPTW به کار بردند. این الگوریتم در مقایسه با بهترین حالت الگوریتم search Tabu قابل رقابت است.
  • حالتی از الگوریتم ژنتیک که در VRP کاربرد دارد الگوریتم ژنتیک مبتنی بر ترتیب است که تمامی کروموزوم ها، جایگشت یک لیست هستند؛ یعنی جوابها به صورت توالی کدبندی می شوند.
  • برخی از مسائل بررسی شده با الگوریتم ژنتیک مبتنی بر ترتیب:
    VRPTW
    TSP
    Bin Packing
     مسائل جایابی

یک کروموزوم (جواب) در VRP

  •  تعداد وسایل نقلیه
  •  مشتریانی که هر مسیر شامل می شود
  •  ترتیب ملاقات برای هر مسیر را مشخص کند.

untitlwwwwed-1

یک مثال برای تابع برازندگی

un12121212titled-1untitled-12222222

عملگرهای تقاطع سنتی برای الگوریتم ژنتیک مبتنی بر ترتیب

ویتلی و همکاران  و استارکودر و همکاران

  • ترکیب مجدد یال Recombination Edge
  • تقاطع ترتیب ۱ ۱ Crossover Order
  • تقاطع ترتیب ۲ ۲ Crossover Order
  • PMX
  • تقاطع حلقه Crossover Cycle
  • تقاطع موقعیت Crossover Position

تقاطع ترتیب ۱

untitle121ddddd-1

یک الگوریتم عملگر تقاطع جدید

  • برای هر فرد I1 از مجموعه انتخاب شده S تکرار کنید:
  • به صورت تصادفی فرد دیگری از (S(I2 انتخاب کنید.
  • از I2 به صورت تصادفی، زیرمسیر SR را انتخاب کنید: {an,…,a2,a1}
  • مشتری c را که به SR متعلق نیست و از لحاظ جغرافیایی به a1 نزدیکتر است بیابید.
  • SR را در I1 به گونه ای جای دهید که a1 درست بعد c قرار گیرد.
  • از I1 اصلی تمامی مشتریان تکراری را که در SR نیز ظاهر شده اند حذف کنید که نتیجتا فرزند D به عمل می آید.

فرض کنید مشتری ۶ نزدیکترین مشتری به مشتری ۱۰ است. به این جهت {۷،۴،۱۰} جدا می شود و پس از مشتری ۶ وارد یکی از مسیرهایی که به I1 تعلق دارد می شود.

untitlwdwdwdwded-1

ویژگی های عملگر تقاطع در VRP

قسمتی از اطلاعات والدین را به فرزندان منتقل می کند. توجه شود که این فرایند تعداد وسایل نقلیه را زیاد نمی کند بلکه ممکن است چندین مسیر را حذف کند.

یا

نه تنها مشتری های یک مسیر را با مسیر دیگر معاوضه می کنند بلکه تعداد وسایل نقلیه را هم بهبود می دهد (بهینه می کند).

عملگر جهش

  • فرزندان به عمل آمده از تقاطع می توانند مورد عمل جهش واقع شوند. ۴ عملگر جهش مطرح است:
    ۱) وارون سازی (inversion)
    ۲) جابجایی (displacement)
    ۳) درج (insertion)
    ۴) معاوضه (swap)
    تمامی عملگرهای جهش ذکرشده، احتمال کاربرد خاص خود را دارند.
  • وارون سازی یک زیرمسیر در نظر می گیرد و ترتیب مشتریان ملاقات شده ای که به آن زیرمسیر تعلق دارند را وارون می کند.

۱۲۳۴۵ → ۱۲۵۴۳

  • جابجایی یک زیرمسیر انتخاب می کند و آنرا به مکان دیگری که به صورت درونی )intra( یا بینی )inter( می تواند جابجا کند وارد می کند )قسمت انتخاب شده می تواند هم در همان مسیر و هم در مسیر
    دیگری وارد شود(.

۱۲۳۴۵۶۷ → ۱۲۶۳۴۵۷

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

uwwwww1111ntitled-1

عملگر معاوضه دو مشتری انتخاب می کند و جای آنها را با هم تعویض می کند. این دو مشتری می توانند متعلق به یک مسیر یا مسیرهای متفاوت باشند. همانند  عملگر قبلی ممکن است مسیر با توالی جدیدی ایجاد شود (احتمال این رخداد به همانگونه محاسبه می شود).

untitlwwww2222ed-1

معاوضه و وارون سازی توانایی حذف و اضافه کردن تعداد وسایل نقلیه برای یک کروموزوم را ندارند. از سوی دیگر، درج و جابجایی قادر به بهبود مسیرها هستند.

untsssssssssitled-2

2178

پایه‌ریزی یک منبع آموزشی و علمی فارسی هدفی است که لحظه‌ای از آن غافل نبوده‌ایم. (فوق لیسانس رشته علوم کامپیوتر - پردازش تصویر)

ارسال دیدگاه

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

توسط
تومان