Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

управления является порождение управляющих конечных 
автоматов (как классических, так и на основе теории нечетких 
множеств), где также достигнуты определенные успехи. 
Итак, 
эволюционные вычисления неплохо себя зарекомендовали в 
качестве методов поиска как при решении задач классического ИИ 
(т. е. при решении корректно поставленных NP-полных задач), так 
и при решении задач машинного обучения, хотя и не дали их 
полного решения. 
Почему же методы эволюционных вычислений оказываются достаточно 
успешными для решения проблем поиска? Эволюционные стратегии в 
применении к поиску экстремума функции от вещественных 
переменных очень похожи на стохастический градиентный спуск за 
исключением того, что в них происходит «скрещивание» решений. С 
генетическими алгоритмами ситуация чуть сложнее, так как в них 
небольшие мутации генов могут привести к значительному изменению 
«фенотипа» (примером может служить изменение старшего бита в 
двоичной записи числа). Но и в ГА основной особенностью является 
скрещивание, благодаря которому новые решения строятся как 
фрагменты имеющихся решений. Если задача разбивается на подзадачи 
и решению каждой подзадачи соответствует отдельный участок генома, 
то за счет скрещивания подзадачи могут решаться независимо. 
Действительно, если решение какой-то подзадачи улучшает общее 
решение независимо от других подзадач, то в генофонде популяции 
соответствующий участок генома быстро стабилизируется (его 
вариативность сильно уменьшится). Еще в большей степени этому 
будет способствовать использование не равномерного скрещивания, а 
кроссинговера, при котором потомкам передаются длинные фрагменты 
генотипов родителей. Кроссинговер будет работать хорошо, только 
если решения отдельных подзадач локализованы в геноме. 
Итак, мы видим, что ГА дополнены одним, но очень мощным приемом, 

---

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

---

А.Е. Кононюк Дискретно-непрерывная математика 
56 
эволюционных вычислений оказываются вовсе не универсальными. В 
связи с этим, если мы рассмотрим эволюционные вычисления как 
методы поиска в пространстве решений, то становится понятным, 
почему с их помощью не так просто автоматически получить ИИ. По 
сути, эти методы сами будут составлять интеллектуальную систему, 
перед которой ставится задача поиска программы ИИ. Нет ли здесь 
противоречия? Не получается ли так, что нам уже нужно иметь ИИ, 
чтобы компьютер смог сам его придумать? Принципиального 
противоречия здесь нет: более «глупая» программа может вывести 
более «умную» посредством «грубой силы», т. е. используя очень 
интенсивный перебор. Конечно, чем глупее эволюционная программа, 
тем больше грубой силы ей придется приложить. Полным перебором 
задачу построения ИИ или даже игры в шахматы на практике не 
решить. Естественно, недостаточно и нескольких простых 
метаэвристик. Такой взгляд показывает наивность попыток с помощью 
простой искусственной эволюции вывести интеллектуальные 
программы. Но как это удалось сделать естественной эволюции?