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

Sokolov N.

graduate student

2 course of study of the Department "Power and electrical engineering"

Cherepovets State University

Russia, Cherepovets

MODERN OPPORTUNITIES AND PROSPECTS OF APPLICATION GENETIC AND EVOLUTIONAL OPTIMIZATION ALGORITHMS

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

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

Нахождение глобального минимума функции Розенброка является довольно сложной задачей, и многие алгоритмы оптимизации не справляются с ней (например, метод Хука-Дживса находит локальный минимум и останавливается на этом). Но если условие задачи не требует точного нахождения глобального минимума, если достаточно найти удовлетворяющее заданной погрешности решение – ГА будет являться эффективным механизмом поиска, конкурируя с остальными методами, которые не применяют знания о пространстве поиска[1].

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

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

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

Пример третий - применение ГА для решения задач оптимизации системы организации и управления пассажирскими перевозками. Другими словами, с помощью ГА можно рассчитать оптимальный график для движения автобусов по городу, с учетом многих факторов: количество подвижного состава на линии не должно превышать общего количества автобусов в парке; количество мест в автобусах на линии не должно превышать номинального их количества для автобусов, имеющихся в парке; время пребывания автобуса в наряде не должно быть меньше 8 часов и больше 12 часов; обязательное прохождение автобусом, начиная с начальной остановки через все последующие остановки маршрута. [6]

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

В наше время производительность современных процессоров компьютеров увеличилась примерно в 15-25 раз по сравнению с концом 1990-х годов, а многоядерные процессоры позволяют более эффективно распределять вычисления внутри поколений ГА. Более того, в 1999 году, появилась статья с решением аппроксимации вычисления функции exp( ), необходимой для вычисления значения гиперболического тангенса (наиболее используемой сигмоидной нелинейной функции нейронов для многослойных нейронных сетей) - аппроксимация значительно увеличивает скорость вычисления гиперболического тангенса (примерно в 4,4 раза), а так же время срабатывания (ГА нужно именно время срабатывания, а не результат работы алгоритма обратного распространения) нейронной сети - в 1,5-2 и более раза в зависимости от размеров нейросети). Таким образом, стали работать быстрее не только компьютеры, но и большинство используемых нейросетевых моделей (например, различные варианты многослойных персептронов) можно заметно ускорить.

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