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

[nikvic]

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

Мне был бы интересно, чтобы кто-то выполнил сравнение ГА и не ГА, подобное мне.

Я "играл" с вариантом задачи коммивояжёра. Например, матрица стоимостей переездов заполняется случайными числами, и ищется циклическая перестановка, минимизирующая стоимость маршрута.

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

Интересно, что фактически нет новых теорем - после первой слабенькой.

Для дискретных "хромосом" их популяции ведут себя как дискретные цепи Маркова (куча состояний), и там есть финальное распределение. Остаётся непонятным, для каких задач всё это работает...

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

[Munin]

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

Если такой-то символ, попавший в розыгрыше на такое-то место даёт увеличение функции адаптации, то мы его закрепляем в текущей позиции.

Это к ГА отношения не имеет. Это вы покоординатный спуск описываете. ГА не такой "умный".

[profrotter]

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

Это к ГА отношения не имеет. Это вы покоординатный спуск описываете

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

nikvic в сообщении #801288 писал(а):

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

Можем мы на что-нибудь взглянуть?

[nikvic]

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

Можем мы на что-нибудь взглянуть?

К сожалению, на диске 20-летней давности, которые не годятся для нового блока.
Алгоритмы могу описать.

[_hum_]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А здесь мы имеем функцию адаптации. Конкретно в примере 1.10 она равна сумме совпадений символов в искомой и эталонной строке.

Не знаю, может, я не совсем ясно изложил мысль. Речь идет о применении ГА к задачам поиска максимумов/минимумов функций. Функция адаптации в таких задачах и есть та функция, максимум которой надо найти. Соответственно, в общем случае нет никакой возможности узнать заранее, что выбранное тем или иным образом значение одного из аргументов этой функции является оптимальным (в точке максимума будет именно таким). (Представьте, что вы не знаете, какую фразу нужно составить и не знаете, как конкретно вычисляется совпадение текущей фразы с заданной. У вас есть лишь информация о том, что чем ближе фраза к заданной, тем выше значение функции адаптации, плюс имеется возможность получать конкретные значения функции адаптации для любой фразы.)

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

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

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

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

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

Ладно, давайте тогда более конкретно, раз мой вопрос не понятен.

Пусть есть задача максимизации некоторой функции $f = f(x,y)$. Область определения функции дискретизиурется таким образом, чтобы оставить только точки, кодирующиеся с помощью некоторого кодирующего отображения

$$c: (x,y) \mapsto u = (b_1,b_2,\dots,b_s) \in \{0,1\}^s,$$

где $s$ - некоторая универсальная константа. На множестве кодирующих бинарных последовательностей введем метрику

$$d(u',u'') = \sum_{i=1}^s |b_i' - b_i''|.$$

И рассмотрим два алгоритма - ГА и следующий:

шаг 0. Набрасываем в $\{0,1\}^s$ случайным образом (например, равномерно) $N$ точек
шаг 1. Вычисляем в соответствующих им исходных точках значения функции f
шаг 2. Отбираем $K_p$-штук точек с самыми большими значениями функции, остальные точки выбрасываем из рассмотрения
Шаг 3. В отобранных точках случайным образом выбираем $K_f$ пар $(u^\mathrm{father}, u^\mathrm{mother})$, для каждой из которых:
Шаг 3.1 Случайным образом выбираем значение $r \in \overline{1,s}$.
Шаг 3.2 Каким-либо образом выбираем две новые точки $v^\mathrm{child\, A}$, $v^\mathrm{child\, B}$, удовлетворяюшие:

1) $d(v^\mathrm{child\, A}, u^\mathrm{father} ) \leqslant r, \quad d(v^\mathrm{child\, A},u^\mathrm{mother}) \leqslant s - r$
2) $d(v^\mathrm{child\, B}, u^\mathrm{mother} ) \leqslant r, \quad d(v^\mathrm{child\, B},u^\mathrm{father}) \leqslant s - r $

Шаг 4. Получившиеся $K_p + 2 K_f$ точек дополняем до $N $точками $w$, выбранными случайным образом, отталкиваясь от некоторых точек $v$ и иcходя из условия $d(w,v) \leqslant 1$.

Шаг 5. Переходим к шагу 1 (с учетом проверки условия на останов).

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

[Munin]

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

Тема заявлена как вопрос о том, что же в ГА принципиально нового.

Ну я и попытался на него ответить.

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

Стандартный научный подход в таких случаях - попытаться свести новое явление к чему-то ранее уже известному

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

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

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

http://boxcar2d.com/ , например. Оптимизация одной части конструкции мало сказывается на оптимальности другой части конструкции. (Иногда сказывается, но это сравнительно редкий случай.) Другие случаи идеологически похожи.

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

Хотелось бы что-нибудь более конкретного, чтобы знать, где целесообразно его применять, а где нет.

А в литературе по ГА нет комментариев касательно области применимости?

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

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

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

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

Меня интересует другое - какой общий (не привязанный к генетике и теории эволюции) принцип позволяет ускорять перебор.

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

[_hum_]

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

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

:) Если не пытаться свести его к уже известному, то как же в новом явлении разобраться. И я не говорил, что полностью. Вы выбросили фразу

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

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

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

http://boxcar2d.com/ , например.

Да, известный пример. Только опять же, чисто эволюционный :) Но, наверное, да, общий класс таких задач можно охарактеризовать тем, что

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

Оптимизация одной части конструкции мало сказывается на оптимальности другой части конструкции.

(Я, кстати, так не смог заметить на глаз "эволюционирование" в нужном направлении.)

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

А в литературе по ГА нет комментариев касательно области применимости?

Я не копался в литературе - ее тонны, а меня этот вопрос интересует (пока) больше из любознательности, чем практической необходимости.

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

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

Чем именно неудачные? Целевая функция не подпадает под указанный класс?

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

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

Меня интересует другое - какой общий (не привязанный к генетике и теории эволюции) принцип позволяет ускорять перебор.

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

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


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

[Munin]

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

(Я, кстати, так не смог заметить на глаз "эволюционирование" в нужном направлении.)

Там долго ждать надо :-) Пару десятков поколений. В общем, открываете в отдельном окошке, сворачиваете, и смотрите через несколько часов.

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

Я не копался в литературе - ее тонны, а меня этот вопрос интересует (пока) больше из любознательности, чем практической необходимости.

Ну-у-у, как же так! Как раз даже любознательность - но серьёзная, а не совсем на уровне "походя охаять", должна заставлять залезть ну хотя бы на уровень серьёзных учебников и обзорных статей.

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

Чем именно неудачные? Целевая функция не подпадает под указанный класс?

Может быть, не под мой указанный класс, а под класс, на котором ГА дают выигрыш.

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

И, кстати, а по поводу алгоритма пчел

А я вообще не в курсе. Извините. ГА ещё помню в общих чертах, а пчёлы, наверное, уже после меня появились. Ещё simulated annealing помню.