Все известные мне алгоритмы оптимизации для функций черного ящика, такие как имитация отжига или Байесовская оптимизация возвращает глобальный минимум.
Я ищу алгоритм Python, который возвращает мне глобальные а также все локальные минимумы.
Есть ли алгоритм, решающий эту задачу?
Или существует ли какой-либо из алгоритмов глобального минимума, который также возвращает локальные минимумы?
Или есть какие-либо алгоритмы глобального минимума, которые возвращают также локальные минимумы?
Я не понимаю, что вы подразумеваете под глобальными минимальными алгоритмами, но поскольку вы упомянули симулированный отжиг, я предполагаю, что вы говорите о метаэвристике с возможностями глобального поиска.
Нет никакой гарантии, что метаэвристика, очень часто используемая для решения NP-сложных задач, будет исследовать все пространство поиска, следовательно, нет гарантии, что будут найдены все локальные минимумы. Тем не менее, я предполагаю, что вы это знаете, и что вы хотите, так это изменить метод таким образом, чтобы он предоставлял, а не только одно решение (наилучшее из найденных), список локальных минимумов, найденных во время процедуры поиска глобальных минимумов.
Алгоритмы на основе единого решения, такие как поиск с запретом, повторный локальный поиск и т. д., работают на основе локального поиска. Они выполняют локальный поиск до тех пор, пока не найдут локальное оптимальное решение, а затем применяют свои собственные соответствующие правила, чтобы попытаться избежать локальных минимумов. Давайте рассмотрим повторный локальный поиск, он выполняет локальный поиск до тех пор, пока решение S не станет локально оптимальным, затем он искажает текущие локальные оптимумы, чтобы выйти из него и получить другую точку в пространстве поиска, чтобы снова выполнить локальный поиск, пока не будет выполнен критерий. . В вашем случае следует каждый раз сохранять локально оптимальное решение, найденное в процессе поиска.
Приведенный ниже псевдокод представляет собой модифицированный алгоритм ILS, чтобы сохранить все локально оптимальные решения, найденные в ходе процедуры поиска.
HillClimbing(S)
while S is not locally optimal do
S ← best(N(S)) // best solution in neighborhood N of solution S
Return S
IteratedLocalSearch()
L ← {} // set of locally optimal solutions
G ← randomSolution()
S ← G
while criterionIsNotMeet() do
HillClimbing(S)
Add S to L // add the current local
if S.objective < G.objective do // minimization
G ← S // best solution found
perturbateSolution(Copy(S))
Такие алгоритмы могут быть легко реализованы. Если вы решите реализовать себя, получите хороший справочный документ, если этого недостаточно, вы можете попытаться найти хорошую реализацию на GitHub или Mathworks Discovery, чтобы основывать свое кодирование.
