SIA: Swarm Intelligence Algorithms

الگوریتم های هوش جمعی

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.

 

 

هادی محمدی شنبه 13 مرداد 1397 ساعت 23:34

کتاب توسعه برنامه موازی GPU با استفاده از کودا

معرفی کتاب توسعه برنامه موازی GPU با استفاده از کودا

این کتاب با نام  توسعه برنامه موازی GPU با استفاده از کودا می باشد که توسط Tolga Soyata نوشته شده است. این کتاب در سال  2018 توسط انتشارات Chapman and Hall/CRC منشر شده است. کتاب حاضر در 15 فصل در قالب 477 صفحه ارائه شده است. نویسنده این کتاب مباحث خود را در سه بخش: توضیحات در مورد اجرای برنامه با cpu و چند نخی ارائه می دهد  و  در قسمت دوم به اجرای برنامه ها در پلتفرم nvidia همراه با GPU را بیان کرده است و در قسمت آخر کتاب دید گسترده ای از مفاهیم GPU و کودا را به خواننده می دهد و به معرفی اجمالی از کتابخانه های کودا مانند cuBLAS, cuFFT, NPP, and Thrust می پردازد. تصویر جلد کتاب در شکل 1 قابل مشاهده می باشد.


شکل 1: تصویر جلد کتاب توسعه برنامه موازی GPU با استفاده از کودا

 

 

هادی محمدی جمعه 5 مرداد 1397 ساعت 22:17

کتاب راهنمای کودا

معرفی کتاب راهنمای کودا

این کتاب با نام  راهنمای کودا : یک راهمنای جامع برای برنامه نویسی در GPU می باشد که توسط Nicholas Wilt نوشته شده است. این کتاب در سال  2013 توسط انتشارات Addison-Wesley منشر شده است. کتاب حاضر در 15 فصل در قالب 522 صفحه ارائه شده است. نویسنده این کتاب مباحث خود را در سه بخش: توضیحات سطح بالا از سخت افزار و نرم افرار که در کودا امکان پذیر است صحبت می کند و پس از آن شرح کاملی از جنبه هایی مانند حافظه، جریان و حوادث ، مدل های اجرائی، جریان چند پروسسی و برنامه نویسی چندگانه پردازنده های گرافیکی را بیان کرده است و در نهایت در بخش سوم به برنامه های کاربردی منتخب و الگوریتم های موازی کلیدی مانند الگوریتم های کاهش و پردازش تصویر پرداخته است. تصویر جلد کتاب در شکل 1 قابل مشاهده می باشد.


شکل 1: تصویر جلد کتاب راهنمای کودا

لازم به توضیح است که این کتاب ویرایش دومش در سال 2018 به چاپ رسیده است که در حال حاضر برای آن باید هزینه پرداخت نمود. تصویر جلد ویرایش دوم این کتاب در شکل 2 آورده شده است.


شکل 2: تصویر جلد کتاب راهنمای کودا – ویرایش دوم

 

 

هادی محمدی جمعه 5 مرداد 1397 ساعت 22:16