X
تبلیغات
زولا

SIA: Swarm Intelligence Algorithms

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

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

نوعی از الگوریتم های ژنتیک تقلید تکامل ساده را انجام می دهند. همه الگوریتم های ژنتیکی با مفهوم کروموزوم آغاز می شوند. دانشمندان کامپیوتر با مبنای 4 کار نمی کنند بلکه بر مبنای 2 کار می کنند. بنابراین در سیستمی که ساخته می شود فقط کروموزوم ها دودوئی هستند. در این الگوریتم مانند الگوریتم ژنتیک معمولی جهش نیز وجود دارد. که صفرها می توانند به یک و یک ها می توانند به صفر تبدیل شوند. بعد از انتخاب می توان از مفهوم تقاطع یا crossover استفاده نمود. پس از آن به هر کروموزوم یک احتمال زنده ماندن مثلاً 0.8 یا 0.1 داده می شود. بدین ترتیب نسل جدید تولید می شود. این احتمال می تواند به عنوان مثال میزان تناسب اندام افراد باشد.

انتخاب نسل بعدی در الگوریتم ژنتیک به روش های مختلفی امکان پذیر می باشد:

مکانیزم اول: استفاده از روش احتمال برای محاسبه برازندگی کروموزوم ها:

دادن احتمال به تمام کروموزوم ها یک نسل که مجموع کل احتمال آنها برابر با یک خواهد بود. بنابراین احتمال زنده ماندن کروموزوم i متناسب با میزان ویژگی آن کروموزوم است مثلاً تناسب اندام افراد. بنابراین کاندیدائی که بیشترین آمادگی را دارد بیشترین احتمال ورود به نسل بعدی را نیز خواهد داشت. فرمول محاسبه احتمال انتخاب کروموزوم i به صورت ذیل می باشد:

.

مکانیزم دوم: استفاده از روش rank space :

در این روش برای انتخاب کروموزوم ها از رتبه استفاده می شود. این روش نه تنها باعث کنترل انتخاب بهترین کروموزوم از نظر برازندگی در تکرارهای مختلف می شود بلکه تحت تاثیر قرار دادن بیش از اندازه این کروموزوم بر روی کروموزوم های مشابه را حذف می کند. روش کار این مکانیزم شامل دو مرحله زیر می باشد:

1.     تمام افراد براساس کیفیت مرتب می شوند. 2. سپس براساس فرمول زیر احتمال براساس رتبه هر فرد مشخص می شود که در آن pc  فضای رتبه می باشد که مقداری بین صفر تا یک تعیین می شود.

P1=pc        ,p2=(1-pc)pc        ,p3=(1-pc)2pc        ,p4=(1-pc)3pc        , pN-1=(1-pc)N-2pc         ,pN=(1-pc)N-1.

برای درک بهتر دو مکانیزم  فوق برای مثال تولید کیک، برازندگی آنها بدست آورده می شود. در جدول 1 تناسب میزان شکر و پودر به کیلوگرم برای تولید کیک نشان داده شده است همان طور که نمایان است میزان این تناسب برای (5,5) بهترین کیفیت را دارا می باشد.

 

جدول 1: تناسب شکر به پودر برای تولید کیک

شکر

9

1

2

3

4

5

4

3

2

1

8

2

3

4

5

6

5

4

3

2

7

3

4

5

6

7

6

5

4

3

6

4

5

6

7

8

7

6

5

4

5

5

6

7

8

9

8

7

6

5

4

4

5

6

7

8

7

6

5

4

3

3

4

5

6

7

6

5

4

3

2

2

3

4

5

6

5

4

3

2

1

1

2

3

4

5

4

3

2

1

 

1

2

3

4

5

6

7

8

9

 

پودر

 

اگر پنج کروموزوم به تصادف در لیست انتخاب برای نسل بعدی قرار بگیرند همان طور که در جدول 2 نشان داده شده است، در آن صورت ابتدا آنها بر اساس کیفیت مرتب می شوند و طبیعتاً آن کروموزومی که دارای کیفیت بیشتر است دارای رتبه بهتر می باشد و پس از آن می توان براساس برازندگی استاندارد و فرمول برازندگی رتبه مقادیر هر کروموزوم را بدست آورد. در این مثال مقدار pc= 0.667 در نظر گرفته شده است. به عنوان مثالp1,p2  به صورت  p1=pc=0.667 و همچنین p2=(1-0.667)*0.667=0.222 محاسبه می شود.

جدول 2: بدست آوردن میزان برازندگی با مکانیزم های 1و2

Rank fitness

Standard fitness

Rank

Quality

Chromosome

0.667

0.4

1

4

(1,4)

0.222

0.3

2

3

(1,3)

0.074

0.2

3

2

(1,2)

0.025

0.1

4

1

(5,2)

0.012

0

5

0

(7,5)

 

مکانیزم سوم: ترکیب دو ویژگی برازندگی کیفیت و تنوع

بعضی از وقت ها فقط با ایجاد کردن تنوع (Diversity) زیاد در روش زندگی افراد می توانند به حیات خود ادامه دهند. و این تنها راه زنده ماندن افراد می باشد. به منظور عملیاتی کردن این مکانیزم پس از اینکه افراد براساس fitness برای نسل بعدی انتخاب شدن قبل از قرار دادن این افراد در مجموعه نسل بعدی میزان تنوع و تفاوت این افراد هم باید به عنوان یک ویژگی در نظر گرفته شود.

روش کار برای این مکانیزم به صورت ذیل می باشد:

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

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

در نمودار  1 تناسب بین برازندگی و تنوع نشان داده شده است.

نمودار 1 : تناسب ویژگی های برازندگی و تنوع در مکانیزم ترکیبی الگوریتم ژنتیک

به منظور درک بهتر این مکانیزم تناسب پودر و شکر برای درست کردن کیک را در جدول 1 در نظر بگیرید به منظور حل با این روش می توان به صورت ذیل اقدام نمود:

همان طور که در جدول 3 نشان داده شده است با فرض اینکه (5,1) کروموزومی باشد که قبلاً انتخاب شده است می توان رتبه های برازندگی کیفیت و تنوع را بدست آورد. لازم به توضیح است که برای بدست آوردن فاصله d از فرمول فاصله بین دو نقطه یعنی  استفاده شده است.

جدول 3: محاسبه رتبه های تنوع و برازندگی برای مثال کیک

Quality Rank

Diversity Rank

1/d2

Score

Chromosome

1

1

0.040

4

(1,4)

2

5

0.250

3

(3,1)

3

3

0.059

2

(2,1)

4

4

0.062

1

(1,1)

5

2

0.050

0

(7,5)

 

بنابراین همان طور که در جدول 4 نشان داده شده است کروموزوم (1,4) به دلیل Fitnessبالاتر در لیست نسل بعدی قرار می گیرد.

جدول4 : محاسبه برازندگی و انتخاب اولین کروموزوم بهتر برای مثال کیک به کمک مکانیزم ترکیبی

Fitness

Combined rank

Rank sum

Chromosome

0.667

1

2

(1,4)

0.025

4

7

(3,1)

0.222

2

6

(2,1)

0.012

5

8

(1,1)

0.074

3

7

(7,5)

 

به همین ترتیب برای چهار کاندید باقیمانده محاسبات مشابه انجام می شود که در نهایت همان طور که در نمودار 2 نشان داده شده است تاثیر تنوع از نظر فاصله در نتیجه بدست آمده لحاظ شده است.

 

 

 

 

شکل2: نتیجه نهائی مکانیزم ترکیبی برای کیک

نتیجه ای که می توان گرفت این است که تنوع در محاسبات الگوریتم های ژنتیکی دخالت داشته باشد باعث یافتن راه حل های بهتر می شود.

[1].https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/lecture-videos/lecture-13-learning-genetic-algorithms/

[2]. https://i.cs.hku.hk/~kpchan/cs23270/6.learn/ga.html.

 

 

نظرات (0)
نام :
ایمیل : [پنهان میماند]
وب/وبلاگ :
برای نمایش آواتار خود در این وبلاگ در سایت Gravatar.com ثبت نام کنید. (راهنما)