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

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

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

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

1) براساس تراکم ( استفاده از رفتار وقایع و موجودات در طبیعت )

2)براساس فیزیک (‌ استفاده از قوانین موجود در فیزیک )

3)براساس تکامل ( مانند الگوریتم ژنتیک )

4)براساس رفتارهای انسانی

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

چگونه مورد استفاده قرار می‌گیرند؟

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

یک مثال کاربردی

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

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

با یک محاسبه متوجه می‌شویم که این تابع باید 168 بُعد ( 7 پمپ و 24 ساعت که در هر ساعت، هر میزان دبی قیمت مختلفی دارد ) داشته باشد.

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