Понимание аспектов эволюционного программирования с генетическими алгоритмами

Введение

  • Генетические алгоритмы — это алгоритмы поиска и оптимизации общего назначения, которые используют принципы, вдохновленные естественной популяционной генетикой, для поиска решений проблем.
  • GA основан на эволюционном программировании и использует оптимизацию стохастического градиента.
  • ГА работает с популяцией людей, представляющих потенциальные решения данной проблемы.
  • ГА стремятся производить лучших (более подходящих) особей (решений), комбинируя лучшие из существующих (через скрещивание, скрещивание и мутацию).

Жизненный цикл эволюционного алгоритма

  • Сначала мы определяем нашу проблему и нашу целевую функцию.
  • Мы определяем наш начальный размер популяции.
  • Мы выполняем генетические операции, такие как отбор, скрещивание и мутация в выбранной популяции, чтобы получить более подходящие гены для следующего поколения.

  • Отбор — фокусирует внимание на людях с высокой физической подготовкой, используя, таким образом, доступную информацию о физической подготовке. Структуры с высокой производительностью могут быть выбраны для репликации несколько раз, а структуры с низкой производительностью могут вообще не выбираться.
  • Кроссовер — объединяет черты двух родительских структур (новые комбинации генов генерируются из предыдущих) для образования двух похожих потомков.
  • Мутация — случайным образом изменяет один или несколько компонентов выбранной структуры (прямая аналогия с природой и дает возможность ввести новую информацию в популяцию).
  • Этот процесс продолжается до тех пор, пока мы не достигнем глобального оптимального значения с наилучшей возможной оценкой пригодности для генов.

Процесс поиска в Google Аналитике

  • Во-первых, мы инициализируем случайное пространство выборки для нашей начальной популяции. Он должен представлять собой случайную выборку пространства поиска. Каждый член популяции оценивается и назначается мера его пригодности в качестве решения.
  • Затем участники выбираются на основе функции пригодности, определенной нами. Структуры в текущей популяции выбираются для репликации на основе их относительной пригодности. Генетические операторы (кроссовер, мутация) выполняются для создания новой популяции.
  • Полученное потомство затем оценивают и возвращают в популяцию, заменяя старших членов.
  • Конкретные решения о том, сколько элементов заменяется во время каждой итерации и как выбираются элементы для замены, определяют диапазон альтернативных реализаций.
  • Поколенческие GA-GA, которые заменяют все население
  • Стационарные GA-GA, которые заменяют лишь небольшую часть хромосом. Как правило, новые хромосомы заменяют худшие хромосомы.

Псевдокод GA

Пример реализации функции GA

Аналитические приложения

  • Комбинаторная оптимизация
  • Проблемы с распределением ресурсов
  • Классическая задача коммивояжера / упаковки в мусорное ведро / составления расписания работы магазина и т. д.
  • Финансовое прогнозирование
  • Оптимизация проектирования — маршрутизация сети, выбор спутниковой орбиты и т. д.
  • Оптимизация функции потерь машинного обучения

использованная литература