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

ОПТИМИЗАЦИЯ ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ 

Оптимізація виробничих процесів. Вип. 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), иначе – 
решение получено. 
Из данного алгоритма видно, что основным элементом аппаратной реализации генетического 
алгоритма является генератор случайных чисел, который генерирует две последовательности из 

ОПТИМИЗАЦИЯ ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ 

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

190

двоичных чисел, с заданной вероятностью получения единичного значения 
(1) =
p
p  на выходе. Каждая 
выходная последовательность образует соответствующий бит вектора решения X  и Y . 
Структурная схема генератора случайных чисел показана на рисунке 1. В схеме LSFR – регистр 
сдвига разрядностью k  с линейной обратной связью, реализующий генератор псевдослучайных чисел 
разрядностью k ; RG – регистр разрядностью 
1
k +  (
2
=
k
log m ), который хранит вероятность генерации 

p ; элемент помеченный как «=» – схема сравнения, генерирующая логическую 1, если выполняется 
<
LSFR
RG . 

 
 
Сложность реализации этого узла 
( )
R
S
k , выражаемая в логических ячейках FPGA, линейно 

зависит от k , примерно как 
( ) = 5
4
R
S
k
k +
. 
Поскольку вычисление целевой функции – отдельная задача, которая здесь не рассматривается, 
будем считать, что некоторая схема со сложностью 
*
F
S  вычисляет за 
*
Ft  тактов по векторам X  и Y  

признак w . В случае, если 
(
) <
( )
F X
F Y , то 
= 1
w
, иначе – 
= 0
w
. 
Согласно алгоритму Compact GA, после каждого оценивания решений X  и Y  осуществляется 
модификация вектора вероятностей P. В терминах аппаратной реализации, это означает, что входы +1 
(обозначим этот сигнал как 
iI ) и –1 (
i
D ) зависят от сигналов 
i
X , 
iY  и результата оценивания решений 

w . Соотношения, связывающие эти сигналы имеют вид: 

= (
)
(
),

= (
)
(
).

i
i
i
i
i

i
i
i
i
i

I
X
Y
X w
Y w

D
X
Y
X w
Y w


⊕
∧
∨

⊕
∧
∨

 
 
 
 
 
(1) 

Поскольку каждая функция в (1) реализуется на одной логической ячейке FPGA, сложность узла 
составит – 
( ) = 2
C
S
k
. 

Общая сложность 
( , )
S n k  схемы зависит от параметров n  и k  следующим образом:  

*
*
( , ) = (
( )
( ))
( , ) = 5
6
( , )
R
C
F
F
S n k
n S
k
S
k
S
n k
nk
n
S
n k
+
+
+
+
. 
Рассмотренная реализация оказывается самой быстродействующей из всех возможных. Если 
положить, что вектора решений X  и Y  оцениваются за один такт и модуль вычисления целевой 
функции представляет собой полностью комбинационную схему, то генерация одной популяции 
осуществляется за один такт синхросигнала, поступающего на тактовые входы регистров LSFR и RG. 
Последовательно-параллельная аппаратная реализация. Параллельная реализация Compact 
GA оказывается очень эффективной. Однако не все преимущества архитектуры FPGA оказываются 
задействованы в данном случае (например, встроенная память). Также, существуют такие задачи, где 
высокое быстродействие параллельного алгоритма Compact GA не требуется, и необходимо найти 
некоторый компромисс между быстродействием и стоимостью (потреблением) FPGA. 
В этих случаях эффективной является последовательно-параллельная реализация алгоритма 
Compact GA, описанная ниже. 
Суть реализации заключается в том, что n  битов вектора решения разбиваются на r  блоков по 

=
/
l
n r



  бит в каждом. Каждый бит решения хранится в адресуемой однобитной ячейке, в которую 

заносится результат сравнения значения LSFR-регистра генератора псевдослучайных чисел с 
вероятностью 
iP . Для оптимального использования ресурсов FPGA, вероятности 
iP  хранятся во 
встроенной RAM-памяти. Поскольку каждый блок работает независимо от других, то число r  
ограничивается количеством блоков встроенной в FPGA RAM-памяти. 

LSFR

RG

=

k

k

set
+1

-1

yi

clk

LSFR

=
xi

k

 
Рисунок 1 – Функциональная схема генератора

одного бита векторов решения 

ОПТИМИЗАЦИЯ ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ 

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

191

Структура блока для формирования l  битов решения показана на рисунке 2. 
 

 
 
Основа модуля – ОЗУ (RAM). По адресу i  в RAM-памяти хранится значение вероятности 
iP  вместе 

с битами векторов решений 
i
X  и 
iY . 
Рассмотрим процесс функционирования модуля. Диаграммы работы показаны на рисунке 3. Пусть 
два вектора решения X  и Y  оценены, и признак w  условия 
(
) <
( )
F X
F Y  сгенерирован. Счетчик CT2, 
инкрементирующийся по спаду сигнала clk, устанавливает адрес i текущей ячейки памяти (на рисунке 2 – 
момент времени 1). Одновременно с этим, генераторы LSFR 
вырабатывают очередное случайное число. 
После установления адреса i на входе A, по фронту 
clk на выходе памяти RD устанавливается вероятность 
P`=
iP  и значения X`=
i
X  и Y`=
iY  (момент времени 2). 
Комбинационные схемы сравнения (обозначенные на 
рисунке 2 символом «=»), вырабатывают значения X и Y 
(момент времени 3). В этот же момент, логическая схема, 
обозначенная на рисунке 2 как «+1/–1», анализируя 
значения сигналов X`, Y` и признака w, модифицирует 
(уменьшает или увеличивает на 1) считанную из памяти 
вероятность P`, формируя новое значение P. 
По спаду сигнала clk сформированные на линиях X и 
Y значения записываются в выбранную пару триггеров FF, 
хранящих биты векторов результата для оценивания 
(момент времени 4). В этот же момент в RAM-память по 
адресу i записываются значения P, X и Y. 
Счетчик адреса CT2 увеличивает свое значение, и 
цикл повторяется для следующего бита решения. 
Видно, что формирование всех l  битов фрагмента 
решения осуществляется за 
= l
τ
 тактов синхросигнала clk. 
Оценим сложность всей реализации. ОЗУ использует 
встроенные в FPGA блоки памяти и поэтому не занимает 

=

k

k

clk

=

k

RAM
RD

CLK

WD

A

LSFR

LSFR

CT2

+1 / -1

k

w

X

Y

P`

X`

Y`

P

=

FF
FF
yi
xi
i

=

FF
FF
i+l

. . .
. . .

xi+l
yi+l

. . .

 
Рисунок 2 – Функциональная схема формирователя 
фрагмента решения 
 

 

clk

A

(P`,X`,Y`)

LSFR

(X,Y)

P

FF

1

1

2

3

4

3

Рисунок 3 – Диаграммы работы формирователя

фрагмента решения 

ОПТИМИЗАЦИЯ ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ 

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

192

логических ресурсов. Обозначим 
2
=
q
log l

 . Счетчик CT2 всегда занимает q  ячеек. Схемы сравнения, 

LSFR и инкрементор-декрементор в сумме занимают 5
4
k +
 ячеек (как генератор одного бита в 
полностью параллельной реализации). 
Рассмотрим логические затраты на реализацию линейки элементов памяти из триггеров FF и 
детекторов адреса. Каждый детектор адреса представляет собой схему, реализующую булеву функцию 
от q  переменных, выход которой подключен к триггерному элементу. Можно показать, что сложность 

( )
bit
S
q  реализации одного бита линейки определяется как число логических элементов, с числом входов 

4, минимально необходимых для реализации функции от q  переменных: 
1
( ) =
3
bit
q
S
q
−

 . 

Сложность 
( , )
B
S
k l  одного блока формирователя фрагмента решения определяется как сумма: 

2
2
( , ) = 5
4
2 (
1)/3
B
S
k l
k
l
log l
log l
+
+
 
 −
 + 
 . 

Сложность 
( , , )
S n k r  реализации схемы в целом оценивается как: 

*
2
2
( , , ) = 5
4
2
(
( / )
1)/3
( / )
( , )
F
S n k r
kr
r
n
log
n r
r log
n r
S
n k
+
+
 
 −
 + 
 +
. 
Об оптимальности последовательно-параллельной реализации. Будем рассматривать такие 
задачи, в которых 
= 2a
n
, где 
{1,2...}
a ∈
. Очевидно, что любая другая задача может быть сведена к 
рассматриваемой. Для наиболее оптимального распределения ресурсов необходимо, чтобы все ячейки 
блоков памяти были заполнены, т.е. = 2b
l
, где 
{1,2...}
b∈
. 

Обозначим l  как: 
2
2
= / = 2
= 2

log n log r
l
n r
γ
−
. Очевидно, что 
Z
γ ∈
. 

В таком случае, можно переписать выражение для сложности 
( , , )
S n k γ : 

*
( , , ) = 5
/2
2
(
1)/3
/2
4
( , )
F
S n k
kn
n
n
S
n k
γ
γ
γ
+
 γ −
 + γ
+
+
. 

Рассматривая функцию 
( , , )
S n k γ  как непрерывную от своих аргументов, можно убедиться в ее 

унимодальности на промежутке 
2
0 <
< log n
γ
. К сожалению, аналитически минимум 
( , , )
S n k γ  по γ  
найти невозможно, и точное решение можно найти только численно. Следующее соотношение дает 
относительно точную оценку минимума 
( , , )
S n k γ  по γ : 

1
3
`
=
((5
5)
(2) 1)
( )
(2)
2
opt
ln
k
ln
k
ln




γ
+
⋅
−
= γ








. 
 
 
 
(2) 

Поскольку 
= l
τ
, то 
=
/n r
τ



 . Рассматривая оптимальность по времени решения, минимум τ  

достигается при разбиении результата на opt
r
 блоков, т.е. 

=
{
, }
opt
FPGA
r
min r
n , 

где FPGA
r
 – число блоков памяти в FPGA. 
Рассмотрим два случая синтеза аппаратной реализации Compact GA для решения n -битной 
проблемы. 
Для первой задачи задано ограничение на стоимость (сложность) через S  и r  в виде: 

,

,

FPGA

FPGA

S
S

r
r

<

 <

 

где
FPGA
S
 – максимальная сложность схемы, 
FPGA
r
 – максимальное число блоков памяти. Требуется 
найти такую структуру, которая бы удовлетворяла этим ограничениями и обладала максимальной 
производительностью (
min
τ →
). Если 
*
5
6
( , )
FPGA
F
S
nk
n
S
n k
≥
+
+
, то эта задача решается с помощью 
полностью параллельной реализации Compact GA. В противном случае, используется последовательнопараллельная реализация с разбиением результата на FPGA
r
 блоков. 
В другом случае, задано ограничение на минимальное быстродействие τ : 

max
τ < τ
. 
Требуется найти такую структуру, которая бы удовлетворяла этому ограничению и обладала 
минимальной сложностью: 
min
S →
. Поскольку 
/
l
n r
τ = =
, то 
max
/
max =
2 n
n
−
τ
γ
⋅
. Вычислив по формуле 

(2) значение 
`opt
γ
, получим два варианта: 
max
`opt
γ
≥ γ
 и 
max
`opt
γ
< γ
. Если 
max
`opt
γ
≥ γ
, то реализуем 

схему с 
`opt
γ = γ
. В противном случае для реализации берем 
max
γ = γ
. 

 

ОПТИМИЗАЦИЯ ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ 

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

193

Применение селективной техники. В реализации, рассмотренной выше, использовались два 
вектора решения X и Y. Как показано в [3], можно уменьшить число вычислений целевой функции, 
введя селекцию из v  векторов решений 
1
X ,...
v
X . 
Для эффективной аппаратной реализации можно переформулировать соответствующий алгоритм, 
приведенный в [3], следующим образом. 
0. Для 
[1, ]
i
n
∈
: 
= 0,5
iP
. 

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

2. Для 
2
[1,
]
v
h
C
∈
 выполнять 

2.1. По значению h  сформировать индексы = ( )
i
i h  и 
= ( )
j
j h  пары решений 
iF  и 
j
F . 

2.2. Если 
iF  < 
j
F , то 
= 1
h
w
, иначе 
= 0
h
w
. 

3. Для 
[1, ]
k
n
∈
, вычислить 
=
( ,
)
i

k
k
P
w X
∆
∆
 и скорректировать 
=
k
k
k
P
P
P
+ ∆
. 

4. Если существует такой 
kP , что 0 <
< 1
kP
, то – продолжить процесс, иначе – решение получено. 
Рассмотрим общую структуру системы, показанную на рисунке 4. 
Как и для случая 
= 2
v
, биты результата хранятся в блоках памяти (для коррекции вероятностей) и 
в линейке триггеров-защелок (для оценки решения). 
 

B1

Br

.
.
.

X1
Xv

(F(X),F(Y))

MX

A

D

MX

A

D

CT2

h / i

h / j

W

log2 
hmax

.
.
.

.
.
.

.
.
.

DMX

A

D
w

n

log2 v

log2 v

hmax

h

i

j

X

Y

n

 
Рисунок 4 – Структура реализации с селекцией из множества векторов решений 
 
На рисунке 4 блоки X1-Xv – векторы решений. Компоненты X1-Xv генерируются с помощью 
элементов B1-Br, каждый из которых содержит ОЗУ и v  генераторов случайных чисел. Каждый Bi 

осуществляет генерацию =
/
l
n r

  одноименных бит в X1-Xv. 
Как только векторы результата X1-Xv сгенерированы, начинает работу счетчик CT2, который на 
своем выходе последовательно выдает коды h  пар результата от 0 до 
2
=
1
max
v
h
C − . Преобразователи h/i 

и h/j формируют по коду h  индексы i и j для выбора двух векторов решений. Через мультиплексоры MX 
значения векторов решений подаются на схему оценивания (F(X),F(Y)) в качестве аргументов X  и Y . 
Схема оценивания вырабатывает признак 
= 1
w
 при 
(
) <
( )
F X
F Y . Далее значение w  передается через 
демультиплексор DMX на регистр W. Таким образом, после перебора и оценивания всех пар, 
оказывается сформирован вектор W, в котором каждый бит 
iw  представляет результат оценки i-ой пары. 

Преобразователи h/i и h/j задают табличное отображение кодов h пар в индексы i и j (
= 0
h
, 

( , ) = (0,1)
i j
; 
= 1
h
, ( , ) = (0,2)
i j
; и т.д.). 
Блок генерации фрагмента решения Bi подобен структуре, изображенной на рисунке 3 (для 
= 2
v
) 
с тем отличием, что содержит 
> 2
v
 генераторов LSFR и схем сравнения для формирования компонентов 
каждого вектора решения 
i
X . 

ОПТИМИЗАЦИЯ ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ 

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

194

Модуль коррекции вероятности 
kP  на 
( ,
)
i
k
w X
∆
, заменяющий управляемый инкрементордекрментор в реализации на рисунке 2, состоит из системы элементов, представляющих собой модули 
для вычисления значений сигналов 
iI  и 
i
D  по выражению (1), выходы которых присоединены к 

управляемым инкременторам-декременторам. Всего в схеме содержится 
max
h
 таких элементов, каждый 

из которых анализирует значение 
h
w  и обрабатывает соответствующую 
h
w  пару (
,
)
(
,
)
j
i
i
j
k
k
x x
X
X
=
 

векторов решения. Например, для 
4
v =
 схема коррекции 
kP  осуществляет следующее преобразование: 

0
1
1
0
2
2
0
3
3
1
2
4
1
3
5
2
3
6

0
1
1
0
2
2
0
3
3
1
2
4
1
3
5
2
3
6

`
(
,
,
)
(
,
,
)
(
,
,
)
(
,
,
)
(
,
,
)
(
,
,
)

(
,
,
)
(
,
,
)
(
,
,
)
(
,
,
)
(
,
,
)
(
,
,
),

k
k
P
P
I x
x w
I x
x
w
I x
x w
I x x
w
I x x w
I x
x w

D x
x w
D x
x
w
D x
x
w
D x x
w
D x x
w
D x
x w

=
+
+
+
+
+
+
−

−
−
−
−
−
−
 

где 
(
,
,
) = (
)
(
)
i
j
h
i
j
i
h
j
h
I x x
w
x
x
x w
x w
⊕
∧
∨
 и 
(
,
,
) = (
)
(
)
i
j
h
i
j
i
h
j
h
D x x
w
x
x
x w
x w
⊕
∧
∨
 согласно (1); 
kP  – 

значение вероятности на предыдущем шаге. 
Оценим сложность рассмотренной реализации. 
Сложность одного блока формирования фрагмента решения 
( , , )
B
S
v k l  может быть определена 
следующим образом: 

2

2
2
( , , ) = (2
2)
(
1)/3
6
B
v
S
v k l
v
k
vl
log l
log l
C
+
+
 
 −
 + 
 +
. 

Сложность всей схемы 
( , , , )
S v n k r  находится как: 

2
*
2
2
( , , , ) =
(2
2)
(
( / )
1)/3
( / )
6
( , )
v
F
S v n k r
vr
k
vn
log
n r
r log
n r
rC
S
n k
vn
+
+
 
 −
 + 
 +
+
+
. 
Некоторые практические результаты. Предложенные структуры для аппаратной реализации 
генетического поиска были опробованы на ПЛИС (FPGA) EP2C20F484C7N семейства Cyclone II. Все 
схемы описаны на языке Verilog HDL и в качестве логического компилятора был использован 
Quartus II 6.0. 
Приведем результаты простой полностью параллельной реализации генетического алгоритма. 
Тактовая частота устройства f = 100 МГц. Размер популяции 
= 64
m
. Рассматривается квадратичная n
битная проблема: 
2

=1
(
) =

N

i

i

F X
x
∑
, где для представления 
ix  отводится 10 битов и
= /10
N
n
. 

Приведем результаты аппаратной реализации и быстродействия системы для различных структур 
и разного числа n  (таблица 1). 
 
Таблица 1 – Результаты различных реализаций алгоритма Compact GA 

n
*
F
S
, лог. эл. 
||S , лог. эл. 
||τ , мкс 
S
S , лог. эл. 
S
τ , мкс 
Sτ , лог. эл. 
ττ , мкс 

30 
108 
1099 
10 
261 
320 
1645 
10 

60 
242 
2242 
13 
484 
416 
1872 
26 

100 
426 
3616 
18,2 
892 
582,4 
2029 
36,4 

200 
871 
7273 
23,6 
1707 
755,2 
2751 
94,4 

400 
1758 
14428 
30 
3400 
960 
3972 
300 

 
В таблице 1 использованы следующие обозначения: n  – число битов вектора решения; 
*
F
S
 – 

сложность схемы оценивания решений в логических элементах FPGA; 
||S  – сложность полностью 

параллельной реализации Compact GA; 
||τ  – время минимизации функции с применением параллельной 

реализации; 
S
S  – сложность реализации, полученной при оптимальном по сложности разбиении 

результата, на блоки по 
`
2
32
opt
γ
=
 бита; 
S
τ  – время минимизации функции при оптимальном по 

сложности разбиении результата; Sτ  – сложность реализации, полученной при разбиении результата на 

50
FPGA
r
r
=
=
 блоков для максимизации быстродействия; 
S
τ  – время минимизации функции при 
разбиении результата на 
50
r =
 блоков. 
Как видно из результатов, даже для 400-битной проблемы время поиска минимума не превышает 1 
мс, что позволяет применять рассмотренные аппаратные реализации в системах оптимизации и 
управления реального времени. Использование последовательно-параллельной реализации позволяет 
значительно снизить аппаратные затраты для приложений, где не требуется сверхвысокое 
быстродействие. 
 
 

ОПТИМИЗАЦИЯ ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ 

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

195

Выводы. Предложены и проанализированы различные варианты аппаратной реализации 
генетического алгоритма Compact GA для оптимизации функций. Рассмотрена полностью параллельная 
реализация, 
последовательно-параллельный 
подход 
и 
применение 
селекции. 
Предложенные 
соотношения для оценки быстродействия и сложности позволяют выбрать наиболее оптимальный 
вариант реализации для заданной задачи. 
Дальнейшие исследования будут направлены на применение конвейеризации к процессам 
генерации и оценивания решений, частичному (сокращенному) оцениванию результатов. Предложенный 
подход с небольшими изменениями может быть применен для реализации некоторых других вариантов 
генетических алгоритмов (в первую очередь, для SG-Clans алгоритма). 
 
Библиографический список 
1. Martinez M. Generalized predictive control using genetic algorithms (GAGPC) / M. Martinez, 
J.S. Senent, X. Blasco // Proceedings of Engineering Applications of Artificial Intelligence, Castellón, Spain, 
June 1 – 4, 1998. — Castellón, 1998. — V. 11. — P. 355 – 367. 
2. Rudnick E.M. Application of Simple Genetic Algorithm to Sequential Circuit Test Generation / E.M. 
Rudnick, J.G. Holm, D.G. Saab, J.H. Patel // Proc. European Design & Test Conf, Paris, France, September 17 – 
20, 1994. — Paris, 1994. — P. 40 – 45. 
3. Harik G. The Compact genetic Algorithm / G. Harik, F. Lobo and D. Goldberg // IEEE Transactions on 
Evolutionary Computation. — 1999. — V. 3. — P. 287 – 309. 
4. Chatchawit A. A Hardware Implementation of the Compact Genetic Algorithm / A. Chatchawit and 
C. Prabhas // Proceedings of the 2001 IEEE Congress on Evolutionary Computation, Seoul, Korea, May 27 – 30, 
2001. — Seoul, 2001. — P. 624 – 629. 
5. Гудилов В.В. Методы повышения эффективности вероятностных алгоритмов, адаптированные к 
возможности динамических изменений параметров функционирования на примере аппаратной 
реализации генетического алгоритма UMDA / В.В. Гудилов, В.М. Курейчик // Перспективные 
информационные технологии и интеллектуальные системы: сб. научн. тр. — Таганрог, 2005. — № 1 (21). 
— C. 42 – 54. 

Поступила в редакцию 24.10.2007 г.