GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.1 (3)След. > >>   Поиск:  
 Автор Тема: Генетические алгоритмы. Определение глобального екстремума функции.
гость
87.123.61.*
Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 02 дек 07 5:06
Доброе время суток
Есть вопросик.

Надо оптимизировать с заданой погрешностью многоэкстремальную функцию при помощи генетического алгоритма.

Разбил область исследований сеткой так:
max|Х2-Х1|<MaxError

Прогу написал. Работает и сходится.

Можно ли математически или алгоритмически определить качество найденного решения? Т.е. как ТОЧНО узнать, находится ли "кто-то" из популяции в глобальном екстремуме или нет?

Время не имеет значения(в разумных пределах, конечно).

Если не отошлю работу завтра, останутся от меня рожки да ножки. Незнаю что делать.
Заранее спасибо.
[Ответ][Цитата]
mserg
Сообщений: 258
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 02 дек 07 12:19
Ну, что ж, надеюсь, завещание уже написано?

Где сама функция то? Можно или нет найти глобальный оптимум за разумное время зависит от вида функции, количества переменных и т.д. Если переменных не так много – то можно использовать интервальный анализ. Короче, задачу - в студию!
[Ответ][Цитата]
daner
Сообщений: 4593
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 02 дек 07 13:35
А функция, "от-фени" заданна? или это все-таки задача какая-то?
А вообще, все зависит от самой функции. Если у нее производная не сложная, то возможно экстремумы можно и руками найти, ну а потом проверить, которая из них самая большая.
Впрочем, много-параметровые производные, дело хитрое.
[Ответ][Цитата]
Wolodimir
Сообщений: 6
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 02 дек 07 14:18
Прошу прощения за коряво сформулированную задачу.

Дано:
Целевая функция - Rastrigin''s function
Количество переменных - 2
Интервал поиска - A1=A2={-5.12; 5.12}
"Разумный предел" затраченного времени - это такое время, когда "метод интервалов", как вы выразились, остается хотя бы на порядок медленнее.
-------------------------------------
Найти оптимум
-------------------------------------

Задача, конечно, тривиальная. Но вот критерий оптимума не задан. Т.е. в условии отсутствует значение F*(Х) такое, что все Х*, при которых F*(Х)<=F(Х*), могли бы считаться удовлетворительным решением.

В связи с этим возникает вопрос: можно ли качественно отличить глобальный экстремум от локального, не видя графика функции?
[Ответ][Цитата]
mserg
Сообщений: 258
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 02 дек 07 17:11
Генетический алгоритм не обеспечивает оценку расстояния до оптимума, поэтому фраза «нужно найти оптимум с заданной точностью с помощью генетического алгоритма» - АБСУРД. Но, не суть...

Если же нужно ПРОВЕРИТЬ, находит ли генетический алгоритм на данном конкретном примере оптимум с заданной точностью – то это другое дело. Для этого нужно решить задачу «точным» способом с высокой точностью и использовать это решения для проверки ГА.

Заметим, что функция Растригина имеет ограниченную производную и она сепарабельна по переменным, а переменных x1 и x2 симметрично входят в функцию. Поэтому, пройдясь по сетке значений x1 (x2 выбирается равным x1) можно найти глобальный оптимум с определенной точностью. Шаг сетки выбирается в зависимости от требуемой точности оптимума и от максимума модуля производной оптимизируемой функции.

Интервальный анализ (а не "метод интервалов") - штука нетривиальная. Например, есть библиотека PROFIL/BIAS. Если сможете ее откомпилировать, то там можете подставить свою функцию в пример – система найдет глобальный оптимум.
[Ответ][Цитата]
Wolodimir
Сообщений: 6
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 03 дек 07 23:48
>Интервальный анализ (а не "метод интервалов")...

прошу прощения.

>Генетический алгоритм не обеспечивает оценку расстояния до оптимума,...

верно

>поэтому фраза «нужно найти оптимум с заданной точностью с помощью генетического алгоритма» - АБСУРД. Но, не суть...

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

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

При даном условии задачи мне не видится другой возможности оценивать качество найденных решений.
[Ответ][Цитата]
mserg
Сообщений: 258
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 04 дек 07 21:26
Да, вероятность, конечно есть. Я даже могу дать оценку для задачи с двумя переменными: это примерно 1e-30 ...
Не верите? Ну, добавьте одно исключение в своей функции: при x1=1.2883746653 и x2=-0.92887465653 функция должна принять значение -100000000000000000. Скорее компьютер исчерпает свой ресурс, чем будет найден минимум.
[Ответ][Цитата]
гость
176.36.117.*
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 07 дек 17 16:59
Цитата:
Автор: гость

Доброе время суток
Есть вопросик.

Надо оптимизировать с заданой погрешностью многоэкстремальную функцию при помощи генетического алгоритма.

Разбил область исследований сеткой так:
max|Х2-Х1|<MaxError

Прогу написал. Работает и сходится.

Можно ли математически или алгоритмически определить качество найденного решения? Т.е. как ТОЧНО узнать, находится ли "кто-то" из популяции в глобальном екстремуме или нет?

Время не имеет значения(в разумных пределах, конечно).

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

вопрос можно поставить по другому: Как оценить качество алгоритма оптимизации? Чем один хуже другого? Ну, то есть всем понятно, нужно чтобы минимальным количеством сэмплов нашел глобальный экстремум, но количественно что это за метрика? Как количественно сравнить отжиг и генетику?
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 07 дек 17 17:08
Коллекция плохих функций
https://en.wikipedia.org/wiki/Test_functions_for_optimization
[Ответ][Цитата]
АMS
Сообщений: 498
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 07 дек 17 17:51
зашыбись....

ебстрэмум...

етим фсё сказано.
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 07 дек 17 18:37
Это не про мышление, а когда решение уже есть. Чтобы просто работало побыстрее и ошибка была меньше. Обычно такое считают единственно-интеллектуальным те, кто и это сделать не может. Для них оно заумное и всемогущее. Тут часто кто сам чего не умеет, то и считает нужным повесить на машину.
[Ответ][Цитата]
гость
176.36.117.*
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 08 дек 17 13:32
Цитата:
Автор: NO.

Коллекция плохих функций
https://en.wikipedia.org/wiki/Test_functions_for_optimization
Нет, это не совсем то что я имел в виду. Нужен метрический функционал, точнее алгоритм измерения оптимизационных алгоритмов, на входе алгоритм на выходе некая мера его крутизны.
[Ответ][Цитата]
Victor G. Tsaregorodtsev
Сообщений: 3187
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 10 дек 17 11:02
Цитата:
Автор: гость
Нужен метрический функционал, точнее алгоритм измерения оптимизационных алгоритмов, на входе алгоритм на выходе некая мера его крутизны.

Дык, вроде же 20 лет назад доказали вот это:
https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 10 дек 17 11:35
Да там вообще не сравнимо, например алгоритм1 не находит максимум если начинает к нему двигаться из точки (0,1), а алгоритм2 если из точки (1,0). В остальном одинаковы. И который из них лучше?
[Ответ][Цитата]
гость
185.47.62.*
На: Генетические алгоритмы. Определение глобального екстремума функции.
Добавлено: 01 мар 18 15:47
Цитата:
Автор: Victor G. Tsaregorodtsev


Дык, вроде же 20 лет назад доказали вот это:
https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization
Как "это" можно "доказать"? Всё равно что доказать "бритву Оккама"
[Ответ][Цитата]
 Стр.1 (3): [1]  2  3След. > >>