{ "cells": [ { "cell_type": "markdown", "id": "5a3ba2b9", "metadata": {}, "source": [ "Лицензия MIT\n", "\n", "© Алексей Александрович Щербаков, 2024" ] }, { "cell_type": "markdown", "id": "00ffec2d", "metadata": {}, "source": [ "# Лекция 5.2. Стохастическая оптимизация\n", "\n", "Градиентные методы, упомянутые на предыдущей лекции, хорошо работают в ситуация, когда имеется хорошее приближение к глобальному экстремуму, или же когда у целевой функции имеется достаточно большое количество локальных экстремумов, которые, тем не менее, являются удовлетворительными решениями рассматриваемой практической задачи. Последний аргумент обуславливает частое использование таких детерминистских методов на практике. Однако бывают ситуации, когда хорошее начальное приближение неизвестно, и перебор решений, получаемых на основании различных начальных данных оказывается слишком ресурсоемким. В этих ситуациях применяются различные стохастические алгоритмы оптимизации, которые, аналогично детерминистским, могу использовать или не использовать информацию о градиентах целевой функции. В отличие от детерминистских методов, где расчет градиента лучше использовать, где это возможно, существует ряд популярных стохастических подходов, основанных только на оценке самой целевой функции, нашедших широкое применение. На данной лекции рассмотрим такие методы.\n", "\n", "Под стохастичностью подразумеватся, что при решении оптизационной задачи возникает расчет случайных величин, либо в целевой функции, либо в рамках алгоритма. Случайность в целевой функции подразумевает, что оценка возможных решений допускает неопределенность или шум. Случайность в алгоритме применяется с целью повыщения вероятности нахождения глобальных оптимумов или лучших локальных оптимумов.\n", "\n", "Алгоритмы локальной оптимизации при наличии шума включают методы случайного поиска (Random Search, Stochastic Hill Climbing), стохастический градиентный поиск (SGD) и его различные модификации (например, Adam, RMSprop, Adagrad), стохастические квазиньютоновские методы (oLBFGS, SQN). Часть этих методов для некоторых задач позволяет эффективно находить и глобальные экстремумы. В целом, для поиска глобальных оптимумов применяются другие методы, включающие эволюционные алгоритмы (генетические алгоримы, дифференциальная эволюция), методы роя частиц (Particle Swarm Optimization), методы колонии муравьёв (Ant Colony Optimization), стохастический имитационный отжиг (Simulated Annealing). К безградиентным методам относятся методы случайного поиска и эволюционные стратегии.\n", "\n", "В отношении оптических и фотонных устройств наборы оптимизируемых параметров, как правило, включают геометрию и физические параметры задачи, а целевые функции должны учитывать требуемый функционал, что иллюстративно показано на рисунке ниже.\n", "\n", "
\n", "\n", "
Проектирование оптических систем.

\n", "
\n" ] }, { "cell_type": "markdown", "id": "ab869914", "metadata": {}, "source": [ "## Некоторые алгоритмы стохастической оптимизации\n", "\n", "### Генетические алгоритмы\n", "\n", "Идея генетических алгоритмов, как и других эволюционных алгоритмов основана имитации естественного отбора. Здесь к векторам оптимизируемых параметров применяются такие операции как скрещивание (кроссовер), мутации и отбор. Сами векторы называются векторами генов (генотипы), так что каждый элемент может битом, числом или некоторым объектом. Алгоритм инициализируется набором случайно заданных генотипов, которые оцениваются с помощью целевой функции (здесь используется название функция приспособленности). Затем с учетом значения приспособленности выбираются наилучшие решения, к которым применяются операции скрещивания и мутации, в результате чего получаются новые решения. Для этих новых решений вычисляется функция приспособленности и осуществляется селекция в новое поколение. Затем процесс повторяется.\n", "\n", "
\n", "\n", "
Иллюстрация шагов генетического алгоритма.

\n", "
\n", "\n", "### Эволюционные стратегии\n", "\n", "Основное отличие эволюционных стратегий от генетических алгоритмов - оперирование векторами действительных чисел. При поиске решения сначала применяется мутация и скрещивание, а затем - детерминированный отбор из поколения потомков (и, возможно, родителей). Мутация зачастую представляет собой добавление нормально распределенной случайной величины к каждой компоненте вектора. В алгоритмах дифференциальной эволюции применяется гибридный подход, в котором новые особи получается через линейную комбинацию существующих.\n", "\n", "### Метод роя\n", "\n", "В методах роя кадый элемент вектора оптимизируемых параметров сопоставляется с положением некоторой частице. Также каждая частица роя имеет некотороую скорость. На каждом шаге происходит сдвиг частиц в новое положение, вычисление целевой функции для частиц роя, сопоставление наилучших состояний каждой отдельной частицы и всех частиц с текущими значениямим на основании значений целевой функции, а также обновление скоростей частиц в зависимости от их состояния.\n", "\n", "
\n", "\n", "
Иллюстрация метода роя частиц.

\n", "
" ] }, { "cell_type": "markdown", "id": "6a6acd51", "metadata": {}, "source": [ "#### Литература\n", "\n", "1. Fouskakis, D., Draper, D. [Stochastic Optimization: a Review. International Statistical Review](https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1751-5823.2002.tb00174.x), 70(3), 315–349 (2002)\n", "2. [Introduction to Genetic Algorithms in Python](https://algodaily.com/lessons/introduction-to-genetic-algorithms-in-python)\n", "3. Rasmus E. Christiansen and Ole Sigmund, [Inverse design in photonics by topology optimization: tutorial](https://opg.optica.org/josab/fulltext.cfm?uri=josab-38-2-496&id=446780), J. Opt. Soc. Am. B 38, 496-509 (2021)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.8" } }, "nbformat": 4, "nbformat_minor": 5 }