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