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

[kaipa]

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

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

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

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

Comments

[imageman72.livejournal.com]

> Во-первых, буду придираться.
можете, только отвечать скучно на это

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

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

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

Кстати, на какого рода функциях (задачах) вы получили преимущество при использовании метода Монте-Карло?

[ushastyi.livejournal.com]

Подождите, а причем тут "более сложные задачи". Вы сами написали, что "функция жизни" -- это максимизация жизнеспособности организма. Вы отказываетесь от такого определения? Прекрасно. Теперь, по-вашему, задача жизни -- это "решать более сложные задачи"? Откуда? Зачем? Если на то пошло, то жизнь вообще противоречит Второму Началу Термодинамики, так как уменьшает энтропию. А человек это делает особенно успешно. И какая тогда функция жизни?

Только Вы не подумайте, что я издеваюсь. Я задаю вопросы, на которые я не знаю ответа. И, наверное, никто не знает. И ГА тут совершенно не причем.

По поводу преимущества метода Монте-Карло. В функциях с большим количеством локальных экстремумов (ям). Особенно если они близки к глобальному. Нет никакой стратегии, чтобы отличить локальную яму от глобальной, не спустившись до низу. При этом нельзя гарантировать, что были найдены все локальные ямы. Для такого рода задач неплохой должно подходить http://en.wikipedia.org/wiki/Simulated_annealing , но я не проводил таких исследований.