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

فهرست مطالب
فصل اول) کلیات    

1-1) مقدمه              

1-2) تعریف مسئله  

1-3) اهداف الگوریتم ژنتیک  

1-4) دلایل استفاده از الگوریتم ژنتیک   

1-5) معرفی ساختار پایان نامه                

1-6) خلاصه و نتیجه گیری   

فصل دوم) مطالعه و بررسی الگوریتم ژنتیک        

2-1) مقدمه              

2-2) معرفی الگوریتم ژنتیک 

     2-2-2) فضای جستجو       

     2-2-3)  مسائل NP  ( NP – HARD )             

2-3) ساختار الگوریتم ژنتیک 

     2-3-1) طرح کلی الگوریتم ژنتیک    

     2-3-2)  عملگرهای GA    

          2-3-2-1) ترکیب          

          2-3-2-2) جهش            

          2-3-2-3) احتمال  ترکیب             

          2-3-2-4) احتمال جهش 

          2-3-2-5) سایز جمعیت 

          2-3-2-6) انتخاب          

               2-3-2-6-1) انتخاب چرخ رولت              

               2-3-2-6-2) انتخاب رتبه         

               2-3-2-6-3) انتخاب حالت ثابت               

     2-3-2-7) نخبه سالاری     

     2-3-2-8) رمزنگاری         

               2-3-2-8-1) رمزنگاری باینری               

               2-3-2-8-2) رمزنگاری جایگشت           

               2-3-2-8-3) رمزنگاری درخت               

     2-3-2-9) ترکیب و جهش  

               2-3-2-9-1) ترکیب تک نقطه ای           

               2-3-2-9-1)ترکیب تک برشی 

2-4) نقاط قوت الگوریتم‌های ژنتیک      

2-5) محدودیت‌های الگوریتم های ژنتیک              

2-6) استراتژی برخورد با محدودیت‌ها   

     2-6-1) استراتژی اصلاح عملگرهای ژنتیک   

     2-6-2) استراتژی رَدّی      

     2-6-3) استراتژی اصلاحی               

     2-6-4) استراتژی جریمه‌ای               

2-7) بهبود الگوریتم ژنتیک    

2-8) انواع الگوریتمهای ژنتیکی            

     2-8-1) الگوریتم ژنتیکی سری          

     2-8-2) الگوریتم ژنتیکی موازی       

2-9) خلاصه و نتیجه گیری   

فصل سوم) کاربردهای الگوریتم ژنتیک و مثال های حل شده              

3-1) مقدمه              

3-2) حلّ معماي هشت وزیر   

     3-2-1) جمعیت آغازین      

     3-2-2)تابع برازندگی         

     3-2-3) آمیزش   

     3-2-4) جهش ژنتیکی        

3-3) الگوریتم ژنتیک و حلّ مسألۀ فروشندۀ دورهگرد          

     3-3-1) حل مسأله TSP به وسیله الگوریتم ژنتیک             

     3-3-2) مقایسه روشهای مختلف الگوریتم و ژنتیک برای TSP         

     3-3-3) نتیجه گیری           

3-4) حلّ مسأله معمای سودوکو             

     3-4-1) حل مسأله               

     3-4-2) تعیین کروموزم     

     3-4-3) ساختن جمعيت آغازين يا نسل اول       

     3-4-4) ساختن تابع از ارزش            

     3-4-5) تركيب نمونه‌ها و ساختن جواب جديد   

     3-4-6) ارزشيابي مجموعه جواب      

     3-4-7) ساختن نسل بعد     

3-5) مرتب سازی به کمک GA             

     3-5-1) صورت مسأله        

     3-5-2) جمعیت آغازین      

     3-5-3) تابع برازندگی        

     3-5-4) انتخاب   

     3-5-5) ترکیب   

     3-5-6) جهش     

واژه‌نامه انگلیسی به فارسی    

منابع و مراجع