عنوان :
تعداد صفحات : ۵۲
نوع فایل : ورد و قابل ویرایش
یکی از شاخههای پردازش تکاملی، الگوریتمهای ژنتیک میباشد. الگوریتم ژنتیک (یا GA) یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می کند. مسئله ای که باید حل شود ورودی است و راه حل ها طبق یک الگو کد گذاری می شود ومتریک که تابع fitness هم نام دارد هر راه حل کاندید را ارزیابی می کندکه اکثر آنها به صورت تصادفی انتخاب می شوند.
در ابتدای مقاله قسمتهای مختلف یک الگوریتم ژنتیک را بیان کرده و هریک را به اختصار تشریح میکنیم. سپس بیان میکنیم که یک الگوریتم ژنتیک چه خصوصیاتی باید داشته باشد، سپس یکی از مهمترین کاربردهای الگوریتم های ژنتیک حل مسئله فروشنده دوره گرد می باشد .
در برنامه نویسی ژنتیک سعی میکنیم که با استفاده از الگوریتمهای ژنتیک، و مفاهیم درختهای تجزیه برای کاربردهای خاص، به جای اینکه کد برنامه لازم را بنویسیم، به کامپیوتر این امکان را بدهیم که تنها با دانستن مفهوم کلی از کار، برنامه مورد نظر را برایمان آماده کند. در واقع یک دستور سطح بالا به کامپیوتر بدهیم و خود کامپیوتر برنامه لازم برای اجرای برنامه مورد نظر را آماده کند، سپس برنامه را اجرا و خروجی مطلوب ما را به ما ارائه دهد.
واژه های کلیدی: الگوریتم ژنتیک، انتخاب مجدد، ترکیب، جهش ژنی، حل مسئله فروشنده دوره گرد، برنامه نویسی ژنتیک
چکیده ۴
مقدمه ۵
الگوریتم ژنتیک چیست؟ ۹
ایده اصلی ۱۴
جهش ۱۸
الگوریتم ۲۱
نقاط قوت الگوریتم های ژنتیک: ۲۴
محدودیتهای GAها ۲۵
چند نمونه از کاربرد های الگوریتم های ژنتیک: ۲۶
چند نمونه مساله حل شده با الگوریتم ژنتیک ۲۷
تغییر از یک نسل به نسل بعدی(Crossover) ۳۰
Mutation ۳۷
برنامه نویسی ژنتیک ۴۱
آشنائی با برنامه نویسی ژنتیک ۴۱
تاریخچه ۴۱
برنامه نویسی ژنتیک چیست؟ ۴۱
قدمهای اولیه برنامه نویسی ژنتیک: ۴۲
درختهای تجزیه (Parse Trees): ۴۳
برنامه نویسی ژنتیک و یک مثال ۴۴
فهرست منابع ۵۲
قانون انتخاب طبیعی بدین صورت است که تنها گونههایی از یک جمعیت ادامه نسل میدهند که بهترین خصوصیات را داشته باشند و آنهایی که این خصوصیات را نداشته باشند به تدریج و در طی زمان از بین میروند.
مثلا فرض کنید گونه خاصی از افراد هوش بسیار بیشتری از بقیه افراد یک جامعه یا کولونی دارند. در شرایط کاملا طبیعی این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتا بالاتری خواهند داشت و این رفاه خود باعث طول عمر بیشتر و باروری بهتر خواهد بود(توجه کنید شرایط طبیعی است نه در یک جامعه سطح بالا با ملاحظات امروزی یعنی طول عمر بیشتر در این جامعه نمونه با زاد و ولد بیشتر همراه است). حال اگر این خصوصیت(هوش)ارثی باشد به طبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشتر اینگونه افراد بیشتر خواهد بود. اگر همین روند را ادامه دهید خواهید دید که در طی نسلهای متوالی دائما جامعه نمونه ما باهوش و باهوشتر میشود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته است در طی چند نسل عملا افراد کم هوش را از جامعه حذف کند علاوه بر اینکه میزان هوش متوسط جامعه نیز دائما در حال افزایش است.
بدین ترتیب میتوان دید که طبیعت با بهرهگیری از یک روش بسیار ساده(حذف تدریجی گونههای نامناسب و در عین حال تکثیر بالاتر گونههای بهینه) توانسته است دائما هر نسل را از لحاظ خصوصیات مختلف ارتقا بخشد.
در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مساله یاری کند مفهومیست به نام :
تصادف یا جهش.
هدف اصلی روشهای هوشمند به کار گرفته شده در هوش مصنوعی یافتن پاسخ بهینه مسائل مهندسی است. به عنوان مثال اینکه چگونه یک موتور را طراحی کنیم تا بهترین بازدهی را داشته باشد یا چگونه بازوهای یک ربات را محرک کنیم تا کوتاهترین مسیر را تا مقصد طی کند(دقت کنید که در صورت وجود مانع یافتن کوتاهترین مسیر دیگر به سادگی کشیدن یک خط راست بین مبدا و مقصد نیست) همگی مسائل بهینهسازی هستند.
در مورد نکته دوم باید بگوییم که روشهای ریاضی بهینهسازی اغلب منجر به یک فرمول یا دستورالعمل خاص برای حل هر مسئله میشوند. در حالی که روشهای هوشمند دستورالعملهایی هستند که به صورت کلی میتوانند در حل هر مسئلهای به کار گرفته شوند. این نکته را پس از آشنایی با خود الگوریتم بیشتر و بهتر خواهید دید.
اما یک موجود چگونه قادر است که شکل و فرم موجودات بعد از خود را تعیین کند؟ برای اینکه جواب سوال را دریابیم، ابتدا باید فرآیند تولید مثل موجودات را بررسی کنیم.
در جریان تولید مثل یک موجود کروموزومهای والدین موجود با یکدیگر ترکیب میشوند و سلول تخم را تشکیل می دهند. تکثیر این سلول تخم منجر به تشکیل یک فرزند تقریباً مشابه والدینش میشود. این موجود ترکیبی از خصوصیات والدین خود را به همراه خواهد داشت. این روند باعث تکامل یک موجود میشود.
اما تا اینجای کار اتفاق خاصی که باعث ایجاد یک موجود جدید گردد به وقوع نپیوسته است. نکته کار اینجاست که در حین تشکیل سلول تخم تغییرات ناخواستهای درون کروموزوم(های) سلول بوجود میآید. این تغییرات اگر کوچک باشند، در حین تکثیر سلول تخم و تشکیل موجود اصلی اصلاح میشوند. اما تغییرات بزرگ اصلاح نمیشوند و منجر به تشکیل یک موجود جدید میشوند.
اگر موجود جدید (و بطور کلی فرزند) ایجاد شده نسبت به والدین در تقابل با محیط برتری داشته باشد، قطعاً در جریان زندگی موفقتر است و امکان تولید مثل پیدا میکند و در نتیجه میتواند خصوصیات خوبش را به فرزندانش منتقل نماید. با توجه به اینکه این فرزندان نیز در تقابل با محیط موفقتر هستند، امکان تولید مثل پیدا میکنند.
با توجه به مطالب فوق متوجه میشوید که سه فاکتور اصلی مبنای نظریه داروین را تشکیل میدهند، این سه فاکتور عبارتند از:
تنوع: ترکیب شدن مشخصات والدین متفاوت باعث میشود که خصوصیات خوب آنها ترکیب شود و یک موجود بهتر بوجود آید.
تصادف: عامل ایجاد تغییرات در موجودات فرزند
انتخاب: که توسط محیط انجام میشود، به این معنی که موجودات با شایستگی پائین احتمال ادامه حیات و تولید مثل کمتری دارند. (بقای شایستهترین)
روند فوق و مخصوصاً سه فاکتور فوق مبنای کار دانشمندان رشته کامپیوتر قرار گرفت و در نتیجه الگوریتمهای ژنتیک بوجود آمدند. این روش در سال ۱۹۷۰ توسط John Holland معرفی گردید
این روشها با نام Evolutionary Algorithms نیز خوانده میشوند. پیشرفت این الگوریتمها باعث شد که کلاً مجموعه روشهای حل مساله با نام پردازش تکاملی بوجود بیاید.
پردازش تکاملی از شاخههای زیر تشکیل شده است:
الگوریتمهای ژنتیک (Genetic Algorithms)
برنامه نویسی ژنتیک (Genetic Programming)
استراتژیهای تکاملی (Evolutionary Strategies)
برنامه نویسی تکاملی (Evolutionary Programming)
نحوه ارائه مطالب به این صورت است که در ابتدا قسمتهای مختلف یک الگوریتم ژنتیک را بیان کرده و هریک را به اختصار تشریح میکنیم. سپس بیان میکنیم که یک الگوریتم ژنتیک چه خصوصیاتی باید داشته باشد،
همانطور که گفتیم یکی از شاخههای پردازش تکاملی، الگوریتمهای ژنتیک میباشد. این الگوریتمها با الهام از روند تکاملی طبیعت، مسائل را حل میکنند. به این معنی که مانند طبیعت یک جمعیت از موجودات تشکیل میدهند و درون این موجودات اقدام به انجام اعمالی چون انتخاب والدین، تولید مثل، جهش و … میکنند و این اعمال را آنقدر تکرار میکنند تا به مجموعه بهینه و یا موجود بهینه برسند.
این الگوریتمها با توجه به خصوصیات خاصی که دارند، به خوبی از عهده حل مسائلی که نیاز به بهینهسازی دارند و یا پارامترهای زیادی در آنها دخیل است، برمیآیند. در این قسمت به معرفی این الگوریتمها میپردازیم.
موتور الگوریتم ژنتیک یک جمعیت آغازین از فرمول ایجاد می کند.هر فرد در برابر مجموعه ای از داده های مورد آزمایش قرار می گیرد و مناسبترین آنها انتخاب می شود که شاید ۱۰ درصد از مناسبترین ها باقی بمانند و بقیه کنار گذاشته می شوند. مناسبترین افراد با هم جفتگیری (جابجایی عناصر دی ان ای)وتغییر(تغییر تصادفی عناصر دی ان ای) کرده اند.مشاهده می شود که با گذشت از میان تعداد زیادی از نسلها،الگوریتم ژنتیک به سمت ایجاد فرمول هایی که خیلی دقیق ترهستند،میل می کنند.جذابیت زیاد الگوریتم های ژنتیک این است که نتایج نهایی قابل ملاحظه ترند.فرمول نهایی برای کاربر انسانی قابل مشاهده خواهد بود،و برای ارائه سطح اطمینان نتایج می توان تکنیک های آماری متعارف رابر روی این فرمول ها اعمال کرد.فناوری الگوریتم های ژنتیک همواره در حال بهبود است.
الگوریتم ژنتیک GA یک تکنیک جستجو در علم کامپیوتربرای یافتن راه حل بهینه ومسائل جستجو است.الگوریتم های ژنتیک یکی از انواع الگوریتم های تکاملی اند که از علم زیست شناسی مثل وراثت، جهش،انتخاب ناگهانی ، انتخاب طبیعی و ترکیب الهام گرفته شده اند.
عموماً راه حلها به صورت ۲ تایی ۰ و۱ نشان داده می شوند ولی روشهای نمایش دیگری هم وجود دارد.تکامل از یک مجموعه کاملاً تصادفی از موجودیت ها شروع می شود و در نسلهای بعدی تکرار می شود.در هر نسل،مناسبترین ها انتخاب می شوند نه بهترین ها.
یک راه حل برای مسئله مورد نظر،با یک لیست از پارامترها نشان داده می شود که به آنها کروموزوم یا ژنوم می گویند. کروموزوم ها عموماً به صورت یک رشته ساده از داده ها نمایش داده می شوند،البته انواع ساختمان داده های دیگر هم می توانند مورد استفاده قرار گیرند:
اعداد صحیح
رشتههای بیتی
اعداد حقیقی در فرم نقطه شناور
اعداد حقیقی به فرم رشته های بیتی
یک مجموعه از اعداد حقیقی یا صحیح
ماشینهای حالت محدود
هر فرم دیگری که بتوانیم عملگرهای ژنتیک را بر روی آنها تعریف کنیم
در ابتدا چندین مشخصه به صورت تصادفی برای ایجاد نسل اول تولید می شوند. در طول هر نسل ،هر مشخصه ارزیابی می شود وارزش تناسب(fitness) توسط تابع تناسب اندازه گیری می شود.
سپس باید نسل اولیه را مشخص کنیم. بعد از اینکه شکل کروموزومها را تعریف نمودیم، بایستی جمعیتی را تشکیل دهیم، که میخواهیم عناصر آنرا تکامل دهیم. تعداد عناصر موجود در این جمعیت معمولاً ثابت است. به این معنی که هنگامی که تعدادی عنصر در جریان تولید مثل به این جمعیت اضافه میکنیم، بایستی به همین تعداد عنصر نیز از جمعیت قبلی حذف کنیم.
قبل از اینکه الگوریتم بتواند آغاز به کار کند، بایستی یک جمعیت اولیه از کروموزومها تشکیل بدهیم. در اکثر الگوریتمها این جمعیت اولیه به صورت تصادفی تشکیل میشود. به این معنی که به اندازه طول جمعیت، کروموزوم تصادفی ایجاد میکنیم و آنها را به جمعیت اولیه اضافه میکنیم.
جهت دریافت و خرید متن کامل مقاله و تحقیق و پایان نامه مربوطه بر روی گزینه خرید انتهای هر تحقیق و پروژه کلیک نمائید و پس از وارد نمودن مشخصات خود به درگاه بانک متصل شده که از طریق کلیه کارت های عضو شتاب قادر به پرداخت می باشید و بلافاصله بعد از پرداخت آنلاین به صورت خودکار لینک دنلود مقاله و پایان نامه مربوطه فعال گردیده که قادر به دنلود فایل کامل آن می باشد .