Хабрахабр: Метки / генетический алгоритм

Алгоритмы / Генетический алгоритм: оптимальный размер популяции

aLelik — Sun, 31 Jul 2011 18:53:38 GMT

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

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

Хромосомы с меньшей приспособленностью формируют пул для скрещивания между собой. Попарное скрещивание хромосом из пула проводится до тех пор пока не будет достигнута требуемая общая численность популяции (с учетом хромосом уже созданных с помощью оператора митоза). Выбор хромосом для скрещивания производится случайным образом методом рулетки (хромосомам с большей приспособленностью соответствует больший сектор на колесе рулетки). Численность популяции остается постоянной на протяжении всего времени работы генетического алгоритма.

Доля хромосом к которым применяется оператор митоза обратно пропорциональна средней величине приспособленности популяции и прямо пропорциональна среднеквадратичному отклонению приспособленности популяции (причем зависимость выбираем не линейную, а логарифмическую). Для первого поколения задаем долю популяции, размножающейся митозом, равной 50%

далее небольшой анализ выбора оптимального размера популяции

Алгоритмы / Генетический алгоритм: боремся с преждевременной сходимостью

aLelik — Sun, 26 Jun 2011 20:05:27 GMT

В предыдущем очерке (Выбор размера популяции для генетического алгоритма) был определен минимальный размер популяции необходимый для работоспособности генетического алгоритма:
N = 1 + LOG2(1/(1-P1^(1/L))), где
P1 — требуемая вероятность того, что случайный набор хромосом будет содержать все необходимые элементы для каждого локуса;
L — длина хромосомы.

В реальности данный размер популяции будет необходимым, но не достаточным для эффективной работы генетического алгоритма.
Происходит это из за преждевременной сходимости — остановки алгоритма до достижения глобального максимума (а зачастую и до достижения даже локальных максимумов).
Причина этого заложена в самой природе алгоритма: чем выше приспособленность хромосомы тем больше вероятность того, что она примет участие в скрещивании. Соответственно, тем большее количество раз она сможет принять участие в скрещивании.
Таким образом, генетический код хромосом, функция приспособленности которых существенно превышает среднее значение для популяции, получая преимущество, вытесняет из популяции другие наборы генетического кода.

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

Сам собой напрашивается экстенсивный путь борьбы с этим явлением — увеличение размера популяции, но найти интенсивный (не ресурсозатратный) путь гораздо интересней.

Добро пожаловать под кат

DIY или Сделай Сам / Генетический алгоритм на примере бота Robocode

kefiijrw — Mon, 24 Jan 2011 18:25:16 GMT

Когда писалась эта статья, хабрапоиск по словосочетанию «Генетический алгоритм» выдавал благородную пустоту. Однако недостаточный уровень *вырезано цензурой* отодвинул дату публикации, и вот только сейчас после позорного нудливого попрошайничества с моей стороны эта статья получила возможность показать себя миру. За этот промежуток времени успели выйти в свет как минимум три (столько мне на глаза попалось) статьи на подобную тему, и, вполне вероятно, что-то из написанного ниже вы прочитаете не впервые. Таким людям я предлагаю не хмурить носики от очередной попытки неопытного юнца научно-популярно объяснить ГА, а проходить ~~к следующему экспонату~~ ко второй части, где описывается создание на основе ГА бота для программистской игры Robocode. Это, по последним сведениям разведки, еще не встречалось на хабре.

Часть первая. Жизнь и творчество генетического алгоритма.

Начнем издалека. Есть некоторый набор задач, которые требуют решения. Наша цель — найти действия, которые смогут преобразовать Дано (начальные условия задач) в Ответ (целевое состояние).

Если ситуация простая, и решение такой задачи можно явно посчитать из условий при помощи этих ваших матанов, то и славно, тут и без наших премудростей все хорошо, ~~нас наебали, все расходимся~~. Например, при решении квадратного уравнения ответ (нахождение значений x1, x2) получаются из начального условия (коэффициентов a, b, c) путем применения формулы, которую мы все учили в школе. А что делать в более печальном случае, когда нужной формулы в учебнике нету? Можно попробовать с помощью мозгового штурма решить одну из задач. Аналитически. Численными методами. Силой отчаянного перебора функций. Через некоторое время послышатся мечтательное студенческое «хоть бы оно само решилось». Ага, тут-то мы и вылезаем из-за занавесок. Итак, цель — написать программу, которая бы находила функцию (программу), получающую на вход исходные данные и возвращающую годные циферки. Сила метапрограммирования, в бой!

пучина невежества

Алгоритмы / [Из песочницы] Увеличение поисковых способностей генетических алгоритмов с помощью прогнозирования временных рядов

mdfyz — Wed, 05 Jan 2011 13:07:30 GMT

На написание статьи, подтолкнула публикация Прогнозирование временных рядов.

Здесь я покажу, как прогнозирование временных рядов может быть применено для увеличения поисковых способностей (ПС) генетических алгоритмов (ГА).

Читать дальше →

Ненормальное программирование / Выращиваем программы

Hizof — Tue, 04 Jan 2011 15:10:54 GMT

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

Читать дальше →

Учебный процесс в IT / Что такое генетический алгоритм?

freetonik — Mon, 08 Mar 2010 17:28:46 GMT

В рамках проекта Computer Science Student сегодня я постараюсь дать короткое наглядное объяснение: что такое генетический алгоритм? В самой простой и общей формулировке для решения самой простой задачи. Исходные коды решения (код не самый качественный, потому что писался на скорую руку; но код и не важен в этом курсе) и текст самих заданий доступен на CS-Student Wiki.

Первая часть

Вторая часть — под катом.

Читать дальше →

Алгоритмы / Векторизуем изображение генетическим алгоритмом

SkywalkerY — Sun, 30 Aug 2009 07:26:52 GMT

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

Хочу знать как!

Искусственный интеллект / Ломаем каптчу Яндекса

P_r_i_m_a_t — Wed, 15 Jul 2009 11:13:24 GMT

На прошлой неделе был топик «Ломаем капчу» — каптча там была довольно простая, но в комментариях предложили сломать каптчу Яндекса. Мне эта идея показалась интересной, и я решил попробовать.

Читать дальше →