کاربرد های 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 امین شهر است .