Искусственный интелект. Генетические алгоритмы

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

     Примеры применения генетических алгоритмов.

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

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

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

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

     В 1994 году Эндрю Кин из университета Саутгемптона использовал генетический алгоритм в дизайне космических кораблей. За основу была взята модель опоры космической станции, спроектированной в NASA из которой после смены 15 поколений, включавших 4.500 вариантов дизайна, получилась модель, превосходящая по тестам тот вариант, что разработали люди.

     Аналогичный генетический алгоритм был использован NASA при разработке антенны для  спутника.

     Джон  Коза из Стэнфорда разработал технологию генетического программирования, в  которой результатом эволюции становятся не отдельные числовые параметры "особей", а целые имитационные программы, которые являются виртуальными аналогами  реальных устройств. Эта технология позволила компании Genetic Programming повторить 15 человеческих изобретений, 6 из которых были запатентованы после 2000 года, то есть представляют собой самые передовые достижения, а один из контроллеров, "выведенных" в GP, даже превосходит аналогичную человеческую разработку.

     Сейчас  плоды электронной эволюции можно  найти в самых разных сферах: от двигателя самолета Boeing 777 до новых антибиотиков.

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

     Основные  задачи применения генетических алгоритмов 2, для решения которых 10 лет назад были применены генетические алгоритмы, чтобы показать, что в настоящее время, на гораздо более мощной персональной вычислительной технике, можно с помощью генетических и эволюционных алгоритмов находить околооптимальные решения чуть ли не 99% задач принятия решения.

     Первый  пример - создание команды роботов  для разминирования территории. Генетическим алгоритмом оптимизировалась многослойная нейронная сеть, управляющая движением робота и выдающая, кроме этого, сигнал другим роботам команды. Т.о, кроме параметрической оптимизации нейромодели выполнялось еще и неявное "создание" некоторого языка коммуникации между роботами. Результаты показали преимущество команды однотипных коммуницирующих между собой роботов перед командой не обменивающихся сигналами роботов и перед командой случайно двигающихся роботов.

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

     Оба примера требовали довольно долгого  вычисления значения фитнес-функции для особи. Для роботов-минеров надо было оценить качество разминирования, достигнутое после моделирования некоторого времени работы и передвижений команды однотипных роботов (а не одного робота - целью ведь было повышение качества от возникновения коммуникаций в команде), для нейроигрока в шашки нужно было сыграть партию, причем каждый делаемый ход выбирался после перебора всех возможных для данной позиции двух полных ходов (двух своих ходов и двух ходов противника), и качество этих возможных ходов как раз и прогнозировалось нейронной сетью. Т.е. время, затрачиваемое на вычисление значения фитнес-функции, было сравнимо с длительностью эпохи обычного обучения нейросети для довольно объемной задачи.

     В настоящее время скорость работы современных процессоров даже персональных компьютеров выросла как минимум  в 10-20 раз по сравнению с концом 1990х годов, а многоядерность процессоров позволяет эффективно распараллеливать вычисления внутри поколения генетического алгоритма. Более того, в 1999г появилась статья с рецептом аппроксимации вычислений функции exp(), нужной при вычислении значения гиперболического тангенса (наиболее часто используемой нелинейной функции нейронов для многослойных нейронных сетей) - аппроксимация ускоряет вычисление гиперболического тангенса в 4.4 раза и время срабатывания (именно срабатывания - генетическому алгоритму нужно именно оно, а не результат работы алгоритма обратного распространения) нейронной сети - в 1.5-2 и более раза в зависимости от размера нейросети (экспериментальные результаты приведены в заметке про ускорение вычислений гиперболического тангенса). Т.е. не только компьютеры стали работать быстрее, но и некоторые оптимизируемые нейросетевые модели (например, многослойные персептроны) можно существенно ускорить.

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

     Сравнение с другими моделями достоинства и  недостатки.

Генетический  алгоритм - новейший, но не единственно  возможный способ решения задач  оптимизации. С давних пор известны два основных пути решения таких  задач - переборный и локально-градиентный. У этих методов свои достоинства  и недостатки, и в каждом конкретном случае следует подумать, какой из них выбрать.

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

Каждый  вариант решения (для 30 городов) - это  числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в этой задаче 30 параметров, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода.  

Переборный метод наиболее прост  по своей сути и тривиален в  программировании. Для поиска оптимального решения (точки максимума целевой  функции) требуется последовательно  вычислить значения целевой функции  во всех возможных точках, запоминая  максимальное из них. Недостатком этого метода является большая вычислительная стоимость. В частности, в задаче коммивояжера потребуется просчитать длины более 10³⁰ вариантов путей, что совершенно нереально. Однако, если перебор всех вариантов за разумное время возможен, то можно быть абсолютно уверенным в том, что найденное решение действительно оптимально.  

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

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

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

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

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

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

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

    Перспективы развития генетического  алгоритма.

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

     Заключение

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

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