اشتراک گذاری یک تجربه : الگوریتم ژنتیک برای مبتدیان – بخش چهارم( بخش آخر)

مسائلی وجود دارند که الگوریتم های دقیق آنها مدت زمان بسیار زیادی طول می کشد تا به جواب برسد .

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

مساله فروشنده دوره گرد یکی از این مسائل است .تا بحال کسی نتوانسته است الگوریتم سریعی ( الگوریتم زمانی چند جمله ای) برای آن پیدا کند ، البته کسی هم نتوانسته است وجود نداشتن چنین الگوریتمی را اثبات کند.

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

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

در ادامه مطلب ، بخش چهارم ( بخش آخر) از این مطالب را بخوانید .

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

هدف در این مساله پیدا کردن کوتاه ترین مسیر برای یک فروشنده دوره گردی است که باید از n شهر بگذرد .

این مساله در بخش دوم مطالب ما معرفی شد .

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

سوال اول : کروموزوم ها و ژن ها چگونه ساخته می شوند ؟

جنبه نظری :

در مساله فروشنده دوره گرد ، هر شهر با مختصات شهر که به عنوان ورودی مساله داده شده است مشخص می شود . این مختصات همان طول و عرض جغرافیایی شهر هستند .

هر راه حل مساله ، باید شامل تمام شهر ها باشد .( فروشنده دوره گرد باید از تمام شهرها عبور کند )

پس اگر به عنوان مثال مختصات ۱۰ شهر را داشته باشیم که از شهر یک تا شهر ۱۰ نامگذاری شده باشند، یک کروزموزوم می تواند به صورت زیر باشد :

جنبه عملی :

در ابتدا شما باید بدانید که کروموزوم های ما از اجزای کوچکتری به نام ژن ها ساخته می شوند . پس باید بتوانیم کلاسی برای وارد کردن و ذخیره شهرها داشته باشیم . این کلاس در برنامه ما City  نام دارد . آن را پیدا کنید و نگاهی به متد ها و خصوصیات آن کنید .

کلاس City دو خصوصیت (Property) مهم به نام های x و y دارد که همان طول و عرض نقطه شهر هستند .

هر جا که نمونه ای از شهر ایجاد کنیم این مقادیر باید به عنوان ورودی ارسال شوند . به عنوان مثال :

City city1 = new City(60 ,12 )

شما می توانید هر چند تا شهر که می خواهید توسط این کلاس ایجاد کنید .( مانند روش بالا)

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

حتما شما هم در موبایل خود آهنگ های متنوعی دارید . برای اینکه آهنگ های دلخواه خود را در یک جا داشته باشید چه کار می کند ؟ بله ، یک Playlist درست می کنید . اینجا هم ، TourManager دقیقا همان کار PlayList را انجام می دهد .

نگاهی به کلاس TourManager کنید . متدها و خصوصیات این کلاس همه از نوع Static تعریف شده اند. کلاس های ایستا قابل نمونه سازی نیستند . این کلاس مشخصه ای به نام distinationCities دارد . این مشخصه یک لیست می باشد که شهر ها در آن قرار می گیرند . اگر تعداد شهرهای ورودی از ابتدا مشخص باشد می توانستیم از آرایه استفاده کنیم .

این کلاس متدهای برای وارد کردن شهر جدید به لیست(addCity) ، دریافت یک شهر مشخص (getCity) و چاپ مختصات شهر ها (toString) دارد .

تا کنون توانستیم شهر ها را ایجاد کنیم و داخل یک لیست به صورت مرتب قرار دهیم . حالا باید بتوانیم کروموزوم بسازیم . این کار توسط کلاس Tour انجام می شود.

کلاس Tour هم مثل کلاس TourManager در واقع یک لیست به همراه متدها و خصوصیات مختلف است . منتها چون قرار است کروموزوم بسازیم ، این کلاس به صورت ایستا تعریف نشده است ،پس قابل نمونه سازی است .

نگاهی به کلاس Tour کنید . این کلاس مشخصه ای (Property) به نام tour دارد . tour یک لیست است که عناصر آن از نوع شهر هستند.

متد اصلی این کلاس که باید به آن توجه کنید generateIndividual است . این متد ، سات کروموزوم را به عهده دارد . ابتدا تمام شهرهای واقع در TourManager به صورت مرتب به لیست tour وارد می شوند ، تا اینجای کار این لیست دقیقا مانند TourManager است . در ادامه این لیست توسط shuffleTour بر می خورد .

( لیست موسیقی خود را در تلفن همراه با نام PlayList به یاد آورید که بازدن دکمه Shuffle تبدیل به لیستی با همان آهنگ ها ولی با ترتیب متفاوت خواهد شد )

هر بار که این تابع فراخوانی شود یک کروموزوم جدید ساخته می شود .

سوال دوم ) چگونه یک جمعیت اولیه از کروموزوم ها ایجاد کنیم ؟

جنبه نظری :

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

جنبه عملی :

برای ساخت جمعیت و عملیات مربوط به آن کلاس Population را ساخته ایم .

هر نمونه ای از کلاس Population را می توان به عنوان آرایه ای از تورها در نظر گرفت . این کلاس یک مشخصه (Property ) مهم و یک متد (Method) مهم دارد .

مشخصه مهم آن ، آرایه ای است به نام toursArray که همانطور که از نامش پیداست آرایه ایست از تور ها ( توجه کنید که هر تور آرایه ای از شهر ها بود )

Tour[] toursArray;

متد مهم آن ، متد سازنده کلاس به نام Population است  .کار این متد این است که به تعداد مشخصی کروموزوم می سازد و به ترتیب آنها را در خانه های آرایه toursArray ذخیره می کند .

این متد دو پارامتر هم دارد  .

پارامتر اول اندازه جمعیت (population_Size)  و پارامتر دوم مقدار دهی اولیه (initialize) که یک پارامتر منطقی است .

به این ترتیب ، به عنوان مثال برای ایجاد جمعیتی به اندازه ۵۰ کروموزوم باید از کد زیر استفاده کنیم :

Population pop = new Population(50, true) ;

سوال سوم ) تابع برازش برای مساله فروشنده دوره گرد چیست ؟

جنبه نظری :

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

اصولا الگوریتم ژنتیک برای حل مسائل ماکزیمم (بیشینه سازی) مناسب است  .  بنابراین برای حل مسائل مینیمم سازی مثل مساله فروشنده دوره گرد باید آن را توسط یک سری تبدیل ها به فرم ماکزیمم تبدیل کنیم .

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

فرض کنیم ABCD یک تور ما باشد که شامل ۴ شهر است با داشتن مختصات شهر ها می توانیم فاصله شهر A تا B و سپس B تا C و سپس C تا D را و D تا A را محاسبه کنیم و درنهایت مجموعه این فواصل عدد مشخصی برای هر تور است . معکوس این عدد را می توان به عنوان خروجی تابع برازش در نظر گرفت .

توجه : فاصله دو نقطه A و B را می توان با داشتن مختصات دو نقطه از فرمول ساده زیر به دست آورد :

جنبه عملی :

دوباره به کلاس Tour بر می گردیم . این کلاس غیر از متدهای قبلی دو متد مهم دیگر هم دارد .

 متد getDistance :

کاری که این متد انجام می دهد این است که مجموع فواصل شهرها را به همان ترتیبی که در تور قرار گرفته اند محاسبه می کند . برای این کار از یک حلقه for استفاده کرده ایم  و تا انتهای تور فاصله شهر ها را دو تا دوتا محاسبه می کنیم و در یک متغیر به نام distance نگه می داریم و در انتها عدد حاصل را برمی گردانیم .

متد getFitness : ابن تابع همان تابع برازش ماست . این تابع ، ابتدا تابع قبلی یعنی getDistance را فراخوانی می کند و سپس معکوس آن را برمی گرداند . اما چرا معکوس ؟ چون می خواهیم هر چه خروجی تابع برازش بیشتر باشد برازندگی کروموزوم ما بهتر باشد فرض کنید برازندگی یک کروموزوم ۰/۰۱  و برازندگی کروموزوم دیگر ۰/۱ باشد ، آن کروموزومی که برازندگی بالاتری داشته یعنی ۰/۱ پس مخرج کوچکتری هم داشته است .

سوال چهارم ) چگونه یک جمعیت جدید از کروموزوم ها را بسازیم  ؟

جنبه نظری : جمعیت جدید را از جمعیت قبلی و با کمک مجموعه ای از عملگر ها می سازیم .

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

در انتها نوبت به عمل جهش می رسد . عمل جهش با درصد پایینی فراخوانی می شود . به این ترتیب فقط تعداد اندکی از کروموزوم ها شامل پدیده جهش می شوند.

جنبه عملی :

کلاس GA را برای ایجاد یک نسل جدید به کمک عملگرهای مخصوص الگوریتم ژنتیک ساخته ایم .

این کلاس فقط یک متد عمومی دارد که شما می توانید آن را فراخوانی کنید . این متد همان متد سازنده کلاس است  :

public Population makeGeneration(Population pop)

همانطور که متوجه شده اید این متد یک پارامتر ورودی دارد که همان جمعیت قبلی است و خروجی این متد هم جمعیت جدیدی از نوع Population است .

اما کاری که این متد انجام می دهد چیست ؟

این متد ابتدا یک جمعیت جدید ایجاد می کند :

Population newPopulation = new Population(pop.populationSize () , false) ;

پارامتر false باعث ایجاد یک جمعیت خالی و به پارامتر جمعیت ورودی می شود . سپس بهترین کروموزوم جمعیت فعلی را به کمک تابع getFittest به دست می آورد .این کروموزوم که همان نخبه جمعیت قبلی است به عنوان اولین عنصر به جمعیت جدید اضافه می شود .

newPopulation.saveTour(0 , pop.getFittest( ) ) ;

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

سوال پنج )  عملگر انتخاب در مساله فروشنده دوره گرد ، چیست ؟

 جنبه نظری :

عملگر انتخاب از بین کروموزوم های موجود ، تعدادی کروموزوم را برای تولید مثل انتخاب می کند . سه نوع مهم عملگر انتخاب عبارتند از روش چرخ رولت، روش رتبه بندی و روش مسابقه ای یا تورنمنت

عملگر انتخاب ما در حل مساله فروشنده دوره گرد از نوع انتخاب تورنمنت (Tournament Selection) می باشد . در این روش تعداد کمی از کروموزوم ها (مثلا ۵ تا ) به صورت تصادفی انتخاب می شوند و آن کروموزومی که از همه برازنده تر است ( در بین این ۵ تا) برنده مسابقه شده برگردانده می شود .

جنبه عملی :

کلاس GA را دوباره مرور کنید . در انتهای کلاس یک متد به نام tournamentSelection  وجود دارد. این متد همان عملگر انتخاب ما می باشد.

 private Tour tournamentSelection(Population pop)

این متد یک پارامتر ورودی به نام pop دارد که همان جمعیتی است که می خواهیم عمل انتخاب را روی آن انجام دهیم .

در این متد ابتدا یک جمعیت کوچک به اندازه ۵ و خالی از کروموزوم ساخته می شود .

Population tournament = new Population(tournamentSize, false) ;

حالا این جمعیت را با انتخاب تورهای تصادفی از جمعیت ورودی pop پر می کنیم .

در انتها برازنده ترین تور را به دست آورده و به عنوان خروجی برمی گردانیم.

  Tour fittest = tournament . getFittest ( ) ;

سوال ششم )چگونه عمل تقاطع در مساله فروشنده دوره گرد صورت می گیرد  ؟

جنبه نظری :

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

دو کروموزوم A و B را در نظر بگیرید . (اندازه هر کروموزوم را به عنوان مثال ۵ بگیرید)

اگر از تقاطع دو نقطه ای استفاده کنیم باید دو خانه به صورت تصادفی کروموزوم بالایی انتخاب کنیم . مثلا خانه های ۳ و ۵ . حالا فرزند خانه های ۱ و ۲و ۶ را از پدر به ارث می برد و خانه های بعدی را به ترتیب از عناصری که در مادر هستند و آنها را ندارد به ارث می برد  :

ما در پیاده سازی خود از روش دو نقطه ای استفاده می کنیم .

جنبه عملی :

دوباره کلاس GA را مرور می کنیم . این کلاس دارای متدی به نام crossover است  . این متد همان عملگر تقاطع و البته از نوع دو نقطه ای است  :

private Tour crossover(Tour father, Tour mother)

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

این متد ابتدا یک فرزند که باید از نوع Tour باشد می سازد :

 Tour child = new Tour() ;

دو نقطه به صورت تصادفی از تور پدر پیدا می کند . این دو نقطه startPos و endPos هستند .

حالا نوبت به پر کردن خانه های تور فرزند است . تمامی شهر هایی (ژن هایی) که در فاصله startPos و endPos در تور پدر قرار دارند به تور فرزند منتقل می شوند . این کار توسط یک حلقه for انجام می شود .

if (i >= startPos && i <= endPos) {
child.setCity( i , father.getCity ( i ) )  }

حالا در یک حلقه for دیگر ، تور مادر را پیمایش می کنیم.اولین شهری از تور مادر که در تور فرزند نبود را در اولین خانه خالی تور فرزند قرار می دهیم . این کار را ادامه می دهیم تا تور فرزند پر شود .

تور فرزند را به عنوان خروجی برمی گردانیم.

سوال هفتم )چگونه عمل جهش در مساله فروشنده دوره گرد صورت می گیرد  ؟

جنبه نظری :

 در طبیعت جهش فرآیندی است که در آن یک ژن از کروموزوم به صورت تصادفی تغییر می کند .
عمل جهش با نرخ جهش پایینی انجام می شود در اینجا این نرخ را برابر ۰/۰۱۵ در نظر می گیریم . حالا کافی است یک عدد تصادفی ایجاد کنیم اگر این عدد کمتر از نرخ جهش بود عمل جهش روی کروموزوم را انجام می دهیم والا خیر .

جنبه عملی :

دوباره باید سراغ کلاس GA برویم . این کلاس متد دیگری به نام mutate دارد . این متد همان عملگر جهش ماست :

private void mutate (Tour tour)

این متد یک پارامتر ورودی به نام tour و از نوع Tour دارد .

عمل جهش روی ژن ها انجام می شود پس برای هر شهر (ژن ) موجود در تور کارهای زیر را انجام می دهیم :

 ابتدا یک عدد تصادفی ایجاد می کنیم . اگر کمتر از نرخ جهش ما بود ، یک شهر(ژن )دیگر به صورت تصادفی انتخاب می کنیم ( عدد خانه مربوطه آن را tourPos2 می نامیم)  شهر های این دو خانه را پیدا می کنیم .

City city1 = tour.getCity(tourPos1);
City city2 = tour.getCity(tourPos2);

شهرهای دو خانه را جابه جا می کنیم :

tour.setCity(tourPos2, city1);

tour.setCity(tourPos1, city2);

سوال هشتم )چگونه جواب بهینه را در مساله فروشنده دوره گرد به دست آوریم  ؟

کلاس اصلی ( کلاس form1) برنامه را مرور کنید.

برنامه ابتدا یک جمعیت اولیه ایجاد می کند و سپس بهترین کروموزوم این جمعیت را چاپ می کند .

Population pop = new Population(50, true);

حالا توسط یک حلقه تکرار ، ۱۰۰نسل جدید ایجاد می کنیم . در هر بار بهترین کروموزوم آن جمعیت را چاپ می کنیم .

 for ( int i = 0 ; i < 100 ;  i++) {
pop = myGA.makeGeneration( pop ) ; }

پاسخ نهایی مساله بهترین کروموزوم جمعیت ۱۰۰ ام خواهد بود .

برنامه برای دانلود :

فایل فشرده برنامه را از اینجا دانلود کنید. آن را از حالت فشرده به کمک برنامه winrar خارج کنید . حالا فایل GeneticAL.sln را از پوشه مربوط به برنامه اجرا کنید . البته شما نیاز به Visual Studio .NET خواهید داشت . این برنامه به زبان C#.NET نوشته شده است . در صورت مشاهده مشکل در برنامه ، از طریق ایمیل در تماس باشید . تشکر


منابع :

۱- وفایی جهان،مجید ،مبانی مدل سازی و شبیه سازی کامپیوتری ، انتشارات خط اول ،ص ۱۱۵-۱۳۵ ،سال ۱۳۹۲

۲- نیپولیتان ، جعفر نژاد قمی ، طراحی الگوریتم ها ، انتشارات علوم رایانه ، سال ۱۳۹۰

۳- http://www.theprojectspot.com/tutorial_post/creating-a-genetic-algorithm-for-beginners

 

پاسخ دهید

*