Интелектуальные информационные системы

Введение

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

Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

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

Актуальность генетические алгоритмы способны "развивать" решения реальных задач, подражая законам  естественного отбора биологических  организмов. Генетические алгоритмы  могут использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере, поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Вполне реальный пример: израильская  компания Schema разработала программный продукт Channeling для оптимизации работы сотовой связи путем выбора оптимальной частоты, на которой будет вестись разговор. В основе этого программного продукта и используются генетические алгоритмы [2].

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

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

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

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

Далее генетические алгоритмы  будут рассмотрены более детально.

1 История появления  эволюционных алгоритмов

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

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

История эволюционных вычислений началась с разработки ряда различных  независимых моделей. Основными  из них были генетические алгоритмы  и классификационные системы  Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

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

Усилия, направленные на моделирование  эволюции по аналогии с природными системами, к настоящему времени  можно разбить на две большие  категории:

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

На практике мы не можем  разделять эти вещи так строго. Эти категории - просто два полюса, между которыми лежат различные  вычислительные системы. Ближе к  первому полюсу - эволюционные алгоритмы, такие как эволюционное программирование (Evolutionary Programming), генетические алгоритмы (Genetic Algorithms) и эволюционные стратегии (Evolution Strategies). Ближе ко второму полюсу – системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).

Исследования в области  нейронных сетей, позволяющих получить хорошие (хотя и приближенные) результаты при решении сложных задач  управления, часто финансирует военное  научное агентство DARPA. Пример - проект Smart Sensor Web, который предусматривает организацию распределенной сети разнообразных датчиков, синхронно работающих на поле боя. Каждый объект (стоимостью не более $300) в такой сети представляет собой источник данных - визуальных, электромагнитных, цифровых, инфракрасных, химических и т. п. Проект требует новых математических методов решения многомерных задач оптимизации. Ведутся работы по автоматическому распознаванию целей, анализу и предсказанию сбоев техники по отклонениям от типовых параметров ее работы (например, по звуку). Операция "Буря в пустыне" стала стимулом к развитию экспертных систем с продвинутым ИИ, применяемым в области снабжения. На разработках, связанных с технологиями машинного зрения, основано все высокоточное оружие В СМИ нередко можно прочитать о грядущих схватках самостоятельно действующих армий самоходных машин-роботов и беспилотных самолетов. Однако существует ряд нерешенных научных проблем, не позволяющих в ближайшие десятилетия превратить подобные прогнозы в реальность. Прежде всего это недостатки систем автоматического распознавания, не способных правильно анализировать видеоинформацию в масштабе реального времени. Не менее актуальны задачи разрешения коллизий в больших сообществах автономных устройств, абсолютно точного распознавания своих и чужих, выбора подлежащих уничтожению целей, алгоритмов поведения в незнакомой среде и т. п. Поэтому на практике военные пытаются достичь менее масштабных целей. Значительные усилия вкладываются в исследования по распознаванию речи, создаются экспертные и консультационные системы, призванные автоматизировать рутинные работы и снизить нагрузку на пилотов. Нейронные сети достаточно эффективно применяются для обработки сигналов сонаров и отличения подводных камней от мин. Генетические алгоритмы используются для эвристического поиска решения уравнений, определяющих работу военных устройств (систем ориентации, навигации), а также в задачах распознавания - для разделения искусственных и естественных объектов, распознавания типов военных машин, анализа изображения, получаемого от камеры с низким разрешением или инфракрасных датчиков.

2 Применение генетических  и эволюционных алгоритмов оптимизации

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