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

لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه: 44

کار برد های GA

برخی از مهم تر ین کار بردهای GA در علوم مختلف عبارتند از:

زمینه

کاربرد

کنترل:

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

طراحی :

طراحی هواپیما – طراحی مدارات VLSI – شبکه های ارتباطی و ...

مدیریت و برنامه ریزی :

برنامه ریزی تولید – زمان بندی – تخصیص منابع و ...

روباتیک:

مسیر حرکت روبات ...

یادگیری ماشین :

طراحی شبکه های عصبی – الگوریتم های طبقه بندی و ...

پردازش سیگنال:

طراحی فیلتر و ...

سایر موارد:

هنر و موسیقی – حل مسئله فروشنده دوره گرد – مسیر یابی در شبکه ها و ...

طراحی آنتن

سیستم های ارتباط ماهواره ای از آنتنها برای دریافت سیگنال های ارسال شده از ماهواره استفاده می کنند . هر آنتن دارای یک Main  Beam  و تعدادی Sidelobe است .قسمت Main  beam که در جهت ماهواره قرار می گیرد دارای بهره (gain)  بالایی است تا بتواند سیگنال های ضعیف را تقویت کند . اما Sidelobe ها دارای بهر ه های پایینی هستند . بر خلاف Main  beamدر جهت های مختلفی قرار می گیرند . شکل زیر یک آنتن را با Sidelobe و Main  beam آن نشان می دهد .

مشکل این جا است که امکان ورود سیگنال ها ی ناخواسته قوی به داخل Sidelobe ها و یا ورود سیگنال های اصلی ضعیف به داخل Main  beam وجود دارد . فرض کنیم که  Main  beam یک آنتن ماهواره ای در راستا و جهت ماهواره قرار گرفته باشد .  سیگنال ها ی ماهواره بسیار ضعیف هستند زیرا از فاصله بسیار دور و با قدرت کمی ارسال می شوند اگر یک تلفن بی سیم نیز با همان فرکانس ماهواره در نزدیکی آن کار کند ممکن است سیگنال ها ی تلفن  وارد Side lobe آنتن شده و باعث تداخل با سیگنال های اصلی گردد . بنا بر این مهندسان افزایش بهره Main  beam و کاهش بهره Side lobe هستند .

یک نوع از آنتن ها (Antenna   array) است . ویژگی این آنتن ها توانایی آنها را در کاهش بهرة  Side lobeها است . در حقیقت این نوع آنتن یک گروه از آنتن های تکی هستند که سیگنال های آنها را با هم جمع کرده و یک خروجی را تولید می کند .

سیگنال های دریافتی در هر آنتن دارای یک دامنه و فاز است که یک تابعی از فرکانس، موقعیت آنتن و زاویه ارسال سیگنال ها است .

خروجی این آنتن یک تابعی از سیگنال های در یافتی در هر آنتن است . بنا بر این با توجه به مقدار دامنه های سیگنال برای آنتن ها ممکن است باعث کاهش یا حذف Side lobe شود. در این مثال نشان می دهیم که چگونه می توان با استفاده از GAبه طراحی شبکه آنتن با Side lobe کم پرداخت .

مدل این آرایه خطی در راستای محور X و به صورت زیر است :

فرمول ریاضی در این خصوص برای حالتی که Main  beamبه صورت 90 درجه باشد برابر است با :

AF (  ) =  ei(n-1)                                                                                    (8-1)

که در این معادله :

N :تعداد آنتن ها

an: دامنه وزن دهی شده برای am =an+ 1-m که m = 1,2 ,… , N/2

: طول موج

d: فاصله بین آنتن ها

   : زوایه موج میدان الکترو مغناطیس

    =Kdu = Kdcos 

K= 2

هدف در این مسئله پیدا کردن an به گونه ای است که حداقل سطحSide lobe در الگوی آنتن وجود داشته باشد .

یک راه برای مسئله تولید Side lobeهایی برابر-   و پایین پیک Main  beam است به عبارت دیگر هیچگونهSide lobe ای وجود نداشته باشد .

روش حل این مسئله را شبکه دو جمله ای و وزن های دامنه سیگنال را ضرایب دو جمله ای می گویند ، بنا بر این یک آرایه 5 عضوی با وزن هایی که به عنوان ضرایب چند جمله ای در نظر گرفته شده است ، با پنج ضریب در نظر می گیریم .

ضرایب یک معادله چند جمله ای ، از مرتبه (N-1)یا وزن های دو جمله ای یک آرایه N عنصری همان ضرایب چند جمله ایN-1 (Z+1)   مفروض برای N ردیف مثلث پاسکال هستند .                        1                     

                                                        1     1 

                                                    1      2       1

                                                1       3     3       1

                                            1        4      6       4     1

                                             .

                                             .

                                             .    

در اولین تلاش اقدام به حذف Side lobe های یک آرایه 42 تایی با d=0.5 می کنیم .

هر دو روش الگوریتم ژنتیک پیوسته و باینری در پیدا کردن یک محدود کننده دامنه نوسان که حداکثر سطح Side lobeآن کمتر از 4db- و پایین پیک ، Main  beam باشد ناکار آمد هستند و این موضوع ناامید کننده است . مشکل احتمالا" به خاطر تابع هزینه است . تابع هزینه ما برابر با ماکزیمم سطح Side lobeمعادله (8-1) با پارامتر anاست . پیاده کردن این فرمول مشکل و همراه با جواب های نا خواسته ای خواهد بود که منجر به منحرف شدن GA می گردد .

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

این روش همان تبدیل  zبرای معادله 8-1 است . بنا بر این با جایگذاری مقدار            

در معادله فوق خواهیم داشت :

AF

تابع هزینه حداکثر سطح Side lobe معادله فوق است که  به عنوان پارامتر آن در نظر گرفته می شود . شکل 50 همگرایی GAپیوسته را با تعداد 21 متغیر و تعداد 8 کروموزوم در Mating  pool  و  نشان می دهد .

و برای این روش GAباینری نیز جواب به صورت شکل 51 در می آید :

 هر الگوریتم پس از 10 بار تکرار و با تولید مقادیر به صورت تصادفی اجرا می شود . شکل زیر نتیجه میانگین هزینه را پس از 75 نسل برای این دو الگوریتم نشان می دهد :

همان طور که در شکل مشخص است ، روش باینری از این روش پیوسته جلو افتاده است. اما چرا ؟ شاید یک دلیل آن اندازه فضای جستجو باشد.

مسئله فروشنده دوره گرد TSP  

این مسئله یکی از مسائل مشهور در بهینه سازی و در بسیاری از رشته های مهندسی است که در طی چندین سال یک راه حل جامعی با استفاده از روش های کلاسیک بهینه سازی برای حل آن وجود نداشته است . هدف در این مسئله پیدا کردن کوتاه ترین مسیر برای فروشنده دوره گرد است که باید از N شهر بگذرد . این نوع مسئله در بسیاری از کاربرد های مهندسی مثل لوله کشی خطوط گاز ، طراحی آنتن ها، نحوه قرار گیری ترانزیستورها در مدارات VLSI و یا مرتب کردن اشیاء برای یک پیکره بندی خاص کاربرد دارد . اویلر در سال 1759 یک فرمی از این مسئله را ارائه کرد که در سال 1948 توسط شرکت Rand معرفی شد . مقدار تابع هزینه به فرم ساده برای این مسئله با توجه به مسافتی که فروشنده طی می کند با:

فرض موقعیت (  Xn ,yn  ) و N و ...وn=1 برابر است با :

که در این فرمول (  Xn ,yn ) مختصات و موقعیت n امین شهر است .

برای مثال ، فرض کنیم نقطه ابتدا و انتها برابر با :

 باشد از آنجایی که مسیر های محتمل بهینه بسیار زیادی با افزایش تعداد شهر ها به وجود می آید ، امکان حل این مسئله با استفاده از روش های بهینه سازی کلاسیک وجود ندارد . حتی در مقایسه با شبکه های عصبی الگوریتم ژنتیک نشان داده اند که در حل این مسئله بهتر عمل می کنند ! برای عملگر ادغام در حل این مسئله از روش جایگشتی (Permutation ) استفاده شده است و عملگر جهش ( موتاسیون ) به صورت تصادفی یک رشته را انتخاب کرده و بر روی آن عمل می کند .

برای مثال تعداد شهر ها را برابر با N =13 در نظر می گیریم که تعداد ترکیب های نقاطی که باید چک شود برابر است با :                            13!/2 = 3.1135* 109

برای شروع فرض می کنیم شهرها به صورت مستطیلی شکل و مطابق شکل زیر قرار گرفته باشند .

تعداد 200 کروموزوم و نرخ جهشی برابر با 04/0 پس از 35 نسل به صورت شکل می گردد :

حال فرم پیچیده تری را در نظر می گیریم . فرض کنیم 25 شهر به صورت تصادفی در یک مستطیلی با ابعاد 1*1 قرار گرفته اند . در این حالت برای 50 کروموزوم و با نرخ موتاسیون 04/0 پس از 130 نسل مقدار مینیمم به دست می آید . شکل زیر نحوه همگرایی الگوریتم را نشان می دهد :

و شکل نیز جواب بهینه ( بهترین مسیر) را نشان می دهد :  

یک نتیجه مهم : جمعیت های کوچک با نرخ موتاسیون بالا برابر حل مسائل جایگشتی

( Permutation )مناسب نیست .

رمز گشایی یک پیام سری :

در این مثال ، از روش GA پیوسته برای شکستن یک رمز استفاده می کنیم . یک پیام رمز شامل یکسری حروف جا به جا شده است که به صورت تصادفی و یا بر اساس یک متد خاص قرار گرفته اند . برای مثال :فرض کنیم تمام حروف dرا با حرف cو فضاهای خالی را با  qنشان دهیم . اگر پیام از همه حروف الفبا به علاوه فضای خالی استفاده کند . تعداد !27 ( فاکتوریل ) کد ممکن وجود دارد که فقط یکی از آنها درست است و اگر پیام از s سمبل استفاده کند تعداد !s - !27 کد ممکن وجود خواهد داشت .

بنابراین یک کروموزوم شامل 27 ژن با مقادیر واحدی از 1 تا 27 متناظر با حروف الفبا در نظر گرفته می شود . مثلا" 1 برای فضای خالی (space) 2 برای a و ...

مقدار تابع هزینه (Cost   function)مطابق فرمول زیر از تفاضل حدس (guess) از پیام (message) و جمع این مقادیر به دست می آید .

اگر مقدار Costصفر باشد ، یعنی پیام کشف شده است .

برای مثال فرض کنیم بخواهیم ببینیم GA برای رمز گشایی پیام :

"bonny and amy are our children"                                          

چگونه عمل می کند .

این پیام در مجموعه شامل 30 سمبل است .

 GAدر این مسئله با فرض جمعیت کروموزوم در mating  pool  برابر با 40 و نرخ جهشی برابر با 20/0پس از 68 نسل مطابق شکل زیر رمز به دست می آورد :

این فقط قسمتی از متن مقاله است . جهت دریافت کل متن مقاله ، لطفا آن را خریداری نمایید