k = 1,2,3,…,n
که در آن X={ بردار طراحی و رابطه‌های (۳٫۱) به ترتیب محدودیت‌های نامساوی، مساوی و محدوده قابل قبول برای متغیرهای طراحی می‌باشند.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

۳-۳- بررسی روش‌های جستجو و بهینه‌سازی
پیشرفت کامپیوتر در طی پنجاه سال گذشته باعث توسعه روش‌های بهینه‌سازی شده، به طوری که دستورهای متعددی در طی این دوره تدوین شده است. در این بخش، مروری بر روش‌های مختلف بهینه‌سازی ارائه می‌شود.
شکل ۳-۱ روش‌های بهینه‌سازی را در چهار دسته وسیع دسته‌بندی می‌کند. در ادامه بحث، هر دسته از این روش‌ها مورد بررسی قرار می‌گیرند.
شکل ۳-۱ طبقه‌بندی انواع روش‌های بهینه‌سازی
۳-۳-۱- روش‌های شمارشی
در روش‌های شمارشی^[۳۸]، در هر تکرار فقط یک نقطه متعلق به فضای دامنه تابع هدف بررسی می‌شود. این روش‌ها برای پیاده‌سازی، ساده‌تر از روش‌های دیگر می‌باشند؛ اما به محاسبات قابل توجهی نیاز دارند. در این روش‌ها سازوکاری برای کاستن دامنه جستجو وجود ندارد و دامنه فضای جستجو شده با این روش خیلی بزرگ است. برنامه‌ریزی پویا^[۳۹] مثال خوبی از روش‌های شمارشی می‌باشد. این روش کاملاً غیرهوشمند است و به همین دلیل امروزه به ندرت به تنهایی مورد استفاده قرار می‌گیرد.
۳-۳-۲- روش‌های محاسباتی
این روش‌ها از مجموعه شرایط لازم و کافی که در جواب مسأله بهینه‌سازی صدق می‌کند، استفاده می‌کنند. وجود یا عدم وجود محدودیت‌های بهینه‌سازی در این روش‌ها نقش اساسی دارد. به همین علت، این روش‌ها به دو دسته روش‌های با محدودیت و بی‌محدودیت تقسیم می‌شوند.
روش‌های بهینه‌سازی بی‌محدودیت با توجه به تعداد متغیرها شامل بهینه‌سازی توابع یک متغیره و چند متغیره می‌باشند.
روش‌های بهینه‌سازی توابع یک متغیره، به سه دسته روش‌های مرتبه صفر، مرتبه اول و مرتبه دوم تقسیم می‌شوند. روش‌های مرتبه صفر فقط به محاسبه تابع هدف در نقاط مختلف نیاز دارد؛ اما روش‌های مرتبه اول از تابع هدف و مشتق آن و روش‌های مرتبه دوم از تابع هدف و مشتق اول و دوم آن استفاده می‌کنند. در بهینه‌سازی توابع چند متغیره که کاربرد بسیار زیادی در مسائل مهندسی دارد، کمینه‌سازی یا بیشینه‌سازی یک کمیت با مقدار زیادی متغیر طراحی صورت می‌گیرد.
یک تقسیم‌بندی، روش‌های بهینه‌سازی با محدودیت را به سه دسته برنامه‌ریزی خطی، روش‌های مستقیم و غیرمستقیم تقسیم می‌کند. مسائل با محدودیت که توابع هدف و محدودیت‌های آنها خطی باشند، جزو مسائل برنامه‌ریزی خطی قرار می‌گیرند. برنامه‌ریزی خطی شاخه‌ای از برنامه‌ریزی ریاضی است و کاربردهای فیزیکی، صنعتی و تجاری بسیاری دارد.
در روش‌های مستقیم، نقطه بهینه به طور مستقیم جستجو شده و از روش‌های بهینه‌یابی بی‌محدودیت استفاده نمی‌شود. هدف اصلی روش‌های غیرمستقیم استفاده از الگوریتم‌های بهینه‌سازی بی‌محدودیت برای حل عمومی مسائل بهینه‌سازی با محدودیت می‌باشد.
در اکثر روش‌های محاسباتی بهینه‌یابی، از گرادیان تابع هدف برای هدایت جستجو استفاده می‌شود. اگر مثلاً به علت ناپیوستگی تابع هدف، مشتق آن قابل محاسبه نباشد، این روش‌ها اغلب با مشکل روبه‌رو می‌شوند.
۳-۳-۳- روش‌های ابتکاری و فرا ابتکاری (جستجوی تصادفی)
یک روش ناشیانه برای حل مسائل بهینه‌سازی ترکیبی این است که تمامی جواب‌های امکان‌پذیر در نظر گرفته شود و توابع هدف مربوط به آن محاسبه شود و در نهایت، بهترین جواب انتخاب گردد. روشن است که شیوه شمارش کامل، نهایتاً به جواب دقیق مسأله منتهی می‌شود؛ اما در عمل به دلیل زیاد بودن تعداد جواب‌های امکان‌پذیر، استفاده از آن غیرممکن است. با توجه به مشکلات مربوط به روش شمارش کامل، همواره بر ایجاد روش‌های مؤثرتر و کاراتر تأکید شده است. در این زمینه، الگوریتم‌های مختلفی به وجود آمده است که مشهورترین نمونه آنها، روش سیمپلکس برای حل برنامه‌های خطی و روش شاخه و کرانه برای حل برنامه‌های خطی با متغیرهای صحیح است. برای مسائلی با ابعاد بزرگ، روش سیمپلکس از کارایی بسیار خوبی برخوردار است، ولی روش شاخه و کرانه کارایی خود را از دست می‌دهد و عملکرد بهتری از شمارش کامل نخواهد داشت. به دلایل فوق، اخیراً تمرکز بیشتری بر روش‌های ابتکاری^[۴۰] یا فرا ابتکاری ^[۴۱]یا جستجوی تصادفی^[۴۲]صورت گرفته است.
روش‌های جستجوی ابتکاری، روش‌هایی هستند که می‌توانند جوابی خوب (نزدیک به بهینه) در زمانی محدود برای یک مسأله ارائه کنند. روش‌های جستجوی ابتکاری عمدتاً بر مبنای روش‌های شمارشی می‌باشند، با این تفاوت که از اطلاعات اضافی برای هدایت جستجو استفاده می‌کنند. این روش‌ها از نظر حوزه کاربرد، کاملاً عمومی هستند و می‌توانند مسائل خیلی پیچیده را حل کنند. عمده این روش‌ها، تصادفی بوده و از طبیعت الهام گرفته شده‌اند.
۳-۴- مسائل بهینه‌سازی ترکیبی^[۴۳]
در طول دو دهه گذشته، کاربرد بهینه‌سازی در زمینه‌های مختلفی چون مهندسی صنایع، برق، کامپیوتر، ارتباطات و حمل و نقل گسترش یافته است.
بهینه‌سازی خطی و غیرخطی (جستجو جهت یافتن مقدار بهینه تابعی از متغیرهای پیوسته)، در دهه پنجاه و شصت از اصلی‌ترین جنبه‌های توجه به بهینه‌سازی بود.
بهینه‌سازی ترکیبی عبارت است از جستجو برای یافتن نقطه توابع با متغیرهای گسسته و در دهه ۷۰ نتایج مهمی در این زمینه به دست آمد. امروزه بسیاری از مسائل بهینه‌سازی ترکیبی (مانند مسأله فروشنده دوره‌گرد) که اغلب از جمله مسائل NP-hard^[44] هستند، به صورت تقریبی (نه به طور دقیق) در کامپیوترهای موجود قابل حل می‌باشند.
به طور رسمی یک بهینه سازی ترکیبی A یک چهارتایی است به طوری که:
مجموعه نمونه هاست.
برای یک نمونه داده شده، مجموعه راه حل های امکان پذیر است.
برای یک مورد داده شده و راه حل ممکن برای ، اندازه را مشخص می کند که معمولاً یک عدد حقیقی مثبت است.
هدف تابع است که یا برابر کمینه و یا بیشینه است.
هدف این است که برای یک نمونه ، یک راه حل بهینه پیدا کنیم که یک راه حل ممکن است با این شرط که

(۲٫۳)

برای هر مسأله بهینه سازی ترکیبی، یک مسأله تصمیم متناظر وجود دارد که می پرسد ببیند آیا یک راه حل ممکن برای مقدار خاص وجود دارد یا نه. به عنوان مثال یک گراف وجود دارد که شامل رئوس و است. یک مسأله بهینه سازی ممکن است «یافتن یک مسیر از به که از کمترین یال ها بگذرد» باشد. این مسأله ممکن است یک جواب مثلاً ۴ داشته باشد. یک مسأله تصمیم متناظر این خواهد بود که «آیا یک مسیر از به با بهره گرفتن از ۱۰ یال یا کمتر وجود دارد؟» این مسأله با یک بله یا خیر ساده جواب داده می شود. در زمینه الگوریتم های تخمین، الگوریتم ها برای مسائل سخت برای یافتن راه حل های نزدیک بهینه طراحی می شوند. بنابراین یک نسخه معمول تصمیم، یک توصیف ناکافی از مسأله است زیرا فقط راه حل های قابل قبول را مشخص می کند. اگرچه می توانیم مسائل تصمیم مناسبی مطرح کنیم، این مسائل دیگر بیشتر به طور طبیعی، یک مسأله بهینه سازی می شوند.
۳-۵- روش های حل مسائل بهینه‌سازی ترکیبی
روشن است که شیوه شمارش کامل، نهایتاً به جواب دقیق مسأله منجر می‌شود؛ اما در عمل به دلیل زیاد بودن تعداد جواب‌های امکان‌پذیر، استفاده از آن بی‌نتیجه است. برای آنکه مطلب روشن شود، مسأله مشهور فروشنده دوره‌گرد (TSP^[45]) را در نظر می‌گیریم.
این مسأله یکی از مشهورترین مسائل در حیطه بهینه‌سازی ترکیبی است که بدین شرح می باشد:
تعیین مسیر حرکت یک فروشنده بین N شهر به گونه‌ای که از هر شهر تنها یکبار بگذرد و طول کل مسیر به حداقل برسد، بسیار مطلوب است. تعداد کل جواب‌ها برابر است با . فرض کنید کامپیوتری موجود است که می‌تواند تمام جواب‌های مسأله با بیست شهر را در یک ساعت بررسی کند. بر اساس آنچه آورده شد، برای حل مسأله با ۲۱ شهر، ۲۰ ساعت زمان لازم است و به همین ترتیب، زمان لازم برای مسأله ۲۲ شهر، ۵/۱۷ روز و برای مسأله ۲۵ شهر، ۶ قرن ا ست!
به دلیل همین رشد نمایی زمان محاسبه، شمارش کامل روشی کاملاً نامناسب است.
همان طور که گفته شد، با توجه به مشکلات مربوط به روش شمارش کامل، همواره بر ایجاد روش‌های مؤثرتر و کاراتر تأکید شده است. در این زمینه، الگوریتم‌های مختلفی به وجود آمده که مشهورترین آنها، الگوریتم سیمپلکس برای حل برنامه‌های خطی و روش شاخه و کران برای حل برنامه‌های خطی با اعداد صحیح است.
بنابراین در سال‌های اخیر توجه بیشتری بر روش‌های ابتکاری برگرفته از طبیعت که شباهت‌هایی با سیستم‌های اجتماعی یا طبیعی دارد، صورت گرفته است و نتایج بسیار خوبی در حل مسائل بهینه‌سازی ترکیبی NP-hard به دنبال داشته است. در این الگوریتم‌ها هیچ ضمانتی برای آنکه جواب به دست آمده بهینه باشد، وجود ندارد و تنها با صرف زمان بسیار می‌توان جواب نسبتاً دقیقی به دست آورد؛ در حقیقت با توجه به زمان صرف شده، دقت جواب تغییر می‌کند.
۳-۵-۱- روش های ابتکاری
برای روش‌های ابتکاری نمی‌توان تعریفی جامع ارائه کرد. با وجود این، در اینجا کوشش می‌شود تعریفی تا حد امکان مناسب برای آن عنوان شود:
روش جستجوی ابتکاری، روشی است که می‌تواند جوابی خوب (نزدیک به بهینه) در زمانی محدود برای یک مسأله ارائه کند. هیچ تضمینی برای بهینه بودن جواب وجود ندارد و متأسفانه نمی‌توان میزان نزدیکی جواب به دست آمده به جواب بهینه را تعیین کرد.
در اینجا مفاهیم برخی از روش‌های اصلی ابتکاری بدون وارد شدن به جزییات معرفی می‌شود.
۳-۵-۱-۱- آزاد‌سازی
آزادسازی^[۴۶] یکی از روش‌های ابتکاری در بهینه‌سازی است که ریشه در روش‌های قطعی بهینه‌سازی دارد. در این روش، ابتدا مسأله به شکل یک مسأله برنامه‌ریزی خطی عدد صحیح ^[۴۷] یا مختلط^[۴۸] (و گاهی اوقات کمی غیر خطی)، فرموله می‌شود. سپس با برداشتن محدودیت‌های عدد صحیح بودن، یک مسأله آزاد شده به دست آمده و حل می‌شود. یک جواب خوب (و نه لزوماً بهینه) برای مسأله اصلی می‌تواند از روند کردن جواب مسأله آزاد شده (برای رسیدن به یک جواب موجه نزدیک به جواب مسأله آزاد شده)، به دست آید؛ اگر چه روند کردن جواب برای رسیدن به یک جواب لزوماً کار آسانی نیست، اما در مورد بسیاری از مدل‌های معمول، به آسانی قابل انجام است.
۳-۵-۱-۲- تجزیه