Pull to refresh

Comments 42

Правильно подобранная операция скрещивания (Crossover) может существенно повысить целенаправленность эволюции. Вообще, на мой взгляд, основной проблемой в решении задач генетическими алгоритмами является подбор представления (формата) генов решения, при котором бы функция приспособленности набора генов с изменением каждого гена менялась бы «вероятно незначительно», и приспособленность результата скрещивания двух решений так же «вероятно незначительно» отличалась бы от приспособленности родителей.
(((x*x)**0.106)**2))

Кажется стоит допилить сокращения таких штук.
Как происходит мутация формул? Она затрагивает один из токенов, содержащихся в формуле, и может пойти тремя путями:

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

Если претенденты вообще не трогали массив — выбирать случайного. Если тронули, то это уже лучше чем вообще ничего не делали с массивом. Из двух претендентов, которые что-то изменили в массиве — выбирать того кто привёл его к более сортированному виду чем он был раньше (ввести метрику отсортированности — например, количество элементов в верном порядке, стоящих рядом).
итоги первого эксперимента заставили меня сильно усомниться в шансах на успех с сортировками

Мне кажется что-то вроде bogosort вполне может получится.
Кажется стоит допилить сокращения таких штук

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


А что если в качестве ещё одного вида мутации константам добавить округление

Это и происходит в случае shift: константа может поменять свой тип с Float на Int, и, таким образом, отбросить дробную часть.


Касательно сортировок. Да, согласен, оценка степени сортированности массива это первый из наиболее напрашивающихся критериев успеха. Но, повторюсь, неверные шаги сортировок искажают их до неузнаваемости. Тут можно провести аналогию с хеш-функцией, где решение это исходная строка, а результат оценивается по её хешу. Один символ в строке поменялся — хеш радикально преобразился.

Рекомендую посмотреть push language и его инфраструктура. Там целые программы (правдо для стековой машины) генерятся при помощи ГА
Мне кажется у вас слишком много «мусора» в генофонде, и поэтому алгоритм основное время капается в нем.

В задачах символьной регрессии удобнее представлять геном в виде дерева, например так — images.myshared.ru/10/988544/slide_3.jpg

А для сокращения(упрошения выражений) использовать математические пакеты типо матлаба (они сделают все как надо).

Замечательная работа по теме — «distilling free-form natural laws from experimental data». Ребята вывели законы механики с помощью генетических вычислений.

И вот тут предприняты попытки сделать более интелектуальные упрощения, чтобы на корню не губить потенциальные решения — github.com/air-labs/CA

Ваша картинка:
image
Геном в первом эксперименте и представлен в виде дерева, например:


xp2 = Formula::PowerOperator.new(Formula::Variable.new(:x), Formula::IntConstant.new(2)) # (x**2)
xm3 = Formula::MultiplicationOperator.new(Formula::IntConstant.new(3), Formula::Variable.new(:x)) # (3*x)
xp_xm = Formula::SubtractionOperator.new(xp2, xm3) # ((x**2)-(3*x))
xpx = Formula::AdditionOperator.new(xp_xm, Formula::IntConstant.new(2)) # (((x**2)-(3*x))+2)
f = Formula::PowerOperator.new(xpx, Formula::FloatConstant.new(0.5)) # ((((x**2)-(3*x))+2)**0.500)

Да, возможно имело смысл обратиться к готовым решениям по сокращениям.
Спасибо за наводки, ознакомлюсь.

Да когда же вы уже наиграетесь в «природу» (нейросети, генетику)? Читайте Пенроуза («Тени разума» хотя бы).
А что не так? ГА просто один из способов решения задачи оптимизации, нейросеть просто способ аппроксимировать ф-ию.
Вот и выходит все «просто». Потому и результат никакой. Ожидаемо никакой… но чтобы это понять надо читать серьезную литературу. А не модификации ГА, которые обещают чудо.
Ну почему же никакой, вон, нейросети и в Го играют, и картиночки успешно распознают.
ГА слабы в большинстве задач, это да
Вам лучше в политику, а не в IT или науку. Вы «умеете» убеждать без каких-либо глубоких знаний в предмете.
спасибо за совет, профессор с глубокими знаниями генетики
UFO landed and left these words here
В любой задаче, в которой вы способны подобрать представление (формат) генов решения, при котором бы функция приспособленности набора генов с изменением каждого гена менялась бы «вероятно незначительно», и приспособленность результата скрещивания двух решений так же «вероятно незначительно» отличалась бы от приспособленности родителей.
Ну вот использовать ГА для обучения тех же нейросетей это не очень хорошая идея (для большинства случаев) — обучение будет происходить очень медленно, и нет гарантии что будет найден локальный минимум.
И почему важно чтобы " функция приспособленности набора генов с изменением каждого гена менялась бы «вероятно незначительно»"?
1) Попробуйте дать более надёжные гарантии.
2) Так работает натуральная эволюция.
1) Что значит дать более надежные гарантии?
2) Разве из этого вытекает, что подобное правило справедливо для ГА?
Ну и если у меня есть гладкая ф-ия потерь (которая меняется незначительно от вариации аргумента), разве не проще использовать градиентные методы первого/второго порядка, которые имеют намного лучшую сходимость по сравнению с ГА?
1) Сформулируйте сами.
2) Да, вытекает (не из самого факта, а из математических теорий, почему это работает в натуральной эволюции). Нет, не всегда функция отбора формализуема более, чем «вероятно, изменение гена не слишком существенно изменило значение функции приспособленности».
Для далёкого от темы человека — вода. Для того, кто сам уже реализовывал ГА, — замечание вполне конкретное и понятное (возможно, даже тривиальное, но по своему опыту сужу, что часто плохие результаты и разочарования в ГА случались из-за неверно подобранного формата генов). Возможно, меня спрашивали о конкретных прикладных задачах, а не о формальных критериях таких задач, тогда могу предложить вот список «Применение генетических алгоритмов» на странице: https://ru.wikipedia.org/wiki/Генетический_алгоритм.
Вот тут ребята применили ГА к маршрутизации в TCP: https://www.opennet.ru/opennews/art.shtml?num=37482. Многие торговые роботы, торгующие на биржах, для оптимизации рисков тоже используют ГА.
UFO landed and left these words here
Если ф-ия выпуклая, то нам не обязательно определять область поиска решения — глобальный минимум и так один, и мы к нему рано или поздно придем.

За пример спасибо — первый раз вижу чтобы ГА применяли к чему-то более-менее полезному (правда компетенции чтобы оценить качество решения у меня нету =( )

На счет того, что ГА единственный вариант для случаев когда мы не можем нормально анализировать целевую ф-ию — не согласен.
Есть же целая куча derivative free оптимизаций — всякие Particle swarm optimization, CMA-ES, etc
UFO landed and left these words here
>А если не секрет, то где?
В логистике. Ни задача нахождения кратчайшего (читай эффективного, с учетом метрик — пропускная, тоннаж, габариты, разрешения для опасных грузов) пути ни задача упаковки грузов (просто максимальной утилизации контейнера, даже без учета требований такелажа к каждой коробке) не решены. NP-трудные задачи. И решают их в основном генетическими алгоритмами, нейросетки почему то не в ходу, подозреваю что из-за трудности с обучением.

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

Пенроуз делает анализ разных методов (в том числе новомодные вроде нейросетей) на предмет «сильного ИИ». Один из его выводов, к примеру, — псевдослучайность всегда лучше случайности (в ГА кажется на случайность сильно полагаются). Еще одно его интересное предположение: мозг обладает интеллектом вовсе не из-за громадного кол-ва нейронов и связей. Причины следует искать внутри нейрона, квантовой механики… Книга сложная, но замечательна здоровым скептицизмом.
Теперь давайте посмотрим на суть этой статьи. К предметной области А решили применить метод из совершенно далекой предметной области В. Ну как минимум хотелось бы аргументации — а с чего ради гвозди забивать подушкой? Аргументация в подобных статьях одна — ну Дарвин же, природа, ГА — это круто… И дальше поток терминов, эвристик… Чтобы забивать подушкой гвоздь — нужна сильная аргументация. Если бы автор потратил столько же времени на аргументацию — был бы как минимум предметный разговор. А так — еще один эвристический бесполезный алгоритм.
Мнение Пенроуза о «невычислимости» сильного ИИ, во-первых, очень непопулярно среди учёных (пока накопленные научным методом данные не дают шансов никаким квантовым эффектам в нейронах, которые могли бы хоть как-то системно влиять на поведение мозга, Пенроуз делал ставку на тубулин), а, во-вторых, он вообще о другом, он о сильном ИИ с аналогичным человеческому по мощности сознанием. А генетический алгоритм — это не искусственный разум, это всего лишь алгоритм оптимизации, то, что относят к сфере «слабого ИИ».
Простите, непопулярно среди учёных — кто конкретно из таких же известных? Желательно математиков.
«это всего лишь алгоритм оптимизации» — так под оптимизацию любую задачу можно подогнать. Что вы и проделали. Только аргументация нулевая. Почему среди кучи методов оптимизации вы решили ГА попробовать? Вообще какой смысл применять «подушку» к забиванию гвоздей когда рядом молоток лежит?
Вы человек очень умный, зрящий в корень, вы сразу подловили меня на подлоге. Но я без злого умысла, это следствие моего заблуждения и самообмана. Спасибо, благодаря вам я, наконец, прозрел. Больше никогда в жизни не подойду к генетическим алгоритмам.

Может быть, оставите свои контакты, чтобы я отправлял к вам всех, кто ещё так же как и я блуждает в неведении? У вас очень убедительная риторика.
в том числе новомодные вроде нейросетей

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


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


Что касается примера, использованного в статье — что поделать, на прорыв в кибернетике он не тянет :) С другой стороны, на простом примере, "на пальцах", легче доносить мысли и что-то объяснять.

«многократно доказывали свою эффективность» — вообще то примеров как раз мало. Желтых вывесок и липовых кандидатских — море. Реальных _эффективных_ применений — ну что то я не вижу такой тренд. К примеру, в ABBY (я это знаю из рассказа ведущего разработчика FineReader) тоже купились одно время на якобы мощь нейросетей. Попробовали, и отказались… Потому что _эффективные_ решения надо искать в той же предметной области что и проблема.

Про полезность попыток применения ГА — не спорю, пробовать надо. Но делать такие эксперименты надо чистыми. Выбирать предметную область максимально ближе к явлениям в ГА…
Если таким способом можно получить, например, быстрый InvSqrt, то метод достаточно интересен для приближенных алгоритмов.

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

Заметил в Вашем примере родословной, что нектороые синтксически разные деревья, на самом деле семантически одинаковы:


(((x-0)**2)/1)
((((x-0)**2)-0)/1)
(((x-0)**2)-0)
(((x-0)**2)-0.000)

Некоторое время тому я тоже интересовался данной тематикой.


Чтобы уменьшить количество семантически одинаковых деревьев, я разбивал каждую итерацию Генетического Алгоритма на два этапа:
1) операции над синтаксическими деревьями (скрещивание и мутации)
2) оптимизация числовых коэффициентов каждого синтаксическогг дерева (опять же с использованием Генетического Алгоритма)
Дополнительная оптимизация: в случае, если поддерево не содержит переменных — оно заменяется на лист с единственным числовым значением.


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


Более подробоное описание можно найти в моём посте: https://habrahabr.ru/post/163195/ (правда у меня весь код реализован на Java, и в посте можно найти ссылку на GitHub)

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


(x - x)
(0 / x)

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


Операция оптимизации в моём случае называется сокращением, и вынесена как один из вариантов мутации, по тем же соображениям:


((4 - 2) * 3)
6

Первое дерево может прийти ко второму за одну мутацию типа shift, применённую к операции верхнего уровня (умножению). Однако, пока это разные деревья, и у них, соответственно, разные возможные пути мутации.

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

Можно не пытаться скармливать сразу большой массив и как-то анализировать пригодность результата. Эволюция же работает с малыми изменениями окружающей среды, при радикальных изменениях она терпит крах (массовые вымирания видов).
Предлагаю выращивать популяцию, способную сортировать короткие массивы, начиная например с 3 элементов.
Имея такую популяцию уже можно вносить изменения в окружение — увеличить размер массива на один элемент.
Те, кто справился, — проходят без изменений. Остальные мутируют/скрещиваются, пытаются адаптироваться.

Увеличение длины массива можно рассматривать как распространение вида на новые территории. Более универсальный вид захватит максимально возможную территорию (как это сделал, к примеру, человек).
Да, декомпозиция целевой задачи на постепенно усложняющиеся этапы кажется единственной возможностью применить ГА, если фитнес-функция для полной задачи трудно выразима. Однако после декомпозиции оказывается, что «этапность» как раз и выражает фитнес-функцию полной задачи (т.е., она и будет предоставлять последовательность этапов, которые должен решить тестируемый экземпляр, начисляя победных очков за каждый последующий этап больше, чем за предыдущий).
Вы описали то же самое, но другими словами. В первом случае мы меняем условия поэтапно, во втором — проверяем выживаемость на разной территории (поэтапно). Второй случай лучше ложится в классическое описание ГА с одно фитнесс функцией, но на любой алгоритм можно найти другой, эквивалентный ему. Разумеется предпочтение отдается наиболее эффективному.
Фитнес-функцией просто легче «играть» (подбирать, сравнивать разные версии), чем глобально перепрограммировать этапы отбора, придумав новое разделение задачи. Плюс это позволит существовать в одной популяции одновременно и успешным экземплярам, застрявшим на последнем этапес, и экземплярам, застрявшим на промежуточных этапах, что может защитить популяцию от вырождения (от скатывания решения к локальному максимуму).

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

Сокращение формул это попытка заранее произвести операции над константами, где это возможно. Например из "(3+2)" получить «5», а из «8/(x/2)» получить "(16/x)". Задача неожиданно оказалась настолько нетривиальна

Ну ещё бы! Умные люди придумали до нас использовать категорию графов и кодекартов квадрат в ней, например. Можно вообще Ehrig'а почитать по преобразованиям графов по правилам.
Only those users with full accounts are able to leave comments. Log in, please.