Привет.

Подскажите каким методом лучше всего находить минимум функции, которая имеет такой вид:



Из-за кучи локальных минимумов градиентные методы отпадают. Склоняюсь к генетическому алгоритму, но не будет ли это стрельбой из пушки по воробьям?

Здравствуйте, Jenyay, Вы писали:

J>Привет.

J>Подскажите каким методом лучше всего находить минимум функции, которая имеет такой вид:

J>

J>Из-за кучи локальных минимумов градиентные методы отпадают. Склоняюсь к генетическому алгоритму, но не будет ли это стрельбой из пушки по воробьям?

Нет, не будет, если удастся быстро получить решение задачи.

Для таких функций хорошо подходит т.н. метод численного отжига (это не стеб, это дурацикй, но укоренившийся перевод термина simulated annealing). Это некий симбиоз метода Монте-Карло с градиентным методом. Один из вариантов в одномерном случае заключается в следующем.

Представим, что в эту чашку с зазубринами, которую обрисовывает функция, кинули тяжелый шарик. На шарик действует сила тяжести, вязкого трения и хаотическая сила, которая его периодически "пинает". Вот собственно, и все. Подбирая масштабы времени затухания движения, частоту "пинков", а так же абсолютные значения сил, почти всегда можно добиться, что в результате численного интегрирования шарик закатится в самую глубокую яму.

Для повышения эффективности я использовал "порождение" новых шариков от тех, которые уже скатились достаточно глубоко. Здесь, по-моему, это излишне.

Могу поискать маткадовский файл с примером.

P.S. У функции такой вид, как будто это результат какого-то поточечного расчета, который из-за влияния численных погрешностей получается зашумленным. Может быть, ее можно просто и нахально сгладить?

Здравствуйте, volk, Вы писали:

V>P.S. У функции такой вид, как будто это результат какого-то поточечного расчета, который из-за влияния численных погрешностей получается зашумленным. Может быть, ее можно просто и нахально сгладить?

Вот мне тоже так показалось. Но в этом случае непонятно, что мешает пробежаться по всем точкам?

Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, volk, Вы писали:

V>>P.S. У функции такой вид, как будто это результат какого-то поточечного расчета, который из-за влияния численных погрешностей получается зашумленным. Может быть, ее можно просто и нахально сгладить?

V_>Вот мне тоже так показалось. Но в этом случае непонятно, что мешает пробежаться по всем точкам?

Возможно, это был демонстрационный пример, где сетка значений гуще, чем в расчете, а каждое вычисление функции стоит дорого. (RSDN Telepathy team )

Здравствуйте, Jenyay, Вы писали:

J>Привет.

J>Подскажите каким методом лучше всего находить минимум функции, которая имеет такой вид:

J>

J>Из-за кучи локальных минимумов градиентные методы отпадают. Склоняюсь к генетическому алгоритму, но не будет ли это стрельбой из пушки по воробьям?
Можно попробовать использовать метод Монте-Карло. Кидаем на ось равномерно распределенные точки и затем выбираем минимальное значение функции. Это очень упрощенный алгоритм. Этим методом вообще говоря удобно считать интегралы. Но я делал курсовую именно по этому методу и именно для поиска экстремумов.

Здравствуйте, volk, Вы писали:

V>Нет, не будет, если удастся быстро получить решение задачи.

V>Для таких функций хорошо подходит т.н. метод численного отжига (это не стеб, это дурацикй, но укоренившийся перевод термина simulated annealing). Это некий симбиоз метода Монте-Карло с градиентным методом. Один из вариантов в одномерном случае заключается в следующем.

Название встречалось, но там не рассказывалось в чем состоит метод.

V>Представим, что в эту чашку с зазубринами, которую обрисовывает функция, кинули тяжелый шарик. На шарик действует сила тяжести, вязкого трения и хаотическая сила, которая его периодически "пинает". Вот собственно, и все. Подбирая масштабы времени затухания движения, частоту "пинков", а так же абсолютные значения сил, почти всегда можно добиться, что в результате численного интегрирования шарик закатится в самую глубокую яму.

V>Для повышения эффективности я использовал "порождение" новых шариков от тех, которые уже скатились достаточно глубоко. Здесь, по-моему, это излишне.

V>Могу поискать маткадовский файл с примером.

Было бы по крайней мере любопытно. Можешь прислать на jenyay.ilin {at} gmail.com?

V>P.S. У функции такой вид, как будто это результат какого-то поточечного расчета, который из-за влияния численных погрешностей получается зашумленным. Может быть, ее можно просто и нахально сгладить?

Это функция, которая показывает ошибку между реальным отраженным сигналом и модельным рассчитываемым.

Здравствуйте, Vintik_69, Вы писали:

V_>Вот мне тоже так показалось. Но в этом случае непонятно, что мешает пробежаться по всем точкам?

Сейчас минимум и ищется перебором. Работает примерно минуту, но еще есть моменты, которые можно ускорить. Реально будет работать раза в два быстрее, но не хотелось бы действовать таким ломовым способом, и надеюсь, что нормальный метод и ускорит решение.

Здравствуйте, jeep, Вы писали:

J>Можно попробовать использовать метод Монте-Карло. Кидаем на ось равномерно распределенные точки и затем выбираем минимальное значение функции. Это очень упрощенный алгоритм. Этим методом вообще говоря удобно считать интегралы. Но я делал курсовую именно по этому методу и именно для поиска экстремумов.

Можно попробовать. Просто надеялся, что есть какой-нибудь менее случайный алгоритм.

Здравствуйте, Jenyay, Вы писали:

J>Здравствуйте, jeep, Вы писали:

J>>Можно попробовать использовать метод Монте-Карло. Кидаем на ось равномерно распределенные точки и затем выбираем минимальное значение функции. Это очень упрощенный алгоритм. Этим методом вообще говоря удобно считать интегралы. Но я делал курсовую именно по этому методу и именно для поиска экстремумов.

J>Можно попробовать. Просто надеялся, что есть какой-нибудь менее случайный алгоритм.
Я привел, опять же повторяю, очень упрощенный алгоритм. Это очень точный метод. Подчеркиваю очень точный. Его точность уменьшается с ростом размерности функции. В основном он очень удобен для n — мерных функций интегрирование и дифференцирвание которых усложнено другими методами(например численное дифференцирование дает большие погрешности,как в прочем и интегрирование). А этот метод в твоем случае может дать 10^-9 — -10 степень точности (даже по алгоритму который я написал)очень за короткое время(мгновенно). Можешь сам усовершенствовать его заглянув в учебник по статистике или по численным методам. В инете я не нашел много матерьяла по нахождению экстремумов этим методом. Но по интегрированию навалом.

Здравствуйте, <Аноним>, Вы писали:

А>Я привел, опять же повторяю, очень упрощенный алгоритм. Это очень точный метод. Подчеркиваю очень точный. Его точность уменьшается с ростом размерности функции. В основном он очень удобен для n — мерных функций интегрирование и дифференцирвание которых усложнено другими методами(например численное дифференцирование дает большие погрешности,как в прочем и интегрирование). А этот метод в твоем случае может дать 10^-9 — -10 степень точности (даже по алгоритму который я написал)очень за короткое время(мгновенно). Можешь сам усовершенствовать его заглянув в учебник по статистике или по численным методам. В инете я не нашел много матерьяла по нахождению экстремумов этим методом. Но по интегрированию навалом.

Ок. Возможно попробую и его

Здравствуйте, Jenyay, Вы писали:

J>Здравствуйте, volk, Вы писали:

V>>Могу поискать маткадовский файл с примером.
J>Было бы по крайней мере любопытно. Можешь прислать на jenyay.ilin {at} gmail.com?
Отправил.
Файлы для Mathcad12 и 13.

На стенки "чашки" кидается несколько шариков, которые сползают к ближайшим локальным минимумам. Кинетическая энергия падает за счет трения -- поэтому они в конце концов и останавливаются. Инерция шариков дает им возможность "давить" мелкие шероховатости; подбирая эмпирический коэффициент массы и трения, можно добиться разной степени фильтрации.

Собственно расчет состоит в интегрировании уравнений движения простейшим методом Эйлера.

Функция переделана так, чтобы быть хотя бы слегка похожей на то, что нарисовал ты.

На основе этого примера была написана (не мной) программа, которая отлавливала пики на зашумленном спектре.

Будут вопросы -- спрашивай.

З.Ы. Посмотрев на этот расчет выпуклым взглядом, я что-то стал сильно сомневаться, что он будет работать быстрее, чем поточечный пробег, в который он может быть превращен при вырожденных параметрах.
Вот здесь приведена классификация всяких методов минимизации и куча ссылок. Но, опять же, эти методы предназначены для многомерной оптимизации. Большинство из них не дает особого выигрыша в одномерном случае.

Здравствуйте, volk, Вы писали:

V>Отправил.
V>Файлы для Mathcad12 и 13.

V>На стенки "чашки" кидается несколько шариков, которые сползают к ближайшим локальным минимумам. Кинетическая энергия падает за счет трения -- поэтому они в конце концов и останавливаются. Инерция шариков дает им возможность "давить" мелкие шероховатости; подбирая эмпирический коэффициент массы и трения, можно добиться разной степени фильтрации.

V>Собственно расчет состоит в интегрировании уравнений движения простейшим методом Эйлера.

V>Функция переделана так, чтобы быть хотя бы слегка похожей на то, что нарисовал ты.

V>На основе этого примера была написана (не мной) программа, которая отлавливала пики на зашумленном спектре.

V>Будут вопросы -- спрашивай.

V>З.Ы. Посмотрев на этот расчет выпуклым взглядом, я что-то стал сильно сомневаться, что он будет работать быстрее, чем поточечный пробег, в который он может быть превращен при вырожденных параметрах.
V>Вот здесь приведена классификация всяких методов минимизации и куча ссылок. Но, опять же, эти методы предназначены для многомерной оптимизации. Большинство из них не дает особого выигрыша в одномерном случае.

Спасибо, покопаюсь

Здравствуйте, Jenyay, Вы писали:

J>Подскажите каким методом лучше всего находить минимум функции, которая имеет такой вид:

посмотри еще метод отжига. може немного быстрее ГА будет