Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 40
В общем случае генетический алгоритм — это оптимизация полного перебора, поэтому теоретически он применим ко всем задачам, которые можно решить полным перебором.
Хотелось бы в статье видеть не только конкретный пример (который, как по мне, не самый удачный), а и обобщение методов кроссовера, обоснования выбора способа расчета выживаемости и т.д.
Скажите, а ваша жена поняла это объяснение?:)
Кому интересно, наглядная демонстрация генетических алгоритмов. Часами можно смотреть.
megaswf.com/serve/1031310/
Кому интересно, наглядная демонстрация генетических алгоритмов. Часами можно смотреть.
megaswf.com/serve/1031310/
оооо. Это шикарно!
Надо отправить это чувакам из Тольятти. :)
на питоне бы этот велосипед поиметь с физикой
для чего, если не секрет?
См pyevolve (http://pyevolve.sourceforge.net/).
Вот сайт с оригиналом этой игры www.boxcar2d.com/
Там же есть собственный редактор, форум и возможность попробовать свои алгоритмы.
Там же есть собственный редактор, форум и возможность попробовать свои алгоритмы.
> 0.135266
А это что такое?
А это что такое?
Как я понял, это
1)
|114-30|=84
|54-30|=24
|56-30|=26
|163-30|=133
|58-30|=28
2) 1/84+1/24+1/26+1/133+1/28
3) Понял примерно по вот этому фрагменту:
4) Но не понял, почему, что, зачем и почему именно так это высчитывается :) Может кто пояснить?
1)
|114-30|=84
|54-30|=24
|56-30|=26
|163-30|=133
|58-30|=28
2) 1/84+1/24+1/26+1/133+1/28
3) Понял примерно по вот этому фрагменту:
...
float multinv = MultInv();
....
float CDiophantine::MultInv() {
float sum = 0;
for(int i=0;i<MAXPOP;i++) {
sum += 1/((float)population[i].fitness);
}
return sum;
}4) Но не понял, почему, что, зачем и почему именно так это высчитывается :) Может кто пояснить?
Вообще автор упустил такой момент, как функция ранжирования (fitness-функция или «приспособленность»). Не то чтобы упустил, не описал должным образом, хотя эта функция пожалуй является ключевой в этом алгоритме.
Так вот это по всей видимости и есть ее расчет
Так вот это по всей видимости и есть ее расчет
Самое главное — расчет по пункту 1. Чем меньше число, тем ближе результат к желаемому значению. Генетический алгоритм случайно перебирает варианты и закрепляет в следующих поколениях те, что ближе к идеалу, то есть к желаемому значению. Достаточно рассчитать пункт 1, и затем выбрать для следующего поколения те варианты, которые ближе всего к идеалу. Но так решение не получишь — нужно мутировать и видоизменять варианты решения. Поэтому остальные расчеты дают вероятность, с которой родители каждого типа дадут потомство. То есть папа с мамой, наиболее близкие к идеалу, дадут больше потомков (мутантов, но все равно унаследуют часть признаков от папы и мамы). Наихудшие особи сдохнут, но есть маленькая вероятность, что некоторые все-таки спарятся и дадут потомство — жутких выродков. Но это необходимо, т.к. у выродков случайно может появиться хороший ген (генами в данном случае являются просто числа — решения уравнения).
Кстати, выбирать числа — решения уравнений или коэффициенты или другие константы — методом генерации случайной функции ОЧЕНЬ плохо. Вероятность подобрать нужное число низкая (поэтому в примере взято уравнение с областью решений — целыми числами от 0 до 30). В генетических алгоритмах и числа надо кодировать генетически, и для этого двоичное представление идеально. Тогда мутация будет не в виде random(), а в виде случайной смены 0 на 1 или 1 на 0 в случайно выбранном разряде. Число требуемых вариантов для перебора, по теории оптимального эксперимента, будет пропорционально логарифму от числа вариантов случайного перебора.
Кстати, выбирать числа — решения уравнений или коэффициенты или другие константы — методом генерации случайной функции ОЧЕНЬ плохо. Вероятность подобрать нужное число низкая (поэтому в примере взято уравнение с областью решений — целыми числами от 0 до 30). В генетических алгоритмах и числа надо кодировать генетически, и для этого двоичное представление идеально. Тогда мутация будет не в виде random(), а в виде случайной смены 0 на 1 или 1 на 0 в случайно выбранном разряде. Число требуемых вариантов для перебора, по теории оптимального эксперимента, будет пропорционально логарифму от числа вариантов случайного перебора.
Ну общий принцип в словах-то ясен, но почему надо именно делить (причем не саму «близость», а 1/близость) на сумму таких же разделений?
Потому что нам нужны именно обратные коэфициенты — чем больше расстояние, тем процент выживаемости меньше, и наоборот. А если делить например, 84 / (84+24+26+133+28) то это получается прямая пропорциональность — чем больше расстояние, тем процент выживаемости больше, но нам не это нужно. Ну а делить нужно для того, чтобы определить в процентном соотношении, насколько близок данный результат от желаемого.
Считаю тут будет уместно представить список постов на хабре:
Генетический алгоритм: боремся с преждевременной сходимостью
Генетический алгоритм: оптимальный размер популяции
Генетический алгоритм на примере бота Robocode
Выбор размера популяции для генетического алгоритма
Генетические алгоритмы в MATLAB
Генетические алгоритмы для поиска решений и генерации
Концепции практического использования генетических алгоритмов
Что такое генетический алгоритм?
ТАУ-Дарвинизм
Обзор методов эволюции нейронных сетей
ТАУ-Дарвинизм: реализация на Ruby
Применение эволюционных стратегий для идентификации параметров нечетких систем
Вариант синхронной импульсной нейронной сети с обратными связями
«Живые графы» — выращивание графов на клеточных автоматах с примерами на Silverlight
Метод имитации отжига — как альтернатива
habrahabr.ru/blogs/personal/18844/
Генетический алгоритм: боремся с преждевременной сходимостью
Генетический алгоритм: оптимальный размер популяции
Генетический алгоритм на примере бота Robocode
Выбор размера популяции для генетического алгоритма
Генетические алгоритмы в MATLAB
Генетические алгоритмы для поиска решений и генерации
Концепции практического использования генетических алгоритмов
Что такое генетический алгоритм?
ТАУ-Дарвинизм
Обзор методов эволюции нейронных сетей
ТАУ-Дарвинизм: реализация на Ruby
Применение эволюционных стратегий для идентификации параметров нечетких систем
Вариант синхронной импульсной нейронной сети с обратными связями
«Живые графы» — выращивание графов на клеточных автоматах с примерами на Silverlight
Метод имитации отжига — как альтернатива
habrahabr.ru/blogs/personal/18844/
Хорошо, но просто — благо и задача несложная, что в реальном мире бывает редко…
Уравнения с целочисленными корнями… Вам наверно уже очевидно, что корни данного уравнения лежат на отрезке [1;30]
Лично мне это совсем не очевидно. Z = {...,-2, -1, 0, 1, 2, ...}
>Поскольку алгоритм самообучающийся
Мне одному показалась эта фраза несколько неверной?
Это алгоритм не управления, а оптимизации.
Причем это модификация простейшего алгоритма случайного поиска.
Алгоритм не в коем случае не самообучающийся.
Сходимость зависит от той задачи которую вы пытаетесь решить и от ее размерности.
Если использовать этот алгоритм использовать для решения системы двух линейных уравнений или к примеру восстановления исходной строчки(сама по себе это не задача, скорее способ проверить алгоритм), то сходимость будет высокой. Во-первых результат будет достигнут очень быстро, во-вторых очень точно.
Если же пытаться обучать нейронные сети, то тут может ждать разочарование, так как процесс обучения может затянуться на очень большое количество времени, а результат может совсем не обрадовать. Хотя конечно всегда все будет зависеть от задачи, размера обучающей выборки и так далее далее далее.
Автору так же думаю стоило упомянуть о том, что существует множество методов мутации генов и стратегий селекции.
А так конечно же спасибо за статью
Мне одному показалась эта фраза несколько неверной?
Это алгоритм не управления, а оптимизации.
Причем это модификация простейшего алгоритма случайного поиска.
Алгоритм не в коем случае не самообучающийся.
Сходимость зависит от той задачи которую вы пытаетесь решить и от ее размерности.
Если использовать этот алгоритм использовать для решения системы двух линейных уравнений или к примеру восстановления исходной строчки(сама по себе это не задача, скорее способ проверить алгоритм), то сходимость будет высокой. Во-первых результат будет достигнут очень быстро, во-вторых очень точно.
Если же пытаться обучать нейронные сети, то тут может ждать разочарование, так как процесс обучения может затянуться на очень большое количество времени, а результат может совсем не обрадовать. Хотя конечно всегда все будет зависеть от задачи, размера обучающей выборки и так далее далее далее.
Автору так же думаю стоило упомянуть о том, что существует множество методов мутации генов и стратегий селекции.
А так конечно же спасибо за статью
> Мне одному показалась эта фраза несколько неверной?
Тоже сразу хотел написать. Этот алгоритм не самообучающийся. Применительно к некоторому классу задач (например Нейросети) он сам является учителем.
> Если использовать этот алгоритм использовать для решения системы двух линейных уравнений или к примеру восстановления исходной строчки
А если использовать его в обработке сигналов для оптимизации нейросети хотя бы с 50-100 вещественных весовых коэффициентов, то пространство поиска разростается так, что и сходимость становится очень непредсказуемой и минимальный размер популяции становится слишком большим.
Тоже сразу хотел написать. Этот алгоритм не самообучающийся. Применительно к некоторому классу задач (например Нейросети) он сам является учителем.
> Если использовать этот алгоритм использовать для решения системы двух линейных уравнений или к примеру восстановления исходной строчки
А если использовать его в обработке сигналов для оптимизации нейросети хотя бы с 50-100 вещественных весовых коэффициентов, то пространство поиска разростается так, что и сходимость становится очень непредсказуемой и минимальный размер популяции становится слишком большим.
Не понял почему алгоритм новомодный если ему больше 35 лет?
«про новомодные алгоритмы, такие как нейронные сети»
Вы издеваетесь? Эти алгоритмы успели уже много раз появится, стать взрывобразно популярными, забыться и заново возродится.
Вы издеваетесь? Эти алгоритмы успели уже много раз появится, стать взрывобразно популярными, забыться и заново возродится.
Автозамена сработала: cc(c) на cc©© заменился.
Есть разновидность генетических алгоритмов — генетическое программирование. Очень понятно описано в захабренной книге «Программируем коллективный разум». Суть в том, что программы представляются в виде деревьев, и мутируют деревья.
Я сейчас веду проект в области поиска мошеннических схем в потребительском кредитовании, и попробовал применить эту методику на практике. Мутируемым решил сделать SQL. То есть представляем запрос типа
Если интересно, постараюсь выбрать время и написать полноценную статью. Алгоритм сходится неплохо на выборках свыше 1000 примеров при правильном выборе целевой функции (то, что автор поста назвал коэффициентом выживаемости). Скажем, до 200 поколений. Конечно, при условии, что в обучающей выбоке действительно есть паттерн, который можно отловить деревом решения.
Я сейчас веду проект в области поиска мошеннических схем в потребительском кредитовании, и попробовал применить эту методику на практике. Мутируемым решил сделать SQL. То есть представляем запрос типа
select * where x>10 and y<=23 and z=x в виде дерева select * where (((x>10) and y<=23) and z=x) и понеслась. В конце концов, это те же деревья решений, столь любимые работниками департаментов риск-менеджмента.Если интересно, постараюсь выбрать время и написать полноценную статью. Алгоритм сходится неплохо на выборках свыше 1000 примеров при правильном выборе целевой функции (то, что автор поста назвал коэффициентом выживаемости). Скажем, до 200 поколений. Конечно, при условии, что в обучающей выбоке действительно есть паттерн, который можно отловить деревом решения.
Вот если бы с каждым новым уравнением время решения сокращалось (засчет опыта предыдущих решений) — тогда было бы здорово. А так… Брутфорс…
это не в коем случае не брутфорс. Представьте себе 100мерное пространство признаков. Долго вы брутфорсить будете. В то время как генетические алгоритмы позволяют найти результат за более приемлемое время.
Причем учтите еще тот факт, что зачастую каждый признак это не дискретная величина с ограниченным диапазоном значений, а непрерывная величина в заранее неизвестных пределах. Так же существуют задачи у которых решение может быть не одно. При определенных модификациях ГА могут найти их.
Причем учтите еще тот факт, что зачастую каждый признак это не дискретная величина с ограниченным диапазоном значений, а непрерывная величина в заранее неизвестных пределах. Так же существуют задачи у которых решение может быть не одно. При определенных модификациях ГА могут найти их.
> Причем учтите еще тот факт, что зачастую каждый признак это не дискретная величина с ограниченным диапазоном значений, а непрерывная величина в заранее неизвестных пределах.
Во-первых, изначально (в классической постановке) ГА оптимизируют именно дискретные параметры (нуклеотид, как прообраз, имеет четыре значения А-Ц-Т-Г). Во-вторых, любой алгоритм, реализованный на ЭВМ работает с дискретными данными.
Но мысль ваша в принципе верна. 100 параметров даже в виде вещественного числа одинарной точности это (2^32)^100 пространство поиска. Если я ошибся с комбинаторикой — поправьте. Но пространство поиска действительно ООООЧЕНЬ огромное для простого брутфорса.
Во-первых, изначально (в классической постановке) ГА оптимизируют именно дискретные параметры (нуклеотид, как прообраз, имеет четыре значения А-Ц-Т-Г). Во-вторых, любой алгоритм, реализованный на ЭВМ работает с дискретными данными.
Но мысль ваша в принципе верна. 100 параметров даже в виде вещественного числа одинарной точности это (2^32)^100 пространство поиска. Если я ошибся с комбинаторикой — поправьте. Но пространство поиска действительно ООООЧЕНЬ огромное для простого брутфорса.
«Если вы не можете объяснить свою теорию своей жене, ваша теория ничего не стоит» — возможно, имелась в виду цитата Эйнштейна «Если вы что-то не можете объяснить 6-летнему ребёнку, вы сами этого не понимаете». Есть ещё похожие слова, приписываемые Курту Воннегуту: «Плох тот учёный, который не может объяснить суть своей теории пятилетнему ребёнку доступными для него словами». Вариант с женой какой-то неполиткорректный :-)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Генетический алгоритм. Просто о сложном. Рассказ Марка Андреева