Игнаси Белда - Том 33. Разум, машины и математика. Искусственный интеллект и его задачи

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

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

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

* * *

УПИТАННЫЕ ПТИЦЫ С ОСТРОВА МАВРИКИЙ И ДАВЛЕНИЕ ОТБОРА

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

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

Все эти факторы препятствовали появлению признаков, которые были присущи похожим видам, обитавшим в более конкурентных средах.

В отсутствие хищников и при избытке пропитания в изолированной экосистеме острова додо не нужны были сильные крылья и мощные лапы. Кстати, в дословном переводе с португальского «додо» означает «глупый». Кто знает, возможно, додо стали «глупыми» именно из-за того, что отсутствовало давление отбора?

Додо на гравюре XVII века.

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

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

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

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