Автор: Васюк А.О.
Источник: Інформаційні управляючі системи та комп’ютерний моніторинг (ІУС КМ - 2012) - 2012 / Матерiали III мiжнародної науково-технiчної конференцiї студентiв, аспiрантiв та молодих вчених. — Донецьк, ДонНТУ — 2012, Том 2, с. 132-136.
Рассматриваются вопросы применения генетических и эволюционных алгоритмов в системах искусственного интеллекта. Подробно изучена история развития эволюционных вычислений.
Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе [1].
Целью является исследование генетических алгоритмов для последующего применения их в решениях задач систем искусственного интеллекта. Таким способом можно решить, например, задачу поиска маршрута для автономного объекта-робота.
Актуальность генетические алгоритмы способны "развивать" решения реальных задач, подражая законам естественного отбора биологических организмов. Генетические алгоритмы могут использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере, поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Вполне реальный пример: израильская компания Schema разработала программный продукт Channeling для оптимизации работы сотовой связи путем выбора оптимальной частоты, на которой будет вестись разговор. В основе этого программного продукта и используются генетические алгоритмы [2].
Далее генетические алгоритмы будут рассмотрены более детально.
Природа поражает своей сложностью и богатством всех своих проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Многое из того, что мы видим и наблюдаем, можно объяснить единой теорией: теорией эволюции через наследственность, изменчивость и отбор.
Чарльз Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью или, как он его называл, "спуск с модификацией". Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в природе. Неудивительно, что ученые, занимающиеся компьютерными исследованиями, обратились к теории эволюции в поисках новых решений.
История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.
Главная трудность с возможностью построения вычислительных систем, основанных на принципах естественного отбора и применением этих систем в прикладных задачах, состоит в том, что природные системы достаточно хаотичны, а все наши действия, фактически, носят четкую направленность. Мы используем компьютер как инструмент для решения определенных задач, которые мы сами и формулируем, и мы акцентируем внимание на максимально быстром выполнении при минимальных затратах. Природные системы не имеют никаких таких целей или ограничений, во всяком случае, нам они не очевидны. Выживание в природе не направлено к некоторой фиксированной цели, вместо этого эволюция совершает шаг вперед в любом доступном направлении.
Усилия, направленные на моделирование эволюции по аналогии с природными системами, к настоящему времени можно разбить на две большие категории:
На практике мы не можем разделять эти вещи так строго. Эти категории - просто два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как эволюционное программирование (Evolutionary Programming), генетические алгоритмы (Genetic Algorithms) и эволюционные стратегии (Evolution Strategies). Ближе ко второму полюсу – системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).
Генетические и эволюционные алгоритмы оптимизации являются алгоритмами случайно-направленного поиска и применяются в основном там, где сложно или невозможно сформулировать задачу в виде, пригодном для более быстрых алгоритмов локальной оптимизации (например, для градиентных алгоритмов, где возможно, вдобавок, "мгновенное" вычисление градиента представленной в виде нейронной сети функции с помощью алгоритма обратного распространения ошибки), либо если стоит задача оптимизации недифференцируемой функции или задача многоэкстремальной глобальной оптимизации. Рассотрим 2 задачи, для решения которых 10 лет назад были применены генетические алгоритмы, чтобы показать, что в настоящее время, на гораздо более мощной персональной вычислительной технике, можно с помощью генетических и эволюционных алгоритмов находить околооптимальные решения чуть ли не 99% задач принятия решения [3].
Первый пример - создание команды роботов для разминирования территории, описанный в статье [4]. Генетическим алгоритмом оптимизировалась многослойная нейронная сеть, управляющая движением робота и выдающая, кроме этого, сигнал другим роботам команды. То есть, кроме параметрической оптимизации нейромодели выполнялось еще и неявное "создание" некоторого языка коммуникации между роботами. Результаты показали преимущество команды однотипных коммуницирующих между собой роботов перед командой не обменивающихся сигналами роботов и перед командой случайно двигающихся роботов.
Второй пример - известное создание нейросетевого игрока в шашки, который достиг мастерского уровня [5-7]. Внутри поколения генетического алгоритма нейросети-особи играли сами с собой, и по итогам игр отбирались лучшие для следующего поколения.
Оба примера требовали довольно долгого вычисления значения фитнес-функции для особи. Для роботов-минеров надо было оценить качество разминирования, достигнутое после моделирования некоторого времени работы и передвижений команды однотипных роботов (а не одного робота - целью ведь было повышение качества от возникновения коммуникаций в команде), для нейроигрока в шашки нужно было сыграть партию, причем каждый делаемый ход выбирался после перебора всех возможных для данной позиции двух полных ходов (двух своих ходов и двух ходов противника), и качество этих возможных ходов как раз и прогнозировалось нейронной сетью. Т.е. время, затрачиваемое на вычисление значения фитнес-функции, было сравнимо с длительностью эпохи обычного обучения нейросети для довольно объемной задачи.
В настоящее время скорость работы современных процессоров даже персональных компьютеров выросла как минимум в 10-20 раз по сравнению с концом 1990х годов, а многоядерность процессоров позволяет эффективно распараллеливать вычисления внутри поколения генетического алгоритма.
Отсюда можно сделать вывод, что генетические алгоритмы сейчас можно использовать практически всюду, препятствий в виде неприемлемых вычислительных затрат не осталось. Главное - суметь правильно или нетривиально поставить задачу и запрограммировать быструю реализацию оптимизируемой модели . И такие программы работают на порядок быстрее других.
1.Генетический алгоритм. Материал из Википедии – свободной энциклопедии. Электронный ресурс. Режим доступа:
http://ru.wikipedia.org/wiki/Генетический_алгоритм
2. Популярно о генетических алгоритмах. Исаев Сергей. Электронный ресурс. Режим доступа:http://algolist.manual.ru/ai/ga/ga1.php
3. Применение генетических и эволюционных алгоритмов оптимизации. Нейронные сети и анализ даннях. Материал из сайта Виктора Царегородцева NeuroPro. Электронный ресурс. Режим доступа: http://www.neuropro.ru/memo314.shtml
4. Божич В.И., Кононенко Р.Н., Абияка А.А. Нейросетевое управление в мультиагентной системе с самоорганизующейся коммуникацией // Материалы Всеросс. конф. "Нейроинформатика-99", М.: МИФИ, 1999. Часть 3. - С.239-246.
5. Chellapilla K., Fogel D.B. Evolution, neural networks, games and intelligence / Proc. IEEE, 1999. Vol.87, No.9. - pp.1471-1496.
6. Chellapilla K., Fogel D.B. Evolving neural networks to play checkers without expert knowledge / IEEE Trans. Neural Networks, 1999. Vol.10, No.6. - pp.1382-1391.
7. Chellapilla K., Fogel D.B. Evolving an expert checkers playing program without using human expertise / IEEE Trans. Evolutionary Computation, 2001. Vol.5, No.4. - pp.422-428.