Генетические алгоритмы

Генетические алгоритмы (genetic algorithms - GA, эволюционные вычисления) - это один из важнейших компонентов искусственного интеллекта (artificial life) - совокупности методов построения динамических моделей сложных, быстро меняющихся объектов и явлений.Любой проектировщик сложных систем сталкивается с одним и тем же комплексом проблем, плохо поддающихся решению традиционными методами теории управления, оптимизации и системного анализа. Неполнота знаний о внешнем мире, неизбежная погрешность датчиков, непредсказуемость реальных ситуаций - все это заставляет разработчиков мечтать об интеллектуальных системах, способных подстраиваться к изменению "правил игры" и самостоятельно адаптироваться в процессе динамического моделирования "условий, приближенных к боевым".Впервые построение таких систем стало возможно благодаря применению генетических алгоритмов. [подробнее...]

Решаемые задачи

Примеры решений / Продукты

Статьи по данной технологии:
1.  "Тропою Создателя - Первые шаги "искусственной жизни""








Решаемые задачи :

Многие представители большого бизнеса (в том числе такие гиганты, как Ford) заявляют, что уже давно используют элементы A-life (и, в частности, генетические алгоритмы) в ситуационном моделировании и деловых играх для руководителей. Промышленники применяют методы A-life в первую очередь при создании разнообразных роботов, манипуляторов и автоматизированных производств. Одно из определений A-life даже трактует ее как теорию управления сообществом роботов, решающих навигационные задачи путем адаптации к внешним условиям. Разработчики БИС всерьез увлечены разработкой нового поколения микросхем, реализующих базовые алгоритмы A-life "в кремнии". Разработана модель асинхронного нейроподобного кристалла, на котором собирается для начала реализовать модели глаза и уха, и уже получил первый патент на одно-транзисторную модель синапса. А на конференции ECAL был продемонстрирована первая программируемая микросхема (ПЛМ), способная к самосовершенствованию. В схему "зашит" генетический алгоритм, оптимизирующий программный код обработки внешних воздействий. Особняком стоит такая экзотическая область, как компьютерная вирусология. Исследователи, использующие методы A-life, подошли к этой проблеме, трактуя компьютерные вирусы как специфическую разновидность искусственной жизни, способную к мутациям, размножению, инфицированию среды обитания и самосовершенствованию. При такой трактовке становится реальностью давняя идея об универсальном антивирусе, который будет обнаруживать не конкретные виды вирусов (как большинство существующих программ) а проявления новых форм компьютерной жизни - изменение дисциплины обработки прерываний, нетипичное поведение известных программ, незнакомый "почерк" общения программ с файловой системой и т.п. Фирма IBM уже анонсировала первый коммерческий антивирус, построенный на подобных принципах. Что же касается таких областей, как моделирование катастроф, чрезвычайных ситуаций и военных конфликтов, то здесь история ситуационных центров, фактически использующих элементы A-life, насчитывает уже несколько десятилетий.


Примеры решений / Продукты :

Бизнесменам хорошо знакома фирма Flavors Technology, которая решает большое количество трудно формализуемых финансовых и управленческих задач, используя методы A-life и теории хаоса, реализованные на специализированной многопроцессорной системе. Менее известно, что фирма Thinking Machines, знаменитый разработчик суперкомпьютеров, также имеет собственные программные наработки по воплощению A-life для решения ряда оборонных задач.Еще один пример "из жизни". На складе небольшой фирмы, занимающейся отверточной сборкой компьютеров постоянно присутствует несколько разновидностей каждого компонента ПК - дисководов, корпусов, материнских плат и т.д. Цена собранного компьютера не равна сумме его компонент. Возникает элементарная оптимизационная задача - как из всего этого добра собрать компьютеры на максимальную сумму ? Даже при небольшом обороте в 100 тыс. долларов в месяц, получить оптимальное решение вручную почти невозможно. А средний по мощности GA-пакет (например, GeneHunter) справится с этой задачей за несколько минут, причем решение лишь одной этой задачи окупит его стоимость за неделю. Все вышесказанное справедливо не только для компьютеров, но и для повышения доходности от торговли мебелью, стройматериалами, а также массы других приложений.


Подробнее о технологии генетических алгоритмов :

К A-life принято относить компьютерные модели, обладающие рядом конкретных особенностей. Во-первых, центральная модель системы - будь то персонаж детской игры, самоходный робот или интеллектуальный агент Internet - обладает способностью адаптироваться к условиям внешнего мира, пополняя знания о нем путем взаимодействия с другими объектами и средой. Во-вторых, компоненты системы, развиваясь в процессе эволюции, способны передавать свои характерные черты по наследству. Соответственно, присутствует механизм порождения новых поколений - путем деления, скрещивания либо дублирования существующих объектов. В-третьих, окружающий мир достаточно жесток и сводит к минимуму шансы на выживание и появление потомства у слабых и плохо приспособленных особей. И, наконец, присутствует механизм порождения новых форм (аналог мутаций в реальном мире), обычно содержащий элемент случайности.С математической точки зрения генетические алгоритмы - это разновидность методов оптимизации, объединяющая черты вероятностных и детерминированных оптимизационных алгоритмов. Поиск оптимального решения с помощью GA начинается с представления параметров решения в виде вектора (целочисленного или битового) - "генетического кода" или "хромосомы". Далее определяется набор операций, позволяющих получать новые решения из совокупности существующих. Продолжая аналогию с генетическими механизмами реального мира, "дочернее" решение может порождаться одним или двумя "родителями", наследуя черты обоих вследствие операций скрещивания. Однако (и это пожалуй, самое важное), новые поколения копируют свойства предшественников неточно. Присутствует специальный механизм мутации, привносящий случайные искажения. Наконец, модель внешнего мира при реализации генетических алгоритмов, обычно - увы - отсутствует, что отличает GA от Artificial life в целом. Реакция внешнего мира заменяется заранее заданной целевой функцией, позволяющей сравнивать качество полученных решений.Далее - все просто. На основе одного-двух начальных решений порождается первое поколение решений. Для каждого вычисляется значение функции качества, после чего определенный процент наихудших решений уничтожается, а наилучших - скрещивается. Так появляется следующее поколение. Мутации периодически расширяют базу для селекции, не позволяя процессу вырождаться. Через несколько поколений значение функции качества перестает улучшаться. Это означает, что выведено семейство решений, наилучшим образом удовлетворяющих заданным критериям. Остается только "расшифровать" генетический код итоговых решений и перевести их в привычный для разработчика вид.