устройство аппаратной реализации эволюционного алгоритма с нечеткими операторами

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Из известных технических решений наиболее близким по технической сущности к заявляемому объекту является RU 2005108760 10.09.2006 G06N 3/12 «Устройство аппаратной реализации вероятностных генетических алгоритмов с параллельным формированием хромосомы».

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

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

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

блок микропрограммного управления;

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

блок мультиплексоров;

блок инициализации.

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

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

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

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

на фигуре 1 приведена структурная схема аппаратно-реализованного генетического алгоритма с нечеткими операторами,

на фигуре 2 приведена принципиальная схема блока мутации,

на фигуре 3 приведена принципиальная схема блока инверсии,

на фигуре 4 приведена принципиальная схема блока кроссинговера,

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

на фигуре 6 приведена структурная схема нечетких генетических операторов,

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

на фигуре 8 приведена принципиальная схема блока Trin,

на фигуре 9 приведены функции принадлежности, реализуемые блоками Trin и Trap,

на фигуре 10 приведена принципиальная схема блока Trap.

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

Блок памяти предназначен для:

- формирования независимого пространства памяти для хранения популяции и критериев в одном адресном пространстве;

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

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

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

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

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

Блок мутации выполняет изменение одного гена хромосомы. Номер гена выбирается нечетким контроллером.

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

Блок кроссинговера выполняет деления двух хромосом на части и осуществляет обмен. В результате на выходе получается две новые хромосомы.

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

Принципиальная схема 32-разрядного генератора псевдослучайных чисел содержит сдвиговый регистр, два элемента «Исключающее ИЛИ» и элемент НЕ.

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

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

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

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

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

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

Контроллер создан с использованием языка проектирования цифровых устройств VHDL и схемотехнического редактора Quartus II.

Блоки Trin и Trap образуют фуззификатор, который преобразует N-мерный входной вектор x=[x₁,x₂, ,x_N] в нечеткое множество А, характеризуемое функцией принадлежности µ_A(x) с четкими переменными.

Блок Trin реализует треугольную функцию принадлежности. На входы а_1, b_1 и а_2, b_2 подаются значения а и b уравнений прямых (y=ax+b)a1-b и b-a2, которые образуют функцию принадлежности.

Блок Trap реализует трапецеидальную функцию принадлежности.

Изменяя значения входов а_1, b_1 и а_2, b_2 блоков Trin и Trap, можно изменять параметры функций принадлежности во время работы контроллера.

Блок дефуззификатора Defuz трансформирует нечеткое множество в детерминированное значение y в форме выбора максимального из максимальных значений y.

Работает устройство следующим образом: при установке высокого уровня сигнала выбора устройства CsEn производится переход устройства в активный режим ожидания. В данном режиме устройство находится до поступления сигнала синхронизации CLK. При поступлении сигнала синхронизации в блоке микропрограммного управления 1.3 производится считывание микрокоманд управления, настраивающих блок микропрограммного управления на отработке режима инициализации, и микрокоманд управления устройством, производящих инициализацию всех остальных блоков. Результатом режима инициализации является формирование разрядности хромосомы блоком 1.6 в соответствии со значением сигнал выбора разрядности хромосомы; настройка блока генерации популяции 1.5 на генерацию хромосом с заданной разрядностью и установка генераторов случайной последовательности в начальное состояние, в соответствии со значением режима начальной установки для блока генерации популяции; настройка соответствующих мультиплексоров блока мультиплексоров 1.9 на режим адресации блока памяти с блока адресного указателя 1.4 и установки входного значения для блока памяти 1.11 и блока вычисления критерия 1.10 непосредственно с блока генерации популяции 1.5, установки входного значения для памяти критериев непосредственно с блока вычисления критерия 1.10 и параллельной установки данного значения и адреса записи критерия на вход внутренних входных регистров блока отбора 1.12; блок памяти 1.11 переводится в режим записи; блок вычисления критерия 1.10 настраивается на вычисление значения критерия для заданного количества бит в хромосоме: в блоке отбора 1.12 выполняется сброс всех внутренних регистров.

Этап генерации популяции включает параллельное функционирование блоков микропрограммного управления 1.3, генерации популяции 1.5, адресного указателя 1.4, памяти 1.11, вычисления критерия 1.10.

После завершения этапа генерации популяции из блока памяти 1.11 выбираются две хромосомы и поступают на вход блока кроссинговера 1.7. В состав блока кроссинговера включен нечеткий контроллер, предназначенный для нечеткого выбора точек разрыва хромосомы. Контроллер построен по классической системе нечеткого вывода Мамдани-Заде.

В блоке мутации и инверсии также в состав включен нечеткий контроллер.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- семейство: Arria GX

- тип кристалла: EP1AGX50

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

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

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