دانلود مقاله بهینه‌ سازی و معرفی انواع مختلف روش‌ های آن

چکیده بهینه‌سازی یک فعالیت مهم و تعیین‌کننده در طراحی ساختاری است.

طراحان زمانی قادر خواهند بود طرح‌های بهتری تولید کنند که بتوانند با روش‌های بهینه‌سازی در صرف زمان و هزینه طراحی صرفه‌جویی نمایند.

بسیاری از مسائل بهینه‌سازی در مهندسی، طبیعتاً پیچیده‌تر و مشکل‌تر از آن هستند که با روش‌های مرسوم بهینه‌سازی نظیر روش برنامه‌ریزی ریاضی و نظایر آن قابل حل باشند.

بهینه‌ سازی ترکیبی (Combinational Optimization)، جستجو برای یافتن نقطه بهینه توابع با متغیرهای گسسته (Discrete Variables) می‌باشد.

امروزه بسیاری از مسائل بهینه‌سازی ترکیبی که اغلب از جمله مسائل با درجه غیر چندجمله‌ای (NP-Hard) هستند، به صورت تقریبی با کامپیوترهای موجود قابل حل می‌باشند.

از جمله راه‌حل‌های موجود در برخورد با این گونه مسائل، استفاده از الگوریتم‌های تقریبی یا ابتکاری است.

این الگوریتم‌ها تضمینی نمی‌دهند که جواب به دست آمده بهینه باشد و تنها با صرف زمان بسیار می‌توان جواب نسبتاً دقیقی به دست آورد و در حقیقت بسته به زمان صرف شده، دقت جواب تغییر می‌کند.

مقدمه هدف از بهینه‌سازی یافتن بهترین جواب قابل قبول، با توجه به محدودیت‌ها و نیازهای مسأله است.

برای یک مسأله، ممکن است جواب‌های مختلفی موجود باشد که برای مقایسه آنها و انتخاب جواب بهینه، تابعی به نام تابع هدف تعریف می‌شود.

انتخاب این تابع به طبیعت مسأله وابسته است.

به عنوان مثال، زمان سفر یا هزینه از جمله اهداف رایج بهینه‌سازی شبکه‌های حمل و نقل می‌باشد.

به هر حال، انتخاب تابع هدف مناسب یکی از مهمترین گام‌های بهینه‌سازی است.

گاهی در بهینه‌سازی چند هدف به طور همزمان مد نظر قرار می‌گیرد؛ این گونه مسائل بهینه‌سازی را که دربرگیرنده چند تابع هدف هستند، مسائل چند هدفی می‌نامند.

ساده‌ترین راه در برخورد با این گونه مسائل، تشکیل یک تابع هدف جدید به صورت ترکیب خطی توابع هدف اصلی است که در این ترکیب میزان اثرگذاری هر تابع با وزن اختصاص یافته به آن مشخص می‌شود.

هر مسأله بهینه‌سازی دارای تعدادی متغیر مستقل است که آنها را متغیرهای طراحی می‌نامند که با بردار n بعدی x نشان داده می‌شوند.

هدف از بهینه‌سازی تعیین متغیرهای طراحی است، به گونه‌ای که تابع هدف کمینه یا بیشینه شود.

مسائل مختلف بهینه‌سازی به دو دسته زیر تقسیم می‌شود: الف) مسائل بهینه‌سازی بی‌محدودیت: در این مسائل هدف، بیشینه یا کمینه کردن تابع هدف بدون هر گونه محدودیتی بر روی متغیرهای طراحی می‌باشد.

ب) مسائل بهینه‌ سازی با محدودیت: بهینه‌سازی در اغلب مسائل کاربردی، با توجه به محدودیت‌هایی صورت می‌گیرد؛ محدودیت‌هایی که در زمینه رفتار و عملکرد یک سیستم می‌باشد و محدودیت‌های رفتاری و محدودیت‌هایی که در فیزیک و هندسه مسأله وجود دارد، محدودیت‌های هندسی یا جانبی نامیده می‌شوند.

معادلات معرف محدودیت‌ها ممکن است به صورت مساوی یا نامساوی باشند که در هر مورد، روش بهینه‌سازی متفاوت می‌باشد.

به هر حال محدودیت‌ها، ناحیه قابل قبول در طراحی را معین می‌کنند.

به طور کلی مسائل بهینه‌سازی با محدودیت را می‌توان به صورت زیر نشان داد: Minimize or Maximize : F(X) (1-1 ) Subject to : I = 1,2,3,…,p j = 1,2,3,…,q k = 1,2,3,…,n که در آن X={ بردار طراحی و رابطه‌های (1-1) به ترتیب محدودیت‌های نامساوی، مساوی و محدوده قابل قبول برای متغیرهای طراحی می‌باشند.

بررسی روش‌ های جستجو و بهینه‌ سازی پیشرفت کامپیوتر در طی پنجاه سال گذشته باعث توسعه روش‌های بهینه‌سازی شده، به طوری که دستورهای متعددی در طی این دوره تدوین شده است.

در این بخش، مروری بر روش‌های مختلف بهینه‌سازی ارائه می‌شود.

شکل 1-1 روش‌های بهینه‌سازی را در چهار دسته وسیع دسته‌بندی می‌کند.

در ادامه بحث، هر دسته از این روش‌ها مورد بررسی قرار می‌گیرند.

روش‌های بهینه‌سازی روش‌های شمارشی با محدودیت بی محدودیت روش‌های ابتکاری روش‌های محاسیاتی (جستجوی ریاضی) مستقیم برنامه‌ریزی خطی توابع چند متغیره توابع یک متغیره الگوریتم کلونی مورچه‌ها غیر مستقیم الگوریتم ژنتیک شبکه‌ها شبیه‌سازی آنیلینگ روش‌های فرا ابتکاری آزاد سازی تجزیه جستجوی سازنده جستجوی بهبود یابنده تولید ستون تکرار جستجوی همسایه شکل 1 1: طبقه‌بندی انواع روش‌های بهینه‌سازی 1-1-1- روش‌های شمارشی در روش‌های شمارشی (Enumerative Method)، در هر تکرار فقط یک نقطه متعلق به فضای دامنه تابع هدف بررسی می‌شود.

این روش‌ها برای پیاده‌سازی، ساده‌تر از روش‌های دیگر می‌باشند؛ اما به محاسبات قابل توجهی نیاز دارند.

در این روش‌ها سازوکاری برای کاستن دامنه جستجو وجود ندارد و دامنه فضای جستجو شده با این روش خیلی بزرگ است.

برنامه‌ریزی پویا (Dynamic Programming) مثال خوبی از روش‌های شمارشی می‌باشد.

این روش کاملاً غیرهوشمند است و به همین دلیل امروزه بندرت به تنهایی مورد استفاده قرار می‌گیرد.

1-1-2- روش‌های محاسباتی (جستجوی ریاضی یا- Based Method Calculus) این روش‌ها از مجموعه شرایط لازم و کافی که در جواب مسأله بهینه‌سازی صدق می‌کند، استفاده می‌کنند.

وجود یا عدم وجود محدودیت‌های بهینه‌سازی در این روش‌ها نقش اساسی دارد.

به همین علت، این روش‌ها به دو دسته روش‌های با محدودیت و بی‌محدودیت تقسیم می‌شوند.

روش‌های بهینه‌سازی بی‌محدودیت با توجه به تعداد متغیرها شامل بهینه‌سازی توابع یک متغیره و چند متغیره می‌باشند.

روش‌های بهینه‌سازی توابع یک متغیره، به سه دسته روش‌های مرتبه صفر، مرتبه اول و مرتبه دوم تقسیم می‌شوند.

روش‌های مرتبه صفر فقط به محاسبه تابع هدف در نقاط مختلف نیاز دارد؛ اما روش‌های مرتبه اول از تابع هدف و مشتق آن و روش‌های مرتبه دوم از تابع هدف و مشتق اول و دوم آن استفاده می‌کنند.

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

یک تقسیم‌بندی، روش‌های بهینه‌سازی با محدودیت را به سه دسته برنامه‌ریزی خطی، روش‌های مستقیم و غیرمستقیم تقسیم می‌کند.

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

برنامه‌ریزی خطی شاخه‌ای از برنامه‌ریزی ریاضی است و کاربردهای فیزیکی، صنعتی و تجاری بسیاری دارد.

در روش‌های مستقیم، نقطه بهینه به طور مستقیم جستجو شده و از روش‌های بهینه‌یابی بی‌محدودیت استفاده نمی‌شود.

هدف اصلی روش‌های غیرمستقیم استفاده از الگوریتم‌های بهینه‌سازی بی‌محدودیت برای حل عمومی مسائل بهینه‌سازی با محدودیت می‌باشد.

در اکثر روش‌های محاسباتی بهینه‌یابی، از گرادیان تابع هدف برای هدایت جستجو استفاده می‌شود.

اگر مثلاً به علت ناپیوستگی تابع هدف، مشتق آن قابل محاسبه نباشد، این روش‌ها اغلب با مشکل روبه‌رو می‌شوند.

1-1-3- روش‌های ابتکاری و فرا ابتکاری (جستجوی تصادفی) یک روش ناشیانه برای حل مسائل بهینه‌سازی ترکیبی این است که تمامی جواب‌های امکان‌پذیر در نظر گرفته شود و توابع هدف مربوط به آن محاسبه شود و در نهایت، بهترین جواب انتخاب گردد.

روشن است که شیوه شمارش کامل، نهایتاً به جواب دقیق مسأله منتهی می‌شود؛ اما در عمل به دلیل زیاد بودن تعداد جواب‌های امکان‌پذیر، استفاده از آن غیرممکن است.

با توجه به مشکلات مربوط به روش شمارش کامل، همواره بر ایجاد روش‌های مؤثرتر و کاراتر تأکید شده است.

در این زمینه، الگوریتم‌های مختلفی به وجود آمده است که مشهورترین نمونه آنها، روش سیمپلکس برای حل برنامه‌های خطی و روش شاخه و کرانه برای حل برنامه‌های خطی با متغیرهای صحیح است.

برای مسائلی با ابعاد بزرگ، روش سیمپلکس از کارایی بسیار خوبی برخوردار است، ولی روش شاخه و کرانه کارایی خود را از دست می‌دهد و عملکرد بهتری از شمارش کامل نخواهد داشت.

به دلایل فوق، اخیراً تمرکز بیشتری بر روش‌های ابتکاری (Heuristic) یا فرا ابتکاری (Metaheuristic) یا جستجوی تصادفی (Random Method) صورت گرفته است.

روش‌های جستجوی ابتکاری، روش‌هایی هستند که می‌توانند جوابی خوب (نزدیک به بهینه) در زمانی محدود برای یک مسأله ارائه کنند.

روش‌های جستجوی ابتکاری عمدتاً بر مبنای روش‌های شمارشی می‌باشند، با این تفاوت که از اطلاعات اضافی برای هدایت جستجو استفاده می‌کنند.

این روش‌ها از نظر حوزه کاربرد، کاملاً عمومی هستند و می‌توانند مسائل خیلی پیچیده را حل کنند.

عمده این روش‌ها، تصادفی بوده و از طبیعت الهام گرفته شده‌اند.

2- مسائل بهینه‌سازی ترکیبی (Optimization Problems Combinational) در طول دو دهه گذشته، کاربرد بهینه‌سازی در زمینه‌های مختلفی چون مهندسی صنایع، برق، کامپیوتر، ارتباطات و حمل و نقل گسترش یافته است.

بهینه‌سازی خطی و غیرخطی (جستجو جهت یافتن مقدار بهینه تابعی از متغیرهای پیوسته)، در دهه پنجاه و شصت از اصلی‌ترین جنبه‌های توجه به بهینه‌سازی بود.

بهینه‌سازی ترکیبی عبارت است از جستجو برای یافتن نقطه توابع با متغیرهای گسسته و در دهه 70 نتایج مهمی در این زمینه به دست آمد.

امروزه بسیاری از مسائل بهینه‌سازی ترکیبی (مانند مسأله فروشنده دوره‌گرد) که اغلب از جمله مسائل NP-hard هستند، به صورت تقریبی (نه به طور دقیق) در کامپیوترهای موجود قابل حل می‌باشند.

مسأله بهینه‌سازی ترکیبی را می‌توان به صورت زوج مرتب R,C نمایش داد که R مجموعه متناهی از جواب‌های ممکن (فضای حل) و C تابع هدفی است که به ازای هر جواب مقدار خاصی دارد.

مسأله به صورت زیر در نظر گرفته می‌شود: یافتن جواب به گونه‌ای که C کمترین مقدار را داشته باشد.

جواب بهینه معیار زیر را ارضا می‌کند: = C() = (2-1) مقدار بهینه نام دارد و وظیفه ما پیدا کردن است.

2-1- روش حل مسائل بهینه‌سازی ترکیبی روشن است که شیوه شمارش کامل، نهایتاً به جواب دقیق مسأله منجر می‌شود؛ اما در عمل به دلیل زیاد بودن تعداد جواب‌های امکان‌پذیر، استفاده از آن بی‌نتیجه است.

برای آنکه مطلب روشن شود، مسأله مشهور فروشنده دوره‌گرد (TSP) را در نظر می‌گیریم.

این مسأله یکی از مشهورترین مسائل در حیطه بهینه‌سازی ترکیبی است که بدین شرح می‌باشد: تعیین مسیر حرکت یک فروشنده بین N شهر به گونه‌ای که از هر شهر تنها یکبار بگذرد و طول کل مسیر به حداقل برسد، بسیار مطلوب است.

تعداد کل جواب‌ها برابر است با !

.

فرض کنید کامپیوتری موجود است که می‌تواند تمام جواب‌های مسأله با بیست شهر را در یک ساعت بررسی کند.

بر اساس آنچه آورده شد، برای حل مسأله با 21 شهر، 20 ساعت زمان لازم است و به همین ترتیب، زمان لازم برای مسأله 22 شهر، 5/17 روز و برای مسأله 25 شهر، 6 قرن ا ست!

به دلیل همین رشد نمایی زمان محاسبه، شمارش کامل روشی کاملاً نامناسب است.

همان طور که گفته شد، با توجه به مشکلات مربوط به روش شمارش کامل، همواره بر ایجاد روش‌های مؤثرتر و کاراتر تأکید شده است.

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

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

در این الگوریتم‌ها هیچ ضمانتی برای آنکه جواب به دست آمده بهینه باشد، وجود ندارد و تنها با صرف زمان بسیار می‌توان جواب نسبتاً دقیقی به دست آورد؛ در حقیقت با توجه به زمان صرف شده، دقت جواب تغییر می‌کند.

برای روش‌های ابتکاری نمی‌توان تعریفی جامع ارائه کرد.

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

هیچ تضمینی برای بهینه بودن جواب وجود ندارد و متأسفانه نمی‌توان میزان نزدیکی جواب به دست آمده به جواب بهینه را تعیین کرد.

در اینجا مفاهیم برخی از روش‌های اصلی ابتکاری بدون وارد شدن به جزییات معرفی می‌شود.

1- آزاد‌سازی آزادسازی (Relaxation)، یکی از روش‌های ابتکاری در بهینه‌سازی است که ریشه در روش‌های قطعی بهینه‌سازی دارد.

در این روش، ابتدا مسأله به شکل یک مسأله برنامه‌ریزی خطی عدد صحیح LIP) = Linear Litegar Programmingا مختلط MIP) = Mixed Integer Programming ) (و گاهی اوقات کمی غیر خطی)، فرموله می‌شود.

سپس با برداشتن محدودیت‌های عدد صحیح بودن، یک مسأله آزاد شده به دست آمده و حل می‌شود.

یک جواب خوب (و نه لزوماً بهینه) برای مسأله اصلی می‌تواند از روند کردن جواب مسأله آزاد شده (برای رسیدن به یک جواب موجه نزدیک به جواب مسأله آزاد شده)، به دست آید؛ اگر چه روند کردن جواب برای رسیدن به یک جواب لزوماً کار آسانی نیست، اما در مورد بسیاری از مدل‌های معمول، به آسانی قابل انجام است.

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

هر یک از این موارد تصمیم‌گیری ممکن است به تنهایی پیچیده نباشند، اما در نظر گرفتن همه آنها در یک مدل به طور همزمان، چندان آسان نیست.

روش ابتکاری تجزیه (Decomposition) می‌تواند در چنین مسائلی مفید واقع شود.

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

2-1- تکرار یکی از روش‌های تجزیه، تکرار (Iteration) است.

در این روش، مسأله به زیرمسأله‌های جداگانه‌ای تبدیل می‌شود و در هر زمان یکی از زیرمسأله‌ها با ثابت در نظر گرفتن متغیرهای تصمیم موجود در سایر زیرمسأله‌ها در بهترین مقدار شناخته شده‌شان، بهینه می‌شود؛ سپس یکی دیگر از زیرمسأله‌ها در نظر گرفته می‌شود و این عمل به طور متناوب تا رسیدن به یک جواب رضایت‌بخش، ادامه می‌یابد.

2-2- روش تولید ستون (Column Generation) این نیز یکی از روش‌های تجزیه است که عموماً برای مسائلی که دارای عناصر زیادی هستند (مانند مسأله کاهش ضایعات برش با تعداد الگوهای زیاد) کاربرد دارد.

در این روش، حل مسأله به دو بخش تقسیم می‌شود: یافتن ستون‌ها (یا عناصر) جواب (مثلاً در مسأله کاهش ضایعات برش و یافتن الگوهای برش).

یافتن ترکیب بهینه این عناصر، با توجه به محدودیت‌ها (در مسأله کاهش ضایعات برش و یافتن ترکیب مناسب الگوها).

یکی از روش‌های معمول برای یافتن ستون‌ها، مقدار متغیرهای دوگانه مسأله اصلی است، اما هر روش دیگری نیز می‌تواند مورد استفاده قرار گیرد.

جستجوی سازنده (Constructive Search) در این روش، با شروع از یک جواب تهی، تصمیم‌ها مرحله به مرحله گرفته می‌شود تا یک جواب کامل به دست آید.

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

آنچه که یک الگوریتم سازنده و یک الگوریتم آزمند را از هم متمایز می‌کند، نحوه ساختن جواب‌ها می‌باشد.

یک الگوریتم سازنده، جواب را به هر طریق ممکن تولید می‌کند، اما در یک الگوریتم آزمند، جواب مرحله به مرحله و با توجه به یافته‌ها، ساخته می‌شود (در هر مرحله، بخشی از جواب ساخته می‌شود).

جستجوی سازنده در مسائلی مانند زمانبندی ماشین و بودجه‌بندی سرمایه کاربرد داشته است.

در اینجا مثال مسیریابی کامیون مطرح می‌شود.

در این مسأله کالا باید به نقاط مشخصی (هر یک با میزان مشخصی از تقاضا برای کالا) حمل شود؛ مسأله، سازماندهی این نقاط در مسیرهای مشخص با توجه به محدودیت ظرفیت کامیون است.

جستجوی بهبود یافته (Improving Search) بر خلاف روش جستجوی سازنده، این روش با جواب‌های کامل کار می‌کند.

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

یک مسأله در طراحی این روش، انتخاب جواب اولیه است.

گاهی اوقات جواب اولیه یک جواب تصادفی است و گاهی نیز برای ساختن یک جواب اولیه، از روش‌هایی نظیر جستجوی سازنده استفاده می‌شود.

مسأله دیگر، تعیین حرکت‌ها یا به عبارتی، تعریف همسایگی (مجموعه جواب‌هایی که با یک حرکت از جواب فعلی قابل دسترسی هستند) در مسأله است.

4-1- روش جستجوی همسایه ( NS= Neighbourhood Search) استفاده از الگوریتم مبتنی بر تکرار مستلزم وجود یک سازوکار تولید جواب است.

سازوکار تولید جواب، برای هر جواب i یک همسایه به وجود می‌آورد که می‌توان از i به آن منتقل شد.

الگوریتم‌های تکراری به عنوان جستجوی همسایه (NS) یا جستجوی محلی نیز شناخته می‌شوند.

الگوریتم بدین صورت بیان می‌شود که از یک نقطه (جواب) شروع می‌شود و در هر تکرار، از نقطه جاری به یک نقطه همسایه جابه‌جایی صورت می‌گیرد.

اگر جواب همسایه مقدار کمتری داشته باشد، جایگزین جواب جاری می‌شود (در مسأله حداقل‌سازی) و در غیر این صورت، نقطه همسایه دیگری انتخاب می‌شود.

هنگامی که مقدار جواب از جواب تمام نقاط همسایه آن کمتر باشد، الگوریتم پایان می‌یابد.

مفهوم روش جستجوی همسایه از حدود چهل سال پیش مطرح شده است.

از جمله اولین موارد آن، کارهای کرز می‌باشد که برای حل مسأله فروشنده دوره‌گرد از مفهوم جستجوی همسایه استفاده کرده است.

در کارهای اخیر ریوز نیز جنبه‌هایی از این شیوه یافت می‌شود.

اشکالات الگوریتم فوق بدین شرح است: ممکن است الگوریتم در یک بهینه محلی متوقف شود، اما مشخص نباشد که آیا جواب به دست آمده یک بهینه محلی است یا یک بهینه سراسری.

بهینه محلی به دست آمده به جواب اولیه وابسته است و در مورد چگونگی انتخاب جواب اولیه هیچ راه حلی در دسترسی نیست.

به طور معمول نمی‌توان یک حد بالا برای زمان اجرا تعیین کرد.

البته الگوریتم‌های مبتنی بر تکرار مزایایی نیز دارند؛ از جمله اینکه یافتن جواب اولیه، تعیین مقدار تابع و سازوکار تولید جواب همسایه به طور معمول ساده است.

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

روش‌های فرا ابتکاری (Metaheuristic) برگرفته از طبیعت 3 - معرفی در سال‌های اخیر یکی از مهمترین و امیدبخش‌ترین تحقیقات، «روش‌های ابتکاری برگرفته از طبیعت» بوده است؛ این روش‌ها شباهت‌هایی با سیستم‌های اجتماعی و یا طبیعی دارند.

کاربرد ‌آنها برگرفته از روش‌های ابتکاری پیوسته می‌باشد که در حل مسائل مشکل ترکیبی (NP-Hard) نتایج بسیار خوبی داشته است.

در ابتدا با تعریفی از طبیعت و طبیعی بودن روش‌ها شروع می‌کنیم؛ روش‌ها برگرفته از فیزیک، زیست‌شناسی و جامعه‌شناسی هستند و به شکل زیر تشکیل شده‌اند: استفاده از تعداد مشخصی از سعی‌ها و کوشش‌های تکراری استفاده از یک یا چند عامل (نرون، خرده‌ریز، کروموزوم، مورچه و غیره) عملیات (در حالت چند عاملی) با یک سازوکار همکاری ـ رقابت ایجاد روش‌های خود تغییری و خود تبدیلی طبیعت دارای دو تدبیر بزرگ می‌باشد: انتخاب پاداش برای خصوصیات فردی قوی و جزا برای فرد ضعیف‌تر؛ جهش که معرفی اعضای تصادفی و امکان تولد فرد جدید را میسر می‌سازد.

به طور کلی دو وضعیت وجود دارد که در روش‌های ابتکاری برگرفته از طبیعت دیده می‌شود، یکی انتخاب و دیگری جهش.

انتخاب ایده‌ای مبنا برای بهینه‌سازی و جهش ایده‌ای مبنا برای جستجوی پیوسته می‌باشد.

از خصوصیات روش‌های ابتکاری برگرفته از طبیعت، می‌توان به موارد زیر اشاره کرد: پدیده‌ای حقیقی در طبیعت را مدل‌سازی می‌کنند.

بدون قطع می‌باشند.

اغلب بدون شرط ترکیبی همانند (عامل‌های متعدد) را معرفی می‌نمایند.

تطبیق‌پذیر هستند.

خصوصیات بالا باعث رفتاری معقول در جهت تأمین هوشمندی می‌شود.

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

3-1- مسأله فروشنده دوره‌گرد (Travelling Salesman Problem = TSP) در ابتدا به مسأله فروشنده دوره‌گرد (TSP) توجه می‌کنیم؛ در این مسأله مأموری به صورت تصادفی در فضای جستجو (گرافn بعدی) حرکت می‌کند.

تنها موقعیت اجباری این است که مأمور باید فهرست شهرهایی را که رفته به جهت اجتناب از تکرار به خاطر بسپارد.

در این روش بعد از n حرکت، مأمور به شهر شروع باز می‌گردد و راه‌حلی به دست می‌آید.

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

روش‌های فرا ابتکاری می‌توانند مطابق موارد زیر به دست آیند: استفاده از شیوه‌ای مبتنی بر علاقه‌مندی برای انتخاب هر حرکت مأمور؛ استفاده از روش جستجوی محلی (معاوضه موقعیت گره‌ها) برای بهبودی راه‌حل؛ استفاده از روش جستجوی محلی تصادفی و تنها پذیرش تغییرات بهبود یافته؛ استفاده از m مأمور که از شهرهای مختلف شروع می‌کنند.

استفاده از تعدادی مأمور با استخدام غیر قطعی؛ استفاده از روش‌های گروهی برای قسمت‌بندی فضا و یا مأموران؛ استفاده از قانون پذیرش بدون قطع برای تغییرات اصلاح نشده؛ استفاده از اطلاعات آخرین حرکات برای اجرای یک سیستم حافظه‌ای.

3-2- انواع روش‌های فرا ابتکاری برگرفته از طبیعت - الگوریتم ژنتیک الگوریتم ژنتیک (Genetic Algorithm) روشی عمومی از روش‌های فرا ابتکاری برای بهینه‌سازی گسسته می‌باشد که مسائل جدول زمانبندی را حل می‌نماید.

روش شبیه‌سازی که در ادامه مورد بحث قرار می‌گیرد، راهبرد تکاملی نام دارد.

این روش در سال 1975 به وسیله هولند (Holland) و در سال 1989 توسط گولدبرگ (Goldberg) ابداع شده است.

این روش نوعی روش جستجوی همسایه است که عملکردی مشابه ژن دارد.

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

ب) جمعیتی از این موجودات قابل تکثیر وجود داشته باشد.

پ) چنین وضعیتی دارای تنوع باشد.

ت) این موجودات به وسیله قابلیت‌هایی در زندگی از هم جدا شوند.

در طبیعت، گونه‌های متفاوتی از یک موجود وجود دارند که این تفاوت‌ها در کروموزوم‌های این موجودات ظاهر می‌شود و باعث تنوع در ساختار و رفتار این موجودات می‌شود.

این تنوع ساختار و رفتار به نوبه خود بر زاد و ولد تأثیر می‌گذارد.

موجوداتی که قابلیت‌ها و توانایی بیشتری برای انجام فعالیت‌ها در محیط دارند (موجودات متکامل‌تر)، دارای نرخ زاد و ولد بالاتری خواهند بود و طبعاً موجوداتی که سازگاری کمتری با محیط دارند، از نرخ زاد و ولد پایین‌تری برخوردار خواهند بود.

بعد از چند دوره زمانی و گذشت چند نسل، جمعیت تمایل دارد که موجوداتی را بیشتر در خود داشته باشد که کروموزوم‌هایشان با محیط اطراف سازگاری بیشتری دارد.

در طی زمان، ساختار افراد جامعه به علت انتخاب طبیعی تغییر می‌کند و این نشانه تکامل جمعیت است.

2- آنیلینگ شبیه‌سازی شده این روش توسط متروپولیس (Metropolis) و همکاران در سال 1953 پیشنهاد شده و جهت بهینه‌سازی به وسیله وچی (Vecchi)، گلات (Gelatt) و کرک‌پاتریک (kirkpatrick ) در سال 1983 مورد بازبینی قرار گرفته است.

این روش در مسائل تاکسی تلفنی کاربرد دارد.

الگوریتم آنیلینگ شبیه‌سازی شده (Simulated Annealing) در شکل عمومی، بر اساس شباهت میان سرد شدن جامدات مذاب و حل مسائل بهینه‌سازی ترکیبی به وجود آمده است.

در فیزیک مواد فشرده، گرم و سرد کردن فرایندی است فیزیکی که طی آن یک ماده جامد در ظرفی حرارت داده می‌شود تا مایع شود؛ سپس حرارت آن بتدریج کاهش می‌یابد.

بدین ترتیب تمام ذرات فرصت می‌یابند تا خود را در پایین‌ترین سطح انرژی منظم کنند.

چنین وضعی در شرایطی ایجاد می‌شود که گرمادهی کافی بوده و سرد کردن نیز به آهستگی صورت گیرد.

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

حد بالایی زمان اجرای الگوریتم نیز قابل تعیین است.

بنابراین الگوریتم گرم و سرد کردن شبیه‌سازی شده، الگوریتمی است تکراری که اشکالات روش‌های عمومی مبتنی بر تکرار را ندارد.

در روش آنیلینگ شبیه‌سازی شده، به صورت پی در پی از جواب جاری به یکی از همسایه‌های آن انتقال صورت می‌گیرد.

این سازوکار توسط زنجیره مارکوف به صورت ریاضی قابل توصیف است.

در این روش، یک مجموعه آزمون انجام می‌گیرد؛ این آزمون‌ها به نحوی است که نتیجه هر یک به نتیجه آزمون قبل وابسته است.

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

روش جستجوی همسایه و روش آنیلینگ شبیه‌سازی شده، هر دو روش‌های تکراری هستند.

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

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

اما عملکرد الگوریتم آنیلینگ شبیه‌سازی شده سریع‌تر است.

شبکه‌های عصبی شبکه‌های عصبی (Neural Networks) مصنوعی سیستم‌های هوشمندی هستند که از شبکه‌های عصبی طبیعی الهام گرفته شده‌اند.

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

مدل فون نیومن گرچه هم اکنون بسیار استفاده می‌شود، اما از کمبودهایی رنج می‌برد که تلاش شده است این کمبودها در شبکه‌های عصبی مصنوعی برطرف شود.

در سال 1943 مدلی راجع به عملکرد نورون‌ها (Neuron) نوشته شد که با اندکی تغییر، امروزه بلوک اصلی سازنده اکثر شبکه‌های عصبی مصنوعی می‌باشد.

عملکرد اساسی این مدل مبتنی بر جمع کردن ورودی‌ها و به دنبال آن به وجود آمدن یک خروجی است.

ورودی‌های نورون‌ها از طریق دنریت‌ها که به خروجی نورون‌های دیگر از طریق سیناپس متصل است، وارد می‌شوند.

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

مدل پایه‌ای نورون به صورت شکل 1-3 تعریف می‌شود.

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

حال می‌توانیم برای راحتی کار تعریف کنیم که در آن همان آستانه مربوط به نورون j ام است؛ تابع f ( شکل 2-3) را نیز به صورت زیر تعریف می‌کنیم: 1 if F(= 0 if (شکل 2-3) این مدل و برخی از کارهای مربوط به آن را باید به عنوان شروع مطالعات تحلیلی در نظر گرفت.

گر چه این مدل ساده فاقد ویژگی‌های پیچیده بدنه سلولی نورون‌های بیولوژیکی است، اما می‌توان به آن به صورت مدلی ساده از آنچه که واقعاً موجود است نگریست.

جستجوی ممنوع روشی عمومی است که به وسیله گلوور (Glover) در سال 1989 پیشنهاد شده و در حل مسائل برنامه‌ریزی کاری ـ خرید کاربرد دارد.

روش جستجوی ممنوع (Tabu Search)، همانند روش آنیلینگ شبیه‌سازی شده بر اساس جستجوی همسایه بنا شده است.

در این روش عملکرد حافظه انسان شبیه‌سازی شده است.

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

این مرکز همچنین فهرستی از حرکات منع شده را تنظیم می‌کند و این فهرست همواره بر اساس آخرین جستجوها منظم می‌شود.

این روش از انجام هر گونه عملیات مجدد و تکراری جلوگیری می‌کند.

شکل نوین جستجوی ممنوع توسط گلوور مطرح شده است.

روش جستجوی مبتنی بر منع، با ایجاد تغییری کوچک در روش جستجوی همسایه به وجود می‌آید.

هدف این روش آن است که بخش‌هایی از مجموعه جواب که پیش از این بررسی نشده است، مد نظر قرار گیرد.

بدین منظور حرکت به جواب‌هایی که اخیراً جستجو شده، ممنوع خواهد بود.

ساختار کلی روش جستجوی ممنوع بدین صورت است که ابتدا یک جواب اولیه امکان‌پذیر انتخاب می‌شود؛ سپس برای جواب مربوط، بر اساس یک معیار خاص مجموعه‌ای از جواب‌های همسایه امکان‌پذیر در نظر گرفته می‌شود.

در گام بعد، پس از ارزیابی جواب‌های همسایه تعیین شده، بهترین آنها انتخاب می‌شود و جابه‌جایی از جواب جاری به جواب همسایه انتخابی صورت می‌گیرد.

این فرایند به همین ترتیب تکرار می‌شود تا زمانی که شرط خاتمه تحقق یابد.

در روش جستجوی ممنوع، فهرستی وجود دارد که جابه‌جایی‌های منع شده را نگهداری می‌کند و به فهرست تابو معروف است و کاربرد اصلی آن، پرهیز از همگرا شدن به جواب‌های بهینه محلی است.

به عبارت دیگر، به کمک فهرست تابو جابه‌جایی به جواب‌هایی که اخیراً جستجو شده‌اند، ممنوع خواهد شد.

فقط بخش‌هایی از مجموعه جواب که پیش از این مورد بررسی قرار نگرفته، مد نظر خواهند بود.

در واقع جابه‌جایی از جواب جاری به جواب همسایه امکان‌پذیر زمانی انجام می‌شود که در فهرست تابو قرار نداشته باشد.

در غیر این صورت، جواب همسایه دیگری که در ارزیابی جواب‌های همسایه در رده بعدی قرار گرفته است، انتخاب شده و جابه‌جایی به آن صورت می‌گیرد.

در روش جستجوی ممنوع بعد از هر جابه‌جایی، فهرست تابو بهنگام می‌شود، به نحوی که جابه‌جایی جدید به آن فهرست اضافه شده و جابه‌جایی که تا n تکرار مشخص در فهرست بوده است، از آن حذف می‌شود.

نحوه انتخاب می‌تواند با توجه به شرایط و نوع مسأله متفاوت باشد.

سیستم مورچه (Ant System) این روش در سال 1991 توسط مانیه‌زو (Maniezzo) دوریگو (Dorigo) و کولورنی (Colorni) پیشنهاد شده است که در حل مسأله فروشنده دوره‌گرد و مسائل تخصیص چندوجهی کاربرد دارد.

الگوریتم بهینه‌سازی کلونی مورچه‌ها از عامل‌های ساده‌ای که مورچه نامیده می‌شوند، استفاده می‌کند تا به صورت تکراری جواب‌هایی تولید کند.

مورچه‌ها می‌توانند کوتاه‌ترین مسیر از یک منبع غذایی به لانه را با بهره‌گیری از اطلاعات فرمونی پیدا کنند.

مورچه‌ها در هنگام راه رفتن، روی زمین فرمون می‌ریزند و با بو کشیدن فرمون ریخته شده بر روی زمین راه را دنبال می‌کنند؛ چنانچه در طی مسیر به سوی لانه به یک دوراهی برسند، از آن جایی که هیچ اطلاعی درباره راه بهتر ندارند، راه را به تصادف برمی‌گزینند.

انتظار می‌رود به طور متوسط نیمی از مورچه‌ها مسیر اول و نیمی دیگر مسیر دوم را انتخاب کنند.

فرض می‌شود که تمام مورچه‌ها با سرعت یکسان مسیر را طی کنند.

از آنجا که یک مسیر کوتاه‌تر از مسیر دیگر است، مورچه‌های بیشتری از آن می‌گذرند و فرمون بیشتری بر روی آن انباشته می‌شود.

بعد از مدت کوتاهی مقدار فرمون روی دو مسیر به اندازه‌ای می رسد که روی تصمیم مورچه‌های جدید برای انتخاب مسیر بهتر تأثیر می‌گذارد.

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

بعد از مدت کوتاهی تمام مورچه‌ها این مسیر را انتخاب خواهند کرد.

منابع: طارمی، رضا؛ بهینه‌سازی شبکه خیابان‌های شهری با استفاده از الگوریتم ژنتیک؛ پایان‌نامه کارشناسی‌ارشد، دانشگاه علم و صنعت ایران ، 1382 واحد منشوری، علی‌رضا؛ بهینه‌سازی در روش دو بعدی؛ پایان‌نامه کارشناسی‌ارشد، دانشگاه صنعتی شریف ، 1372 ابوالقاسمی، فرهاد؛ کاربرد الگوریتم سیستم مورچه‌ها در مسأله طراحی شبکه؛ پایان‌نامه کارشناسی ارشد، مهندسی سیستم‌های اقتصادی اجتماعی، مؤسسه عالی پژوهشی در برنامه‌ریزی و توسعه، 1380 Tutorial: Heuristic Optimization ,Ronald L.Rardinm,School of Industrial Engineering ,Purde University