Научно-методически статии
ИЗКУСТВЕНА ИМУННА СИСТЕМА
Резюме. Настоящата разработка описва същността и приложението на изкуствените имунни системи като клас от изчислителни системи, вдъхновени от принципите и процесите на имунната система при гръбначните животни. Разглеждат се четири основни модела. Разработен е алгоритъм за всеки от тях въз основа на концепциите за изучаване, разпознаване и запомняне на чуждите тела в даден организъм с цел решаване на определена група задачи. Разработката е класирана на първо място в Националния кръг на Международния конкурс MITE: „Методология и информационни технологии в образованието“.
Ключови думи: algorithms, immune system, clonal selection, negative selection, dendritic cell
Увод. Изкуствената имунна система (Artificial Immune System – AIS) представлява модел за изследване на структурата и функциите на биологична имунна система и използването им за решаване на задачи в математиката, инженерството и информатиката. Построяването на AIS използва методи на изкуствения интелект, имунологията и теоретичната биология. В настоящата разработка се разглеждат именно такива алгоритми.
Използвани термини. Антиген – чуждо тяло. Антитяло – белтък, който отговаря за унищожаването на определена група антигени. B- и Т-лимфоцити – имунни клетки на организма. Афинитетно зреене – процес на подобряване на сходството на антителата на B-клетките с антигенa. Апоптоза – естествена смърт на клетките. Некроза – насилствена смърт на клетките.
Методи. Основните техники са заимствани от имунологичните теории, които обясняват поведението на имунната система при бозайниците. AIS предлага 4 фундаментални алгоритъма, които намират приложение в различни обществени сфери.
I. Метод на отрицателния подбор (Negative Selection Algorithm). Това е един от механизмите в естествената имунна система, който вдъхновява развитието на много от съществуващите изкуствени имунни системи.
Биологична обосновка. В процеса на възникване на Т-лимфоцити в тимуса, ако Т-клетката разпознае някоя собствена клетка на организма като чужда, тя се елиминира, преди да започне своята имунна функционалност, тоест за клетката настъпва контролирана смърт (т.нар. апоптоза). Така клетките, които преминават успешно този процес, би трябвало да са нереактивни към собствените организмови клетки. Това свойство на лимфоцитите се нарича имунна търпимост.
Алгоритъм. Алгоритъмът за негативен подбор генерира детектори, които да елиминират някой друг детектор, който се свързва с група от декларирани собствени елементи. Всеки детектор си обгражда площ във формата на хиперкуб, чиято големина определяме по следната формула: \(\left(\cfrac{2 r}{\sqrt{n}}\right)^{n}\), където \(r\) е външният радиус.
В началото на алгоритъма се създава група от собствени низове \(-\mathbf{S}\), която определя нормалното състояние на системата. Следващата стъпка е да се генерира група от детектори \(-D\), които да се свързват и разпознават \(S\). Тези детектори могат да се приложат за нова информация, за да може да се класифицират като свои и несвои. Алгоритъмът създава групата от детектори чрез описания по-долу алгоритъм.
Вход: \(S_{\text {seen }}=\) група от познати собствени елементи.
Изход: \(D=\) група от генерирани детектори.
Описание на алгоритъма.
Начало
Повтаряй
− Създай детектори на случаен принцип и ги постави в група \(P\).
− Определи сходството на всеки елемент от \(P\) с всеки елемент от групата познати собствени елементи \(S\).
− Ако поне един елемент от \(S\) разпознае детектор от \(P\) според прага на разпознаване, тогава отхвърли детектора.
− В противен случай го добави в групата на позволените да съществуват детектори \(D\).
Докато се изпълни критерият за край.
Край
Алгоритъмът се прилага в различни сфери. Може да се използва за установяване на аномалии и засичане на злоупотреба с данни, причинена от вирус в компютърната система.
II. Метод на клоновата селекция (Clonal Selection Algorithm). Това е клас от алгоритми, свързани с изграждането на селекционен механизъм в даден организъм в продължение на определен период от време.
Биологична обосновка. Имунната реакция при бозайниците се предизвиква чрез разпознаването на „своите“ и „чуждите“ клетки в организма. При появата на подходящ антиген и срещата му с лимфоцит се предизвиква поява на клонинги на бялата кръвна клетка. Клонингите произвеждат идентични рецептори на клонираната клетка, които се насочват към „вредителя“. Собствените клетки не предизвикват разрушителна имунна реакция, а „несвоите“ клетки (патогени) се унищожават от антителата (клонингите), произвеждани от \(B\)-и \(T\)-лимфоцитите. Унищожават се още и лимфоцитите, които имат антигенни рецептори към клетките на самия организъм. По време на клоновото разширение сходството на антителата на \(B\)-клетките с антигена се подобрява. Това явление се нарича афинитетно зреене. При следващата поява на дадения антиген реакцията на имунната система е по-ефективна благодарение на останалите антитела от предишния представител.
Изчислителни данни. В този алгоритъм подборът се осъществява въз основа на сходството между антиген и антитяло. Възпроизвеждането е на принципа на клетъчното делене, а вариацията е подобна на соматичната хипермутация (адаптация към антигените). Последно споменатото е свързано с произволна промяна на гените на произведените антитела, при което се запазва информацията за дадения вредител.
Деленето на \(B\)-клетките е правопропорционално на сходството му с антигена: колкото по-голямо е сходството, толкова повече клонове се произвеждат. Втората особеност на този механизъм е, че мутациите, предизвикани от антигена, са обратнопропорционални на сходството с него. Kолкото по-голямо е сходството, толкова по-малка е мутацията на гена. Използва се в задачи за свързване по даден шаблон. Този алгоритъм търси оптимално решение на клонирането и високочестотната вариация на имунните клетки.
Алгоритъм. Нека имаме група от шаблони \(S\), които играят ролята на антигени. Задачата e да се създаде група от запомнящи антитела \(M\), чиито елементи да се свързват с тези в \(S\). Това става по следния начин.
Вход: \(S=\) група от модели за разпознаване, \(n=\) броят на най-лошите елементи, избрани за премахване.
Изход: \(M=\) група от запомнящи детектори, способни да разпознаят непознати модели.
Описание на алгоритъма.
Начало
− Създаване на начален произволен набор от антитела \(A\).
За всички шаблони от \(S\), които играят ролята на антигени, изпълни:
− Определи сходството с всяко антитяло в \(A\).
− Създай клонинги на групата на антителата в \(A\) с най-голямо сходство.
Броят на клонингите на антителата трябва да е пропорционален на сходството им с антигена.
− Измени характеристиките на клонингите от \(A\) и копирай този с най-голямо сходство в групата \(M\) от запомнящи детектори, способни да разпознаят непознати модели.
Край
III. Метод на имунните мрежи (Immune Network Algorithm). Този алгоритъм е построен на основата на теорията за естествения подбор при антитялообразуването с цел да се обяснят запазените спешни реакции на организма, както и имунната памет.
Биологична обосновка. Основната предпоставка на този механизъм е свързана с това, че всеки лимфоцитен рецептор в организма може да бъде разпознат от група рецептори. Групата, която разпознава лимфоцитите, може да бъде разпозната от други рецептори и така нататък. По този начин се изграждат имунни мрежи, в които клетките си взаимодействат. Същността на тази теория е, че целият набор от антитела в организма се произвежда непрекъснато и в ниски количества от тези лимфоцити в резултат на това взаимодействие между клетките. Когато антигенът проникне в организма, той се свързва към съответното му антитяло. Това води до произвеждане на елземпляри на антитялото.
Aлгоритъм. Алгоритъмът за изкуствени имунни мрежи има 2 стъпки.
1) Генерират се определен брой антитела, представляващи изкуствена имунна мрежа.
2) За да се открие местно оптимално решение, се осъществява клонова селекция на всяко от антителата в мрежата.
Процесът продължава, докато средното здравословно състояние на клетките е близо до предишното поколение (преди появата на антиген). Това означава, че мрежата е стабилизирана. Антителата в клетката си взаимодействат и се потиска мрежата. Накрая се генерират на случаен принцип нови антитела. Процесът се повтаря, докато не са изпълнени условията за край. Алгоритъмът е следният.
Вход: \(S=\) група от модели за разпознаване, \(n t=\) праг на мрежово сходство, \(c t=\) праг на групата от клонинги, \(h=\) брой на клонинги с най-голямо сходство, \(a=\) брой на новите антитела, които ще се създадат.
Изход: \(N=\) група от запомнящи детектори, способни да разпознаят непознати модели.
Описание на алгоритъма.
Начало
− Създаване на начален произволен набор от мрежови антитела \(N\).
Повтаряй
За всички шаблони от групата модели за разпознаване \(S\) изпълни.
− Определи сходството с всяко антитяло в \(N\).
− Създай клонинги на групата на антителата в \(N\) с най-голямо сходство.
− Броят на клонингите на антителата трябва да е пропорционален на сходството им с антигена.
− Измени характеристиките на клонингите отнинги е от \(A\) и постави \(h\) на брой антитела с най-висок афинитет в \(C\).
− Унищожи всеки елемент от \(C\), чието сходство с антигена е по-малко от предварително зададения праг \(c t\).
− Определи сходството сред всички антитела в \(C\) и унищожи тези антитела, чието сходство с всеки друг е по-малко от прага \(c t\).
− Обедини оставащите клонинги от \(C\) в \(N\).
Край
Алгоритъмът поддържа разнообразието на популацията, но има недостатъци, като бавно откриване на сходства и слаба точност на търсене.
Съществува подобрена версия на този алгоритъм, която следи състоянието на клетките, вариращи във времето. Този алгоритъм въвежда търсеща процедура, наречена златна област, и 2 оператора за мутация: едномерна мутация и генна дубликация. Златната област се използва за избиране на най-добрата стъпка за размер на мутацията. Едномерната мутация е подобна на Гаусовото разпределение, но е еднопосочно. В оператора за дубликация на гени на случаен принцип се копира един елемент в друг и така се симулира поведението на хромозомите в еволюционното развитие на биологичните видове. Този подобрен алгоритъм има по-голяма точност, но е по-бавен.
Изкуствените имунни мрежи се използват за представяне на данни, контрол и оптимизация на домейни, споделяне на характеристики с изкуствени невронни мрежи, групиране и други.
IV. Метод на дендритните клетки (Dendritic Cell Algorithm). Това е алгоритъм, вдъхновен от теорията за „ролята на сигналите за опасност“.
Биологична обосновка. Теорията за разпознаване на „свое“ от „чуждо“ не отразява промените, които настъпват при растежа и развитието на организма. Възниква въпросът какво се случва, когато „своето“ се промени? Как организмът преминава през пубертета, бременността, остаряването и други промени, без да атакува собствените си тъкани? Например лактиращата млечна жлеза произвежда белтъци, които не са били част от по-ранното „свое“, както e и плодът на една бременност. В същото време, защо не отхвърляме всички тумори, които продуцират нови или мутантни белтъци? Това е така, защото имунната система реагира не толкова към чужди антигени, колкото към такива, които смята за опасни.
Предлага се модел за индукция на различна имунна реактивност към автоантигени, произхождащи от клетки с различна съдба. Едните са клетки, подложени на програмирана „естествена смърт“ (апоптоза), при която не се отделят стрессигнали и имунната система не се активира. Другите са клетки, подложени на „насилствена смърт“ (некроза), причинена от микроорганизми, травма и др., при която се отделят специфични пептиди – сигнали за опасност към имунната система и тя се активира.
Основни положения:
1) За да бъдат активирани наивни \(T\)-клетки, е необходимо да има както среща с антигена, представен от антиген-представяща клетка (АПК), така и костимулация. АПК се активират също и от опасни алармиращи сигнали от наранени клетки (изложени на патогени, токсини, механични и други увреждания).
2) Костимулаторният сигнал трябва да дойде от същата клетка, която е представила антигена.
3) \(T\)-клетки, които имат само антигенна стимулация, без допълнителни стимули, претърпяват апоптоза.
Хипотезата „Опасност“ предлага обяснение за индукцията на автоимунитет, каквото никоя от другите теории не дава. Според нея някои автоимунни заболявания са причинени от генни мутации, свързани с физиологичната смърт на клетки и процесите на очистване, а други – от патогени и токсини в околната среда, които предизвикват некроза. Във втория случай имунната система просто отговаря на алармиращите (опасни) сигнали, като уврежда организма.
Нито клетките на придобития имунитет, нито тези на вродения предизвикват имунния отговор – това са тъканите на организма. Когато сме здрави, тъканите индуцират толеранс, а когато те са в дистрес, провокират ефективен имунен отговор. В основата на имунния отговор стои специфичен „вътрешен разговор“ между клетките на имунната система и тъканите, като по този начин се получава различен поглед към представите за „свое“ и „чуждо“.
Алгоритъм. Този алгоритъм е базиран на популацията. Имаме група тела, които притежават собствена памет. Алгоритъмът позволява използването на 2 типа числа – цели и рационални. Сигналът за опасност и сигналът за безопасност са числа с реална числова стойност (\(0-100\) ). Всяко от тях расте пропорционално с аномалията или нормалността на дадената ситуация. Целта е сигналите за опасно и безопасно да не са реципрочни, за да може системата да взема по-лесно решения при наличието на спорна информация.
Потокът от антигени също представлява сигнал, който има целочислена стойност. Изброяват се обектите и състоянията в проблемната област, които са аномални или нормални.
Сигналните входове се комбинират с определени стойности за генериране на два междинни сигнала – CSM и K. CSM сигналът е мярка за общата стойност на сигнала, на който дадена клетка е подложена. К сигналът е мярка за постоянната разлика между нормалното и аномалното на въведената информация. Стойностите и на двата сигнала се променят във времето. Когато оформеният CSM сигнал достигне до определени клетъчни спецификации в клетката, се казва, че клетката „мигрира“: тя става готова да класифицира антигена, който е определила за нормален или аномален. Начинът на образуване на двата междинни сигнала е представен чрез следните формули.
1) \(C S M=S n+D n\); 2) \(K=D n-2 S n\), където \(D n\) е текущият пример за опасен сигнал, а \(S n\) е текущият пример за безопасен сигнал.
Описание на алгоритъма:
Начало
− Създаване на начален произволен набор от чужди клетки \(S\).
За всички шаблони от \(S\) изпълни:
Определи вида на сигнала.
Ако сигналът е опасен:
− създай клонинги на клетката, която е засякла опасен сигнал;
− унищожи антигена;
− измени характеристиките на клонингите от \(A\) и копирай този с най-голямо сходство в \(M\).
Иначе:
− унищожи клетката, без да създаваш клонинги.
Край
Заключение. Описаните методи намират широко приложение в различни сфери и са основа за решаване на редица важни проблеми и задачи. Представените алгоритми се използват за оптимизация и разпознаване на домейни по шаблон, анализ, групиране и класификация на данни. Те помагат за откриване на аномалии, засичане на грешки и извличане на данни. Някои антивирусни програми са изградени на тези принципи. Последните тенденции са свързани с навлизането им в роботиката и инженерството. Създадени са охранителни системи, които прилагат тези модели.
REFERENCES / ЛИТЕРАТУРА
Tan, Y. (2016). Artificial Immune System: Applications in Computer Security. Wiley & IEEE.
Tan, Y. (2015). Anti-Spam Techniques Based on Artificial Immune System. CRC Press/Taylor & Francis.
Brownlee, J. (2012). Clever Algorithms: Nature-Inspired Programming Recipe. lulu.com.
Timmis, J., Hart, E. & Andrews, P. (2010). On Artificial Immune Systems and Swarm Intelligence. Swarm Intelligence.
Mo, H. (2009). Handbook of Research on Artificial Immune Systems and Natural Computing: Applying Complex Adaptive Technologies. China: Harbin Engineering University, China.
Castro, L. & Timmis, J. (2002). Artificial Immune Systems: A New Computational Intelligence Approach. Springer Science & Business Media.