• Генетический алгоритм — наглядная реализация

    Года четыре назад, в универе услышал о таком методе оптимизации, как генетический алгоритм. О нем везде сообщалось ровно два факта: он клёвый и он не работает. Вернее, работает, но медленно, ненадежно, и нигде его не стоит использовать. Зато он красиво может продемонстрировать механизмы эволюции. В этой статье я покажу красивый способ вживую посмотреть на процессы эволюции на примере работы этого простого метода. Нужно лишь немного математики, программирования и все это приправить воображением.

    Кратко об алгоритме


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

    Сама суть метода заключается в том, что мы модулируем эволюционный процесс: у нас есть какая-то популяция (набор векторов), которая размножается, на которую воздействуют мутации и производится естественный отбор на основании минимизации целевой функции. Рассмотрим подробнее эти процессы.
    Читать дальше →
  • Что такое деревья поведения и как они используются



      / фото Harry Li CC

      Нас в компании «ИТ-ГРАД» очень интересуют вопросы искусственного интеллекта. Мы уже затрагивали тему автопилотируемых автомобилей, а неделю назад публиковали материал, в котором рассказывали о новых достижениях ученых и разработчиков в сфере ИИ, а также об опасениях скептиков.

      Сегодня мы вновь коснемся этого вопроса и поговорим о том, что такое деревья поведения, как они используются в робототехнике и есть ли у них будущее.
      Читать дальше →
      • +17
      • 18.5k
      • 4
    • Реализация графов и деревьев на Python

        Продолжаем публикацию наиболее интересных глав из книги Magnus Lie Hetland «Python Algorithms». Предыдущая статья расположена по адресу habrahabr.ru/blogs/algorithm/111858. Сегодня же речь пойдет об эффективной работе с графами и деревьями и особенностях их реализации в Python. Базовая терминология теории графов уже обсуждалась (например здесь: habrahabr.ru/blogs/algorithm/65367), так что я не включил часть главы о терминах в эту статью.

        Реализация графов и деревьев


        Многие задачи, например, задача обхода точек по кратчайшему маршруту, могут быть решены с помощью одного из мощнейших инструментов — с помощью графов. Часто, если вы можете определить, что решаете задачу на графы, вы по-крайней мере на полпути к решению. А если ваши данные можно каким-либо образом представить как деревья, у вас есть все шансы построить действительно эффективное решение.
        Читать дальше →
      • Генетический алгоритм и виртуальный мир ботов

          Не так давно я написал публикацию про генетический алгоритм и геном, состоящий из одной инструкции.


          Хочу поделиться с читателями Geektimes видео от foo52ru, которое стало стимулом для экспериментов и во многом определило содержание моей работы.
        • Генетическое программирование («Yet Another Велосипед» Edition)


            Давайте на время отвлечемся от очередного "языка-убийцы C++", ошеломляющих синтетических тестов производительности какой-нибудь NoSQL-ой СУБД, хайпа вокруг нового JS-фреймворка, и окунемся в мир "программирования ради программирования".

            Читать дальше →
          • Выразительный JavaScript: Проект «Электронная жизнь»

            • Translation

            Содержание




            Вопрос о том, могут ли машины думать так же уместен, как вопрос о том, могут ли подводные лодки плавать.

            Эдсгер Дейкстра, Угрозы вычислительной науке


            В главах-проектах я перестану закидывать вас теорией, и буду работать вместе с вами над программами. Теория незаменима при обучении программированию, но она должна сопровождаться чтением и пониманием нетривиальных программ.

            Наш проект – постройка виртуальной экосистемы, небольшого мира, населённого существами, которые двигаются и борются за выживание.
            Читать дальше →
            • +26
            • 43.3k
            • 4
          • Приемы при проектировании архитектуры игр

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

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

              В публикации рассматриваются следующие темы:
              • Наследование VS компоненты
              • Сложные иерархии классов юнитов, предметов и прочего
              • Машины состояний, деревья поведений
              • Абстракции игровых объектов
              • Упрощение доступа к другим компонентам в объекте, сцене
              • Сложные составные игровые объекты
              • Характеристики объектов в игре
              • Модификаторы (баффы/дебаффы)
              • Сериализация данных

              Читать дальше →
            • Игра «Жизнь» и моделирование естественного отбора

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

                Я задумался об игре «Жизнь», которую на Хабре не так давно вспоминали. Мне стало обидно за несчастные клетки, которые живут и умирают в зависимости от одних только начальных условий, и ничего сами для своего выживания сделать не могут. В результате я придумал расширение для правил игры, с которым можно моделировать не только изменение численности популяции, но и естественный отбор внутри неё.

                Самые нетерпеливые сразу могут посмотреть, что получилось, а остальных прошу под кат за рассказом.
                Читать дальше →
              • Игра «Жизнь»: моделируем эволюцию

                  В комментариях к моему предыдущему посту «Игра «Жизнь» и моделирование естественного отбора» первое же, что предложили, — добавить скрещивание, чтобы новая клетка получала не копию генома одного родителя, а смесь от нескольких. Я подозревал, что итог это не изменит. Но, покрутив в голове идею, заинтересовался: ведь так можно получить модель не просто естественного отбора, а уже полноценной эволюции. Благо, реализовать это было не сложно. Так что встречайте: «Жизнь», теперь со скрещиванием и мутациями.

                  Ну да, ещё и с мутациями. Моделировать, так моделировать.

                  Подробности, как водится, под катом.
                  Читать дальше →
                • Поиграем в эволюцию? Генетические алгоритмы в скринсейвере

                  Последний месяц в армии. Постепенно освобождается время для разных интересных проектов. Остается только определиться, чем именно занять мозги. Закончил читать «Эгоистичный ген» Ричарда Докинза и идея была сформулирована – хочу сделать визуализацию, использующую принципы эволюции.

                  image
                  Рисунок 1. Популяция бактерий перестраивает среду под свои нужды.

                  Итак, вперед!
                  Читать дальше →
                • AI монстров и поиск пути с помощью тепловых карт

                    image Допустим, у нас есть плоская карта, состоящая из тайлов. На некоторых тайлах стоят монстры, а на некоторых других – всякие штуки, которые монстров интересуют: игрок, оружие, зелья, боеприпасы и прочее в том же духе. Задача состоит в том, чтобы объяснить монстрам, к каким штукам им идти и как. Путь должен быть близким к оптимальному, а время вычисления – настолько маленьким, насколько это возможно. Один из самых простых способов – использовать тепловую карту дистанций до определённой цели или целей.
                    Читать дальше →
                  • Сотворение мира Опыт создания разумной жизни своими руками

                    Иногда проводишь день в попытках без использования терминов «рекурсивный вызов» и «идиоты» объяснить главному бухгалтеру, почему на самом деле простое изменение учетной системы затягивается почти на неделю из-за орфографической ошибки, допущенной кем-то в коде в 2009 году. В такие дни хочется пооборвать руки тому умнику, который сотворил этот мир, и переписать все с ноля.

                    image

                    TL;DR
                    Под катом история о том, как я в качестве практики для изучения Python разрабатываю свою библиотеку для агентного моделирования с машинным обучением и богами.

                    Ссылка на github. Для работы из коробки нужен pygame. Для ознакомительного примера понадобится sklearn.
                    Читать дальше →
                  • Evo, часть 2 — о скрещивании

                      Приветствую вас, хабражители!

                      В продолжение поста «Аналог игры «Жизнь» — Evo» хотелось бы дать более подробное описание команд «языка генов», который используется в Evo, и поделиться своими соображениями по методам скрещивания особей в этой игре.
                      Читать дальше →
                    • Аналог игры «Жизнь» — Evo

                      Приветствую вас, хабражители!

                      Недавно прочитал статью про игру Жизнь, и вспомнилось мне, что я в мае этого года начинал писать свой проект подобной направленности. Только вот интерес к нему за рутиной работы быстро угас, хотя написано было немало. И сейчас, вдохновлённый этой статьёй, я взял этот проект с пыльной полки и добавил несколько фич, о которых расскажу далее.
                      Вкратце, мой вариант имеет следующие условия:
                      • жизнь развивается на поле 256*256 клеток;
                      • на поле могут размещаться объекты трёх типов: живность, пища(назовем её травой) и камень (препятствие);
                      • живность представляет собой фактически модифицированную машину Тьюринга, если точнее, то это больше похоже на Автомат с магазинной памятью, т.е. живность является «процессором», выполняющим свой «генетический» код;
                      • живность имеет возможность совершать определенные действия (двигаться, есть, размножаться (пока только клонированием, мутации будут со дня на день, скрещивание в перспективе)), отдавая соответствующие команды;
                      • наступив на траву, живность её вытаптывает;
                      • для поглощения еды надо дать команду «Ешь в этом направлении!», находясь в соседней клетке;
                      • живность имеет память, что позволяет строить циклы, условия и т.п., т.е. полная по Тьюрингу (поправьте меня, если не прав!), объем памяти неограничен;
                      • живность может складывать и вычитать значения в уме, разрядность ограничена одним байтом;
                      • существует возможность реализации генетических алгоритмов (пока не реализовано).
                      Кому интересны подробности, прошу под кат!

                      Читать дальше →
                    • Генетический алгоритм своими руками

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


                      image


                      У созданий всего 64 гена, но можно ввести всего лишь 10 первых.


                      Читать дальше →
                    • EvoJ — удобный фреймворк для генетических алгоритмов

                      Здравствуйте, коллеги!

                      Здесь часто появляются статьи на тему генетических алгоритмов, разрешите и мне внести свои пять копеек.

                      Вот уже пару лет я виде хобби разрабатываю Java-фреймворк EvoJ посвященный ГА. Когда я только начинал работу с ГА самое большое неудобство представляла необходимость векторизации переменных составляющих решение, поэтому в своем фреймворке я постарался сделать векторизацию переменных прозрачной для программиста, возложив всю грязную работу на плечи фреймворка. Кроме того, так как ГА очень хорошо поддается распараллеливанию, я постарался сделать переход к многопоточности не менее легким.
                      Читать дальше →
                    • Природный генетический алгоритм или доказательство эволюции живых организмов на C++

                      Введение


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

                      Одним из наиболее распространенных методов естественных вычислений являются генетические алгоритмы. Чтобы лучше разобраться, как эти алгоритмы устроены и как работают, было решно воспроизвести один из таких алгоритмов — генетический. Для того, чтобы применять какой-либо метод для решения конкретных задач этот метод необходимо освоить. Поэтому генетический алгоритм, рассмотренный в данной работе, не решает никакой конкретной задачи. Главными являются одновременно процесс и результат работы по созданию программы по моделированию и визуализации работы генетического алгоритма. Важен полученный программистский опыт.
                      Программа моделирует поведение популяции самых примитивных живых организмов. Эта программа вряд ли будет иметь какое-либо практическое применение, но она наглядно иллюстрирует принцип работы генетических алгоритмов.

                      Моделирование работы генетического алгоритма, в котором естественный отбор определяется условиями среды


                      Моделирование – метод научного познания объективного мира через построение и изучение моделей.

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

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

                      Для работы выбран язык программирования C++, так как этот язык является мощным, проверенным временем языком программирования. C++ получил широкое распространение среди программистов. Для визуализации использована открытая графическая библиотека OpenGL.
                      Читать дальше →