مقالات و پایان نامه ها

– الگوریتم ژنتیک/پایان نامه بهینه سازی شبیه سازی برنامه تولید

دانلود پایان نامه

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

الگوریتم ژنتیک یک تکنیک جستجو برای حل مسائل با استفاده از مدل ژنتیک است. این الگوریتم در زمره الگوریتم‌های مبتنی بر جمعیت قرار دارد که ایده اساسی خود را از نظریه تکامل می‌گیرد. این الگوریتم بر خلاف دو الگوریتم پیشین، در هر تکرار، مجموعه‌ای از جواب‌های مسئله را مورد بررسی قرار می‌دهد. سازوکارها و مجموعه قوانین این الگوریتم برگرفته از مفاهیم علم ژنتیک است.]8[

2-14-5-1- تاریخچه و زمینه پیدایش

چارلز داروین نظریه سیر تکاملی بشر را بیان کرد که بر اساس آن ارگانیسم‌های زیستی در طول نسل‌های مختلف با توجه به اصل “انتخاب طبیعت” و “بقا سازگارترین” تکامل می‌یابند. در سال 1960 ریچنبرگ ایده مطرح شده توسط داروین را در حوزه بهینه‌سازی پارامترها به‌کار گرفت و این ایده را استراتژی تکاملی نامید. این استراتژی شکل اولیه و خام الگوریتم ژنتیک را به‌کار می‌گیرد.]8[

الگوریتم ژنتیک در سال 1975 توسط هالند توسعه داده شد که هدف وی طراحی الگوریتمی برای حل مسائل خاص نبود، بلکه به‌دنبال فهم پدیده سازگاری به نحوی بود که در طبیعت رخ می‌دهد. با انتشار کتاب او با نام “انطباق در سیستم‌های طبیعی و مصنوعی” الگوریتم ژنتیک به دنیای بهینه‌سازی معرفی شد. وی اصول سیر تکامل طبیعی را در مسائل بهینه‌سازی و ساختار الگوریتم ژنتیک توضیح می‌دهد. الگوریتم ژنتیک بر اساس اصول ژنتیک و تکامل بنا شده است که امروزه برای حل مسائل پیچیده بهینه‌سازی مانند جدول زمان‌بندی، تولید کارگاهی و … استفاده می‌شود.]8[

2-14-5-2- خط سیر الگوریتم ژنتیک

همان‌گونه که گفته شد الگوریتم ژنتیک در زمره الگوریتم‌های مبتنی بر جمعیت قرار می‌گیرد. مبتنی بر جمعیت بودن به این مفهوم است که در هر تکرار بیش از یک جواب مدنظر قرار می‌گیرد. اصطلاحاً مجموعه جواب‌های مورد بررسی در هر تکرار، یک جمعیت از جواب‌ها نامیده می‌شود. قوانین و دستورالعمل‌های الگوریتم ژنتیک به گونه‌ای است که جمعیت هر تکرار باعث تعریف و یا ایجاد تکرار آتی می‌شود. گفتنی است که جواب‌های نخستین جمعیت می‌تواند به‌صورت تصادفی از منطقه موجه انتخاب شوند و یا این‌که با روش‌های ابتکاری ایجاد شوند.]8[

- الگوریتم ژنتیک/پایان نامه بهینه سازی شبیه سازی برنامه تولید

در شکل 2-9 جواب‌هایی که با دایره توخالی نشان داده شده‌اند، جمعیت نسل کنونی را تشکیل می‌دهند و دایره‌های خط چین معرف جمعیت نسل آتی هستند. در واقع سازوکار رسیدن به جواب‌های جدید، نوعی شبیه‌سازی از زاد و ولد در فضای منطقه موجه است.

فرزندان حاصل از این زاد و ولد (جواب‌های جدید) ممکن است به جواب‌های بهتر یا بدتر از والدین منجر شود. پذیرش جواب‌های بدتر به‌عنوان جواب‌های نسل جدید به رویکردی بستگی دارد که در پیاده‌سازی الگوریتم ژنتیک مورد استفاده قرار می‌گیرد. در برخی رویکردها تنها جواب‌های بهتر از والدین پذیرفته می‌شوند و در برخی نیز جواب‌های بدتر به جمعیت آتی منتقل می‌شوند. این روند یعنی تولید جمعیت‌های جدید از جمعیت‌های قبلی تا جایی ادامه می‌یابد که شرط توقف الگوریم حاصل شود.]8[

2-15-5-3- مفاهیم و سازوکارهای الگوریتم ژنتیک

الگوریتم ژنتیک از استعاره استفاده می‌کند، به نحوی که یک مسئله بهینه‌سازی در محیطی رخ می‌دهد که جواب‌های ممکن به‌عنوان افرادی هستند که در آن محیط زندگی می‌کنند و برای یافتن بهترین جواب لازم است تا پردازش‌هایی روی این افراد صورت پذیرد. اصطلاحات زیر در این محیط مورد استفاده قرار می‌گیرند:]8[

فرد

به هر یک از جواب‌های مسئله بهینه‌سازی اصطلاحاً یک فرد می‌گوییم. تعیین ساختار هر فرد به مسئله مورد مطالعه بستگی دارد.

کدگذاری

کدگذاری فرآیند نشان دادن جواب‌های مسئله در قالبی قابل استفاده برای الگوریتم ژنتیک است و کدگذاری می‌تواند نقشی اساسی در GA داشته باشد.

تابع برازندگی

برازندگی یک فرد در الگوریتم ژنتیک به معنای میزان ارزش یا کیفیت آن فرد (جواب) با توجه به معیارهای مختلف است که یکی از آن معیارها تابع هدف است. در ساده‌ترین شکل مسائل بهینه‌سازی تابع برازندگی همان تابع هدف است.

جمعیت

جمعیت به مجموعه‌ای از افراد (جواب‌ها) گفته می‌شود. جنبه‌های مهم جمعیت که در الگوریتم ژنتیک استفاده می‌شود، عبارتند از:

  • تولید جمعیت اولیه
  • اندازه جمعیت

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

فرآیند جستجو

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

عملگرها

عملگر اصطلاحی کلی برای سازوکارها یا پردازش‌های صورت گرفته در الگوریتم ژنتیک است که وظایف متنوعی به‌عهده دارند. شکل 2-10 جریان کلی الگوریتم ژنتیک و نقش این عملگرها را در این الگوریتم نشان می‌دهد.]8[

- الگوریتم ژنتیک/پایان نامه بهینه سازی شبیه سازی برنامه تولید

-14-5-4-کاربردهای الگوریتم ژنتیک

کاربرد الگوریتم ژنتیک حوزه وسیعی از مسائل بهینه‌سازی در زمینه‌های مختلف فنی مهندسی، علوم و اجتماعی را در برمی گیرد.]17[

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

تعداد زیادی از پژوهشگران در زمینه الگوریتم ژنتیک در شاخه‌های مختلف پژوهش کرده‌اند که می‌توان به‌صورت زیر ارائه نمود:]17[

  1. برای مسئله سفارش تولید در یک فرآیند مونتاژ از الگوریتم ژنتیک استفاده می‌شود.

سیستم فرآیند مونتاژ مشتمل بر دو زیرسیستم است:

  • اولین زیرسیستم، دستگاهی است که کار آن فراوری مجموعه‌ای از محصولات می‌باشد.
  • دومین زیرسیستم، حمل کننده است که محصولات را حمل‌ونقل می‌کند.
  1. الگوریتم ژنتیک جهت یافتن خط مشی بهینه یا نزدیک به آن برای سیستم‌های بزرگ استفاده شده است و هم‌چنین برای یافتن استراتژی تصمیم‌گیری بهینه یا نزدیک به بهینه در یک سیستم پیچیده بزرگ استفاده گردیده است.
  2. الگوریتم ژنتیک برای برنامه‌ریزی تولید یک شرکت تولیدی چند ملیتی استفاده گردیده است.
  3. الگوریتم ژنتیک برای طراحی جا و مکان مدور سیستم‌های تولیدی استفاده شده است.
  4. الگوریتم ژنتیک برای مسئله انتخاب روبات و تخصیص ایستگاه کاری به‌طور بهینه برای یک سیستم[1] (CIM) به‌کار برده شده است.
  5. الگوریتم ژنتیک برای بالانس خط مونتاژ استفاده شده است. مسئله بالانس خط مونتاژ تعداد ایستگاه‌های کاری و تخصیص بهینه کل عملیات برای هر ایستگاه کاری را معین میکند.
  6. الگوریتم ژنتیک برای بازاریابی توریسم استفاده شده است. با فرض وجود شبکه‌ای از سایت‌های موجود و مجموعه‌ای از سایت‌های ممکن جدید و با فرض پویا بودن شبکه موجود از لحاظ سودآوری، جذابیت برای مشتری بالقوه و دیگر معیارهای مناسب.
  7. الگوریتم ژنتیک برای مسائل “کلمه‌سازی” استفاده می‌شود. به‌طوری که هرگاه کلمات به‌طور تصادفی قرار گرفته باشند و خواسته باشیم کلمه‌ای معنی‌دار را به‌وجود آوریم از قدرت الگوریتم ژنتیک می‌توان برای این مسائل استفاده نمود.
  8. از الگوریتم ژنتیک برای این‌که هزینه طرح کمترین مقدار باشد می‌توان استفاده نمود.
  9. الگوریتم ژنتیک در بهینه‌سازی برنامه جامع توسعه سیستم آب جهت تامین نیازهای آینده استفاده نمود.
  10. از الگوریتم ژنتیک در طراحی خرپا که برای نگه‌داری پل، سقف و یا دیگر قسمت‌های مهندسی استفاده می‌شود، به‌کار رفته است.
  11. برنامه‌ریزی کار در یک کارخانه
  12. مسئله فروشنده دوره گرد
  13. برنامه‌ریزی و بهینه‌سازی قابلیت اعتماد نیز با الگوریتم ژنتیک قابل حل می‌باشد. بسیاری از سیستم‌ها نقش بحرانی در عملیات مختلف دارند و اگر خراب شوند، ممکن است پی‌آمدهایی سخت به‌بار آورند.
  14. طراحی مدل برنامه‌ریزی استراژیک سیستم‌های اطلاعاتی با استفاده از فرآیند تحلیل سلسله مراتبی و الگوریتم ژنتیک قابل حل می‌باشد.
  15. الگوریتم ژنتیک برای برنامه‌ریزی خطوط انتقال نیرو و نصب ژنراتورها مورد استفاده قرار می‌گیرد.
  16. الگوریتم ژنتیک برای مسائل حمل‌ونقل استاندارد، مرکب و هم‌چنین مسائل برنامه‌ریزی چندمعیاره مورد استفاده قرار می‌گیرد.
  17. الگوریتم ژنتیک در جایابی و تعیین ظرفیت بهینه خازن‌های سبک توزیع قدرت به‌منظور کاهش تلفات توان و انرژی و بهبود ولتاژ استفاده گردیده است.
  18. الگوریتم ژنتیک در برنامه‌ریزی قدرت راکتیو، پخش بار اقتصادی، بهینه‌سازی ولتاژ برنامه‌ریزی ژنراتورها و طراحی ترانسفورموتورها استفاده شده است.
  19. الگوریتم ژنتیک در مسائل زمان‌بندی، تولید و جریان کارگاه‌ها، مسئله پوشش مجموعه‌ای استقرار تسهیلات، و برنامه‌ریزی تولید به‌کار رفته است.
  20. الگوریتم ژنتیک در طراحی موتور، ساختن تراشه‌ها و بهینه‌سازی شبکه‌ها با ابعاد بزرگ نیز مورد استفاده قرارگرفته است.
  21. زمان‌بندی کارگاهی
  22. طراحی قرارگیری تجهیزات، مسئله قرارگیری تجهیزات شامل تصمیم‌گیری برای محل قرارگیری تجهیزات و منابع در یک پیکربندی است که منجر به بهترین اجرا یا توجه به ضوابط مشخص می‌شود.

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

[1]. Computer Integrated Manufacturing

دانلود پایان نامه
92