Комментарии 22
Как по мне — самое сложное в реальных приложениях генетических алгоритмов — правильная фитнес-функция. В примере из топика все тривиально, однако на деле все не так просто. Если у вас есть достаточно линейная, гладкая и легко вычислимая фитнес-функция — вы решите задачу и генетикой, и градиентным спуском, и прочей нейронщиной, без проблем. А если фитнес-функция плоха, то ничего не поможет.
Второе по сложности — генетический код. Нужно придумать хорошие признаки, которые опять-таки должны быть достаточно линейны относительно фитнес-функции.
Подвох в том, что если у вас есть и первое, и второе, задача скорее всего и так уже имеет достаточно простое и очевидное аналитическое решение.
Второе по сложности — генетический код. Нужно придумать хорошие признаки, которые опять-таки должны быть достаточно линейны относительно фитнес-функции.
Подвох в том, что если у вас есть и первое, и второе, задача скорее всего и так уже имеет достаточно простое и очевидное аналитическое решение.
Не соглашусь. Чтобы написать правильную фитнес-функцию, нужно только лишь внимательно подумать и составить формализованный перечень требований к конечному решению задачи. Сверка решения с этими требованиями — задача, как правило, линейная и решаемая. Создание генома — в общем-то, тоже вопрос сформулированности ТЗ.
Генетическое программирование призвано решать недетерминированные задачи, для которых невозможно линейным образом сгенерировать хоть какое-либо решение. IRL их всегда было и будет много. Один из классов таких задач — NP-полные задачи. Я сейчас как раз занимаюсь решением одной из них. Весьма, скажу, увлекательное занятие!
Кстати, хозяйке на заметку, довольно неплохая библиотека для работы с сабжем (java):
jgap.sourceforge.net/
Генетическое программирование призвано решать недетерминированные задачи, для которых невозможно линейным образом сгенерировать хоть какое-либо решение. IRL их всегда было и будет много. Один из классов таких задач — NP-полные задачи. Я сейчас как раз занимаюсь решением одной из них. Весьма, скажу, увлекательное занятие!
Кстати, хозяйке на заметку, довольно неплохая библиотека для работы с сабжем (java):
jgap.sourceforge.net/
Кстати говоря, сам занимаюсь NP задачами (и выше) и иногда вижу статьи, которые успешно применяют GA для решения задач с примерно такой формулировкой: «Сложность задачи слишком высока для поиска точного решения, поэтому мы предлагаем генетический алгоритм в качестве аппроксимации». Обычно на этом этапе формальная спецификация задачи уже присутствует и вопрос в том, как найти хоть какое-то разумное решение.
Можно спросить, как более сведущего человека? Я правильно понимаю, что задачи из пространства NP можно решить алгоритмически, а NP-сложные и, в частности, NP-полные задачи можно решить исключительно аппроксимацией (будь то ГП, graph rewriting или что-то еще)?
Не, можно и точно, весь вопрос в существовании эффективных солверов для класса сложности. Для NP есть куча эффективных SAT солверов, а для других классов их как правило мало и скорость поиска решений очень быстро падает с ростом сложности. Поэтому для конкретных задач часто используют эвристики и приближенные решения.
Для примера, SMT — обобщение SAT для разных логик в духе функций или арифметики. Сложность выше, скорость существенно меньше, но можно решать задачи в духе найти f такую, что f(x) > 5 для всех x и f(x) > f(y) для x > y.
Или answer set programming — решает задачи на второму уровне полиномиальной иерархии (т.е. один уровень выше, чем NP), используя некоторые логические правила вывода, из которых состоит программа.
Для примера, SMT — обобщение SAT для разных логик в духе функций или арифметики. Сложность выше, скорость существенно меньше, но можно решать задачи в духе найти f такую, что f(x) > 5 для всех x и f(x) > f(y) для x > y.
Или answer set programming — решает задачи на второму уровне полиномиальной иерархии (т.е. один уровень выше, чем NP), используя некоторые логические правила вывода, из которых состоит программа.
Согласен про фитнес функцию. Хотя мне кажется, что генетические алгоритмы оптимизации рулят в многоанентских средах, где фитнес функция невычислима вообще, и результатом может быть только победа в поединке с другим агентом.
Не по теме: есть русский термин для фитнесс-функции — функционал невязки. Просто вспомнил)
НЛО прилетело и опубликовало эту надпись здесь
В комменте выше речь о том, что «Если у вас есть достаточно линейная, гладкая и легко вычислимая фитнес-функция ...». А не любая фитнес-функция.
Тоже много экспериментировал с ГА. От себя добавлю, что сложность ГА прежде всего в правильной реализации операторов (скрещивания и мутации, а также селекции и редукции), чтобы подальше отвести ГА от случайного поиска и поближе к направленному. Представление особи (хромосомы/решения) тоже нетривиальная задача. Давно уже никто битовой строкой не представляет. Можно просто векторами. Можно списками, деревьями и графами. Но чем сложнее кодирование особи, тем еще более сложными будут скрещивание и мутация.
Наверное, надо бы статью на хабр сделать со своим видением ГА. Плюсами и минусами.
Тоже много экспериментировал с ГА. От себя добавлю, что сложность ГА прежде всего в правильной реализации операторов (скрещивания и мутации, а также селекции и редукции), чтобы подальше отвести ГА от случайного поиска и поближе к направленному. Представление особи (хромосомы/решения) тоже нетривиальная задача. Давно уже никто битовой строкой не представляет. Можно просто векторами. Можно списками, деревьями и графами. Но чем сложнее кодирование особи, тем еще более сложными будут скрещивание и мутация.
Наверное, надо бы статью на хабр сделать со своим видением ГА. Плюсами и минусами.
Но, простите, это заложено в определении NP-задачи — решаемость за полиномиальное время. Предполагать решение NP-задачу сколько-нибудь «быстро» — это абсурд. Тем более, NP-полную задачу.
Совершенно согласен про операторы. Причем важно не только их правильно реализовать, но и правильно применять в алгоритме эволюции. Про геном не соглашусь. Разумеется, битовая строка — это смешно в век ООП. Как и невозможность/нетривиальность представления какого-либо типа данных. Весь мир уже описан в XML так или иначе.
Признаюсь, я новичок в этом деле, статью непосредственно про ГП я не осилю, но если у меня получится решить мою задачу — обязательно об этом напишу.
Совершенно согласен про операторы. Причем важно не только их правильно реализовать, но и правильно применять в алгоритме эволюции. Про геном не соглашусь. Разумеется, битовая строка — это смешно в век ООП. Как и невозможность/нетривиальность представления какого-либо типа данных. Весь мир уже описан в XML так или иначе.
Признаюсь, я новичок в этом деле, статью непосредственно про ГП я не осилю, но если у меня получится решить мою задачу — обязательно об этом напишу.
> Предполагать решение NP-задачу сколько-нибудь «быстро» — это абсурд.
Если у вас есть доказательство, что ваша задача NP класса, согласен, абсурд. Доказательство есть? :)
Если у вас есть доказательство, что ваша задача NP класса, согласен, абсурд. Доказательство есть? :)
А вот это уже нетривиальный вопрос, но правильный :) Формулами не блесну, ибо я не математик (и, строго говоря, даже не программист по профессии), но скажу, что моя задача, в принципе, сводится к этой, с некоторыми дополнительными условиями.
НЛО прилетело и опубликовало эту надпись здесь
Да, в случае с построением формулы в фитнес-функцию пришлось бы встраивать непростую проверку синтаксиса, а ООП избавляет от такой необходимости на корню.
Интересный документ. Технически — используется достаточно очевидная в наше время объектная модель с хэшмапами символов, однако в качестве хромосомы все равно выступает, по сути, битовая строка. Забавно читать: девять лет назад считалось космическими технологиями, а сегодня сделать по другому и в голову-то не приходит :)
Вот только с математической точки зрения мне трудно понять, как апроксимируются математические выражения. Ведь при изменении любого оператора или параметра результат выполнения функции будет меняться на всем пространстве аргументов, так? К примеру, если в популяции появится хромосома с абсолютно правильным набором операторов, но с неправильными параметрами, она с большой вероятностью будет отброшена, разве нет?
Интересный документ. Технически — используется достаточно очевидная в наше время объектная модель с хэшмапами символов, однако в качестве хромосомы все равно выступает, по сути, битовая строка. Забавно читать: девять лет назад считалось космическими технологиями, а сегодня сделать по другому и в голову-то не приходит :)
Вот только с математической точки зрения мне трудно понять, как апроксимируются математические выражения. Ведь при изменении любого оператора или параметра результат выполнения функции будет меняться на всем пространстве аргументов, так? К примеру, если в популяции появится хромосома с абсолютно правильным набором операторов, но с неправильными параметрами, она с большой вероятностью будет отброшена, разве нет?
Да, думаю много кому (включая меня) было бы интересно.
Знал бы фитнес-функцию, жил бы в Сочи.
Как по мне, так генетический алгоритм достаточно узок в применении и скорее позволяет красиво посмотреть как там ищется минимум в нашем многомерном пространстве. Как более практически применимый я бы порекомендовал Simmulated Annealing (Алгоритм имитации отжига) — он умеет выпрыгивать из маленьких ям, у меня с ним получалось решать оптимизационные задачи и он тоже достаточно прост по своей идее и хорош с точки зрения контроля за ним.
немного не в тему, но тоже любопытный пример применения генетического алгоритма
Этот пример не менее потрясающий: www.youtube.com/watch?v=YZUNRmwoijw
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Играем с генетическими алгоритмами