Мы используем файлы cookie.
Продолжая использовать сайт, вы даете свое согласие на работу с этими файлами.
Генетичний алгоритм
Штучна імунна система
Другие языки:

Штучна імунна система

Подписчиков: 0, рейтинг: 0

Шту́чні іму́нні систе́ми (англ. AIS - Artificial immune system) належать до класу обчислювальних інтелектуальних систем, що використовують принципи імунної системи хребетних. Для розв'язання задач ці алгоритми використовують властивості імунної системи до навчання і пам'яті.

Означення

Штучна імунна система (ШІС) — це адаптивна обчислювальна система, що використовує моделі, принципи, механізми та функції, описані в теоретичній імунології, які застосовуються для розв'язання прикладних задач. Попри те, що природні імунні системи вивчені далеко не повністю, на сьогодні існують щонайменше три теорії, які пояснюють функціонування імунної системи та описують взаємодію її елементів, а саме: теорія негативного відбору, теорія клональної селекції і теорія імунної мережі. Вони лягли в основу створення трьох алгоритмів функціонування ШІС. Сфера застосування ШІС включає такі області (але не обмежується ними):

Історія

ШІС почало своє існування в середині 1980-х років з досліджень Фармера, Пакарда та Перелсона у 1986му, а також роботою Варела (1990). Форрест і Кепхарт опублікували свої перші роботи про ШІС в 1994 році. Дасгупта виконав дослідження Negative Selection Algorithm. Хант і Кук почали роботи по моделюванню імунної мережі в 1995 році; Тімміс і Ніл продовжили цю роботу і зробили кілька поліпшень. Де Кастро і фон Зубен, а також Нікосії і Cutello в 2002 році виконали дослідження на тему: clonal selection. Перша книга по ШІС була видана під редакцією Дасгупти в 1999 році.
В даний час вивчаються нові ідеї, такі як danger theory і алгоритми, що походять від імунної системи. Проте існують деякі сумніви, що вони ще не будуть пропонувати нічого понад існуючих алгоритмів ШІС.

Інші недавні події пов'язані з дослідженням виродження в моделях ШІС. Спочатку ШІС було направлено на пошуки ефективних абстракцій процесів, що протікають в імунній системі, але останнім часом переорієнтовується на моделювання біологічних процесів та застосування імунних алгоритмів для вирішення проблем біоінформатики.
У 2008 році Дасгупта та Ніно опублікували підручник з імунологічних обчислень, який являє собою збірник до сучасних робіт, пов'язаних з імунітетом на основі методів ШІС.

Методи

Методи ШІС використовують специфічні імунологічні теорії, які пояснюють функції і поведінку адаптивної імунної системи ссавців.

  • Негативний алгоритм вибору користується процесами позитивної та негативної селекції, які відбуваються під час дозрівання Т-лімфоцитів в вилочкової залозі. Негативний відбір відноситься до ідентифікації і видалення негативно реагуючих клітин. Цим займаються Т-клітини, які можуть здійснити вибір і провести атаку тканини. Цей клас алгоритмів, як правило, використовується для класифікації і розпізнавання проблемних областей, де простір проблеми моделюється на основі наявних знань. Наприклад, у разі виявлення аномалій домену алгоритм на звичайних (не аномальних) зразках цієї моделі і здійснює виявлення невидимих або аномальних зразків.
  • Імунні мережеві алгоритми — алгоритми, що користаються теорією ідеотипічних мереж, запропонован Нільсом Кай Джерном, яка описує регуляції імунної системи за допомогою ідеотипічних антитіл (антитіл, які вибирають для інших антитіл). Цей клас алгоритмів сфокусовано на мережевому графі структур, де антитіла (або антитіла, які продукують клітини) є вузли та алгоритм навчання передбачає зростання або скорочення відстаней між вузлами на основі близькості (подібності в просторі подання проблеми). Імунні мережеві алгоритми були використані в кластеризації, візуалізації даних, контролі та оптимізації областей, а деякі — для розробки штучних нейронних мереж.
  • Дендритні алгоритми. Ці алгоритми засновані на абстрактній моделі дендритної клітини (ДК).

Принцип роботи

Імунна система має всі головні особливості штучного інтелекту: пам'ять, здатність навчатися, уміння розпізнавати й ухвалювати рішення щодо того, як розглядати чужорідний білок (антиген), що потрапив в організм, навіть якщо останній ніколи не існував на Землі. Подібно до штучних нейронних мереж, ШІС можуть накопичувати нову інформацію і, використовуючи попередньо вивчену інформацію, здійснювати розпізнавання образів децентралізованим способом.

Імунна система виконує кілька функцій. Разом з іншими системами організму вона підтримує стійкий стан життєвих функцій, названий гомеостазом. Однак найзначнішою її роллю є захист організму від захворювань, зумовлених проникненням в організм інфекційних агентів або чужорідних речовин, що несуть чужорідну генетичну інформацію, а також знищення пошкоджених клітин. Мікроорганізми, які подібні до вірусів, бактерій, грибків і паразитів, класифікуються як хвороботворні, оскільки вони можуть викликати захворювання після вторгнення в наш організм. Першочерговим завданням, з яким зіштовхується імунна система, є розпізнавання цих хвороботворних організмів. Імунна система не розпізнає весь хвороботворний організм цілком. Розпізнавання відбувається на рівні окремих молекул мікроба, які називають антигенами. Основним елементом, що забезпечує функціонування імунітету, є В — і Т-клітини (лімфоцити). Вони містять на своїй поверхні спеціальні молекули (рецептори) — антитіла. Антитіла є безпосередніми виконавцями процесу розпізнавання чужорідних антигенів. З погляду хімії процес розпізнавання антигенів антитілами зводиться до міжмолекулярної взаємодії, під час якої антитіла «хімічно» зв'язуються з активними (рецепторами) ділянками антигенів і в такий спосіб нейтралізують їх. При цьому чим краще антитіло розпізнає антиген, тим сильнішим виходить зв'язок. Розглядаючи обчислювальні аспекти парадигми імунних систем, можна виділити такі елементи імунних алгоритмів:

  • — множина способів подання компонентів системи;
  • — множина механізмів, що дозволяють оцінити взаємодію індивідуумів з навколишнім середовищем і одного з одним;
  • — процедури адаптації, які управляють динамікою системи, тобто зміною її стану в часі.

Способи подання дозволяють створювати абстрактні моделі імунних органів, клітин або молекул; механізми оцінювання, які називають також функціями афінності, дозволяють кількісно оцінити взаємодії цих «штучних імунних органів», а процедури адаптації, виражені у вигляді безлічі загальних алгоритмів досягнення мети, управляють динамікою ШІС.

Основні поняття ШІС

Розвиток популяції, зокрема для алгоритму клональної селекції, можна теоретично розглядати як рух у дискретному просторі станів, що відбувається відповідно до певних ймовірнісних правил. Оскільки ймовірності переходу в новий стан залежать тільки від поточного стану системи (а не від її попередніх станів), можна сказати, що поводження ШІС може бути описане за допомогою властивостей марковських ланцюгів.

Афінністю називають міру взаємодії (або силу зв'язку) відповідних комплементарних ділянок антигену й антитіла або двох антитіл. Афінність може бути формально представлена у вигляді однієї з метрик (наприклад, Евклідової відстані); ця міра вказує на ступінь подібності або розбіжності між відповідними атрибутами рядків таку, що SP × S P → ℜ+.

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

Крос-реактивним порогом називають область у багатовимірному просторі форм, що охоплює антитіло, усередині якої проявляється його активність стосовно антигенів або інших антитіл.

Рівнем гіпермутації називають чисельне значення, яке використовується для визначення кількості клонів підданої мутації клітини пам'яті, які можна ввести в популяцію клітки.

Проектування ШІС

Для проектування структури ШІС найчастіше застосовують методи, які активно використовують в інших біологічних обчислювальних парадигмах — таких як, наприклад, нейронні мережі й еволюційні алгоритми. Набір функцій оцінки, узятих з даних обчислювальних парадигм, цілком може бути використано для оцінювання взаємодії індивідуумів ШІС. Разом з тим еволюційні алгоритми добре підходять для керування зміною в часі станів клітин і молекул, з яких складається штучна імунна система. Із врахуванням сказаного вище, процес побудови ШІС можна розділити на два основних етапи:

  • — вибір належної форми подання індивідуумів і міри афінності;
  • — застосування кожного з існуючих алгоритмів (або нового алгоритму) для керування зміною станів системи в часі.

Алгоритм клональної селекції

Крок 1. Ініціалізація. Створення (звичайно випадковою генерацією) початкової популяції антитіл (AB).

Крок 2. Обчислення афінності. Для кожного антитіла обчислити його афінність стосовно кожного антигену. Результати записати в матрицю афінностей.

Крок 3. Клональна селекція та поширення. Вибрати з популяції по n найкращих антитіл для кожного рядка матриці D і помістити їх в окрему популяцію клонів. Згенерувати клони елементів популяції AB пропорційно до їх афінності; тобто чим вища афінність, тим більша створюється кількість клонів і навпаки.

Крок 4. Дозрівання афінності. Піддати мутації всі клони популяції AB з імовірністю, обернено пропорційною їх афінностям, тобто чим нижча афінність індивідуума, тим вища ймовірність його мутації. Обчислити нову афінність кожного антитіла j аналогічно до кроку 2, одержавши нову матрицю афінностей CD. Вибрати з популяції AB n антитіл, для яких відповідний вектор-стовпчик матриці CD дає кращий узагальнений результат афінності, і перенести їх у популяцію клітин пам'яті RM.

Крок 5. Метадинаміка. Замінити d гірших антитіл популяції AB новими випадковими індивідуумами.

Крок 6. Замінити n антитіл популяції AB клітками пам'яті з RM і переходити до кроку 2 до тих пір, поки не буде досягнуто критерію зупинки.

Особливістю алгоритму клональної селекції є те, що він, на відміну від імунної мережі, підтримує постійний розмір популяції антитіл.

Псевдокод 

input   : S = set of patterns to be recognised, n the number of worst elements to select for removal
output  : M = set of memory detectors capable of classifying unseen patterns
begin
     Create an initial random set of antibodies, A 
   
  forall  patterns in S   do         
     Determine the affinity with each antibody in A 
     Generate clones of a subset of the antibodies in A  with the highest affinity. 
        The number of clones for an antibody is proportional to its affinity             
     Mutate attributes of these clones to the set A, and place a copy of the highest 
        affinity antibodies in A  into the memory set, M
     Replace the n lowest affinity antibodies in A with new randomly generated antibodies
  end 
 
end

Статті та посилання


Новое сообщение