Разум, машины и математика. Искусственный интеллект и его задачи
Шрифт:
Различия между эволюционными алгоритмами определяются тем, как именно реализован каждый из этих основных этапов.
* * *
ДАРВИН И ЛАМАРК: ДВА РАЗНЫХ ВЗГЛЯДА НА ЭВОЛЮЦИЮ
Жан Батист Пьер Антуан де Моне Ламарк (1744–1829) — французский натуралист, который совершил революцию в биологии, предложив классификацию живых организмов в зависимости от их сложности, а также четко разделив органический и неорганический мир. Еще одним его вкладом в науку стало создание первой биологической теории эволюции, изложенной в книге «Философия зоологии», которая была опубликована в 1809 году, за 50 лет до того, как свою теорию эволюции предложил Дарвин.
Теория Ламарка, в отличие от дарвиновской, основывается на наследовании приобретенных признаков,
Хотя гипотезы Ламарка были отвергнуты в пользу теории Дарвина, не так давно их правильность была подтверждена для некоторых частных случаев. К примеру, известно, что мать, организм которой после пережитой болезни выработал особые антитела, может передать их детям, которые получат иммунитет к этой болезни. Таким образом, здесь мы имеем дело с наследованием признаков, приобретенных при жизни в результате адаптации к окружающей среде.
Карикатура на Ламарка, изображенного в виде жирафа.
Инициализация популяции — отдельный этап, достаточно независимый от используемого эволюционного алгоритма. Инициализация определяется скорее особенностями рассматриваемой задачи — присутствием в ней ограничений, которые следует учитывать, или, напротив, полным отсутствием представления о том, как должно выглядеть «хорошее» решение, в результате чего инициализация выполняется абсолютно случайным образом. Существуют задачи, в которых случайная инициализация предпочтительнее, однако особи первого поколения должны обладать определенными различиями, чтобы охватить все возможные решения.
На этом этапе особенно важно представление знаний об особи, так как оно в значительной степени определит оставшуюся часть эволюционного алгоритма.
Чаще всего особи представляются в виде хромосом. Это новое понятие заимствовано у природы: хромосома представляет собой последовательность генов, а каждый ген — число, обозначающее часть решения.
Рассмотрим в качестве примера алгоритм, цель которого — увеличение емкости картонной коробки при наименьшем расходе картона на ее изготовление. Если мы используем эволюционный алгоритм, то хромосомы, посредством которых мы представим решение, будут иметь три гена: длину, ширину и высоту. При инициализации будет создана популяция коробок произвольных размеров, представленных в виде троек чисел, заключенных в допустимых интервалах. В ходе работы алгоритма популяции коробок будут эволюционировать до тех пор, пока не будет найдена оптимальная коробка в соответствии с установленными критериями.
Следующий этап после инициализации — оценка. Обычно считается, что это важнейшая часть эволюционного алгоритма, так как именно она определяет задачу, которую требуется решить. На первом шаге оценки воссоздается решение: информация из хромосомы (генотипа) каждой особи используется для моделирования решения (фенотипа), представленного особью. Целью оценки может быть как простое вычисление объема картонной коробки по известным размерам, как в нашем примере, так и чрезвычайно сложные и дорогостоящие расчеты, к примеру моделирование жесткости конструкции при проектировании моста.
После воссоздания фенотипа необходимо оценить полученное решение. Каждой особи присваивается свое значение приспособленности, которое на последующих этапах эволюционного алгоритма поможет отличить хорошие решения от плохих.
Оценка фенотипов может быть сложной, дорогостоящей и даже зашумленной.
Иными словами, при решении некоторых сложных задач приспособленность одного и того же фенотипа при разных оценках будет различаться. Шум, который также можно назвать ошибкой, неизменно присутствует в задачах, в которых оценка приспособленности используется для численного моделирования. К примеру, при моделировании сопротивления усталости металлов, из которых изготавливаются детали двигателей внутреннего сгорания, решение математических уравнений, описывающих усталость металла, оказывается столь дорогостоящим, что моделирование более выгодно. При этом вполне возможно, что результаты повторного моделирования для каждой детали будут отличаться.
Использование генетических алгоритмов для проектирования деталей двигателей внутреннего сгорания, осуществленное компанией Honda в 2004 году, показало: процесс оценки отличался высоким уровнем шума и неточностью, а также был весьма длительным — расчет приспособленности для каждой особи в популяции занимал восемь часов.
* * *
УПИТАННЫЕ ПТИЦЫ С ОСТРОВА МАВРИКИЙ И ДАВЛЕНИЕ ОТБОРА
Когда исследователи в XVII веке впервые прибыли на остров Маврикий, они обнаружили неожиданный дар небес — упитанных птиц с вкусным мясом, которых стали называть додо. Крылья этих птиц были слишком маленькими, а лапы — слишком короткими, поэтому они не могли ни улететь, ни убежать от охотников. Исследователи безжалостно охотились на додо, а кошки, собаки, крысы и другие животные, завезенные человеком на остров, разоряли гнезда птиц и питались их яйцами.
Додо полностью вымерли менее чем за сто лет, и сегодня эти милые и безобидные птицы известны нам только по рисункам и гравюрам. Додо никогда не испытывали необходимости эволюционировать, а когда они столкнулись с давлением отбора, птицам попросту не хватило времени на то, чтобы справиться с ним. Давление отбора — движущая сила эволюции. Без него живые существа не имеют достаточно стимулов для того, чтобы приспособиться к среде, они не испытывают необходимости развивать оптимальное поведение или другие признаки. В разные годы естествоиспытатели документально описали различные виды, которые, очевидно, находились в похожей ситуации: они обитали в среде, изобиловавшей пропитанием, где отсутствовали хищники, а межвидовая конкуренция была слабой.
Все эти факторы препятствовали появлению признаков, которые были присущи похожим видам, обитавшим в более конкурентных средах.
В отсутствие хищников и при избытке пропитания в изолированной экосистеме острова додо не нужны были сильные крылья и мощные лапы. Кстати, в дословном переводе с португальского «додо» означает «глупый». Кто знает, возможно, додо стали «глупыми» именно из-за того, что отсутствовало давление отбора?
Додо на гравюре XVII века.
Следующий этап эволюционного алгоритма, выполняемый после оценки особей текущего поколения, — это отбор. Его цель — выделить лучших особей, которые оставят потомство. Процесс отбора лучших особей является основой естественной эволюции. Интенсивность этого процесса называется давлением отбора. Давление отбора тем больше, чем меньше доля особей, переходящих в следующее поколение.
Однако можно доказать, что если мы применим столь простую стратегию, как прямой отбор лучших особей, то давление отбора будет слишком велико. При значительном давлении отбора эволюционные алгоритмы обычно работают не слишком хорошо, так как завершают работу на локальных, а не глобальных оптимумах.
Главное преимущество эволюционных алгоритмов — возможность получить хорошие решения на больших областях поиска, или, говоря математическим языком, возможность найти оптимумы функций, как правило, многомерных и имеющих несколько локальных или глобальных максимумов. Если давление отбора при эволюционной оптимизации слишком велико, то есть если мы хотим найти решение слишком быстро, для чего выберем лучших особей и ограничимся поверхностным рассмотрением, то алгоритм завершит работу слишком рано, а его результатами будут локальные, а не глобальные оптимумы.
Этап отбора идеально подходит для моделирования давления отбора в эволюционных алгоритмах. В пределе, когда давление отбора будет наибольшим, производится единичный отбор — иными словами, из текущего поколения выбирается только одна особь, на основе которой образуется следующее поколение. Другим предельным случаем будет полностью случайный отбор, при котором приспособленность особей не учитывается. Логично, что следует выбрать некую промежуточную стратегию, при которой производится отбор лучших особей для размножения и вместе с тем присутствует некоторая степень случайности, позволяющая рассмотреть альтернативные варианты. При такой стратегии с определенной вероятностью может быть выбрана любая, даже самая неприспособленная особь. Сегодня применяются три стратегии отбора, обладающие этими свойствами: рулетка, ранговая селекция и турнирная селекция.
Метод селекции, основанный на принципе колеса рулетки, достаточно прост. Он заключается в том, что каждая особь может быть выбрана с вероятностью, пропорциональной ее приспособленности по отношению к приспособленности остальных особей. Следовательно, если нужно отобрать 10 особей, колесо рулетки потребуется вращать 10 раз.
В примере на рисунке представлено восемь особей и значения их функции приспособленности в процентах от целого. Как вы можете догадаться, при каждом вращении рулетки вероятность выбора определенной особи будет пропорциональной отношению ее значения функции приспособленности к целому. Метод рулетки не исключает возможность выбора менее приспособленных особей — они всего лишь будут выбираться с меньшей вероятностью. Если мы будем вращать колесо рулетки 10 раз, то несколько раз обязательно выберем приспособленных особей, но также вероятно, что несколько раз выбранные особи будут не самыми конкурентоспособными. Именно возможность выбора неконкурентоспособных особей делает генетические алгоритмы столь мощными: это позволяет следовать несколькими путями одновременно, открывать другие варианты, выявлять множество различных максимумов, а в долгосрочной перспективе — находить хорошее локальное решение, а в лучшем случае — глобальный максимум.