منبع پایان نامه ارشد درمورد بهینه سازی، طراحی الگو، شبیه سازی

میرسند . تعدادی روشهای تصادفی محاسباتی را برای یافتن احتمال مقادیر متغیرها بهکار می برند که سرعت پایین تری دارند، اما توفیق بیشتری در یافتن بهینهی مطلق دارند .
تک هدفه و چند هدفه: یک مسألهی بهینـه‌سازی تک هدفه، دارای تنها یک تابع هدف می باشد. اما در یک مســألهی چند هدفه، تعداد تابع هدفهایی که بهطور همزمان بهینه میشوند؛ بیش از یکی است. معمولاً در یک مسألهی بهینه‌سازی چند هدفه، با دادن اهمیت (وزن) به هر یک از توابع هدف و جمع بستن آنها، مسأله را تبدیل به یک مسألهی تک هدفه میکنند. حل مسائل بهینه‌سازی چند هدفه، به تنهایی مبحث مستقل و مهمی از حوزه بهینه‌سازی است.
یک بعدی و چند بعدی: اگر تنها یک متغیر وجود دارد، بهینه سازی یک بعدی است . یک مسأله که دارای متغیرهای بیشتر از واحد باشد، نیاز به انجام بهینهسازی چند بعدی است. بدیهی است که هرقدر تعداد متغیرها بیشتر باشد، بهینه سازی مشکل تر است. بهینه سازی چند بعدی عموماً با تقریب زدن به یک سری بهینهسازی یک بعدی انجام می شوند .
3-3-روشهای حل مسائل بهینهسازی
روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتم‌های دقیق43 و الگوریتم‌های تقریبی44 تقسیم‌بندی می‌شوند[39]. الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی ندارند و زمان حل آنها در این مسائل به صورت نمایی افزایش می‌یابد.
روش ریاضی که زیر شاخه ای از این روش است، به دو دسته مبتنی بر مشتق (بردار گرادیان و ماتریـس هسیان تابع هدف) و مبـتنی بر جســتجو (در حقیقت از مشــتق در آن استفاده نمیشود) تقسیم میشود. در این روش اغلب گرادیان تابع هدف مورد استفاده قرار میگیرد. بنابراین، در جایی که تابع دارای عدم پیوستگی باشد دستیابی به این روش عملاً دچار مشکل میگردد. متأسفانه روشهای کلاسیک ریاضی دارای دو اشکال پایهای می باشند؛ نخست اینکه برای هر مسأله بایستی روش حل مخصوص آن بهکار گرفته شود. همچنین، اغلب نقطهی بهینهی محلی بهعنوان نقطهی بهینهی کلی در نظر گرفته میشود. دستهبندی این روش در شکل 3-2 نمایش داده شده است.
شکل 3-3 تقسیم بندی روش محاسباتی.
بر خلاف الگوریتم‌های دقیق، الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. الگوریتم‌های تقریبی نیز به دو دسته الگوریتم‌های ابتکاری45 و فرا ابتکاری46 تقسیم‌بندی می شوند.
در روشهای ابتکاری و فرا ابتکاری بر خلاف روشهای ریاضی، که دارای پایه و اساس ریاضی بوده و همگرایی الگوریتمهای آن اثبات میگردد، ممکن است همگرایی مستندی نداشته باشند. در حل مسایل بهینهسازی اگر تابع هدفی که قرار است نقطهی بهینه آن یافت شود، محدب یا مقعر نباشد (یعنی ماتریس هسیان تابع مذکور نامعین باشد)، در این صورت تقریباً هیچ الگوریتم ریاضی وجود ندارد که تضمین کند جواب بهینه سراسری مسأله همگراست. به این دلیل، همواره بر ایجاد روشهای مؤثرتر و کاراتر تأکید شده است. لذا، در طی 20 سال اخیر نوع جدیدی از الگوریتم تخمینی، با دستیابی به هدفی قابل استفادهتر، با عنوان الگوریتمهای ابتکاری و فرابتکاری، پایهریزی گردیده است. در این روش در زمان محدود، جوابی نزدیک به جواب بهینه بهدست میآید. باید در نظر داشت که اساس این روش جدید بر پایه روش شمارشی بنا نهاده شده است؛ با این تفاوت که از اطلاعات اضافی برای هدایت کردن مسیر جستجو استفاده می‌گردد. دو مشکل اصلی الگوریتم‌های ابتکاری، قرار گرفتن آنها در بهینه‌های محلی و عدم قابلیت آنها برای کاربرد در مسائل مختلف است. الگوریتم‌های فرا ابتکاری یا متاهیوریستیک‌ها برای حل این مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم‌های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای مکانیزم‌های خروج از بهینه محلی می‌باشند و قابل کاربرد در طیف وسیعی از مسائل هستند.
توانایی حل مسائل بسیار پیچیدهتر از قابلیتهای دیگر آن میباشد. به طور عمده این روش‌ها، تصادفی بوده و از طبیعت الهام گرفته شده‌اند. مطالعات نشان داده است الگوریتمهای مبتنی بر رفتار گروهی موجودات زنده در مقایسه با دیگر روشهای بهینه سازی بر روی برخی از مسائل کارایی بهتری دارند به همین دلیل گرایش زیادی برای استفاده از این الگوریتمها وجود دارد. به هر حال، علی رغم وجود کارایی خوب، این روشها هنوز از مشکلات و معایبی رنج می برند که باعث کاهش کارایی آنها در برخی مسائل می شود. همگرایی زودرس، سکون و سرعت همگرایی پایین برخی از مشکلات اصلی این الگوریتم ها است.
فرآیند طراحی و پیاده‌سازی الگوریتم‌های فرا ابتکاری دارای سه مرحله‌ی متوالی است که هر کدام از آن‌ها دارای گام‌های مختلفی هستند[40]. در هر گام فعالیت‌هایی باید انجام شود تا آن گام کامل شود. مرحله‌ی یک آماده‌سازی است که در آن باید شناخت دقیقی از مسأله‌ای که می‌خواهیم حل کنیم بهدست آوریم و اهداف طراحی الگوریتم فرا ابتکاری برای آن باید با توجه به روش‌های حل موجود برای این مسأله، به طور واضح و شفاف مشخص شود. مرحله‌ی بعدی، ساخت نام دارد. مهمترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای اندازه گیری عملکرد و طراحی الگوریتم برای استراتژی حل انتخابی می‌باشد. آخرین مرحله پیاده‌سازی است که در آن تنظیم پارامترها، تحلیل عملکرد و در نهایت تدوین و تهیه گزارش نتایج باید انجام شود.
معیارهای مختلفی برای طبقه‌بندی این الگوریتم‌ها استفاده میشود که در ادامه چند نمونه ذکر میشود:
• مبتنی بر یک جواب و مبتنی بر جمعیت : الگوریتم‌های مبتنی بر یک جواب در حین فرآیند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتم‌های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند. از الگوریتم‌های متداول فراابتکاری مبتنی بر جمعیت می‌توان الگوریتم‌های تکاملی (الگوریتم ژنتیک، برنامه‌ریزی ژنتیک، …)، بهینه‌سازی کلونی مورچگان،کلونی زنبورها، روش بهینه‌سازی ازدحام ذرات و الگوریتم رقابت استعماری و از الگوریتم‌های متداول فراابتکاری مبتنی بر یک جواب می‌توان الگوریتم جستجوی ممنوعه و الگوریتم تبرید شبیه‌سازی شده را نام برد.
• الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم‌های فراابتکاری از طبیعت الهام گرفته شده‌اند. مانند الگوریتم خفاش یا کلونی مورچه ها، در این میان برخی از الگوریتم‌های فراابتکاری نیز از طبیعت الهام گرفته نشدهاند.
• با حافظه و بدون حافظه: برخی از الگوریتم‌های فراابتکاری فاقد حافظه می‌باشند به این معنا که این نوع الگوریتم‌ها از اطلاعات به دست آمده در حین جستجو استفاده نمی کنند (به طور مثال تبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتم‌های فرا ابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند.
• قطعی و احتمالی: یک الگوریتم فرا ابتکاری قطعی نظیر جستجوی ممنوعه، مسآله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتم‌های فرا ابتکاری احتمالی نظیر تبرید شبیه سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.
الگوریتمهای فراابتکاری در حل بسیاری از مسائل بهینه‌سازی در حوزه‌های مختلف کاربرد دارند. در ادامه به طور اجمالی چند نمونه از این الگوریتمها به اختصار معرفی میگردد. پس از آن به تفصیل الگوریتــم خفاش که یک الگوریتم فراابتکاری میباشد و همچنین اساس کار این رساله بر آن بنا گردیده است، مورد بررسی قرار خواهد گرفت.
3-3-1- بهینه سازی تودهی ذرات
بهینه سازی تودهی ذرات به وسیلهی کندی و ابرهارت ارائه شده است [41] . این روش ، از رفتارهای هوشمند پرندگان در یافتن غذا الگو برداری شده است . مانند الگوریتمهای هوش جمعی دیگر، PSO از مجموعهای از جوابهای ممکن استفاده میکند و تا زمانی که از روی این جوابها یک جواب بهینه به دست آید یا معیار خاتمه برآورده شود ، الگوریتم ادامه مییابد. در این الگوریتم هر جواب ممکن به وسیلهی یک ذره نشان داده می شود و یک تودهی ذرات، مجموعهای از ذرات میباشد . مسوولیت تکامل توده به یک ناحیهی بهینه بر عهدهی تساوی سرعت میباشد. این تساوی دربرگیرندهی سه مؤلفه میباشد : مؤلفهی ضریب سرعت ، مؤلفهی فردی ((pi و مؤلفهی اجتماعی (Pg). کل روش را میتوان به صورت یک الگوریتم رفتاری توزیع شده در نظر گرفت که یک جستجوی چند بعدی را انجام میدهد.
در شبیه سازی، رفتار هر ذره به وسیلهی بهترین ذرهی محلی یا بهترین ذرهی سراسری تحت تأثیر قرار میگیرد. یک ویژگی جالب در PSO این است که به ذرات اجازه داده میشود تا از تجربه قبلی خود استفاده کنند . این الگوریتم به طور موفق بر روی بازهی وسیعی از کاربردها اعمال شده است .
ابتدا ، تمامی ذرات به طور تصادفی در فضای جستجو مقدار دهی اولیه میشوند . همچنین موقعیتهای اولیهی pi هر ذره نیز مقدار دهی اولیه میشوند. سپس بهترین ذرهی موجود در توده شناسایی شده و به جواب pg انتساب داده می شود. پس از آن، تودهی ذرات تا زمانی که معیار خاتمه به دست آید، در فضای جستجو پرواز میکند. پرواز، شامل اعمال کردن تساوی سرعت بر روی هر ذره است که سبب میشود موقعیت و برازندگی هر ذره تغییر کند. برازندگی به دست آمده توسط هر ذره با برازندگی به دست آمده از طریق بهترین موقعیت قبلی آن یعنی موقعیت pi مقایسه میشود. اگر موقعیت جدید دارای برازندگی بهتری نسبت به برازندگی بهترین موقعیت قبلی باشد، در این صورت موقعیت جدید جایگزین pi خواهد شد. همچنین، اگر بهترین موقعیت جدید ذرات دارای برازندگی بهتری نسبت به برازندگی بهترین موقعیت توده یعنی موقعیت pg باشد، در این صورت بهترین موقعیت جدید جایگزین pg خواهد شد. الگوریتم PSO دارای ساختار سادهای است و تعداد معدودی پارامتر در آن وجود دارد. الگوریتم حاصل برای محاسبهی موقیت بعدی ذره به صورت زیر بیان می شود :
vt+1= v t+ +1 1 1(pi – xi)+ ) 222 (p g- xi) (3-2)
xt+1= x t+ vt+1
که در آن ثابت های 22و11، توازن بین تأثیر یافتههای اشخاص یا دانش فردی (ه1) و یافتههای کل گروه (یا دانش جمعیه2) (که هر دو در آغاز پیدایش این الگوریتم مقدار 2 میگرفتند) و 2 و11 اعداد تصادفی با توزیع یکنواخت و دارای کران بالای max ، پارامترهای الگوریتم میباشند. توجه نمائید که پرانتزها باعث شتاب ذرات به طرف بهترین یافته های قبلی در فضا می گردند. برای یک فضای n – بعدی، سرعت ذرات در هر بعد محاسبه و سپس در یک بردار نهایی برای به روز کردن وضعیت ذره قرار میگیرند. این تکنیک برای تعدادی از کاربردها و مسائل پایهای مورد استفاده قرار گرفت که در اجرا بسیار جالب عمل میکردند. در واقع، این روشها از تحریک پدیدههای طبیعی و گروه بندی های اجتماعی برای بهینه سازی توابع مختلط که کاربرد وسیعی در صنعت دارند، الهام گرفته شده اند .
3-3-2- الگوریتم جفت گیری زنبور عسل
جفتگیری زنبورهای عسل بهعنوان یک روش عمومی برپایه رفتار حشرات جهت بهینهسازی مورد استفاده قرار میگیرد؛ که در واقع از فرآیند جفتگیری زنبورهای واقعی الهام گرفته است. یک کندو، دارای یک ملکه، صدها زنبور نر و حدود دهها هزار زنبور کارگر میباشد. نقش اصلی ملکه تولید مثل و تخمگذاری میباشد. زنبورهای نر به عنوان پدر کندو ایفای نقش مینمایند. زنبـورهای کارگر وظیفه بچهداری و در برخی موارد تخمگذاری را بر عهده دارند. تخمهای بارور به تولید ملکه و زنبورهای کارگر منجر میشود و در مقابل تخمهای نابارور، زنبورهای نر را تولید میکند.
زمان جفتگیری ملکه

مطلب مرتبط :   مقاله رایگان درموردتقسیم سود، کیفیت گزارشگری، گزارشگری مالی، سیاست تقسیم سود

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