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

صفحه 1:
مر 

صفحه 2:
الكُوريتم ژنتیک 

صفحه 3:
‘Gi. Z ‏الگوریتم های فرا ابتکاری/فرا اکتشافی‎ ‏نوعی از الگوریتم‌های تصادفی هستند که برای یافتن پاسخ‎ " ‏بهینه به کار می‌روند.‎ ""راهکارهای پیشرفته و کلی جستجو می‌باشند و گام‌ها و معيارهايى را ييشنهاد مى كنند که در فرار از دام بهینه‌های موضعى بسيار مؤثر هستند. "یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند كه داراى راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده‌ای از مسائل را دارند. 

صفحه 4:
الگوریتم های فرا ابتکاری/فرا اکتشافی روش‌ها و الگوریتم‌های بهینه‌سازی ۱.دقیق ‎(exact)‏ ‏۲الگوریتم‌های تقریبی ‎(approximate algorithms)‏ الگوربتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه‌سازی سخت کارلیی کافی ندارند و زمان اجرای آن‌ها متناسب با ابعاد مسائل به صورت نمایی افزایش می‌یابد. الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. 

صفحه 5:
انواع الگوریتم های تقریبی 1الکور بنم‌های ابتکاری ‎(heuristic)‏ ‏2.فراابتکاری ‎meta-)‏ ‏1521 اناعط) ) hyper) ‏3.فوق ابتکاری‎ (heuristic 

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

صفحه 7:
دسته‌بندی الگوریتم‌های فرا ابتکاری 1.مبتنی بر یک جواب و مبتنی بر جمعیت: الگوریتم‌های مبتنی بر یک جواب در حین فر آیند جستجو یک جواب را تغییر می‌دهند. در حالی که در الگوریتم‌های مبتنی بر جمعیت در حین جستجوء یک جمعیت از جواب‌ها در نظر گرفته می‌شوند. 2الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم‌های فراابتکاری از طبیعت الهام گرفته شده‌اند. در اين ميان برخى از الگوربتم‌های فراابتکاری نیز از طبیعت الهام گرفته نشده اند . 

صفحه 8:
با حافظه و بدون حافظه: برخی از الگوریتم‌های فراابتکاری فاقد حافظه می‌باشند. به لین معنا که. لین نوع الگوربتم‌ها از اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند لبه طور مثال تبرید شبیه‌سازی شده). لین در حللی است که در برخی از الگوریتم‌های فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حیین جستجو را در خود ذخیره می‌کند. 4.قطعى و احتمللي: يك الكوريتم فراابتكارى قطعى نظير جستجوى ممنوعه. مسئله رابا استفاده از تصميمات قطعى حل مىكند. اما در الكوريتمهاى فراابتكارى احتمللى نظير تبريد شبيه سازى شده. يك سرى قوانين احتمللى در حين جستجو مورد استفاده قرار مى كيرد 

صفحه 9:
الگوریتم های مبتنی بر یک جواب -الگوریتم تبرید شبیه سازی ‎simulated annealing o12‏ -جست وجوی ممنوعه ‎tabu search‏ -جست و جوى حريصانه 5621701 2 01145 variable ic Slice ‏-جست و جوی‎ neighborhood search guided local searchoxs cule ‏-جست و جوی محلی‎ interated localosgs 155 les og> 9 Ce search 

صفحه 10:
الگوریتم های مبتنی بر جمعیت Genetic Algorithm ‏الگوریتم ژنتیک‎ -الگوریتم رقابت استعماری 60۳0۴6161۷6 ]5ناج۱۳۴۵۲ ‎Algorithm‏ -الگوریتم بهینه سازی کلونی مورچگان 6010۳۷ ۸۵۲ ‎Optimization Algorithm‏ -الگوریتم کلونی زنبور عسل ۵۱9۵۲۱۲۳۲0 60۱0۷ عع8 -الگوریتم کرم شب تاب ۱9۵۲:۲۳۲۴ ‎Firefly‏ Artificial Immune SysteM ‏-الگوریتم سیتم ایمنی مصنوعی‎ Algorithm Harmony Search Algorithm (390,8 ‏-الگوریتم جستجوی‎ Particle Swarm o1,3 ‏-الگوریتم بهینه سازی تجمعی‎ Optimization Algorithm 

صفحه 11:
هيوريستيك ها الگوریتم هلیی هستند که می توانند یافتن جوابهای خوب در فاصله مشخصی از جواب بهینه را تضمین کنند که به آنها الگوربتم های تقریبی می گویند. الگوربتم های دیگری هستند که تضمین می دهند با احتمال بالا جواب نزدیک بهینه تولید کنند که‌به آنها الگوریتم های احتمللی گفته می شود. جدای از لین دو دسته. حی توان الگوربتم هلیی را پذیرفت که هیچ تضمینی در ارلئه جواب ندارند اما بر اساس شواهد و سوابق نتلیج آنهاسبه طور متوسط بهترین تقلبل کیفیت و زمان حل برای مسئله مورد بررسی را به همراه داشته اند 

صفحه 12:
هیور يستيك تمعیارها. روشهایا اصولی برای تصمیم گیری بین چند گزینه خط مشی و انتخاب اثربخش ترین برای دستیابی به اهداف مورد نظر . انتیجه برقراری اعتدال بین دو نیاز هستند: نیاز به ساخت معیار های ساده و در همان زمان توانایی تما ن | "یک هیوریستیک می تولند حسابی سرانگشتی باشد که برای هدلیت یک دسته از اقدامات به کار میرود. برای مثال.یک روش مشهور برای انتخاب طللبی رسیده عبار تست از فشار دادن محل اتصالبه ريشه ازیبک طللبی نامزد انتخاب و سپس بو کردن آن محل. اگر بوی آن محل مانند بوى داخل طللبى باشد.آن طللبیبه احتمال زیاد رسیده است. این قاعده سرانگشتینه تضمین حی کند که تنها طللبی های رسیده به عنوان نامزد انتخاب شهند ونه تضمین عی کند که طللبی های رسیده آزملیش شده. رسیده تشخیص داده شوند اما به هر حال این روش .اثربخش ترین روش شناخته شده است. بز درست اب های خوب و بد. 

صفحه 13:
جهانی که در آن زندگی می‌کنيم . ‎٩‏ به طور مداوم در حال تغیبر است. ‏۴ هر موجودی که قصد ماندن در چنین محیطی را داشته باشد. بایستی بتواند خود را با شرایط اطراف تطبیق دهد. ‏# اين فرآیند تطبیق, به نام‌های تکامل یا فرگشت ‎(Evolution)‏ ‏معروف است. 

صفحه 14:
تکامل عست؟ تكامل ‎(Evolution)‏ حاصل عملکرد پدیده‌هایی همچون © انتخاب طبيعى ‎(Natural Selection)‏ (Reproduction) Jo agi © (Mutation) ‏جهش‎ © تغییرات براه ‎wera‏ Symbiosis) (aw jor 9° است. انگیزه خودتکثیری, سگ و گربه در اثر مجاورت و همزیستی با ءانسان از سایر گربه انان باهوش ترند انطباق بیشتر با" دارد شانس بقاء بيشتر دارد. مثال تابودی دایتاسورها 

صفحه 15:
زنتیک : 5 ‎suk ۱ > oo‏ ۰ ‎٩‏ طبیعت برای آن که بتواند کار بهینه‌سازی را به خوبی انجام دهد بایستی اطلاعات به دست آمده در طول میلیون‌ها سال را به نحوی ذخیره کند. ۴ زیربنای تشکیل دهنده موجودات ‎wij‏ عناصر شیمیایی هستند. لذا طبیعت از همین عناصر ‎ly‏ ذخیره‌سازی اطلاعات مربوط به هر گونه زیستی, استفاده می کند. 

صفحه 16:
اقا چگونه؟ ۴ اطلاعات مربوط به هر موجود زنده, در یک ساختار پیچیده شیمیایی به نام 11۸ ذخیره شده‌اند. * ۸ حاوی تمام اطلاعات ضروری برای بازسازی یک موجود زنده است. لذا از ۸( به عنوان تنظیم کننده اطلاعات وراثتی نیز یاد -اطلاعات ما ريينة_ر می‌شود. > ‎Gta‏ ‏2 مرش داهن ۳۲ انسان 

صفحه 17:
ساختار 1037۸ مولکول ‎DNA‏ به شکل یک نردبان مارپیچ است که شاخه های اصلی آن از توالی قند و فسفات تشکیل شده اند. پایه های این نردبان» از اتصال چهار نوع باز آلی تشکیل شده اند. ۳ سیخ سایتوزین ‎ )0(‏ گوانین (6) تیمین ‎ )1(‏ آدنین (۸) 

صفحه 18:
1۸ از نمای نزدیک ... جهار نوع تركيبه كه همكى نيازمند برقرار شدن پیوند هیدروژنی هستند. قابل ایجاد می باشند: TA AT GC CG 

صفحه 19:
ژن چیست؟ ‎٩‏ اطلاعات مربوط به تمام موجودات زنده. در توالی و ترتیب‌های خاصی از ترکیب‌های شیمیایی معرفی شده در بخش قبل» ذخیره مى شوند. ‏؟ ژن‌ها بخش‌های به خصوصی از ساختار 108۷۸ هستند که خواص و ویژگی‌های موجود زنده را تعریف می‌کنند. ‏* 12۸ انسان, شامل بیش از سه میلیارد عدد از ترکیبات پایه است که نوع و توالی بیش از ‎۹٩‏ درصد از اين تعداده برای تمام انسان‌ها مشترک می باشد. در واقع اطلاعات مربوط به هر فرد در کمتر از یک درصد از ساختار ۸ ذخیره سازی شده است. 

صفحه 20:
ژنتیک الفبای طبیعت است ... _ 0 0 9 تک تک عناصر سازنده-ژنو تیپ خروجی انواع ترکیبهای ژنو تیپ -فنوتیپ یا تابع هدف 

صفحه 21:
يك نتيجه مهم .. ** رابطهاى يك به يك ميان هر موجود زنده و رشته ژنی‌اش وجود دار به این معنی که, هر موجود زندهاى» يك ساختار 10114 ثابت دارد كه در هيج موجود زنده ديكرى؛ حتى از همان گونه, تکرار نشده است. البته برخی تک سلولی‌های بسیار ساده, از اين امر مستثنى هستند. **از چنین رابطه‌ای با نام کدینگ یاد می‌شود. می‌توان هر موجود زنده را به عنوان اطلاعات اصلی» و رشته ۸( آن را به عنوان کد در ‎een‏ صورت یکستزی ‎TL‏ 0( زتی) نشان میدهد. هر فنود ی با معیارهای طبيعت دارد مى مافد. و اتن اكز به آرت برسه يكجون همكرايى در خواص داريم. اكر از اين مكانيزم تقليد كنيم ‎ ‎ ‎ ‎ 

صفحه 22:
یک ایده !ا * موجودات کنونی, نتیجه هزاران بار تکرار یک الگوريتم بهینه‌سازی عظیم هستند, که هدف از اجرای آن» افزاینش توان بقای موجودات زنده است. * می‌توان از مکانیزمی که طبیعت برای بهتر کردن موجودات زنده استفاده کرده است. تقلید کرد و اقدام به بهین‌سازی نمود. در فرآیند بهینه سازی؛ ما در بى ياقتن بهترین جواب, از میان چندین جواب ممکن برای یک مسأله هستیم. * به اين منظور باید جواب‌ها. همانند موجودات زنده, داراى 224 يا كد معلدل باشند. © می‌بایست معیاری برای ارزیابی هر جواب در دست داشته باشیم. 

صفحه 23:
طرح أوليه يك الكوريتم تكاملى do yl ly 1 ايجلا مجموعهاى از جوابهاى تصلافی (. مقايسه جوابها رتبهبندى أنها و انتخاب يبترين ها (. ترکیب جوابهاى به دست أمله با شبيه سازى فرأيندهاى طبيعى براساس اطلاعات جمعيت فعلى جمعيت ‎dole‏ توليد ‎peal y «fe‏ جوابهاى جديدبا جوابهاى قليمى ‏جدید بدست می اوریم ‎ ‏4 بازگشت به مرحله ۲ [در صورت نی نیپ پزاجل 4-2 رات زماتی که شرايظ ‏توقف یا شراب این پروسه تکرار می گردد. مورد نظر ‎ ‎ ‎ ‎ 

صفحه 24:
چرخه تکامل در یک الگوریتم تکاملی a 9 86 eee ‏سیف‎ 

صفحه 25:
الگوریتم ژنتیک * از اوایل دهه ۱۹۵۰ میلادی, تلاش‌هایی برای شبیه‌سازی پدیده تکامل بر روی کامپیوترها آغاز شد. که در این میان توجه بسیاری از محققین حوزه‌های مربوط به علوم ریاضی و مهندسی, به اين زمينه جلب شد. نهایتا در اوایل دهه ۱۹۷۰ جان هالند. در کتابش الگوریتم ژنتیک را به عنوان ابزاری عمومی برای بهینه سازی, معرفی نمود. * الگوریتم ژننیک» نوع خاصی از الگوریتم‌های تکاملی است که برگرفته تکامل .طبیعی و تقشل #ننيك ذر طبيعث أسقد 

صفحه 26:
لگوریتم ژنتیک * یکی از شاگردان هالند به نام دیوید گولدبرگ» کارهای پراکنده‌ای را که توسط هالند انجام شده بود جمع‌آوری کرد و به همراه نتایج حاصل از تحقیقات خود در قالب یک کتاب جامع. منتشر نمود. می‌توان گفت. گولدبرگ با انتشار این کتاب» بیشترین سهم را در توسعه و معرفی الگوریتم ژنتیک داشته است. ۴ در اواسط دهه ۱۹۷۰ نتایج کارهای دیونگ منتشر شدند» که ‎SE‏ از کارآمدی الگوریتم ژنتیک برای حل انواع مسائل بهینه‌سازی بودند. 

صفحه 27:
مر احل الگوریتم ژنتیک ‎GA : Genetic Algyritine‏ ‎"١‏ ايعلدجمعب نضا د وازاى كنصا ‎wager IDG BCT, gay YO‏ ۳ انتحاب اعضاى حمعي برزى ١عبل‏ حفيل واجددحموت حصق باقن #ارعام حعب | ملى» ‎Maye Gr I's Kab Gar » haz‏ ‎min blot‏ مره با 5 ۲ ‎Ka‏ هرد حازنم محقق نه باش زمجله 0 کزری کم ۶ بان 

صفحه 28:
لول مسلط حاهّه : ۱- رسیین به حرتارل موی ان پاسم میرن زان / کر معن PLO roa ‏سیری هرد زمان / 4ك[ عمق سن مسا كذ‎ mY 

صفحه 29:
بهینه سازی فرآیند بهتر کردن هر چیزی .يك مهندس و یا یک محقق ایده جدیدی را خلق میکند و بهینه سازی به این ایده خلق شده کیفیت می بخشد . در فرایند بهینه سازی تغییرلتی بر روی ایده اولیه انجام می شود و با نتایج حاصل از این تغییرات. ایده اولیه بهبود می یابد. تا مادامی که بتوان ايده مورد نظر را در غللب الکترونیکی نوشتء کامپیوتر وسیله ای مناسب برای بهینه سازی خواهد بود . بهتر درنظر گرفتن یک جواب به مسئله مورد بررسی» روش بررسی مسئله و محدوده تغییرات بستگی دارد. 

صفحه 30:
Optimizoriow ‏دعین سازی‎ Obgective Funstion Goel yw N\ Minbwization ‏سازى‎ ou Moxiwrzostion Giweuatl Fh — a Cosy Func. 852 2 1 ۲۸۵55 Func, ‏تاع برلزثری‎ Enor Func, tb 9 Probie Fume. Seige 

صفحه 31:
شرح الگوریتم ژنتيك هدف بسیاری از مسایل مهندسی و علوم : بهینه سازی تابع هدف روشهای تحلیل مسایل مهندسی : LAGRANGE MULTIPLIERSI,SY ‏روش مضارب‎ . (METHOD (Calculus Of Variations) =! 235 Guo wil( (Numerical Methods) ‏شيوه هاى عددى‎ ۳ Gradient based) ‏روش های مبتنی بر گرادیان‎ ((Methods ۴ روش های تابع جریمه ‎(Penalty Function‏ 

صفحه 32:
شرح الگوریتم ژ حل همه مسایل مهندسی استفاده از روش های مبتنی بر گرادیان تابع هدف امکان پذیر نیست روش هاى قطعى ‎Deterministic)‏ (9 & ( (Stochastic) solai cle (3, تصادفی, روش های تصادفی :از نمونه برداری تصادفی در فضای جستجو یا مد لهای تصادفی تابع هدف استفاده می کنند. که در سالهای اخیر توجه زیادی رلبه خود جلب کرده لند و اینبه دلیل ارایه روش های موثری در حل مسایل بهینه سازی مشکل و امکان دستیابی به نقاط بهینه کلی می باشد . روش های غیر تصادفی: دارای لین اشکال هستند که‌به محض رسیدن‌به اولین نقطه بهینه محلی متوقف شده و توانلیی خروج از لین نقطه و حرکت‌به سوی نقاط بهینه دیگر و در نهلیت نقطه بهینه مطلق را ندارند 

صفحه 33:
الکوریتم ژنتيك * الگوریتم ژنتیک به روش بهینه سازی الهام گرفته از طبیعت جاندار است که مى توان در طبقه بندی ها . از آن به عنوان یک روش عددی . جستجوی مستقیم و تصادفی معرفی کرد. ۴ این الگوریتم , الگوریتمی مبتنی بر تکرار است و اصول اولیه آن از علم 5 اقتباس گردیده است و با تقلید از تعدادی از فرایندهای مشاهده شده در تکامل طبیعی اختراع شده است و به طور موثری از معرفت قدیمی موجود در یک جمعیت استفاده می کند. تا حل های جدید و بهبود بافته را ایجاد کند. * این الگوریتم در مسایل متنوعی نظیر بهینه سازی, شناسایی و کنترل سیستم . پردازش تصویر و مسایل ترکیب توپولوژی و آموزش شبکه های عصبی مصنوعی و سیستم های مبتنی بر تصمیم و قاعده به کار می رود. 

صفحه 34:
الگوریتم ژنتيك ۴۵۵5 ۴ 

صفحه 35:
ف علم زنتيك *© درباره جكونكى توارث و انتقال صفحات بيولوزيكى از نسلى به نسل بعدصحبت مى كند. ۴ عامل اصلی انتقال صفحات بیولوژیکی در موجودات زنده کروموزوم 6]0۳010501۳06))ها و ژن ها68606)) می باشد و نحوه عملکرد ان ها به گونه ای است که در نهایت ژن ها و کروموزوم ها ی برتر و قوی تر باقی مانده و ژن هاى ضعيف تراز بين مى روند. * نتيجه عمليات متقابل رن ها و كروموزوم ها باقى ماندن موجودات اصلح و برتر مى باشد. اين الكوريتم براى بهينه سازى. جستجو و ياد كيرى ماشين مورد استفاده قرار ۴ اساس این الگوریتم قانون تكامل دارو بهترين" است كه ميكويد موجودات ضعیف تر از بین میروند و موجودات قوی تر باقی میمانند. * در واقع تکامل فرایندی است که روی رشته ها صورت میگیرد.نه روی موجودات زندهای که معرف موجودات رشته است. در واقع. قانون انتخاب طبیعی ‎Natural‏ ‎)١ 6» 20‏ برای بقا می گوید که هر چه امکان تطبیق موجود بیشتر باشد بقای موجود امکان پذیر تر است و احتمال تولید مثل بیشتری, برایش وجود دارد. اين قانون بر اساس پیوند بین رشته ها و عملکرد ساختمان های رمز گشایی شده ان ها می باشد. 

صفحه 36:
الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی با تطبیق الگو استفاده م ىكنند. * به عبارت ديكر افراد يك جامعه انسانى إحيوانى اكياهى/..) از طريق جفتكيرىازاد و ولد نسل ‎gs aley! ( New Generation) 24>‏ کنند. * شانس بقاء یک فرد در جدید به ترکیب خاص گروموزومی آن فرد در نسل جديد وابسته است. * به جز در موارد استثنابی که ممکن است جپشهایی(1۵00//) در خصوصیات یک فرد نسل جدید رخ ده معمولا افراد نسل جدید سازگاری پیشتری با طبیعت دارند. 

صفحه 37:
۶ در اغلب موارد افراد جهش يافته با طبیعت ناسازگارند. *_ در موارد نادر, ممکن است موجودی با خصوصیات بسیار عالی و سازگاری بالا تولید شود. بطور خلاصه در هر نسل به گونه های بهتر, فرصت تولید مثل داده شده(5000اوانا۳) و گونه های دارای خصوصیات نامطلوب بتدريج از بين مى روند. *؟ در نتیجه با گذشت زمان افراد نسلهای مختلف تکامل (2۷0/۷0/0۳) می پایند. 

صفحه 38:
الگوریتم ژنتیک معروف ترین وچر کار بردترین تکنیک جستجو فراابتکاری برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم‌های تکامل است که از تکنیک‌های زیست‌شناسی فرگشتی مانند ورائت و جهش استفاده می‌کند. لین الگوریتم برای اولین بار توسط جان هلند در سال ۱۹۷۰ معرفی شد. 

صفحه 39:
الگوریتم ژنتیک به صورت ذاننی جز الگوربتم های گسسته و باینری میباشد. ولی ساختارش به شکلی میباشد که میتولند مسائل پیوسته را نیز حل کند از لین رو پر اپشن ترین الگوریتم فراابتکاری است و به همین علت پر کاربردترین الگوریتم میباشد. 

صفحه 40:
عملگرهای الگوریتم ژنتیک 1 تبدیل جواب مساله به رشته اعداد باینری( تبدیل متغیرهای مساله به کد) 2 هررشته با یک مقدار عددی ارزیابی می شود هرجه کیفیت رشته جواب بالاتر باشد مقدار برازندگی جواب بیشتراست. 3 نسل قدیمی کروموزوم ها با هم ترکیب شده تا نسل تازه ای از کروموزوم ها بوجود آیند. ۵4 زنی ازمجموعه ژنهای جمعیت حذف يا ژنی به آن اضافه می شود. 5 روی بهترین جواب مساله انجام می شود. 

صفحه 41:
نواع روش های کدگذاری * کدگذاری ری :عم لاه مور ی ۰و !نان ده یبن به نی مد نهر كرومؤزوة ‎es al be‏ * کدگذاری جایگشت :برای کد گذاری مسائلی مثل فروشنده‌ی دوره گرد که ترتیب رفتن به شهرها ‎ab‏ پهینه شود استفاده می شود. کدگذاری مقدارحفیقی :در هر ژن ‏ مقدار حقیفی قرار می گیل 

صفحه 42:
ساختار الگوریتم 

صفحه 43:
1.تعريف ديتاى اوليه باتوجه به ماهيت هر مساله اين قسمت در ابتداى الكوريتم تعريف ميشود.مثلا در مساله 6 وزير 8 وزير داريم. 

صفحه 44:
2.تعریف پارامتر های الگوریتم ‎npop=10; % number of population,ss‏ pc=0.8; % percent of crossover s,a.S pm=0.2; % percent of mutation,e.S5 maxiter=100; % number of Iterations,s_s 

صفحه 45:
3.تولید جمعیت اولیه تصادفی با توجه به ساختار هر مساله فرق میکند به طور مثال برای مساله 5۳ فروشنده از درایه ۵ به درایه ۱و از از ۱به ۴ از ۴ به ۳ و از ۳ به ۲و برمی گردد به ۵.محدودیت در 9 آ:از شهر یکبار عبور مى کنیم و در تنتها به همان شهر برمی گردیم. هر کدام از اين درایه ها یک ژن است. ee 2 3 4 1 5 8 321 | Fitnes 5 

صفحه 46:
23 440 Pop3.fit428 181 Pop5.fit159 349 580 270 393 212 Pop1.fit 1 ۱2 ۱4 | 56 Pop3.fit 314/15] Popa.fit 5 ۱3 ۱2 | Pop7. fit 4 ۱3 | 5 | Pop9. fit 53 4| 0 fit 4 Yeonumber of Popl. x 35 Pop2. x 12 Pop3. x 1 | 4 Pop4. x 12 Pop5. 2 2/1 Pop6 000*29 

صفحه 47:
شروع حلقه اصلی 

صفحه 48:
مثل همه الگوریتم های فرابتکاری بايد جواب هاى اوليه تغيير كنند به شيوه اى كه به سمت بهتر شدن ميل داشته باشند. حال اين كه دراين الكوريتم ابن روند به جه شكلى است در ادامه مشاهده خواهيد كرد. در الكوريتم زنتيكد اولين تغيير يا ابراتور كراس اوور يا تقاطع است. دو جواب يا دو والد با شيوه هاى زير انتخابه مى كنيم: 

صفحه 49:
انواع تقاطع در الگوریتم ژنتیک ‎٠‏ کراس آور باینری/جایگشتی ‏1. تک نقطه ای ‏2. دو نقطه ای ‏3 ماسک ‏کراس آور مخصوص مسایل پیوسته ‎Arithmetic.1‏ ‏2. هیوریستیک 

صفحه 50:
CrossOver alola; ,Sloc ابتدا باید دو والد (جواب) را انتخاب کنیم. شیوه انتخاب: ۱- چرخه رولت ۳۲- تورنومنت ۳- تصادفی ۴- انتخاب چرخ گردان 

صفحه 51:
1- چرخه رولت آن که بهتر است شلنس بیشتری برای انتخاب شدن دارد. فرض مساله ماکزیمم سازی است.یک عدد تصادفی از صفر تاییک انتخاب میکنیم مثلا ۰1۶ که بین ۴ ۰/۷ است. ۰/۷ را انتخاب می کنیم.چون دوا وللد می خواهیم دو بار این پروسه تکرار می شود. eS 1 2 3 4 

صفحه 52:
2- تور نومنت سه عدد 7 و 4 و 5 را به طور تصادفی انتخاب می کنیم.7 5011۲10۱ از همه بهتر استوبعنوان والد انتخاب ‎no‏ شود. Champion rs ‏حول مس‎ ‏و‎ 1۳ Tournament result 3- تصادفی جولبه‌اییمو سکیا از بسکتا دملنتخابمیک نیم10 

صفحه 53:
والد 4 2 1 5 3 1 ally ‏جواب‎ go) ‏دورفرزند‎ yl de ‏دو والد مورد نظر انتجاب حده افد‎ ‏جدید ) بر اساس این دو والد تولید کرد.‎ شیوهتولید: ۱- تقاطع تک نقطه ای ۲- تقاطع دو نقطه ای ۳- تقاطع ماسک ۴- تقاطع پیوسته ( یونیفرم < آربتماتیک) 

صفحه 54:
انتغاب چرخ گردان در این روش عدد برازش داده شده ملاک قرار كرفته و عددى كه داراى بالاترين مقدار برازش باشد انتخاب مى كردد. در واقع به اين صورت عمل مى شود كه به هر عضو جامعه . یک احتمال تجمعی نسبت داده وبا اين احتمال ‏ شانس انتخاب هر عضو تعبين مي كردد. 

صفحه 55:
یک نقطه تصادفی از یک تا ۵ را انتخاب می کنیم مثلا درایه ‎Fr‏ اطع تک نقطه ۲ را انتخاب می کنیم.بعد برش می زنیم. اعداد نباید تکراری تقا ای باشند.۵و ۳ و ۴ را که از والددیگر گرفتیم می ماند اما ۵و۳ را با او۲ جابجا می کنیم تا603۲آاشود. | فرزند والد 9 315 1 4 2 1 5 3 1 فرزند والد 4 2 1 2 1 2 ۱9 2 فرزند و اش ۰۱2 1 

صفحه 56:
parents ww offspring wy 

صفحه 57:
تقاطع دو نقطه ای دو نقطه را بطور تصادفی انتخاب می کنیم و مابین ان را تغییر می دهیم.]038۲]وسط جایشان عوضمی شود. Crossover Points !| ا Parents: 1010001110 0011010010 1 P= | offspring: 1010010010 0011001110 

صفحه 58:
تقاطع ماسک (Randomly generated) 0011010010 1010010110 اگر درایه ماسک امان 1 بود از والد اول می گیرد .اگر ۵ بود از والد دوم.برای فرزند دوم بالعکس Mask: 0110011000 Parents: 1010001110 Offspring: 0011001010 

صفحه 59:
تقاطع پیوسته ( بونیفرم - آریتماتیک) 9 0.7 0.6 0.3 0.8 والد 1 0.20.3 0.2 0.6 1 والد2 

صفحه 60:
تقاطع پیوسته ( بونیفرم - آریتماتیک) یک بردار بین صفر و یک تولید می کنیم: ‎Offspringl=a*parent1+(1-a)*parent2‏ ‎Offspring2=(1-a)*parentl+a*parent2‏ 

صفحه 61:
کراس آور هیوریستیک * Offspringl1=parent1+r*(parent2- parent1) * Offsring2= parent2+r*(parent1- parent2) 

صفحه 62:
جه تعداد فرزند تقاطعی تولید کنیم؟ ‎pc=0.8; % percent of crossover‏ Nc=8; 

صفحه 63:
عملگر جهش ابتدا باید یک والد (جواب) را انتخاب کنیم. شیوه انتخاب: ۱- چرخه رولت ۲- تورنومنت ۳- تصادفی 

صفحه 64:
والد 4 2 1 5 3 1 یک والد مورد نظر انتخاب شده اند. بر اساس روش جهش تولید کرد. شیوه تولید: Swap - ۳6۷۵۲5۲۵۴ ۲ ۱۱۳۱۱۲۵۲۴۸ ۳ 

صفحه 65:
دوتا درایه را بطور تصادفی انتخاب 0 .کرده جای آنها را عوض می کنیم | | Mh) 3/5) 2/2) 4 55 ‏د‎ 3 2 1 5 4 

صفحه 66:
همان دو درایه انتخاب می شود مابین آندو آینه یا ‎Reversion‏ .برعكس می شود ‎| | ‏6 4 2 1 5 3 والد ‏فرزن ‏ها | ره | اش اه ره ۱ 

صفحه 67:
Scramble * Pick a subset of genes at random * Randomly rearrange the alleles in those positions 1112134151617819 ———» +16 (note subset does not have to be contiguous 

صفحه 68:
dnsert Mutation) >> ‏جهش‎ "* * بصورت تصادقی دو ژن را انتخاب می کند و مقدار دوم را به مکان بعد از اولی منتقل می کند و بقیه ژن ها را برای پر کردن جای آن شیفت می دهد. * این عماگر اغلب اطلاعات مربوط به ترتيب و مجاورت را حفظ می کند. | Ph] —- CEPT ۷ © 

صفحه 69:
‎ls ۰‏ جهش با توزیع احتمالی ‏از ‎ 

صفحه 70:
uniform ‏یک تعداد درایه انتخاب کرده سپس یک مقدار‎ ‏.تصادفی به آنها اضاقه یا کم می شود‎ (1.29 5.68 2.86 4.11 5.55) (1.29 5.68 2.73 4.22 5.55) 

صفحه 71:
چه تعداد فرزند جهشی تولید کنیم؟براساس درصد اولیه که تعیین نموده ایم.۲ بار فرایند ز پر انجام می شود. ‎pm=0.2; %” percehit of mutation‏ Nm=2; 

صفحه 72:
10=Old Population 8=CrossPop 2=MutPop 

صفحه 73:
انتخاب ۱- مرتب سازی از خوب به بد ۲- انتخاب بهترین ها ( به تعداد مورد نیاز) 

صفحه 74:
پایان یک دور از حلقه اصلی 

صفحه 75:
تا زمان برقراری شرط توقف این روند را ادامه میدهیم شرط های توقف ۱- تعداد تکرار ۲- زمان وک عدم بهبود ۴- همگرایی maxiter=100; % number of Iteration 

صفحه 76:
نمايش نتايج مراحل کلی الگوریتم ژنتیک: ‎INSERT DATA.1‏ ‎POPULATION 95.2‏ 3.کراس اور ‎MUTATION.4‏ ‎FITNESS.5‏ 

صفحه 77:
مساله فرو شنده دوره گرد 

صفحه 78:
مسئله‌ای مشهور است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و ها پ ویتتی از دانشگاه پرینستون مورد شقرارمك ين شكل است: تعدادى شهر كاري و هزينه رفتن مستقيم از يكى به ديكرى را مىدانيم. مطلوب است كمهزينهترين مسيرى كه از يك شهر شروع شود و از تمامى شهرها دقيقا يكبار عبور كند و به شهر شروع بازكردد. 1 تعداد كل رافحلها برابر است با 000001 20 براى ©<- كدهج تعداد شهرها است 

صفحه 79:
<> | 1 و از 1به 3 و از 3 به 5 و از 5 به 2۰ می رود 

صفحه 80:
مسئله 9 -وزیر مسعله چند وزیر یک معمای شطرتجی و ریاضیاتی است که یر انانن آن باید 9 وزیر شطرنج در یک صفحه 10*1 شطرتج یه‌گونه‌ای قرار حاده شوند که هیچ‌یک زیر ضرب دیگری نباشند. با توجه به اینکه وزیر به‌صورت افقی, عمودی و آریب حرکت می‌کند. باید هر وزیر را در طول. عرض و قطر متفاوتی قرار داد. مسئله 10 وزیر در صورتی جواب دارد له مساوی ۱ یا بیشتر از ۳ باشد. یعنی مسئله دو وزیر و سه وزیر راه حلی ندارند ‎١‏ هیچ دو وزیری نمیتوانند در یک ردیف قرار بگیرند. ۲ _ هیچ دو وزیری نمیتواتند در یک ستون قرار یگیرند. ۳ هیچ دو وزیری تمیتوانند در یک قطر قرار بگیرند. 

صفحه 81:
حوزه هر یک از وزیر ها سطر. ستون و قطر موقعیتی است که در صفحه شطرنج قرار گرفته است. 

صفحه 82:
متغير بكار كرفته شده در اين مسئله. آرایه ی یک بعدی به طول 7 می باشد. هر جایگشت از مقادير ممكن از يكار را حالت از فضای جستجو اراله می شود. تعریف متفیر بکار رفته محدودیت دوم را ارضا می کندد [[:1:2,۰) > ,۵۰0۱0 ,02۰۰ ,0)) ع ۸ تصميم كيرى و :0)سلول 4 ام متفیر تصمیم گیری است. به عنوان یک اظر با صفحه شطرنج. حاوی سطر محل وزير می باشد. اولین محدودیت به صورت زیر بیان شده استد )2( ر 0‏ ,0 ...1( € ‎vi,j‏ منومین محدودیت نیز به ضورت زیر بیان شده اننته wij €(4,-.,n},1Q—Q| = li-Jl (3) 

صفحه 83:
الگوریتم 8وزیر نکته:در هشت وزیر هدف چیدن ۸ مهره وزیر است بطوربکه هیچ مهره ای مهره های دیگر را در یک سطر. یک ستون با یک قطر تهدید اگر اختلاف بین اعداد درون درلیه ها- اختلاف درايه ها ->وزیرها برخورد دارند. 

صفحه 84:


صفحه 85:


صفحه 86:


صفحه 87:
لموله ى از مسئله ى كوله بسي يك بعدى جه جعبه فابى بابد انتخاب شوند نا مقدار بول بيشينه شود اما وزن جعبه فا مذكور ‎joe‏ از 15 كبلوكرم نشرد؟ بك مسلله جلد محدودبئي؛ مس توأئد هم وزن رهم حجم ‎Mag Ry ll fs le aKa Bt Un‏ ها یک ‎$i thy‏ إراه حل؛ اكر هر تهداد دلخراهی از جعبه ها در دسترس باسد: 3 جعبه ی زرد و3 جع eine Pei pees : يعني أز هر جعبه قلط يكن باشيد؛ نُمامى جعبه ها به جز جعبه ى سبز را اتئخاب مى كليم) 

صفحه 88:
n ‏مدا > را بیشینه کنید.‎ ۰ i=1 > wiz; 3 W, rE {0, 1[ ‏به طوری که‎ ۰ i=1 

صفحه 89:
شما یک کوله پشتی داربد که حجم ‎GUE‏ ‏دارد. همچنین تعدادی وسیله نیز دارید که حجم هر کدام را به شما داده اند. می‌خواهید تعدادی از این وسیله‌ها را در کوله پشتی بریزید به طوری که بیشترین حجم ممکن از کوله پشتی اشغال شود. (فرض کنید شکل وسایل طوری است که فضای بی‌استفاده بین آن‌ها باقی نمی‌ماند.) 

صفحه 90:
فروشنده دوره گرد مسأله فروشنده دوره گرد يا ‎Traveling Salesman‏ ‎Lass! 4 Problem‏ 9۳ ]۰ یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر و تحقیق در عملیات است. سه روش کلی برای کد کردن راه حل های مسأله ۲5۳ ارائه شده است که در الگوریتم های مختلفی قابل استفاده هستند. راه حل های سه گاه عبارتند از: 

صفحه 91:
للف) نملیش جواب به صورت رشته گسسته جایگشتی که در الگوریتم های زیر قلبل استفاده است: الگوریتم های ژنتیک با 5 1 ببه اختصار 64) شبيه سازى تبرید با ۸۳۳۵۵۱۱۳9 51۳0۷۱۵۲60 ببه اختصار ‎(SA‏ ‏جستجوی ممنوعه یا ‎(TS jtas! a) Tabu Search‏ جستجوی همسایگی متغیر یا ‎Variable‏ ‏لاع ندع5 ۱۱6۱9۳۱۳00۲۳۵۵ ببه اختصار ۷۱۱5 بهینه سازی کلونی مورچگان يا ‎Ant Colony‏ 0 ببه اختصار 86:0) جستجوى هارمونى يا 0 ۲۱۵۲۲۲۱۵۲۱۷ ببه اختصار ۳۱5) و سایر الگوریتم های دهینه سازی گسسته 

صفحه 92:
ب) نمایش جواب به صورت کلیدهای تصادفی یا ۷6۷ ۵۲۱00۲۳ که در الگوریتم های زیر قابل استفاده است: الگوریتم های زنتیک يا 606۳6 ۹ 1 ربه اختصار (/3)) بهینه سازی ازدحام ذرات & ‎Particle‏ ‏۴ 5۷۷/۵۲۲۳۳۲ (به اختصار ۳۹0۵) الگوریتم رقابت استعماری با ۸۱90۲۱۲۳۳۲ 0۵۳۵۵611۷6 ۱۳۱۵۵۲۵۱5 «به اختصار 10۸۵) تكامل تفاضلى يا ‎any (DE jla:+! 4) Differential Evolution‏ سازی مبتنی بر جغرافیای زیستی یا 88560 810-9609۲۵۵۷ 0 ر(به اختصار 580 استراتژی های تکاملی یا ‎Evolution Strategies‏ «به اختصار 65) برنامه ریزی تکاملی یا ۳9 0۳03۳۷ ۴۷۵۱۵ «به اختصار ۴۳) و سایر الگوریتم های بهینه سازی پیوسته 

صفحه 93:
پ) نمایش جواب به شکل ماتربس های شبیه فرومون که توسط تمامی الگوریتم های اشاره شده در مورد (ب) قابل استفاده می باشد. 

صفحه 94:
بچیدگی محاسباتی الگوربتم فروشنده دوره گرد لین الگوریتم بطور مستقیم در مرتبه زملنی!60)۳0 حل حی شود لما اگر به روش برنامه نوبسی پهبا برای حل لن استفاده کنیم مرتبه زملنی آن (0 2*27 )0 خواهد شد که جز مرتبه های نملیی است. باید توجه داشت على رغم آنكه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل می باشد . شبه کد الگوربتم فوق بصورت زیر است که در لن تعداد زیر مجموعه های ییک مجموعه ‎1١‏ ‏عضوی ۲ به توان ۲0 می باشد و ۴0۲ اول یک ضریب ‏ را نیز حاصل می شود کهبه ازای تمام شهرهای غیر مبداحی باشد و حاصل (11*)2*۲ را پسید می آورد. بنابرلین برای جستجوی کمترین مقدار نیاز به یک عملیات خطی از مرتبه 9 داریم که در زمان فوق نیز ضرب می شود و در نهایت زمان (۲۱(*)92) را برای اين الگوربتم حاصل می کند. 

صفحه 95:
فرض كنيد نمودار شکل زیر نقشه چهار شهر و ,فاصله بین آنها برحسب کیلومتر باشد 8 30 6 30 ١ 25 ‏م‎ 40 م 

صفحه 96:
فرض کنید یک فروشنده بخواهد از هر شهر تنها یک بار عبور کند که نقطه شروع و پایان شهر باشد. کمترین مسافتی که فروشنده می تواند همه مسیر را بپیماید. کدام است؟ حل مسئله این مساله را می توان با نوشتن همه دورهای همیلتونی ممکن با نقطه شروع و پایان از راس و محاسبه کل مسافت پیموده شده برای هر دور حل کرد. مسير مساقت (کیلوعتر) 125=30430+25+40 140=30435+25+50 155=50+30+35+40 140 155 125 

صفحه 97:
مساله فروشنده دوره گرد یکی از مسائل مشهور بهینه سازی است که بر اساس آن یک فروشنده دوره گرد می خواهد به از شهر رفته و كالاى خود را به فروش برساند » به طورى که تما شهر ها را رفته از هر شهرفقط یک بار عبور كرده و در نهایت کمترین مسیررا طی کرده باشد . فضای حل مساله 75 با زیاد شدن تعداد شهرها به سرعت افزایش می یابد و دیگر با روش های خطی نمی توان جواب بهینه آن را به دست آورد. به همین دلیل است که این مساله جزو گروه مسائل 7 قرار می گیرد. ( مسائل ۱۳-1070 مسائلی هستند که با روش های تحلیلی بسختی و با پیچیدگی حل می شوند.) تعداد کل رامحل‌ها ‎J gly‏ م ۲ 1 دورهاى هميلتونى *' در يك كراف كامل با 8 رأس. با (8-1) 171 براى ‎١‏ <7 كه 8 تعداد شهرها است. در واقع اين عدد 

صفحه 98:
حل سئله فروشندهى دوره كرد با استفاده از الكوريقم بای شببه سازى اين مساله» يك شبكه فرضى بر روى شهر بجنو با ۲۰ اس و ‎٩‏ یال در ظر رفه شده است که تام مسير هأى بين رئوس بصورت خط مستقيم بوده و نمام نقاط داراى مختصات مي بأشند. 

صفحه 99:
۲۰۰-۱ مرکز مهم در داخل شهر بجنورد در نظر کرفته شد ۲- برای این ۲۰ مرکز یک ماتریس هزینه در نظر گرفته می شود ( منظور از هزینه فاصله بین مراکز فاصله ‎ar and gph‏ عمام ‎Sal Ftp‏ .يل تفع 2 ۳- فواصل بین مراکز محاسیه شده و چون هدف پیدا کردن حدا شایستگی ۳ برای هر راه حل کاندد محاسبه می شود . مدظور از تابع شایستگی . تابعی است که پاسخ بهينه را بای حل بره گرد:» تیع شایستگن » مینیمم فاصله طی. شده بین مراک مساله مور مجاینبهرمی کند:: در مس از روش های ذکر شده مان ‎Single-Point‏ , :150-۳08 استفاده نمود زیرا مساله پاسخ ار این مقاله از روش #نرلت۲2 استفاده شده است که این روش بطور خاص برای حل مساله فروشنده دوره گرد با لتفاده از الگوريتم ژنتیک طراحی شده است .در این روش در موحله ال دو وال در نظر گرفته می شود. در ستون اول اين جدول شماره مراكز قرار می گیرد. در ستون هاى بعدى نحوه قراركيرى اين مركز بين ساير مراكز بررسى مى شود. براى نمايش عملكرد اين الكوريتم . * مركز در نظر كرقته شده است. 4 2 5 3 5 1 1 2 4 6 1 3 1 2 6 = 4 Jor why Se Sat ‏امی رود ا‎ tag ej artes Gilles ey goat Lisl glen ‏عال یکی از مراکز بطور کاملا‎ تالت مود 

صفحه 100:
مرحلة أول هن ام | بخ | مر سام امام اتام 

صفحه 101:
مرحله جهارم حلف مقدار اتب شده فله های جدول 

صفحه 102:
مرحله ششم علق مقار تخاب شده i os) نف مر غاب شد se gh aj 

صفحه 103:
۵-. مرحله بعدی » مرحله جپش است . در اين مرحله ۲ مرکز بطور کاملا تصادقی انتخب می شوند و مکان ها در جدول با هم عوض مى شود . إين عمل به اين خاطر انجام مى كيرد كه ممكن است باعث بهبوذ شرايط شده و توايع را سريعتر : همگرا نماد 

صفحه 104:
۶- طرز کار برنامه و الكوريتم نوشته شده ‎face aS at alg go Saal‏ انتخاب»احتمالجهش » اخجبال انبل يجيد ‎ ‏تخاب را مایق حالت مورد نظر خویش وارد ای . با فشرئن دکمه 11/1 برامه اجرا شله و مسیر ب ‎ ‏عامنگذاری شده شير نله می شود ‎ 

صفحه 105:
nif Jet Aaa bate ad ‏اخط‎ JE be sled se las ار دارم در این که در ها ‎cae yep mes gees‏ کید پزمي وه