В чем все-таки новизна генетических алгоритмов?

[_hum_]

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

шаг 0. Набрасываем случайным образом $N$ точек
шаг 1. Вычисляем в них значения функции
шаг 2. Отбираем $K$ штук, где значения наибольшие, остальные точки выбрасываем из рассмотрения
Шаг 3. В отобранных точках выбираем $N-K-L$ пар, и для каждой такой пары выбираем точку, которая равноудалена от каждой из точек пары (в какой-то метрике, например, хэмминговской);
Шаг 4. Получившиеся $N-L$ точек дополняем $L$ точками, выбранными случайным образом из их окрестностей.
Шаг 5. Переходим к шагу 1 (с учетом критерия на остановку).

И как-то у меня не получается сразу понять, в чем изюминка...Интуитивно кажется, это как-то с зависимостью между шагами связано...Но вот что конкретно...

Кто разобрался, проясните ситуацию, если не сложно.

[Munin]

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

[_hum_]

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

[Munin]

В виде целевой функции и в шаге 3 (который вы изобразили неправильно, ну да не в этом дело), который на самом деле согласован с целевой функцией.

[_hum_]

Munin в сообщении #800847 писал(а):

В виде целевой функции

То есть, целевая функция должна быть какого-то специфического класса? Какого именно?

Цитата:

и в шаге 3 (который вы изобразили неправильно, ну да не в этом дело)

в чем конкретно неправильность? что выбираются две точки, а не одна?

Цитата:

, который на самом деле согласован с целевой функцией.

что вы имели в виду? где это согласование прослеживается?

[Munin]

_hum_ в сообщении #800867 писал(а):

То есть, елевая функция должна быть какого-то специфического класса?

Да! Например, $f(x,y,z,\ldots)=f_1(x)+f_2(y)+f_3(z)+\ldots$

_hum_ в сообщении #800867 писал(а):

в чем конкретно неправильность?

Для каждой пары $p,q$ выбираем точку $r,$ по определённому правилу соответствующую двум точкам. Обычно правило такое:
3.1. Координаты делятся на два дополнительных подмножества $\{i\}$ и $\{j\}.$ Тоже случайно. (Иногда - не вполне случайно, например, каждое подмножество состоит из небольшого количества интервалов.)
3.2. Новая точка имеет координаты $r_{\{i\}}=p_{\{i\}}$ и $r_{\{j\}}=q_{\{j\}}.$
Это правило называется "кроссовер". Есть и другие правила, иногда добавляемые или не добавляемые в зависимости от модификации алгоритма. Если есть несколько правил, то какие конкретно применяются - выбирается случайно. "Кроссовер" (или какой-то его близкий аналог) есть всегда.

_hum_ в сообщении #800867 писал(а):

где это согласование прослеживается?

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

[_hum_]

Munin в сообщении #800878 писал(а):

_hum_ в сообщении #800867 писал(а):

То есть, елевая функция должна быть какого-то специфического класса?

Да! Например, $f(x,y,z,\ldots)=f_1(x)+f_2(y)+f_3(z)+\ldots$

Так это же очень специфический класс (даже, кроме стат. физики, ничего в голову не приходит, где бы они могли возникать). А я именно читал про применения ГА в задаче оптимизации произвольных функций. Там еще сравнение с методом пчелиного роя было.

П.С. Я в курсе самого метода и на какой аналогии он построен.

[profrotter]

У меня была похожая тема topic42705.html. С картинками. Не обнаружил разницы с обычным розыгрышем. Упаковка красивая, но в ГА приходится расчитывать функцию адаптации для каждой альтернативы. В итоге ГА может работать и дольше, требуя чрезмерно больше памяти.

[_hum_]

profrotter, все-таки в ГА что-то заложено...он сильнее простого подбора. Вот пример, который наводит на соответствующие мысли:

см. Пример 1.10. писал(а):

Пример 1.10. Синтез текста. Этот пример прекрасно демонстрирует мощь генетических алгоритмов. Задача синтеза текста заключается в получении фрагмента известной украинской песни несе Галя воду из случайно сгенерированного списка букв при помощи генетического алгоритма. Так как для каждой позиции текста возможны 32 различные буквы алфавита, а таких позиций в заданном выражении 12, то вероятность получения необходимой строки случайным способом равна $(\frac{1}{31})^{12} = 1.27 \times 10^{-18}$, т. е. практически нуль.[Тогда как ГА спокойно его "щелкает".]

И, как видится, потому, что алгоритм случайного перебора "работает" по формуле:

$$P(A_1 A_2 \dots A_n) = P(A_1)P(A_2)\dots P(A_n),$$

а ГА - по какому-то аналогу

$$P(A_1 A_2 \dots A_n) = P(A_1)P(A_2|A_1)\dots P(A_{n}|A_1A_2\dots A_{n-1}),$$

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

П.С. И да, господа, вам не кажется, что метод пчелиного роя (см., например, Алгоритм пчел для оптимизации функции, Bees Algorithm) - это тот же ГА, только "вид сбоку"?

[profrotter]

_hum_, теоретизирований я видел не мало. Практики не видел. Кроме своей. Да и вам советую практиковаться. Давайте синтезировать строку. Посмотрим кто кого щёлкает. Какой тут критерий синтеза, кстати? Как характериуется степень похожести одной строки на другую? Алгоритм не может работать по формулам, выражающим вероятность какого-то события, мне думается.

-- Сб дек 14, 2013 23:36:28 --

В любом случае мне кажется, что Вы, влед за автором примера 1.10, недобросовестно представляете себе случайный перебор, как последовательность независимых розыгрышей из заданного набора символов. Но представьте себе такую последовательность розыгрышей, в которой полученные символы в некоторых позициях, если они приближают нас к требуемой строке фиксируются на своём месте. Прямо как в поле чудес: "Есть такая буква в этом слове!". Такой алгоритм тоже приведёт к успеху, но ничего общего с ГА не имеет. Так вот, чтобы ГА хорошо сходился приходится реализовывать примерно то же самое - вводить элитные особи, которые хранят лучшие результаты. В той теме, на которую я дал ссылку я много писал об этом и приводил примеры. Но там же много написано.

Посмотрел пример 1.10. В общем символы преобразуются в числа. У меня в теме есть похожий пример в сообщении #432791 на целых 500 чисел (символов, если угодно).

[Munin]

_hum_ в сообщении #800910 писал(а):

Так это же очень специфический класс

На самом деле, на практике встречающийся очень часто. Точнее, случай, в котором члены $f_{12}(x,y)$ есть, но сравнительно малы (и $x,y$ - разумеется, векторы). Это случай, когда оптимизируется некая система, но (по крайней мере в области оптимума) влияние её подсистем друг на друга достаточно мало.

[_hum_]

profrotter в сообщении #801024 писал(а):

Такой алгоритм тоже приведёт к успеху, но ничего общего с ГА не имеет.

:) Вы уверены, что ничего общего не имеет? Я в самом первом посте пытался перевести ГА на обычный мат. язык с помощью введения расстояния Хэмминга

$$d(\mathbf{x},\mathbf{y}) = \sum_{i=1}^K |\sign(x_i - y_i)|,$$

чтобы из-за шелухи вроде "хромосома", "кроссиговер" и проч. не созадвалось обманчивое впечатление об уникальности алгоритма. Правда, при этом я предполагал, что идет обмен только половинками хромосом, потому сформулировал шаг 3 в виде выбора равноудаленной точки. Но, видимо, если предполагать случайный выбор точки обмена, то это будет нечто из разряда случайного выбора точек из окрестностей радиусов $r_1 = K - \alpha, r_2 = \alpha$, где $\alpha$ - случайная величина, равномерное распределенная на значениях $1, 2, \dots, K$.

Тут не суть в том, как внешне выглядит, а в том, какие принципы используются. Вот вы говорите,

Цитата:

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

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

profrotter в сообщении #801024 писал(а):

В той теме, на которую я дал ссылку я много писал об этом и приводил примеры. Но там же много написано.

Да, довольно сложно читать. Я знаком лишь с основами (фактически только по той статейке, из которой пример). Ни про каких лидеров и проч. не в курсе (и, думаю, это не принципиально для сути метода).

profrotter в сообщении #801024 писал(а):

Посмотрел пример 1.10. В общем символы преобразуются в числа. У меня в теме есть похожий пример в сообщении #432791
на целых 500 чисел (символов, если угодно).

И? Вывод ваш каков? Что вашим не "ГА-методом" вы бы тоже этот пример "щелкнули"? Тогда, может быть, стоило бы подробнее здесь изложить, чтобы сравнить с ГА?

Munin в сообщении #801059 писал(а):

На самом деле, на практике встречающийся очень часто. Точнее, случай, в котором члены $f_{12}(x,y)$ есть, но сравнительно малы (и $x,y$ - разумеется, векторы). Это случай, когда оптимизируется некая система, но (по крайней мере в области оптимума) влияние её подсистем друг на друга достаточно мало.

А это ваши собственные соображения (что ГА только к такому классу функций приложим), или общепринятый взгляд на этот алгоритм?

[Munin]

_hum_ в сообщении #801130 писал(а):

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

А может быть, вы ошиблись, и алгоритм-то на самом деле уникален, и вы пытаетесь доказать несуществующую эквивалентность его другим алгоритмам? Вы не задумывались о таком варианте?

_hum_ в сообщении #801130 писал(а):

А это ваши собственные соображения (что ГА только к такому классу функций приложим), или общепринятый взгляд на этот алгоритм?

Я не сказал, что он только к такому классу функций приложим. Я сказал, что на таком классе функций он даёт выигрыш по сравнению с Монте-Карло.

Наверное, ГА даёт выигрыш и шире: он схож не просто с Монте-Карло, а с Монте-Карло + покоординатным спуском.

Это мои собственные соображения. Но у меня сложилось впечатление, что ваше знакомство с ГА - чуть более чем поверхностное.

[profrotter]

_hum_ в сообщении #801130 писал(а):

Но в "Поле чудес" вы знаете, какую букву отгадали, а здесь нет!

А здесь мы имеем функцию адаптации. Конкретно в примере 1.10 она равна сумме совпадений символов в искомой и эталонной строке. Если такой-то символ, попавший в розыгрыше на такое-то место даёт увеличение функции адаптации, то мы его закрепляем в текущей позиции. Это кстати не означает, что он там остаётся навсегда. В других итерациях-розыгрышах мы будем тоже пытаться заменить его другими и, если это приведёт к увеличению функции адаптации, заменим его другим. Если нет - оставим на месте.

_hum_ в сообщении #801130 писал(а):

Что вашим не "ГА-методом" вы бы тоже этот пример "щелкнули"?

Уже "щёлкнул" более серьёзный пример на строку из 500 символов, каждый из которых представлен 16 битами, а не 8-мью, как в случае эски-символов. Ссылки вам были приведены. Чего ж ещё? "Мой" метод точно не ГА - нет скрещивания и всё тут. Есть просто "сохранение хороших результатов", получаемых в ПС-итерациях.

Я ни на чём не настаиваю. Конечно в ГА что-то есть: это что-то буквально завораживает когда программируешь - это исключительное чувство приобщения к мировому процессу эволюции, быть может это даже лёгкое ощущение себя творцом маленькой компьютерной жизни, которая будет иметь место в каждом акте оптимизации?..

Мне был бы интересно, чтобы кто-то выполнил сравнение ГА и не ГА, подобное мне. Может у меня ошибки в программе. Но мы же теоретики.

[Munin]

_hum_ в сообщении #801130 писал(а):

Но в "Поле чудес" вы знаете, какую букву отгадали, а здесь нет!

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