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

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

Иллюстрации

Показать все

Реферат

Предлагаемое устройство относится к аппаратным системам, реализующим вероятностные генетические алгоритмы, используемые в эволюционных инструментальных комплексах, исследованиях при проектировании виртуальных аппаратных средств (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, где заявленный блок инициализации вероятностного генетического алгоритма, блок установки количества используемых бит в хромосоме, блок вычисления величины элитной области, блок генерации попул