آشنایی الگوریتم های ژنتیک
اسلاید 1: آشنایی الگوریتم های ژنتیکGenetic Algorithmsدر طبيعت، گونه های زنده، جهت ادامه بقا، مجبورند خود را با شرايط محيطی وفق دهند. اين کار تحت فرآيندی بنام تکامل صورت مي گيرد.
اسلاید 2: irmgn.irتقسیم بندی کلی روشهای حل مسایل بهینه سازیروشهای دقیق (Exact): روشهایی مانند (سیمپلکس، دوگان، شبکه، شاخه و حد، برنامه ریزی پویا، لاگرانژین و...) که دستیابی به حل بهینه را تضمین می کنند. روشهای غیردقیق (No Exact) : روشهایی که در صدد دستیابی به حل های نزدیک به بهینه می باشند ولی دستیابی به حل بهینه را تضمین نمی کنند. رویکردهای ابتکاری مانند Hungarian برای حل مسأله تخصیص یا Johnson برای حل مسأله زمانبندی دو ماشین و یا روشهای فوق ابتکاری برگرفته از مکانیزم های طبیعی متعلق به این دسته می باشند.
اسلاید 3: irmgn.irبهینه سراسری و موضعیxF(x)xGlobalxLocalN(xLocal,)
اسلاید 4: irmgn.irتعریف همسایگی (Neighborhood) : یک همسایگی از جواب شدنی xX مانند N(x,) به مجموعه ای از جواب های شدنی گفته می شود که با اعمال عملگر بروی x قابل دستیابی باشند. عملگر می تواند به معنی حذف، اضافه یا تغییر عناصر موجود در x باشد. به عملگر اصطلاحاً حرکت (Move) نیز گفته می شود. تعریف بهینه موضعی (Local Optimum): هرگاه یک همسایگی مانند N(x,) یافت شود بگونه ای که حل x از هر حل موجود در آن همسایگی بهتر باشد؛ به x اصطلاحاً بهینه موضعی گفته می شود.
اسلاید 5: irmgn.irمفهوم NPnTتعریف NP : عبارت NP مخفف (Non –Deterministic Polynomial) به معنای چندجمله ای نامعین بوده و در بحث پیچیدگی محاسبات مطرح می گردد. عبارت فوق به مسایلی اطلاق می گردد که زمان حل آنها توسط یک الگوریتم دقیق برحسب ابعاد مسأله از نوع یک سری چندجمله ای نامعین مانند سری نمایی باشد. مسایلی همانند TSP، knapsack، Job Shop Scheduling و... جزء مسایل NP می باشند.
اسلاید 6: irmgn.irروش ابتکاریتعریف : یک روش ابتکاری عبارت است از تکنیکی که حل های نزدیک به بهینه را با یک هزینه محاسباتی قابل قبول جستجو می کند. ولی تضمینی برای رسیدن به حل بهینه نمی دهد. توجه به این نکته حائز اهمیت می باشد که در اکثر مدلسازی ها؛ نمی توان کلیه پارامترهای مؤثر بر شرایط مسأله را وارد مدل نمود، لذا تضمینی وجود ندارد که بهترین حل بدست آمده توسط مدل همان حل مطلوب برای شرایط واقعی باشد. حال این سئوال مطرح می باشد که یک حل دقیق از یک مدل تقریبی بهتر می باشد یا یک حل تقریبی از یک مدل دقیق؟ در پاسخ به این سئوال رویکردهای فراابتکاری این امکان را مهیا می سازند که بتوانیم یک حل تقریباً خوب را از یک مدل کاملاً دقیق بدست آوریم چراکه افزایش پیچیدگی مسأله تأثیر چندانی در عملکرد آنها نخواهد داشت.
اسلاید 7: irmgn.irروشهای ابتکاری بر مبنای مکانیزم های طبیعیشبکه های عصبی مصنوعی(Artificial Neural Network) الگوریتم های ژنتیک (Genetic Algorithm) جستجوی ممنوع (Tabu Search)سرد شدن تدریجی (Simulated Annealing)جامعه مورچگان (Ant Colony)
اسلاید 8: irmgn.irمبانی الگوریتم ژنتیک ارگانیسم های طبیعی جهت ادامه بقای خود ناچار به تطبیق هرچه بیشتر با محیط اطراف خود می باشند. - ارگانیسم هایی که نتوانند خود را با محیط و شرايط زيست محيطی که در آن حضور دارند، تطبیق دهند، محکوم به فنا می باشند. - خصوصیات هر ارگانیسم طبیعی در یک رشته بنام کروموزوم کد شده است. - کروموزوم ها خود متشکل از تعدادی اجزاء بنام ژن می باشند بطوریکه هر ژن با توجه به مقدارخود، مبین خصوصيات ارگانیسم مانند اندازه قد؛ وزن، رنگ مو، رنگ پوست، رنگ چشم، نوع رفتار و.... می باشد. به مقادیری که هر ژن می تواند اختیار کند alleles و به موقعيت مکانی ژن درکروموزوم Locus می گویند. - هر موجود زنده در سیر تکامل خود خصوصیات والدینش را نیز به ارث می برد. - نوع گونه زنده (Organism) به ساختارکروموزوم (Genotype or Structure)، مقادیر ژن آن و تأثيرات ناشی از محيط اطراف (Phenotype) بستگی دارد.
اسلاید 9: irmgn.irالگوریتم ژنتیک در يک نگاهالگوریتم ژنتیک اولين بار توسط جان هلند در 1975 مطرح گرديد. اساس الگوریتم ژنتیک، تکامل طبیعی می باشد. الگوریتم ژنتیک بر خلاف ساير رويکردهای فراابتکاری؛ بجای کار بروی يک جواب (کروموزوم) منفرد؛ در هرتکرار بروی جمعيتی از جواب ها کار می کند. به جمعيت (Population) فوق در هر تکرار الگوريتم نسل (Generation) گفته می شود. برای توليد نسل جديد، برخی از جواب ها در نسل فعلی انتخاب می شوند که به آن جمعيت والد (Mating pool) می گويند. کروموزوم های جمعيت والد با استفاده از سه عملگر اساسی ژنتيک بنام های تقاطع (Crossover) و جهش (Mutation) يا حضور مجدد (Reproduction)، فرزندان (Offspring) خود را جهت حضور در نسل بعدی توليد می کنند. عملگر جهش عموماً برای حفظ سطح قابل قبولی از تنوع (Diversity) در جمعيت مورد استفاده قرار مي گيرد. فرازندانی برای حضور در نسل بعدی پذيرفته می شوند که دارای برازندگی (Fitness-Profit-Goodness-Utility) بهتری نسبت به والدين خود باشند. اين امر موجب می گردد که نسل جديد نسبت به نسل قبلی تکامل (Evolution) یابد. با افزايش تکرارالگوريتم، متوسط برازندگی نسل ها بهبود خواهد یافت تا اينکه الگوريتم به ناحيه خاصی از فضای جواب همگرا گردد.
اسلاید 10: irmgn.irهمسانی ذاتی و تئوری الگومفهوم بنيادين هلند برای توسعه تحليل نظری الگوريتم های ژنتيک مفهوم الگو (Schema) می باشد. فرض کنيد يک کروموزوم باينری به طول N مفروض می باشد بطوريکه هر ژن آن فقط مقادیر 0 يا 1 را می تواند داشته باشند. يک الگو به مجموعه ای از کروموزوم های مشابه گفته می شود که در تعداد مشخصی از ژن ها از لحاظ مکان و مقدار همسان باشند. الگو می تواند مبين يک ابرصفحه در فضای N بعدی باشد. شکل زير يک الگو و دو نمونه (Instance) متعلق به آن را نشان می دهد بطوريکه بجای علامت * مقدار 0 يا 1 می تواند قرار گيرد. 0101010در حالت کلی يک کروموزوم باينری بطول N ؛ تعداد 2N نوع الگو دارد. زيرا در هر مکان؛ علامت * يا يک مقدار واقعی می تواند قرار گيرد. با بدست آوردن برازندگی کروموزوم های متعلق به يک الگو می توان اطلاعاتی در مورد برازندگی يک الگو خاص بدست آورد. هدف اصلی يافتن الگوهایی با برازندگی بالاتر می باشد.1001011
اسلاید 11: irmgn.irهمسانی ذاتی و تئوری الگوهلند ثابت کرد که تحت شرايط یکسان؛ پردازش يک جمعيت به اندازه M در يک نسل به معنای پردازش O(M3) الگو می باشد. او همچنين ثابت کرد که با بکار بردن عملگرهای ژنتیکی؛ هرالگوی ارائه شده در نسل فعلی هم ارز با برازندگی نسبی خود؛ مستقل از الگوهای ديگر افزايش يا کاهش خواهد يافت. برای اثبات ادعاهای فوق به تعاریف زير نياز می باشد: 1- طول الگو : فاصله بين اولين و آخرين ژن تعريف شده در الگو. 2- ترتيب الگو: تعداد ژنهای تعريف شده در الگو. 3- نرخ برازندگی الگو : نسبت متوسط برازندگي الگو به متوسط برازندگی جمعيت طول الگو = 4ترتيب الگو = 2
اسلاید 12: irmgn.irتطبیق مفاهيم ژنتیکی با مفاهيم بهينه سازیمفاهيم ژنتيکیمفاهيم بهينه سازیکروموزومجواب شدنی ( يک نقطه از فضای مسأله)نسلجمعيتی از جوابهای شدنیعملگر ژنتيکیتوليدحل همسايهمقدار برازندگیمقدار تابع هدف - مطلوبيتتکاملحرکت بسوی بهينه موضعی
اسلاید 13: irmgn.irشش گام اساسی در طراحی یک الگوریتم ژنتیک جهت مسايل بهينه سازی1- طراحی ساختار کرموزوم یا نحوه نمایش حل مسأله (Representation). 2- استراتژی توليد جمعيت اوليه (Seeding) . 3- استراتژی انتخاب جمعيت والد (Mating Pool) يا مکانيزم انتخاب. 4- طراحی يا انتخاب عملگرهای ژنتيکی متناسب با ساختارکروموزوم و قيود مسأله. (Operators) 5- نحوه محاسبه برازندگي يا کيفيت کروموزوم ها (Fitness). 6- تعيين معيار توقف. (Stop Criteria).
اسلاید 14: irmgn.irطراحی ساختار کرموزوم يا نحوه نمايش حل مسأله ماهيت ساختار کروموزوم بستگی به کيفيت متغير تصميم و قيود مسأله دارد. مواردی همچون پيوسته/گسسته، باينری/غيرباينری بودن متغير تصميم و يا تعداد بعد آن، همچنين نوع ارتباط بين متغيرهای تصميم در قيود مسأله مبنای اصلی طراحی کروموزوم می باشند. به عنوان نمونه؛ در يک مسأله Single Machine با 7 کار و با تابع هدفی از جنس ديرکرد (Tardiness) ، با توجه به اينکه هر توالی ممکن از کارها برای مسأله شدنی می باشد؛ می توان از ساختاری مانند شکل زير برای نمايش حل شدنی يا کرموزوم استفاده کرد. جهت ارضای قيود اساسی مسأله هر ژن فقط يکی از مقادير 1 تا 7 را می تواند اختيار کند. شکل زير يک نقطه از فضای شدنی مسأله يا به عبارت ديگر يک توالی از کارها را نشان می دهد. توالی ( مکان ژن)کار ( مقدار ژن)
اسلاید 15: irmgn.irساختار کرموزوم در مسأله Job Shop با فرض بيکاری عمدیدر حالتی که هدف از جنس کمينه سازی زودکرد نيز باشد استفاده از بيکاری عمدی مدنظر می باشد. برای نمایش کروموزوم در چنين حالتی، می توان علاوه بر سطر مربوط به نمایش توالی کارها، سطر ديگری به کرموزوم جهت نمایش مقدار بيکاری عمدی اضافه کرد. با توجه به نوع مسأله مقادير اين سطر می توانند عدد صحيح يا حقيقی باشند و محدوديتی برای مقادير اين سطر به لحاظ تئوريک وجود ندارد. به عنوان نمونه، مقدار 1 در سطر 2 و مکان [3] به معنای وجود 1واحد بيکاری عمدی قبل از کار 4 می باشد.
اسلاید 16: irmgn.irساختار کرموزوم در مسأله پوشش مجموعه (Set Covering)در مسأله پوشش مجموعه؛ N نقطه تقاضا موجود می باشد که بايد خدمات خاصی به آنها ارايه گردد. در k نقطه فوق، يک مرکز خدمت دهی بصورت بالقوه موجود است. هر نقطه فاقد امکانات جهت استفاده از حداقل یکي از مراکز فوق بايد تا حد معينی بدان نزديک باشد. هدف تإسيس یا استقرار تسهيلات در يک يا چند نقطه فاقد مرکز خدمت دهی می باشد بطوريکه کليه نقاط فاقد امکانات سرويس دهی شده و هزينه تأسيس يا استقرار کمينه گردد. فرض کنيد 7 شهر موجود می باشد که بايد بدانها خدمات آتش نشانی ارائه گردد بطوريکه در شهرهای 2و4 مرکز آتش نشانی وجود دارد. در 5 شهر ديگر می توان بصورت بالفعل مرکز آتش نشانی تأسيس نمود. در نتيجه ساختار کروموزوم را می توان بصورت شکل زير با ژنهای باينری درنظر گرفت بطوريکه مقدار 1 برای ژن i ام به معنای تأسيس مرکز آتش نشانی در شهر i می باشد. طبق فرض شهرهای 2و4 همواره مقدار 1را دارند.
اسلاید 17: irmgn.irساختار کرموزوم در مسأله تشکيل سلول (Cell Formation)هدف از مسأله تشکيل سلول در حالت کلاسيک؛ پردازش تعدادی قطعه توسط برخی انواع ماشين های موردنياز آنها می باشد بگونه ای هزينه نقل و انتقالات مواد و ترافيک درون کارگاه کمينه گردد. اين کار با تشکيل خانواده قطعات و گروه های ماشين انجام می شود. بطوريکه با تخصيص هر خانواده قطعه به يک گروه ماشين، يک سلول پردازشی ایجاد می گردد. با توجه به اينکه هر قطعه نياز به چند نوع پردازش مختلف دارد، لذا احتمالاً به بيش از يک سلول جهت پردازش نياز خواهد داشت. البته با اين فرض اوليه که از هر نوع ماشين فقط يک عدد در دسترس بوده و يا تعدد ماشين ها مجار نباشد. همچنين حداکثر تعداد مجاز سلولها نيز از ابتدا مشخص می باشد. فرض کنيد 7 نوع قطعه و 5 نوع ماشين در دسترس بوده و حداکثر تشکيل 3 سلول مجاز باشد. در اين حالت می توان از يک کروموزوم به طول 5+7 استفاده کرد بطوريکه مقادير ژن برای آن نشان دهنده شماره سلول می باشد. تخصيص قطعه به سلولتخصيص ماشين به سلول
اسلاید 18: irmgn.irاستراتژی توليد جمعيت اوليه (Seeding)جهت توليد جمعيت اوليه عموماً از روش توليد تصادفی کروموزوم ها استفاده می شود. در روش تصادفی از آنجائيکه کروموزوم ها متعلق به نواحی مختلف فضای جواب می باشند لذا تنوع کروموزوم ها بالا است؛ در نتيجه در تکرارهای اوليه الگوريتم؛ تکامل نسل ها سريعتر انجام می گيرد ولی با افزايش تکرار، تشابه کروموزوم ها نيز افزايش يافته تا اينکه در نهايت الگوريتم به يک يا چند حل شاخص همگرا گردد. در برخی از تحقيقات، از تکنيک های ابتکاری يا فراابتکاری ديگر همانند SA يا TS نیز جهت بدست آوردن يک جمعيت اوليه با کيفيت بالا استفاده شده است. اگرچه اشکال عمده روش فوق افزايش احتمال همگرايي زودرس (Premature Convergence) يا کاهش تنوع در جمعيت می باشد.
اسلاید 19: irmgn.irنحوه ايجاد جمعيت اوليهآيا کروموزوم موجه است؟آيا کروموزوم غير تکراري است؟انتخاب يک کروموزوم بصورت تصادفيشروعپايانافزودن اين کروموزوم به جمعيت اوليهآيا تعداد جمعيت اوليه برابر n است؟ تعداد جمعيت اوليه = nخيربلهخيربلهخيربله
اسلاید 20: irmgn.irمکانيزم انتخاب جمعيت والد (Mating Pool)مکانيزم انتخاب تعيين می کند که کدام يک از کروموزوم های نسل فعلی بطور مستقيم يا غيرمستقيم در نسل بعد نيز حضور يابند. شکل زير تقسيم بندی جامعی از مکانيزم های انتخاب که تاکنون ارائه شده است را نشان می دهد. مکانيزمهای انتخابمکانيزمهای تصادفیمکانيزمهای بر مبنای رتبه بندیچرخ رولتی(RWS)ترنمنتترنمنت تصادفینمونه گيری تصادفی جامع(SUS)رتبه بندی سنتیمدلهای نخبهمدلهای ارزش انتظاریمدلهای ارزش انتظاری نخبهSpeciation
اسلاید 21: irmgn.irتعريف فشار انتخاب (Selection Pressure)فشار انتخاب عبارت است از احتمال انتخاب برازندترين اعضای نسل فعلی. فشار انتخاب بالا منجر به يک جستجوی تهاجمی می گردد، بطوريکه باعث بهربرداری از اطلاعاتی می گردد که تاکنون در طول فرآيند جستجو بدست آمده بدون آنکه در صدد کاوش مناطق اکتشاف نشده فضای جواب باشد. فشار انتخاب بالا عموماً موجب همگرايي زودرس ( بهينه موضعی) شده در حاليکه فشار انتخاب پايين ممکن است روند تکامل نسل ها را دچار نقصان سازد.
اسلاید 22: irmgn.ir تشريح برخی از مکانيزم های انتخاب1- انتخاب چرخ رولتی (RWS): در اين روش احتمال انتخاب کروموزوم ها با برازندگی بيشتر بالاتر می باشد. به عبارت ديگر به هر کروموزوم به نسبت برازندگی آن، يک شانس انتخاب داده می شود. در نتيجه ممکن است بعضی از کروموزوم ها چندبار انتخاب شده و يا اصلاً انتخاب نشوند. 2- مدلهای نخبه: در اين روش برازنده ترين اعضای نسل فعلی بايد در نسل بعد حضور يابند. 3- روش ترنمنت (Tournament): در اين روش در هر تکرار يک مجموعه k عضوی از نسل فعلی انتخاب شده و بهترين آنها برای حضور در نسل بعد انتخاب می شوند. به پارامتر k اندازه ترنمنت می گويند. اين کار به تعداد نسل ها تکرار می شود. طبیعی است که با افزايش مقدار k فشار انتخاب نيز افزايش مي یابد. 4-روش رتبه بندی (Ranking): در اين روش اعضای نسل فعلی برحسب درجه برازندگی از بهترين تا بدترين مرتب شده و هر عضو به تعداد دفعات ممکن نسخه برداری می شود. سپس يک رويکرد انتخاب مقتضی اعمال می گردد. اين روش برای مسايل چند هدفی مناسب می باشد.
اسلاید 23: irmgn.irعملگر جهشوالدين3245110110فرزند32451101100
اسلاید 24: irmgn.irعملگر تقاطعی ( Rank X)3245135142Parent 1Parent 20.920.680.540.320.080.860.720.380.220.14123450.460.821.780.761.04
اسلاید 25: irmgn.irعملگر تقاطعی ( Rank X)3245135142Parent 1Parent 20.920.680.540.320.080.860.720.380.220.14123450.460.821.780.761.04Offspring
اسلاید 26: irmgn.irعملگر تقاطعی (تک نقطه ای)0110010010Parent 1Parent 20110010010Offspring 1Offspring 2
اسلاید 27: irmgn.irنمونه ای از تکامل در الگوريتم ژنتيک با جمعيتی برابر با 10 کروموزوم
اسلاید 28: irmgn.irنمای کلی از الگوريتم ژنتيک کلاسيکمقداردهی به پارامترهای اوليه مسأله ( اندازه جمعيت؛ حداکثرتعداد نسل ها؛ نرخ اعمال عملگرها) توليد جمعيت اوليه و محاسبه مقادير برازندگی نسبی هر عضو جمعيتتعيين اعضای والد نسل بعد از جمعيت فعلیاعمال عملگرهای ژنتیکی ( تقاطعی؛ جهش؛ توليد مجدد) بروی جمعيت والد جهت توليد فرزندان جديدپذيرش فرزندان با برازندگی بهتر نسبت به والدين خود و و ايجاد نسل جديدتعداد نسل ها از حداکثر مجاز تجاوز کرده است؟خيربلهتوقف
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.