Бесплатного обеда не бывает

[kaipa]

В аспирантуре я занимался проблемами нелинейной оптимизации. Самый общий и простой метод оптимизации (или поиска экстремума целевой функции, что одно и то же) в нелинейных задачах -- это метод Монте-Карло или просто случайный поиск. К нему можно добавить некоторый статистический аппарат, чтобы оценивать точность оптимизации. Был соблазн попробовать генетические алгоритмы (ГА), в то время они были новы и довольно популярны. Я накупил кучу книжек, которые рассказывали, как здорово некоторые задачи решались при помощи ГА. Реализовал алгоритм, который работал, но не давал каких-то выдающихся результатов по сравнению со случайным поиском. А потом, рецензируя статьи по этой тематике, наткнулся на теорему, осознание которой полностью отвратило меня от всякий экспериментов с ГА, во всяком случае для тех задач, которые тогда ставились. Речь идет о теореме "Бесплатного обеда не бывает" -- No Free Lunch Theorem (NFL). Может быть, на русский это лучше перевести, как "бесплатного сыра не бывает", но название теоремы пришло из одного конкретного примера.

Смысл теоремы в том, что не существует алгоритма (поиска или оптимизации), который "работает" лучше других на всем множестве задач (я намеренно употребляю такие расплывчатые формулировки, но на самом деле условия применимости теоремы весьма широки). Если некоторый алгоритм работает лучше (быстрее, точнее) на одних задачах, значит, на других задачах он будет хуже. Теорема имеет принципиальное значение. Если взять весь класс задач, к которому применим конкретный алгоритм, то он будет не лучше, чем просто случайный поиск. А зачем тогда усложнять? :) Конечно, есть специфические задачи, которые можно решать специфическими алгоритмами, подобранными для этих задач, но обобщить способ "подбора" невозможно.

Интересно, что NFL оказывается тесно связана с Колмогоровской сложностью.

http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization

Comments

Re: Продолжаю не соглашаться.

[imageman72.livejournal.com]

что касается мутаций, то они пусть редко, но всё-таки двигают человечество вперед.

К примеру 10 тысяч лет назад взрослые люди не могли усваивать молоко. Однако позже в геноме людей (в разных племенах в разное время) произошли мутации, которые позволили взрослым усваивать молоко. http://www.membrana.ru/print.html?1166028720 С тех пор эти мутированные гены встречаются часто, потому что закрепились в геноме как полезные.

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

> Нет ничего проще случайного поиска
Я не о простоте, а о скорости нахождения минимума (пусть и не глобального, а просто "хорошего").

Дадим одинаковое время разным людям: "найти самое маленькое значение у функции f(x)=....". При этом функцию подберем довольно сложную, да еще с ограничениями (как это часто бывает в жизни). Это может быть и поиск молекулы-катализатора химической реакции или нахождение формы манипулятора робота, который работает в быстром течении жидкости. Программист может выбирать любой метод решения задачи. Выиграет тот, кто за (к примеру) неделю выдаст наиболее хорошее решение.

Какой твой прогноз - кто выиграет? 1. Любитель Монте-карло. 2. Любитель ГА. 3. Любитель аналитических решений.

отдельно упомянем вариант "Программист, выбравший симбиоз методов A и B".

Мой прогноз:
a) при высокой сложности задачи аналитик почти не имеет шанса;
б) Монте-карло получит среднее(посредственное) решение, которое можно будет легко улучшить градиентным спуском
в) ГА получит хорошее решение
в случае, если программист сможет быстро(!) аналитически решить хоть часть задачи, то (вместе с ГА) он может получить отличное решение.

Твой прогноз, скорее всего, будет другой.

Что касается метода симуляции отжига, то я его пробовал. На сложных задачах он хуже.

Ты так и не сказал, на каких задачах получил лучший результат у Монте-Карло и более плохой у ГА.

Какой метод ты предпочитаешь, когда аналитически не можешь разобрать (решить) функцию?

Re: Продолжаю не соглашаться.

[ushastyi.livejournal.com]

Дадим одинаковое время разным людям: "найти самое маленькое значение у функции f(x)=....". При этом функцию подберем довольно сложную, да еще с ограничениями (как это часто бывает в жизни). Это может быть и поиск молекулы-катализатора химической реакции или нахождение формы манипулятора робота, который работает в быстром течении жидкости. Программист может выбирать любой метод решения задачи. Выиграет тот, кто за (к примеру) неделю выдаст наиболее хорошее решение.

Какой твой прогноз - кто выиграет? 1. Любитель Монте-карло. 2. Любитель ГА. 3. Любитель аналитических решений.


Аналитические решения не рассматриваем. Реальные нелинейные задачи с десятками, а то и сотнями размерностей аналитически не решаются.

В соответствии с теоремой о бесплатном обеде (с чего мы и начали), у 1 и 2 равные шансы при одинаковом времени работы (временем здесь является количество вычислений целевой функции). Но так как запрограммировать Монте-Карло гораздо проще и быстрее, чем ГА, то за неделю можно перебрать куда большее количество случайных вариантов и найти наименьший, чем с ГА, для которого придется писать программу (или использовать библиотеку) и подбирать коэффициенты. То есть Монте-Карло выиграет. Ведь казино выигрывает всегда :)

И это не прогноз, а научно доказанный факт. О чем и был мой пост.

Re: Продолжаю не соглашаться.

[imageman72.livejournal.com]

вот тут http://imageman72.livejournal.com/1235.html мною описана функция, на которой я тестировал

result:=14;
for I := 0 to 22 do if (x[i]<0) or (x[i]>1) then
x[i]:=random;

for I := 0 to 22-3 do begin
result:=result+sin(x[i]*i+x[i+1]+2*x[i+2])*sqr(x[i]);
end;

в моем случае методами ГА значение <0.3 найдено 4 раза из 10 запусков. ГА я специально под эту задачу не настраивал. Взял (несколько доработанный) компонент (библиотеку) для Дельфи.

Ради хохмы попробовал метод Монте-Карло. Делал 1 200 000 итераций (т.е. в 6 раз больше, нежели в ГА). Типичное "лучшее" решение было от 6.0 до 6.9. Это намного больше решения, которое было найдено методами ГА (ГА нашел решение <0.3)

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

Re: Продолжаю не соглашаться.

[ushastyi.livejournal.com]

Не совсем понял, что за функцию Вы исследуете. result -- это, я понимаю, значение? А переменная?

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

Кстати, немаловажно, что в случае с Монте-Карло довольно нетрудно оценить статистически с какой точностью и надежностью найден минимум (через порядковые статистики), то есть иметь оценку вроде "экстремум лежит в интервале (m1, m2) с вероятностью 0.99". С ГА это сделать гораздо сложнее. Нет никой зацепки насколько хорошо или плохо найденное решение.

будем рассматривать реальные задачи

[imageman72.livejournal.com]

result - это значения, а переменные, которые нужно найти - массив x (22 числа), причем переменные из диапазона [0..1]

> на всем классе допустимых задач поиска экстремума

это, видимо, главная ошибка. Сейчас, к примеру, большинство вычислений с плавающей запятой делаются с 19-20 значащих цифр. И мало кого волнуют, что можно делать вычисления с 1000 значащими цифрами. Так и тут: нужно рассматривать типичные, наиболее часто встречающиеся в жизни задачи, а не рассматривать "сферического коня в ваакууме". Да, не все задачи оптимально решать методами ГА. Какие неоптимально - а черт его знает. Может часть комбинаторных, может часть задач, которые можно реализовать только целочисленно. Но и чисто случайный поиск ничего хорошего не принесет. Лучше все-таки даже на таких задачах запускать ГА, просто регулировать уровень мутаций (ставить повыше). А с уровнем мутаций 100% ГА вообще в Монте-Карло превращаются :)

Re: будем рассматривать реальные задачи

[ushastyi.livejournal.com]

А, задачу понял, спасибо. Посмотрю на досуге.

Про значащие цифры -- это не имеет значения. Применимость теоремы о бесплатном обеде реально высокая. Посмотрите условия, в википедии есть.

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

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