устройство аппаратной реализации вероятностных генетических алгоритмов

Формула изобретения

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

Описание изобретения к патенту

Предлагаемое устройство относится к аппаратным системам, реализующим вероятностные генетические алгоритмы, используемые в эволюционных инструментальных комплексах, исследованиях при проектировании виртуальных аппаратных средств (Virtual Hardware), искусственной жизни (Artificial Life) и в области самоадаптирующихся и реконфигурируемых аппаратных средств (Self-Adapting and Reconfigurable Hardware), и предназначено для снижения вычислительных затрат на проведение эволюционного поиска и обеспечения автономности функционирования объекта при принятии решений в изменяющейся среде при использовании в автономных интеллектуальных системах, обеспечения возможности использования в качестве аппаратного устройства в эволюционных инструментальных комплексах, в робототехнике, исследованиях в области саморазвивающихся и самоадаптирующихся аппаратных средств, исследованиях в области построения адаптивных систем управления и принятия решений, в области автоматизации управления, повышения эффективности оптимизационных задач и т.п.

Известно устройство

"Fitness function circuit" Patent number: US 6185547, Application number: US 19970909830 19970812.

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

Признаками аналога, совпадающими с существующими признаками заявляемого изобретения, являются:

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

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

Известно устройство

"Genetic algorithm machine and its production method, and method for executing a genetic algorithm" Patent number: US 5970487, Application number: US 19970910103 19970813, универсальная не проблемно-ориентированная аппаратная структура для выполнения генетического алгоритма (ГА), увеличивающая скорость выполнения ГА посредством памяти популяции, первого и второго регистра хромосомы, модуля кроссинговера (crossover), оператора мутации (mutation) и компаратора отбора. Не проблемно-ориентированный аспект аппаратной структуры становится проблемно-ориентированным без изменений состава структуры при включении в структуру схемы проблемно-ориентированной функции фитнесса (функции пригодности) для оценки хромосом, представляющих потенциальное решение задачи. Аппаратная структура таким образом становится пригодной для различных проблемно-ориентированных аспектов схем проблемно-ориентированных функций.

Признаками аналога, совпадающими с признаками заявляемого изобретения, являются:

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

селектор для выбора хромосом из числа хромосом в популяции и выполнения операции скрещивания на множестве родительских хромосом для создания новых хромосом и выход новых хромосом как дочерних хромосом;

компаратор отбора для регулирования критерия выживания мутированных хромосом, основанного на вычисленном значении фитнесса;

схема инициализации для инициализации памяти популяции;

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

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

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

метод для формирования машины ГА для выполнения ГА, используя представление решения задачи как хромосомы, указанный метод заключает в себе этапы:

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

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

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

Из известных технических решений наиболее близким по технической сущности к заявляемому объекту является "Hardware Compact GA", представленное в A Hardware Implementation of the Compact Genetic Algorithm A.Chatchawit and C.Prabhas, Proceedings of the 2001 IEEE Congress on Evolutionary Computation // Seoul, KoreaMay 27-30, 2001, pp.624-629.

Параметры компактного генетического алгоритма Compact GA - размер популяции (n) и длина хромосомы (l). Популяция представлена l-разрядным вектором вероятности (р). Значение p[i] - вероятность того, что i-тая позиция бита индивидуума, отобранного случайным образом из популяции, будет единичной. Сначала р инициализируется как (0.5, 0.5..., 0.5). Затем индивиды а и b генерируются согласно значению вероятности р. Значение функции фитнесса далее назначается индивидуумам а и b соответственно. Если fa>fb, тогда вектор вероятности будет модифицирован к индивидууму а. Если fa=1, и fb=0, тогда p[i] будет увеличен на 1/n. Если fa=0, fb=1, тогда p[i] будет уменьшен на 1/n. Если fa=fb, тогда p[i] не будет модифицирован. Цикл повторяется до тех пор, пока каждое значение p[i] станет нулевым или единичным. В конечном счете р представляет заключительное решение.

Каждое значение вероятности p[i] может быть модифицировано параллельно. Кроме того, функционирование Compact GA может частично совмещаться. Это позволят использовать конвейерную обработку, которая улучшает аппаратные характеристики.

Аппаратный генетический алгоритм Compact GA включает следующие блоки: генератор случайного числа (RNG), регистр вероятности (PRB), компаратор (СМР), буферы (BUF) и вычислитель значения функции фитнесса (функции пригодности) (FEV).

Аппаратный генетический алгоритм Compact GA выполняет операции на векторе вероятности р. Каждое измерение p[i] модифицируется параллельно. RNG, PRB и СМР модули используются, чтобы генерировать две хромосомы и хранить их в буфере BUF. FEV модули оценивают значение фитнесса двух хромосом. СМР модуль определяет победителя/проигравшего и модифицирует значение вектора вероятности PRB.

Аппаратный генетический алгоритм Compact GA работает следующим образом. Когда сигнал сброса получен, в генераторы случайного числа устанавливаются в инициализирующие значения, регистры вероятности устанавливаются в 0.5, и буфера сбрасываются в начальное состояние. Затем, повторяются следующие шаги, пока все регистраторы вероятности не будут нулевыми или единичными (решение задачи onemax):

1. Результат вычисления значения функции фитнесса зависит от выполняемой операции увеличения или уменьшения выполняемой на регистре вероятности. Затем случайные числа и регистры вероятности сравниваются.

2. Буферы сохраняют результат сравнения. Если случайное число больше, чем p[i], i-тая позиция бита индивидуума а будет установлена в ноль. Иначе она будет установлена в единицу. Т.к. буфера синхронизированы, новые случайные числа генерируется одновременно.

3. Буферы выполняют ту же самую операцию, как в шаге 2 для индивидуума b. В этом шаге индивидуумы передаются вычислителям значений функции фитнесса, которые являются комбинационными схемами. Сравнение значений функции фитнесса используется, чтобы модифицировать регистры вероятности в шаге 1.

Каждый шаг выполняется за один такт.

В результате, Compact GA выполняет одну генерацию за три тактовых цикла для задачи one-max. Количество тактов на генерацию зависит от задачи оптимизации. Более сложным задачам требуется 3+е циклов, где е - количество циклов, используемое при оценке значения функции фитнесса индивидуума. Проект реализован с использованием языка описания аппаратуры Verylog. Размер популяции n и длина хромосомы l установлены как 256 и 32 соответственно. На заключительном этапе проект изготовлен на FPGA фирмы Xilinx. По результатам синтеза для задачи one-max проект использует 15210 эквивалентных вентилей, максимальная частота функционирования 23,57 МГц, было достигнуто повышение быстродействия по сравнению с программной версией в 1000 раз.

Признаками прототипа, совпадающими с признаками заявляемого изобретения, являются:

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

регистр вероятности содержит значение вероятности, являющиеся числом p[i], представленным в формате с плавающей запятой;

компаратор - комбинационная схема, сравнивающая два целых числа m и n. Если m n то на выходе будет "1". Иначе на выходе будет "0";

буфер - последовательная схема, содержащая i-ю битовую позицию индивидуумов а и b. Буферы содержат значения индивидуумов, в то время как они оцениваются;

вычислитель значения функции фитнесса. Используется два вычислителя чтобы вычислять значение фитнесса индивидуумов а и b параллельно. Для задачи one-max вычислитель значения функции фитнесса просто считает количество единиц в двоичной строке.

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

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

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

Устройство аппаратной реализации вероятностных генетических алгоритмов поясняется чертежами, где

на фигуре 1 приведен алгоритм генерации популяции,

на фигуре 2 приведена схема генератора псевдослучайной двоичной последовательности,

на фигуре 3 приведен пример параллельного формирования хромосомы, где блоки 3.1_1..3.1_32 представляют блоки генераторов случайной двойной последовательности RNG, 3.2_1..3.2_32 - регистры вероятности PRG, 3.3_1..3.3_32 - схему сравнения СМР,

на фигуре 4 приведен алгоритм вычисления критерия,

на фигуре 5 приведен пример параллельного вычисления критерия, где блоки 5.1..5.30 являются сумматорами соответствующей разрядности,

на фигуре 6 приведен пример параллельного функционирования блока отбора, где блок 6.1 представляет входной регистр блока отбора, 6.2..6.9 - блоки модулей сравнения,

на фигуре 7 приведен пример функционирования модуля отбора, где блок 7.1 - входной регистр модуля отбора, 7.2 - регистр хранения лучшего критерия, 7.3 - регистр адреса лучшей хромосомы, 7.4 - схема сравнения (компаратор отбора) модуля отбора,

на фигуре 8 приведен пример формирования элитной области, где 8.1 и 8.2 регистры,

на фигуре 9 приведен алгоритм вычисления вероятности,

на фигуре 10 приведен пример вычисления вероятности для бита 4,

на фигуре 11 приведен пример параллельного формирования вероятности, где блок 11.1 блок памяти, 11.2..11.33 - блоки сумматоров с накоплением,

на фигуре 12 приведена структурная схема устройства аппаратной реализации вероятностного генетического алгоритма UMDA, где блок 12.1 - блок инициализации, 12.2 - блок вычисления величины элитной области, 12.3 - блок генерации прерываний, 12.4 - блок микропрограммного управления, 12.5 - блок адресного указателя, 12.6 - блок генерации популяции, 12.7 - блок формирования разрядности хромосомы, 12.8 - блок мультиплексоров, 12.9 - блок памяти, 12.10 - блок вычисления критерия, 12.11 - блок отбора, 12.12 - блок формирования элитной области, 12.13 - блок вычисления вероятности; и содержит:

блок инициализации 12.1 вероятностного генетического алгоритма для инициализации вероятностного генетического алгоритма на этапе инициализации и регулирования параметрами в процессе функционирования;

блок формирования разрядности хромосомы 12.7 для установки количества используемых бит в хромосоме для предоставления возможности настраивать размер хромосомы на этапе инициализации и в процессе функционирования;

блок вычисления величины элитной области 12.2 для вычисления величины элитной области на этапе инициализации и в процессе функционирования;

блок генерации популяции 12.6 для генерации популяции посредством параллельной генерации бит хромосомы;

блок памяти 12.9 для хранения хромосом популяции и значений критериев для хромосом;

блок адресного указателя 12.5 для формирования адресов считывания или записи хромосом и критериев;

блок вычисления критерия 12.10 для вычисления значений критерия (функции пригодности) поступающих на вход блока хромосом;

блок отбора 12.11 для отбора адресов хромосом из популяции с лучшим значением критерия;

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

блок вычисления вероятности 12.13 вычисления вероятности нахождения единичных бит для каждой позиции бита в хромосоме на основе всех хромосом элитной области;

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

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

блок генерации прерываний 12.3 для генерации аппаратных прерываний во время функционирования устройства.

1. Устройство АВГА, заявленное выше, где вышеупомянутый блок инициализации вероятностного генетического алгоритма в дальнейшем содержит модуль настройки и инициализации генераторов случайной двоичной последовательности блока генерации популяции, модуль настройки и инициализации блока вычисления вероятности, модуль количества используемых бит в хромосоме, модуль количества итерационных циклов, модуль размера популяции и модуль значения коэффициента размера элитной области;

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

3. Устройство АВГА, заявленное выше, где вышеупомянутый блок вычисления величины элитной области производит вычисление величины элитной области как произведение значений размера популяции и коэффициента размера элитной области, содержащихся в модуле размера популяции и модуле значения коэффициента размера элитной области.

4. Устройство АВГА, заявленное выше, где вышеупомянутый блок генерации популяции выполняет параллельную генерацию бит хромосомы на основе сравнения значения, генерируемого на генераторе случайной двоичной последовательности и значения вероятности для данного бита хромосомы, результат сравнения сохраняется как значение бита хромосомы;

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

5. Устройство АВГА, заявленное выше, где вышеупомянутый блок памяти предназначен для:

формирования независимого пространства памяти для хранения популяции и критериев в одном адресном пространстве, где в дальнейшем включает память популяции и память критериев;

независимой записи и хранения хромосом и/или их критериев в соответствующее пространство памяти, с уникальным адресом для каждой хромосомы и соответствующему ей критерию;

независимой выдачи хромосомы и/или критерия по запросу с указанием адреса хромосомы и/или критерия;

формирования и одновременного хранения популяции и элитной области в рамках единого адресного пространства памяти популяции.

6. Устройство АВГА, заявленное выше, где вышеупомянутый блок адресного указателя выполняет независимое формирование адреса считывания или записи для хромосом и критериев в соответствующих режимах работы адресного указателя.

7. Устройство АВГА, заявленное выше, где вышеупомянутый блок вычисления критерия производит вычисление значения критерия (функции пригодности) для входных значений хромосом, на основе решения задачи one-max и устанавливает на выходе вычисленные значения и признак нахождения решения.

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

9. Устройство АВГА, заявленное выше, где вышеупомянутый блок формирования элитной области выполняет формирование элитной области, на основе отобранных хромосом из популяции с лучшим значением критерия, посредством перемещения отобранных хромосом в начальную область адресного пространства памяти популяции, в порядке убывания значения критерия;

10. Устройство АВГА, заявленное выше, где вышеупомянутый блок вычисления вероятности производит вычисление значения вероятности для каждого бита хромосомы на основе всех хромосом из вышеуказанной элитной области и модифицирует значения вероятностей, используемые в вышеуказанном блоке генерации популяции;

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

11. Устройство АВГА, заявленное выше, где вышеупомянутый блок мультиплексоров выполняет взаимодействие между вышеуказанными блоками: блоком генерации популяции, блоком вычисления критерия, блоком отбора, блоком формирования элитной области, блоком памяти, блоком адресного указателя и блоком генерации прерывания.

12. Устройство АВГА, заявленное выше, где вышеупомянутый блок микропрограммного управления в дальнейшем содержит модуль памяти микрокоманд управления для управления устройством АВГА и модуль памяти микрокоманд управления для управления блоком управления, производит управление работой устройства АВГА посредством генерации 32-битной команды управления, где каждый бит отвечает за управление работой соответствующего блока или модуля в зависимости от режима функционирования алгоритма;

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

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

14. Устройство АВГА, заявленное выше, где вышеупомянутый модуль настройки и инициализации блока вычисления вероятности выполняет инициализацию блока вычисления вероятности посредством установки значений вероятности для всех бит хромосомы в начальное значение;

модуль настройки и инициализации блока вычисления вероятности выполняет настройку значений вероятностей при увеличении количества используемых бит хромосомы в процессе функционирования устройства АВГА посредством установки значений вероятностей добавленных бит в начальное значение.

15. Устройство АВГА, заявленное в 8, где вышеупомянутый блок отбора содержит восемь модулей отбора, каждый из которых содержит компаратор, мультиплексор и регистры критерия и адреса, собранных в последовательность для сравнения, сохранения и пропускания входных значений критериев и соответствующих им адресов от одного модуля к другому.

16. Устройство АВГА, заявленное в 15, где вышеупомянутый модуль отбора сравнивает значение критерия, приходящее на вход модуля со значением критерия, содержащегося в регистре критерия данного модуля;

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

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

17. Устройство АВГА, заявленное в 10, где вышеупомянутое формирование элитной области выполняется посредством перемещения хромосом с лучшим значением критерия в начало адресного пространства памяти при параллельном сохранении размещенных по заменяемому адресу хромосом и критериев, в пространстве памяти, соответствующем адресу перемещаемых значений.

18. Устройство АВГА, заявленное в 14, где вышеупомянутый модуль генерации прерывания завершения формирования популяции генерирует прерывание при совпадении сгенерированного количества хромосом популяции со значением, установленном в вышеупомянутом модуле размера популяции.

19. Устройство АВГА, заявленное в 14, где вышеупомянутый модуль генерации прерывания завершения формирования элитной области генерирует прерывание при совпадении количества хромосом, перемещенных в элитную область со значением, хранящимся в вышеупомянутом блоке вычисления величины элитной области.

20. Устройство АВГА, заявленное в 14, где вышеупомянутый модуль генерации прерывания выполнения заданного количества итерационных циклов генерирует прерывание при совпадении количества выполненных итерационных циклов со значением, хранящимся в вышеупомянутом модуле количества итерационных циклов.

21. Устройство АВГА, заявленное в 14, где вышеупомянутый модуль признака завершения функционирования алгоритма генерирует прерывание завершения функционирования алгоритма при получении признака нахождения решения из вышеупомянутого блока вычисления критерия.

22. Устройство АВГА, заявленное в 13, где вышеупомянутые режимы функционирования алгоритма соответствуют специфике функционирования устройства АВГА и включают режим инициализации устройства АВГА, режим инициализации итерационного цикла, режим генерации популяции, режим отбора, режим формирования элитной области и режим завершения функционирования.

23. Устройство АВГА, заявленное в 13, где вышеупомянутый модуль памяти микрокоманд управления содержит микрокоманды обработчика режима инициализации устройства АВГА, обработчика режима инициализации итерационного цикла, обработчика режима генерации популяции, обработчика режима инициализации обработчика отбора и формирования элитной области, обработчика прерывания завершения формирования популяции, обработчика прерывания завершения формирования элитной области, обработчика прерывания выполнения заданного количества итерационных циклов, обработчика прерывания завершения функционирования алгоритма.

24. Устройство АВГА, заявленное в 23, где вышеупомянутая специфика функционирования устройства соответствует принципу функционирования вероятностного генетического алгоритма UMDA (Н.Mühlenbein. The Equation for Response to Selection and its Use for Prediction. Evolutionary Computation, May 1998, pp.303-346) с внесенными изменениями в принцип функционирования алгоритма UMDA.

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

26. Устройство АВГА, заявленное в 25, где вышеупомянутые изменения в принципе функционирования алгоритма UMDA содержат принципы организации параллельной и многоуровневой конвейерной обработки информации и поддержку динамических изменений параметров функционирования устройства АВГА.

27. Устройство АВГА, заявленное в 27, где вышеупомянутые принципы организации параллельной обработки информации включают параллельную организацию блока генерации популяции, где генерация всех бит хромосомы выполняется параллельно за один машинный такт, параллельную организацию блока вычисления критерия, где выполняется вычисление значения критерия на основе всех бит хромосомы, параллельную организацию блока отбора, позволяющего выполнять отбор лучших значений одновременно для восьми различных значений, параллельную организацию блока вычисления вероятности, где значения вероятности вычисляются одновременно для всех бит хромосомы, посредством выполнения операции суммирования с накоплением.

28. Устройство АВГА, заявленное в 27, где вышеупомянутые принципы организации многоуровневой конвейерной обработки информации включают организацию внутриблочной и межблочной конвейерной обработки, где внутриблочная конвейерная обработка выполняется в вышеупомянутом блоке вычисления критерия и блоке отбора, межблочная конвейерная обработка обуславливает основные характеристики функционирования устройства АВГА.

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

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

31. Устройство АВГА, заявленное в 1, где заявленный блок инициализации вероятностного генетического алгоритма, блок установки количества используемых бит в хромосоме, блок вычисления величины элитной области, блок генерации популяции, блок памяти, блок адресного указателя, блок вычисления критерия, блок отбора, блок формирования элитной области, блок вычисления вероятности, блок мультиплексоров, блок генерации прерываний функционируют синхронно, с общим машинным циклом.

32. Метод для изготовления устройства АВГА, заключает в себе этап выполнения аппаратной памяти популяции, памяти критериев, блока инициализации вероятностного генетического алгоритма, блока формирования разрядности хромосомы, блока вычисления величины элитной области, блока генерации популяции, блока адресного указателя, блока вычисления критерия, блока отбора, блока формирования элитной области, блока вычисления вероятности, блока мультиплексоров, блока генерации прерываний и блока микропрограммного управления, которые спроектированы, чтобы выполнить вероятностный генетический алгоритм UMDA.

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

УСТРОЙСТВО АВГА реализует алгоритм генерации популяции, приведенный на фигуре 1, посредством блока генерации популяции 12.6, генерирующего популяцию посредством последовательной генерации хромосом генераторами псевдослучайной двоичной последовательности реализованным, согласно фигуре 2, объединенных в параллельную структуру, показанную на фигуре 3, передающего сгенерированную хромосому блоку вычисления критерия 12.10, алгоритм функционирования которого приведен на фигуре 4, вычисляющего значение критерия отбора (решение задачи one-max) для каждой хромосомы популяции посредством реализации схемы, приведенной на фигуре 5, содержащей первый (5.1-5.23) и второй (5.24-5.30) уровни, передающую вычисленное значение критерия блоку отбора 12.11, приведенного на фигуре 6, реализующего оператор отбора, производящего отбор хромосом с лучшим значением критерия посредством модулей отбора, приведенных на фигуре 7, и передающим данные хромосомы блоку формирования элитной области 12.12, реализующим стратегию элитизма, при формировании элитной области в памяти популяции согласно фигуре 8 и передающему отобранные хромосомы блоку вычисления вероятности 12.13, алгоритм работы которого приведен на фигуре 9, поясняется фигурой 10 и реализуется структурой, приведенной на фигуре 11, передающей вычисленные значения вероятностей блоку генерации популяции 12.6, что в совокупности объединяется в приведенную на фигуре 12 структурную схему устройства аппаратной реализации вероятностного генетического алгоритма UMDA.

Работает устройство следующим образом: при установке высокого уровня сигнала выбора устройства CsEn, производится переход устройства АВГА в активный режим ожидания. В данном режиме устройство АВГА находится до поступления сигнала синхронизации CLK. При поступлении сигнала синхронизации в блоке микропрограммного управления 12.4 производится считывание микрокоманд управления, настраивающих блок микропрограммного управления на отработку режима инициализации, и микрокоманд управления устройством АВГА, производящих инициализацию всех остальных блоков. Результатом режима инициализации является формирование разрядности хромосомы блоком 12.7 в соответствии со значением сигнал выбора разрядности хромосомы WidhtCh; настройка блока генерации популяции 12.6 на генерацию хромосом с заданной разрядностью и установка генераторов случайной последовательности в начальное состояние, в соответствии со значением режима начальной установки для блока генерации популяции (определяется входные сигналом EnRnd); настройка соответствующих мультиплексоров блока мультиплексоров 12.8 на режим адресации блока памяти с блока адресного указателя 12.5 и установки входного значения для блока памяти 12.9 и блока вычисления критерия 12.10 непосредственно с блока генерации популяции 12.6, установки входного значения для памяти критериев непосредственно с блока вычисления критерия 12.10 и параллельной установки данного значения и адреса записи критерия на вход внутренних входных регистров блока отбора 12.11; блок памяти 12.9 переводится в режим записи; блок вычисления вероятности 12.13 устанавливает все значения вероятностей для используемых бит хромосомы в начальное значение, равное 0,5; блок вычисления критерия 12.10 настраивается на вычисление значения критерия для заданного количества бит в хромосоме; в блоке отбора 12.11 выполняется сброс всех внутренних регистров; блок вычисления величины элитной области вычисляет значение величины элитной области посредством перемножения размера популяции popsize и параметра tau; блок инициализации 12.1 подготавливает значения величины популяции и элитной области для блоков генерации прерываний 12.3, непосредственно для модулей величины популяции и элитной области путем декремента значений величины популяции и элитной области, а также выполняет установку адресного указателя 12.5 в нулевое состояние.

После завершения вычисления значения величины элитной области в блоке 12.2 выполняется переход к этапу генерации популяции. Алгоритм генерации популяции приведен на фигуре 1. Переход к этапу генерации популяции производится посредством отработки блоком микропрограммного управления 12.4 обработчика этапа инициализации и перехода к обработчику этапа генерации популяции.

Этап генерации популяции включает параллельное функционирование блоков микропрограммного управления 12.4, генерации популяции 12.6, адресного указателя 12.5, памяти 12.9, вычисления критерия 12.10 и отбора 12.11. Этап генерации популяции разбивается на два подэтапа, где на первом выполняется наполнение конвейера (инициализация этапа), на втором - работа в режиме полного конвейера. Наполнение конвейера включает в себя 4 машинных такта.

На первом такте, по переднему фронту, в блоке генерации популяции 12.6 выполняется генерация случайной двоичной последовательности на генераторах случайного числа 3.1_1..3.1_32 (на фигуре 2 приведена схема генератора псевдослучайной двоичной последовательности), по заднему фронту выполняется сравнение сгенерированных значений на схемах сравнения 3.3_1..3.3_32 и формирование хромосомы Chromosome. Т.е. на первом такте блок генерации популяции генерирует хромосому, которая через блок мультиплексоров 12.8 поступает на вход данных памяти популяции и блока вычисления критерия 12.10. Алгоритм функционирования блока вычисления приведен на фигуре 4. По переднему фронту первого такта блок адресного указателя 12.5 устанавливает нулевой адрес хромосомы и критерия, которые через блок мультиплексоров поступают на соответствующие адресные входы памяти популяции и памяти критериев, образующих блок памяти 12.9. Значение адреса хромосомы подается также на вход блока генерации прерывания 12.3 на блок генерации прерывания величины популяции.

Значения адреса записи и хромосомы должны оставаться неизменны в момент записи хромосомы в память популяции, поэтому на втором такте блок адресного указателя 12.5 и генерации популяции 12.6 находятся в режиме ожидания, удерживая на выходах адрес записи хромосомы и значение хромосомы. По переднему фронту второго синхроимпульса производится запись значения хромосомы в память популяции согласно установленному адресу записи хромосомы и запись хромосомы в блок вычисления критерия 12.10. (Вычисление значения критерия производится согласно алгоритму, приведенному на фигуре 4, функционально блок вычисления критерия является комбинационной схемой и позволяет выполнять вычисления одновременно для двух значений). По заднему фронту второго такта в блоке генерации прерывания величины популяции выполняется сравнение значений величины популяции и адреса хромосомы, поступившего на вход блока генерации прерываний 12.3 с блока адресного указателя. Если установленный в блоке инициализации 12.1 размер популяции и адрес хромосомы совпадают, то формируется прерывание формирования популяции и блок микропрограммного управления переходит на этап формирования элитной области. Иначе продолжается функционирование этапа генерации популяции.

На третьем такте этапа генерации популяции выполняется генерация новой хромосомы в блоке генерации популяции 12.6 и инкремент адреса хромосомы в блоке адресного указателя 12.5. По заднему фронту, на адресном входе памяти популяции устанавливается новое значение адреса записи очередной хромосомы и на входе данных памяти популяции и блока вычисления критерия 12.10 устанавливается значение очередной хромосомы.

По переднему фронту четвертого такта выполняется запись второй хромосомы в память популяции и в блок вычисления критерия, который входит в режим наполнения конвейера и выполняет вычисление значения критерия одновременно для двух хромосом: для первой хромосомы на втором уровне, образованного элементами 5.24.. 5.30, и второй хромосомы на первом уровне, образованного элементами 5.1..5.23. По окончании четвертого такта в блоке популяции находятся две хромосомы, и на выходе блока вычисления критерия устанавливается значение критерия для первой хромосомы, сохраненной в памяти популяции по нулевому адресу. На данном такте аналогично такту два выполняется сравнение вычисленного в блоке инициализации 12.1 значения размера популяции и значения адреса хромосомы, полученного с блока адресного указателя 12.5.

В режиме полного конвейера выполняется та же последовательность действий, что и в режиме наполнения конвейера для тактов 3 и 4 с некоторыми дополнениями.

На первом такте, кроме генерации новой хромосомы и инкремента адреса хромосомы, по переднему фронту первого такта выполняется сохранение значения критерия, сформированного блоком вычисления критерия 12.10, посредством передачи значения критерия через блок мультиплексоров 12.8, во входном регистре 6.1 блока отбора 12.11 и в буферном регистре, устанавливающем значение на вход памяти критериев.

По заднему фронту первого такта в блоке отбора 12.11 выполняется сравнение значения входного регистра 7.1 со значением внутреннего регистра лучшего критерия 7.2. Сравнение выполняется одновременно во всех модулях сравнения 6.2-6.9, образующих блок отбора.

По переднему фронту второго такта выполняются действия, описанные для этапа наполнения конвейера для четвертого такта, а также запись в память критериев значения критерия из буферного регистра для хромосомы, записанной в памяти популяции по нулевому адресу. Выбор в модулях сравнения 6.2-6.9 значений адреса и критерия, соответственно сигналу выбора, полученного со схемы сравнения 7.4, для передачи последующему модулю сравнения.

По заднему фронту второго такта выполняется сохранение значений, поступающих на вход внутренних регистров адреса 7.3 и регистров лучшего критерия 7.2 в модулях сравнения блока отбора. Т.о. в случае наличия единичного уровня на сигнале выбора будет выполнена передача значений внутренних регистров последующему модулю и перезапись данных регистров, значениями, установленными на входе данного модуля, иначе следующему модулю передаются значения, установленные на входе. Выполняется инкремент значения указателя адреса критерия в блоке адресного указателя.

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

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

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

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

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

При переходе к этапу формирования элитной области выполняется передача адреса хромосомы, сохраненного в регистре адреса 7.3 первого модуля блока отбора, блоку формирования элитной области. Выполняется сброс блока адресного указателя 12.5 и блока вычисления критерия 12.10 в нулевые состояния. В блоке микропрограммного управления 12.4 во внутренний счетчик генерации внутреннего прерывания количества циклов устанавливается значение 8. Память популяции и память критериев переводится в режим чтения.

По переднему фронту первого такта этапа формирования элитной области формируется сигнал чтения, одинаковый для памяти популяции и памяти критериев, т.е. выполняется чтение значения хромосомы и критерия из памяти популяции и критериев, расположенных по нулевому адресу. Поступает сигнал тактирования блока отбора 12.11, при этом на вход в качестве адреса хромосомы и значения критерия поступают нулевые значения, установленные на блок адресного указателя 12.5 (с счетчика элитных хромосом посредством блока мультиплексоров) и блоке вычисления критерия 12.10 соответственно.

По переднему фронту второго такта выполняется установка адреса хромосомы, полученного от блока формирования элитной области 12.12, на адресный вход блока памяти 12.9 для памяти популяции и критериев.

По заднему фронту второго такта выполняется сохранение значений хромосомы и критерия, установленных на выходе памяти популяции и памяти критериев, в регистре 8.2 посредством блока мультиплексоров 12.8.

По переднему фронту третьего такта выполняется чтение элитного значения хромосомы и критерия из памяти популяции и критериев (ячейка памяти с адресом S1).

По переднему фронту четвертого такта память популяции и память критериев переводится в режим записи, значения хромосомы критерия, установленные на выходных портах блоков памяти популяции и критериев сохраняются в регистре 8.1 посредством блока мультиплексоров 12.8. Блок мультиплексоров 12.8 устанавливает на вход памяти популяции и памяти критериев значения хромосомы и критерия, сохраненные в регистр 8.2. Блок мультиплексоров 12.8 устанавливает на вход адреса памяти популяции и памяти критериев адрес с блока адресного указателя. Поступает сигнал тактирования блока отбора 12.11.

По переднему фронту пятого такта выполняется запись хромосомы и критерия из регистра 8.2 в память популяции и память критериев по адресу S1.

Значение хромосомы из регистра 8.1, посредством блока мультиплексоров 12.8, поступает на вход блока вычисления вероятности. Алгоритм функционирования блока вычисления вероятности приведен на фигуре 9. На фигуре 3 приведен пример вычисления вероятности для бита 4.

По переднему фронту шестого такта блок мультиплексоров 12.8 устанавливает на вход памяти популяции и памяти критериев адрес, установленный на блок адресного указателя 12.5, и значения хромосомы и критерия, сохраненные в регистре 8.1. Выполняется передача адреса хромосомы S2, сохраненного в регистре адреса 7.3 второго модуля 6.3 блока отбора 12.11, блоку формирования элитной области 12.12. Для второго и последующих адресов S блок формирования элитной области 12.12 выполняет проверку поступившего адреса хромосомы. Проверка необходима для устранения ошибки перемещения, связанной с адресацией (указанием) на хромосомы, перемещенные в предшествующих шагах в процессе формирования элитной области, т.е. действительный адрес расположения которых был изменен. Подается сигнал тактирования блока вычисления вероятности, по которому значение элитной хромосомы поступает на вход сумматоров с накоплением 11.2..11.33 блока вычисления вероятности. Величина подсуммирования устанавливается на выходе памяти 11.1. На вход памяти поступает значение величины элитной области, на выходе устанавливается шестнадцатиразрядное значение величины, обратной к размеру элитной области.

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

Подается сигнал тактирования блока вычисления вероятности.

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

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

На этапе завершения формирования элитной области выполняется завершение функционирования блоков формирования элитной области, отбора и вычисления вероятности, при этом вычисленные значения вероятности поступают на блок генерации популяции. Производится инкремент счетчика итерационных циклов и сравнение значения счетчика итерационных циклов и значения, установленного на модуле количества итерационных циклов, который получает значение с входа nCircle. Если значения совпадают, блок генерации прерывания количества итерационных циклов формирует прерывание завершения функционирования и выполняется переход на этап завершения функционирования алгоритма. Иначе выполняется переход на этап инициализации.

На этапе завершения функционирования алгоритма на выходном порту (End) устройства устанавливается высокий уровень сигнала завершения функционирования и при поступлении на вход устройства сигнала разрешения чтения значений элитных хромосом Read, с каждым четным тактом сигнала синхронизации производится последовательный вывод значений элитных хромосом из элитной области на выходной порт устройства (Output).

Заявляемое устройство позволяет добиться максимальной оптимизации, с позиции времени функционирования алгоритма; добиться оптимизации с позиции требуемых аппаратных ресурсов; применять алгоритм в автономных системах; использовать алгоритм UMDA в системах реального времени, исследованиях при проектировании "виртуальных аппаратных средств" (Virtual Hardware), "искусственной жизни" (Artificial Life) и "самоадаптирующихся и реконфигурируемых аппаратных средств" (Self-Adapting and Reconfigurable Hardware), исследованиях в области построения адаптивных систем управления и принятия решений, в области автоматизации управления, повышения эффективности оптимизационных задач и т.п.;

Заявляемое устройство обладает следующими характеристиками:

- совокупность существенных признаков объекта (качественные оценки технико-экономических преимуществ): скорость обработки, эффективность, производительность, универсальность.

- ожидаемый положительный эффект от использования изобретения: повышение скорости нахождения оптимального решения, расширение области применения данного вероятностного генетического алгоритма.

- необходимые конструктивные признаки объекта, определяемые особенностью реализации алгоритма: параллельная 32-блочная система с аппаратной поддержкой интерактивных изменений в параметрах функционирования.

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

Основные временные характеристики устройства аппаратной реализации вероятностного генетического алгоритма UMDA.

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

- инициализация всех необходимых параметров - 176 нс.

- генерация популяции на 256 особей при параллельном вычислении критерия и функционировании блока отбора - 6.176 мкс.

- формирование 8 элементов элитной области и параллельного вычисления вероятностей - 540 нс.

- чтение из памяти 120 значений критериев с параллельным выполнением отбора адресов элитных хромосом - 2,88 мкс.

- чтение из памяти 8 значений критериев с параллельным выполнением отбора адресов элитных хромосом без этапа инициализации - 192 нс.

- время одного итерационного цикла вероятностного генетического алгоритма (популяция = 256, элитная область = 128, разрядность хромосомы от 1 до 32 бит) составляет 8,409 микросекунды.

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

- производитель ПЛИС (FPGA): Altera

- семейство: АСЕХ1К

- тип кристалла: EP1K100FC256-1

- максимальная частота функционирования устройства АВГА: 125 МГц

- необходимое количество логических ячеек - 3017

- необходимый объем внутренней памяти - 26.312 bit.

В таблице 1 приведены временные характеристики аппаратно- и программно-реализованного алгоритма UMDA. В таблице 2 общее повышение быстродействия в сравнении с прототипом.

Таблица 1. Временные характеристики аппаратно- и программно-реализованного алгоритма UMDA
Основные параметры функционирования			Аппаратная реализация *		Программная реализация
Тактовая частота			125 МГц		540 МГц (Р3)
Инициализация алгоритма:			176 н.с.
Генерация одной хромосомы (32 бита)			24 н.с.		0,7135·10-3 сек
Генерация популяции на 256 особей (при параллельном вычислении критерия и выполнении отбора*)			6,176·10-6 сек		1,8267·10-1 сек
Формирование 8 лучших элементов элитной области в порядке убывания			3,072·10-6 сек		2,9392·10 -1 сек
Формирование 128 элементов элитной области при параллельном вычислении значений вероятности			7,78·10 -5 сек		4,7027 сек
Время 1-го итерационного цикла			8,409·10-5 сек		22,983 сек
* - при программной реализации значение измерено только для оператора генерации популяции.
Таблица 2. Общее повышение быстродействия. Сравнение с прототипом.
Univariate Marginal Distributiona Algorithm (UMDA)				Compact Genetic Algorithm
Программная реализация 540 МГц, Р3	Аппаратная реализация 125 МГц FPGA	Увеличение быстродействия		Программная реализация 200 МГц, Ultra Sparc 2		Аппаратная реализация 20 МГц FPGA	Увеличение быстродействия
23 сек	84 мксек	27,380		2:30 min		0.15 сек	1,000