لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه51
فهرست مطالب
بخش اول : الگوریتم ژنتیک
الگوریتم ژنتیک چیست؟
نحوه انجام عملیات جهش
نقاط قوت الگوریتم های ژنتیک:
تغییر از یک نسل به نسل بعدی(Crossover)
چکیده:
الگوریتم های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش بینی یا تطبیق الگو استفاده می کنند. الگوریتم های ژنتیک اغلب گزینه خوبی برای تکنیک های پیش بینی بر مبنای رگرسیون هستند. همچنین ساده خطی وپارامتریک نیزگفته می شود، به الگوریتم های ژنتیک می توان غیر پارامتریک نیز گفت.
مختصراً گفته می شود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می کند. مسئله ای که باید حل شود ورودی است و راه حل ها طبق یک الگو کد گذاری می شود ومتریک که تابع fitness هم نام دارد هر راه حل کاندید را ارزیابی می کندکه اکثر آنها به صورت تصادفی انتخاب می شوند. یکی از مهمترین کاربردهای الگوریتم های ژنتیک حل مسئله فروشنده دوره گرد می باشد که در بخش دوم به طور کامل به آن می پردازیم.
کلاً این الگوریتم ها از بخش های زیر تشکیل می شوند :
انتخاب مجدد selection
ترکیب combination
جهش ژنی mutation
که در ادامه آنها را توضیح خواهیم داد.
مقدمه:
قانون انتخاب طبیعی بدین صورت است که تنها گونههایی از یک جمعیت ادامه نسل میدهند که بهترین خصوصیات را داشته باشند و آنهایی که این خصوصیات را نداشته باشند به تدریج و در طی زمان از بین میروند.
مثلا فرض کنید گونه خاصی از افراد هوش بسیار بیشتری از بقیه افراد یک جامعه یا کولونی دارند. در شرایط کاملا طبیعی این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتا بالاتری خواهند داشت و این رفاه خود باعث طول عمر بیشتر و باروری بهتر خواهد بود(توجه کنید شرایط طبیعی است نه در یک جامعه سطح بالا با ملاحظات امروزی یعنی طول عمر بیشتر در این جامعه نمونه با زاد و ولد بیشتر همراه است). حال اگر این خصوصیت(هوش)ارثی باشد به طبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشتر اینگونه افراد بیشتر خواهد بود. اگر همین روند را ادامه دهید خواهید دید که در طی نسلهای متوالی دائما جامعه نمونه ما باهوش و باهوشتر میشود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته است در طی چند نسل عملا افراد کم هوش را از جامعه حذف کند علاوه بر اینکه میزان هوش متوسط جامعه نیز دائما در حال افزایش است.
بدین ترتیب میتوان دید که طبیعت با بهرهگیری از یک روش بسیار ساده(حذف تدریجی گونههای نامناسب و در عین حال تکثیر بالاتر گونههای بهینه) توانسته است دائما هر نسل را از لحاظ خصوصیات مختلف ارتقا بخشد.
در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مساله یاری کند مفهومیست به نام :
تصادف یا جهش.
هدف اصلی روشهای
مشخصات این فایل
عنوان: الگوریتم های ژنتیک
فرمت فایل :پاورپوینت (قابل ویرایش)
تعداد اسلایدها : 54
این پاورپوینت در مورد الگوریتم های ژنتیک می باشد.
بخشی از تیترها به همراه مختصری از توضیحات هر تیتر از پاورپوینت الگوریتم های ژنتیک
الگوریتم های ژنتیک و تنازع بقا :
قانون انتخاب طبیعی : تنها گونه هایی از یک جمعیت ادامه نسل می دهند که بهترین خصوصیت را داشته باشند.
تکامل طبیعی : جستجوی کورکورانه (تصادف)+بقای قوی تر
مقایسه روش های کلاسیک ریاضیات با الگوریتم ژنتیک:
روشهای کلاسیک ریاضیات دارای دو اشکال اساسی هستند:
اغلب این روشها نقطه بهینه محلی(Local Optima) را بعنوان نقطه بهینه کلی در نظر می گیرند.روشهای ریاضی بهینهسازی اغلب منجر به یک فرمول یا دستورالعمل خاص برای حل هر مسئله میشوند. در حالی که روشهای هوشمند دستورالعملهایی هستند که به صورت کلی میتوانند در حل هر مسئلهای به کار گرفته شوند. این نکته را پس از آشنایی با خود الگوریتم بیشتر و بهتر خواهید دید.
معرفی اجمالی GA:
از الگوریتم ژنتیک در مسائل جستجو و بهینه سازی استفاده می گردد.ابتدا یک نسل اولیه ایجاد می گردد(بصورت تصادفی) که در واقع کروموزوم های اولیه هستند. هر یک از این کروموزوم ها جوابی(به عبارت صحیح تر شبه جواب) برای مسئله هستند.اما جواب اصلی که ما به دنبال آن هستیم نیستند. سپس پدیده جهش(با احتمال خیلی کم) ممکن است رخ دهد. در نهایت کروموزموم ها از نظر امتیاز رتبه بندی می گردند(انتخاب تابعی مناسب برای تعیین امتیاز بسیار مهم است)...(ادامه دارد)
ارزیابی( Evaluatio) :
یکتا بودن تابع ارزیابی برای هر مسئله
بررسی هر کروموزوم
توجه به محدودیتهای موجود در مسئله
نسبت دادن یک مقدار به هر کروموزوم با نام برازندگی (Fitness)
Fitness = میزان خوبی یک کروموزوم
Fitness = فاصله باقیمانده تا جواب نهایی
عملیات انتخاب ( Selection ) :
انتخاب یک جفت کروموزوم برای تولیدمثل
تعداد دفعات انتخاب دلخواه
ایده همه روشهای انتخاب = انتخاب بهترین کروموزومها
روشهای موجود:
1) Roulette Wheel Selection
2) Ranking Selection
3) Tournament Selection
و ...(ادامه دارد)
تبادل (Crossover):
از عملگرهای اساسی در الگوریتمهای ژنتیک
مقداردهی پارامتر بعنوان احتمال انجام عمل تبادل
تولید یک عدد تصادفی بین صفر ویک
انجام عمل تبادل در صورتی که عدد تصادفی تولید شده بزرگتر از احتمال انجام تبادل باشد
جمعبندی :
کاربرد الگوریتمهای ژنتیک برای جستجو در فضاهای خیلی بزرگ
کارایی نسبتاً خوب این الگوریتمها در پیدا کردن Global Optima
بدست آوردن یک تابع خوب برای محاسبه برازندگی کروموزومها
دقت زیاد در مقداردهی پارامترهای کنترل....(ادامه دارد)
مقدمه و تاریخچه
روند الگوریتمهای ژنتیک
مزایا و معایب الگوریتمهای ژنتیک
پارامترهای کنترل
حل TSP با استفاده از GA
جمعبندی
کتاب روانشناسی ژنتیک (تحول روانی از تولد تا پیری)
تالیف دکتر محمود منصور
شامل 382 صفحه کتاب با فرمت pdf
لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل: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 نسل مطابق شکل زیر رمز به دست می آورد :
این فقط قسمتی از متن مقاله است . جهت دریافت کل متن مقاله ، لطفا آن را خریداری نمایید
مشخصات این فایل
عنوان: جهش ژنتیکی
فرمت فایل :word(قابل ویرایش)
تعداد صفحات : 19
این مقاله درمورد جهش ژنتیکی می باشد.
بخشی از تیترها به همراه مختصری از توضیحات هر تیتر از مقاله جهش ژنتیکی
جهش القایی
در اثر استفاده از مواد جهشزا بوجود میآید. و باعث افزایش مقدار زمینهای جهش میشوند. بعضی مواد شیمیایی ، تابشهای فرابنفش و اشعه ایکس از عوامل جهشزا به شمار میآیند. جهش القایی بر رابطه مکملی نوکلئوتید تاثیر میگذارد پرتو ایکس و گاما .....(ادامه دارد)
جهش حذف و اضافه
این جهشها اثر نامطلوبی دارند. اگر تعداد مضرب اسید آمینه در سطح نوکلئوتیدهای حذف اضافه شده سه یا مضربی از سه باشد به تعداد مضربها اسید آمینه در پروتئین حذف یا اضافه میشود. رمزها از جایگاه جهش به بعد تغییر میکنند. و پروتئین حاصل از توالی جهش یافته فعالیت نخواهد داشت مگر در مواردی که فقط تعداد کمی اسید آمینه در انتهای کربوکسیل پروتئین عوض شده باشد. این نوع جهشها ، جهش تغییر چارچوب .....(ادامه دارد)
جهش در اثر پرتوها
پرتو فرابنفش عامل جهشزای بسیار موثری است. پرتوهای فرابنفش با طول موج 260 نانومتر بوسیله بازهای DNA به شدت جذب میشوند و این امر به ایجاد تغییرات شیمیایی در رشته DNA میانجامد معروفترین و شناخته شدهترین اثر پرتوفرابنفش بر روی بازهای رشته DNA این است که موجب ایجاد پیوندهای دو تایی (دیمر) بین مولکول تیمین مجاور هم میشود نسخهبرداری غیر طبیعی از این قسمتها که حاوی تیمین دیمر است موجب جهش خواهد شد.
بسیاری از ارگانیسمها دارای آنزیمهای ترمیم کنندهای هستند که میتوانند آسیبهای ناشی از پرتو را ترمیم کنند علاوه بر این ، پرتو فرابنفش میتواند موجب تغییرات دیگر در .....(ادامه دارد)
ژن کوناگون - اعمال گوناگون
اگر چه هر سلولی بالقوه قادر به ساختن همه انواع پروتئین های انسانی است اما سلولها ژن ها را انتخاب استفاده می کنند. بعضی از ژنها سازنده پروتئین هایی هستند که برای اعمال اساسی سلول ضروری است و این ژن ها در هر سلولی فعال باقی میمانند. فی الواقع هر سلول ژنی را فعال می کند که در آن زمان به کار آن محتاج است و بقیه را متوقف .....(ادامه دارد)
DNA دگرگون مساوی با پروتئین دگرگون
در حالیکه یک ژنی جهش یافته است پروتئینی که آن ژن رمز آن را میدهد قاعدتا غیر طبیعی خواهد بود . گاهی پروتئین می تواند اعمال زیستی خود را انجام دهد . ولی ناکامل است و گاهی کاملا ناتوان است . نتیجه نهائی منوط به آنست که این پروتئین چه تغییری یافته و یا چه اهمیتی در اعمال حیاتی دارد
به طور کلی جهش به تغییرات ماده ی ژنتیکی در فرآیندی که به وسیله ی آن تغییر حادث می گردد اطلاق می شود. موجودی که فنوتیپ جدیدی را در اثر جهش نشان می دهد، .....(ادامه دارد)
وی در خصوص دومین مورد اظهار داشت : وارد وارد کردن یک ژن به داخل سلولهای پیگیری بمنظور جایگزینی یا غیر فعال کردن یک ژن جهش یافته غالبی که فرآورده های غیر طبیعی آن موجب بیماری می شود که می توان به بیماری ها نگتینتون ( با تکرار توالی CAG بوجود می آید ) اشاره نمود و سومین مورد پوشاندن ژن جهش یافته می باشد که احتمالاً گسترده ترین کاربرد ژن درمانی است و مبتلایان به بیماری اکتسابی ازجمله سرطان از این روش سود می برند .
محمد جواد سلطانی اظهار داشت : در روش ژن درمانی می توان به دو عامل بسیار مهم ، سلول هدف و خصوصیات ژن انتقال یافته اشاره کرد که سلول هدف ، سلولی است دارای نیمه عمر طولانی در بدن که قابلیت همانند یسازی چشمگیری دارد تا اثر زیستی .....(ادامه دارد)