فایل ورد کامل تحقیق الگوریتم ژنتیک؛ بررسی علمی اصول محاسبات تکاملی و کاربردهای آن در علوم مهندسی و رایانه

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

 فایل ورد کامل تحقیق الگوریتم ژنتیک؛ بررسی علمی اصول محاسبات تکاملی و کاربردهای آن در علوم مهندسی و رایانه دارای ۲۱ صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد فایل ورد کامل تحقیق الگوریتم ژنتیک؛ بررسی علمی اصول محاسبات تکاملی و کاربردهای آن در علوم مهندسی و رایانه  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی فایل ورد کامل تحقیق الگوریتم ژنتیک؛ بررسی علمی اصول محاسبات تکاملی و کاربردهای آن در علوم مهندسی و رایانه،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از متن فایل ورد کامل تحقیق الگوریتم ژنتیک؛ بررسی علمی اصول محاسبات تکاملی و کاربردهای آن در علوم مهندسی و رایانه :

الگوریتم ژنتیک

الگوریتم ژنتیک از روشهای جستجوی مستقیم اتفاقی است که بر پایه اصول انتخاب طبیعی و بقای اصلح قرار دارد. اصطلاحات بکار رفته در الگوریتم ژنتیک کاملاً شبیه واژگان ژنتیک طبیعی است و حتی تشابه نزدیکی بین عناصر این دو وجود دارد. این روش، اولین بار توسط جان هلند از دانشگاه میشیگان در سال ۱۹۷۵ پیشنهاد شد.
ساختار اصلی که توسط الگوریتم پردازش می‌شود، رشته ( کرموزم ) است. یک رشته زنجیره ای از تعدادی کد ( اغلب کدهایی دودیی ) با طول معلوم است. بیتهای رشته (صفر یا ۱ در یک رشته دودویی) معادل ژنهای طبیعی‌اند. هر کدام بیانگر یک متغیر ( مشابه یک ویژگی در ژنتیک طبیعی همانند رنگ چشم ) و هر مصداق خاصی از کد به طور مستقیم یا غیر مستقیم بیانگر مقدار مشخصی از آن متغیر است ( معادل مثلاً چشم آبی ).

شکل ۱- رشته در الگوریتم ژنتیک شامل پارامترها بصورت کد دودویی است.
کدهای یک رشته به اندازه تعداد متغیرهاست، پس یک رشته اساسا بیانگر یک جواب ممکن است. با الگوریتم ژنتیک ایجاد یک جمعیت اولیه از رشته‌ها از طریق انتخاب تصادفی مقادیر بیتهای رشته آغاز می‌شود. تعداد رشته‌ها (کروموزمها) در جمعیت، اندازه جمعیت نامیده می‌شود. اندازه جمعیت در ابتدا توسط کاربر تعیین می‌شود یا اینکه بر طبق قاعده‌ای که بعدا خواهد آمد، توسط کامپیوتر تعیین می‌شود و در طی جستجو، ثابت نگه داشته می‌شود.
برازندگی یک رشته (جواب ممکن ) توسط تابع محاسبه می‌شود. چون الگوریتم ژنتیک دنبال ماکزیمم کردن برازندگی جوابهای ممکن است، در یک مسأله ماکزیمم سازی، برازندگی برابر مقدار تابع هدف محاسبه شده برای مقادیر خاص پارامتر که هر رشته بیان می‌کند، می‌باشد. یعنی تابع برازندگی همان تابع هدف است اما در مسأله مینیمم سازی برازندگی با افزایش تابع هدف کاهش می‌یابد. یک راه برای جبران آن تعریف تابع برازندگی به صورت :
۱- تابع هدف- مقدار ثابت = تابع برازندگی
که مقدار ثابت به اندازه کافی بزرگ انتخاب می‌شود تا از منفی شدن برازندگی جلوگیری شود. یک مقدار متداول برای این مقدار ثابت، مجموع و ماکزیمم تابع هدف درهر نسل است.
روش دیگرمعکوس کردن تابع هدف می‌باشد.
پس از ارزیابی رشته‌های نسل صفر، نسل جدید (نسل اول) از برازنده‌ترین اعضای نسل صفر ایجاد می‌شود. برای این کار، در یک فرایند انتخاب آن والدین اعضای نسل جدید انتخاب می‌گردد، به هر رشته وزنی متناسب با برازندگیش داده می‌شود. این فرایند تولید مثل متناسب با برازندگی نامیده می‌شود و تعداد کپی‌هایی از هر رشته در نسل حاضر را که به اتاق لقاح می‌روند، تعیین می‌کند. رشته‌های انتخاب شده شانس آن را می‌یابند که در ایجاد رشته‌های نسل بعد شرکت کنند. هیچ تضمینی برای بقای یک فرد وجود ندارد بلکه تجربه‌های تصادفی تصمیم می‌گیرند که کدام بالاتری، اما نه تضمین، برای بقا دارند.
ساده‌ترین راه برای انجام تولید مثل متناسب با برازندگی شبیه سازی فرایند با عملکرد یک چرخ رولت وزندار است. هر رشته از جمعیت دارای یک قطاع چرخ است که اندازه آن متناسب با برازندگی آن رشته است. در نتیجه احتمال انتخاب برابر برازندگی نسبی است. یک مسأله در مورد انتخاب چرخ رولت واضح است. فرایند انتخاب نه تنها به رتبه هر فرد بلکه به تعریف دقیق تابع هدف بستگی دارد. هر تبدیل غیرخطی تابع برازندگی بر فرایند انتخاب اثر می‌گذارد. بنابر این مسأله زیر در انتخاب چرخ رولت پیش می‌آید : در طی اولین نسل، جمعیت خیلی ناهمگن است. یعنی برازندگی افراد خیلی متفاوت است. وقتی که الگوریتم شروع به همگرا شدن می‌کند، برازندگی همه افراد خیلی شبیه هم می‌شود، در نتیجه همه افراد تقریباً با احتمال یکسان بقا می‌یابند، به عبارت دیگر قدرت انتخاب خیلی کم می‌شود و الگوریتم ژنتیک به جستجوی اتفاقی تباه می‌شود. (شکل ۲)

شکل ۲- ده فرد از بین جمعیت صد عضوی انتخاب می‌شود. قدرت انتخاب بالاست اگر افراد بهتر بر بدتر ترجیح داده شود. پایین‌ترین قدرت انتخاب ممکن زمانی است که همه افراد مستقل از رتبه‌شان بقا یابند. در این حالت الگوریتم ژنتیک به جستجوی اتفاقی ناکارا تباه می‌شود.
برای جلوگیری از این مسأله، چندین روش برای مقیاس بندی مقادیر برازندگی پیشنهاد شده است. یک راه حل ساده آن است که مقادیر برازندگی چنان مقیاس بندی شود که بالاترین مقدار همواره به یک و پایین ترین مقدار همواره به صفر نگاشته شود. با چنین مقیاس بندی قدرت انتخاب در همه نسلها ثابت می‌ماند.
برای تولید مثل، چرخ رولت به تعداد اندازه جمعیت چرخانده می‌شود. در هر چرخش یک عدد برنده به دست می‌آید که مشخص کننده رشته ای است که وارد اتاق لقاح می‌شود. واضح است که هر چه قطاع این رشته بزرگتر باشد، احتمال اینکه کپی‌هایی در اتاق لقاح داشته باشد ولذا در ایجاد نسل بعدی شرکت کند، بالاتر است.
رشته‌ها در اتاق لقاح به طور تصادفی لقاح می‌کنند. یعنی زوج رشته‌ها به طور تصادفی انتخاب شده، مخلوط شده و احتمالا توسط عملگرهای ژنتیکیب تولید رشته‌های نسل بعدی تغییر می‌کنند.

شکل ۳- ایجاد نسل بعدی در الگوریتم ژنتیک
دو عملکرد ژنتیکی متداول عبارتند از پیوند و جهش، پیوند مهمترین عملگر ژنتیکی است. پیوند یک نقطه‌ای ساده به صورت زیر است: وقتی که زوجی از رشته‌ها به صورت اتفاقی از اتاق لقاح انتخاب شد، یک موقعیت صحیح K (محل پیوند) در طول رشته به طور تصادفی بین ۱و l-1 که I طول رشته برحسب بیت است انتخاب می‌شود. حال با تعویض تمام بیتهای بین موقعیت K+1 وI دو رشته جدید ایجاد می‌شود. در پیوند دو نقطه‌ای، دو نقطه پیوند انتخاب می‌شود و بخشی از رشته که بین این دو نقطه است، جابجا می‌شود تا دو بچه بوجود آید. می‌توان بطور مشابه پیوند n نقطه‌ای تعریف کر د. پیوند یک نقطه‌ای در شکل (۴) نشان داده شده است.

شکل ۴- عملگر پیوند در الگوریتم ژنتیک
فرایند لقاح با سایر زوج رشته‌ها تکرار می‌شود تا اینکه تعداد مطلوبی از رشته‌های بچه ایجاد شود. در الگوریتم ژنتیک با اندازه جمعیت ثابت این تعداد برابر اندازه جمعیت اصلی است. پیوند منجر به تبادل اطلاعات تصادفی اما ساخت اما ساخت یافته می‌شود. هر رشته بچه ترکیبی از ویژگیهای والدین را به ارث می‌برد. با ملاحظه این واقعیت که در هر روند جستجو موازن ای بین آفرینش دانش جدید و بهره برداری از دانش موجود برقرار است، می‌توان پیوند را وسیله ای برای بهره برداری از دانش موجود در الگوریتم ژنتیک در نظر گرفت. پیوند با ترکیب کروموزنها برای تشکیل الگوهای رشته‌ای که ممکن است قبلا در جمعیت وجود نداشته باشد، ساز و کاری برای کشف نواحی جدیدی از فضای جستجو را فراهم می‌کند.
دانش جدید با اعمال ژنیتیکی دیگری به سیستم به نام جهش ایجاد می‌شود. جهش اساسا تغییر تصادفی یک بیت ( ۰به ۱ یا ۱ به ۰ ) در یک رشته ای که به طور تصادفی انتخاب شده، می‌باشد. این عملگر معمولاً پس از عمل پیوند در اتاق لقاح روی رشته‌ها اعمال می‌شود. دوباره محل جهش بطور تصادفی در طول رشته ( بین بیتهای ۱ تا l ) انتخاب می‌شود و بیت مربوطه عوض می‌شود. جهش نوعی از قدم زدن تصادفی در فضای جستجو را مطرح می‌کند و مانع از به دام افتادن سیستم در نقطه بهینه محلی می‌شود. همچنین جهش امکان تشکیل الگوهای رشته ای که ممکن است در جمعیت محدود تصادفی اولیه وجود نداشته باشد، فراهم می‌کند. نرخ جهش معمولاً پایین نگهداشته می‌شود تا کروموزمهای خوب بدست آمده از پیوند از بین نرود. اگر نرخ جهش بالا باشد ( بالای ۱/۰)،کارآیی الگوریتم ژنتیک کاهش می‌یابد و به جستجوی تصادفی نزدیک می‌شود. شکل ۵ عملگر جهش را نشان می‌دهد.

۵- عملگر جهش در الگوریتم ژنتیک
با پیشرفت الگوریتم در طی نسلهای متوالی، برازندگی میانگین جمعیت افزایش می‌یابد و جواب بهینه فراگیر پس از نسلهای کمی پیدا می‌شود. باید ذکر شود که افزایش برازندگی میانگین در نسلهای متوالی به معنی آن نیست که همه رشته‌ها در همه نسلها برازنده هستند. افراد ضعیفی ممکن است در یک نسل ظاهر شود اما مطابق اصل بقای اصلح آنها می میرند و به زودی با افراد قویتر جایگزین می‌شوند. در الگوریتم ژنتیک این سرنوشت به شکل تولید مثل متناسب با برازندگی جامه عمل می‌پوشد که در آن کروموزمهای ضعیفتر شانس کمتری برای انتخاب شدن جهت داشتن فرزند در نسل بعدی دارند.
می‌توان سیاستی در پیش گرفت که برازندگی میانگین نسلهای متوالی بطور یکنوا صعودی باشد. این کار از طریق انتقال مستقیم تعداد مشخصی از برازنده ترین افراد هر نسل به نسل بعدی بدون اعمال عملگرهای ژنتیکیبر آنها امکان پذیر است و نخبه‌گرایی نام دارد.
فرایند تکاملی وقتی خاتمه می‌یابد که همگرایی آشکار شود یا معیار خاتمه دیگری ( مانند پردازش تعداد مشخصی نسل ) ارضا شود. همگرایی الگوریتم ژنتیک توسط یکنواختی برازندگی رشته‌ها در یک جمعیت اندازه گیری می‌شود. یک معیار خاتمه متداول آن است که برازندگی میانگین جمعیت ۹۵ %ماکزیمم برازندگی در همان جمعیت باشد.