عنوان :

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

تعداد صفحات : ۱۰۰

نوع فایل : ورد و قابل ویرایش

چکیده

الگوریتم های ژنتیک یکی از الگوریتم های جستجوی تصادفی است که ایده ی آن برگرفته از طبیعت می باشد . الگوریتم های ژنتیک در حل مسائل بهینه سازی کاربرد فراوانی دارند .مقاله حاضر در پنج فصل بیان شده که فصل اول مقدمه و فصل دوم الگوریتم ژنتیک رابیان می کند.الگوریتم‌های ژنتیک الگوریتم‌هایی هستند که دارای قدرت بسیار زیادی در یافتن جواب مسئله هستند، اما باید توجه داشت که شاید بتوان کاربرد اصلی این الگوریتم ها را در مسائلی در نظر گرفت که دارای فضای حالت بسیار بزرگ هستند و عملاً بررسی همه حالت‌ها برای انسان در زمان‌های نرمال (در حد عمر بشر) ممکن نیست. از طرفی باید توجه داشت که حتماً بین حالات مختلف مسئله باید دارای پیوستگی مناسب و منطقی باشیم. در نهایت الگوریتم‌های ژنتیک این امکان را به ما می‌دهد که دارای حرکتی سریع در فضای مسئله به سوی هدف باشیم. به گونه‌ای که می‌توانیم تصور کنیم که در فضای حالات مسئله به سوی جواب مشغول پرواز هستیم.

در فصل سوم از آنجا که هدف اصلی این تحقیق بهینه سازی عملکرد کوره های احتراقی به منظور کاهش میزان آلاینده های تولید شده در اثر انجام عملیات احتراق است لازم است پارامترهایی که بهینه سازی بر اساس آنها انجام می شود و روش انجام محاسبات احتراق و بهینه سازی مشخص شود. پارامترهای مورد نظر برای بهینه سازی عبارتند از : درصد هوای اضافی ، دمای هوای خروجی از پیش گرمکن و نوع سوخت. در واقع با در نظر گرفتن اثرات این سه عامل بهینه سازی به گونه ای انجام می شود که میزان انتشار آلاینده ها به حداقل مقدار خود نزدیک و بهترین سوخت با توجه به پارامترهای فوق انتخاب شود. آلاینده های مورد نظر CO_X وNO_X  وSO_X می باشد و عملیات بهینه سازی بر روی سه نوع سوخت ” گاز طبیعی ، نفت کوره و گازوئیل ” انجام شده است. برای انجام عملیات بهینه سازی لازم است تابع هدف که رابطه ای خطی یا غیر خطی با دمای هوای خروجی از پیش گرمکن و درصد هوای اضافی بر میزان تولید سه ترکیب فوق هستند تابع هدف را تشکیل می دهند که این روابط با به کارگیری روشهای برازش اطلاعات تهیه شده اند. به این ترتیب تابع هدف بر اساس نیاز می تواند به هر یک از صورتهای زیر نوشته شود:

۱- کاهش CO_X

۲- کاهشNO_X

۳-کاهش SO_X

۴- کاهش CO_X  + NO_X

۵- کاهش NO_X +SO_X + CO_X

روابط به دست آمده توابعی غیر خطی از دما و درصد هوای اضافی هستند و مدل مسئله بهینه سازی با استفاده از روابط فوق و با استفاده از روش تابع پنا لتی که مخصوص بهینه سازی توابع غیر خطی است تهیه شده و با انجام عملیات بهینه سازی شرایط بهینه برای به حداقل رساندن ترکیبات آلاینده به دست آمده است. کلیه مراحل فوق توسط یک برنامه ی کامپیوتری انجام می شود. این نرم افزار با زبان برنامه نویسی MATLAB نوشته شده و مراحل اجرای این برنامه عبارتند از:

محاسبه ترکیبات حاصل از احتراق

محاسبه دمای آدیاباتیک شعله

رسم منحنی هایی که بیانگر تاثیر افزایش یا کاهش دمای هوای پیش گرم شده و در صد هوای اضافی بر دمای آدیاباتیک شعله و میزان تولید CO_X  وNO_X  وSO_X هستند.

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

هر یک از این محاسبات برای سه نوع سوخت انجام می شود و در پایان با توجه به نتایج مربوط به هر یک از سوخت ها می توان مناسب ترین نوع سوخت را به منظور تولید کمترین میزان آلاینده انتخاب  کرد.

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

در فصل چهارم برای استفاده از جعبه ابزار الگوریتم ژنتیک دو راه وجود دارد.

فراخوانی توابع GA در صفحه ی فرمان

استفاده از gatool ، یک واسط گرافیکی برای ژنتیک الگوریتم

در اینجا ما به بیان روش دوم می پردازیم.

Genetic Algorithm Tool یک واسط گرافیکی کاربر می باشد که به شما امکان می دهد بد ون استفاده ازصفحه فرامین (command line ) ازالگوریتم ژنتیک استفاده کنید.

در فصل پنجم نتایج حاصل از تابع پنالتی و الگوریتم ژنتیک را توضیح می دهد و در انتها به این نتیجه می رسیم الگوریتم ژنتیک در اکثریت مواقع بهتر از تابع پنالتی نتیجه می دهد.

واژه های کلیدی: الگوریتم های ژنتیک، کروموزوم، جمعیت، کدگذاری، برازش، انتخاب، ترکیب، جهش، احتراق ، بهینه سازی ، درصد هوای اضافی ، دمای هوای خروجی از پیش گرمکن و نوع سوخت، gatool

فهرست مطالب

فصل اول    ۱
۱-۱- مقدمه    ۲
فصل دوم    ۳
مقدمه ای بر الگوریتم ژنتیک    ۳
۲-۱- مقدمه    ۴
۲-۲- پیشینه    ۵
۲-۳- اصطلاحات زیستی    ۵
۲-۴- تشریح کلی الگوریتم ژنتیک    ۶
۲-۵- حل مساله با استفاده از الگوریتم های ژنتیک    ۷
۲-۶- اجزای الگوریتم ژنتیک    ۷
۲-۶-۱- جمعیت    ۸
۲-۶-۲- کدگذاری    ۹
کدگذاری دودویی    ۹
کدگذاری مقادیر    ۱۰
۲-۶-۲-۳- کدگذاری درختی    ۱۰
۲-۶-۳- عملگرهای الگوریتم ژنتیک    ۱۰
۲-۶-۳-۱- Fitness ( برازش )    ۱۱
۲-۶-۳-۲-  selection (انتخاب)    ۱۱
انتخاب چرخ رولت    ۱۲
انتخاب ترتیبی    ۱۳
انتخاب بولتزمن    ۱۴
انتخاب حالت پایدار    ۱۵
نخبه سالاری    ۱۵
انتخاب رقابتی    ۱۵
۲-۶-۳-۳- Crossover (ترکیب)    ۱۶
ترکیب تک نقطه ای    ۱۶
ترکیب دو نقطه ای    ۱۷
ترکیب n نقطه ای    ۱۷
ترکیب یکنواخت    ۱۸
ترکیب حسابی    ۱۸
۲-۶-۳-۴-  Mutation(جهش)    ۱۹
وارونه سازی بیت    ۲۰
تغییر ترتیب قرارگیری    ۲۰
تغییر مقدار    ۲۰
۲-۷- مفاهیم تکمیلی    ۲۱
۲-۷-۱- برتری ها و ضعف های الگوریتم ژنتیک    ۲۱
۲-۷-۲-  نکات مهم در الگوریتم های ژنتیک    ۲۲
۲-۷-۳- نتیجه گیری‌    ۲۲
فصل سوم    ۲۳
کاهش اثرات زیست محیطی آلاینده های    ۲۳
Cox ، NOx و SOx در کوره ها    ۲۳
۳-۱- مقدمه    ۲۴
۳-۲- احتراق    ۲۵
۳-۲-۱- روش محاسبه ترکیب ترکیبات تعادلی با استفاده از ثابت تعادل    ۲۶
۳-۲-۲- روش محاسبه دمای آدیاباتیک شعله    ۲۷
۳-۲-۳- انتخاب سیستم شیمیایی    ۳۰
۳-۲-۴-  تاثیر دمای هوا و هوای اضافی بر تولید محصولات    ۳۵
۳-۳- بهینه سازی    ۳۶
۳-۳-۱- روش های حل مسائل بهینه سازی    ۳۸
۳-۳-۲- روش تابع پنالتی    ۳۸
۳-۳-۳- الگوریتم حل تابع پنالتی    ۳۹
۳-۴- برنامه کامپیوتری و مراحل آن    ۴۰
۳-۵- تشکیل تابع هدف    ۴۴
۳-۶- تشکیل مدل مسئله بهینه سازی    ۴۸
۳-۷- روش حل    ۵۰
فصل چهارم    ۵۲
توضیحاتی در رابطه با gatool نرم افزار مطلب    ۵۲
۴-۱- gatool    ۵۳
۴-۲- تنظیم گزینه ها برای الگویتم ژنتیک    ۵۵
۴-۳- Plot Options    ۵۵
۴-۴- Population Options    ۵۶
۴-۵- Fitness Scaling Option    ۵۷
۴-۶- Selection Option    ۵۸
۴-۷- Reproduction Options    ۵۹
۴-۸- Mutation Options    ۵۹
۴-۹- Crossover Options    ۶۱
۴-۱۰- Migration Options    ۶۲
۴-۱۱- Output Function Options    ۶۳
۴-۱۲- Stopping Criteria Options    ۶۳
۴-۱۳- Hybrid Function Options    ۶۴
۴-۱۴- Vectorize Options    ۶۴
فصل پنجم    ۶۵
نتایج    ۶۵
۵-۱- نتایج حاصل از تابع پنالتی و الگوریتم ژنتیک    ۶۶
۵-۲- نتیجه گیری    ۹۴
فهرست مراجع    ۹۵

۱-۱- مقدمه

به طور کلی انتخاب و طراحی بهینه در بسیاری از مسائل علمی و فنی باعث تولید بهترین محصول یا جواب ممکن در یک شرایط خاص می شود. برای مثال تولید محصولات مناسب در حوزه های مختلف فنی و مهندسی وابسته به طراحی دقیق و بهینه ی شکل، اندازه و قطعات محصول است. در نتیجه هر مسئله ی مهندسی ممکن است داری چندین جواب مختلف باشد که بعضی از آنها ممکن و بعضی غیر ممکن است . وظیفه ی طراحان پیدا کردن بهترین جواب ممکن از میان جواب های مختلف است. مجموعه ی جواب های ممکن فضای طراحی را شکل می دهند که باید در این فضا به جستجوی بهترین یا بهینه ترین جواب پرداخت.

از آنجایی که نتیجه ی کار با توجه به نوع انتخاب این متدها و روش ها حاصل می شود لذا به اهمیت موضوع انتخاب بهینه ( Optimum ) و بهینه سازی در همه ی مسائل پی می بریم پس:

(( هدف ما این است که در فضای جواب های ممکن به دنبال بهترین جواب بگردیم. ))

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

Simulated Annealing

Ant colony

Random Cost

Evolution strategy

Genetic Algorithm

Celluar Automata

در این پایان نامه به بررسی و استفاده از روش Genetic Algorithm می پردازیم.

فصل دوم:مقدمه ای بر الگوریتم ژنتیک

۲-۱- مقدمه

الگوریتم های ژنتیک یکی از الگوریتم های جستجوی تصادفی است که ایده ی آن برگرفته از طبیعت می باشد . الگوریتم های ژنتیک در حل مسائل بهینه سازی کاربرد فراوانی دارند . به عنوان مثال می توان به مسئله فروشنده دوره گرد اشاره کرد . در طبیعت از ترکیب کروموزوم های بهتر ، نسل های بهتری پدید می آیند . در این بین گاهی اوقات جهش هایی نیز در کروموزوم ها روی می دهد که ممکن است باعث بهتر شدن نسل بعدی شوند. الگوریتم ژنتیک نیز با استفاده از این ایده اقدام به حل مسائل می کند .

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

۲-۲- پیشینه

پیشینه ی الگوریتم ژنتیک به سال های حدود ۱۹۶۰ برمی گردد. در دهه های ۵۰ و ۶۰ تحقیقات متعددی برای استفاده از نظریه تکامل در بهینه سازی مسائل مهندسی به طور مستقل صورت گرفت. ایده ی اصلی در همه این سیستم ها، رشد یک جمعیت از پاسخ های اولیه یک مساله به سمت پاسخ بهینه با الهام گیری از عملگرهای انتخاب و تغییر ژنتیک طبیعی بود. در سال های ۱۹۶۵ تا ۱۹۷۳ رکنبرگ(Rechenberg ) کتاب خود را به نام  تکنیک های تکامل (Evolution strategies (Evolutionsstrategie in original) ) در زمینه محاسبات تکاملی منتشر کرد و در سال های بعد نظریه او توسط محققین دیگر توسعه یافت. الگوریتم ژنتیک نخستین بار توسط  جان هلند ( John Holland ) مطرح و به وسیله خود او و دانشجویان و همکارانش گسترش یافت. تلاش های او و اطرافیانش در این زمینه در نهایت به نشر کتاب سازگاری در طبیعت و سیستم های مصنوعی (Adaption in Natural and Artificial Systems ) انجامید. پس از آن تحقیقات گسترده ای توسط افراد مختلف در این زمینه انجام شد (به عنوان مثال در سال ۱۹۹۲ جان کزا (John Koza ) الگوریتم ژنتیک را به صورت عملیاتی در برنامه نویسی به کار برد و برنامه نویسی ژنتیک (genetic programming(GP) ) را به عنوان روش خود مطرح ساخت.) و الگوریتم ژنتیک به صورت امروزی خود رسید.

۲-۳- اصطلاحات زیستی

در راستای فهم کامل الگوریتم ژنتیک، ابتدا بهتر است با برخی از اصطلاحات زیستی به کار رفته در تئوری این الگوریتم آشنا شویم. همه موجودات زنده از واحدهای کوچکی به نام سلول تشکیل شده اند. هر سلول نیز به نوبه خود از مجموعه ای از یک یا چند کروموزوم (chromosome ) تشکیل شده است. کروموزوم ها رشته هایی از مولکول DNA می باشند که در حقیقت برنامه کاری موجود زنده را در خود ذخیره می کنند. هر کروموزوم شامل چندین ژن( gene ) می باشد، که هر ژن بلوکی از مولکول DNA می باشد که پروتئین خاصی را کدگذاری می کند. به طور کلی می توان گفت که هر ژن یک خصیصه (trait ) از موجود زنده (مانند رنگ چشم) را کد گذاری می کند. حالت های ممکن برای یک خصیصه را (allele  ) می گویند. هر ژن موقعیت مخصوص خود را در کروموزوم دارد که به آن (locus ) می گویند. بسیاری از موجودات زنده در هر سلول چندین کروموزوم دارند. مجموعه کامل مواد ژنتیکی در سلول (مجموعه همه کروموزوم ها) (genome ) نامیده می شوند. اصطلاح (genotype ) به مجموعه خاصی از کروموزوم های موجود در genome اتلاق می شود. Genotype ها در پی تحولات و تغییر، به phenotypeها خصوصیات فیزیکی و ذهنی موجود زنده (مانند رنگ چشم، بلندی، اندازه مغز و یا میزان هوش) تبدیل می شوند.

در طی تولید مثل جنسی(reproduction )، در اثر الحاق(recombination or crossover ) ژن ها از کروموزوم های والدین(parents ) با یکدیگر ترکیب شده تا کروموزوم کامل جدیدی را تشکیل دهند. در طی این تغییرات، ممکن است تغییرات کوچکی در برخی از بخش های DNA   ژن های فرزند، بوجود آمده و فرزند دچار جهش (mutation ) گردد. در نهایت تناسب (fitness ) یک موجود زنده با توجه به احتمال زیستن آن برای تکثیر(زیست پذیری(viability ) ) یا برحسب تابعی از تعداد فرزندان آن گونه (باروری(fertility )) تعیین می گردد.

۲-۴- تشریح کلی الگوریتم ژنتیک

یک تشریح کلی از الگوریتم ژنتیک را می‏توان به صورت زیر در نظر گرفت :

-۱ جمعیتی از رشته‏ها را به صورت تصادفی بسازید.
-۲ هررشته داخل جمعیت را ارزیابی کنید.
-۳ رشته‏های جدید را با ترکیب رشته‏های جاری ایجاد کنید. برای ترکیب رشته‎های والد از عملگر‏های جهش و تبادل استفاده کنید.
-۴ اعضایی از جمعیت را برای ایجاد فضایی برای رشته‏های جدید حذف کنید.
-۵ رشته‏های جدید را ارزیابی نموده و آنها را داخل جمعیت قرار دهید.
-۶ اگر زمان اجرا تمام شده است توقف نمایید و بهترین رشته را باز گردانید. در غیر این صورت به مرحله سه بازگردید.

روند ذکر شده در بالا متداول‏ترین روش الگوریتم ژنتیک را تشریح می‏کند. اما محققین مختلف، آن را به روش‏های متفاوت پیاده سازی کرده‎اند.

دو روش متداول دیگر برای اختتام: (همگرا شدن الگوریتم، تولید تعداد خاص نسل می‏باشد).

۲-۵- حل مساله با استفاده از الگوریتم های ژنتیک

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

Population = GeneratePopulation(K)

For I = 1 to MaxIterations Fitness(Population) If any of chromosomes is optimal Then  Break Offspring =  Crossover(Population) Mutate(Offspring)

EndFor

۲-۶- اجزای الگوریتم ژنتیک

با توجه به آنچه گذشت، الگوریتم ژنتیک بخشی از نظریه حسابگری تکاملی (evolutionary computing ) است که در حال حاضر به عنوان بخشی از هوش مصنوعی به سرعت در حال رشد می باشد. ایده اصلی این الگوریتم در نظریه تکامل داروین نهفته است.  از نظر کاربردی، الگوریتم ژنتیک یکی از روش های بهینه سازی مسائل است که اساس آن بر انتخاب طبیعی (natural selection) (عامل اصلی تکامل زیستی) و برخی مفاهیمی که از علم ژنتیک الهام گرفته شده اند، استوار است. در این روش به بیان ساده، برای بهینه سازی تابع هدف (تابع تناسب(fitness function )) مساله، در هر مرحله، از یک جمعیت (population) اولیه کروموزوم ها (افراد (individuals) ) که در حقیقت پاسخ های اولیه مساله می باشند، به یک جمعیت جدید از کروموزوم ها و یا یک نسل (generation) جدید که در حقیقت پاسخ های ثانویه مساله مفروض می باشند می رسیم. بنابراین با تکرار این عملیات و تولید جمعیت جدید از جمعیت قبلی در هر مرحله و در نتیجه رسیدن به نسل های موفق، جمعیت به سمت یک پاسخ بهینه رشد خواهد کرد.
در الگوریتم ژنتیک هر کروموزوم نشان دهنده پاسخی از مساله مورد نظر می باشد. این پاسخ بسته به نوع کدسازی مساله مورد نظر که  با توجه به خصوصیات مساله تعیین می شود، می تواند به صورت ماتریسی  از اعداد حقیقی (کدسازی حقیقی)، یک رشته از بیت های ۰و۱ ای (کدسازی باینری) و … مطرح شود. بنابراین هر کدام از ژن ها که اجزاء کروموزوم ها میباشند، می توانند نشانگر یک عدد حقیقی، یک بیت و … باشند.

اجزای الگوریتم ژنتیک عبارتند از:

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

کدگذاری : نمایش اعضاء در الگوریتم ژنتیک

عملگرهای الگوریتم ژنتیک : عملگرهای ژنتیک که باعث ترکیب ساخت ژنتیکی فرزندان در طول تولید مثل می شوند.

۲-۶-۱- جمعیت

مفهوم جمعیت در الگوریتم ژنتیک شبیه به چیزی است که در زندگی طبیعی وجود دارد. برای مساله گزاره هایی وجود دارند که می توانند به عنوان پاسخ، چه درست، چه غلط در نظرگرفته شوند. به این گزاره ها پاسخهای ممکن یا شدنی می گوییم. مثلا اگر مساله یافتن ماکزیمم یک تابع در مجموعه اعداد صحیح باشد، تمام اعداد صحیح می توانند به عنوان پاسخ شدنی مساله در نظر گرفته شوند.

در الگوریتم ژنتیک به عنوان اولین مرحله لازم است مجموعه ای از جوابهای شدنی به عنوان جمعیت اولیه ایجاد شود. اعضای این مجموعه معمولا به صورت تصادفی انتخاب می شوند اما در الگوریتمهای بهینه، از قیدهایی استفاده می شود تا جمعیت پراکندگی بیش از حد نداشته باشد. تعداد اعضای جمعیت به نوع مساله بستگی دارد. در واقع تعداد اعضا، پارامتری است که با تغییر آن می توان دقت جوابها و سرعت همگرایی جستجو را بهبود بخشید. در برخی مسائل یک جمعیت ۸ عضوی کاملاٌ مناسب است در حالی که در برخی یک جمعیت ۱۰۰ عضوی نیز کافی نیست. بر اساس تجربه بهتر است تعداد اعضای جمعیت عددی بین ۱۰ تا ۱۶۰ باشد.

بعد از انتخاب جمعیت، لازم است اعضای آن به شکل کروموزوم درآیند. هر کروموزوم آرایشی از چند ژن است. در مرحله تبدیل (کدگذاری) (Encoding) ، جوابها به ژنها تبدیل می شوند. روشهای مختلفی برای کدگذاری وجود دارد. انتخاب روش وابسته به نوع مساله ای است که به آن پرداخته می شود. نکته قابل ذکر در تبدیل جوابها به کروموزوم ها این است که طول کروموزوم ها باید برابر و ثابت باشد یعنی اگر یک جواب از مجموعه به کروموزومی با n ژن تبدیل شد، طول تمام کروموزومهای دیگر نیز باید n باشد. طول کروموزومها را نوع کدگذاری، جنس پاسخها و محدوده پاسخها تعیین می کند. کروموزومها در الگوریتم ژنتیک باید به گونه ای باشند که دقیقا تمام مشخصات پاسخ را در خود ذخیره کنند. مثلا اگر مساله با اعداد حقیقی کار می کند، کروموزوم باید شامل اطلاعات مربوط به علامت عدد، تعداد رقمهای اعشاری، محدوده عدد و … باشد. مهمترین نوع کدگذاری، کدگذاری باینری است.

۲-۶-۲- کدگذاری

بعد از انتخاب جمعیت، لازم است اعضای آن به شکل کروموزوم درآیند. هر کروموزوم آرایشی از چند ژن است. در مرحله تبدیل (کدگذاری) (Encoding) ، جوابها به ژنها تبدیل می شوند. روشهای مختلفی برای کدگذاری وجود دارد. انتخاب روش وابسته به نوع مساله ای است که به آن پرداخته می شود. نکته قابل ذکر در تبدیل جوابها به کروموزوم ها این است که طول کروموزوم ها باید برابر و ثابت باشد یعنی اگر یک جواب از مجموعه به کروموزومی با n ژن تبدیل شد، طول تمام کروموزومهای دیگر نیز باید n باشد. طول کروموزومها را نوع کدگذاری، جنس پاسخها و محدوده پاسخها تعیین می کند. کروموزومها در الگوریتم ژنتیک باید به گونه ای باشند که دقیقا تمام مشخصات پاسخ را در خود ذخیره کنند. مثلا اگر مساله با اعداد حقیقی کار می کند، کروموزوم باید شامل اطلاعات مربوط به علامت عدد، تعداد رقمهای اعشاری، محدوده عدد و … باشد. مهمترین نوع کدگذاری، کدگذاری باینری (دودویی ) است.

کدگذاری دودویی

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

در روش کد گذاری دودویی همه ی کورموزم ها با رشته هایی که شامل بیت هایی از ۱-۰ است کد می شوند .

اغلب این روش کدگذاری برای اکثر مسائل طبیعی نیست و بعد از CrossOver و جهش باید تغییراتی درآن به وجود آورد.

Chromosome A	۱۰۱۱۰۰۱۰۱۱۰۰۱۰۱۰۱۱۱۰۰۱۰۱
Chromosome B	۱۱۱۱۱۱۱۰۰۰۰۰۱۱۰۰۰۰۰۱۱۱۱۱

شکل ۲-۲- مثالی از کروموزوم ها به روش کدگذاری دودویی

کدگذاری مقادیر

شیوه ی کدگذاری مقادیر را در مواردی بکار می بریم که مسئله دارای مقادیر پیچیده ای است، مانند اعداد صحیح که استفاده از کد گذاری باینری در این حالت بسیار دشوار است .

Chromosome A	۱٫۲۳۲۴  ۵٫۳۲۴۳  ۰٫۴۵۵۶  ۲٫۳۲۹۳  ۲٫۴۵۴۵
Chromosome B	ABDJEIFJDHDIERJFDLDFLFEGT
Chromosome C	(back), (back), (right), (forward), (left)

شکل ۲-۳- مثالی از کروموزوم ها با استفاده از روش کدگذاری مقادیر

کدگذاری مقادیر روش خوبی برای کدگذاری مسئله های خاص است، ولی با این وجود برای اینگونه کد گذاری اغلب باید شیوه های توسعه یافته ی جدیدی در Crossover و جهش به کار برد .

۲-۶-۲-۳- کدگذاری درختی

کدگذاری درختی اساساً برای استنتاج برنامه یا بیان طرح برنامه های الگوریتم ژنتیک مورد استفاده قرار می گیرد. کد گذاری درختی برای استنتاج برنامه ها یا هر راهبردی که بتواند به صورت درخت کدگذاری شود بسیار مفید است. زبان برنامه نویسیLISP  اغلب بدین منظور به کار میرود.  بنابراین Crossover و جهش را می توان به سادگی با این روش انجام داد.

۲-۶-۳- عملگرهای الگوریتم ژنتیک

Fitness ( برازش، ارزیابی )

Selection ( انتخاب )

Crossover ( ترکیب )

Mutation ( جهش )

۲-۶-۳-۱- Fitness ( برازش )

با استفاده از این عملگر ، میزان بهینگی هر کروموزوم را تعیین می کنیم . به عنوان مثال در مسئله فروشنده دوره گرد ، تورهایی با مسافت کمتر بهینه تر هستند . و یا در مسئله n وزیر تعداد برخوردهای کمتر باعث بهینگی بیشتر کروموزوم می شود . بنابراین می توان نتیجه گرفت که عملگر Fitness برای هر کروموزوم احتمالی را نسبت می دهد که این احتمال ، همان احتمال ترکیب شدن کروموزم برای تولید نسل های آینده را نشان می دهد . بدیهی است که کروموزوم های بهینه تر شانس بیشتری برای ترکیب با دیگر کروموزوم ها خواهند داشت . بنابراین احتمالی که به آنها نیز نسبت می دهیم باید بیشتر باشد .

100,000 ریال – خرید نهایی کردن خرید مورد به سبد خرید اضافه شد

جهت دریافت و خرید متن کامل مقاله و تحقیق و پایان نامه مربوطه بر روی گزینه خرید انتهای هر تحقیق و پروژه کلیک نمائید و پس از وارد نمودن مشخصات خود به درگاه بانک متصل شده که از طریق کلیه کارت های عضو شتاب قادر به پرداخت می باشید و بلافاصله بعد از پرداخت آنلاین به صورت خودکار  لینک دنلود مقاله و پایان نامه مربوطه فعال گردیده که قادر به دنلود فایل کامل آن می باشد .