فهرست مطالب 

 فصل اول------------------------------------------------------- 1

1-1- مقدمه------------------------------------------------------------ 2

1-2- به دنبال تکامل...----------------------------------------------------- 3

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

1-4- درباره علم ژنتیک----------------------------------------------------- 6

1-5- تاریخچۀ علم ژنتیک--------------------------------------------------- 6

1-6- تکامل طبیعی (قانون انتخاب طبیعی داروین)------------------------------------ 7

1-7- رابطه تکامل طبیعی با روش‌های هوش مصنوعی--------------------------------- 10

1-8- الگوریتم---------------------------------------------------------- 11

1-8-1- الگوریتم‌های جستجوی ناآگاهانه--------------------------------------- 12

1-8-1-الف- جستجوی لیست-------------------------------------------- 12

1-8-1-ب- جستجوی درختی-------------------------------------------- 13

1-8-1-پ- جستجوی گراف--------------------------------------------- 14

1-8-2- الگوریتم‌های جستجوی آگاهانه---------------------------------------- 14

1-8-2-الف- جستجوی خصمانه------------------------------------------ 15

1-9- مسائل NP-Hard---------------------------------------------------- 15

1-10- هیوریستیک------------------------------------------------------- 17

1-10-1- انواع الگوریتم‌های هیوریستیک--------------------------------------- 19

 فصل دوم------------------------------------------------------- 21

2-1- مقدمه------------------------------------------------------------ 22

2-2- الگوریتم ژنتیک------------------------------------------------------ 23

2-3- مكانیزم الگوریتم ژنتیك------------------------------------------------- 25

2-4- عملگرهای الگوریتم ژنتیك---------------------------------------------- 28

2-4-1- کدگذاری------------------------------------------------------ 28

2-4-2- ارزیابی------------------------------------------------------- 29

2-4-3- ترکیب-------------------------------------------------------- 29

2-4-4- جهش-------------------------------------------------------- 29

2-4-5- رمزگشایی----------------------------------------------------- 30

2-5- چارت الگوریتم به همراه شبه كد آن----------------------------------------- 30

2-5-1- شبه كد و توضیح آن----------------------------------------------- 31

2-5-2- چارت الگوریتم ژنتیک--------------------------------------------- 33

2-6- تابع هدف--------------------------------------------------------- 34

2-7- روش‌های کد کردن--------------------------------------------------- 34

2-7-1- کدینگ باینری--------------------------------------------------- 35

2-7-2- کدینگ جایگشتی------------------------------------------------- 36

2-7-3- کد گذاری مقدار------------------------------------------------- 37

2-7-4- کدینگ درخت-------------------------------------------------- 38

2-8- نمایش رشته‌ها------------------------------------------------------- 39

2-9- انواع روش‌های تشکیل رشته--------------------------------------------- 41

2-10- باز گرداندن رشته‌ها به مجموعه متغیرها-------------------------------------- 42

2-10-1- تعداد بیت‌های متناظر با هر متغیر-------------------------------------- 43

2-11- جمعیت---------------------------------------------------------- 44

2-11-1- ایجادجمعیت اولیه----------------------------------------------- 44

2-11-2- اندازه جمعیت-------------------------------------------------- 45

2-12- محاسبه برازندگی (تابع ارزش)------------------------------------------- 46

2-13- انواع روش‌های انتخاب------------------------------------------------ 48

2-13-1- انتخاب چرخ رولت---------------------------------------------- 49

2-13-2- انتخاب حالت پایدار---------------------------------------------- 51

2-13-3- انتخاب نخبه گرایی----------------------------------------------- 51

2-13-4- انتخاب رقابتی-------------------------------------------------- 52

2-13-5- انتخاب قطع سر------------------------------------------------- 52

2-13-6- انتخاب قطعی بریندل---------------------------------------------- 53

2-13-7- انتخاب جایگزینی نسلی اصلاح شده------------------------------------ 53

2-13-8- انتخاب مسابقه-------------------------------------------------- 54

2-13-9- انتخاب مسابقه تصادفی-------------------------------------------- 54

2-14- انواع روش‌های ترکیب------------------------------------------------ 54

2-14-1- جابه‌جایی دودوئی----------------------------------------------- 55

2-14-2- جابه‌جایی حقیقی------------------------------------------------ 58

2-14-3- ترکیب تک‌نقطه‌ای----------------------------------------------- 59

2-14-4- ترکیب دو نقطه‌ای----------------------------------------------- 60

2-14-5- ترکیب n نقطه‌ای------------------------------------------------ 60

2-14-6- ترکیب یکنواخت------------------------------------------------ 61

2-14-7- ترکیب حسابی-------------------------------------------------- 62

2-14-8- ترتیب------------------------------------------------------- 62

2-14-9- چرخه------------------------------------------------------- 63

2-14-10- محدّب------------------------------------------------------ 64

2-14-11- بخش_نگاشته------------------------------------------------- 64

2-15- احتمال تركیب------------------------------------------------------ 65

2-16- تحلیل مكانیزم جابجایی------------------------------------------------ 66

2-17- جهش----------------------------------------------------------- 66

2-17-1- جهش باینری--------------------------------------------------- 69

2-17-2- جهش حقیقی--------------------------------------------------- 69

2-17-3- وارونه سازی بیت------------------------------------------------ 70

2-17-4- تغییر ترتیب قرارگیری--------------------------------------------- 70

2-17-5- وارون سازی--------------------------------------------------- 71

2-17-6- تغییر مقدار---------------------------------------------------- 71

2-18- محک اختتام اجرای الگوریتم ژنتیک---------------------------------------- 72

2-19- انواع الگوریتم‌های ژنتیکی---------------------------------------------- 72

2-19-1- الگوریتم ژنتیکی سری--------------------------------------------- 73

2-19-2- الگوریتم ژنتیکی موازی-------------------------------------------- 74

2-20- مقایسه الگوریتم ژنتیک با سیستم‌های طبیعی----------------------------------- 75

2-21- نقاط قوّت الگوریتم‌های ژنتیک------------------------------------------- 76

2-22- محدودیت‌های GAها------------------------------------------------- 78

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

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

2-23-2- استراتژی رَدّی-------------------------------------------------- 79

2-23-3- استراتژی اصلاحی----------------------------------------------- 80

2-23-4- استراتژی جریمه‌ای----------------------------------------------- 80

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

2-25- چند نمونه از کاربردهای الگوریتم‌های ژنتیک---------------------------------- 81

 فصل سوم------------------------------------------------------ 86

3-1- مقدمه------------------------------------------------------------ 87

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

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

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

3-2-3- آمیزش-------------------------------------------------------- 95

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

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

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

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

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

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

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

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

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

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

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

3-4-6- ارزشیابی مجموعه جواب-------------------------------------------- 118

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

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

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

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

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

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

3-5-5- ترکیب-------------------------------------------------------- 123

3-5-6- جهش-------------------------------------------------------- 124

  فهرست منابع و مراجع----------------------------------------------- 126

   پیوست----------------------------------------------------------- 127

واژه‌نامه---------------------------------------------------------- 143

فهرست مطالب 

 فصل اول------------------------------------------------------- 1

1-1- مقدمه------------------------------------------------------------ 2

1-2- به دنبال تکامل...----------------------------------------------------- 3

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

1-4- درباره علم ژنتیک----------------------------------------------------- 6

1-5- تاریخچۀ علم ژنتیک--------------------------------------------------- 6

1-6- تکامل طبیعی (قانون انتخاب طبیعی داروین)------------------------------------ 7

1-7- رابطه تکامل طبیعی با روش‌های هوش مصنوعی--------------------------------- 10

1-8- الگوریتم---------------------------------------------------------- 11

1-8-1- الگوریتم‌های جستجوی ناآگاهانه--------------------------------------- 12

1-8-1-الف- جستجوی لیست-------------------------------------------- 12

1-8-1-ب- جستجوی درختی-------------------------------------------- 13

1-8-1-پ- جستجوی گراف--------------------------------------------- 14

1-8-2- الگوریتم‌های جستجوی آگاهانه---------------------------------------- 14

1-8-2-الف- جستجوی خصمانه------------------------------------------ 15

1-9- مسائل NP-Hard---------------------------------------------------- 15

1-10- هیوریستیک------------------------------------------------------- 17

1-10-1- انواع الگوریتم‌های هیوریستیک--------------------------------------- 19

 فصل دوم------------------------------------------------------- 21

2-1- مقدمه------------------------------------------------------------ 22

2-2- الگوریتم ژنتیک------------------------------------------------------ 23

2-3- مكانیزم الگوریتم ژنتیك------------------------------------------------- 25

2-4- عملگرهای الگوریتم ژنتیك---------------------------------------------- 28

2-4-1- کدگذاری------------------------------------------------------ 28

2-4-2- ارزیابی------------------------------------------------------- 29

2-4-3- ترکیب-------------------------------------------------------- 29

2-4-4- جهش-------------------------------------------------------- 29

2-4-5- رمزگشایی----------------------------------------------------- 30

2-5- چارت الگوریتم به همراه شبه كد آن----------------------------------------- 30

2-5-1- شبه كد و توضیح آن----------------------------------------------- 31

2-5-2- چارت الگوریتم ژنتیک--------------------------------------------- 33

2-6- تابع هدف--------------------------------------------------------- 34

2-7- روش‌های کد کردن--------------------------------------------------- 34

2-7-1- کدینگ باینری--------------------------------------------------- 35

2-7-2- کدینگ جایگشتی------------------------------------------------- 36

2-7-3- کد گذاری مقدار------------------------------------------------- 37

2-7-4- کدینگ درخت-------------------------------------------------- 38

2-8- نمایش رشته‌ها------------------------------------------------------- 39

2-9- انواع روش‌های تشکیل رشته--------------------------------------------- 41

2-10- باز گرداندن رشته‌ها به مجموعه متغیرها-------------------------------------- 42

2-10-1- تعداد بیت‌های متناظر با هر متغیر-------------------------------------- 43

2-11- جمعیت---------------------------------------------------------- 44

2-11-1- ایجادجمعیت اولیه----------------------------------------------- 44

2-11-2- اندازه جمعیت-------------------------------------------------- 45

2-12- محاسبه برازندگی (تابع ارزش)------------------------------------------- 46

2-13- انواع روش‌های انتخاب------------------------------------------------ 48

2-13-1- انتخاب چرخ رولت---------------------------------------------- 49

2-13-2- انتخاب حالت پایدار---------------------------------------------- 51

2-13-3- انتخاب نخبه گرایی----------------------------------------------- 51

2-13-4- انتخاب رقابتی-------------------------------------------------- 52

2-13-5- انتخاب قطع سر------------------------------------------------- 52

2-13-6- انتخاب قطعی بریندل---------------------------------------------- 53

2-13-7- انتخاب جایگزینی نسلی اصلاح شده------------------------------------ 53

2-13-8- انتخاب مسابقه-------------------------------------------------- 54

2-13-9- انتخاب مسابقه تصادفی-------------------------------------------- 54

2-14- انواع روش‌های ترکیب------------------------------------------------ 54

2-14-1- جابه‌جایی دودوئی----------------------------------------------- 55

2-14-2- جابه‌جایی حقیقی------------------------------------------------ 58

2-14-3- ترکیب تک‌نقطه‌ای----------------------------------------------- 59

2-14-4- ترکیب دو نقطه‌ای----------------------------------------------- 60

2-14-5- ترکیب n نقطه‌ای------------------------------------------------ 60

2-14-6- ترکیب یکنواخت------------------------------------------------ 61

2-14-7- ترکیب حسابی-------------------------------------------------- 62

2-14-8- ترتیب------------------------------------------------------- 62

2-14-9- چرخه------------------------------------------------------- 63

2-14-10- محدّب------------------------------------------------------ 64

2-14-11- بخش_نگاشته------------------------------------------------- 64

2-15- احتمال تركیب------------------------------------------------------ 65

2-16- تحلیل مكانیزم جابجایی------------------------------------------------ 66

2-17- جهش----------------------------------------------------------- 66

2-17-1- جهش باینری--------------------------------------------------- 69

2-17-2- جهش حقیقی--------------------------------------------------- 69

2-17-3- وارونه سازی بیت------------------------------------------------ 70

2-17-4- تغییر ترتیب قرارگیری--------------------------------------------- 70

2-17-5- وارون سازی--------------------------------------------------- 71

2-17-6- تغییر مقدار---------------------------------------------------- 71

2-18- محک اختتام اجرای الگوریتم ژنتیک---------------------------------------- 72

2-19- انواع الگوریتم‌های ژنتیکی---------------------------------------------- 72

2-19-1- الگوریتم ژنتیکی سری--------------------------------------------- 73

2-19-2- الگوریتم ژنتیکی موازی-------------------------------------------- 74

2-20- مقایسه الگوریتم ژنتیک با سیستم‌های طبیعی----------------------------------- 75

2-21- نقاط قوّت الگوریتم‌های ژنتیک------------------------------------------- 76

2-22- محدودیت‌های GAها------------------------------------------------- 78

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

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

2-23-2- استراتژی رَدّی-------------------------------------------------- 79

2-23-3- استراتژی اصلاحی----------------------------------------------- 80

2-23-4- استراتژی جریمه‌ای----------------------------------------------- 80

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

2-25- چند نمونه از کاربردهای الگوریتم‌های ژنتیک---------------------------------- 81

 فصل سوم------------------------------------------------------ 86

3-1- مقدمه------------------------------------------------------------ 87

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

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

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

3-2-3- آمیزش-------------------------------------------------------- 95

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

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

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

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

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

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

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

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

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

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

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

3-4-6- ارزشیابی مجموعه جواب-------------------------------------------- 118

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

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

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

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

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

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

3-5-5- ترکیب-------------------------------------------------------- 123

3-5-6- جهش-------------------------------------------------------- 124

  فهرست منابع و مراجع----------------------------------------------- 126

   پیوست----------------------------------------------------------- 127

واژه‌نامه---------------------------------------------------------- 143