فرآیند ارزیابی و الگوریتم ژنتیک


Widget not in any sidebars

3-4-4. ساختار کلی الگوریتم ژنتیک
ساختار کلی یک الگوریتم ژنتیک را می‌توان به این صورت تصور کرد. ابتدا پیش از هر چیز باید مکانیسمی برای تبدیل هر جواب مسأله به یک کروموزوم تعریف کرد. پس از آن یک مجموعه از کروموزوم‌ها که در حقیقت مجموعه‌ای از جواب‌های مسأله هستند به عنوان یک جمعیت آغازین تهیه می‌گردند. این مجموعه که اندازه آن دلخواه است و توسط کاربر تعریف می‌شود اغلب به صورت تصادفی ایجاد می‌گردد.
بعد از این مرحله باید با بکارگیری عملیات ژنتیک اقدام به ایجاد کروموزوم‌های جدید موسوم به نوزاد نمود. این عملیات به دو گونه عمده تقاطعی و جهشی تقسیم‌بندی می‌شوند. همچنین برای گزینش کروموزوم‌هایی که باید نقش والدین را بازی کنند دو مفهوم نرخ تقاطعی و نرخ جهشی کاربرد فراوان دارند که این دو نیز پیش از شروع الگوریتم توسط کاربر تعیین می‌شوند.
بعد از تولید یکسری کروموزوم جدید یا اولاد باید با استفاده از عمل تحول اقدام به انتخاب برازنده‌ترین کروموزوم‌ها نمود. این فرآیند که در فرآیند انتخاب نمود می‌یابد گلچین‌کردن کروموزوم‌های برازنده در میان والدین و اولاد است به طوریکه تعداد کروموزوم‌های منتخب برابر با اندازه جمعیت اولیه باشد. فرآیند انتخاب مبتنی بر مقدار برازندگی هر رشته است. در حقیقت فرآیند ارزیابی محوری‌ترین بحث در فرآیند انتخاب است.
تا بدین مرحله یک تکرار یا یک نسل از الگوریتم طی شده است. الگوریتم بعد از طی چندین نسل به تدریج به سمت جواب بهینه همگرا می‌شود. شرط توقف مسأله نیز طی‌کردن تعداد معینی تکرار است که پیش از آغاز الگوریتم توسط کاربر تعیین می‌شود.
ساختار کلی یک الگوریتم ژنتیک را می‌توان به صورت ذیل بیان کرد[37] :
Procedure: Genetic Algorithm
Step 1: Set t:=0
Step 2: Generate initial population, p(t).
Step 3: Evaluate p(t) to creat fitness values
Step 4: While (not termination cordination) do:
Step 5: Recombine p(t) to yield c(t), selecting from p(t) according to the fitness values.
Step 6: Evaluate c(t)
Step 7: Generate p(t+1) from p(t) and c(t)
Step 8: Set t:=t+1
Step 9: End.
Step 10: Stop
در این الگوریتم داریم:
P(t) = ام t والد نسل
C(t) = ام t نوزاد نسل
اما هالند که خود از پیشگامان الگوریتم ژنتیک است در کارهای ابتدایی خود از انتخاب برای برگزیدن والدین استفاده می‌کند. یعنی با استفاده از عمل تحول یک جمعیت گلچین شده به عنوان والدین ایجاد و سپس با استفاده از آنها اقدام به تهیه تعدادی اولاد (نوزاد) می‌نماید. در این گام نیز برای ثابت نگاه داشتن اندازه جمعیت، اولاد تولید شده جایگزین والدین مربوطه شوند. این تنها تغییر در کلیات رویکرد هالند با رویکرد گرفنستت و بیکر است.
3-4-5. مفاهیم کلیدی الگوریتم ژنتیک