الگوریتم ژنتیک چیست؟

الگوریتم ژنتیک چیست؟

الگوریتم های فراابتکاری به دو دسته تقسیم می شوند: 1. مبتنی بر یک جواب 2. مبنی بر جمعیت. در دسته اول در هر مرحله جستجو فقط یک جواب تغییر می کند. ولی در دسته دوم در هر مرحله جستجو یک جمعیت به عنوان جواب برگردانده می شود. الگوریتم هایی مانند شبیه سازی تبرید و جستجوی ممنوعه جزو دسته اول هستند و الگوریتم هایی مانند الگوریتم ژنتیک، کلونی مورچگان، بهینه سازی ازدحام ذرات و کلونی زنبور عسل جزو دسته دوم محسوب می شوند.  

مراحل الگوریتم ژنتیک به صورت ذیل می باشد(شکل 1):

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

تولید جمعیت اولیه: همانطور که ذکر شد چون الگوریم ژنتیک جزو دسته دوم می باشد بنابراین این الگوریتم در ابتدا با یک جمعیت اولیه آغاز می شود. به همین دلیل در ابتدای این الگوریتم یک جمعیت اولیه باید تولید شود. این کار می تواند به صورت تصادفی باشد. یعنی از بین تمام جواب های یا راه حل های ممکن چند راه حل به عنوان جمعیت اولیه تولید گردد.

انتخاب (انتخاب والدین): در این مرحله طبق نظریه داروین که مبنا بر این است که افراد شایسته بقاء دارند به همین دلیل باید از بین جمعیت اولیه افراد شایسته تر انتخاب گردد. که به عنوان والدین برای تولید فرزندان شایسه تر می باشند. برای مرحله انتخاب به طور کلی می توان از سه روش استفاده نمود:

1.     روش تصادفی: در این روش به تصادف والدین به صورت تصادفی از بین جمعیت اولیه انتخاب می شوند. مزیت این روش سادگی پیاده سازی و همچنین انتخاب والدین غالب و مغلوب با یک شانس می باشد. که این کار شاید منجر به تولید فرزند بهتر گردد.

2.     روش چرخه رولت: در این روش براساس میزان جواب هر ژن با جواب های ژن های دیگر جمع می شود و یک فاصله از صفر تا مجموع کل جواب ها تولید می شود. که به دلیل سادگی این فاصله را به صورت دایره ای در نظر می گیرد. سپس از بین این فاصله یک عدد به تصادف انتخاب می گردد محدوه عدد مربوط به هر ژن باشد آن ژن به عنوان ژن برتر انتخاب می گردد. به عنوان یک مثال ساده وضعیت تابع برازندگی چهار کروموزوم  به صورت جدول 1 می باشد. روش عملکرد چرخه رولت با فرض اینکه عدد بیشتر نشان دهنده بهتر بودن نسبت به اعداد کوچکتر می باشد چرخه رولت این مثال به صورت شکل 2 می باشد. روش محاسبه چرخه رولت بدین صورت است که sum=1+4+3+2=10 می باشد یعنی مجموع تابع برازندگی حال براساس مجموع برای هر کدام از کروموزوم ها یک احتمال انتخاب به صورت فرمول مقابل استفاده می شود :

Pro(chromosei)=Fitness_chromosei/sum(chromose)

بنابراین داریم:

Pro(chromose1)=1/10=0.1

Pro(chromose2)=4/10=0.4

Pro(chromose3)=3/10=0.3

Pro(chromose4)=2/10=0.2

که در آن کروموزوم 2 به دلیل بیشترین برازندگی شانس و احتمال انتخاب آن بیشتر از همه می باشد.

جدول 1: مشخصات چهار کروموزوم

 

شکل 2: چرخه رولت چهار کروموزوم

3.     روش رقابتی یا مسابقه ای: در این روش دو یا چند جواب یا راه حل انتخاب شده و از بین آنها بهترین آنها انتخاب می گردد.

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

1.     کدگذاری دودوئی: در این روش که معمول ترین شیوه نمایش برای الگوریتم ژنتیک می باشد هر کروموزوم به صورت یک عدد دودئی نمایش داده می شود.(شکل 3)

0

1

1

0

0

1

0

شکل 3: روش کدکذاری دودوئی

2.     کدگذاری جایگشتی: در این روش کدگذاری کروموزوم ها به شکل رشته ای از اعداد طبیعی نمایش داده می شوند.(شکل 4)

0

5

4

2

3

1

6

شکل 4: روش کدگذاری جایگشتی

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

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

 

شکل 5: تقاطع تک نقطه ای

2.     تقاطع چند نقطه ای: در این روش برخلاف روش تک نقطه ای، m نقطه از بازه 1 تا n-1 تولید می گردد و به صورت یک در میان برای هر بازه بخشی از کروموزوم انتخاب می گردد.(شکل 6)

شکل 6: تقاطع دو نقطه ای

جهش: این عملگر به منظور رسیدن به بهینگی بهتر می باشد. که از بین ژن های یک رشته کروموزوم در یک یا چند ژن به طور تصادفی تغییرات ایجاد می شود. یکی از روش های پیاده سازی این روش اگر روش کد گذاری دودوئی باشد یک ژن به تصادف انتخاب شده و مقدار آن معکوس می شود اگر صفر بود به یک و اگر یک بود به صفر تبدیل می گردد.(شکل 7)

 

شکل 7: مثالی از عملگر جهش

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

[1]: Luo Lie,” Heuristic Artificial Intelligent Algorithm for Genetic Algorithm”, published Jun 2010 in Key Engineering Materials volume 439-440 on pages 516 to 521.