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

[kaipa]

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

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

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

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

Comments

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]

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

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

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

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