Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Эффективная аппаратная реализация генетического алгоритма Compact GA для поиска экстремума функций

Бесплатно
Основная коллекция
Артикул: 620051.01.99
Борисевич, А. В. Эффективная аппаратная реализация генетического алгоритма Compact GA для поиска экстремума функций / А. В. Борисевич // Электронный журнал "Знаниум". - Москва : НИЦ Инфра-М, 2014. - 7 с. - ISSN 2311-8539. - Текст : электронный. - URL: https://znanium.com/catalog/product/470335 (дата обращения: 29.03.2024)
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
ОПТИМИЗАЦИЯ ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ 

Оптимізація виробничих процесів. Вип. 10: зб. наук. пр. — Севастополь: Вид-во СевНТУ, 2007. 

189

УДК 519.854.6 
А.В. Борисевич 
Севастопольский национальный технический университет 
ул. Университетская 33, г. Севастополь, Украина, 99053 
E-mail: alex.borysevych@gmail.com 
ЭФФЕКТИВНАЯ АППАРАТНАЯ РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКОГО АЛГОРИТМА 
COMPACT GA ДЛЯ ПОИСКА ЭКСТРЕМУМА ФУНКЦИЙ 
 
Предложена сверхбыстродействующая аппаратная реализация генетического алгоритма 
для поиска экстремума функций многих переменных, оптимальная по нормированному 
отношению стоимости к производительности. Рассмотрены различные варианты реализации 
предложенного подхода на больших программируемых интегральных схемах (FPGA). Даны оценки 
сложности соответствующих схем. 
 
Введение. Численная оптимизация функций большого числа аргументов чрезвычайно актуальна 
во многих практических приложениях. Отдельный класс составляют задачи управления на основе 
процедуры численной оптимизации, периодически применяемой к модели динамического процесса для 
вычисления траекторий управляющих воздействий с учетом текущего состояния системы (так 
называемое управление на основе предсказания – MPC [1]). Определенные задачи синтеза и диагностики 
дискретных систем также ведут к решению задач оптимизации функций от большого числа переменных. 
Для решения этих и многих других задач может быть применен генетический алгоритм – метод 
стохастического поиска экстремума функции, отличающийся большой гибкостью (возможностью 
применения к неявно заданным, дискретным и разрывным функциям), высокой производительностью и 
не требующий информации о производных оптимизируемой функции. Генетический алгоритм является 
эволюционным алгоритмом, т.е. алгоритмом, построенным на прямых аналогиях с процессом эволюции 
в биологических системах. В целом, генетическому программированию посвящено огромное количество 
работ. В частности в [1] генетический алгоритм применен к задаче управления на основе предсказания. 
Генетический алгоритм также является эффективным инструментом построения проверяющих и 
диагностических тестов для дискретных схем [2]. 
В условиях использования нелинейных и вероятностных моделей, а также возрастающей 
вычислительной сложности задач оптимизации, создание функционально-ориентированных аппаратных 
систем для решения задач оптимизации представляет собой естественный и эффективный подход. В 
работе [3] была предложена версия генетического алгоритма (Compact GA), реализация которой 
отличается чрезвычайно малыми затратами памяти и высокой производительностью, не уступающей 
традиционным реализациям генетических алгоритмов. Учитывая эти свойства Compact GA, можно 
предложить его аппаратную реализацию в виде автомата, который синтезируется в большой 
программируемой интегральной схеме (ПЛИС, FPGA) и описан на языке VHDL или Verilog HDL. 
Следует заметить, что некоторым вопросам аппаратной реализации Compact GA посвящена работа [4]. В 
работе [5] предложена реализация алгоритма вероятностного алгоритма UMDA. 
Целью статьи является следующее: 
– 
синтез 
аппаратной 
последовательно-параллельной 
реализации 
генетического 
поиска, 
оптимально использующей логические ресурсы FPGA; 
– построение реализации Compact GA с учетом возможности селекции решений (хромосом). 
Параллельная аппаратная реализация. Вначале проанализируем полную параллельную 
реализацию алгоритма Compact GA. 
Рассматривается n-битная проблема, которая определена как минимизация функции 
(
)
F X , где X 
– n-битный двоичный вектор. Входным параметром также является размер популяции m. 
Генетический алгоритм Compact GA может быть описан следующим образом. 
0. Для 
[1, ]
i
n
∈
: 
= 0,5.
iP
 

1. Сгенерировать два двоичных вектора X  и Y , для которых 
({
= 1}) =
i
i
p
X
P  и 
({
= 1}) =
i
i
p Y
P . 

2. Вычислить 
=
(
)
X
F
F X  и 
=
( )
Y
F
F Y . 

3.1. Если 
X
F  < 
Y
F , то для 
[1, ]
i
n
∈
, и всех таких 
i
i
X
Y
≠
 выполнить 
=
/
(1
)/
i
i
i
i
P
P
X m
X
m
+
−
−
. 

3.2. Иначе – для 
[1, ]
i
n
∈
, и всех таких 
i
i
X
Y
≠
 выполнить 
=
/
(1
)/
i
i
i
i
P
P
Y m
Y
m
+
−
−
. 

4. Если существует такой 
iP , что 0 <
< 1
iP
, то – продолжить процесс (перейти к п.1), иначе – 
решение получено. 
Из данного алгоритма видно, что основным элементом аппаратной реализации генетического 
алгоритма является генератор случайных чисел, который генерирует две последовательности из