Разум, машины и математика. Искусственный интеллект и его задачи
Шрифт:
Мы рассказали о некоторых наиболее популярных методах, применяемых на каждом из этапов эволюционных алгоритмов. Следует понимать, что существует и множество других методов.
* * *
ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ ЛАМАРКА
Двойственность теорий Дарвина и теорий Ламарка проявляется и в эволюционных алгоритмах.
Отметим, что обе теории оказались крайне эффективными для решения задач оптимизации. Чаще всего используются дарвиновские эволюционные алгоритмы, описанные в этой главе, а алгоритмы, созданные согласно теориям Ламарка, содержат дополнительный этап между оценкой и отбором. Этот этап заключается в краткой локальной оптимизации, имитирующей обучение или адаптацию особи к окружающей среде перед достижением репродуктивного возраста.
Локальная оптимизация,
Если же мутация привела к снижению приспособленности особи, она отвергается, после чего цикл «мутация-оценка» повторяется начиная с состояния, предшествовавшего мутации. Первые эволюционные алгоритмы, построенные согласно теории Ламарка, получили название эволюционных стратегий. Как мы уже упоминали, они использовались немецкими инженерами во время Второй мировой войны для оптимизации сопл двигателей первых реактивных самолетов.
Как вы уже увидели, используя методы оптимизации, основанные на природных процессах, ученые добились огромных успехов в области искусственного интеллекта. Не так давно эволюционные вычисления при изготовлении лекарств позволили добиться заметных успехов. Напомним, что при создании медикаментов целью исследователей является подбор соединения, для которого энергия связи с определенным белком будет отрицательной и минимально возможной. Искомое соединение должно сформировать внутри нашего организма неразрывную связь с белком-мишенью, чтобы их неодолимо тянуло друг к другу, как сладкоежек тянет к карамели.
Рассмотрим, как действует эволюционный алгоритм при оптимизации молекул во время разработки лекарств. Сначала требуется инициализировать популяцию молекул. На этом этапе молекулы обычно формируются случайным образом. Для простоты будем рассматривать поколения всего из трех молекул, хотя обычно их число в одном поколении достигает нескольких сотен.
Далее произведем оценку молекул, рассчитав энергию взаимодействия каждой из них с белком-мишенью. Для этого используются различные вычислительные методы. Один из них (мы не будем подробно описывать принцип его действия) называется молекулярным докингом — это трехмерное моделирование, в ходе которого оценивается, сможет ли молекула образовать связь при встрече с мишенью и какой будет энергия этой связи. Возникает любопытная ситуация: при использовании эволюционного алгоритма для поиска идеальной молекулы на одном из его этапов мы вновь применяем эволюционный алгоритм, чтобы оценить качество молекулы по сравнению с остальными. Результатом докинга являются оцененные молекулы.
Следующий этап — отбор, который можно организовать, например, путем турнирной селекции. В ходе турнирной селекции случайным образом формируются пары молекул, после чего производится оценка их энергии взаимодействия и принимается решение о том, какие молекулы останутся, а какие — отсеются. Напомним, что энергия взаимодействия должна быть отрицательной и принимать минимально возможное значение.
Следующий этап эволюционного алгоритма — размножение, в ходе которого на основе отобранных молекул создаются новые, сочетающие в себе свойства молекул предыдущего поколения. Так, путем скрещивания двух молекул, отобранных на предыдущем шаге, создаются две новые молекулы.
На следующей иллюстрации показано, как две молекулы делятся.
И, наконец, путем соединения частей этих молекул образуются две новые молекулы.
На этапе замещения особи первого поколения замещаются новыми, созданными на предыдущем этапе. Наиболее популярный и простой метод замещения — элитизм, при котором замещаются все молекулы предыдущего поколения за исключением одной, наиболее приспособленной. В нашем случае новое поколение будет состоять из двух молекул, полученных в результате скрещивания, и одной молекулы из предыдущего поколения с энергией взаимодействия, равной —8.
После замещения эволюционный цикл завершается и повторяется необходимое число раз. Иными словами, дальше производится оценка молекул второго поколения, затем среди них отбираются лучшие, и так далее, после чего формируется третье поколение молекул. Процесс повторяется, пока не будет достигнуто заранее определенное число поколений или популяция не сойдется, то есть 90 % особей не будут представлять собой одну и ту же молекулу.
Разумеется, мы приводим упрощенное описание процесса, а в действительности все обстоит намного сложнее. Но скажите, разве сам процесс не прекрасен?
Глава 3. Машинное обучение
Четверг, 6 мая 2010 года, 9:30 утра. Начинаются торги на американских фондовых биржах. Этот день ничем не отличался от остальных: утренняя сессия прошла без каких-либо аномалий. Но в 14:45 без явной причины некоторые самые важные рыночные котировки за несколько секунд обвалились. Даже с учетом высокой волатильности, характерной для финансовых рынков в период нестабильности, этот обвал был достаточно неожиданным: акции некоторых наиболее крупных и надежных компаний потеряли в цене более 60 %, а весь американский и, как следствие, мировой финансовый рынок обрушился за несколько минут. Индекс Доу-Джонса (один из наиболее популярных биржевых индексов) потерял 9,2 %, что стало крупнейшим падением в течение одного дня торгов за всю историю (этот день позже будет назван черным вторником). Позднее падение стабилизировалось, и индекс снизился «всего» на 3,2 %, но в результате за несколько секунд безвозвратно исчезли триллионы долларов.
Первые признаки обвала были обнаружены на Нью-Йоркской фондовой бирже.
Было предложено множество объяснений, но точная причина черного вторника до сих пор неизвестна. Согласно одной из гипотез, которую поддерживает большинство финансовых аналитиков, причиной обвала стала деятельность высокочастотных трейдеров (HFT — от англ. High Frequency Traders), однако рыночные регуляторы традиционно отвергали эту версию. Высокочастотные трейдеры — это автоматические интеллектуальные системы купли-продажи акций и финансовых инструментов, способные принимать решения в течение нескольких микросекунд. Сегодня системами высокочастотной торговли совершается 50 % всех международных финансовых операций.
Но как может информационная система, интеллектуальная или нет, принимать столь масштабные решения так быстро? Любой начинающий инвестор знает, что котировки ценных бумаг на финансовых рынках зависят от бесконечного множества социальных, экономических и политических факторов, начиная от последних заявлений финского министра занятости о регулировании труда в стране и заканчивая непредвиденным снижением спроса на сырье в связи с потеплением на юге Германии. Как может информационная система учитывать такой объем информации, чтобы принимать, казалось бы, интеллектуальные решения о покупке или продаже акций, причем всего за несколько секунд? Вот в чем вопрос.