در این پست مثالی در ارتباط با الگوریتم ژنتیک را می خواهیم بررسی کنیم. این مثال از مقاله ای با نام طراحی شبکه ی دیده بانی کیفیت آب در رودخانه های بزرگ به کمک ژنتیک الگوریتم انتخاب شده که در سایت ELSEVIER به چاپ رسیده که به اعتبار آن می افزاید.
در طراحی شبکه های دیده بانی کیفیت آب، نقاطی که از آنها آب نمونه برداری می شود از اهمیت بسیار زیادی برخوردارند در نتیجه ایستگاه ها باید با دقت انتخاب شوند که تمام اهداف مورد نظر را برآورد کنند. این ایستگاه ها باید خاصیت های زیر را داشته باشند:
- نمایانگر حوزه ی آبگیر
- نظارت کننده ی منابع آلودگی
- نشان دهنده ی نیاز آبی
- برآورد کننده ی استاندارد های کیفیت آب
- تست تغییرات کیفیت آب
- براورد کننده ی بار آلودگی
در گذشته طراحی این شبکه ها بر اساس تجربه ی متخصصان بوده. قصد این مقاله استفاده از روش های نوینی مانند الگوریتم ژنتیک برای بهینه سازی این شبکه ها می باشد.
تشریح محدوده
در این مقاله محدوده ی رودخانه ی Nakdong بررسی شده که دومین رودخانه ی کره از نظر بزرگی است. شاخه ی اصلی این رودخانه ۵۲۱٫۵ کیلومتر طول دارد.
ارتباط GIS و GA
مراحل کلی فرایند ژنتیک الگوریتم:
برای این بهینه سازی باید یک سیستم اطلاعات جغرافیایی (Geographic Information System) داشته باشیم که در اینجا از ArcView 3.2 به عنوان GIS استفاده شده. همچنین از library به نام GAlib و محیط برنامه نویسی VC++ برای اجرای عملیات الگوریتم ژنتیک استفاده شده.به منظور بهینه سازی هر مدلی توسط الگوریتم ژنتیک ابتدا باید موارد زیر به دقت تعیین شوند:
- ژن ها چه چیزی را نشان می دهند؟
- کرومزوم به چه شکل است و طولش چقدر می باشد؟
- تابع fitness چیست؟
در این مقاله ابتدا منطقه ی مورد نظر را توسط ابزاری در ArcView جدول بندی کرده و به هر یک از خانه ها یک عدد یکتا داده شده است.
هر ژن می تواند یکی از آن عدد های یکتا باشد. مجموعه ای از این ژن ها یک کرومزم را تشکیل می دهند. تعداد ژن های هر کرومزم بستگی به تعداد ایستگاه هایی دارد که می خواهیم داشته باشیم. به عنوان مثال در این مقاله می خواهیم ۱۱۰ ایستگاه داشته باشیم، پس تعداد ژن های هر کرومزم ۱۱۰ عدد می باشد.
هر کرومزوم دارای یک fitness می باشد. هر چه این fitness بالاتر باشد نشان دهنده ی نزدیک تر بودن آن به حالت مورد نظر ما می باشد.
-
ببخشید! شما گفتید که کل نقشه را جدول بندی می کنیم! که شامل رودخانه و خشکی می شود. اما اینطوری که من متوجه شدم ایستگاه ها حتما باید در کنار رودخانه باشند پس به نظر من درست این بود که فقط قسمت هایی که رودخانه در آن قرار دارد را شماره دهی کنیم! -
” نکته ی خیلی خوبی را اشاره کردید. یکی از راه ها برای حل این مشکل راهی بود که شما به آن اشاره کردید که کمی سخت است. در این مقاله به جای این کار در قسمت fitness دهی به خانه هایی که رودخانه در آنها نیست ضریب صفر داده می شود و در نتیجه به خاطر سلامتی صفر خود به خود حذف خواهند شد! “
پس هر کرومزوم نشان دهنده ی مکان تمامی ایستگاه ها و هر ژن نشان دهنده ی مکان یک ایستگاه می باشد! حال باید تابع fitness را تعریف کنیم.در بالا گفته شد هر ایستگاه باید دارای ۶ خاصیت باشد. تابع سلامت باید هر شش خاصیت را بپوشاند. در این مقاله ۶ خاصیت در ۴ تابع گنجانده شده و تابع سلامت هر ژن به صورت مجموع این چهار تابع با یک وزن مشخص تعیین گردیده:
و در نهایت سلامت هر کرومزوم از مجموع سلامت تمامی ژن ها بدست می آید. چهار تابع سلامت به صورت زیر تعریف شده است:
در الگوریتم ژنتیک همیشه یک سری کرومزم به عنوان جمعیت اولیه داریم که پس از محاسبه ی سلامت هر یک از آنها عملیات ترکیب و جهش روی آنها انجام شده و جمعیت جدید بوجود می آید.
همانطور که می دانیم کرومزومی که سلامت بیشتری دارد امکان ترکیب و بقایش بیشتر می باشد.
ترکیب بصورت تعویض چند ژن در دو کرومزم و جهش با تغییر تصادفی یک ژن صورت می گیرد. در هر نسل تعدادی جمعیت در فرایند ترکیب بوجود آمده و ما بقی مانند جمعیت اولیه تولید می شوند.
اینجا سوال پیش می آید که تعداد جمعیت اولیه و درصد ترکیب و جهش در هر دوره چه مقدار باشد تا بهترین نتیجه حاصل شود!
معمولا بهترین حالت برای این موارد با آزمایش و خطا بدست می آید. تجربه نشان داده که بهترین حالت معمولا با درصد ترکیب بالا و درصد جهش پایین بدست می آید.
در این مقاله چهار حالت زیر امتحان شده و پس از گذشت ۴۰۰۰ نسل بهترین نتیجه در مورد دوم با جمعیت اولیه ی ۳۰۰ و در صد ترکیب و جهش به ترتیب ۸۰% و ۱% مشاهده شده.
در زیر نمودار سلامت کرومزم های هر چهار حالت را مشاهده می کنید:
در زیر نتیجه ی نهایی این مقاله (در سمت راست) و حالت فعلی قرار گیری ایستگاه ها (در سمت چپ) را می توانید ببینید:
در این ۱۱۰ ایستگاه محل ۳۵ ایستگاه بین حالت بدست آمده و حالت موجود یکی می باشد و بقیه ی آنها با هم متفاوت می باشد که به این معنا است که برای بهبود سودمندی شبکه باید در بقیه ی آنها تغییر مکان ایجاد شود.
در نهایت نتیجه ی این مقاله در صورتی که تعداد ایستگاه ها ۱۳۰، ۱۵۰، ۱۷۰، ۱۹۰ و ۲۱۰ عدد می بود ارائه شده که به شکل زیر می باشد:
لینک های داخلی
- Design of a water quality monitoring network in a largeriver system using the genetic algorithm
- مقدمه ای بر هوش مصنوعی
avval
chi shode zadi to in khatta !
bezar bebinam chi gofT
سلام سیاوش جان … مطلب رو نرسیدم کامل بخونم … البته فقط یک نگاه گذرا بهش انداختم … اما مثل همیشه خیلی خوب بود … به خصوص که به رشته تخصصی من هم نزدیک بود …
موفق باشی مرد بزرگ
ممنونم از مطلب و کتابی که بارگذاری کرده اید.
بسیار خوب بود. در صورتی که باز هم در مورد الگوریتم ژنتیک مطلبی دارید خواهشمندم راهنمایی بفرمایید.
خیلی خیلی جالب بود اما چرا انقدر کم ؟!
سلام جناب محمودیان،
Elsevier یک زورنال نیست. بلکه پایگاهی است که از طریق آن به بسیاری از ژورنال‌های علمی می‌توان دسترسی داشت.
با آرزوی موفقیت برای شما
میتونید کمکم کنید موضوع پایان نامه منم همینه
لطفا جواب بدید
دستتون درد نکنه نجاتم دادید . استادمون خوش حال میشه