<<
>>

Параллельная обработка информации на основе генетических алгоритмов

Предлагается новая технология параллельной обработки ин­формации при решении задач оптимизации на основе генетиче­ских алгоритмов. Генетические алгоритмы основаны на создании популяции альтернативных решений, их селекции, определения целевой функции и применения генетических операторов для мо­делирования эволюции и получения наборов оптимальных и ква- зиоптимальных решений.

Одним из возможных путей ускорения вычислений за счет параллельного выполнения генетических алгоритмов является представление их структуры в виде совокупности слабо связан­ных потоков команд.

Тогда алгоритм может быть сегментирован как набор процессов, каждый из которых может выполняться на отдельном процессоре и (при необходимости) осуществлять взаимодействие с другими процессорами. Такая архитектура эво­люционного поиска аналогична архитектурам ЭВМ с множе­ственным потоком команд и множественным потоком данных [13.1, 13.2].

Предлагается при обработке информации выполнять микро-, макро- и мета-эволюцию. Используя мета-эволюцию, создается

не одна популяция, а некоторое множество (т. е. «вид») популя­ций. Поиск решений осуществляется путем объединения реше­ний из различных популяций.

Верхний и нижний уровни генетического алгоритма работают параллельно. Взаимодействие между уровнями фиксировано и осуществляется исходя из предварительного отношения «доми­нирование-подчинение» φ = (Φ, M), Φ ⊆M ? M. Здесь φ— нечеткое отношение, Φ — график нечеткого отношения, задаю­щего доминирование подчинения, M — множество, область, на которой задано нечеткое отношение.

На рис. 13.2 приведена одна из разработанных схем парал­лельного поиска, когда популяция решений оптимизационной задачи разбивается на 6 подпопуляций и каждая исследуется своим простым генетическим алгоритмом (ГА1-ГА6). Далее вы­полняются различные виды миграции альтернативных решений между генетическими алгоритмами, согласно коммутационным схемам.

Это дает возможность распараллеливать процесс, эффектив­но управлять поиском, получать оптимальные и квазиоптималь- ные решения. Временная сложность алгоритмов, реализованных на таких схемах (архитектурах), в основном совпадает со слож­ностью быстрых итерационных алгоритмов и лежит в пределах O(n)-O(n3), где n — число входов алгоритмов. Эта сложность обещает перспективность использования композитных алгорит­мов, основанных на бионических принципах, при решении задач компоновки в САПР.

В работе [13.9] описана многоуровневая архитектура «Ма­шина Тьюринга» для автономного агента. При решении задач обработки информации в неопределенных или нечетких услови­ях с некоторыми допущениями в качестве автономного агента можно рассматривать генетический алгоритм [13.3, 13.9]. При­ведем модифицированную архитектуру «Машина Тьюринга» для задачи проектирования. Такая архитектура объединяет в себе механизмы рассуждений на основе знаний о решаемой задаче. Пусть задан «главный» генетический алгоритм, взаимодейству­ющий с другими соподчиненными генетическими алгоритмами, анализирующий нечеткие события внешней среды, информация о которой носит фрагментарный характер. При этом «главный» ге­нетический алгоритм выступает в роли экспертной системы или лица, принимающего решения. Предлагается такая архитектура поиска, которая функционирует в условиях неопределенности, неполноты, неточности и реагирует на неожиданные (незакреп-

9 В.

М. Курейчик, Б. К. Лебедев, О. Б. Лебедев

Рис. 13.2. Схема параллельного поиска

ленные в жесткой структуре алгоритма) нечеткие высказывания. Пример такой архитектуры приведен на рис. 13.3.

Уровень планирования генерирует и конструирует полные и частичные популяции альтернативных решений задачи. Уро­вень моделирования и эволюции анализирует поведение объек­тов внешней среды и генетического алгоритма. Это используется для реализации той или иной модели эволюции, для обработки

Рис. 13.3. Многоуровневая архитектура генетического алгоритма «Машина Тьюринга»

текущего состояния задачи. Уровень реакции на событие опреде­ляет способность генетического алгоритма реагировать на сигна­лы, идущие от верхних уровней. Уровень функционирования ге­нетических операторов выбирает порядок, способ и вероятность их применения. Каждый уровень напрямую связан с подсистема­ми действия и восприятия. Любой уровень независимо от других может реагировать на текущее состояние внешней среды. В рас­сматриваемой архитектуре включена подсистема управления на основе различного вида правил, активируемая внешней средой и подсистемой адаптации. Ее основная задача — получение локально-оптимальных результатов компоновки. Система играет роль «посредника» между входом и выходом, т. е. вероятностным или нечетким автоматом, который анализирует данные разных уровней, вводит на различные уровни новые и удаляет ненужные

данные. Такое управление сохраняется в течение всех поколе­ний работы генетического алгоритма. Подсистемы управления и адаптации обеспечивают синхронизацию входов и выходов всех уровней.

Предлагается подход динамического «отслеживания» опти­мальных параметров и структур генетических алгоритмов с по­мощью методов параметрической и структурной адаптации. Для адекватного управления структурой генетических алгоритмов предлагается использовать автомат адаптации, предложенный М. Л. Цетлиным [13.10]. Схема процесса альтернативной адап­тации показана на рис. 13.4. Здесь компенсатор регулирует ди­намически изменяемый размер популяции решений, расширяя, сужая или оставляя ее постоянной. После реализации эволюции компенсатор при взаимодействии с внешней средой реализует принципы эволюционного поиска. При этом лучшие решения отправляются для смешивания популяций и выхода из локаль­ных оптимумов. Блоки сумматор, редуктор и фильтр позволяют повысить эффективность реализации эволюции и скорость при­нятия решения. Отметим, что в инженерных задачах большой размерности процесс решения резко усложняется, но параллель­ное выполнение генетических алгоритмов на порядок снижает временную сложность.

Рис. 13.4. Схема процесса альтернативной адаптации

Определение параметров генетических алгоритмов также мо­жет носить адаптивный характер. Для этого предлагается ис­пользование параметрических методов адаптации. Как правило, эти алгоритмы используют метод деления отрезка и, поэтому, пригодны для адаптивного «отслеживания» таких величин как

вероятность кроссинговера, размер популяции и т. д. Преиму­щество адаптивного метода становится заметным при n >100, где n — число, пропорциональное размерности задачи. Таким образом, логично сделать вывод об эффективности адаптивного подхода.

Приведем композитную архитектуру многоагентной систе­мы генетических алгоритмов (рис. 13.5) [13.9]. Она позволяет интегрировать рассуждения и действия конструктора-технолога по решению задачи оптимизации. Здесь генетический алгоритм в процессе работы выполняет следующие действия: восприни­мает и фильтрует информацию из внешнего мира (о моделях объектов разбиения); строит план работы на основании этой ин­формации; вступает в связь с другими генетическими алгоритма­ми для создания многоальтернативного генетического алгоритма; генерирует решения, принимая или отклоняя предложения из внешней среды. В основе опыта генетического алгоритма лежат следующие знания: о внешней среде; о «внутреннем мире» само­го генетического алгоритма; о «внутренних мирах» других гене­

Рис. 13.5. Генетический алгоритм с композитной архитектурой

тических алгоритмов; о взаимодействии с внешней средой; о вза­имодействии с другими генетическими алгоритмами. В структуре знаний выделяют базу фактов решения задач и инвариантную базу, которая не меняется на всех этапах.

Основная идея построения композиционной архитектуры ге­нетического алгоритма аналогична [13.9]. Здесь ведется постро­ение сложного генетического алгоритма из первичных компонент (строительных блоков), каждый из которых реализует одну из заданных подзадач общей задачи.

Каждый строительный блок имеет простое описание и ис­пользует свой набор решений. Сложное поведение системы обес­печивается динамической компонентой взаимодействия генетиче­ских алгоритмов. Тогда генетический алгоритм состоит из трех основных компонент (рис. 13.5):

• внутреннего состояния генетического алгоритма, которая включает знания о себе, знания о стратегиях управления генетическим поиском, генерации гипотез, позволяет учиты­вать неполноту знаний о задаче в управляющей части;

• взаимодействующей компоненты, которая соединяет ГА1 с внешней средой и с ГА2, причем обеспечивается обмен информацией с другими генетическими алгоритмами;

• анализа состояния внешней среды, которая содержит знания о решаемой задаче.

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

В заключение отметим следующее. Предложенный в работе метод адаптивного выбора может быть использован для решения любых задач САПР. Экспериментальные исследования показа­ли эффективность предложенного метода. Так, при компоновке объектов с использованием предложенного метода среднее число связей между блоками сократилось на величину до 25%. Из­менения входных параметров управляемого процесса поиска ре­шения допустимо только при малых диапазонах изменения этих параметров. При нежестких требованиях к качеству решений время может быть незначительным, так как уровень погрешно­стей в несколько процентов достигается в процессе выполнения не более нескольких десятков испытаний с помощью ПГА. Но при этом необходимо использовать оптимизированные наборы

эвристик. При более жестких требованиях к точности решений необходимо использовать композитные алгоритмы и предложен­ные архитектуры.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Параллельная обработка информации на основе генетических алгоритмов:

  1. МЕТОД, АЛГОРИТМЫ ОБРАБОТКИ ИЗОБРАЖЕНИЙ И СТРУКТУРНО-ФУНКЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ ОПТИКО-ЭЛЕКТРОННОГО УСТРОЙСТВА ТРЕХМЕРНОГО ТЕХНИЧЕСКОГО ЗРЕНИЯ С МНОЖЕСТВЕННЫМИ ИСТОЧНИКАМИ ИЗОБРАЖЕНИЙ
  2. 2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОБРАБОТКИ ИЗОБРАЖЕНИЙ УСТРОЙСТВОМ ТРЕХМЕРНОГО ТЕХНИЧЕСКОГО ЗРЕНИЯ С МНОЖЕСТВЕННЫМИ ИСТОЧНИКАМИ ИЗОБРАЖЕНИЙ
  3. 4.1. ПОСТАНОВКА И АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ
  4. Алгоритм формирования тремерной рабочей сцены при использовании нескольких оптико-электронных датчиков
  5. ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНО-ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ РАСЧЕТА ПЛИТ
  6. ГЛАВА 4. РАЗРАБОТКА АЛГОРИТМА ОПТИМИЗАЦИИ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  7. 1. Правовые основы системы образования
  8. 3. Основы административно-правового статуса граждан
  9. 2.2 Технология получения КМ на основе алюминия (Al-3масс.%Ni- 1масс.%Cu)
  10. Тема 18. Правовые основы управления образованием
  11. II ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДА ИНТЕРПОЛЯЦИИ ПО КОЭФФИЦИЕНТУ ФОРМЫ