الگوریتم های بهینه سازی

الگوریتم های بهینه سازی (Optimization Algorithms) به آن دسته از الگوریتم‌هایی گفته می‌شود که با توجه به محدودیت‌ها و نیازهای یک مسئله بهینه سازی، برای یافتن یک جواب قابل قبول تلاش می‌کند. مسائل بهینه سازی با روش‌های مختلفی حل می‌شوند؛ مانند استفاده از الگوریتم های بهینه سازی، استفاده از الگوریتم‌های ابتکاری یا هیوریستیک (Heuristic) و همچنین، استفاده از روش های فرا ابتکاری یا متاهیوریستیک (Metaheuristic) که گاهی اوقات این روش‌ها با یکدیگر تلفیق می‌شوند و راه حل جدیدی را ارائه می‌دهند. در بسیاری از متون نیز به تمامی این الگوریتم‌ها، الگوریتم های بهینه سازی نیز می‌گویند. اما تفاوتی بین این تعاریف وجود دارد.

 

الگوریتم های بهینه سازی

الگوریتم‌های بهینه سازی از یک روند سیستماتیک برای پیدا کردن یک جواب بهینه برای مسئله تعریف شده استفاده می‌کند. این کار به‌وسیله اکتشاف فضای مورد جستجو به‌صورت تکرار شونده یا Iterative صورت می‌گیرد. الگوریتم‌های بهینه سازی معمولاً بر تکنیک‌های ریاضی متکی هستند و جواب پیدا شده توسط این الگوریتم‌ها می‌تواند به صورت قطعی (Deterministic) و یا احتمالی (Probabilistic) باشند. الگوریتم‌های بهینه سازی معمولاً برای حل مسائل مشخصی ایجاد می‌شوند. الگوریتم‌هایی مانند  الگوریتم ژنتیک، الگوریتم ذوب شبیه سازی شده (Simulated Annealing) و الگوریتم بهینه سازی ازدحام ذرات یا PSO از این دسته هستند.

الگوریتم های ابتکاری

الگوریتم‌های ابتکاری یا هیوریستیک، از یک دامنه مشخص استفاده می‌کنند تا در زمانی کوتاه به جواب قابل قبولی برسند بنابراین تضمین نمی‌کنند که جواب داده شده، جواب بهینه باشد. این الگوریتم‌ها بر پایه جستجو ساخته شده‌اند و با کاهش فضای جستجو، سعی در پیدا کردن جواب دارند. برای مسائل بسیار سخت و پیچیده معمولاً استفاده از الگوریتم‌های ابتکاری منطقی به‌نظر می‌رسد؛ چرا که ممکن است یافتن جوابی بهینه غیرممکن (Infeasible) باشد و یا نیازمند زمان بالایی برای پیدا کردن آن باشد. از نمونه الگوریتم‌های هیوریستیک می‌توان به الگوریتم‌های حریصانه (Greedy) و تپه‌نوردی (Hill Climbing) اشاره کرد.

الگوریتم های فرا ابتکاری

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

الگوریتم های بهینه سازی چگونه کار می‌کنند؟

همان‌طور که در ابتدای مقاله گفته شد، هدف الگوریتم های بهینه سازی، یافتن یک جواب با توجه به محدودیت‌های اعمال شده و نیاز یک مسئله است. ممکن است تعداد جواب‌های یک مسئله زیاد باشد؛ اما الگوریتم‌های بهینه سازی سعی در پیدا کردن اپتیمال‌ترین یا همان بهینه‌ترین جواب دارند. برای محقق کردن این امر، الگوریتم‌ها از تابعی به نام تابع هزینه (Cost Function) استفاده می‌کنند. این تابع با توجه به نوع و هدف مسئله تغییر می‌کند؛ به عنوان مثال، ممکن است در جستجوی اینترنتی، تابع هزینه زمان پیدا کردن آیتم مورد نظر باشد.

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

بررسی مراحل بهینه سازی

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

1. فرموله کردن مسئله: برای شروع حل یک مسئله، ابتدا می‌بایست ساختار کلی آن را تعریف کنیم. به این صورت که تمامی پارامترهای مهم به ترتیب مشخص شوند، اهداف مسئله تعیین گردد و پارامترهای ورودی و خروجی مشخص شوند. ادامه مراحل انجام فرآیند وابسته به این مرحله می‌باشد؛ بنابراین فرموله کردن دقیق و با جزئیات، بسیار در حل مسائل بهینه سازی موثر است.
2. مدل سازی مسئله: بعد از فرموله کردن مسئله، نوبت به ایجاد یک مدل ریاضی برای مسئله می‌شود. مسائل بسیار گوناگونی وجود دارد که برای بعضی از آنها فرمول‌های بسیار زیادی ایجاد شده است؛ بنابراین می‌توانیم از مدل‌های از پیش تعریف شده استفاده کنیم و یا مدل‌های مشابه را با تغییرات جزئی به مدل مدنظر خودمان تغییر دهیم.
3. بهینه سازی مسئله: در این مرحله با استفاده از اعمال الگوریتم‌ها بر روی مدل ساخته شده، سعی می‌کنیم یک جواب بهینه یا تقریباً بهینه (بستگی به انتخاب الگوریتم‌مان دارد) پیدا کنیم. لازم است بگوییم که جواب پیدا شده در این مرحله برای مدل ساخته شده است و استفاده از آن در دنیای واقعی بر روی مسائل واقعی ممکن است منجر به پیدا کردن جوابی متفاوت شود.
4. استقرار مسئله: در این مرحله، جواب به دست آمده بررسی می‌شود و تصمیم نهایی برای درستی مدل ایجاد شده و انتخاب الگوریتم گرفته می‌شود. اگر جواب به‌دست آمده قابل قبول باشد، کار بهینه سازی همین جا تمام می‌شود. در غیر این صورت باید به مراحل قبلی برگردیم و مجدداً فرآیندها را انجام دهیم.

انواع مسائل بهینه سازی

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

1. مسائل بهینه سازی بدون محدودیت (Unconstrained Optimization Problems): در این مسائل، هدف کلی ما بیشینه کردن و یا کمینه کردن تابع هدفمان است و هیچ گونه محدودیتی بر روی پارامترهای تعیین شده اعمال نمی‌شود. این مسائل از پیچیدگی کمتری برخوردارند و مدل‌سازی آنها نیز ساده‌تر است.
2. مسائل بهینه سازی با محدودیت (Constrained Pptimization Problems): در این مسائل، برروی بعضی از پارامترها و یا تمامی پارامترها، محدودیت اعمال می‌شود. محدودیت می‌تواند با توجه به نیازهایمان باشد و یا محدودیت‌های رفتاری در دنیای واقعی و وابسته به فیزیک و طبیعت باشد؛ به عنوان مثال فرض کنید در جواب یک مسئله بهینه سازی، سرعت یک ماشین 500 کیلومتر در ساعت در نظر گرفته شود. می‌دانیم که از نظر فیزیکی و قانونی این سرعت ممکن نیست بنابراین محدودیت سرعت (مثلاً 100) برروی متغیر سرعت اعمال می‌شود و یا متغیر هزینه نهایی برای یک کار ساده ساختمانی به چند ده میلیارد برسد که غیرمنطقی به نظر می‌رسد (شاید چند سال بعد منطقی بنظر برسد). در این جا با محدودیت قیمت گذاشتن بر روی متغیر هزینه، جواب نهایی را پیدا می‌کنیم. انتخاب الگوریتم و روش بهینه سازی نیز با توجه به این محدودیت ها صورت می‌گیرد.

مشکلات الگوریتم های بهینه سازی

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

• هزینه بالا: حل مسائل بهینه سازی نیاز به محاسبات بسیار زیادی دارد. هرچه دیتاست‌ها بزرگ‌تر می‌شوند، فضای مورد جستجو نیز بزرگ‌تر می‌شود و به مراتب نیازمندی به منابع افزایش پیدا می‌کند؛ همچنین زمان مورد نیاز نیز برای حل این مسائل پیچیده زیاد می‌شود.
• حساس به نقطه شروع: بعضی از الگوریتم‌های بهینه سازی، مخصوصاً الگوریتم های جستجوی محلی، می‌توانند به نقطه شروع حساس باشند. با توجه به نقاط شروع مختلف این الگوریتم‌ها ممکن است در نقاط بهینه محلی، گیر کنند که خود مشکل دیگری است.
• گیر کردن در نقطه ی بهینه محلی (Local Optima): بعضی از الگوریتم‌ها مانند الگوریتم‌های بر پایه گرادیان یا تکنیک حریصانه ممکن است در نقطه بهینه محلی گیر کنند. این مشکل، مانع پیدا کردن بهینه‌ترین جواب که در نقطه Global Optima یا بهینه ی سراسری است می‌شود. مدیریت سخت محدودیت ها: اکثر مسائل بهینه سازی دارای محدودیت‌هایی برروی متغیرها می‌باشند که می‌بایست ارضا شوند. بعضی از الگوریتم‌ها با مدیریت کردن این محدودیت‌ها برای پیدا کردن جواب به‌صورت کارآمد مشکل دارند و ممکن است منجر به پیدا کردن جوابی نامناسب شود و یا اصلاً جوابی پیدا نکند.
• انتخاب الگوریتم بهینه سازی و پارامتر های وابسته: تعداد بسیار زیادی الگوریتم‌های بهینه سازی وجود دارد و تعداد آنها سال به سال نیز بیشتر می‌شود. انتخاب یک الگوریتم بهینه سازی مناسب ممکن است چالش برانگیز باشد؛ چرا که الگوریتم‌های مختلف ممکن است جواب‌های مختلفی پیدا کنند و همچنین انتخاب پارامتر آنها نیاز به تخصص ویژه‌ای داشته باشد.

مهم‌ترین الگوریتم های بهینه سازی

الگوریتم‌های بهینه سازی زیادی وجود دارد که هر کدام ویژگی‌های خاص خودش را دارد. در این جا به بعضی از مهم‌ترین آنها اشاره می‌کنیم:

الگوریتم ژنتیک (Genetic Algorithm)

یکی از معروف‌ترین الگوریتم های بهینه سازی، الگوریتم ژنتیک است. این الگوریتم به‌صورت تصادفی عمل می‌کند و منطق آن بر پایه انتخاب ژنتیک در طبیعت است. این الگوریتم در دسته الگوریتم های تکاملی (Evolutionary Algorithms) نیز قرار دارد.

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

حتما بخوانید :

الگوریتم کرم شب تاب (Firefly Algorithm)

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

الگوریتم بهینه سازی ازدحام ذرات (PSO)

الگوریتم بهینه سازی ازدحام ذرات یا PSO  یا Particle Swarm Optimization که در سال 1995 توسط Eberhart و Kennedy معرفی شد، نوعی از الگوریتم بهینه سازی فرا ابتکاری است که از رفتار دسته پرندگان الهام گرفته شده است. به این صورت که در دسته‌ی پرندگان، برای دست یافتن به غذا، پرندگان به سمت پرندگانی حرکت می‌کنند که به غذا نزدیک‌تر باشند. در اینجا ذرات یا پارتیکل‌ها همان جواب مسئله هستند. هر ذره به سمت فضای جواب مسئله حرکت می‌کند. جستجو در این الگوریتم براساس تجربیات خود ذره و یا تجربیات بهترین ذره در جمعیت است. 

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

• الگوریتم کلونی مورچه‌ها
• الگوریتم زنبور عسل مصنوعی
• الگوریتم جهش قورباغه
• الگوریتم شمع و پروانه
• الگوریتم وال یا نهنگ
• الگوریتم گرگ خاکستری

جمع‌بندی

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