Разработка декодеров искусственной иммунной системы, восприимчивых к нечетким командам

Чернышев Юрий Олегович доктор технических наук профессор, Донской государственный технический университет 344000, Россия, Ростовская область, г. Ростов-на-Дону, площадь Гагарина, 1 Chernyshev Yurii Olegovich Doctor of Technical Science Professor, Department of Automation of Production Processes, Don State Technical University 344000, Russia, Rostovskaya oblast', g. Rostov-na-Donu, ploshchad' Gagarina, 1 myvnn@list.ru Другие публикации этого автора

Венцов Николай Николаевич кандидат технических наук доцент, Донской государственный технический университет 344000, Россия, Ростовская область, г. Ростов-на-Дону, площадь Гагарина, 1 Ventsov Nikolai Nikolaevich PhD in Technical Science Associate Professor, Department of Information Technology, Don State Technical University 344000, Russia, Rostovskaya oblast', g. Rostov-na-Donu, ploshchad' Gagarina, 1 vencov@list.ru Другие публикации этого автора

Работа выполнена при финансовой поддержке РФФИ (проекты: 15-01-05129, 16-01-00390, 16-01-00391)

Форрест C. (Forrest S.) и Дасгупта Д (Dasgupta D.) на основе принципов распознавания своего и чужого в системе иммунитета предложили алгоритм отрицательного отбора для обнаружения изменений, в контролируемой системе. Этот подход можно формализовать следующим образом ^[1-4]:

- определяется «свое» как совокупность S строк длины над конечным алфавитом, которую необходимо защищать или контролировать. Например, в качестве S могут выступать нормальная форма активности или допустимое решение задачи;

- образуется набор детекторов W, каждый из которых не должен соответствовать любой строке в S. Вместо точного или идеального соответствия, может использоваться правило частичного соответствия при котором две строки соответствуют друг другу, если и только если, они совпадают, по крайней мере в h следующих друг за другом позициях, где h — некоторый целочисленный параметр;

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

Кандидаты в детекторы (множество W) могут генерироваться случайно, с последующей проверкой (цензурированием) на соответствие любой строке «своего».

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

Особенностью итерационных алгоритмов является чередование процессов модификации и анализа текущих решений. Анализ решений, как правило, сводится к четкому делению особей на перспективные/вырождающиеся, корректные/ошибочные, лучшие/худшие ^[2-5]. Предлагается дополнить известные итерационные модели поиска элементами метода отрицательного отбора — одним из инструментов искусственных иммунных систем. Использование такого подхода на основе нечетких декодеров, позволяет избавиться от бинарной количественной классификации и перейти к расплывчатым и качественным оценкам. Кроме этого механизм отрицательного отбора возможно применить для более детализированного анализа значений переменных, влияние которых может быть существенным на последующих этапах проектирования, изготовления и эксплуатации изделия.

Основными этапами решения задачи проектирования при таком подходе являются: анализ предметной области, генерация нечетких детекторов, генерация особей, отрицательный отбор, модификация особей. Для случая решения задачи размещения элементов СБИС характеристикой особи может являться длина полупериметра L прямоугольника, описывающего элементы, расположенные в соответствии с решением, которое кодирует данная особь ^[6-7]. Величина L может быть использована как для сопоставления особей, так и для задания множеств разрешенных и запрещенных решений. В данной работе рассматриваются вопросы представления запрещенных областей, оценок соответствия особей заданным областям, а также возможные варианты влияния на вычислительный процесс результатов анализа положения особи в пространстве решений.

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

Например, предположим, что длина полупериметра L, описывающего фрагмент проектируемого изделия, должна быть не более 0,7 nm (нанометров). В соответствии с этим условием, нечеткий декодер должен описывать принадлежность длины полупериметра к указанной запрещенной области.

Вначале определим способ оценки близости некоторого значения величине 0,7 nm. Для этого зададим функцию μ1(L), описывающую степень близости числовой величины к 0,7 nm ^[8-9]. На рис. 1 представлен график такой функции μ1(L), описывающей принадлежность длины полупериметра L к нечеткому условию «близко к 0,7 nm».

Рис.1 Зависимость принадлежности к условию

«близко к 0,7 nm» от длины полупериметра.

Значения графика функции μ1(L), представленного рис.1, характеризуют удаленность длины полупериметра L от 0,7. Для LÎ (0,35;0,7), чем меньше значение μ1(L), тем меньше L числа 0,7. Для LÎ(0,7;1,05), чем меньше значение μ1(L), тем больше L числа 0,7. Таким образом, на основе функции μ1(L), описывающей соответствие нечеткому условию «близко к 0,7 nm» можно построить функцию μ2(L), описывающую соответствие нечеткому условию «меньше 0,7 nm». На отрезке ^[0,35;0,7] функция μ2(L) строится на основе функции μ1(L) по правилу μ2(L)=1-μ1(L), на отрезке ^[0,7;1,05], функция определяется по формуле μ2(L)=0. На рис. 2 приведен график зависимости функции μ2 от длинны полупериметра L.

Рис.2 Зависимость принадлежности к условию

«меньше 0,7 nm» от длины полупериметра.

Из данных, представленных на рис. 2 следует, что чем меньше значение L на отрезке ^[0,35;0,7], тем ближе значение функции μ2(L) к единице.

В соответствии с концепцией искусственных иммунных систем декодер должен содержать описание критической, потенциально не допустимой ситуации. В рассматриваемом случае недопустимая ситуация, описывается условием L>0,7, поэтому введем для декодера D функцию μ3(L)=1-μ2(L), описывающую соответствие текущей длины L нежелательной ситуации, т. е. ситуации, когда L меньше 0,7. Чем ближе значение функции к единице, тем ближе контролируемый параметр к области запрещенных решений. График функции μ3 от длинны полупериметра L приведен на рис.3.

Рис.3 Зависимость принадлежности к условию

декодера от длины полупериметра

Операция отрицательного отбора состоит в вычислении μ3(L), чем выше значение функции μ3(L), тем более активной должна быть реакция иммунной системы.

По аналогии можно построить декодеры на основе нечеткого правила «очень близко к 0,7 nm» или «слегка близко к 0,7 nm». Для реализации нечеткого правила «очень близко к 0,7 nm» необходимо определить функцию μ4(L)=CON(μ1(L))=μ1(L)*μ1(L) ^[9,10]. График функции приведен на рис.4.

Рис.4 Зависимость принадлежности к условию

«очень близко к 0,7 nm» от длины полупериметра

На основе функции CON(μ1(L)), описывающей соответствие нечеткому условию «очень близко к 0,7 nm», можно построить функцию μ5(L), описывающую соответствие нечеткому условию «очень меньше 0,7 nm». На отрезке ^[0,35;0,7] функция μ4(L), строится на основе функции CON(μ1(L)) по правилу μ5(L)=1-μ4(L), на отрезке ^[0,7;1,05] функция, определяется по формуле μ5(L)=0. На рис. 5 приведен график функции μ5 от длинны полупериметра L.

Рис.5 Зависимость принадлежности к условию

«очень меньше 0,7 nm» от длины полупериметра

Введем для декодера D функцию μ6(L)=1-μ5(L), описывающую соответствие текущей длины L нежелательной ситуации, т.е. ситуации, когда L«существенно меньше 0,7». Чем ближе значение функции μ6(L) к единице, тем ближе контролируемый параметр к области запрещенных решений. График зависимости функции μ6 от длинны полупериметра L приведен на рис.6.

Рис.6 Зависимость принадлежности к условию

декодера от длины полупериметра

Сопоставив графики функций μ3 (рис.3) и μ6 (рис.6) можно утверждать, что для L=0,6 функция μ3(L)=0,8, а μ6(L)=0,6. Таким образом, декодер, построенный на основе функции принадлежности μ3 (исходное условие «близко к 0,7 nm»), трактует ситуацию критичнее на 20-30%, чем декодер μ6, построенный на основе условия «очень близко к 0,7 nm».

С помощью функции DIL=Öμ1(L) можно построить функции принадлежности к условиям «слегка близко к 0,7 nm», «слегка меньше 0,7 nm», а также определить функцию принадлежности для соответствующего декодера ^[9-11].

Если необходимо задать расплывчатый декодер для оценки соответствия интервалу, то вначале определяется функция принадлежности данному интервалу. Пример графика зависимости функции μ7 от длинны полупериметра L, описывающей принадлежность к условию «от 0,55 до 0,7», приведен на рис. 7.

Рис.7 Зависимость принадлежности к условию

«от 0,55 до 0,7» от длины полупериметра

На рис. 8 приведена функция зависимости декодера μ8 от длинны полупериметра L, μ8(L)=1- μ7(L).

Рис.8 Зависимость принадлежности к условию

декодера от длины полупериметра

Данные представленные функцией декодера (рис.8), позволяют утверждать, что критические сигналы будут вырабатываться декодером в случае, если L<0,5 или L>0,7.

По аналогии с условиями «очень близко к 0,7 nm» и «слегка близко к 0,7 nm»можно определить для декодеров функции принадлежности «очень в диапазоне от 0,55 до 0,7 nm» (рис.9) и «слегка в диапазоне от 0,55 до 0,7 nm» (рис.10).

Рис.9 Зависимость принадлежности к условию

декодера от длины полупериметра

Рис.10 Зависимость принадлежности к условию

декодера от длины полупериметра

Сопоставив графики функций μ9 (рис.9) и μ10 (рис.10) можно утверждать, что для L=0,5 функция μ9(L)=0,2, а μ10(L)=0,05. Таким образом, декодер, построенный на основе функции принадлежности μ9, в точке L=0,5 воспринимает ситуацию в 4 раза критичнее, чем декодер μ10.

Используя соответствующие нечеткие функции принадлежности μ декодера, можно корректировать процесс оценивания степени близости контролируемого параметра к критической ситуации. Сопоставив графики функций μ3 (рис.3) и μ6 (рис.6) можно утверждать, что для L=0,6 функция μ3(L)=0,8, а μ6(L)=0,6. Таким образом, декодер, построенный на основе функции принадлежности μ3 (исходное условие «близко к 0,7 nm»), трактует ситуацию критичнее на 20-30%, чем декодер μ6, построенный на основе условия «очень близко к 0,7 nm». Сопоставив графики функций μ9 (рис.9) и μ10 (рис.10) можно утверждать, что для L=0,5 функция μ9(L)=0,2, а μ10(L)=0,05. Таким образом, декодер, построенный на основе функции принадлежности μ9, в точке L=0,5 воспринимает ситуацию в 4 раза критичнее, чем декодер μ10. Применение функций CON и DIL к функциям принадлежности декодеров позволяет менять их восприимчивость на тестовых данных от 20-30% до 200%-300%.