هوش مصنوعی 153 بازدید

«بهینه سازی ریاضیاتی» (Mathematical Optimization) که به آن «برنامه‌نویسی ریاضیاتی» (Mathematical Programming) نیز گفته می‌شود، فرایندی است که در آن بهترین جواب (با توجه به مجموعه‌ای از معیارها) از میان مجموعه‌ای از جواب‌های ممکن، برای یک مسأله خاص انتخاب می‌شود. امروزه مسائل بهینه سازی در تمامی رشته‌های علمی کَمی (Quantitative Disciplines) نظیر «علوم کامپیوتر» (Computer Science)، مهندسی (Engineering)، «تحقیق در عملیات» (Operations Research)، «اقتصاد» (Economics) و سایر موارد مورد استفاده قرار می‌گیرند. در طول قرن‌های متمادی، توسعه روش‌های تولید جواب و حل مسأله، یکی از حوزه‌های مهم تحقیقاتی در علم «ریاضیات» (Mathematics) بوده است و اهمیت آن‌ها در طی چند سال گذشته چند برابر شده است.

جهت درک بهتر و اصولی‌تر حوزه بهینه سازی (ریاضیاتی)، ابتدا لازم است تا شناخت کافی در مورد مسائل بهینه سازی ایجاد شود. به بیان ساده، در یک «مسأله بهینه سازی» (Optimization Problems)، هدف «کمینه‌سازی» (Minimizing) یا «بیشینه‌سازی» (Maximizing) یک «تابع حقیقی» (Real Function) است؛ برای چنین کاری سیستم بهینه سازی ریاضیاتی، به طور سیستماتیک، مقادیر ورودی را از یک مجموعه مجاز از مقادیر انتخاب و پس از آن، مقدار تابع حقیقی را محاسبه می‌کند.

تعمیم نظریه بهینه سازی (Optimization Theory) و تکنیک‌های آن به دیگر حوزه‌های علمی و تحقیقاتی مرتبط، در حیطه کاربردهای مهم رشته «ریاضیات کاربردی» (Applied Mathematics) محسوب می‌شود. به طور کلی، اصطلاح بهینه سازی به فرایندی اطلاق می‌شود که هدف آن پیدا کردن بهترین مقادیر یک (یا چند) «تابع هدف» (Objective Functions) در یک دامنه تعریف شده است.

بهینه سازی

مؤلفه‌های یک مدل بهینه سازی

بهینه سازی ابزار مهمی در «تصمیم‌گیری» (Decision Making) و تحلیل سیستم‌های فیزیکی محسوب می‌شود. از نظر ریاضی، یک مسأله بهینه سازی، مسأله پیدا کردن بهترین جواب از میان مجموعه‌ای از جواب‌های کاندید (Candidate) یا امکان‌پذیر (Feasible) است.

بهینه سازی

ساختن یک مدل بهینه سازی

اولین گام در فرایند بهینه سازی، ساختن یک مدل مناسب برای بهینه سازی است؛ مدل‌سازی (Modelling)، به فرایند شناسایی و نمایش ریاضی «هدف» (Objective)، «متغیرها» (Variables) و «قیدهای» (Constraints) مسأله گفته می‌شود:

  • هدف (Objective)، معیار کمی عملکرد سیستم است که قرار است کمینه یا بیشینه شود. به عنوان نمونه، در «تولید» (Manufacturing) هدف کمینه‌سازی هزینه‌های تولید و یا بیشینه‌سازی سود است. در حالی که در برازش داده‌ها (Data Fitting) روی یک مدل، هدف کمینه‌سازی انحراف کل داده‌های مشاهده شده (Observed Data) از داده‌های پیش‌بینی شده (Predicted Data) است.
  • متغیرها (Variables) یا به عبارت دیگر «ناشناخته‌ها» (Unknowns)، مؤلفه‌هایی از مدل بهینه سازی محسوب می‌شوند که قرار است مقادیر مناسبی برای آن‌ها یافت شود. به عنوان نمونه در فرایند تولید، متغیرها می‌توانند پارامترهایی نظیر مقدار منابع مصرف شده و یا زمان صرف شده در هر فعالیت باشد. در حالی که در برازش داده‌ها، متغیرها همان پارامترهای مدل خواهند بود.
  • قیدها (Constraints) توابعی هستند که روابط میان متغیرها (Variables) را نشان می‌دهد و از این طریق، مقادیر مجاز برای متغیرها مشخص می‌شود. به عنوان نمونه در فرایند تولید، مقدار منابع مصرف شده نمی‌تواند از مقدار منابع در دسترس فراتر برود.

مشخص کردن نوع مسأله بهینه سازی

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

 مسائل بهینه سازی (Optimization Problems)

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

با داشتن: یک تابع به فرم $$f : A \rightarrow R$$ که مقادیر را از مجموعه‌ای نظیر $$A$$ (دامنه مسأله) به اعداد حقیقی (Real Numbers) نگاشت می‌کند.

هدف: پیدا کردن عنصری مثل $$X _ { 0 } \in A$$ است، به طوری که شرط $$f ( X _ { 0 }) \leq f ( X) \;\;\; f o r \; a l l\;\;\ \; X \in A$$ (برای مسائل کمینه‌سازی) یا شرط $$f ( X _ { 0 }) \geq f ( X) \;\;\; f o r \; a l l\;\;\ \; X \in A$$ (برای مسائل بیشینه‌سازی) برقرار باشد.

به فرمول‌بندی مسائل به شکل نشان داده شده، نمایش مسأله بهینه سازی یا نمایش مسأله برنامه‌نویسی ریاضی (Mathematical Programming Problem) گفته می‌شود. نکته بسیار مهم در مورد مسائل بهینه‌سازی این است که بسیاری از مسائل «جهان واقعی» (Real-World) و مسائل تئوری را می‌توان از طریق چارچوب عمومی نمایش داده شده مدل‌سازی کرد. به فرمول بندی مسائل بهینه سازی در قالب زیر توجه کنید:

$$f ( X _ { 0 } ) \geq f ( X ) \;\;\; \Leftrightarrow \;\;\; \widetilde { f } ( X _ { 0 } ) \leq \widetilde { f } ( X )$$

$$\widetilde { f } ( X ) :=- f ( X ) , \;\;\;\;\; \widetilde { f }:A \rightarrow R$$

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

مفاهیم اولیه در بهینه سازی (ریاضیاتی)

روش‌های بهینه سازی، یکی از معتبرترین و قابل قبول‌ترین روش‌های حل مسأله در حوزه‌‌های مختلف علمی محسوب می‌شوند. به عنوان نمونه، در رشته فیزیک، به مسائلی که از طریق چارچوب بالا فرمول‌بندی شوند، تکنیک‌های «کمینه‌سازی انرژی» (Energy Minimization) گفته می‌شود. به عبارت دیگر در اصل، مقدار تابع $$f$$ انرژی سیستمی که مدل‌سازی شده است را نشان می‌دهد. از جمله سیستم‌های بهینه سازی که از مفاهیم موجود در حوزه فیزیک («فیزیک آماری» (Statistical Physics)) استفاده می‌کنند، می‌تواند به الگوریتم «بهینه سازی اکسترمال» (Extremal Optimization) اشاره کرد. در ادامه، کدهای پیاده‌سازی الگوریتم بهینه سازی اکسترمال در زبان Ruby نمایش داده شده است:

همچنین در حوزه «هوش مصنوعی» (Artificial Intelligence) و «یادگیری ماشین» (Machine Learning) نیز بسیار حیاتی است که کیفیت «مدل داده» (Data Model)، به طور پیوسته و توسط یک «تابع هزینه» (Cost Function) ارزیابی شود؛ در این حالت، منظور از کمینه‌سازی تابع هزینه، پیدا کردن مجموعه‌ای از «پارامترهای بهینه» (Optimal Parameters) است که سبب تولید مقدار بهینه خطا (کمترین خطای ممکن) در سیستم می‌شوند.

از جمله الگوریتم‌های بهینه سازی که در دسته «الگوریتم‌های تخمین توزیع» (Estimation of Distribution Algorithms) قرار می‌گیرد، می‌توان به الگوریتم «بهینه سازی بیزی» (Bayesian Optimization) اشاره کرد. در ادامه، کدهای پیاده‌سازی الگوریتم بهینه سازی بیزی در زبان Ruby نمایش داده شده است:

در فرمول‌بندی مسائل بهینه سازی (Optimization Problems)، مجموعه $$A$$ زیر مجموعه‌ای از «فضای اقلیدسی» (Euclidean Space) یا $$R ^ { n }$$ است. معمولا در مسائل بهینه سازی، برای $$A$$ مجموعه‌ای از «قیود» (Constraints) تعریف می‌شوند؛ قیود، «برابری‌ها» (Equalities) یا «نابرابری‌هایی» (Inequalities) هستند که تمامی اعضای مجموعه $$A$$ باید آن‌ها را ارضا کنند. همچنین، به مجموعه $$A$$ یا همان دامنه یک تابع بهینه‌سازی مانند $$f$$ (به عبارت دیگر، دامنه تابع هدف مسأله بهینه‌سازی)، «فضای جستجو» (Search Space) یا «مجموعه انتخاب» (Choice Set) نیز گفته می‌شود.

با توجه به تعاریف انجام شده، هر یک از اعضای مجموعه $$A$$، یک جواب کاندید یا جواب امکان‌پذیر برای تابع بهینه‌سازی $$f$$ محسوب می‌شوند. تابع بهینه‌سازی $$f$$ با نام‌های دیگری نظیر «تابع هدف» (Object Function)، «تابع زیان» (Loss Function) یا «تابع هزینه» (Loss Function)، «تابع برازندگی» (Fitness Function) و در برخی رشته‌های خاص، «تابع انرژی» (Energy Function) شناخته می‌شود. تابع زیان و تابع هزینه برای مسائل کمینه‌سازی و تابع هدف، برای مسائل بیشینه‌سازی مورد استفاده قرار می‌گیرند.

به یک جواب کاندید یا امکان‌پذیر، که تابع هدف مسأله بهینه سازی را بیشینه یا کمینه کند، «جواب بهینه» (Optimal Solution) گفته می‌شود. همانطور که پیش از این نیز اشاره شد، مسائل بهینه سازی در ریاضیات، معمولا در قالب مسائل «کمینه‌سازی» (Minimization) نمایش داده می‌شوند.

کمینه محلی (Local Minimum)، بیشینه محلی (Local Maximum) و بهینه سراسری (Global Optimum)

یک کمینه محلی $$X^{\star}$$ تابع $$f$$، عنصری است که به ازاء آن پارامتری مانند $$\delta > 0$$ وجود دارد، به طوری که:

,$$\forall X \in A \; w h e r e \parallel X – X ^ { \star }\parallel \leq \delta$$

و به ازاء تمامی مقادیر $$X$$ که قید (Constraint) بالا را ارضا می‌کنند، عبارت $$f ( X ^ { \star } ) \leq f ( X )$$ برقرار است. به عبارت دیگر در برخی نواحی اطراف $$X^{\star}$$، تمامی مقادیر تابع $$f$$، بزرگتر یا برابر با مقدار عنصر کمینه محلی هستند. همچنین، بیشینه محلی به صورت مشابه و به شکل زیر تعریف می‌شود:

یک بیشینه محلی $$X^{\star}$$ تابع $$f$$، عنصری است که به ازاء آن پارامتری مانند $$\delta > 0$$ وجود دارد، به طوری که:

,$$\forall X \in A \; w h e r e \parallel X – X ^ { \star }\parallel \leq \delta$$

و به ازاء تمامی مقادیر $$X$$ که قید (Constraint) بالا را ارضا می‌کنند، عبارت $$f ( X ^ { \star } ) \geq f ( X )$$ برقرار است. به عبارت دیگر در برخی نواحی اطراف $$X^{\star}$$، تمامی مقادیر تابع $$f$$، کوچکتر یا برابر با مقدار عنصر بیشینه محلی هستند.

بهینه سازی محدب و غیر محدب

اگرچه عناصر کمینه یا بیشینه محلی بهتر از (یا حداقل برابر با) عناصر همسایگی اطرافشان هستند، ولی یک عنصر بیشینه یا کمینه سراسری (یا همان مقدار بهینه سراسری (Global Optimum)) از تمامی جواب‌های کاندید یا امکان‌پذیر برای یک مسأله بهینه سازی بهتر خواهد بود. به طور کلی، تنها در صورتی که تابع هدف مسأله بهینه سازی «محدب» (Convex) نباشد، ممکن است بیش از یک «کمینه محلی» (Local Minimum) یا «بیشینه محلی» (Local maximum) در مسأله وجود داشته باشد.

در مسائل «بهینه سازی محدب» (Convex Optimization)، در صورتی که یک جواب بیشینه محلی یا کمینه محلی برای مسأله وجود داشته باشد، این جواب، بهینه سراسری مسأله مورد نظر نیز خواهد بود. با این حال، در یک مسأله بهینه سازی «غیر محدب» (Non-Convex) ممکن است بیش از یک جواب بیشینه محلی یا کمینه محلی وجود داشته باشد که لزوما همه آن‌ها بهینه سراسری مسأله مورد نظر نخواهند بود.

بهینه سازی

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

بهینه سازی

برای غلبه بر چنین معضلی در روش‌های بهینه سازی، زیر شاخه‌ای به نام «بهینه سازی سراسری» (Global Optimization) در حوزه‌های ریاضیات کاربردی و «آنالیز عددی» (Numerical Analysis) پدید آمده است. هدف روش‌های بهینه سازی سراسری، پیاده‌سازی «الگوریتم‌های قطعی» (Deterministic Algorithms) است که قادر هستند «همگرایی» (Convergence) به جواب بهینه سراسری واقعی یک مسئله بهینه سازی محدب را در زمان محدود تضمین کنند.

بهینه سازی

نمادگذاری‌ها در بهینه سازی ریاضیاتی

در ادامه، مهم‌ترین نماد‌گذاری‌ها در بهینه سازی ریاضیاتی مورد بررسی قرار می‌گیرند.

مقدار کمینه یا بیشینه یک تابع

نمادگذاری زیر را در نظر بگیرید:

$$m i n _ { x \in R } ( x ^ { 2 } + 1 )$$

نمادگذاری نمایش داده شده، مقدار کمینه تابع هدف $$ x ^ { 2 } + 1$$ را، وقتی که مقدار $$x$$ از مجموعه اعداد حقیقی $$R$$ انتخاب شده باشد، نمایش می‌دهد. مقدار کمینه این تابع برابر با ۱ (یک) است و در نقطه $$x=0$$ رخ می‌دهد. به طور مشابه، نمادگذاری زیر:

$$m a x _ { x \in R } \; (2 x)$$

مقدار بیشینه تابع هدف $$(۲ x)$$ را نمایش می‌دهد. در این تابع، پارامتر $$x$$ می‌تواند هر مقدار حقیقی به خود بگیرد. در این حالت، از آنجایی که تابع هدف «بی‌کران» (Unbounded) است، هیچ مقدار بیشینه‌ای برای آن وجود نخواهد داشت. به عبارت دیگر، جواب این مسأله «بی‌نهایت» (Infinity) یا «تعریف نشده» (Undefined) است.

آرگومان‌های ورودی بهینه (Optimal Input Argument)

نمادگذاری زیر را در نظر بگیرید:

$$ a r g \;m i n _ { x \in \left ( -\infty , -1 \right] } ( x ^ { 2 } + 1 )$$

نمادگذاری که در ادامه مشاهده خواهید کرد، هیچ تفاوتی با نمادگذاری بالا ندارد:

$$ a r g \;m i n _ { x } ( x ^ { 2 } + 1 ), \; s u b j e c t \; to: { x \in \left ( -\infty , -1 \right] }$$

نمادگذاری‌های نمایش داده شده، مقدار (یا مقادیر) آرگومان $$x$$ در بازه $$x \in \left ( -\infty , -1 \right]$$ را نشان می‌دهد؛ مقادیری که تابع هدف $$x ^ { 2 } + 1$$ را کمینه‌سازی می‌کنند. نکته مهم در مورد نمادگذاری تعریف شده برای مسأله بهینه‌سازی بالا این است که در این نمادگذاری، مقادیر کمینه تابع هدف مشخص نشده‌اند و تنها قید مرتبط با مقادیر ممکن برای آرگومان $$x$$ نمایش داده شده است. در این مورد، از آنجایی که مقدار صفر در مجموعه مقادیر امکان‌پذیر آرگومان $$x$$ وجود ندارد، مقدار کمینه این تابع در نقطه $$x=-1$$ حاصل می‌شود.

به طور مشابه، برای نمایش آرگومان‌های ورودی بهینه یک مسأله بیشینه‌سازی، نمادگذاری زیر را در نظر بگیرید:

$$ a r g \;m a x _ { x \in \left [ -5 , 5 \right],\; y\in R } ( x \;cos \;y )$$

مانند حالت قبل، نمادگذاری که در ادامه مشاهده خواهید کرد، هیچ تفاوتی با نمادگذاری بالا ندارد:

$$ a r g \;m a x _ { x , \;y} ( x \; cos \;y), \; s u b j e c t\; t o : x \in \left [ -5 , 5 \right],\; y\in R$$

نمادگذاری‌های نمایش داده شده، جفت مقادیر $$(x,y)$$ را نشان می‌دهند که مقدار تابع هدف $$x \; cos \;y$$ را بیشینه می‌کنند؛ در این تابع هدف، قید خاصی روی آرگومان $$x$$ تعریف شده است که بر اساس آن، تنها مقادیر موجود در بازه $$\left [ -5 , 5 \right]$$ قابل قبول هستند. مانند مورد قبلی، در نمادگذاری تعریف شده برای مسأله بیشینه‌سازی بالا، مقادیر بیشینه تابع هدف مشخص نشده‌اند و تنها قیدهای مرتبط با مقادیر ممکن برای آرگومان $$x$$ و $$y$$ نمایش داده شده‌اند. در این مورد، جفت مقادیر $$(x,y)$$ که به فرم $$ (۵ , \; ۲k\pi)$$ و $$ (-۵ , \; (۲ k + 1 ) \pi)$$ هستند، جواب‌های این مسأله بهینه‌سازی هستند؛ پارامتر $$k$$ می‌تواند هر مقدار صحیحی را به خود بگیرد.

بنابراین، عملگرهای $$ a r g \;m i n$$ و $$ a r g \;m a x$$، به ترتیب بیانگر «آرگومان کمینه تابع هدف» (Argument of Minimum) و «آرگومان بیشینه تابع هدف» (Argument of Maximum) هستند و مشخص می‌کنند که مسأله مورد نظر، یک مسأله کمینه‌سازی است یا یک مسأله بیشینه‌سازی.

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

همانطور که پیش از این نیز اشاره شد، گام دوم در فرایند بهینه سازی، مشخص کردن نوع و یا طبقه‌بندی مسأله‌ای است که قرار است بهینه‌سازی شود. از آنجایی که هر یک از الگوریتم‌های حل مسائل بهینه سازی (Optimization)، جهت یافتن مقادیر بهینه انواع خاصی از مسائل پیاده‌سازی می‌شوند، مشخص کردن «دسته‌بندی» (Classification) مدل‌های بهینه سازی نقش مهمی در این فرایند ایفا خواهد کرد. در ادامه، برخی از مهم‌ترین دسته‌بندی‌های ارائه شده از مدل‌های بهینه سازی نمایش داده خواهد شد.

مسائل بهینه سازی «پیوسته» (Continuous) و بهینه سازی «گسسته» (Discrete)

برخی از مدل‌های بهینه سازی، جهت بهینه سازی توابعی طراحی شده‌اند که متغیرهای آن‌ها، مقادیر مجاز خود را از یک «مجموعه گسسته» (Discrete Set) اتخاذ می‌کنند (زیر مجموعه‌ای از مقادیر صحیح)، در حالی که مدل‌های دیگر، برای بهینه سازی توابعی پیاده‌سازی شده‌اند که متغیرهای آن‌ها می‌توانند مقادیر حقیقی (Real Values) به خود بگیرند. به مدل‌هایی که از متغیرهای گسسته استفاده می‌کنند، مدل‌های مسائل بهینه سازی گسسته (Discrete Optimization Problems) و به مدل‌هایی که برای بهینه سازی متغیرهای پیوسته مورد استفاده قرار می‌گیرند، مدل‌های مسائل بهینه سازی پیوسته (Continuous Optimization Problems) گفته می‌شود.

حل کردن مسائل بهینه سازی پیوسته معمولا سخت‌تر از حل مسائل بهینه‌سازی گسسته است؛ از آنجایی که سطح توابع پیوسته هموار (Smooth) هستند، این امکان وجود دارد که از توابع هدف و قیدهای تعریف شده برای مقادیر متغیرها در نقطه $$X$$، جهت استنتاج اطلاعات مرتبط با نقاط موجود در همسایگی این نقطه استفاده کرد و از این طریق، مقادیر بهینه مسأله بهینه سازی پیوسته را پیدا کرد.

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

نکته مهم در مورد این دسته از مدل‌های بهینه سازی این است که مدل‌های پیوسته نقش مهمی در پیاده‌سازی مدل‌های بهینه سازی گسسته دارند. زیرا، بسیاری از مدل‌های بهینه‌سازی گسسته، مسائل بهینه سازی را به دنباله‌ای از زیر مسائل پیوسته (Continuous Subproblems) تقسیم‌بندی می‌کنند و برای حل کردن هر یک از این زیر مسائل، از مدل های بهینه سازی پیوسته استفاده می‌شود. بنابراین، یکی از مؤلفه‌های اساسی مدل‌های بهینه سازی گسسته، روش‌های حل مسائل بهینه‌سازی پیوسته هستند.

یکی از الگوریتم‌هایی که برای بهینه سازی مسائل پیوسته مورد استفاده قرار می‌گیرد، «الگوریتم بهینه‌سازی فاخته» (Cuckoo Optimization Algorithm) نام دارد. در ادامه، کدهای پیاده سازم این الگوریتم در زبان متلب نمایش داده شده است.

تابع هدف Rastrigin:

مسائل بهینه سازی «مقید» (Constrained) و بهینه سازی «نامقید» (Unconstrained)

از یک جهت دیگر نیز می‌توان میان مسائل و مدل‌های بهینه سازی قائل شد: مسائلی که هیچ قیدی روی متغیرها تعریف نمی‌کنند و مسائلی که برای متغیرها قید تعریف می‌‌کنند. درصد قابل توجه از مسائلی که در جهان واقعی با آن‌ها سروکار داریم، از نوع مسائل بهینه سازی نامقید هستند. در چند سال اخیر، مطالعات زیادی برای فرمول‌بندی دوباره (Re-Formulation) مسائل بهینه سازی نامقید در قالب مسائل بهینه سازی مقید ارائه شده است. در این مطالعات، از طریق جایگزین کردن قیدهای مسأله با «عبارات جریمه» (Penalty Terms)، یک مسأله بهینه سازی مقید به یک مسأله بهینه سازی نامقید تبدیل می‌شود.

مسائل بهینه سازی مقید مربوط به کاربردهایی هستند که در آن‌ها قیدهای صریحی (Explicit Constraints) رو متغیرهای مسأله تعریف شده است. قیدهای تعریف شده روی این دسته از مثال می‌توانند کران‌های (Bounds) ساده و یا سیستم‌هایی از معادلات و نامعادلات باشند که روابط میان متغیرهای مسأله را مدل می‌کنند.

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

مسائل بهینه سازی «قطعی» (Deterministic) و بهینه سازی «تصادفی» (Stochastic)

در مسائل بهینه سازی قطعی، فرض بر این است که داده‌های مسأله داده شده به طور دقیق شناخته شده هستند. با این حال و به دلایل مختلفی، داده‌های بسیاری از مسائل داده شده را به طور دقیق نمی‌توان شناخت (یا در اختیار داشت). اولین دلیل برای در دسترس نبودن داده‌های دقیق مسأله، «خطای اندازه‌گیری» (Measurement Error) داده‌ها است. دلیل دوم و بسیار مهم برای شناخته نبودن داده‌های مسأله این واقعیت است که برخی از داده‌ها، اطلاعات مرتبط با آینده را نمایش می‌دهند (نظیر تقاضا برای یک محصول یا قیمت یک محصول در آینده) که نمی‌توان با قطعیت (Certainty) آنها را شناخت.

در بهینه سازی همراه با عدم قطعیت (Optimization Under Uncertainty) یا بهینه سازی تصادفی (Stochastic Optimization)، عدم قطعیت در مدل ترکیب شده است. تکنیک‌های «بهینه سازی استوار» (Robust Optimization) تنها زمانی می‌توانند مورد استفاده قرار بگیرند که پارامترهای مسأله درون کران‌های مشخصی قرار گرفته باشند؛ در چنین حالتی، هدف پیدا کردن پیدا کردن جوابی است که به ازاء تمامی داده‌ها، امکان‌پذیر (یا قابل قبول) و به نحوی بهینه باشد.

مدل‌های بهینه سازی تصادفی (Stochastic Optimization)، از این واقعیت که «توزیع احتمالی» (Probability Distribution) حاکم بر داده‌ها مشخص و یا قابل تخمین است، بهره می‌برند؛ در چنین حالتی، هدف پیدا کردن یک سیاست (Policy) است که برای تمامی (یا تقریبا تمامی) نمونه‌های داده قابل قبول باشد و عملکرد مورد انتظار مدل (یا سیستم) را بهینه سازی کند.

مسائل بهینه سازی بدون هدف، تک هدفه و چند هدفه

بیشتر مسائل بهینه‌سازی، از یک تابع هدف برخوردار هستند. با این حال، مسائل بهینه سازی جالبی می‌توان پیدا کرد که یا هیچ تابع هدفی ندارند و یا از چندین تابع هدف برخوردار هستند. «مسائل امکان‌پذیری» (Feasibility Problems) مسائلی هستند که در آن‌ها، هدف پیدا کردن مقادیری برای متغیرها است که قید‌های مدل را ارضا کنند؛ در چنین حالتی مدل، تابع هدف خاصی ندارد که بخواهد آن را بهینه سازی کند. «مسائل مکملی» (Complementarity Problems)، مسائل بسیار فراگیری در مهندسی و اقتصاد محسوب می‌شوند؛ در چنین مواردی، هدف مدل‌های بهینه سازی پیدا کردن جوابی است که «شرایط مکملی» (Complementarity Conditions) مسأله را ارضا کند.

«مسائل بهینه سازی چند هدفه» (Multi-Objective Optimization Problems) در بسیاری از حوزه‌های علمی و کاربردی نظیر مهندسی، اقتصاد و «لجستیک» (Logistics) کاربرد دارند و زمانی مورد استفاده قرار می‌گیرند که برای رسیدن به تصمیمات بهینه در سیستم، نیاز است میان دو یا چند «هدف متناقض» (Conflicting Objectives) موازنه برقرار شود. به عنوان نمونه، توسعه یک مؤلفه جدید ممکن است نیازمند کمینه کردن وزن و به طور همزمان، بیشینه کردن قدرت باشد. همچنین، جهت انتخاب سبد سرمایه‌گذاری مناسب باید به نحوی عمل کرد که بازگشت مورد انتظار سرمایه، بیشینه و ریسک سرمایه گذاری، کمینه گردد.

در عمل، برای بهینه سازی مسائل چند هدفه، از راهکارهایی استفاده می‌شود که در آن‌ها، مسائل چند هدفه (Multi-Objective) به مسائل تک هدفه (Single-Objective) تبدیل می‌شوند؛ در این دسته از راهکارها، از طریق تشکیل یک ترکیب وزن‌دار از توابع هدف مختلف و یا به وسیله جایگزین کردن توابع هدف با قیدهای مشخص، مسائل بهینه سازی چند هدفه به مسائل تک هدفه تبدیل می‌شوند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

telegram
twitter

مرتضی جادریان

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

بر اساس رای ۱ نفر

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

برچسب‌ها