بخشی از پاورپوینت

اسلاید 1 :

آشنایی الگوریتم های ژنتیک
Genetic Algorithms

در طبيعت، گونه های زنده، جهت ادامه بقا، مجبورند خود را با شرايط محيطی وفق دهند. اين کار تحت فرآيندی بنام تکامل صورت مي گيرد.

اسلاید 2 :

تقسیم بندی کلی روشهای حل مسایل بهینه سازی
روشهای دقیق (Exact): روشهایی مانند (سیمپلکس، دوگان، شبکه، شاخه و حد، برنامه ریزی پویا، لاگرانژین و.) که دستیابی به حل بهینه را تضمین می کنند.

روشهای غیردقیق (No Exact) : روشهایی که در صدد دستیابی به حل های نزدیک به بهینه می باشند ولی دستیابی به حل بهینه را تضمین نمی کنند. رویکردهای ابتکاری مانند Hungarian برای حل مسأله تخصیص یا Johnson برای حل مسأله زمانبندی دو ماشین و یا روشهای فوق ابتکاری برگرفته از مکانیزم های طبیعی متعلق به این دسته می باشند.

اسلاید 3 :

بهینه سراسری و موضعی
F(x)
xGlobal
xLocal
N(xLocal,)

اسلاید 4 :

تعریف همسایگی (Neighborhood) : یک همسایگی از جواب شدنی xX مانند N(x,) به مجموعه ای از جواب های شدنی گفته می شود که با اعمال عملگر  بروی x قابل دستیابی باشند. عملگر  می تواند به معنی حذف، اضافه یا تغییر عناصر موجود در x باشد. به عملگر  اصطلاحاً حرکت (Move) نیز گفته می شود.
تعریف بهینه موضعی (Local Optimum): هرگاه یک همسایگی مانند N(x,) یافت شود بگونه ای که حل x از هر حل موجود در آن همسایگی بهتر باشد؛ به x اصطلاحاً بهینه موضعی گفته می شود.

اسلاید 5 :

مفهوم NP
تعریف NP : عبارت NP مخفف (Non –Deterministic Polynomial) به معنای چندجمله ای نامعین بوده و در بحث پیچیدگی محاسبات مطرح می گردد. عبارت فوق به مسایلی اطلاق می گردد که زمان حل آنها توسط یک الگوریتم دقیق برحسب ابعاد مسأله از نوع یک سری چندجمله ای نامعین مانند سری نمایی باشد. مسایلی همانند TSP، knapsack، Job Shop Scheduling و. جزء مسایل NP می باشند.

اسلاید 6 :

روش ابتکاری
تعریف : یک روش ابتکاری عبارت است از تکنیکی که حل های نزدیک به بهینه را با یک هزینه محاسباتی قابل قبول جستجو می کند. ولی تضمینی برای رسیدن به حل بهینه نمی دهد.

توجه به این نکته حائز اهمیت می باشد که در اکثر مدلسازی ها؛ نمی توان کلیه پارامترهای مؤثر بر شرایط مسأله را وارد مدل نمود، لذا تضمینی وجود ندارد که بهترین حل بدست آمده توسط مدل همان حل مطلوب برای شرایط واقعی باشد. حال این سئوال مطرح می باشد که یک حل دقیق از یک مدل تقریبی بهتر می باشد یا یک حل تقریبی از یک مدل دقیق؟ در پاسخ به این سئوال رویکردهای فراابتکاری این امکان را مهیا می سازند که بتوانیم یک حل تقریباً خوب را از یک مدل کاملاً دقیق بدست آوریم چراکه افزایش پیچیدگی مسأله تأثیر چندانی در عملکرد آنها نخواهد داشت.

اسلاید 7 :

روشهای ابتکاری بر مبنای مکانیزم های طبیعی
شبکه های عصبی مصنوعی(Artificial Neural Network)
الگوریتم های ژنتیک (Genetic Algorithm)
جستجوی ممنوع (Tabu Search)
سرد شدن تدریجی (Simulated Annealing)
جامعه مورچگان (Ant Colony)

اسلاید 8 :

مبانی الگوریتم ژنتیک
ارگانیسم های طبیعی جهت ادامه بقای خود ناچار به تطبیق هرچه بیشتر با محیط اطراف خود می باشند. 

- ارگانیسم هایی که نتوانند خود را با محیط و شرايط زيست محيطی که در آن حضور دارند، تطبیق دهند، محکوم به فنا می باشند.

- خصوصیات هر ارگانیسم طبیعی در یک رشته بنام کروموزوم کد شده است.

- کروموزوم ها خود متشکل از تعدادی اجزاء بنام ژن می باشند بطوریکه هر ژن با توجه به مقدارخود، مبین خصوصيات ارگانیسم مانند اندازه قد؛ وزن، رنگ مو، رنگ پوست، رنگ چشم، نوع رفتار و.. می باشد. به مقادیری که هر ژن می تواند اختیار کند alleles و به موقعيت مکانی ژن درکروموزوم Locus می گویند.

- هر موجود زنده در سیر تکامل خود خصوصیات والدینش را نیز به ارث می برد.

- نوع گونه زنده (Organism) به ساختارکروموزوم (Genotype or Structure)، مقادیر ژن آن و تأثيرات ناشی از محيط اطراف (Phenotype) بستگی دارد.

اسلاید 9 :

الگوریتم ژنتیک در يک نگاه
الگوریتم ژنتیک اولين بار توسط جان هلند در 1975 مطرح گرديد. اساس الگوریتم ژنتیک، تکامل طبیعی می باشد. الگوریتم ژنتیک بر خلاف ساير رويکردهای فراابتکاری؛ بجای کار بروی يک جواب (کروموزوم) منفرد؛ در هرتکرار بروی جمعيتی از جواب ها کار می کند. به جمعيت (Population) فوق در هر تکرار الگوريتم نسل (Generation) گفته می شود. برای توليد نسل جديد، برخی از جواب ها در نسل فعلی انتخاب می شوند که به آن جمعيت والد (Mating pool) می گويند. کروموزوم های جمعيت والد با استفاده از سه عملگر اساسی ژنتيک بنام های تقاطع (Crossover) و جهش (Mutation) يا حضور مجدد (Reproduction)، فرزندان (Offspring) خود را جهت حضور در نسل بعدی توليد می کنند.

عملگر جهش عموماً برای حفظ سطح قابل قبولی از تنوع (Diversity) در جمعيت مورد استفاده قرار مي گيرد. فرازندانی برای حضور در نسل بعدی پذيرفته می شوند که دارای برازندگی (Fitness-Profit-Goodness-Utility) بهتری نسبت به والدين خود باشند. اين امر موجب می گردد که نسل جديد نسبت به نسل قبلی تکامل (Evolution) یابد. با افزايش تکرارالگوريتم، متوسط برازندگی نسل ها بهبود خواهد یافت تا اينکه الگوريتم به ناحيه خاصی از فضای جواب همگرا گردد.

اسلاید 10 :

همسانی ذاتی و تئوری الگو
مفهوم بنيادين هلند برای توسعه تحليل نظری الگوريتم های ژنتيک مفهوم الگو (Schema) می باشد. فرض کنيد يک کروموزوم باينری به طول N مفروض می باشد بطوريکه هر ژن آن فقط مقادیر 0 يا 1 را می تواند داشته باشند. يک الگو به مجموعه ای از کروموزوم های مشابه گفته می شود که در تعداد مشخصی از ژن ها از لحاظ مکان و مقدار همسان باشند. الگو می تواند مبين يک ابرصفحه در فضای N بعدی باشد. شکل زير يک الگو و دو نمونه (Instance) متعلق به آن را نشان می دهد بطوريکه بجای علامت * مقدار 0 يا 1 می تواند قرار گيرد.
در حالت کلی يک کروموزوم باينری بطول N ؛ تعداد 2N نوع الگو دارد. زيرا در هر مکان؛ علامت * يا يک مقدار واقعی می تواند قرار گيرد. با بدست آوردن برازندگی کروموزوم های متعلق به يک الگو می توان اطلاعاتی در مورد برازندگی يک الگو خاص بدست آورد. هدف اصلی يافتن الگوهایی با برازندگی بالاتر می باشد.

اسلاید 11 :

همسانی ذاتی و تئوری الگو
هلند ثابت کرد که تحت شرايط یکسان؛ پردازش يک جمعيت به اندازه M در يک نسل به معنای پردازش O(M3) الگو می باشد. او همچنين ثابت کرد که با بکار بردن عملگرهای ژنتیکی؛ هرالگوی ارائه شده در نسل فعلی هم ارز با برازندگی نسبی خود؛ مستقل از الگوهای ديگر افزايش يا کاهش خواهد يافت. برای اثبات ادعاهای فوق به تعاریف زير نياز می باشد: 

1- طول الگو : فاصله بين اولين و آخرين ژن تعريف شده در الگو.

2- ترتيب الگو: تعداد ژنهای تعريف شده در الگو.

3- نرخ برازندگی الگو : نسبت متوسط برازندگي الگو به متوسط برازندگی جمعيت

طول الگو = 4
ترتيب الگو = 2

اسلاید 12 :

تطبیق مفاهيم ژنتیکی با مفاهيم بهينه سازی

اسلاید 13 :

شش گام اساسی در طراحی یک الگوریتم ژنتیک جهت مسايل بهينه سازی
1- طراحی ساختار کرموزوم یا نحوه نمایش حل مسأله (Representation).

2- استراتژی توليد جمعيت اوليه (Seeding) .

3- استراتژی انتخاب جمعيت والد (Mating Pool) يا مکانيزم انتخاب.

4- طراحی يا انتخاب عملگرهای ژنتيکی متناسب با ساختارکروموزوم و قيود مسأله. (Operators)

5- نحوه محاسبه برازندگي يا کيفيت کروموزوم ها (Fitness).

6- تعيين معيار توقف. (Stop Criteria).

اسلاید 14 :

طراحی ساختار کرموزوم يا نحوه نمايش حل مسأله
ماهيت ساختار کروموزوم بستگی به کيفيت متغير تصميم و قيود مسأله دارد. مواردی همچون پيوسته/گسسته، باينری/غيرباينری بودن متغير تصميم و يا تعداد بعد آن، همچنين نوع ارتباط بين متغيرهای تصميم در قيود مسأله مبنای اصلی طراحی کروموزوم می باشند. به عنوان نمونه؛ در يک مسأله Single Machine با 7 کار و با تابع هدفی از جنس ديرکرد (Tardiness) ، با توجه به اينکه هر توالی ممکن از کارها برای مسأله شدنی می باشد؛ می توان از ساختاری مانند شکل زير برای نمايش حل شدنی يا کرموزوم استفاده کرد. جهت ارضای قيود اساسی مسأله هر ژن فقط يکی از مقادير 1 تا 7 را می تواند اختيار کند. شکل زير يک نقطه از فضای شدنی مسأله يا به عبارت ديگر يک توالی از کارها را نشان می دهد.
توالی ( مکان ژن)
کار ( مقدار ژن)

اسلاید 15 :

ساختار کرموزوم در مسأله Job Shop با فرض بيکاری عمدی
در حالتی که هدف از جنس کمينه سازی زودکرد نيز باشد استفاده از بيکاری عمدی مدنظر می باشد. برای نمایش کروموزوم در چنين حالتی، می توان علاوه بر سطر مربوط به نمایش توالی کارها، سطر ديگری به کرموزوم جهت نمایش مقدار بيکاری عمدی اضافه کرد. با توجه به نوع مسأله مقادير اين سطر می توانند عدد صحيح يا حقيقی باشند و محدوديتی برای مقادير اين سطر به لحاظ تئوريک وجود ندارد. به عنوان نمونه، مقدار 1 در سطر 2 و مکان [3] به معنای وجود 1واحد بيکاری عمدی قبل از کار 4 می باشد.

اسلاید 16 :

ساختار کرموزوم در مسأله پوشش مجموعه (Set Covering)
در مسأله پوشش مجموعه؛ N نقطه تقاضا موجود می باشد که بايد خدمات خاصی به آنها ارايه گردد. در k نقطه فوق، يک مرکز خدمت دهی بصورت بالقوه موجود است. هر نقطه فاقد امکانات جهت استفاده از حداقل یکي از مراکز فوق بايد تا حد معينی بدان نزديک باشد. هدف تإسيس یا استقرار تسهيلات در يک يا چند نقطه فاقد مرکز خدمت دهی می باشد بطوريکه کليه نقاط فاقد امکانات سرويس دهی شده و هزينه تأسيس يا استقرار کمينه گردد. فرض کنيد 7 شهر موجود می باشد که بايد بدانها خدمات آتش نشانی ارائه گردد بطوريکه در شهرهای 2و4 مرکز آتش نشانی وجود دارد. در 5 شهر ديگر می توان بصورت بالفعل مرکز آتش نشانی تأسيس نمود. در نتيجه ساختار کروموزوم را می توان بصورت شکل زير با ژنهای باينری درنظر گرفت بطوريکه مقدار 1 برای ژن i ام به معنای تأسيس مرکز آتش نشانی در شهر i می باشد. طبق فرض شهرهای 2و4 همواره مقدار 1را دارند.

اسلاید 17 :

ساختار کرموزوم در مسأله تشکيل سلول (Cell Formation)
هدف از مسأله تشکيل سلول در حالت کلاسيک؛ پردازش تعدادی قطعه توسط برخی انواع ماشين های موردنياز آنها می باشد بگونه ای هزينه نقل و انتقالات مواد و ترافيک درون کارگاه کمينه گردد. اين کار با تشکيل خانواده قطعات و گروه های ماشين انجام می شود. بطوريکه با تخصيص هر خانواده قطعه به يک گروه ماشين، يک سلول پردازشی ایجاد می گردد. با توجه به اينکه هر قطعه نياز به چند نوع پردازش مختلف دارد، لذا احتمالاً به بيش از يک سلول جهت پردازش نياز خواهد داشت. البته با اين فرض اوليه که از هر نوع ماشين فقط يک عدد در دسترس بوده و يا تعدد ماشين ها مجار نباشد. همچنين حداکثر تعداد مجاز سلولها نيز از ابتدا مشخص می باشد. فرض کنيد 7 نوع قطعه و 5 نوع ماشين در دسترس بوده و حداکثر تشکيل 3 سلول مجاز باشد. در اين حالت می توان از يک کروموزوم به طول 5+7 استفاده کرد بطوريکه مقادير ژن برای آن نشان دهنده شماره سلول می باشد.
تخصيص قطعه به سلول
تخصيص ماشين به سلول

اسلاید 18 :

استراتژی توليد جمعيت اوليه (Seeding)
جهت توليد جمعيت اوليه عموماً از روش توليد تصادفی کروموزوم ها استفاده می شود. در روش تصادفی از آنجائيکه کروموزوم ها متعلق به نواحی مختلف فضای جواب می باشند لذا تنوع کروموزوم ها بالا است؛ در نتيجه در تکرارهای اوليه الگوريتم؛ تکامل نسل ها سريعتر انجام می گيرد ولی با افزايش تکرار، تشابه کروموزوم ها نيز افزايش يافته تا اينکه در نهايت الگوريتم به يک يا چند حل شاخص همگرا گردد. در برخی از تحقيقات، از تکنيک های ابتکاری يا فراابتکاری ديگر همانند SA يا TS نیز جهت بدست آوردن يک جمعيت اوليه با کيفيت بالا استفاده شده است. اگرچه اشکال عمده روش فوق افزايش احتمال همگرايي زودرس (Premature Convergence) يا کاهش تنوع در جمعيت می باشد.

اسلاید 19 :

نحوه ايجاد جمعيت اوليه
آيا کروموزوم موجه است؟
آيا کروموزوم غير تکراري است؟
انتخاب يک کروموزوم بصورت تصادفي
شروع
پايان
افزودن اين کروموزوم به جمعيت اوليه
آيا تعداد جمعيت اوليه برابر n است؟
تعداد جمعيت اوليه = n

اسلاید 20 :

مکانيزم انتخاب جمعيت والد (Mating Pool)
مکانيزم انتخاب تعيين می کند که کدام يک از کروموزوم های نسل فعلی بطور مستقيم يا غيرمستقيم در نسل بعد نيز حضور يابند. شکل زير تقسيم بندی جامعی از مکانيزم های انتخاب که تاکنون ارائه شده است را نشان می دهد.
مکانيزمهای انتخاب
مکانيزمهای تصادفی
مکانيزمهای بر مبنای رتبه بندی
چرخ رولتی
(RWS)
ترنمنت
ترنمنت
تصادفی
نمونه گيری
تصادفی جامع
(SUS)
رتبه بندی
سنتی
مدلهای
نخبه
مدلهای ارزش
انتظاری
مدلهای ارزش
انتظاری نخبه
Speciation

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید