Компьютерная генетика бьет человеческие рекорды

Сергей Бобровский

Частная исследовательская группа Genetic Programming Inc. (http://www.genetic-programming.com/) каждый год проводит конкурсы с призовым фондом 10 тыс. долл., посвященные эффективному практическому применению генетических алгоритмов. В 2004 г. золотой приз получили:

• Джейсон Лон, Грегори Хорнби (НАСА) и Дерек Линден (компания Linden Innovation Research) за проектирование антенны для космического телескопа НАСА Space Technology 5. Существующие методы проектирования и оптимизации конструкций антенн сложны, ограничены по возможностям и требуют значительных ресурсов для лабораторных испытаний. А эволюционная система нашла оптимальное сочетание между шириной оптического луча и полосой пропускания устройства, и один из ее вариантов сейчас тестируется в качестве кандидата наравне с решениями, подготовленными традиционными научными коллективами;
• Ли Спектор (Хэмпширский колледж) – за систему генерации программ для квантовых компьютеров. Область квантового программирования основана на вероятностных вычислениях и условных устройствах, разрушающихся после принятия или обработки данных. Один из первых квантовых прикладных алгоритмов был предложен в 1996 г. Ловом Гровером из лаборатории Bell – он реализовал на виртуальном квантовом компьютере быстрый поиск в неупорядоченной БД. А так называемый квантовый XOR-алгоритм Дойча – Джозсы, первые публикации о котором появились только в 2004 г., позволяет решать уже целый класс задач реального мира, например, управлять пропускной способностью оптических каналов связи. В то же время эффективность этих алгоритмов сильно зависит от качества описания анализируемой ситуации и корректно выбранных для ее оценки свойств. А система Спектора автоматически генерирует программы, фактически независимые от начальных условий и при этом функционально эквивалентные кодам Гровера и Дойча – Джозсы, позволяя, в частности, выполнять поиск за одно обращение к БД (или так называемому "оракулу", интеллектуальному советнику в варианте Дойча – Джозсы).

Серебряными лауреатами стали:

• Алекс Фунунага (Калифорнийский университет), предложивший прикладное решение фундаментальной проблемы высокоразмерной конъюнктивной нормальной формы (КНФ) так называемого NP-полного класса задач, которая требует доказательства того, что заданная булевая функция может принимать значение "1" ("истина"). Эта проблема актуальна, например, в криптографии, когда важно знать, существует ли в принципе для той или иной технологии разрешающий алгоритм заданной сложности. Метод Фунунаги позволяет создавать эффективные эвристики и поисковые алгоритмы для решения конкретных КНФ-задач. Все они в процессе тестирования проигрывались на различных примерах, и чем сложнее была задача, тем заметнее (на порядок) был выигрыш генетических алгоритмов, а классические численные системы нередко оказывались просто бессильны;
• Ход Липсон (Корнельский университет), продемонстрировавший систему эволюционного моделирования механизмов, которые были спроектированы в XIX веке известными европейскими механиками и создателями автомобилей и велосипедов. Компьютер предложил схожие или лучшие по эффективности варианты устройств;
• Бийэн Хосравиани, Рэймонд Левит и Джон Коза (Стэнфордский университет) – они представили свою систему генетических алгоритмов на традиционный университетский конкурс многомерной оптимизации проекта создания биотехнологического завода. В конкурсе принимают участие группы студентов и специалистов-практиков, распределяя множество проектных задач, и программа предложила вариант, который оказался на 2% короче лучшего человеческого решения за последние 8 лет.

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

Кроме того, организаторы отметили поощрительными призами эволюционные системы классификации сгенерированных компьютером изображений и формирования аппаратных графических фильтров, решения для динамического управления пропускной способностью сетей, а также оригинальное адаптивное решение известной в математике оптимизационной проблемы Эль-Фарола ("когда пойти в бар, чтобы там было не слишком много народа, но и не оказалось бы слишком скучно").

Очередная конференция по генетическим алгоритмам, организуемая фирмой Genetic Programming, пройдет в Вашингтоне в конце июня.

Статья опубликована в PC Week/RE №8 от 15.03.2005 г., стр. 48.