بهینه‌سازی مدرج

بهینه‌سازی مدرج یک تکنیک بهینه‌سازی سراسری است که سعی می‌کند در ابتدا یک مسئله بهینه‌سازی دشوار را، با حل یک مسئله بسیار ساده‌شده حل کند، و به تدریج آن مسئله را (در حین بهینه‌سازی) تغییر دهد تا اینکه به یک مسئله ای، معادل مسئله دشوار تبدیل شود.^[۱]^[۲]^[۳]

توضیحات تکنیک

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

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

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

چند نمونه

بهینه‌سازی مدرج، معمولاً در زمینه پردازش تصویر، برای مکان‌یابی اشیائی که در یک تصویر بزرگ هستند، استفاده می‌شود. می‌توان این مسئله را با تار کردن تصاویر محدب تر کرد؛ یعنی می‌توانیم اشیاء را با جستجو در تارترین تصویر تشخیص دهیم، سپس برای یافتن جواب نهایی، از این نقطه در تصویر شروع کنیم و در تصویری با تاری کمتر جستجو را دنبال می‌کنیم، و به همین صورت ادامه می‌دهیم تا شیء در تصویر واضح اصلی قرار گیرد. انتخاب مناسب عملگر تاری، وابسته است به تبدیل هندسی وابسته به شیء در یک تصویر به تصویر دیگر.^[۴]

بهینه‌سازی مدرج همچنین می‌تواند در یادگیری چندگانه مورد استفاده واقع شود. برای مثال، الگوریتم شکل داده شده چندگانه (Manifold Sculpting)، از بهینه‌سازی مدرج برای جستجوی تعبیه چندگانه برای کاهش ابعاد غیرخطی استفاده می‌کند.^[۵] این الگوریتم، به تدریج در یک مجموعه داده، واریانس ابعاد اضافی را کاهش می‌دهد و بهینه‌سازی در ابعاد باقی مانده انجام می‌شود. همچنین بهینه‌سازی مدرج، برای محاسبه شرایط تفکیک با تومورها،^[۶] برای ردیابی اشیاء در بینایی ماشین،^[۷] و اهداف دیگر نیز استفاده شده‌است.

یک بررسی کامل از روش‌ها کاربردهای آن را می‌توان در^[۳] یافت.

تکنیک‌های بهینه‌سازی مرتبط

تبرید شبیه‌سازی شده ارتباط نزدیکی با بهینه‌سازی مدرج دارد. این الگوریتم، به جای اینکه تابعی را که بر روی آن بهینه‌سازی انجام می‌شود، هموارسازی کند، به‌طور تصادفی، راه حل فعلی را با مقدار تباهیده مختل می‌کند، که ممکن است اثر مشابهی داشته باشد.^{^{[نیازمند منبع]}} از آنجایی که تبرید شبیه‌سازی شده، به نمونه‌گیری تصادفی برای بهبود، متکی است، با این حال، پیچیدگی محاسباتی آن از نظر تعداد ابعاد بهینه‌سازی شده، نمایی است.^{^{[نیازمند منبع]}} در مقابل، بهینه‌سازی مدرج تابع بهینه‌سازی شده را هموار می‌کند، بنابراین تکنیک‌های بهینه‌سازی موضعی که در فضای با ابعاد بالا کارآمد هستند (مانند تکنیک‌های مبتنی بر گرادیان، الگوریتم‌های تپه‌نوردی و غیره) همچنان می‌توانند مورد استفاده واقع شوند.

جستارهای وابسته

ادامه عددی

منابع

↑ «Multi-Resolution Methods and Graduated Non-Convexity». homepages.inf.ed.ac.uk. دریافت‌شده در ۲۰۲۲-۱۱-۲۰.
↑ Blake, Andrew; Zisserman, Andrew (1987). Visual Reconstruction. MIT Press. شماره استاندارد بین‌المللی کتاب 0-262-02271-0
↑ ^۳٫۰ ^۳٫۱ Hossein Mobahi, John W. Fisher III. On the Link Between Gaussian Homotopy Continuation and Convex Envelopes, In Lecture Notes in Computer Science (EMMCVPR 2015), Springer, 2015.
↑ Hossein Mobahi, C. Lawrence Zitnick, Yi Ma. Seeing through the Blur, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2012.
↑ Gashler, M. ; Ventura, D. ; Martinez, T. (2008). "Iterative Non-linear Dimensionality Reduction with Manifold Sculpting" (PDF). In Platt, J. C. ; Koller, D. ; Singer, Y. ; et al. (eds.). Advances in Neural Information Processing Systems 20. Cambridge, MA: MIT Press. pp. 513–20.
↑ Afanasjev, BP; Akimov, AA; Kozlov, AP; Berkovic, AN (1989). "Graduated optimization of fractionation using a 2-component model". Radiobiologia, Radiotherapia. 30 (2): 131–5. PMID 2748803.
↑ Ming Ye; Haralick, R.M.; Shapiro, L.G. (2003). "Estimating piecewise-smooth optical flow with global matching and graduated optimization". IEEE Transactions on Pattern Analysis and Machine Intelligence. 25 (12): 1625–30. doi:10.1109/TPAMI.2003.1251156.

[1] «Multi-Resolution Methods and Graduated Non-Convexity». homepages.inf.ed.ac.uk. دریافت‌شده در ۲۰۲۲-۱۱-۲۰.

[2] Blake, Andrew; Zisserman, Andrew (1987). Visual Reconstruction. MIT Press. شماره استاندارد بین‌المللی کتاب 0-262-02271-0

[mobahi2015-3] ۳٫۰ ^۳٫۱ Hossein Mobahi, John W. Fisher III. On the Link Between Gaussian Homotopy Continuation and Convex Envelopes, In Lecture Notes in Computer Science (EMMCVPR 2015), Springer, 2015.

[4] Hossein Mobahi, C. Lawrence Zitnick, Yi Ma. Seeing through the Blur, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2012.

[5] Gashler, M. ; Ventura, D. ; Martinez, T. (2008). "Iterative Non-linear Dimensionality Reduction with Manifold Sculpting" (PDF). In Platt, J. C. ; Koller, D. ; Singer, Y. ; et al. (eds.). Advances in Neural Information Processing Systems 20. Cambridge, MA: MIT Press. pp. 513–20.

[6] Afanasjev, BP; Akimov, AA; Kozlov, AP; Berkovic, AN (1989). "Graduated optimization of fractionation using a 2-component model". Radiobiologia, Radiotherapia. 30 (2): 131–5. PMID 2748803.

[7] Ming Ye; Haralick, R.M.; Shapiro, L.G. (2003). "Estimating piecewise-smooth optical flow with global matching and graduated optimization". IEEE Transactions on Pattern Analysis and Machine Intelligence. 25 (12): 1625–30. doi:10.1109/TPAMI.2003.1251156.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]