Параллельные вероятностные алгоритмы построения моделей

Каждому нужно резюме из одного предложения (OSR). Те из вас, кого регулярно посещают старшие вице-президенты, директора по исследованиям или очень важные клиенты, всегда держат наготове свой OSR. Если вы не пользовались OSR, ваш ответ должен быть точным и кратким, когда большой начальник задает вопрос: «Чем вы занимаетесь?» Толпы сотрудников выполняют одинаково ценные и разнообразные функции для вашей организации, и у высокопоставленного гостя нет ни времени, ни необходимого жаргона, чтобы оценить 20-минутную диссертацию о прогрессе, достигнутом вами за предыдущие 20 минут.

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

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

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

Один из методов, используемых для устранения узкого места, заключается в том, чтобы главный процессор генерировал одну большую популяцию и отправлял небольшие группы хромосом нескольким другим процессорам для оценки пригодности, которые впоследствии сообщали свои оценки мастеру. Этот метод решает проблему оценки, но создает проблему пропускной способности канала связи. Например, параллельный ГА с популяцией в 1 миллион 1000-битных хромосом должен передавать более 1 гигабита данных между своим главным и параллельным подчиненным процессорами для каждого поколения в процессе поиска, требующего, возможно, тысяч поколений, чтобы прийти к решению.

Фернандо Г. Лобо и его коллеги из Университета Алгарве в Португалии продемонстрировали изящное решение проблемы пропускной способности в статье, представленной на конференции по генетическим и эволюционным вычислениям (GECCO-2004), состоявшейся в июне этого года. Они заменяют традиционный перекрестный и мутационный GA относительно новым животным, известным как вероятностный генетический алгоритм построения модели или PMBGA. Одним из таких штаммов PMBGA является «компактный GA» (cGA), совместно разработанный Лобо, когда он был студентом Иллинойсской лаборатории генетических алгоритмов (IlliGAL) Университета Иллинойса в Урбана-Шампейн.

IlliGAL показал, что детское поколение возможных решений, полученных в результате множественных скрещиваний, статистически идентично поколению, основанному исключительно на вероятностной модели родительских хромосом. Например, учитывая следующие четыре 4-битных хромосомы, которые нужно спарить, 1011, 1000, 1001, 1010, вероятностная модель, описывающая все четыре члена, генерируется путем вычисления вероятности того, что каждый бит будет иметь значение «1», что приводит к четырехзначная вероятностная модель 1,0, 0,0, 0,5, 0,5. Конечно, в этом 4-битном примере есть только 16 возможных решений, но у 1000-битных хромосом их немного больше. Следующее поколение любого размера совокупности может быть создано на основе вероятности того, что каждый бит имеет значение 1. Модель cGA инициализируется с вероятностью 0,5 для каждого бита и сходится, когда модель содержит только значения вероятности 1,0 и 0,0.

А как насчет популяции из 1 миллиона 1000-битных хромосом, которые необходимо оценить на пригодность? Лобо предлагает назначить одного процессора менеджером, который хранит единственную копию последней модели с 1000 значениями наилучшей совокупности. Если мы используем 20 бит для представления значения вероятности с плавающей запятой, модель потребляет 20 килобит памяти — по сравнению с 1 гигабитом, необходимым для традиционного ГА. Каждый параллельный рабочий процессор запрашивает копию модели, генерирует большое количество возможных решений, оценивает их пригодность, вычисляет новую вероятностную модель и отправляет разницу между новой и исходной моделями обратно менеджеру. Менеджер корректирует основную вероятностную модель, используя разницу, и выдает обновленную модель по запросу рабочих.

Простота масштабирования проявляется в том, что любое количество рабочих может запросить последнюю копию мастер-модели, вычислить обновление и асинхронно передать его менеджеру. Дополнительные работники могут присоединиться в любое время, система отказоустойчива к тому, что работники уходят или никогда не возвращают обновление, и между работниками не требуется обязательное общение. Дополнительное тестирование параллельного cGA будет включать в себя распределенный интернет-кластер, аналогичный проекту SETI@home.

Во время работы в Исследовательской лаборатории ВВС в начале 1990-х годов генерал из Комиссии по реорганизации и закрытию базы посетил нашу лабораторию топлива и горения, посмотрел на лазеры, компьютеры, оптику и прицелы стоимостью в миллионы долларов и спросил: эта лаборатория? Мой ответ: «Мы заставляем самолеты летать быстрее и дальше». Пити работает каждый раз.

Первоначально этот материал был опубликован как редакционная статья в журнале Scientific Computing and Instrumentation 21:11 October 2004, pg. 10.

Уильям Л. Уивер — адъюнкт-профессор кафедры интегрированных наук, бизнеса и технологий Университета Ла Саль в Филадельфии, штат Пенсильвания, США. Он имеет B.S. Получил двойную степень по химии и физике и получил докторскую степень. в аналитической химии с опытом в сверхбыстрой лазерной спектроскопии. Он преподает, пишет и рассказывает о применении системного мышления для разработки новых продуктов и инноваций.