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

выражают знания о реальном мире. 
В этом контексте, вычисления со словами есть раздел нечеткой логики. 
В представлении Заде, 
вычисления со словами
должны превратиться 
в 
важнейшее научное направление
, обеспечивающее эффективную 
работу с всеобъемлющей неточностью и неопределенностью реального 
мира. В этой перспективе исходной моделью для вычислений со 
словами, нечеткой логики и мягких вычислений является человеческий 
разум.
Понимание, конструирование и развитие информационных/ 
интеллектуальных систем представляет собой серьезный вызов всем 
тем, кто вовлечен в разработку и приложения нечеткой логики и мягких 
вычислений.
1.6. Эволюционные вычисления
Генетические алгоритмы являются частью более общей группы 
методов, называемой эволюционными вычислениями, которые 
объединяют различные варианты использования эволюционных 
принципов для достижения поставленной цели. 
Также в ней выделяют следующие направления: 

Эволюционные стратегии 
o
Метод оптимизации, основанный на идеях 
адаптации и эволюции. Степень мутации в данном 
случае меняется со временем – это приводит к, так 
называемой, самоадаптации.

Генетическое программирование 
o
Применение эволюционного подхода к популяции 
программ. 

Эволюционное программирование 
o
Было впервые предложено Л.Дж. Фогелем в 1960 
году для моделирования эволюции как процесса 
обучения с целью создания искусственного 
интеллекта. Он использовал конечные автоматы, 
предсказывающие 
символы 
в 
цифровых 
последовательностях, которые, эволюционируя, 
становились более приспособленными к решению 

---

А.Е. Кононюк Дискретно-непрерывная математика 
43 
поставленной задачи.
 
Генетические алгоритмы применяются для решения следующих задач: 

Оптимизация функций

Разнообразные задачи на графах (задача коммивояжера, 
раскраска, нахождение паросочетаний)

Настройка и обучение искусственной нейронной сети

Задачи компоновки

Составление расписаний

Игровые стратегии

Аппроксимация функций

Искусственная жизнь

Биоинформатика
 
Насколько осмысленной является идея использования законов 
эволюции не при имитации самой эволюции, а при решении 
интеллектуальных задач? На первый взгляд, идея может показаться 
интересной, но немного сомнительной: не происходит же у нас в голове 
эволюция, пусть даже виртуальная. Однако эта идея была высказана 
достаточно давно сразу несколькими авторами и оказалась 
относительно успешной. Сейчас область исследований, опирающихся 
на сходные идеи, называется эволюционными вычислениями. Наиболее 
ранним вкладом в нее в 1960-х годах стали эволюционные стратегии, 
предложенные Инго Рехенбергом с коллегами, и эволюционное 
программирование, предложенное Лоуренсом Фогелем, а также 
генетические алгоритмы Джона Генри Холланда (которые стали 
известны в 1970-х). Позднее возникла концепция генетического 
программирования. Все эти разновидности эволюционных вычислений 
являются альтернативой классическим методам поиска и оптимизации, 
включая эвристическое программирование. 
Существующие методы эволюционных вычислений берут за основу 
идеи Дарвина. Одна из этих идей гласит: выживает наиболее 
приспособленный. В действительности, это тавтология, поскольку 
более приспособленный — это, по определению, тот, кто имеет больше 
шансов выжить. Эту тавтологичность подчеркивают и сами 
эволюционисты, чтобы доказать неизбежность эволюции, несмотря на 
отсутствие у природы каких-либо специальных целей. Не случайно идея 

---

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

---

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