Генетический алгоритм — способ оптимизации, какой-либо функции. Но, в нашем случае, мне просто был интересен принцип его работы, своеобразное моделирование эволюции. Ну и чтобы проэволюционировать самому. Мы имеем абстрактное поле, в котором есть организмы (синие и бирюзовые клетки), еда (зеленые) и яд (красные).
У созданий всего 64 гена, но можно ввести всего лишь 10 первых.
Привет, Хабражитель!
Не так давно, вышло очередное дополнение World of Warcraft Legion. Первым делом я принялся прокачивать шамана. В оплоте шаманов я забрел к Мастеру головоломок Ло и увидел то, что вы подумали — головоломку.
Передо мной был квадрат из огненных и водных тотемов 5 на 5, после того как кликаешь на тотем, он меняется на противоположный, например водный на огненный или огненный на водный и так же меняет соседние тотемы сверху, снизу, слева и справа. Необходимо сделать так, что бы все тотемы стали водными. После первого клика я понял, что срочно нужно написать решение для этой классной головоломки.
Что из этого получилось, читай под катом.
Года четыре назад, в универе услышал о таком методе оптимизации, как генетический алгоритм. О нем везде сообщалось ровно два факта: он клёвый и он не работает. Вернее, работает, но медленно, ненадежно, и нигде его не стоит использовать. Зато он красиво может продемонстрировать механизмы эволюции. В этой статье я покажу красивый способ вживую посмотреть на процессы эволюции на примере работы этого простого метода. Нужно лишь немного математики, программирования и все это приправить воображением.
Итак, что же такое генетический алгоритм? Это, прежде всего, метод многомерной оптимизации, т.е. метод поиска минимума многомерной функции. Потенциально этот метод можно использовать для глобальной оптимизации, но с этим возникают сложности, опишу их позднее.
Сама суть метода заключается в том, что мы модулируем эволюционный процесс: у нас есть какая-то популяция (набор векторов), которая размножается, на которую воздействуют мутации и производится естественный отбор на основании минимизации целевой функции. Рассмотрим подробнее эти процессы.
Читать полностью »
Художник Стерлинг Криспин (Sterling Crispin) продолжает пополнять на своём сайте коллекцию дата-масок, созданных специально для обмана алгоритмов распознавания лиц в уличных видеокамерах наблюдения.
Программы компьютерного зрения после тренировки на больших коллекциях фотографий вырабатывают специфические признаки, по которым отличают один объект от другого. Эти признаки можно вычислить, если скрестить алгоритм генерации случайных изображений с системой распознавания образов.
Читать полностью »
Сегодня мы хотели бы рассказать о своем исследовании в области персонализации новостной ленты в рамках проекта favoraim. Сама идея показывать пользователю только те новости (далее записи), которые будут ему интересны, не новая и вполне естественная. Для решения этой задачи есть устоявшиеся и хорошо зарекомендовавшие себя модели.
Принцип работы этих алгоритмов похож: мы анализируем реакцию пользователей (feedback) на предыдущие записи и пытаемся прогнозировать его реакцию на текущие события. Если реакция «положительная», событие попадает в ленту, если «отрицательная» — не попадает. Читать полностью »
Приветствую уважаемое читатели!
В данной статье я хотел бы рассказать о том как я решал транспортную задачу при помощи генетического алгоритма.
Википедия формулирует задачу следующим образом — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе.
Например – необходимо спланировать доставку бутылей воды по городу, известны потребности каждого заказчика, грузоподъёмность транспортных средств и расстояния между точками.
Недавно на хабре проскочил пост, который напомнил мне о такой забавной и довольно интересной вещи, как BoxCar2D (Оригинал, Версия из поста), которую в первый раз я увидел пару лет назад, и которая меня порядком впечатлила. И уже тогда я подметил в ней один фатальный недостаток (вкратце — ее сделал не я), но в тот раз руки так и не дошли до его исправления. И вот теперь я решил это исправить.
Итак, я расчехлил Visual Studio и принялся за дело.
Первым делом я просто повторил функционал BoxCar2D, а именно: фиксированный размер популяции, которая проживает свою жизнь и порождает следующее поколение. Можно было поиграться с тем, как усложняется трасса со временем, что содержит в себе геном и как машинки скрещиваются и мутируют.
Читать полностью »
В продолжение предыдущей игры — Эволюция гоночных автомобилей на JavaScript
Эта игра теперь сетевая, все игроки деляться своими лучшими машинками в каждом раунде. Лучшая машинка каждого игрока игрового мира добавляется к вам в список машин текущего уровня. Лучшие машинки передаются по миру друг другу пользователями которые прямо сейчас играют, используя PubNub Real-time Network.
Сорцы: https://github.com/pubnub/genetic-car-2
Играть на http://gencar.co/
Возможно, вам доводилось видеть игру Box Car 2D — автогонки машинок, сгенерированных с помощью генетического алгоритма. Игра работает на платформе Flash и использует физический движок box2d. За тем, как из бесформенных уродцев через несколько десятков поколений развиваются вполне приличные гоночные автомобили, можно наблюдать часами. Игра существует уже несколько лет, а её фанаты соревнуются в выведении новых «пород» машинок на разных типах трасс. Недавно в сети появился клон этой игры под названием Genetic Cars, написанный на HTML5 и JavaScript. Хотя в нем ещё многого не хватает (например, редактора машинок), некоторые вещи сделаны гораздо лучше, чем в оригинале. Например, есть возможность наблюдать заезд всех машинок одновременно. И самое главное — можно ковыряться в исходниках!
