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

ریاضی هستند و یک دستور العمل مشخص را به منظور رسیدن به جواب مسئله طی می نمایند.
روش های ابتکاری۷: در این روش ها در حل مسائل از ابتکار استفاده شده است. هیچ تضمینی در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتایج آنها، به طور متوسط بهترین تقابل کیفیت و زمان حل برای مسئله مورد بررسی را به همراه داشته‌اند مانند روش نیوتن در یافتن ریشه های یک معادله.
روش های فرا ابتکاری۸: برای بهبود الگوریتم‌های ابتکاری از اواسط دهه هفتاد، موج تازه‌ای از رویکردها آغاز گردید. این رویکردها شامل الگوریتم‌هایی است که صریحاً یا به صورت ضمنی، تقابل بین ایجاد تنوع جستجو (وقتی علائمی وجود دارد که جستجو به سمت مناطق بد فضای جستجو می‌رود) و تشدید جستجو (با این هدف که بهترین جواب در منطقه مورد بررسی را پیدا کند) را مدیریت می‌کنند. این الگوریتم ها بر هدایت هیوریستیک یک الگوریتم سازنده یا جستجوی محلی متمرکز می‌شوند به گونه‌ای که آن الگوریتم بتواند بر شرایط حساس (مانند فرار از بهینه محلی) غلبه کند. به این الگوریتم‌ها، فرا ابتکاری گفته می‌شود. از جمله ویژگی های این الگوریتم ها، می توان به موارد زیر اشاره کرد.
وجود خرق عادت: به این معنی که ممکن است در زمان اجرای الگوریتم عملی را خلاف عادت انجام دهیم مثلاً به جای استفاده از بهترین جوابهای موجود برای یافتن جواب های بهتر، از جوابهای نه چندان خوب یا حتی بد استفاده نماییم. یکی از علل انجام این کار می تواند افزایش تصادفی سازی در زمان جستجو باشد.
تصادفی سازی: دیگر ویژگی این روش ها، وجود عنصر تصادفی سازی است. این امر در عدم به دام افتادن در نقطه بهینه محلی تاثیر زیادی دارد. در واقع یکی از علل عدم کارایی روشهای دقیق در یافتن نقاط بهینه سراسری، عدم داشتن عنصر تصادفی سازی است.
منطق کلان: هر چند که این روش ها از عامل تصادفی سازی بهره می برند اما این امر به این معنی نیست که صرفاً روش هایی برای جستجوی تصادفی فضای حل هستند. در واقع در نهان هر یک از این روش ها منطق کلانی مستور است. هر یک از این روش ها از یک واقعیت طبیعی الهام گرفته شده اند.
الهام گرفته از طبیعت: ایده اصلی تمامی روش های فراابتکاری بر گرفته از طبیعت است. این طبیعت است که به پدید آورندگان این روش ها، شیوه مناسب رسیدن به یک جواب بهینه یا نزدیک به بهینه را آموخته است.
در جدول ۲-۱ ویژگی های این روش ها مورد قیاس قرار گرفته است. در این جدول، ۴ عامل دقت، سرعت، منطق جزئی و احتمال به دام افتادن در نقطه بهینه محلی برای روش های دقیق و ابتکاری و فرا ابتکاری مقایسه شده است. برای مثال همان طور که ملاحظه می نمایید روش های دقیق دقت بیشتری نسبت به روش های ابتکاری و روش های ابتکاری دقت بیشتری نسبت به روش های فرا ابتکاری دارند.
جدول ۲-۱ مقایسه روش های دقیق، ابتکاری و فراابتکاری
به دام افتاده در نقطه بهینه محلی
منطق جزئی
سرعت
دقت
روش های حل

دقیق

ابتکاری

فرا ابتکاری

درواقع یکی از ایراداتی که می توان علاوه بر زمان بر بودن به روش های دقیق گرفت، به دام افتادن در بهینه‌های محلی۹ است، بدون اینکه هیچ شانسی برای فرار از آنها داشته باشند. نقطه بهینه محلی نقطه است که تنها در بخشی از فضای جواب مسئله بهینه است. به دام افتادن در نقاط بهینه محلی سبب می شود که الگوریتم از رسیدن به جوابهای سراسری۱۰ که جواب بهینه مسئله در سرتاسر فضای جواب است باز بماند. در شکل ۲ جواب های محلی و سراسری بر روی یک مسئله به نمایش در آمده است.

شکل ۲-۱ نقاط بهینه سراسری و محلی

هیوریستیک‌ها عبارتند از معیارها، روشها یا اصولی برای تصمیم‌گیری بین چندین خط‌مشی و انتخاب اثربخش‌ترین آن‌ها برای دستیابی به اهداف موردنظر. هیوریستیک‌ها نتیجه برقراری اعتدال بین دو نیاز هستند: نیاز به ساخت معیارهای ساده و همزمان توانایی تمایز درست بین انتخاب‌های خوب و بد. یک هیوریستیک می‌تواند حسابی سرانگشتی باشد که برای هدایت یک دسته از اقدامات به کار می‌رود. برای مثال، یک روش مشهور برای انتخاب طالبی رسیده عبارتست از فشار دادن محل اتصال به ریشه از یک طالبی نامزد و سپس بو کردن آن محل. اگر بوی آن محل مانند بوی داخل طالبی باشد آن طالبی به احتمال زیاد رسیده است. این قاعده سرانگشتی نه تضمین می‌کند که طالبی‌های رسیده به عنوان نامزد انتخاب شوند و نه تضمین می‌کند که طالبی‌های رسیده آزمایش‌شده، رسیده تشخیص داده شوند. اما به هر حال این روش، اثربخش‌ترین روش شناخته شده است. به عنوان مثالی دیگر از استفاده هیوریستیک‌ها ، یک استاد بزرگ شطرنج را در نظر بگیرید که با انتخاب بین چندین حرکت ممکن روبرو شده است. وی ممکن است تصمیم بگیرد که یک حرکت خاص، اثربخش‌ترین حرکت خواهد بود زیرا موقعیتی فراهم می‌آورد که به نظر می‌رسد بهتر از موقعیت‌های حاصل از حرکت‌های دیگر باشد. به کارگیری این معیار به نظر می‌رسد خیلی ساده‌تر از تعیین دقیق حرکت یا حرکاتی خواهد بود که حریف را مجبور به مات شدن کند. این واقعیت که اساتید بزرگ شطرنج همواره پیروز بازی نخواهند بود نشان دهنده این است که هیوریستیک‌های آنها انتخاب اثربخش‌ترین حرکت را تضمین نمی‌کند. نهایتاً وقتی از آنها خواسته می‌شود که هیوریستیک خود را تشریح نمایند آنها فقط توصیفی ناقص از مجموعه‌ای قواعد ارائه می‌دهند و به نظر خود آنها، انجام آن قواعد از توصیف آن ساده‌تر است.
خاصیت هیوریستیک‌های خوب این است که ابزار ساده‌ای برای تشخیص خط‌مشی‌های بهتر ارائه دهند و در حالی که به صورت شرط لازم، تشخیص خط‌مشی‌های اثربخش را تضمین نمی‌کنند اما اغلب به صورت شرط کافی این تضمین را فراهم می آورند. بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت‌های ممکن برای تعیین یک جواب دقیق می‌باشند. گاهی زمان لازم برای یافتن یک جواب دقیق اغلب بیشتر از طول عمر یک انسان است. هیوریستیک‌ها با استفاده از روش‌هایی که نیازمند ارزیابی‌های کمتر هستند، جوابهایی در محدودیت‌های زمانی قابل قبول ارایه می‌نمایند که دارای نقشی اثربخش در حل چنین مسائلی است.
از بین الگوریتم‌های فرا ابتکاری می‌توان به موارد زیر اشاره کرد:
شبیه‌سازی تبرید Simulated Annealing (SA)
جستجوی ممنوع Tabu Search (TS)
الگوریتم‌های ژنتیک Genetic Algorithms (GA)
شبکه‌های عصبی مصنوعی Neural Networks (ANN) Artificial
الگوریتم مورچگان) Ant Colony Optimization (ACO

۲-۶ الگوریتم ژنتیک
۲۹ ۲-۶-۱ تاریخچه
از سال ۱۹۶۰ تقلید از موجودات زنده برای استفاده در الگوریتم های قدرتمند جهت مسائل مشکل بهینه سازی مورد توجه قرار گرفت که تکنیک های محاسبه تکاملی نام گرفتند اصول بنیادی الگوریتم ژنتیک اولین بار توسط جان هالند در سال ۱۹۷۵ در دانشگاه میشیگان ضمن درسی که با عنوان نظریه سیستم های تطبیقی ارائه می داد ابداع گردید.
روش های بهینه سازی الهام گرفته از طبیعت با روش های متعارف بهینه سازی تفاوت مهمی دارند در روش های متعارف هر کاندیدای جدید در صورتی به عنوان جواب بهینه انتخاب می شود که مقدار تابع هدف را بهبود بخشد ، ولی در الگوریتم های الهام گرفته از طبیعت به تمام کاندیداهای جدید شانس انتخاب داده می شود.
الگوریتم ژنتیک یکی از مهم ترین الگوریتم های ابتکاری می باشد که از آن برای بهینه سازی جهت توابع تعریف شده روی دامنه محدود استفاده می شود [۱۷]. در این الگوریتم اطلاعات گذشته با توجه به موروثی بودن الگوریتم استخراج شده و در روند جستجو مورد استفاده قرار می گیرد مفاهیم الگوریتم ژنتیک در سال ۱۹۸۹ توسط گلبرگ توسعه داده شد [۱۵].
چه وقت از الگوریتم ژنتیک استفاده کنیم؟
سوالی که در اینجا ممکن است مطرح شود آن است که چه زمانی از الگوریتم ژنتیک استفاده نماییم. به طور خلاصه GA در موارد زیر به کار می رود.
۱. جواب ها بیش از اندازه پیچیده یا بی تحرک باشند.
۲. فضای جواب گسترده باشد.
۳. منطق معینی برای پیدا کردن جواب های جدید وجود نداشته باشد. به عبارت دیگر روش به دست آوردن جواب های جدید را ندانیم.
۴. بخواهیم جواب های موجود را با هم پیوند بزنیم.
۵. مسئله شبیه مسائلی باشد که تاکنون با GA حل شده است.

۳۰ ۲-۶-۲ کاربرد های الگوریتم ژنتیک
یکی از مهمترین کاربرد های الگورتیم ژنتیک بهینه سازی توابع می باشد همان طور که می دانیم اکثر روش های قطعی دارای این اشکال عمده می باشد که به محض رسیدن به اولین نقطه بهینه موضعی متوقف شده و توانایی خروج از این نقطه و حرکت بسوی نقطه بهینه مطلق را ندارند . برای رفع این اشکال و نیز امکان حل مسائل پیچیده تر ، محققان بر روی الگوریتم هایی که بتوانند از نقاط موضعی عبور کنند ، شروع بکار کرده و تاکنون روش های متفاوتی را ارئه و مورد بررسی قرار داده اند ، در این میان الگوریتم های تصادفی به علت اینکه دارای عملکرد ساده تری هستند و به علاوه برای شکل تابع هدف نیز محدودیتی قائل نمی شوند و در نتیجه از راحتی اجرا به کمک کامپیوتر نیز برخوردار هستندمورد توجه بیشتر قرار گرفتند (لوکس ، مهدوری) از میان این الگوریتم ها، الگوریتم ژنتیک کارایی نسبتاً بالاتری نسبت به سایرین در حل مسائل بهینه سازی مشکل ، گسته ، چند کوهانه و پیچیده داشته است [۱۷].
از دیگر کاربرد های الگوریتم ژنتیک در مساله یادگیری شبکه های عصبی می باشد روش یادگیری شبکه های عصبی با استفاده از الگوریتم ژنتیک یک روش یادیگری همراه با نظارت می باشد.
در حل مسائل بهینه سازی ترکیبی همانند مساله فروشنده دوره گرد ،‌از این الگوریتم می توان استفاده نمود از دیگر مسائلی که در صنعت کاربرد های فراوان دارد و بطور گسترده مورد مطالعه قرار می گیرد مساله کوله پشتی است این مساله عبارت است از تعیین چگونگی جا دادن تعدادی شیء در یک فضا محدود که توسط الگوریتم ژنتیک قابل حل می باشد . از این روش در حل مسائل زمانبندی کار در کارگاها یا جدول زمان بندی کار در کارگاها یا جدوب زمانبندی همچنین مسائل یادیگری ماشین ، فرایند پردازش تصویر ، تعیین تواتر بهینه بازرسی در سیستم های نگهداری و تعمیرات پیشگیرانه ، مسائل طراحی و… استفاده شده است [۸].
۳۱ ۲-۶-۳ مزایای بکارگیری الگوریتم ژنتیک
مزایای بکارگیری این روش نسبت به سایر روش های جستجو و بهینه سازی متداول به شرح ذیل بیان می گردد.
الگوریتم ژنتیک با مجموعه ای از جواب های کد گذاری شده کار می کند نه با خود آنها
الگوریتم ژنتیک از خود تابع و مقادیر ان جهت بهینه سازی استفاده می کند بجای استفاده از مشتقات تابع و سایر مقادیر کمکی
منطق ژنتیک تنها از خود

دسته‌ها: No category

دیدگاهتان را بنویسید