Comments 22
Как по мне — самое сложное в реальных приложениях генетических алгоритмов — правильная фитнес-функция. В примере из топика все тривиально, однако на деле все не так просто. Если у вас есть достаточно линейная, гладкая и легко вычислимая фитнес-функция — вы решите задачу и генетикой, и градиентным спуском, и прочей нейронщиной, без проблем. А если фитнес-функция плоха, то ничего не поможет.
Второе по сложности — генетический код. Нужно придумать хорошие признаки, которые опять-таки должны быть достаточно линейны относительно фитнес-функции.
Подвох в том, что если у вас есть и первое, и второе, задача скорее всего и так уже имеет достаточно простое и очевидное аналитическое решение.
Второе по сложности — генетический код. Нужно придумать хорошие признаки, которые опять-таки должны быть достаточно линейны относительно фитнес-функции.
Подвох в том, что если у вас есть и первое, и второе, задача скорее всего и так уже имеет достаточно простое и очевидное аналитическое решение.
+16
Не соглашусь. Чтобы написать правильную фитнес-функцию, нужно только лишь внимательно подумать и составить формализованный перечень требований к конечному решению задачи. Сверка решения с этими требованиями — задача, как правило, линейная и решаемая. Создание генома — в общем-то, тоже вопрос сформулированности ТЗ.
Генетическое программирование призвано решать недетерминированные задачи, для которых невозможно линейным образом сгенерировать хоть какое-либо решение. IRL их всегда было и будет много. Один из классов таких задач — NP-полные задачи. Я сейчас как раз занимаюсь решением одной из них. Весьма, скажу, увлекательное занятие!
Кстати, хозяйке на заметку, довольно неплохая библиотека для работы с сабжем (java):
jgap.sourceforge.net/
Генетическое программирование призвано решать недетерминированные задачи, для которых невозможно линейным образом сгенерировать хоть какое-либо решение. IRL их всегда было и будет много. Один из классов таких задач — NP-полные задачи. Я сейчас как раз занимаюсь решением одной из них. Весьма, скажу, увлекательное занятие!
Кстати, хозяйке на заметку, довольно неплохая библиотека для работы с сабжем (java):
jgap.sourceforge.net/
+1
Кстати говоря, сам занимаюсь NP задачами (и выше) и иногда вижу статьи, которые успешно применяют GA для решения задач с примерно такой формулировкой: «Сложность задачи слишком высока для поиска точного решения, поэтому мы предлагаем генетический алгоритм в качестве аппроксимации». Обычно на этом этапе формальная спецификация задачи уже присутствует и вопрос в том, как найти хоть какое-то разумное решение.
+1
Можно спросить, как более сведущего человека? Я правильно понимаю, что задачи из пространства NP можно решить алгоритмически, а NP-сложные и, в частности, NP-полные задачи можно решить исключительно аппроксимацией (будь то ГП, graph rewriting или что-то еще)?
0
Не, можно и точно, весь вопрос в существовании эффективных солверов для класса сложности. Для 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), используя некоторые логические правила вывода, из которых состоит программа.
+1
Согласен про фитнес функцию. Хотя мне кажется, что генетические алгоритмы оптимизации рулят в многоанентских средах, где фитнес функция невычислима вообще, и результатом может быть только победа в поединке с другим агентом.
+2
Не по теме: есть русский термин для фитнесс-функции — функционал невязки. Просто вспомнил)
0
В комменте выше речь о том, что «Если у вас есть достаточно линейная, гладкая и легко вычислимая фитнес-функция ...». А не любая фитнес-функция.
Тоже много экспериментировал с ГА. От себя добавлю, что сложность ГА прежде всего в правильной реализации операторов (скрещивания и мутации, а также селекции и редукции), чтобы подальше отвести ГА от случайного поиска и поближе к направленному. Представление особи (хромосомы/решения) тоже нетривиальная задача. Давно уже никто битовой строкой не представляет. Можно просто векторами. Можно списками, деревьями и графами. Но чем сложнее кодирование особи, тем еще более сложными будут скрещивание и мутация.
Наверное, надо бы статью на хабр сделать со своим видением ГА. Плюсами и минусами.
Тоже много экспериментировал с ГА. От себя добавлю, что сложность ГА прежде всего в правильной реализации операторов (скрещивания и мутации, а также селекции и редукции), чтобы подальше отвести ГА от случайного поиска и поближе к направленному. Представление особи (хромосомы/решения) тоже нетривиальная задача. Давно уже никто битовой строкой не представляет. Можно просто векторами. Можно списками, деревьями и графами. Но чем сложнее кодирование особи, тем еще более сложными будут скрещивание и мутация.
Наверное, надо бы статью на хабр сделать со своим видением ГА. Плюсами и минусами.
+2
Но, простите, это заложено в определении NP-задачи — решаемость за полиномиальное время. Предполагать решение NP-задачу сколько-нибудь «быстро» — это абсурд. Тем более, NP-полную задачу.
Совершенно согласен про операторы. Причем важно не только их правильно реализовать, но и правильно применять в алгоритме эволюции. Про геном не соглашусь. Разумеется, битовая строка — это смешно в век ООП. Как и невозможность/нетривиальность представления какого-либо типа данных. Весь мир уже описан в XML так или иначе.
Признаюсь, я новичок в этом деле, статью непосредственно про ГП я не осилю, но если у меня получится решить мою задачу — обязательно об этом напишу.
Совершенно согласен про операторы. Причем важно не только их правильно реализовать, но и правильно применять в алгоритме эволюции. Про геном не соглашусь. Разумеется, битовая строка — это смешно в век ООП. Как и невозможность/нетривиальность представления какого-либо типа данных. Весь мир уже описан в XML так или иначе.
Признаюсь, я новичок в этом деле, статью непосредственно про ГП я не осилю, но если у меня получится решить мою задачу — обязательно об этом напишу.
0
> Предполагать решение NP-задачу сколько-нибудь «быстро» — это абсурд.
Если у вас есть доказательство, что ваша задача NP класса, согласен, абсурд. Доказательство есть? :)
Если у вас есть доказательство, что ваша задача NP класса, согласен, абсурд. Доказательство есть? :)
0
UFO just landed and posted this here
Да, в случае с построением формулы в фитнес-функцию пришлось бы встраивать непростую проверку синтаксиса, а ООП избавляет от такой необходимости на корню.
Интересный документ. Технически — используется достаточно очевидная в наше время объектная модель с хэшмапами символов, однако в качестве хромосомы все равно выступает, по сути, битовая строка. Забавно читать: девять лет назад считалось космическими технологиями, а сегодня сделать по другому и в голову-то не приходит :)
Вот только с математической точки зрения мне трудно понять, как апроксимируются математические выражения. Ведь при изменении любого оператора или параметра результат выполнения функции будет меняться на всем пространстве аргументов, так? К примеру, если в популяции появится хромосома с абсолютно правильным набором операторов, но с неправильными параметрами, она с большой вероятностью будет отброшена, разве нет?
Интересный документ. Технически — используется достаточно очевидная в наше время объектная модель с хэшмапами символов, однако в качестве хромосомы все равно выступает, по сути, битовая строка. Забавно читать: девять лет назад считалось космическими технологиями, а сегодня сделать по другому и в голову-то не приходит :)
Вот только с математической точки зрения мне трудно понять, как апроксимируются математические выражения. Ведь при изменении любого оператора или параметра результат выполнения функции будет меняться на всем пространстве аргументов, так? К примеру, если в популяции появится хромосома с абсолютно правильным набором операторов, но с неправильными параметрами, она с большой вероятностью будет отброшена, разве нет?
0
Да, думаю много кому (включая меня) было бы интересно.
0
Знал бы фитнес-функцию, жил бы в Сочи.
+9
Как по мне, так генетический алгоритм достаточно узок в применении и скорее позволяет красиво посмотреть как там ищется минимум в нашем многомерном пространстве. Как более практически применимый я бы порекомендовал Simmulated Annealing (Алгоритм имитации отжига) — он умеет выпрыгивать из маленьких ям, у меня с ним получалось решать оптимизационные задачи и он тоже достаточно прост по своей идее и хорош с точки зрения контроля за ним.
0
немного не в тему, но тоже любопытный пример применения генетического алгоритма
+2
Этот пример не менее потрясающий: www.youtube.com/watch?v=YZUNRmwoijw
+1
Sign up to leave a comment.
Играем с генетическими алгоритмами