پایان نامه سخت افزار تکاملی با الگوریتم ژنتیک

چکیده فارسی

سخت افزار تکاملی، سخت افزاری است که بتواند ساختار خود را اصلاح کند. این تفکر با پیدایش تکنولوژی FPGAدر بین محققان شروع به رشد کرد. با توجه به اهمیت مدار های ترتیبی همگام در طراحی مدار های منطقی، در این پروژه با یک رهیافت تکاملی سعی در بهینه سازی این گونه مدار ها داریم. درگام اول بهینه سازی، با توجه به اینکه مسئلۀ تخصیص حالت که ذاتاً به این گونه مدار ها مربوط می شود، مسئله ای NP کامل است، سعی داریم با رهیافتالگوریتم ژنتیک تخصیص حالت بهینه مدار را بیابیم. خواهیم دید که یک تخصیص حالت بهینه به طور قابل توجهی در کاهش پیچیدگی بخش ترکیبی مدار ترتیبی تأثیرگذار می باشد. در گام دوم بهینه سازی سعی داریم با رهیافت برنامه نویسی ژنتیکی بخش ترکیبی مدار را از نظر تعداد گیت های معادل و میزان تأخیر انتشار در مدار کاهش می دهیم

مقدمه

سخت افزار تکاملیبخش جدیدی از توسعۀ سخت افزار است که از الگوریتم های تکاملی برای ایجاد سیستم های الکترونیکی استفاده می کند. در حقیقت سخت افزار تکامل یافته، به سخت افزاری گفته می شود که بتواند معماری خودش را به طور پویا و خودکار توسط فرایند انعطاف پذیری چون الگوریتم ژنتیک بهبود ببخشد.

در حقیقت سخت افزار تکاملی از اشتراک علم کامپیوتر، مهندسی الکترونیک و علم زیست شناسی سرچشمه گرفته است.

بعد از سال 1990 ، با توسعۀ تکنولوژی FPGA، محققان به این فکر افتادند که چه طور یک سخت افزار ممکن است با انعطاف پذیری در ارتباط باشد، به طوری که در زمان اجرا نیز قابل برنامه ریزی و باز پیکر بندی باشد. در نتیجه محققان شروع به کار در زمینۀ سخت افزار تکاملی کردند.

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

در فرم پایه سخت افزار تکاملی، الگوریتم تکاملی یک جمعیت از کروموزوم ها (به عنوان مثال در FPGA حافظۀ پیکر بندی یک نمادی از کروموزوم می باشد)که هر کدام نمایشگر یک نمونه مدار می باشد را توسط یک سری عملگر های خود تغییر می دهد، سپس به هر مدار یک میزان سودمندی تخصیص می دهد، که نشان دهندۀ این است که مدار ایجاد شده به چه میزان با مشخصات مورد نظر تطبیق می کند. در هر بار تکرار این الگوریتم، مدارها توسط عملگر ها ی الگوریتم ژنتیک تغییر می کنند. در نتیجه جمعیت جدیدی از جمعیت پیشین استنتاج می شود.

سودمندی یک مدار از دو روش تعیین می شود:

• ارزیابی خارجی : هر مدار به طور مجازی شبیه سازی می شود، در اخر بهترین مدار از جمعیت اخرین مرحله تکرار به طور فیزیکی اجرا می شود. (در این پروژه ما این روش را اتخاذ کرده‌ایم)
• ارزیابی درونی : هر مدار از جمعیت، در هر تکرار از الگوریتم به طور فیزیکی روی سخت افزار واقعی اجرا می شود.

در این پروژه قصد داریم با الهام از الگوریتم های تکاملی، بهینه سازی مدل میلی مدار های ترتیبی همزمان را شبیه سازی کنیم. این بهینه سازی در دو مرحله صورت می گیرد:

1. بهینه سازی تخصیص حالت: نشان می دهیم که یک تخصیص حالت بهینه به طور قابل ملاحظه ای در کاهش پیچیدگی اجزای بخش ترکیبی مدار تأثیر گذار است.در این مرحله الگوریتم ژنتیکی که این بهینه سازی را انجام دهد طراحی میکنیم.
2. بهینه سازی بخش ترکیبی مدار: در این مرحله از پروژه سعی داریم مدار ترکیبی که از نظر تأخیر

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

نویسی ژنتیکی مدار های ترکیبی را بهینه می کنیم.

شرح مختصری از مطالبی که در فصل های اینده به ان می پردازیم، در ذیل اورده شده است :

فصل اول، مطالبی در بارۀ اصول الگوریتم ژنتیک بیان شده است.

فصل دوم، مسئلۀ تخصیص حالت را بررسی می کنیم و نشان می دهیم که یک تخصیص حالت بهینه به طور قابل ملاحظه ای در کاهش پیچیدگی اجزای بخش ترکیبی مدار تأثیر گذار است. و در اخر، الگوریتم ژنتیک به کار رفته را به طور مختصر بیان می کنیم.

فصل سوم، مطالبی در بارۀ اصول برنامه نویسی ژنتیکی پایه بیان شده است.

فصل چهارم، مفاهیمی چون ماکزیمم تأخیر انتشار و تعداد گیت های معادل در یک مدار را توضیح داده و کارهای انجام شده در جهت حداقل سازی این پارامتر ها را بیان می کنیم. و در اخر رهیافت تکاملی ارائه شده برمبنای برنامه نویسی ژنتیکی را شرح می دهیم.

فصل پنجم، نتایج حاصل از اجرای پروژه و مقایسه با روش مرسوم

تعداد صفحات 83 word

فهرست مطالب

عنوان صفحه

فصل اول مقدمه ای بر الگوریتم ژنتیک... 1

1- 1- الگوریتم ژنتیک چیست؟. 2

1-2- فلسفۀ انتخاب اصلح در طبیعت... 2

1-3- مفاهیم پایه ای الگوریتم ژنتیک... 3

1-3-1- تابع ارزیابی.. 5

1-3-2- نحوۀ کد کردن متغیر های تابع.. 5

1-3-3- ایجاد جمعیت اولیه. 6

1-3-4- ارزیابی کروموزوم ها 7

1-3-5- انتخاب والد برای ایجاد نسل بعد. 8

1-3-6- تولید نسل جدید. 12

1-3-7- پایان دادن به اجرا 15

فصل دوم مدار های ترتیبی همگام و مسئلۀ تخصیص حالت... 16

2-1- مدار های ترتیبی همزمان (همگام) 17

2-1-1-مدل های میلی و مور. 18

2-1-2- فرایند طراحی مدار های ترتیبی.. 19

2-1-3- تخصیص حالت... 21

2-1-4- شناسایی یک تخصیص حالت خوب.. 26

2-2- کاربرد سخت افزار تکاملی در مساله تخصیص حالت... 26

2-3- الگوریتم ژنتیک در تخصیص حالت... 26

2-3-1- تعریف کروموزوم ها 27

2-3-2- ایجاد جمعیت اولیه. 28

2-3-3- ارزیابی هزینۀ یک نمونۀ تخصیص حالت... 28

2-3-4- انتخاب تخصیص حالت های مناسب... 32

2-3-5- انجام عمل ادغام روی جمعیت... 32

2-3-6- انجام عمل جهش روی جمعیت... 33

2-3-7- شرایط خاتمۀ الگوریتم.. 34

فصل سوم برنا مه نویسی ژنتیکی.. 35

3-1- برنامه نویسی ژنتیکی چیست؟. 36

3-1-1- کروموزوم ها در برنامه نویسی ژنتیکی.. 36

3-1-2- ایجاد جمعیت اولیه. 37

3-1-3- انتخاب کروموزوم برای ایجاد نسل جدید. 37

3-1-4- تولید نسل جدید. 38

3-2-گام های مقدماتی در اجرای برنامه نویسی ژنتیکی.. 40

3-2-1- گام اول : مجموعۀ پایانه ها 40

3-2-2-گام دوم : مجموعه توابع.. 42

3-2-3- گام سوم : تابع سودمندی.. 43

3-2-4- گام چهارم : پارامتر های برنامه نویسی ژنتیکی.. 44

3-2-5-گام پنجم : شرایط خاتمه و خروجی برنامه. 44

3-3- یک نمونه اجرای برنامه نویسی ژنتیک... 44

3-3-1-گام های مقدماتی.. 45

3-3-2- گام به گام اجرای برنامه. 47

3-3-2-1- ایجاد جمعیت اولیه. 47

3-3-2-2- ارزیابی سودمندی.. 49

3-3-2-3- انتخاب، ادغام و جهش.... 49

3-3-2-4- شرایط خاتمه و خروجی برنامه. 51

فصل چهارم بهینه سازی یک مدار ترکیبی.. 53

4-1- موارد موثر در کارایی مدار. 54

4-1-1- تعداد گیت های به کار رفته در مدار. 54

4-1-2- تأخیر انتشار یک گیت... 55

4-2- سخت افزار تکاملی در بهینه سازی بخش ترکیبی مدار. 56

4-3- برنامه نویسی ژنتیکی در بهینه سازی مدار های ترکیبی.. 59

4-3-1ساختار کروموزوم ها 60

4-3-2- مقایسۀ ساختار ماتریسی و ساختار درختی در برنامه نویسی ژنتیکی.. 63

4-3-4- ارزیابی سودمندی مدار. 63

4-3-5- انتخاب و ایجاد جمعیت جدید. 65

4-3-6- باز تولید مدار. 66

فصل پنجم نتایج و مقایسۀ انها 69

5-1- مقایسۀ یک نمونه مدار پس از دو مرحله بهینه سازی.. 70

مراجع و منابع.. 73

فهرست اشکال

عنوان صفحه

شکل 1-1: مقایسه ای بین الگوریتم ژنتیک و تکامل زیستی.. 2

شکل 1-2: نمودار گردشی الگوریتم ژنتیک... 4

شکل 1-3-ادغام تک نقطه ای.. 13

شکل 1-4- ادغام دو نقطه ای.. 13

شکل 1-5- ادغام یکنواخت... 14

شکل 1-6-یک نمونه عمل ادغام. 14

شکل 2-1 ساختار کلی مدل مدار های ترتبی میلی.. 18

شکل 2-2- فرایند طراحی مدار های ترتیبی.. 19

شکل 2-3 نمودار ماشین حالت... 21

شکل 2-4 ساده سازی در سطح گیت با روش نقشه کارنو. 23

شکل 2-5- مدار خروجی با تخصیص حالت 2-1. 24

شکل 2-6 ساده ساری در سطح گیت با روش نفشه کارنو برای تخصیص حال جدید. 25

شکل 2-7- مدار حاصل از تخصیص حالت جدید. 26

شکل 2-8- یک نمونه کروموزوم برای تخصیص حالت 3-2. 28

شکل 2-9 ماتریس AM... 30

شکل 3-1- ساختار درختیGPدر نمایش عبارت max(x+x,x+3*y) 37

شکل 3-2- کروموزوم های والد. 38

شکل 3-4 کروموزوم های والد مشابه. 38

شکل 3-5 –فرزندان متفاوت از والد های کاملاً مشابه. 39

شکل 3-6- مدل های جهش.... 39

شکل 3-6 جمعیت اولیه. 48

شکل 3-7 –مقایسۀ نمودار های مربوط به عبارت های حاصل از نسل اول با نمودار مربوط به عبارت هدف.. 48

شکل 3-8 جمعیت نسل جدید. 50

شکل 4-1- نمونه ای از معادل سازی گیت ها 55

شکل 4-2- ساختار فنوتیپ ارائه شده توسط لوییس.... 57

شکل 4-3- ژنوتیپی بر مبنای فتوتیپ ارائه شده توسط لوییس.... 58

شکل 4-4 نمونه ای از مدار ترکیبی با فنوتیپ لویس.... 58

جدول 4-1- تعداد گیت های معدل و تأخیر در یک نمونه گیت... 60

شکل4-5- ساختار ژن در این نوع کروموزوم ها 61

شکل 4-6- مدار مربوط به کروموزوم بالا. 62

شکل 4-7 ادغام چهار نقطه. 67

شکل 5-1- مدار (1) با یک تخصیص حالت نامناسب... 70

شکل 5-2- مدار (1) با تخصیص حالت بهینه. 71

شکل 5-3- مدار(1)پس از بهینه سازی بخش ترکیبی.. 71

شکل5-4- نمودار بهترین سودمندی مدارها در نسل های مختلف... 72

فهرست جداول

عنوان صفحه

جدول 1-1- نمونه ای از یک جمعیت تصادفی.. 7

جدول 1-2- کروموزوم های انتخابی.. 9

جدول 1-3- احتمال تجمعی کروموزوم ها 11

جدول 1-4- احتمال اننتخاب هر کروموزوم بر مبنای هزیۀ ان.. 12

جدول 2-1 جدول حالت مربوط به ماشین حالت فوق.. 21

جدول 2-2 جدول درستی ماشین حالت... 23

جدول 2-3 جدول درستی ماشین حالت با تخصیص حالت جدید. 24

جدول3-1- مجموعه پایانه. 41

جدول 3-2- مجموعه توابع.. 42

پایان نامه الگوریتم ژنتیک برنامه نویسی ژنتیکی ساختار کروموزوم ها پایان نامه سخت افزار تکاملی

سجاد یکشنبه 27 تیر 1395 ساعت 11:51