كروموزوم: اساس الگوريتم ژنتيك تبديل جوابهاي مساله به شکل رشتهاي از كدهاست که آن را اصطلاحا كروموزوم يا ژنوتايپ105 مينامند.
فنوتايپ: هر كروموزوم متناظر با يک جواب از مجموعه جوابهاي مساله است. جواب متناظر با هر كروموزوم را يك فنوتايپ 106مينامند.
ژن: عناصر تشكيلدهنده رشته كروموزوم كه معمولا اعداد هستند را ژن107 ميگويند.
جامعه: به مجموعهاي از كروموزومها يک جامعه108 اطلاق ميشود.
نسل: هر تکرار از الگوريتم را يک نسل109 مينامند.

3-6-2- شماي کلي الگوريتم ژنتيک
الگوريتم ژنتيک کلاسيک در قالب شبه برنامه زير صورت ميپذيرد:
ایجاد جمعیت تصادفی اولیه.
ارزشيابي اعضا جامعه بوسيله تابع برازش.
انتخاب والدین و ترکیب آنها برای ایجاد جمعیت فرزندان
انتخاب اعضای جمعیت برای اعمال جهش و ایجاد جمعیت جهش یافتگان
ادغام جمعیت اصلی، فرزندان و جهش یافتگان و ایجاد جمعیت اصلی جدید
توقف الگوريتم در صورت مشاهده شرايط توقف و معرفي بهترين جواب توليد شده به عنوان جواب بهينه.
در غیر این صورت رفتن به مرحله 2.

3-6-3- مفاهيم الگوريتم ژنتيک
مهمترين مفاهيم بکاررفته در الگوريتم ژنتيک عبارتند از:
کدگذاري
جامعه اوليه
عمليات ژنتيک
تابع برازش
شرط توقف الگوريتم.

3-6-3-1-کدگذاري
اولين گام در بكارگيري الگوريتم ژنتيك کدگذاري و نمايش جوابهاي مساله بصورت يك كروموزوم است. انتخاب ساختار مناسب براي کدگذاري جوابها موجب سادهسازي و کاهش زمان محاسباتي عمليات صورت گرفته در طول اجراي الگوريتم ميشود. هر کروموزوم غالبا بوسيله رشتهاي از اعداد نمايش داده ميشود بهطوريکه هر کدام از عناصر اين رشته با قسمتي از يک جواب مساله متناظر است. روشهاي کدگذاري متداول عبارتند از: کدگذاري صفر و يک، کدگذاري ترتيبي، کدگذاري درختي و کدگذاري ارزشي (شکلهاي 3-1، 3-2 و 3-3).

شکل 3-1- کدگذاري ترتيبي

شکل 3-2- کدگذاري ارزشي

شکل 3-3- کدگذاري درختي
کدگذاري غالبا به دو صورت مستقيم و غيرمستقيم صورت ميگيرد: در روش کدگذاري مستقيم يک جواب به طور کامل به صورت کروموزوم در نظر گرفته ميشود. اين روش براي مسایل پيچيده مناسب نيست، زيرا عملگرهاي ژنتيک منجر به توليد فرزندان ناموجه ميشوند. در حالي که در روش کدگذاري غيرمستقيم تنها بخشي از جواب به صورت يک کروموزوم کدگذاري ميشود. در اين رابطه ذکر اين نکته ضروري است که الگوريتم ژنتيک با کدگذاري جوابها يک رابطه بين فضاي کدگذاري و فضاي جوابها ايجاد ميکند بهطوريکه عمليات ژنتيك بر روي فضاي كدگذاري يا كروموزومها اعمال ميشود در حالي كه فرايندهاي انتخاب و ارزشيابي بر روي فضاي جوابها عمل ميکنند. شکل 3-4 به صورت نمادين تقابل فضاي کدگذاري و فضاي جوابها را نمايش ميدهد.

شکل 3-4- فضاي کدگذاري و فضاي جواب

در هنگام کدگذاري جواب ها به طور طبيعي دو مفهوم اساسي بروز مينمايد:

موجه بودن کروموزومها
قانونمندي کروموزومها

موجه بودن کروموزوم در ارتباط با ارضاي محدوديتهاي مساله است که کروموزوم نمايشي از يک جواب آن است. قانونمندي کروموزومها نيز مربوط به حالتي است که عمليات ژنتيک کروموزومي را توليد مينمايد که با هيج جوابي از فضاي جواب متناظر نیست. اين دو مفهوم به صورت نمادين در شکل 3-5 نمايش داده شده است.

شکل 3 – 5- موجه بودن و قانونمندي کروموزومها

3-6-3-2- جامعه اوليه
اولين مرحله پس از کدگذاري و تبديل جوابها به کروموزومها ايجاد جامعه اوليه جوابها ميباشد. بطور معمول جوابهاي اوليه به صورت تصادفي توليد ميشوند. در بعضي موارد با توجه به نوع مساله و به منظور تسريع در همگرايي الگوريتم از روشهاي ابتکاري براي توليد جوابها استفاده ميشود ولي با اين وجود عموميترين روش، استفاده از يک رويکرد تصادفي است. اندازه جامعه اوليه يک پارامتر کليدي براي الگوريتم ژنتيک محسوب ميشود و تاثير فراواني بر کارايي الگوريتم دارد. يک اندازه کوچک براي جامعه اوليه موجب ميشود تنها بخشي از فضاي جواب مورد کاوش قرار گيرد در حالي که اندازههاي بزرگ جامعه اوليه کارايي الگوريتم را به شدت کاهش ميدهد.

3-6-3-3- عمليات ژنتيک
عمليات ژنتيک به فرايند توليد کروموزومهاي جديد (فرزندان) با استفاده از کروموزومهاي موجود (والدين) اطلاق ميشود و به طور كلي توسط سه عملگر عمده انجام ميشود: انتخاب، تقاطع و جهش.

عملگر انتخاب110
نيروي پيشبرنده در الگوريتم ژنتيک انتخاب کروموزومها با توجه به ميزان برازندگي آنها است. کروموزومهاي برازندهتر از شانس بالاتري براي انتخاب شدن به عنوان عضوي از نسلهاي آتي الگوريتم برخوردار هستند. اين موضوع متناظر با اصل بقاي انسب111 در نظريه تکامل تدريجي به مفهوم قابليت طبیعت در تطابق با تغييرات محيطي ميباشد و يکي از الهامبخشترين مفاهيم ژنتيک طبيعي در الگوريتم ژنتيک به شمار ميآيد.
متداولترين مکانيسمهاي انتخاب عبارتند از:

انتخاب چرخ رولت112
انتخاب چرخ رولت يکي از مناسبترين انتخابهاي تصادفي بوده که ايده آن بر اساس احتمال انتخاب ميباشد و اولين بار توسط هالند [53] پيشنهاد شد. احتمال انتخاب متناظر با هر کروموزوم، بر اساس برازندگي آن محاسبه ميشود بطوريکه که اگر f_k ميزان برازندگي کروموزوم kام باشد، احتمال بقاي متناظر با اين کروموزوم برابر است با:

(3-18)

در اين معادله n اندازه جامعه و احتمال بقاي متناظر با کروموزوم kام است.

اگر کروموزومها بر اساس p_k مرتب شوند،q_k که همان مقدار تجمعي p_k است، به صورت زير محاسبه ميشود:

(3-19)

در روش انتخاب چرخ رولت براي انتخاب هر کروموزوم ابتدا يک عدد تصادفي از بازه U~[0 1] توليد ميشود. اين عدد به طور طبيعي از يکي مقادير q_k کوچکتر است و بدين صورت کروموزوم kام متناظر با q_k انتخاب ميشود. روش پيادهسازي چرخ رولت به اين شکل است که يک چرخ فرضي در نظر گرفته ميشود و سطح آن به تعداد کروموزومها طوري تقسيم ميشود که هر بخش از آن متناظر با مقدار برازندگي کروموزوم مربوطه باشد. حال چرخ به گردش در ميآيد و هر جا شاخص چرخ متوقف شد، کروموزوم مربوط به آن بخش انتخاب میشود.

انتخاب مسابقهاي113
پارامتر موثر در اين روش، تور است که عبارتست از تعداد اعضايي که به صورت تصادفي و در قالب يک گروه از جامعه انتخاب شده و سپس بهترين اعضاي اين گروه به عنوان والدين انتخاب ميشوند. اين فرايند آنقدر تکرار ميشود تا تعداد والدين مورد نظر انتخاب شوند.
سایر عملگرهای انتخاب عبارتنداز:
انتخاب تصادفی114
انتخاب بر اساس بهترینها115
انتخاب بر اساس مقیاسبندی116

عملگرتقاطع117
اين نوع عملگر بر روي دو کروموزوم اعمال ميشود و از ترکيب ساختار آنها يک يا چند کروموزوم جديد به عنوان فرزند توليد مينمايد. نرخ تقاطع118 به صورت نسبت تعداد فرزندان توليد شده در هر نسل به تعداد اعضاي جامعه تعريف ميشود. اين نرخ بيانگر تعداد مورد انتظار کروموزومهايي است که توسط اين عملگر دچار تغيير ميشوند. نرخ تقاطع بزرگتر اجازه ميدهد كه بخش وسيعتري از فضاي جواب مورد جستجو قرار گيرد. اگر نرخ تقاطع خيلي بزرگ باشد باعث اتلاف وقت جهت سركشي به نواحي غير قابل اطمينان فضاي جواب خواهد شد. تعدادي از انواع متداول عمليات تقاطع عبارتند از:

تقاطع يک نقطهاي119
در اين روش يک نقطه به صورت تصادفي به عنوان نقطه برش در طول دو کروموزومي که به عنوان والدين انتخاب شدهاند در نظر گرفته شده و کروموزومها از آن نقطه به دو بخش تقسيم ميشوند و دو بخش جدا شده آنها با هم تعويض ميگردد (شکل 3-6).

تقاطع دو نقطه برش120
در اين روش دو نقطه به عنوان نقطه برش در نظر گرفته شده و كروموزومها از آن دو نقطه به سه بخش تقسيم ميشوند. بخش وسط ثابت مانده و بخشهاي دو باقيمانده از دو كروموزوم با هم تعويض ميشوند (شکل 3-7). ساير عملگرهاي تقاطع عبارتند از:
تقاطع چند نقطه برش
تقاطع يکنواخت
تقاطع بخش نگاشته
تقاطع ترتيب

شکل 3 – 6- تقاطع تکنقطهاي

شکل 3 – 7- تقاطع دونقطهاي

عملگر جهش121
اين عملگر بر روی اعضایی از جمعیت تغييرات تصادفي برنامهريزي نشده ايجاد ميكند و ژنهايي كه در جامعه اوليه وجود نداشتهاند را وارد جامعه ميکند. در رابطه با اين عملگر مفهوم نرخ جهش وجود دارد. نرخ جهش عبارتست از درصدي از تعداد ژن هاي موجود كه دچار تغيير ميشوند. اگر نرخ جهش خيلي كوچك باشد، تعداد زيادي از ژنها كه ميتوانستند مفيد باشند تست نميشوند واگر نرخ جهش خيلي بزرگ باشد، يك اختلال تصادفي بوجود آمده و فرزندان شباهت خود را با والدين از دست ميدهند كه اين امر باعث از بين رفتن حافظه تاريخي الگوريتم ميشود. عملگرهاي جهشي مختلفي وجود دارد که مهمترين آنها عبارتند از: جابهجايي122، معکوس کردن123، جایگذاري124.

3-6-3-4- تابع برازش
تابع برازش شاخصي براي ارزيابي کروموزومها ميباشد که در مسایل بهينهسازي اين شاخص تابعي از مقدار تابعهدف مساله است. هرچه يک جواب مناسبتر باشد، کروموزوم منتاظر با آن مقدار برازندگي بيشتري دارد. براي اينکه شانس بقاي چنين جوابي بيشتر شود، احتمال بقاي آن متناسب با مقدار برازندگي آن در نظر گرفته ميشود. بدين ترتيب کروموزومي که برازندگي بيشتري دارد بااحتمال بيشتري در توليد فرزندان شرکت ميکند و جوابهاي بيشتري به دنبال آن توليد ميشوند.

3-6-3-5- شرط توقف الگوریتم
الگوريتم ژنتيک با فراهم شدن يک يا چند شرط توقف125 خاتمه مييابد و بهترين جواب توليد شده در طول نسل هاي متوالي جوابها به عنوان جواب بهينه معرفي ميشود. شرط توقف ميتواند شامل حداکثر تعداد نسلهاي الگوريتم، عدم بهبود جوابها در چندين نسل متوالي، کاهش ميزان انحراف معيار جامعه جوابها و غیره باشد. بطورکلي در مسایل مختلف و در انواع گوناگون الگوريتم ژنتيک شروط توقفي که بهترين عملکرد الگوريتم را فراهم ميکند، لحاظ ميشود.

ساختار کلی الگوریتم ژنتیک در شکل3-8 نمایش داده شده است.

شکل3-8- ساختار کلی الگوریتم ژنتیک

3-7- پیاده سازی الگوریتم ژنتیک پیشنهادی
در این بخش به معرفی اجزای الگوریتم ژنتیک پیشنهادی پرداخته میشود.
3-7-1- کدگذاری الگوریتم
کروموزوم تعریف شده در مساله مورد بررسی دو بخشی است، قسمت اول مربوط به توالی انجام کارها روی ماشینآلات میباشد که یک کروموزوم ترتیبی است و قسمت دوم مربوط به حالات پذیرش سفارشات میباشد که یک کروموزوم صفرو یک است. طول کروموزمها برابر با تعداد کل کارهای کاندید برای پردازش م
یباشد. به عنوان مثال برای نمایش جواب شدنی مسالهایی با 5کار از کروموزوم آمده در شکل 3-9 استفاده میشود:

2
4
5
1
3

1
0
1
1
0

شکل3-9- نمایش کروموزوم

کروموزوم بالا به این صورت رمزگشایی میشود که توالی انجام کارها روی ماشینها به صورت 2-4-5-1-3 میباشد، کارهای 5-3-2 برای پردازش پذیرفته شدهاند و دو کار 4-1 رد شدهاند و به عنوان کارهای تهی126 در توالی قرار گرفتهاند.

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

3-7-3- تابع برازش
تابع برازش مورد نظر در این مطالعه همان تابع هدف در مدل ریاضی ارایه شده میباشد که صورت زیر نمایش داده می شود:
(3-20)

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

3-7-4-1- عملگر تقاطع
عملگر تقاطع برای کروموزومهای این مساله شامل دو عملگر است؛ عملگر تقاطع بخش اول کروموزومها که بایستی طوری باشد که محدودیتهای مساله را نقض نکند به همین دلیل از یک رویکرد ابتکاری جهت ترکیب بخش اول کروموزومها استفاده شده است و عملگر تقاطع برای بخش دوم کروموزومها.مراحل اجرای این نوع تقاطع با استفاده از یک مثال تشریح میشود:

انتخاب دو کروموزوم از بین جمعیت با استفاده از مکانیزم چرخ رولت، به عنوان والدین(شکل3-10):

4
2
5
3
1
Parent1
1
1
0
1
1
0

1
4
2
5
3
Parent2
0
1
1
1
1
0

شکل3-10-انتخاب دو کروکوزوم والد

در تقاطع بخش اول کروموزومها، برای هر کدام از ژنها در دو کروموزوم اعداد تصادفی را به صورت زیر تولید می کنیم:
برای ژن اول یک عدد بین(1,0)
برای ژن دوم یک عدد بین(,0)
برای ژن سوم یک عدد بین(,0)
و برای سایر ژن ها به همین ترتیب (شکل3-11).

4
2
5
3
1
Parent1
0.09
0.19
0.42
0.52
0.85

1
4
2
5
3
Parent2
0.07
0.12
0.27
0.31
0.49

شکل3-11- مرحله دوم عملگر تقاطع برای ایجاد توالی
حال بایستی مقادیر اعداد تصادفی مربوط به کارهای مشابه در دو کروموزوم را با هم جمع کرده بطوریکه مقادیر اعداد تصادفی ژنهای محتوی عدد 1 را با هم، عدد 2 را باهم و… (شکل3-12).

5
4
3
2
1
0.73
0.21
1.01
0.46
0.92

شکل3-12- مرحله سوم عملگر تقاطع برای ایجاد توالی

حال این اعداد را بایستی به صورت نزولی مرتب کنیم و ژنهای متناظر با آنها را در مکانها به ترتیب قرار دهیم،بدین ترتیب کروموزوم جدید ساخته میشود (شکل3-13).

4
2
5
1
3
0.21
0.46
0.73
0.92
1.01

شکل3-13- مرحله چهارم عملگر تقاطع برای ایجاد توالی

برای عملگر تقاطع بخش دوم کروموزوم از یک ماتریس کمکی بهره میبریم. به این صورت که اگر عدد تخصیص یافته از5/0 بزرگتر باشد مقادیر از والد 1 و اگر عدد تخصیص یافته از 5/0 کوچکتر


دیدگاهتان را بنویسید