Методи та засоби гібридних штучних імунних систем в задачах інтелектуального аналізу даних

Размещено на http://www.allbest.ru/

Національний університет "Львівська політехніка"

Автореферат

Дисертація на здобуття наукового ступеня

доктора технічних наук

МЕТОДИ ТА ЗАСОБИ ГІБРИДНИХ ШТУЧНИХ ІМУННИХ СИСТЕМ В ЗАДАЧАХ ІНТЕЛЕКТУАЛЬНОГО АНАЛІЗУ ДАНИХ

Спеціальність 05.13.23 - Системи і засоби штучного інтелекту

ЛИТВИНЕНКО ВОЛОДИМИР ІВАНОВИЧ

Львів - 2010

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

Значний внесок у розроблення теоретичних і прикладних засад створення ШІС внесли Н. Ерне, У. Берсіні, Д. Дасгупта, Д. Тімміс, Ю. Ватанабе, А. Ішігуро, А. Перельсон, Д. Еклі, С. Форрест, С. Хофмеер, Леонардо де Кастро, М. Ніколаєв, Е. Харт, О. Тюрелл, Фернандо Дж. вон Зюбен, Ф. Варела, Д. Кук. О. О.Тараканов та ін. В Україні над проблемами прикладних імунних систем працюють наукові школи В.В. Грицика, П.І. Бідюка, О.І. Михальова, В.П. Широчина та інші.

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

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

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

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

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

Зв'язок з науковими програмами, планами, темами. Розглянуті в роботі завдання відповідають державним науково-технічним програмам, що сформульовані в Законах України «Про наукову і науково-технічну діяльність», «Про національну програму інформатизації», а також планам найважливіших науково-технічних програм Міністерства освіти і науки України: 6 - Інформатика, автоматизація та приладобудування; 6.2.1 - Інтелектуалізація процесів прийняття рішень; 6.2.2 - Перспективні інформаційні технології і системи.

Дисертаційну роботу виконано відповідно до таких науково-дослідних робіт: НДР «Розробка базових компонентів імунно-нейронних технологій обробки зображень», № ДР - 0103U006336 (2002 р. - виконавець); ДКР «Розробити високоефективну систему аналізу, розпізнавання та сприйняття аудіо-відеоінформації з високою роздільною здатністю та чутливістю для образного комп'ютера», № ДР - 0103U006336 (2003 р. - виконавець); НДР Розробка теоретичних основ створення гібридних інтелектуальних систем на основі м'яких обчислень № ДР 1034U000078 (2005 р. - відповідальний виконавець); ДКР «Розробка нових інформаційних технологій на основі байєсівських мереж та імунологічних обчислень для прогнозування метеорологічних умов та інших явищ», № ДР - 01060012102 (2006 р. - відповідальний виконавець); ДКР «Розробка нових методів і алгоритмів сегментації зображень за допомогою імунологічних обчислень», № ДР - 01060012103 (2006 р. - відповідальний виконавець); ДКР Розробка нових інформаційних технологій на основі м'яких обчислень, для оцінки і прогнозу рівня забруднення водних об'єктів № ДР 01060012104 (2006 р. - відповідальний виконавець); НДР Дослідження штучних імунних систем в задачах ідентифікації акустичних сигналів № ДР 0106U012424, (2007 р. - виконавець); Дослідження штучних імунних систем в задачах забезпечення безпеки комп'ютерних систем (№ДР 0106U012423), (2010 р. - виконавець).

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

Для досягнення поставленої мети в роботі розв'язуються такі задачі:

1. Критичний аналіз існуючих принципів і методів побудови моделей та процедур аналізу даних із застосуванням штучних імунних систем.

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

3. Формулювання принципів та методів побудови штучних імунних і гібридних систем інтелектуального аналізу даних.

4. Розроблення системного підходу до розв'язання задач прогнозування на основі гібридних та комбінованих імунних систем.

5. Створення нових та модифікація існуючих моделей гібридних і комбінованих імунних систем для класифікації та кластеризації.

6. Розроблення методів і засобів структурно-параметричного синтезу нейронних мереж для розв'язання задач прогнозування та класифікації.

7. Створення інструментальних засобів конструювання ШІС для розв'язання прикладних задач різної природи.

Об'єкт дослідження - процеси інтелектуального аналізу даних у задачах прогнозування, класифікації та кластеризації.

Предмет дослідження - методи і засоби синтезу штучних імунних та гібридних систем для інтелектуального аналізу даних.

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

Наукова новизна одержаних результатів. На основі виконаних теоретичних та експериментальних досліджень розв'язано важливу науково-прикладну задачу розвитку теорії побудови штучних імунних систем, розроблення ефективних моделей та методів прогнозування процесів і класифікації об'єктів, та створення ефективних комп'ютерних засобів інтелектуального аналізу даних. Отримані такі нові наукові результати:

вперше розроблено:

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

- методологію побудови штучних імунних та гібридних систем, яка ґрунтується на використанні широкого класу адаптивних, гібридних і кооперативних обчислювальних структур для розв'язання задач прогноування та класифікації;

- гібридні моделі штучних імунних систем для ефективного прогнозування динамічних процесів на основі використання операторів експресії генів та їхніх схем подання, зовнішнього критерію МГУА ;

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

- метод структурно-параметричного синтезу колективів класифікаторів радіально-базисних та вейвлет- нейронних мереж для розв'язання задач класифікації;

- метод синтезу нечітких нейронних мереж на основі імуної мережі і клонального відбору для розв'язання задач прогнозування;

- метод синтезу штучних кооперативних імунних мереж з підвищеною збіжністю процедур для задач прогнозування;

- метод синтезу колективів штучних кооперативних імунних мереж для задач класифікації;

- моделі комбінованого використання схем негативного та клонального відборів, а також негативного відбору та імунної мережі, з високою роздільною здатністю класифікацї;

отримали подальший розвиток:

- метод синтезу імунної мережі з підвищеним рівнем адаптації детекторів для задач кластеризації нелінійних структур високої складності;

вдосконалено:

- адаптивні моделі штучних імунних мереж та клональого відбору для розв'язання задач класифікації на основі модифікованих операторів мутації та обчислення фукції афінності.

Практичне значення одержаних результатів полягає в тому, що запропоновані технології, методи і моделі забезпечують:

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

- підвищення якості оцінок прогнозів і класифікації об'єктів різної природи;

- зменшення часу та вартості синтезу гібридних штучних імунних систем для розв'язання задач інтелектуального аналізу даних.

Результати роботи впровадженні при розробці: комп'ютерної системи для розв'язання практичних завдань виявлення аномалій контрольованих параметрів технічної системи, пошуку місця і типу відмови в системі, а також прогнозування технічного стану, яка була впроваджена у ВАТ "Дніпровське підприємство ЕРА" (м. Херсон), Державному НДІ інформаційної інфраструктури (м. Львів), ТзОВ науково-виробнича фірма "МОНАДА" (м. Херсон); розроблене програмне забезпечення було впроваджено в у Центрі військової екології Міністерства оборони України для вирішення прикладних задач моделювання та прогнозування стану екологічної безпеки на об'єктах Збройних сил України (м. Київ); в Севастопольському військово-морському інституті ім. П.С. Нахімова Збройних сил України (м. Севастополь) в навчальний процес Національного авіаційного університету (м. Київ) та Херсонського національного технічного університету (м. Херсон).

Особистий внесок здобувача. У роботах, написаних у співавторстві, здобувачеві належать: розроблення і реалізація бібліотеки класів C++ алгоритму клональної селекції [1], аналіз принципів створення штучних імунних систем [2], експериментальне використання еволюційних методів для визначення хлорофілу за спектрами відбиття листків рослинності [3, 4], архітектура штучної імунної системи для розв'язання задач класифікації на основі механізмів ідіотипічної мережі [ 41 ], алгоритм, програмна реалізація і експериментальні дослідження [5, 22, 25, 33, 35, 37, 40], спосіб кодування структури нечіткої нейронної мережі, та програмна реалізація системи [7], спосіб гібридизації негативного відбору і штучної імунної мережі для розв'язання задач виявлення аномалій [15, 44], спосіб комбінування негативного відбору і наближених множин для розв'язання задач виявлення аномалій [17], експериментальні дослідження і порівняльний аналіз нейронних мереж при дистанційному визначення концентрації хлорофілу [20], знайдені верхні границі кількості поколінь необхідних для подання глобального оптимуму за різних значень параметрів досліджуваної імунної процедури [34], програмна реалізація та експериментальні дослідження [25, 28], формалізація опису методів і обчислювальних процедур імунних систем [27,28], алгоритм синтезу кооперативної імунної мережі, програмна реалізація і експериментальні дослідження [31, 43], алгоритм синтезу колективу вейвлет нейронних мереж для класифікації SELDI мас-спектрів [45].

Апробація результатів дисертації. Основний матеріал роботи пройшов апробацію на таких національних і міжнародних семінарах, конференціях і форумах, та презентовано у збірниках наукових праць: Міжнародна конференція «Контроль і управління в складних системах» (Вінниця, 2001, 2003), Міжнародна конференція з прикладної математики, присвячена 65-літтю з дня народження Б.Н.Пшеничного (Київ, 2002), Міжнародна конференція з індуктивного моделювання МКIМ (Львів, 2002), IEEE International Conference on Artificial Intelligence Syctems (ICAIS 2002) (Divnomorskoe, 2002), Всероссийская конференция «Нейрокомпьютеры и их применение НКП 2002» с международным участием (Москва, 2002), Міжнародна науково-практична конференція студентів, аспірантів та молодих вчених «Системний аналіз та інформаційні технології» ( м.Київ, 2003, 2005), Конференция «Интеллектуальные системы и интеллектуальный САПР» (Дивноморское, 2003), Міжнародна науково-практична конференція «Математичне та програмне забезпечення інтелектуальних систем» (Дніпропетровськ 2003, 2004, 2005, 2006, 2007, 2008), 11-та Міжнародна конференція з автоматичного управлінню (м.Київ, 2004), VII Всероссийская научно-техническая конференция Нейроинформатика-05 (г. Москва, 2005), IEEE International Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, (Sofia, Bulgaria, 2005), Міжнародна науково-практична конференція «Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій» (Євпаторія, 2005-2007), Інтелектуальні системи прийняття рішень та проблеми обчислювального інтелекту (Євпаторія, 2008, 2009, 2010), Всеукраїнська міжнародна конференція з оброблення сигналів і зображень та розпізнавання образів - УКРОБРАЗ (Київ, 2004, 2006), IV-а науково-технічна конференція ВМС Збройних Сил України «Стан і розвиток військово-морських сил Збройних Сил України» (Севастополь, 2005), Науково-методична конференція «Могилянські читання» (Миколаїв, 2007, 2008, 2009, 2010), Ювілейна науково-практична конференція «Актуальні проблеми експлуатації, ремонту, розробки та модернізації авіаційної техніки» (Київ, 2007), International conference on Inductive Modelling (Київ, 2005, Prague, 2007, Kyiv, 2008 і Yevpatoria, 2010).

Публікації. Основні результати дисертації опубліковані в 45 друкованих наукових працях. З них 39 статті у профільних наукових журналах і у збірниках наукових праць згідно з переліком ВАК України з технічних наук (у тому числі 20 без співавторів) і 6 - у матеріалах і тезах конференцій.

Структура та обсяг дисертації. Робота викладена на 395 сторінках, ілюстрована 198 рисунками та 56 таблицями. Робота складається з вступу, семи розділів, висновків, списку використаних джерел, що складається з 317 найменувань і 7 додатків.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

Рис. 1. Компоненти ШІС

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

Проаналізовано основні моделі штучних імунних мереж (неперервні та дискретні моделі), при цьому показано, що існує два рівні взаємодії мережі: 1) взаємодія із зовнішнім середовищем (чужорідні антигени) і 2) взаємодія з іншими елементами мережі. Описані типові застосування штучних імунних мереж. Проаналізовані основні переваги та недоліки штучних імунних систем.

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

Для вирішення означених проблем розроблена методологія проектування та розробки модифікованих та гібридних ШІС, опис та застосування яких наводиться в наступних розділах роботи.

У другому розділі розглянуто основні компоненти обчислювальних моделей, які ґрунтуються на імунній парадигмі (Рис.2): 1) схеми представлення компонент ШІС; 2) мір для кількісного оцінювання стану системи (афінності і міри оцінювання придатності); 3) імунних процедур, що дозволяють керувати поведінкою системи.

Рис. 2. Структурні компоненти ШІС

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

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

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

На підставі названого підходу ШІС, що реалізує принципи теорії негативного відбору, може бути виражена в такий спосіб:

(1)

де - простір форм; - довжина рецептора; - множина «своїх» детекторів; - множина «чужих « детекторів; - крос-реактивний поріг; - загальне число призначуваних детекторів; - розмір множини детекторів; - правило збіжності рядків у суміжних позиціях.

На етапі навчання система, використовуючи навчальну вибірку образів () («свої» антигени), створює множину () комплементарних образів, які називають детекторами. Далі процес розпізнавання відбувається так: новий образ, що надходить у систему, порівнюється із множиною детекторів і при відсутності збігів розпізнається як «свій»; при наявності збігів досліджуваного образу хоча б з одним детектором, він розпізнається як «чужий». Дану процедуру можна зобразити так: для даного простору форм і множини «своїх» визначаємо множину «чужих», , які комплементарні до , таким чином, що .

На підставі запропонованого підходу ШІС, що реалізує принципи теорії клонального відбору, може бути зображена в такий спосіб:

(2)

де -простір форм; - простір пошуку; l - довжина вектора атрибутів (розмірність простору пошуку); k - довжина рецептора антитіла; - розмір популяції антитіл; - функція експресії; f - функція афінності; I - функція ініціалізації початкової популяції антитіл; - умова завершення роботи алгоритму; AG - підмножина антигенів; AB - популяція антитіл; S - оператор селекції; C - оператор клонування; M - оператор мутації; n - кількість кращих антитіл, що відбирають для клонування; d - кількість гірших антитіл, що підлягають заміні новими.

Функція є функцією перетворення варіантів рішень із у їхні внутрішні простори () у вигляді індивідуумів популяції (функція експресії). Передбачається, що для кожного рішення існує одне і тільки одне його представлення . Використовуючи узагальнене подання, можна ввести функцію афінності f: . При цьому завдання полягає у максимізації функції афінності. Приймаючи початковий розмір популяції антитіл (), можна ввести функцію ініціалізації у вигляді: . Введемо стохастичний оператор перетворення на множині , що використовує керуючу множину для генерування керуючих параметрів, що визначають спосіб перетворення на поточному кроці роботи алгоритму. Функціональний запис оператора може бути виражений так: . Оптимальним рішенням щодо оператора і антигену називається індивідуум, афінність якого не може бути збільшена при подальшому впливі оператора перетворення , тобто . Умова завершення () виконується тоді, коли популяція антитіл повністю розпізнає популяцію антигенів, тобто . Оператор селекції S формує підмножину індивідуумів, чия афінність є кращою в даному поколінні. Таким чином, S, разом з керуючою множиною , задає функцію: . В результаті селекції утворюється множина: . Оператор клонування C збільшує представництво елементів множини в популяції і разом з керуючою множиною може бути записаний так: . Оператор мутації M з керуючою множиною має вигляд: . Метадинаміка системи виражена у вигляді функції заміщення гірших антитіл популяції: .

Зображено модель процесу перетворення станів популяцій антитіл за допомогою клональної процедури (3):

(3)

де - номер покоління; - популяція антитіл (детекторів); - підмножина відібраних найкращих антитіл; - підмножина клонів; - підмножина клонів після мутації.

Формалізм ШІС, що реалізує принципи роботи імунної мережі, схожий на (2) з додаванням декількох нових операторів і параметрів:

(4)

де H - оператор клонального видалення; R - оператор стискування мережі. У даному типі алгоритму оператор H використовує граничний коефіцієнт загибелі () як керуючий параметр, зменшуючи розмір мережі за рахунок видалення клітин (антитіл), які не стимулюються: . Множина клітин, що стимулюються, () може бути означена так:

,

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

,

.

Модель процесу перетворення станів популяцій антитіл за допомогою імунної мережі виглядає таким чином:

 (5)

де - редукована мережа кліток пам'яті; - зжата мережа кіток пам'яті.

Формально задачу розробки імунних систем можна зобразити у вигляді,

, (6)

де - множина способів зображення компонентів; - множина механізмів оцінки афінності; - множина процедур адаптації; - множина критеріїв якості ШІС.

Способи формального зображення ШІС забезпечують можливість створювати абстрактні імунні моделі імунних органів, клітин або молекул, механізми оцінки, які також називають функціями афінності, дають можливість кількісно оцінити взаємодії цих «штучних імунних органів», а процедури адаптації, виражені у вигляді множини загальних процедур досягнення мети, керують динамікою ШІС. Процес побудови ШІС розділений на два основні етапи: (1) вибір підходящої форми зображення індивідуумів і міри афінності; (2) застосування кожної з відомих процедур (або нової імунної процедури) для керування зміною станів системи в часі. Форма зображення індивідуумів і міра афінності повністю визначаються предметною галуззю, у якій передбачається використовувати ШІС, і типом розв'язуваної задачі. При комбінованому використанні різних імунних моделей під комбінацією підходів розуміється можливість одночасного використання деякими імунними моделями в межах однієї задачі кількох способів обчислення значень афінності. ШІС, як і будь-яку іншу систему можна розглядати в контексті двох видів взаємодії: (1) взаємодія із внутрішньою структурою обчислювальної системи (внутрішнім оточенням, модифікація імунних операторів, способів зображення та обчислення афінності); (2) взаємодія із зовнішнім середовищем (взаємодія між імунними моделями та процедурами). У ролі зовнішнього середовища виступає задача, для розв'язання якої створюється ШІС. Тут відбувається взаємодія з антигенами як носіями інформації про задачу, що впливає на поведінку системи. У якості внутрішнього оточення виступають компоненти системи (клітини і антитіла), які можуть взаємодіяти не тільки з антигенами, але й один з одним, також керуючи динамікою ШІС. Для кількісного розрахунку обох видів взаємодії використовується поняття афінності. Одним з резервів поліпшення роботи імунних систем є модифікація способів зображення даних (простору форм), підвищення адаптаційних властивостей операторів відбору, мутації та афінності, модифікація схем самих процедур негативного та клонального відбору, а також штучної імунної мережі. Такий підхід називається у роботі «внутрішньою модифікацією» (рис. 3.).

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



Рис. 3. Зображення типів гібридизації ШІС у контексті взаємодії із двома видами оточення: зовнішнім і внутрішнім

Даний факт викликає потребу в гібридизації імунних моделей з іншими процедурами оптимізації, машинного навчання і т.д., при цьому конкретними причинами для гібридизації можуть бути такі: (1) поліпшення роботи імунної процедури (наприклад: швидкість збіжності); (2) підвищення якості розв'язків, отриманих імунною процедурою; (3) включення імунної процедури як частини більшої системи.

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

Показано, що ймовірність виявлення «чужих» рядків збільшується експоненційно стосовно тривалості навчання, що дає можливість апріорно задавати необхідну ймовірність розпізнавання; при цьому встановлено, що при збільшенні ймовірності виявлення «чужих» рядків збільшуються обчислювальні затрати. Збільшення кількості детекторів веде до сповільнення фази розпізнавання, а його зменшення - до погіршення якості роботи алгоритму, тому що збільшується ймовірність утворення «порожнин», що є областями в просторі «чужих», які не розпізнаються жодним з детекторів. Отже, завданням цього дослідження є розробка вдосконаленого методу генерації детекторів, здатного адаптивно їх налаштовувати, а також підбирати їх кількість і розташування.

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

У третьому розділі запропонований формальний підхід до розробки та проектування ШІС, який дав змогу розробити ряд оригінальних ШІС для розв'язання задач прогнозування. Основна ідея для перших двох підходів полягає в наступному: модель клонального відбору або імунної мережі + оператори алгоритму експресії гена + зовнішній критерій МГУА (Рис.4).

Рис.4. Загальний підхід для розробки комбінованих імунних систем для розв'язування задач прогнозування

Головною особливістю першої імунної моделі є використання способу кодування рішень який запропоновано Ферерою Кандідою. У пропонованому методі є дві основні складові: антиген (або хромосома) і деревоподібне подання даного закодованого антигену. Процес декодування антитіл в їхні деревоподібні подання (експресії) називається трансляцією. Дана трансляція містить у собі тип коду і низку правил. Код містить у собі взаємооднозначну відповідність між символами антитіла і функціями або константами, які ці символи становлять. Правила визначають просторову організацію функцій і взаємодій у деревоподібних експресіях антитіл, а також типи під-експресій у багатофакторних системах. Антитіло становить рядок символів фіксованої довжини, при цьому код антитіл для різних експресій має різні розміри та форми. Для такого виду кодування антитіл нормальним є наявність незакодованої області нижче термінальної точки. На рисунку 5 наведений приклад найпростішої генетичної програми. Це не що інше, як дерево математичного виразу, звичний для нас запис якого у вигляді формули математики виглядає в такий спосіб: . Структура генетичної програми включає алфавіт символів, що складається з 2-х підмножин: а) функціональної (F): ; б) термінальної (T) : .

Рис. 5. Генетична програма

Особливістю даного підходу кодування є те що генні вирази умовно поділяють на голову та хвіст. Голова може містити як функціональні, так і термінальні символи. Хвіст - тільки термінальні символи. У цьому випадку, розмір хвоста є функцією від розміру голови і обчислюється за формулою (7)

(7)

де n - максимальна кількість аргументів функції з функціональної підмножини; - хвіст; - голова.

Під афінністю антитіл у такому разі розуміється якість моделі в сенсі обчислення похибки апроксимації. В розробленій моделі передбачене використання зовнішнього критерію регулярності. У цій реалізації вибірка ділиться на реалізацію початкової вибірки , за допомогою якої оцінюють параметри моделі, за результатами перевірки вибірки , за допомогою якої здійснюється вибір потрібної моделі. Критерій регулярності визначає середньоквадратичне відхилення моделі на перевіряльній послідовності:

 (8)

де - табличне значення вхідної змінної; - значення розраховане з допомогою синтезованої моделі.

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

Рис. 6. Графічна інтерпретація взаємодії антигенів і антитіл у гібридній моделі імунної мережі

Афінності антитіл до антигенів у модифікованій версії імунної мережі обчислюється виходячи з таблиці значень апроксимованої функції. Ця таблиця являє собою матрицю наборів значень аргументів досліджуваної функції і відповідних їм значень самої функції. Під час оцінки антитіла символьний рядок його генетичного коду перетвориться в дерево математичного виразу і аргументи (Х) з таблиці підставляються в цей вираз. Отримані в результаті значення функції (Y') разом з відповідними їм табличними (реальними) значеннями (Y) підставляються у формулу середньоквадратичної похибки апроксимації (СКП). Афінність антитіла до антитіла обчислюється як коефіцієнт лінійної кореляції між двома вибірками значень, отриманих при підставленні тих самих наборів аргументів у математичні вирази, що відповідають двом порівнюваним індивідуумам.

Чим вище коефіцієнт кореляції, тим більше схожими є моделі і відповідні їм антитіла ( тобто тим менше відстань між антитілами).

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

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

Рис.7. Загальний підхід для розробки комбінованих кооперативних імунних систем для розв'язання задач прогнозування

Особливістю запропонованої моделі, на відміну від класичних підходів, є те що в моделі використано не індивідуальне, а популяційне кодування генетичних програм, в якому кожне антитіло є лише частиною генетичної програми. Множина термінальних вершин графа не піддається ніяким змінам під час розв'язку задачі, отже, популяцію імунного алгоритму повинні становити тільки антитіла, що кодують функціональні вершини. У цьому разі рядок антитіла може бути представлений так (рис. 8).

Рис. 8 Структура індивідуума популяції імунного алгоритму

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

У четвертому розділі запропонований формальний підхід до розробки та проектування ШІС, який дозволив розробити ряд оригінальних ШІС для розв'язання задач класифікації. Метод негативного відбору і побудований на його основі алгоритм, що узагальнює дану властивість імунної системи, складається з таких компонентів: (1) визначається множина (клас) «своїх» стрічок (векторів) довжини, що складаються із символів скінченного алфавіту (ці вектори моделюють нормальну поведінку системи); (2) генерується множина детекторів, які не розпізнають жодного вектора (не збігаються з ними) із множини, формуючи клас «чужий»; (3) дані, що надходять, контролюються шляхом неперервного порівняння з кожним із детекторів. Виявлення подібності хоча б з одним із детекторів розглядається як аномалія в поведінці системи. Існує два важливих аспекти моделей негативного відбору: 1. Цільове поняття алгоритму є компліментарність «своєї» множини; 2. Мета полягає в тому, щоб розрізнити «свої» і «чужі» образи, але при цьому доступні тільки образи від одного класу (вивчення одного класу). Робота кожного алгоритму негативного відбору відрізняється базовим числом факторів, типу: а) Число детекторів; б) Вплив на ефективність генерації й виявлення; в) Ступінь покриття датчиком; г) Вплив на точність виявлення. Один з недоліків процедури негативного відбору пов'язаний із фазою навчання. По визначенню канонічного алгоритму негативного відбору всі рецептори мають однаковий, заздалегідь певний, постійний у процесі навчання, розмір. Це позначається й на визначенні чіткої границі між «Своїми» і «Чужими» і рівні охоплення рецепторами. Канонічна процедура негативного відбору не є адаптаційним на відміну від інших імунних алгоритмів. Для того щоб знизити негативні робочі характеристики даної процедури розв'язано задачу об'єднання кращих якостей клонального відбору і негативного відбору і розроблено процедуру, яку названо «комбінована процедура клонального негативного відбору». В основі ідеї цього методу лежить припущення про те, що об'єднання процедури клонального відбору з негативним відбором дасть можливість підвищити рівень детекції (рівень охоплення) за допомогою клонального відбору та досягати більшої роздільної здатності (Рис.9).

Рис 9. Способи комбінування процедур негативного та клонального відбору

У даній модифікації запропоновано у фазі навчання оптимізувати покриття детекторами множини «чужих» за допомогою механізму клонального відбору. Для розв'язання поставленої задачі вводиться наступне подання антитіл (Рис.10).

Рис. 10. Подання антитіл негативної клональної моделі

У даному поданні атрибутами є координати центру детектора, а радіусом - граничне значення чутливості детектора (крос-реактивний поріг). Таким чином, кожне антитіло клонального алгоритму кодує один можливий варіант розташування детекторів у просторі «чужих», тобто варіант схеми покриття. Маніпулюючи популяцією антитіл подібної будови, алгоритм знаходить оптимальний варіант схеми покриття.

Наступною є модель в якій для підвищення рівня охоплення детекторів (рівень детекції) , запропонована модифікація фази навчання з використанням штучної імунної мережі. Модифікація полягає у тому, що вся множина згенерованих детекторів представляється у вигляді популяції елементів (вузлів) штучної імунної мережі, задачею якої є пошук оптимальної топології (Рис.11).

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



Рис. 11. Способи модифікації фази навчання при комбінування процедур негативного відбору і штучної імунної мережі

Для розрахунку значень афінності зв'язку «антиген-антитіло» використовується таке співвідношення:

, (9)

де - крос-реактивний поріг антитіла (детектора); - коефіцієнт значущості крос-реактивного порогу (параметр налаштування); - Евклідова відстань. Ця функція використовується для оптимізації розташування детекторів вздовж границі класів. Для розрахунку значень афінності зв'язку «антитіло-антитіло» запропонована формула:

(10)

В залежності від значення імунна мережа піддається стискуванню. Друга функція використовується для оптимізації взаємного розташування детекторів в «аномальному» просторі. Обидві функції використовуються операторами імунної мережі. Імунна мережа спроектована відповідно до співвідношення (4).

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

Рис. 12. Модифікація моделей клонального відбору та штучної імунної мережі для розв'язання задачі класифікації

Афінність розраховується за наступною формулою:

, (11)

де - афінність між -им антитілом і -им антигеном; - відстань між -им антитілом і j-м антигеном (нормована від 0 до 1: 0 - максимально можлива відстань, 1 - повний збіг координат); - кількість антигенів, які потрапили в область охоплення -ого антитіла, у яких ключовий клас збігається з -им антигеном; -загальна кількість антигенів, у яких ключовий клас збігається з -м антигеном; - кількість антигенів, які потрапили в область охоплення -ого антитіла, у яких ключовий клас не збігається -м антигеном.

Для прискорення процесу гіпермутації запроваджено для кожного гену антитіла вираз вагового коефіцієнта:

(12)

(13)

де - вага -го гена антитіла, - антитіло, - антиген. Формула (12) використовується у випадку, якщо відстань між антитілом і антигеном розраховується на основі Евклідової відстані, формула (13) - якщо розраховується на основі Манхетенівської відстань.

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



Рис. 13. Підхід для розробки кооперативних імунних мереж для розв'язання задач класифікації

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

Основна ідея полягає в підвищенні адаптивних здатностей імунної мережі для розв'язання задач кластеризації, за допомогою модифікації операторів обчислення афінності з гібридизацією імунної мережі з алгоритмом MST-дерева (Рис.15).

Розроблений імунний алгоритм кластеризації використовує дійсне кодування антитіл (рис. 14), де - координати центру антитіла в евклідовому просторі,

Рис. 14. Модифікація штучної імунної мережі

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

Формальне подання запропонованої процедури імунної мережі

(

(14)

де - популяція антитіл; - набір даних, що складається з векторів розмірності p; - загальна кількість клонів, створюваних стимульованими клітинами в кожному поколінні (при активації мережі); - кількість поколінь (генерацій) ; - матриця елементів Ag-Ab афінностей; - рівень заміщення (кількість антитіл з мінімальною афінністю, що відбираються для заміщення новими антитілами) ; - граничне значення клонального видалення; - матриця елементів Ab-Ab афінностей; - рівень відбору (кількість антитіл Аb з максимальною афінністю, що відбираються для клонування) ; - рівень мутації; - рівень відбору з популяції клонів; - відсоток поліпшених клітин, що відбираються з популяції клонів для наступного оброблення; - граничне значення супресії; - радіус антитіла; - афінність між антитілом і антигеном; - афінність між антитілами; - кількість розпізнаних даних антитілом; - розмірність простору даних; - показник рівномірності розподілу антигенів в області простору, обмеженого радіусом антитіла; - Евклідова відстань між центром антитіла й усередненим центром усіх розпізнаних цим антитілом антигенів; - параметр значимості радіуса антитіла.

Обчислення значення афінності зв'язків «антиген-антитіло»:

, (15)

де - параметр значимості радіуса антитіла тобто значення його крос-реактивного порога (збільшення значення цього параметра змушує імунну мережу підтримувати антитіла більшого радіуса, що дає більш грубу кластеризацію); - радіус антитіла (антигени, що попадають усередину даної області вважаються розпізнаними антитілом); - кількість розпізнаних даним антитілом антигенів; - Евклідова відстань між центром антитіла й усередненим центром усіх розпізнаних цим антитілом антигенів; - показник рівномірності розподілу антигенів в області простору, обмеженої радіусом антитіла. Показник обчислюється в такий спосіб:

, (16)

де - розмірність простору даних (довжина рецептора антитіла); - показник рівномірності розподілу розпізнаних антигенів уздовж -ї координатної осі простору даних.



Рис. 15. Подання антитіла імунного алгоритму кластеризації

, (17)

де - імовірність влучення розпізнаного антигену в -й інтервал -ї координатної осі простору даних ( у рамках області, обмеженої радіусом антитіла), , - кількість розпізнаних антигенів, що потрапили в -й інтервал -ї координатної осі простору даних.

Отримані антитіла ранжуються і відбирається задана кількість кращих антитіл з яких створюється популяція . Клонування антитіл у популяції клонів , у відповідності їх афінності обчислюється за формулою (18):

, (18)

де N_c - загальна кількість клонів у популяції клонів; ( - фактор множення; N - загальна кількість антитіл у популяції; round - оператор, який округляє аргумент до найближчого цілого числа. Обчислення афінності міжклітинної взаємодії обчислюється за формулою (19):

, (19)

де - радіус антитіла (антитіла, що попадають усередину даної області вважаються розпізнаними антитілом); - Евклідова відстань між центрами антитіл і й усередненим центром усіх розпізнаних цим антитілом антигенів.

В даному розділі також наведені результати тестових експериментів, які демонструють ефективність розроблених методів.

У п'ятому розділі розглянута можливість створення комбінованих методів, основними складовими яких є штучні імунні системи і методи, що ґрунтуються на інших обчислювальних парадигмах. Зокрема в розділі запропонований метод синтезу і навчання прогнозуючих моделей штучних нейронних мереж (ШНМ) радіально-базисного типу та вейвлет-нейронних мереж за допомогою ШІС (Рис.16).

Запропонований підхід дозволяє підвищити ефективність розв'язання задачі прогнозування в умовах її функціонування в реальному часі.



Рис.16. Способи використання процедури клонального відбору для структурно-параметричного синтезу РБФ та вейвлет нейронних мереж при розв'язанні задач прогнозування

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

Рис. 17. Подання структур і налаштувань ШНМ у вигляді рядків антитіл ШІС

Із цих параметрів формується вектор або рядок розв'язку. Рядок РБФ мережі містить елементи налаштувань мережі 1) кількість нейронів прихованого шару (m); 2) центри радіальних базисних функцій ( ); 3) коефіцієнти згладжування (); 4) типи базисних функцій прихованого шару ; 5) ваги вихідного шару ( ); 6) тип активаційної функції вихідного шару; 7) параметри активаційної функції вихідного шару (a). Рядок вейвлет мережі містить наступні елементи налаштувань: типи відповідних вейвлетів внутрішнього шару ( ); зсув і масштаб -го вейвлету внутрішнього шару (); вагові коефіцієнти (); тип функції активації (); параметр функції активації вихідного шару ().

Наступним комбінованим методом є метод синтезу і навчання прогнозуючих моделей нечітких нейронних мереж за допомогою ШІС. Розглядається можливість використання синтезу нечітких нейронних мереж на основі алгоритмів Ларсена та Цукмодо (Рис.18).

Рис. 18. Модифікація процедур клонального відбору та штучної імунної мережі при синтезування нечітких нейронних мереж при розв'язанні задачі прогнозування

Імунна система маніпулює популяцією векторів аналогічної структури і виконує пошук оптимального підбору значень параметрів нейронної мережі, при яких досягається мінімум похибки апроксимації. Рядок антитіла можна умовно розділити на три частини: типи функції приналежності (трикутна, Мексиканський капелюх, симетрично трикутна, Гусова), параметри функцій належності і ваги правил (Рис.19).

Рис. 19. Подання налагоджень нечіткої нейронної мережі у вигляді рядка антитіла

Для оцінювання кожного розв'язку виконується зворотне перетворення рядка в структуру нейронної мережі з відповідними налаштування. Далі, використовуючи навчальну вибірку даних, обчислюється похибка апроксимації, яка і є результатом оцінки рішень, що отримуються за запропонованим методом. У даному розділі наведено також результати експериментів, що свідчать про досить високу ефективність запропонованих методів. Експерименти розділені на три групи. Перша група демонструє вплив деяких параметрів ШІС на збіжність досліджуваних методів. Друга група чисельно оцінює якість прогнозів за допомогою ряду статистичних критеріїв (MAE, MAPE, WAE, WAPE, коефіцієнта Тейла, узгодження прогнозу з тенденцією розвитку процесу (directional accuracy). Третя група експериментів використана для оцінювання якості побудованих прогнозуючих моделей на основі аналізу залишків. В кінці розділу наведено результати експерименту, який демонструє ефективність комбінування прогнозів (колективне прогнозування), одержаних за різними методами.

...