Повышение производительности. 
Аппаратная реализация генетических алгоритмов

При проектировании алгоритма особое внимание было уделено вопросам модификации алгоритма с точки зрения оптимизации временных характеристик функционирования. Основополагающим критерием модификации являлось сохранение принципа функционирования алгоритма при максимально возможном сокращении временных характеристик алгоритма в целом.

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

На рисунке 2 представлена структурная схема устройства, поясняющая принцип взаимодействия генетических операторов на уровне взаимодействия блоков.

Рисунок 2. Структурная схема устройства, аппаратной реализации вероятностного генетического алгоритма UMDA.

В таблице 1 приведено значение общего повышения быстродействия алгоритма при аппаратной реализации по отношению к программной реализации для алгоритма UMDA, рассматриваемого в данной работе и компактного генетического алгоритма, представленного в работе [Chatchawit 2001].

Таблица 1. Общее повышение быстродействия.

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

Ниже представлены основные временные характеристики генетического алгоритма при тактовой частоте 125 МГц:

• — инициализация всех необходимых параметров — 176 нс.
• — генерация популяции на 256 особей при параллельном вычислении критерия пригодности и функционировании оператора отбора — 6.176 мкс.
• — формирование 8 элементов элитной области и параллельного вычисления вероятности — 540 нс.
• — чтение из памяти 120 значений критериев пригодности с параллельным процессом селекции (отбора) — 2,88 мкс.
• — чтение из памяти 8 значений критериев пригодности с параллельным процессом селекции без инициализации процесса чтения и ожидания освобождения внутреннего конвейера — 192 нс.
• — время одного цикла (итерации) генетического алгоритма (популяция = 256, элитная область = 128) составляет 8,409 микросекунды.

Основные параметры проектирования:

• — производитель ПЛИС: Altera
• — семейство: ACEX1K
• — обозначение: EP1K100FC256−1
• — максимальная частота: 125 МГц
• — необходимое количество логических ячеек — 3017
• — необходимый объем внутренней памяти — 24 112 bit.