Контекстная реклама → Методика и система увеличения привлекательности контекстных объявлений
Первое, что интересует клиента проводящего рекламную кампанию — её эффективность. Относительный показатель оценки эффективности — CTR или кликабельность, отношение числа кликов по рекламному объявлению к числу показов. Можно сказать, что CTR — это мера качества рекламного объявления. Чем качественнее объявление, тем выше его позиция, больше показов и дешевле обходятся переходы. Методикой и системой, помогающей увеличивать качество объявлений, я и хочу с вами поделиться.
Алгоритмы → Генетический алгоритм. Просто о сложном из песочницы
В последнее время все больше «ходят» разговоры про новомодные алгоритмы, такие как нейронные сети и генетический алгоритм. Сегодня я расскажу про генетические алгоритмы, но давайте на этот раз постараемся обойтись без заумных определений и сложных терминах.
Как сказал один из великих ученных: «Если вы не можете объяснить свою теорию своей жене, ваша теория ничего не стоит!» Так давайте попытаемся во всем разобраться по порядку.
Как сказал один из великих ученных: «Если вы не можете объяснить свою теорию своей жене, ваша теория ничего не стоит!» Так давайте попытаемся во всем разобраться по порядку.
Алгоритмы → Генетический алгоритм: оптимальный размер популяции
В предыдущем очерке (Генетический алгоритм: боремся с преждевременной сходимостью) в качестве эффективного метода борьбы с преждевременной сходимостью было выбрано использование оператора митоза:
Каждая хромосома, к которой применен оператор митоза, заведомо производит как минимум одного полностью идентичного ей самой потомка.
Помимо этого, чем больше приспособленность хромосомы превышает среднее значение приспособленности по всей популяции, тем больше вероятность того, что хромосома произведет второго потомка.
Хромосомы с меньшей приспособленностью формируют пул для скрещивания между собой. Попарное скрещивание хромосом из пула проводится до тех пор пока не будет достигнута требуемая общая численность популяции (с учетом хромосом уже созданных с помощью оператора митоза). Выбор хромосом для скрещивания производится случайным образом методом рулетки (хромосомам с большей приспособленностью соответствует больший сектор на колесе рулетки). Численность популяции остается постоянной на протяжении всего времени работы генетического алгоритма.
Доля хромосом к которым применяется оператор митоза обратно пропорциональна средней величине приспособленности популяции и прямо пропорциональна среднеквадратичному отклонению приспособленности популяции (причем зависимость выбираем не линейную, а логарифмическую). Для первого поколения задаем долю популяции, размножающейся митозом, равной 50%
Каждая хромосома, к которой применен оператор митоза, заведомо производит как минимум одного полностью идентичного ей самой потомка.
Помимо этого, чем больше приспособленность хромосомы превышает среднее значение приспособленности по всей популяции, тем больше вероятность того, что хромосома произведет второго потомка.
Хромосомы с меньшей приспособленностью формируют пул для скрещивания между собой. Попарное скрещивание хромосом из пула проводится до тех пор пока не будет достигнута требуемая общая численность популяции (с учетом хромосом уже созданных с помощью оператора митоза). Выбор хромосом для скрещивания производится случайным образом методом рулетки (хромосомам с большей приспособленностью соответствует больший сектор на колесе рулетки). Численность популяции остается постоянной на протяжении всего времени работы генетического алгоритма.
Доля хромосом к которым применяется оператор митоза обратно пропорциональна средней величине приспособленности популяции и прямо пропорциональна среднеквадратичному отклонению приспособленности популяции (причем зависимость выбираем не линейную, а логарифмическую). Для первого поколения задаем долю популяции, размножающейся митозом, равной 50%
Алгоритмы → Генетический алгоритм: боремся с преждевременной сходимостью
В предыдущем очерке (Выбор размера популяции для генетического алгоритма) был определен минимальный размер популяции необходимый для работоспособности генетического алгоритма:
N = 1 + LOG2(1/(1-P1^(1/L))), где
P1 — требуемая вероятность того, что случайный набор хромосом будет содержать все необходимые элементы для каждого локуса;
L — длина хромосомы.
В реальности данный размер популяции будет необходимым, но не достаточным для эффективной работы генетического алгоритма.
Происходит это из за преждевременной сходимости — остановки алгоритма до достижения глобального максимума (а зачастую и до достижения даже локальных максимумов).
Причина этого заложена в самой природе алгоритма: чем выше приспособленность хромосомы тем больше вероятность того, что она примет участие в скрещивании. Соответственно, тем большее количество раз она сможет принять участие в скрещивании.
Таким образом, генетический код хромосом, функция приспособленности которых существенно превышает среднее значение для популяции, получая преимущество, вытесняет из популяции другие наборы генетического кода.
Но если приспособленность таких хромосом, значительно меньше чем глобальный максимум функции приспособленности (а для начальных стадий это естественно), а размер популяции не достаточен для поддержания разнообразия, то преждевременная сходимость к значениям далеко отстоящим от оптимальных (или, в лучшем случае, сходимость к локальным максимумам) гарантированна.
Так как даже если в дальнейших генерациях популяции появится хромосома с гораздо большей приспособленностью, то к этому моменту предыдущие лидеры уже успеют сильно размножится и есть вероятность того, что новый лидер будет просто «вытеснен» из популяции, до того как успеет в ней «закрепиться».
Сам собой напрашивается экстенсивный путь борьбы с этим явлением — увеличение размера популяции, но найти интенсивный (не ресурсозатратный) путь гораздо интересней.
N = 1 + LOG2(1/(1-P1^(1/L))), где
P1 — требуемая вероятность того, что случайный набор хромосом будет содержать все необходимые элементы для каждого локуса;
L — длина хромосомы.
В реальности данный размер популяции будет необходимым, но не достаточным для эффективной работы генетического алгоритма.
Происходит это из за преждевременной сходимости — остановки алгоритма до достижения глобального максимума (а зачастую и до достижения даже локальных максимумов).
Причина этого заложена в самой природе алгоритма: чем выше приспособленность хромосомы тем больше вероятность того, что она примет участие в скрещивании. Соответственно, тем большее количество раз она сможет принять участие в скрещивании.
Таким образом, генетический код хромосом, функция приспособленности которых существенно превышает среднее значение для популяции, получая преимущество, вытесняет из популяции другие наборы генетического кода.
Но если приспособленность таких хромосом, значительно меньше чем глобальный максимум функции приспособленности (а для начальных стадий это естественно), а размер популяции не достаточен для поддержания разнообразия, то преждевременная сходимость к значениям далеко отстоящим от оптимальных (или, в лучшем случае, сходимость к локальным максимумам) гарантированна.
Так как даже если в дальнейших генерациях популяции появится хромосома с гораздо большей приспособленностью, то к этому моменту предыдущие лидеры уже успеют сильно размножится и есть вероятность того, что новый лидер будет просто «вытеснен» из популяции, до того как успеет в ней «закрепиться».
Сам собой напрашивается экстенсивный путь борьбы с этим явлением — увеличение размера популяции, но найти интенсивный (не ресурсозатратный) путь гораздо интересней.
Ruby → ТАУ-Дарвинизм: реализация на Ruby
Предисловие
Послушайте, ворона, а может быть собака,
А может быть корова, но тоже хорошо!
У вас такие перья, у вас рога такие,
Копыта очень стройные и добрая душа.
Мультфильм «Пластилиновая ворона».
В этой статье представляю Вашему вниманию реализацию эволюционного подхода к идентификации динамической системы. Программа написана на языке Ruby версии 1.9.2 (gems: NArray, GNUPlot). Заглянув под кат найдете пример вещественного кодирования генной информации и подходящего для него алгоритма скрещивания («flat crossover»).
Алгоритмы → Выбор размера популяции для генетического алгоритма из песочницы
Для души экспериментирую с генетическими алгоритмами.
Хотелось немного поделиться своим опытом, наблюдениями, размышлениями в небольшой серии очерков.
Итак, первый вопрос над которым задумался: какой размер популяции выбирать.
Если сформулировать этот вопрос системно, то он будет звучать так:
По какому принципу, исходя из каких критериев, рассчитывать размер популяции?
Хотелось немного поделиться своим опытом, наблюдениями, размышлениями в небольшой серии очерков.
Итак, первый вопрос над которым задумался: какой размер популяции выбирать.
Если сформулировать этот вопрос системно, то он будет звучать так:
По какому принципу, исходя из каких критериев, рассчитывать размер популяции?
Алгоритмы → Генетические алгоритмы для поиска решений и генерации
В этой статье я на некоторое время отойду от железок и схемотехники и вернусь к более высокоуровневому программированию. Предлагаю вашему вниманию небольшой демо-проект, показывающий возможности генетических алгоритмов.
Алгоритмы → Генетические алгоритмы в MATLAB из песочницы
Суть генетических алгоритмов
Данный топик посвящен решению оптимизационных задач при помощи генетических алгоритмов в среде MATLAB. Заранее приношу извинения за большой объем данных: он обусловлен тем, что при написании топика основной поставленной задачей было подробно раскрыть каждый из настраиваемых в MATLAB параметров работы генетических алгоритмов.
Генетические алгоритмы – это метод решения оптимизационных задач, основанный на биологических принципах естественного отбора и эволюции. Генетический алгоритм повторяет определенное количество раз процедуру модификации популяции (набора отдельных решений), добиваясь тем самым получения новых наборов решений (новых популяций). При этом на каждом шаге из популяции выбираются «родительские особи», то есть решения, совместная модификация которых (скрещивание) и приводит к формированию новой особи в следующем поколении. Генетический алгоритм использует три вида правил, на основе которых формируется новое поколение: правила отбора, скрещивания и мутации. Мутация позволяет путем внесения изменений в новое поколение избежать попадания в локальные минимумы оптимизируемой функции.
(Под катом основная часть + несколько скриншотов).
Алгоритмы → Увеличение поисковых способностей генетических алгоритмов с помощью прогнозирования временных рядов из песочницы
На написание статьи, подтолкнула публикация Прогнозирование временных рядов.
Здесь я покажу, как прогнозирование временных рядов может быть применено для увеличения поисковых способностей (ПС) генетических алгоритмов (ГА).
Здесь я покажу, как прогнозирование временных рядов может быть применено для увеличения поисковых способностей (ПС) генетических алгоритмов (ГА).
Алгоритмы → ТАУ-Дарвинизм
Предисловие
— Кибердворник дядя Федя силой ровно в три медведя, — сообщил Поль, извлекая из недр кибердворника блок регулировки. — Я тут уже знаю одного Федю. Приятный такой, веснушчатый. Очень, очень асептический молодой человек. Это не твой родственник?
Аркадий и Борис Стругацкие (Полдень. ХХII век).
Статья посвящена вопросу применимости генетических алгоритмов к проблеме идентификации динамической системы.
Обновлено: опубликовано продолжение ТАУ-Дарвинизм: реализация на Ruby