Система поиска управляющих факторов на основе когнитивной модели и генетического алгоритма

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

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

Известно устройство, содержащее элемент И, два счетчика, блок хранения векторов, два блока алгебраического суммирования, четыре регистра, блок сравнения с допуском, коммутатор, блок памяти, два элемента задержки, элемент ИЛИ [SU 1809436, G06F 7/4, 1991].

Недостатком устройства является относительно узкие функциональные возможности.

Известно также устройство, содержащее регистр, группу регистров и генератор тактовых импульсов, выход которого соединен с синхровыходами регистров группы, счетчик, блок выделения минимума, блок выделения максимума, два умножителя, два сумматора, блок деления, блок сравнения, коммутатор, блок памяти максимального сигнала и выходной регистр, причем выходы регистров группы соединены с соответствующими входами блоков выделения минимума, выделения максимума и первого сумматора, выход которого соединен с входом задания коэффициента значимости средних результатов устройства, а выход подключен к управляющему входу коммутатора, выход которого соединен с первым информационным входом регистра, синхровход которого соединен с выходом генератора тактовых импульсов и счетным входом счетчика, выход переполнения которого соединен с входом останова генератора тактовых импульсов и синхровходом выходного регистра, выход которого является выходом устройства, а информационный вход соединен с выходом блока максимального сигнала, информационные входы которого соединены с выходами регистра, второй информационный вход которого соединен с выходами разрядов счетчика, выходы блоков выделения минимума и максимума соединены с первыми входами соответственно первого и второго умножителей, вторые входы которых соединены с входами соответствующих коэффициентов устройства, а выходы соединены с входами второго сумматора, выход которого соединен с первым информационным входом коммутатора, второй информационный вход которого является входом постоянной малой величины устройства [SU 1833886 A1, G06F 7/4, 1991].

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

Кроме того, известно устройство, содержащее регистр, группу регистров, генератор тактовых импульсов, счетчик, два умножителя, компаратор, вторая группа регистров, блок умножения импульсов, два блока вычитания, блок умножения на 0 и интегратор, причем, выходы групп регистров соединены с первым и вторым входами первого умножителя, третий вход которого является входом соответствующего коэффициента 1-, характеризующего отношение лица, принимающего решение (ЛПР), к риску, на первый вход компаратора поступает с выхода второй группы регистров величина V_j, характеризующая субъективную ценность исходов, второй вход является входом значения L_p, характеризующего уровень притязаний, соответствующий наименьшему значению полезности, при которой исход удовлетворит ЛПР, выходы компаратора соединены с входами первого блока вычитания, в котором вычисляется величина L_p-V_j, и блока умножения на 0, выходы которых, в свою очередь, соединены с двумя входами второго умножителя, третий вход которого является входом значения 1- устройства, а выход соединен с третьим входом второго блока вычитания, первый и второй входы которого соединены с выходами первого умножителя, выход второго блока вычитания соединен с входом интегратора, а выход интегратора - с входом регистра, выполненного как регистр сдвига, второй вход интегратора соединен с выходом генератора тактовых импульсов через блок умножения импульсов, выходы которого соединены также с входами первой и второй групп регистров, второй выход генератора тактовых импульсов соединен со счетным входом счетчика, выход переполнения которого соединен с входом останова генератора тактовых импульсов и с входом регистра [RU 2214624 С2, G06F 17/00, G06N 7/06, 20.10.2003].

Недостатком и этого устройства является относительно узкие функциональные возможности.

Наиболее близким по технической сущности к предлагаемому является устройство, содержащее блок выделения фрагментов изображения, блок формирования опорного плана поиска, формирователь особи-потомка, первый, второй и третий входы которого соединены, соответственно, с первым, вторым и третьим выходами блока формирования опорного плана поиска, а группа входов - объединена с группой входов блока формирования опорного плана поиска и соединена с группой выходов блока выделения фрагментов изображения, блок определения максимума, первый, второй и третий входы которого соединены, соответственно, с первым, вторым и третьим выходами формирователя особи-потомка, а также формирователь родительской пары, первый и второй выходы которого соединены, соответственно, с первым и вторым входами блока формирования опорного плана поиска, и формирователь рекомбинации, первый и второй входы которого соединены, соответственно с первым и вторым выходами формирователя родительской пары, а выход - соединен с третьим входом блока формирования опорного плана поиска [RU 60757 U1, G06F 19/00, 27.01.2007].

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

Требуемый технический результат заключается в расширении функциональных возможностей.

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

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

Система поиска управляющих факторов на основе когнитивной модели и генетического алгоритма содержит блок 1 формирования опорного плана поиска, формирователь 2 родительской пары и формирователь 3 особи-потомка.

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

Кроме того, система поиска управляющих факторов на основе когнитивной модели и генетического алгоритма содержит блок 7 формирования объектной функции, вход которого соединен с выходом блока 6 формирования целевых факторов, а выход - соединен со входом формирователя 2 родительской пары, выход которого соединен со входом формирователя 3 особи-потомка, выход которого соединен со входом блока 1 формирования опорного плана поиска.

Дополнительно к указанному система поиска управляющих факторов на основе когнитивной модели и генетического алгоритма содержит регистр 8 задания степени влияния управляющих факторов на промежуточные факторы, выход которого соединен со вторым входом блока 4 формирования значений промежуточных факторов, регистр 9 задания степени взаимовлияния промежуточных факторов, выход которого соединен со вторым входом блока 5 коррекции значений промежуточных факторов, регистр задания степени влияния промежуточных факторов на целевые факторы, выход которого соединен со вторым входом блока 6 формирования целевых факторов, и решающий блок 11, вход которого соединен с выходом блока 7 формирования объектной функции.

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

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

Предварительно произведем теоретическое описание работы предложенной системы.

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

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

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

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

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

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

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

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

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

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

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

Условием остановки генетического алгоритма является возникновение одной из следующих ситуаций:

- генетический алгоритм выполнил заданное число шагов (каждый шаг соответствует одному поколению);

- объектная функция достигла заданного значения;

- нет существенного изменения значений объектной функции в течение нескольких поколений.

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

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

Начальная популяция Р° есть набор равномерно распределенных в пространстве кодирования элементов. В случае двоичного кодирования это набор разных двоичных строк длинны l. Размер популяции µ есть число индивидуумов (хромосом), входящих в популяцию.

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

Оператор селекции (Selection) является вероятностной операцией, определенной для воспроизведения большего числа хромосом с высоким значением объектной функции в следующем поколении. В некоторых версиях генетических алгоритмов оператор селекции выбирает набор хромосом в промежуточную популяцию, к которой в дальнейшем могут быть применены операции скрещивания и мутации. Оператор селекции работает по принципу «Рулетки Монте-Карло», когда индивидуумам с большим значением объектной функции выделяется больший сектор рулетки. Таким образом, после вращения рулетки вероятность выбора индивидуумов с большим значением объектной функции выше.

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

Операция скрещивания (на примере бинарного кодирования В^l) выполняется следующим образом:

1. Выбрать два индивидуума из промежуточной популяции.

2. Сгенерировать равномерно распределенное случайное число из интервала [0, 1], и если полученное число меньше р ^Г, выполнить операцию скрещивания, если нет, перейти к шагу 5.

3. Сгенерировать точку скрещивания (crossover point), равномерно распределенное случайное число из интервала [0, l].

4. Поменять местами части выбранных индивидуумов, правее точки скрещивания.

5. Поместить выбранные хромосомы в новую популяцию.

6. Повторить шаги 1-5 до заполнения новой популяции.

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

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

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

Алгоритм мутации заключается в выполнении нескольких шагов:

1. Выбрать случайным образом индивидуума из промежуточной популяции

2. Сгенерировать равномерно распределенное случайное число из интервала [0 1], и если полученное число меньше р выполнить операцию мутации. В противном случае перейти к шагу 5

3. Сгенерировать точку мутации (mutation point), равномерно распределенное случайное число из интервала [0 l]

4. Инвертировать бит, находящийся в точке мутации

5. Поместить выбранную хромосому в новую популяцию

6. Повторить шаги 1-5 до заполнения популяции

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

Предварительно в блок 1 формирования опорного плана поиска записывается массив значений управляющих факторов Х=(х1, х2хn), например, массив равномерно распределенных точек в многофакторном пространстве.

При моделировании реальной системы, для которой требуется найти наилучшее решение в виде некоторого наилучшего сочетания значений управляющих факторов, определяются и записываются в регистр 8 значения весовых коэффициентов Kij, показывающих вклад значения i-ого управляющего фактора в значение j-ого промежуточного фактора, в регистр 9 - значения весовых коэффициентов Cij, показывающих вклад значения i-ого промежуточного фактора в значение j-ого промежуточного фактора, а в регистр 10 - значение весовых коэффициентов Rij, показывающих вклад значения i-ого промежуточного фактора в значение j-ого целевого фактора.

В процессе работы системы в блоке 4 формирования значений промежуточных факторов формируются значения промежуточных факторов y1, y2ym, которые определяются, например, линейным преобразованием управляющих факторов х1, х2хn с использованием соответствующих весовых коэффициентов Kij. Сформированные значения промежуточных факторов y1, y2ym в блоке 5 коррекции преобразуются в откорректированные значения промежуточных факторов y1корр. y2коррymкорр, которые определяются, например, линейным преобразованием промежуточных факторов y1, y2ym с использованием соответствующих весовых коэффициентов Cij. И, наконец, в блоке 6 формирования целевых факторов вычисляются значения целевых факторов z1, z2 zf, которые также определяются, например, линейным преобразованием откорректированных значений промежуточных факторов y1корр, y2коррymкорр с использованием соответствующих весовых коэффициентов Rij.

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

Формируемые в блоке 6 целевые факторы суммируются (напрямую или взвешенно) в блоке 7, в результате чего формируется объектная функция F, которая является критерием, определяющим качество соответствующего индивидуума. Обычно объектная функция является откликом некоторой внешней функции или динамической системы на параметры, закодированные в данной хромосоме.

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

В формирователе 2 реализуется операция селекции , в результате которой выбирается пара хромосом в промежуточную популяцию, к которой в дальнейшем могут быть применены операции скрещивания и мутации. Оператор селекции работает по принципу «Рулетки Монте-Карло», когда индивидуумам с большим значением объектной функции выделяется больший сектор рулетки. Таким образом, после вращения рулетки, вероятность выбора индивидуумов с большим значением объектной функции выше. Размеры секторов рулетки пропорциональны значениям объектных функций во всем множестве значений объектных функций.

Два сформированных двух индивидуумов в виде двух точек из массива равномерно распределенных точек в многофакторном пространстве управляющих факторов, определяющих вначале опорный план поиска, в формирователе 3 особи-потомка определяется точка в многофакторном пространстве управляющих факторов.

Для этого формирователь 3 работает по следующему алгоритму:

1. Зафиксировать двух индивидуумов - две точки из массива равномерно распределенных точек в многофакторном пространстве, которые определены формирователем 2.

2. Сгенерировать точку скрещивания (crossover point) индивидуумов, как равномерно распределенное случайное число из интервала [0, l].

3. Поменять местами части выбранных индивидуумов правее точки скрещивания.

Сформированная особь-потомок заносится из формирователя 3 в блок 1, что изменяет опорный план поиска на текущий план поиска, в котором, по сравнению с предыдущим, добавляется очередная точка.

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

- генетический алгоритм выполнил заданное число шагов (каждый шаг соответствует одному поколению);

- объектная функция достигла заданного значения;

- нет существенного изменения значений объектной функции в течение нескольких поколений.

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

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

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