Эволюционные вычисления

Эволюционные вычисления

2-е издание, исправленное

Скобцов Ю.А.
Cперанский Д.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Эволюционные вычисления/ Ю.А. Скобцов, Д.В. Cперанский - М.: Национальный Открытый
Университет “ИНТУИТ”, 2016

Рассмотрены основы нового направления в теории искусственного интеллекта, включающего
эволюционные вычисления и роевые алгоритмы.
В курсе изложены основные теоретические и методологические материалы по эволюционным
вычислениям, которые являются самостоятельным направлением в теории интеллектуальных систем.
Последовательно вводятся базисные понятия классических генетических алгоритмов (ГА), теория
схем и решения задач численной и комбинаторной оптимизации с помощью генетических
алгоритмов. Рассмотрены многочисленные обобщения и модификации ГА. К ним относятся
параллельные ГА, реализованные по модели «рабочий-хозяин» и «модель островов». Представлены
различные варианты многокритериальных ГА на основе концепции Парето. Описаны вероятностные
ГА, где популяция представляется вектором вероятностей. Изложены основы генетического
программирования на основе различных форм кодирования потенциальных решений: древовидных,
линейных и графоподобных структур. Представлены основы машинного обучения на базе
Мичиганского и Питсбургского подходов. Описаны эволюционные стратегии, где основным
генетическим оператором является мутация, и эволюционное программирование, которое в качестве
потенциального решения использует модель конечного автомата.. Изложены также роевые и
муравьиные алгоритмы.

(c) ООО “ИНТУИТ.РУ”, 2014-2016
(c) Скобцов Ю.А., Cперанский Д.В., 2014-2016

3

Введение.Основы генетических алгоритмов

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

Предисловие

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

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

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

4

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

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

Введение

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

Высокая согласованность и эффективность работы элементов биологических систем
приводила целый ряд исследователей к естественной мысли о возможности
использования принципов биологической эволюции для оптимизации важных для
приложений систем, природа которых отлична от биологической. Так, в 1966 году
Фогель Л., Оуенс С. и Уолш М. в [1] подобную идею использовали для построения
схемы эволюции логических автоматов, решающих задачи прогноза. В 1975 году была
опубликована основополагающая работа Дж. Холланда [2], в которой был предложен
генетический алгоритм, развивающий ту же идею. Д.Гольдберг, ученик Дж. Холланда,
в работе [3] , выполненной в Мичиганском университете, успешно развил и расширил
области его применения.

В 60-х годах прошлого века в Германии Рохенберг И., Швефель Г.-П., и др. [4] начали
разработку так назывемой эволюционной стратегии. Перечисленные работы
послужили толчком и основой развития прикладного направления, которое можно
назвать эволюционными алгоритмами. К их числу, помимо упомянутых генетических
алгоритмов и эволюционных стратегий, относятся также эволюционное
программирование, ориентированное на оптимизацию функций без использования
рекомбинаций, и генетическое программирование, использующее эволюционные идеи
для оптимизации компьютерных программ. Основополагающая работа по
эволюционному программированию принадлежит Дж. Коза [5] из Массачусетского
технологического института.

Отметим, что аналогичные исследования успешно проводились отечественными
учеными еще в Советском Союзе. Так, значительный вклад в развитие указанных
направлений внесли Ивахненко А.Г. [6], Цыпкин Я.З. [7], Расстригин Л.А. [8] и др. В

5

настоящее время исследования по ЭВ активно ведутся Букатовой [9,10], Курейчиком
В.М. [11,12,13], их сотрудниками и учениками, а также многими другими
исследователями.

Учебное пособие состоит из пяти частей.

В первой части “Основы генетических алгоритмов” (разделы пособия 1-5) изложены
идейная сторона простых генетических алгоритмов, их математические основы,
подробно описаны примеры построения генетических алгоритмов для решения
конкретных задач комбинаторной оптимзации и, наконец, представлены современные
модификации и обобщения этих алгоритмов.

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

В третьей части “Вероятностные генетические алгоритмы”(раздел 8) приведен другой
– вероятностный подход в эволюционных вычислениях, где популяция представляется
вектором вероятностей.

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

В пятой части “Эволюционное программирование” (раздел 10) содержится описание
основанного Фогелем Л.Дж. гибкого подхода в эволюционных вычислениях. В нем
форма представления потенциального решения и генетические операторы
адаптируются к решаемой проблемы в достаточно широких пределах. В частности, в
качестве особи в процессе эволюции Фогелем используются конечные автоматы и
целью эволюции является способность решения задач прогнозирования.

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

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

1. Введение в генетические алгоритмы

6

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

1.1. Простой генетический алгоритм

Основы теории генетических алгоритмов сформулированы Дж. Г.Холландом в
основополагающей работе [2] и в дальнейшем были развиты рядом других
исследователей. Наиболее известной и часто цитируемой в настоящее время является
монография Д.Голдберга [3], где систематически изложены основные результаты и
области практического применения ГА.

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

1. Первый принцип основан на концепции выживания сильнейших и естественного

отбора по Дарвину, который был сформулирован им в 1859 году в книге
“Происхождение видов путем естественного отбора”. Согласно Дарвину особи,
которые лучше способны решать задачи в своей среде, чаще выживают и чаще
размножаются (репродуцируют). В генетических алгоритмах каждая особь
представляет собой решение некоторой проблемы. По аналогии с этим принципом
особи с лучшими значениями целевой (фитнесс) функции имеют большие шансы
выжить и репродуцировать. Формализацию этого принципа, как мы увидим далее,
реализует оператор репродукции.

2. Второй принцип обусловлен тем фактом, что хромосома потомка состоит из

частей, полученных из хромосом родителей. Этот принцип был открыт в 1865
году Г.Менделем. Его формализация дает основу для оператора скрещивания
(кроссинговера).

3. Третий принцип основан на концепции мутации, открытой в 1900 году де Вре.

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

7

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

Эволюцию искусственной популяции – поиск множества решений некоторой
проблемы, формально можно описать в виде алгоритма, который представлен на
рис.1.1.

ГА получает множество параметров оптимизационной проблемы и кодирует их
последовательностями конечной длины в некотором конечном алфавите (в простейшем
случае в двоичном алфавите “0” и “1”).

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

1. оператора репродукции (ОР);
2. оператора скрещивания (кроссинговера, ОК);
3. оператора мутации (ОМ).

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

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

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

8

Рис. 1.1.  Простой генетический алгоритм

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

Упомянутые генетические операторы являются математической формализацией
приведенных выше трех основополагающих принципов Ч.Дарвина, Г.Менделя и де Вре
естественной эволюции. Каждый из функциональных блоков ГА на рис. 1.1. может
быть реализован различными способами. Но сначала на простом примере мы
рассмотрим основные моменты классического ГА.

1.2. Генетические операторы

Рассматриваемый ниже пример заимствован из популярной монографии Голдберга [3]
и состоит в поиске целочисленного значения (для простоты)  на отрезке от [0,31], при
котором функции 
 принимает максимальное значение.

9

Рис. 1.2.  Пример функции

Начальный этап работы ГА для данного примера приведен в верхней таблице
(репродукция) рис.1.3 Здесь особи начальной популяции (двоичные коды значений
переменных - столбец 2) сгенерированы случайным образом. Двоичный код значения
х называется хромосомой (она представляет генотип). Популяция образует множество
потенциальных решений данной проблемы. В третьем столбце представлены их
десятичные значения (фенотип). Далее на этом примере проиллюстрируем работу трех
основных генетических операторов.

1.2.1. Репродукция

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

Очевидно, оператор репродукции (ОР) является искусственной версией естественной
селекции – выживания сильнейших по Ч. Дарвину. Этот оператор представляется в
алгоритмической форме различными способами (подробнее различные варианты ОР
будут рассмотрены далее). Самый простой (и популярный) метод реализации ОР –
построение колеса рулетки, в которой каждая хромосома имеет сектор,
пропорциональный по площади значению ее целевой функции. Для нашего примера
“колесо рулетки” имеет вид, представленный на рис.1.4.

Для селекции хромосом используется случайный поиск на основе колеса рулетки. При
этом колесо рулетки вращается и после останова ее указатель определяет хромосому
для селекции в промежуточную популяцию (родительский пул).

10