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

الگوریتم ژنتیک جهت رمزگذاری[1] ساختارها و تولید ساختارهای شروع و انتخاب ساختارها برای تکرارهای بعدی، دارای مراحلی است که بطور اجمالی به شرح ذیل توضیح داده می شود:

2-4-4- ایجاد ساختار اولیه

اولین گام در الگوریتم ژنتیک، تولید ساختارهای اولیه است. ساختار اولیه می بایستی به طور مناسبی کدگذاری گردد. روش های کدگذاری متعددی برحسب نوع مسئله، وجود دارد. مهمترین روش کدگذاری، دوگان[2] و حقیقی[3] می باشد.

2-4-5- تولید ساختارهای جدید

ایجاد ساختارهای جدید بدین صورت است که تعدادی از بهترین ساختارها را درنظرگرفته و از بین این ساختارها، تعداد حضور هر ساختار را به طور تصادفی براساس میزان شایستگی آنها طی روش انتخاب موردنظر تعیین و ساختارهای مذکور دو به دو و بطور تصادفی برای تولید باقیمانده ساختارها، انتخاب و با یکدیگر تلاقی می دهیم، که این عمل را تقاطع[4] می نامیم. سپس بطور تصادفی تعدادی بیت، از کل ساختارها را انتخاب و مقدار آنها را در محدوده قابل قبولی، تغییر می دهیم که این عمل را هم جهش[5] می نامیم. سپس کل ساختارهای موجود و ایجاد شده دوباره مورد ارزیابی قرارگرفته و برجسب نتیجه ارزیابی مرتب می گردند، اگر بهترین ساختار حائز شرائط مطلوب بود، جواب مسئله است، در غیر این صورت مراحل تولید ساختار جدید تا بدست آمدن ساختار بهینه، ادامه پیدا می کند.

2- 4-6- روش های انتخاب[6]

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

2-4-6-1-  انتخاب چرخ گردان[7]

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

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

2-4-6-2-  انتخاب مسابقه ای[8]

این شیوه انتخاب به جای استفاده از مقدار و یا درصد نسبی تابع هدف ساختارها، از رتبه هر ساختار استفاده می کند. روش کار به این صورت است که هر بار K ساختار به طور تصادفی و با احتمال برابر از میان ساختارها انتخاب می شوند. سپس از میان K ساختار تعدادی را که بالاترین رتبه را دارند انتخاب و بقیه حذف می گردند، این عمل را به تعداد کل ساختارها تکرار می کنیم]15[.

2-4-6-3-  انتخاب رتبه ای[9]

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

2-4-7- تقاطع

روش های تقاطع متعددی با توجه به نوع کدگذاری ساختارها وجود دارد که به طور مختصر به دو روش کلی به صورت ذیل اشاره می گردد:

2-4-7-1-  تقاطع تک نقطه ای[10]

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

2-4-7-2-  تقاطع چند نقطه ای[11]

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

2-4-8- جهش

در این جا هم روش های جهش[12] متعددی با توجه به نوع کدگذاری ساختارها وجود دارد که به طور مختصر به دو روش کلی به صورت ذیل اشاره می گردد:

 

2-4-8-1-  جهش تک نقطه ای[13]

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

2-4-8-2-  جهش چند نقطه ای[14]

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

2- 4- 9- پردازش و برازش[15]

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

2-4-10- جایگزینی[16]

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

2-5- معرفی دو تابع کاربردی sparse و graphtraverse  در نرم افزار matlab

در این بخش به معرفی دو تابع مهم و کاربردی sparse و graphtraverse  در نرم افزار matlab پرداخته می شود:

2-5-1- ماتریس sparse

ماتریس sparse برای تحلیل عددی ماتریس های بزرگ با اکثریت اعضای صفر، کاربرد دارد که توسط هاری مارکویتز[17] اختراع گردید.

در لغت   sparse matrixبه معنی ماتریس کم پشته می باشد، ماتریسی است که اکثریت اعضای آن صفر می باشد، همچنین به ماتریسی که اکثریت اعضای آن غیر صفر باشد، ماتریس متراکم[18] گویند.

ماتریس کم پشته در حوزه های تئوری شبکه با اتصالات و یا اطلاعات کم ولی مهم، مفهوم و کاربرد زیادی دارد. اغلب در رشته های مهندسی و علوم، جهت حل معادلات تفاضلی جزئی، با ماتریس های کم پشته زیادی سروکار داریم.

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

در حالت عادی، یک ماتریس کم پشته، یک بردار دو بعدی است. هر عضو بردار بیانگر یک عنصرaij از ماتریس است که از طریق دو اندیس i و j قابل دسترسی است. i تعداد سطر و j تعداد ستون ماتریس را نشان می دهد. برای یک ماتریس m×n حافظه کافی برای ذخیره اطلاعات به تعداد m×n مکان می باشد. این مقدار حافظه ازطریق ذخیره فقط عنصرهای غیرصفر کاهش می یابد.

 

 

2-5-2- تابع sparse

شکل اولیه تابع مذکور بصورت S = sparse(x) است که یک ماتریس کم پشته و یا متراکم را با حذف عنصرهای غیر صفر به شکل پراکنده تبدیل می کند. شکل کلی تابع بصورت S = sparse(i,j,s,m,n,nzmax) است که از ردیف های [i,j,s] برای تولید ماتریس کم پشته m×n با فضای اختصاص داده شده به تعداد nzmax مکان برای عنصرهای غیرصفر استفاده می کند. دو بردار صحیح i و  j و بردار عنصرهای مختلط s همگی دارای طول یکسان می باشند. فرم های ساده شده تابع به صورت ذیل می باشد:

رابطه (2- 1)                                                                                                                                                                                                                                                   S =sparse (i,j,s,m,n)

که در این حالت nzmax برابر طول بردار s است.

رابطه (2- 2)                                                                                                                                               S =sparse(i,j,s)

که در این حالت m = max(i) و n = max(j) است.

2-5-3- تابع graphtraverse

تابع graphtraverse بر روی گره های مجاور براساس الگوریتم جستجوی تعریف شده حرکت کرده و به ترتیب، نزدیکترین گره های بهم متصل را به عنوان خروجی تولید می کند. شکل کلی تابع graphtraverse  بصورت رابطه (2- 3) ذیل می باشد. تابع graphtraverse بر روی گراف G تولید شده توسط تابع sparse، با شروع از گره S، حرکت می کند و گره های پیوسته گراف را بعنوان خروجی تولید می کند.

رابطه (2- 3)          [Disk] = graphtraverse(G,S)

که:

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

 

[1]Coding Method

[2]Binary Coding

[3]Real Coding

[4]Cross-Over

[5]Mutation

[6]Selection Method

[7]Roulette Wheel Selection

[8]Tournam

ent Selection

[9]Ranking Selection

[10]Single Point Cross-Over

[11]Multi Point Cross-Over

[12]Mutation Operator

[13]Single Point Mutation

[14]Multi Point Mutation

[15]Fitness

[16]Reinsertion

[17]Harry M.Markowitz

[18]Dense Matrix