توضیحات
چکیده
الگوریتم ژنتیک (Genetic Algorithm – GA) تکنیک جستجویی در علم رایانه برای یافتن راهحل تقریبی برای بهینهسازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیستشناسی فرگشتی مانند وراثت و جهش استفاده میکند.
در واقع الگوریتمهای ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیشبینی یا تطبیق الگو استفاده میکنند. الگوریتمهای ژنتیک اغلب گزینه خوبی برای تکنیکهای پیشبینی بر مبنای تصادف هستند. مختصراً گفته میشود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامهنویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده میکند. مسألهای که باید حل شود ورودی است و راهحلها طبق یک الگو کد گذاری میشوند که تابع fitness نام دارد هر راه حل کاندید را ارزیابی میکند که اکثر آنها به صورت تصادفی انتخاب میشوند.
کلاً این الگوریتمها از بخش های زیر تشکیل میشوند: تابع برازش، نمایش، انتخاب، تغییر.
فهرست مطالب
چکیده……………………………………………………………………………………………………………………………………………………………. ۱
فصل اول………………………………………………………………………………………………………………………………………………………… ۲
مقدمه…………………………………………………………………………………………………………………………………………………………….. ۲
مقدمه…………………………………………………………………………………………………………………………………………………………….. ۳
پیشینه……………………………………………………………………………………………………………………………………………………………… ۴
اصطلاحات زیستی……………………………………………………………………………………………………………………………………………. ۴
تشریح کلی الگوریتم ژنتیک……………………………………………………………………………………………………………………………….. ۵
حل مساله با استفاده از الگوریتم های ژنتیک………………………………………………………………………………………………………….. ۶
اجزای الگوریتم ژنتیک……………………………………………………………………………………………………………………………………… ۷
جمعیت…………………………………………………………………………………………………………………………………………………………… ۸
کدگذاری………………………………………………………………………………………………………………………………………………………. ۱۰
کدگذاری دودویی…………………………………………………………………………………………………………………………………………… ۱۰
کدگذاری مقادیر……………………………………………………………………………………………………………………………………………… ۱۱
کدگذاری درختی…………………………………………………………………………………………………………………………………………….. ۱۱
عملگرهای الگوریتم ژنتیک………………………………………………………………………………………………………………………………… ۱۲
انتخاب چرخ رولت…………………………………………………………………………………………………………………………………………… ۱۴
انتخاب ترتيبي………………………………………………………………………………………………………………………………………………….. ۱۷
انتخاب بولتزمن…………………………………………………………………………………………………………………………………………………. ۱۸
انتخاب حالت پايدار………………………………………………………………………………………………………………………………………….. ۱۹
نخبه سالاري……………………………………………………………………………………………………………………………………………………. ۱۹
انتخاب رقابتي………………………………………………………………………………………………………………………………………………….. ۱۹
Crossover (تركيب)………………………………………………………………………………………………………………………………………. ۲۰
تركيب تك نقطه اي۱……………………………………………………………………………………………………………………………………….. ۲۱
تركيب دو نقطه اي۱………………………………………………………………………………………………………………………………………….. ۲۲
تركيب n نقطه ای…………………………………………………………………………………………………………………………………………….. ۲۳
تركيب يكنواخت……………………………………………………………………………………………………………………………………………… ۲۳
تركيب حسابي………………………………………………………………………………………………………………………………………………….. ۲۵
Mutation(جهش)…………………………………………………………………………………………………………………………………………. ۲۶
وارونه سازي بيت……………………………………………………………………………………………………………………………………………… ۲۷
تغيير ترتيب قرارگيري………………………………………………………………………………………………………………………………………… ۲۸
تغيير مقدار………………………………………………………………………………………………………………………………………………………. ۲۸
مفاهیم تکمیلی…………………………………………………………………………………………………………………………………………………. ۲۹
برتری ها و ضعف های الگوریتم ژنتیک………………………………………………………………………………………………………………… ۲۹
نكات مهم در الگوريتم هاي ژنتيك……………………………………………………………………………………………………………………… ۳۰
نتيجه گيري……………………………………………………………………………………………………………………………………………………… ۳۱
فصل دوم………………………………………………………………………………………………………………………………………………………… ۳۳
کاهش اثرات زیست محیطی آلاینده های………………………………………………………………………………………………………………. ۳۳
Cox ، NOx و SOx در کوره ها………………………………………………………………………………………………………………………… ۳۳
مقدمه…………………………………………………………………………………………………………………………………………………………….. ۳۴
احتراق…………………………………………………………………………………………………………………………………………………………… ۳۶
روش محاسبه ترکیب ترکیبات تعادلی با استفاده از ثابت تعادل…………………………………………………………………………………… ۳۷
روش محاسبه دمای آدیاباتیک شعله…………………………………………………………………………………………………………………….. ۳۹
انتخاب سیستم شیمیایی………………………………………………………………………………………………………………………………………. ۴۴
تاثیر دمای هوا و هوای اضافی بر تولید محصولات……………………………………………………………………………………………………. ۵۱
بهینه سازی……………………………………………………………………………………………………………………………………………………… ۵۲
روش های حل مسائل بهینه سازی………………………………………………………………………………………………………………………… ۵۵
روش تابع پنالتی……………………………………………………………………………………………………………………………………………….. ۵۵
الگوریتم حل تابع پنالتی……………………………………………………………………………………………………………………………………… ۵۶
برنامه کامپیوتری و مراحل آن……………………………………………………………………………………………………………………………… ۵۷
تشکیل تابع هدف……………………………………………………………………………………………………………………………………………… ۶۲
تشکیل مدل مسئله بهینه سازی………………………………………………………………………………………………………………………………. ۶۸
روش حل……………………………………………………………………………………………………………………………………………………….. ۷۰
فصل پنجم………………………………………………………………………………………………………………………………………………………. ۷۳
نتایج………………………………………………………………………………………………………………………………………………………………. ۷۳
نتیجه گیری……………………………………………………………………………………………………………………………………………………… ۷۴
فهرست مراجع…………………………………………………………………………………………………………………………………………………. ۷۶
بخشی از پایان نامه الگوریتم ژنتیک
– مقدمه
امروزه یکی از مهمترین زمینههای تحقیق و پژوهش، توسعۀ روشهای جستجو بر مبنای اصول تکامل طبیعی میباشد. در محاسبات تکاملی به صورت انتزاعی از مفاهیم اساسی تکامل طبیعی در راستای جستجو برای یافتن راه حلّ بهینه برای مسائل مختلف الهام گرفته شده است. در همین راستا مطالبی که در این فصل پیش روی شما پژوهندۀ گرامی قرار خواهد گرفت مفاهیمی دربارۀ علم کامپیوتر و علم ژنتیک مانند: الگوریتم و انواع آن، جستجو، هیوریستیک، تاریخچه الگوریتم ژنتیک و علم ژنتیک، ژن، کروموزوم، ارث بری و… می باشد، و یا به بیانی خلاصهتر میتوان گفت: در این فصل به بیان مقدّمات خواهیم پرداخت.
انشاءالله مطالعۀ این فصل مفهومی ساده و روشن از موضوعِ این نوشتار را برای شما خوانندۀ محترم به تصویر خواهد کشید و شما را در درک آسان و سریع فصول بعدی یاری خواهد رساند.
به دنبال تکامل…
بسیاری از دانشمندان و اندیشمندان، میل به تکامل را مهترین عامل پیشرفت دستگاه آفرینش و انسان میدانند. از این دیدگاه هر پدیدهای را که بنگرید، یک مسأله جستجوست. انسان همواره میکوشد تا به تکامل برسد، از این رو میاندیشد، میپژوهد، میکاود، میسازد، مینگارد و همواره میکوشد تا باقی بماند. حتی میتوان گفت که میل به زادن فرزند، گامی در برآوردن این نیاز و البته دیگر جانداران است. میتوان این تلاش در راه رسیدن به تکامل را یک مسألۀ جستجو تعبیر کرد.
کوشش یک مؤسسه اقتصادی یا تولیدی –که تابعی برای تبدیل دادهها به ستادهاست- برای کمینه کردن هزینهها و بیشینه کردن سود، یک مسألۀ جستجو است. تلاش یک سپاه در حال جنگ، برای وارد کرد بیشترین خسارات بر دشمن با از دست دادن کمترین نیرو و جنگافزار، یا کوشش یک دانشآموز برای دست یافتن به بالاترین نمره، سعی یک موسیقیدان یا نگارگر برای خلق زیباترین اثر هنری، تلاش یک کاندیدا برای به دست آوردن بیشترین رأی، طراحی یک نجّار برای ساختن راحتترین صندلی، تلاش و نقشه چینی ورزشکاران و مربّیان برای یافتن راههای پیروزی بر حریف و… همگی جستجویی در فضای یک مسأله برای یافتن نقاط یا ناحیه بهینگی (بیشینه یا کمینه) هستند و همین امر موجب پیشرفت تمدن و آفرینش شده است.
در دانش کامپیوتر و فناوری اطلاعات هم «جستجو» یکی از مهمترین مسائل است. تنها کافیست که حجم اطلاعات قرار گرفته بر حافظههای گوناگون و اینترنت را در نظر بگیریم تا جایگاه ویژه آن را دریابیم.
تاکنون روشهای بسیاری توسط طراحان الگوریتمها برای انجام جستجو بر دادههای دیجیتالی ارائه شده است. روشهایی به نام جستجوی سریع و جستجوی دودویی ، از سادهترین الگوریتمهایی هستند که دانشجویان گرایشهای مهندسی کامپیوتر در نخستین سالهای دوره کارشناسی فرا میگیرند، امّا این الگوریتمها شاید، هنگامی که با حجمی گسترده از دادهها روبرو شوند، کارایی ندارند و حتی الگوریتمهای پیشرفتهتر مانند جستجوی بازپخت شبیهسازی شده و الگوریتم عمیقشوندۀ تکراری نیز در هنگام رویارویی با مسائل ابرفضا از یافتن راهحل یا ناحیههای دلخواه در میمانند. در این میان یک روش جادویی وجود وجود دارد که مسائل بزرگ را به سادگی و به گونهای شگفتانگیز حل میکند و آن «الگوریتم ژنتیک» است. ناگفته پیداست که واژۀ «الگوریتم ژنتیک» از دو واژۀ «الگوریتم» و «ژنتیک» تشکیل شده است که خود مبیّن این مطلب است که این روش از دو علم ریاضی و زیستشناسی برای حل مسائل کمک میگیرد.
الگوریتمژنتیک بر خلاف دیگر روشهای جستجو، که توسط طراحان نگاشته میشوند، در حقیقت به دست دستگاه آفرینش پدید آمده، و پس از شناخت نسبی دانشمندان از این روش به صورت مسألهای ریاضی فرموله شده و وارد دانش مهندسی کامپیوتر و دیگر علوم مرتبط گردیده است. در یکی دو دهه گذشته که این الگوریتم در علوم مهندسی بکار گرفته شده، ناباورانه چنان دستآوردها و نتایج شگفتانگیزی داشته که نگاه بسیاری از دانشپژوهان علوم گوناگون فنیمهندسی را به خود جلب کرده است.[۱]
ایدۀ اصلی استفاده از الگوریتم ژنتیک
در دهه ۷۰ میلادی دانشمندی از دانشگاه میشیگان به نام «جان هلند» ایده استفاده از الگوریتم ژنتیک را در بهینهسازیهای مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژنهاست. (ژنها قطعاتی از یک کروموزوم هستند که اطلاعات مورد نیاز برای یک مولکول DNA یا یک پلی پپتید را دارند. علاوه بر ژنها، انواع مختلفی از توالیهای مختلف تنظیمی در روی کروموزومها وجود دارد که در همانندسازی، رونویسی و… شرکت دارند.( . فرض کنید مجموعه خصوصیات انسان توسط کروموزومهای او به نسل بعدی منتقل میشوند. هر ژن در این کروموزومها نماینده یک خصوصیت است. بعنوان مثال ژن ۱ میتواند رنگ چشم باشد، ژن ۲ طول قد، ژن ۳ رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بَدیهیست که در عمل چنین اتفاقی رخ نمیدهد. در واقع بصورت همزمان دو اتفاق برای کروموزومها میافتد. اتّفاق اول موتاسیون(جهش) است. موتاسیون به این صورت است که بعضی ژنها بصورت کاملاً تصادفی تغییر میکنند. البته تعداد اینگونه ژنها بسیار کم میباشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است. مثلاً ژن رنگ چشم میتواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد، در حالی که تمامی نسل قبل دارای چشم قهوهای بودهاند. علاوه بر موتاسیون اتفاق دیگری که میافتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به موتاسیون رخ میدهد چسبیدن ابتدای یک کروموزوم به انتهای یک کروموزوم دیگر است. این همان چیزیست که مثلاً باعث میشود تا فرزند تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن تام فرزند به تنها یکی از والدین جلوگیری میکند