Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2013
Hauptverfasser:	Желдак, Т.А., Слєсарєв, В.В.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2013
Schriftenreihe:	Искусственный интеллект
Schlagworte:	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/85217
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком / Т.А. Желдак, В.В. Слєсарєв // Искусственный интеллект. — 2013. — № 4. — С. 101–112. — Бібліогр.: 12 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-85217
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-852172025-02-09T14:46:22Z Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком Алгоритм моделирования искусственной иммунной системы с оператором селекции Саати и одномерным локальным поиском The algorithm of artificial immune system simulation with Saaty selection operator and one-dimensional local search Желдак, Т.А. Слєсарєв, В.В. Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Розглядається метод умовної оптимізації у безперервному просторі багатьох змінних, заснований на моделюванні імунної системи людини. Запропонований новий оператор селекції клітин для клонування, що базується на методі аналізу ієрархій (МАІ) Сааті. Для інтенсифікації роботи евристичного алгоритму використаний оператор одновимірного локального пошуку. Рассматривается метод условной оптимизации в непрерывном пространстве многих переменных, основанный на моделировании иммунной системы человека. Предложен новый оператор селекции клеток для клонирования, основанный на методе анализа иерархий (МАИ) Саати. Для интенсификации работы эвристического алгоритма использован оператор одномерного локального поиска. The method of constrained optimization in continuous space of several variables, based on the modeling of the human immune system is considered. New operator based on the Saaty Analytic Hierarchy Process (AHP) for cloning cells selection is proposed. Using one-dimensional local search operator to intensify the heuristic algorithm is offered. 2013 Article Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком / Т.А. Желдак, В.В. Слєсарєв // Искусственный интеллект. — 2013. — № 4. — С. 101–112. — Бібліогр.: 12 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/85217 004.023 uk Искусственный интеллект application/pdf Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем
spellingShingle	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Желдак, Т.А. Слєсарєв, В.В. Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком Искусственный интеллект
description	Розглядається метод умовної оптимізації у безперервному просторі багатьох змінних, заснований на моделюванні імунної системи людини. Запропонований новий оператор селекції клітин для клонування, що базується на методі аналізу ієрархій (МАІ) Сааті. Для інтенсифікації роботи евристичного алгоритму використаний оператор одновимірного локального пошуку.
format	Article
author	Желдак, Т.А. Слєсарєв, В.В.
author_facet	Желдак, Т.А. Слєсарєв, В.В.
author_sort	Желдак, Т.А.
title	Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком
title_short	Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком
title_full	Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком
title_fullStr	Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком
title_full_unstemmed	Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком
title_sort	алгоритм моделювання штучної імунної системи з селективним оператором сааті та одновимірним локальним пошуком
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2013
topic_facet	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем
url	https://nasplib.isofts.kiev.ua/handle/123456789/85217
citation_txt	Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком / Т.А. Желдак, В.В. Слєсарєв // Искусственный интеллект. — 2013. — № 4. — С. 101–112. — Бібліогр.: 12 назв. — укр.
series	Искусственный интеллект
work_keys_str_mv	AT želdakta algoritmmodelûvannâštučnoíímunnoísistemizselektivnimoperatoromsaatítaodnovimírnimlokalʹnimpošukom AT slêsarêvvv algoritmmodelûvannâštučnoíímunnoísistemizselektivnimoperatoromsaatítaodnovimírnimlokalʹnimpošukom AT želdakta algoritmmodelirovaniâiskusstvennojimmunnojsistemysoperatoromselekciisaatiiodnomernymlokalʹnympoiskom AT slêsarêvvv algoritmmodelirovaniâiskusstvennojimmunnojsistemysoperatoromselekciisaatiiodnomernymlokalʹnympoiskom AT želdakta thealgorithmofartificialimmunesystemsimulationwithsaatyselectionoperatorandonedimensionallocalsearch AT slêsarêvvv thealgorithmofartificialimmunesystemsimulationwithsaatyselectionoperatorandonedimensionallocalsearch
first_indexed	2025-11-27T00:27:30Z
last_indexed	2025-11-27T00:27:30Z
_version_	1849901189601165312
fulltext	ISSN 1561-5359 «Штучний інтелект» 2013 № 4 101 2Ж УДК 004.023 Т.А. Желдак, В.В. Слєсарєв Державний ВНЗ «Національний гірничий університет», м. Дніпропетровськ, Україна Україна, 49005, м. Дніпропетровськ, пр. Карла Маркса, 19 Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком T.A. Zheldak, V.V. Slesarev State Higher Educational Institution «National Mining University», Dnipropetrovs’k, Ukraine Ukraine, 49005, Dnipropetrovs’k, Karl Marks av., 19 The Algorithm of Artificial Immune System Simulation with Saaty Selection Operator and One-dimensional Local Search Т.А. Желдак, В.В. Слесарев Государственное ВУЗ «Национальный горный университет», г. Днепропетровск, Украина Украина, 49005, г. Днепропетровск, пр. Карла Маркса, 19 Алгоритм моделирования искусственной иммунной системы с оператором селекции Саати и одномерным локальным поиском Розглядається метод умовної оптимізації у безперервному просторі багатьох змінних, заснований на моделюванні імунної системи людини. Запропонований новий оператор селекції клітин для клонування, що базується на методі аналізу ієрархій (МАІ) Сааті. Для інтенсифікації роботи евристичного алгоритму використаний оператор одновимірного локального пошуку. Ключові слова: імунні системи, оптимізація, Сааті, локальний пошук. The method of constrained optimization in continuous space of several variables, based on the modeling of the human immune system is considered. New operator based on the Saaty Analytic Hierarchy Process (AHP) for cloning cells selection is proposed. Using one-dimensional local search operator to intensify the heuristic algorithm is offered. Key words: immune systems, optimization, Saaty, local search. Рассматривается метод условной оптимизации в непрерывном пространстве многих переменных, основанный на моделировании иммунной системы человека. Предложен новый оператор селекции клеток для клонирования, основанный на методе анализа иерархий (МАИ) Саати. Для интенсификации работы эвристического алгоритма использован оператор одномерного локального поиска. Ключевые слова: иммунные системы, оптимизация, Саати, локальный поиск. Вступ Чимало інженерних, соціальних та економічних задач можуть бути сформульо- вані у вигляді задач оптимізації деяких цільових функцій багатьох змінних. При цьому в більшості випадків цільові функції виявляються мультимодальними. Наявність кількох Желдак Т.А., Слєсарєв В.В. «Искусственный интеллект» 2013 № 4 102 2Ж локальних оптимумів цільової функції одночасно з одним чи декількома глобальни- ми оптимумами традиційно розглядається як суттєвий недолік. Існує цілий ряд мето- дів і алгоритмічних прийомів, спрямованих на вихід з локальних оптимумів з метою досягнення єдиного глобального. Задача ускладнюється, коли йдеться не про один, а про декілька критеріїв та мно- жину рішень, недомінованих одне одним, серед яких все одно намагаються віднайти єдиний оптимум. В реальних застосуваннях часто існує необхідність пошуку не єдиного оптимального розв’язку задачі, а їх сімейства. Кожне з отриманих рішень, що в загально- му випадку є субоптимальним, дозволяє розглянути одразу кілька можливих результатів. Таке багатоваріантне розв’язання задачі дозволяє отримати метаевристика, відома як метод моделювання штучної імунної системи. Запропонований нижче імунний алгоритм (ІА) імітує властивості природної імун- ної системи і заснований на принципах соматичної теорії [1] і мережевої гіпотези [2]. Соматична теорія стверджує, що збільшення різноманітності антитіл відбувається за ра- хунок соматичної рекомбінації і мутації генів. В рамках мережевої гіпотези обґрунто- вується припущення, згідно з яким контроль розмноження клонів здійснюється в резуль- таті взаємного розпізнавання антитіл, що функціонують як єдина мережа [1], [3], [4]. В процесі еволюції імунна система вищих ссавців набула здатності знищувати антигени за допомогою антитіл (рис. 1). Рисунок 1 – Механізм формування антитіл в імунній системі На рис. 1 показана робота імунної системи з точки зору процесів обробки і управ- ління інформацією. Користуючись цією схемою, інформаційні процеси в імунній системі можна представити у вигляді алгоритму, який вкладається у наступну послідовність формалізованих кроків, докладно розглянутих у [3]: 1 Розпізнавання антигену. Цей процес відповідає встановленню вигляду задачі оптимізації    XfXff nRDX   min** , де n розмірність вектора X дійсних змінних Xxi  , заданих на області припустимих значень D . 2 Генерація антитіл клітинами пам’яті. Це відповідає пригадуванню успішного вирішення аналогічної (або схожої) задачі в минулому. Алгоритм моделювання штучної імунної системи з селективним оператором… «Штучний інтелект» 2013 № 4 103 2Ж 3 Обчислення афінності (корисності) клітини jX , що є еквівалентним пошуку оптимального рішення:  jj Xf для задачі мінімізації. 4 Диференціювання лімфоцитів: збереження відповідного рішення для наступного кроку пошуку та видалення зайвих кандидатів на рішення. 5 Стимулювання і придушення антитіл в залежності від афінності. Дослідження локальних оптимумів супроводжується підтриманням розмаїття напрямів пошуку. 6 Розмноження антитіл з використанням пам’яті та випадкових генів. У природі описаний процес є безперервним – антитіла продукуються організмом як до відомого антигену, так і до його можливих мутацій. При моделюванні процесу на комп’ютері роботу алгоритму можна зупиняти після певної кількості поколінь або ж через заданий наперед час. Результатом роботи алгоритму буде сімейство рішень, що відповідають антитілам у клітинах пам’яті, максимально пристосованих до антигену. У випадку пошуку екстре- мумів багатомодальних функцій це сімейство відповідатиме масиву з векторів-рішень, афінність яких максимально наближена до глобального оптимуму, тоді як самі рішення попарно відмінні не менш як на задану порогову величину. Показниками ефективності роботи алгоритму можуть бути час виконання та кіль- кість звернень до цільової функції при відшуканні глобального оптимуму, а також надій- ність (повторюваність) отриманих рішень при повторних запусках. Останнє є доволі важливим, адже евристичний метод, що розглядається, відноситься до класу методів випадкового пошуку і має збіжність лише за ймовірністю. Метою даної роботи є розробка такого алгоритму, що реалізовував би метод моделювання штучної імунної системи для вирішення задачі багатовимірної умовної оптимізації багатомодальних безперервних функцій та забезпечував при цьому макси- мально можливі показники ефективності. Аналіз існуючих алгоритмічних рішень Історично першою реалізацією ідеї моделювання штучних імунних систем була ідея селекції та витіснення незалежних пошукових агентів, запропонована у алгорит- мі CLONALG [5]. Даний алгоритм, що є поєднанням головних ідей генетичних алго- ритмів та еволюційних стратегій, використовує двійкове кодування дійсного простору пошуку, селекцію певної частини (близько половини) кращих особин і їх рівномірне клонування, мутацію зворотно, пропорційну корисності, виключення найменш корис- них антитіл та стиснення популяції. Оператор стиснення популяції вилучає надлишковість популяції, виключаючи гірше з близьких рішень, що задовольняють вимозі  pba NbabarXX :1,,,  , (1) де r – певний поріг близькості; * – символ норми, яка розраховується в залеж- ності від метрики простору; pN – розмір популяції. До недоліків алгоритму CLONALG слід віднести відсутність адаптації, обмежену точність, обумовлену двійковим кодуванням, та невикористання як такого механізму пам’яті. Інший алгоритм моделювання імунних систем – алгоритм BCA [6] – фактично є версією еволюційної стратегії з двійковим кодуванням і оператором стиснення. Він використовує одразу два оператори мутації: у 3/4 випадків – бітову, а у 1/4 випадків – суміжну (кілька бітів, що стоять поруч, інвертуються одночасно). Метод показує високу Желдак Т.А., Слєсарєв В.В. «Искусственный интеллект» 2013 № 4 104 2Ж ефективність пошуку при невеликих розмірах популяції 53pN , однак, як і CLONALG, на багатовимірних тестових задачах за якістю рішень програє відомим еволюційним стратегіям. Певним кроком вперед є алгоритм opt-AiNet, головною особливістю якого є робо- та безпосередньо у дійсному просторі та збереження всіх знайдених локальних і глобаль- них оптимумів цільової функції у пам’яті, розмір якої динамічно змінюється. Алгоритм використовує також динамічний розмір популяції, керований механізмом стискання [3]. Здійснюється мутація кожного клону, пропорційно корисності його батьківської кліти- ни за формулою    pjj C j C j NjeNXX jii :1,,1;0    , (2) де iC jX – i -й клон j -ї клітини попередньої популяції; j – радіус мутації для клонів j-ї клітини; j  – відносна афінність j -ї клітини у поколінні minmax max       j j  ;  – ві- льний позитивний параметр методу;  1;0N – нормально розподілена випадкова вели- чина з математичним очікуванням 0 і середньоквадратичним відхиленням (СКВ), що дорівнює 1. Практична реалізація даного алгоритму на ряді функцій [7] показала його знач- ну перевагу над алгоритмом CLONALG у швидкості отримання порівняного за якістю рішення. В роботі [4] запропоновано доповнити алгоритм opt-AiNet оператором випадко- вого локального пошуку. Останнє робить деякі реалізації алгоритму порівняними за ефективністю роботи з відомими генетичними алгоритмами та еволюційними стратегіями на класі розв’язуваних задач. Не випадково – і у цьому головна цінність opt-AiNet – він є основою для кількох більш сучасних алгоритмів, що реалізують викладений вище метод моделювання імунних систем. При вирішенні багатьох прикладних задач з використанням методу моделювання імунних систем застосовується алгоритм HIA, запропонований в [1] і удосконалений в [7]. Його можна розглядати як модифікацію методу opt-AiNet. На відміну від останньо- го, розмір популяції в алгоритмі HIA залишається постійним в процесі всього ітерацій- ного процесу й підтримується оператором стискання (1). Крім того, кожна з клітин має додатковий атрибут t , званий віком клітини. За його допомогою визначаються так звані «елітні» клітини, що прожили maxtt  . Це – рішення, які тривалий час не були покращенні мутацією, тому вважаються локальними оптимумами. Вони заносяться в пам’ять й використовуються для генера- ції клонів у кожному новому поколінні. Мутацію клонів здійснюють двома способами. Перший, відповідальний за інтенси- фікацію пошуку в околі знайденого рішення, полягає у покоординатній зміні клона з ви- користанням адаптивного нормального розподілу рівня мутації  ,;0 j C j C j NXX ii  (3) де  tj – СКВ нормального розподілу, що для кожної ітерації t визначається за- лежністю                   overwiset tXftXfiftXtX t j j C j C jj j ii 1 ;1)1(,)1(12   . (4) Алгоритм моделювання штучної імунної системи з селективним оператором… «Штучний інтелект» 2013 № 4 105 2Ж Другий спосіб має на меті диверсифікувати напрямок пошуку за рахунок обсте- ження ще не розглянутих ділянок і полягає у зміні однієї координати i випадковим числом з усієї області пошуку    nixxUx iiij :1,; max,min,,  . (5) Тут n – розмірність простору;  ii xxU max,min, ; – рівномірно розподілена випадкова величина в межах  max,min,\| iiii xxxxD  . Алгоритм НІА, у порівнянні з попередніми, демонструє надійність пошуку гло- бального оптимуму багатоекстремальних функцій за доволі обмежений час. Деякі дослідники, зокрема [8], [9], включають до алгоритмів моделювання імун- них систем оператори локального пошуку, які базуються на наведених вище методах безумовної оптимізації. Втім, застосування методів сходження на гору, Нелдера-Міда та множників Лагранжа, зокрема, у методі SIA [8] для розв’язання задач з обмежен- нями, хоч й посилює локальну збіжність алгоритмів, втім, не істотно впливає на ймовір- ність отримання глобального оптимуму. У алгоритмі Dopt-AiNet [9] застосовано оператор копіювання координат, який працює наступним чином: якщо після мутації по якійсь із координат афінність клону покращилася, нове значення за цією координатою намагаються застосувати до решти вимірів. Такий оператор показує високу ефективність в разі симетрії функції по коорди- натах, властивої для більшості тестових функцій, наприклад, Растрігіна, Еклі, Швефеля, Гріванка та інших [2]. Однак, при розв’язанні реальних задач, таких як навчання нейрон- них мереж прямого розповсюдження, чи основаних на радіально-базисних функціях, цей оператор абсолютно не ефективний. Більш доцільним бачиться введення у загальний алгоритм роботи штучної імунної системи оператора інформаційного обміну між пошуковими агентами (рекомбінації). Останній, відомий нам з генетичного алгоритму під назвою кросоверу, дозволяє значно покращити якість рішень і досягати потрібної якості в реальному масштабі часу за ра- хунок інформаційного обміну. Зокрема, у [10] пропонується для кожного з утворених клонів з невеликою ймовір- ністю 2,0crossP виконувати його кросовер з випадковою клітиною пам’яті. При цьому для кожного з генів рівноймовірно, залишаться вони без змін, чи будуть замінені на гени клітини пам’яті. Удосконалений алгоритм оптимізації HINO-SF Враховуючи розглянуті вище реалізації алгоритмів, котрі реалізують метод мо- делювання штучних імунних систем, пропонується наступний алгоритм, що не потребує двійкового кодування дійсних змінних та застосовує ряд операторів, відомих, зокрема, з генетичних та меметичних алгоритмів. Метою останніх має стати як інтенсифікація адаптивного локального пошуку, так і якомога повніше вивчення всієї області пошуку. Назвемо запропонований алгоритм HINO-SF (Hybrid Immune Network Optimiza- tion algorithm with Saaty selection and Fibonacci search). Він складається з наступних кроків: 1 Випадково генерується популяція антитіл. Лічильник поколінь встановлюється в 0t . 2 Якщо досягнуто наперед заданий максимум кількості поколінь, здійснюється перехід до кроку 11; в іншому випадку – перехід до кроку 3. 3 3а оцінкою пристосованості клітин поточного покоління призначається кіль- кість клонів для кожної з клітин поточного покоління – оператор селекції. Желдак Т.А., Слєсарєв В.В. «Искусственный интеллект» 2013 № 4 106 2Ж 4 Клонування клітин у кількості, що визначена оператором селекції. 5 Рекомбінація клонованих особин за допомогою оператору ймовірнісного кро- соверу. 6 Розрахунок динамічної ймовірності мутації для клонів та виконання адаптив- ного оператора мутацій. 7 3 певною ймовірністю виконання для кожного клона оператору одновимірного локального пошуку за випадковою координатою методом золотого перетину (Фібоначчі). 8 Стиснення спільної популяції батьків та клонів за рахунок відповідного опера- тору до заданого рівня pN . 9 Знищення з поточного покоління клітин, вік яких досяг заданого значення maxt . Їх місце в основній популяції займають клітини, згенеровані випадково рівномірно в області пошуку. 10 Лічильник поколінь 1 tt . Перехід на крок 2. 11 Виведення поточного покоління, як множини субоптимальних рішень. 12 Зупинка алгоритму. Розглянемо кожен зі згаданих в алгоритмі операторів докладніше. Оператор селекції. Для визначення кількості клонів, що припадає на кожну з осо- бин поточного покоління, пропонується використовувати оператор, що застосовує метод аналізу ієрархій (МАІ) Сааті з відтинанням, вперше застосований у операторах кло- нальної селекції еволюційних оптимізаційних стратегій [11]. Автор називає свій опе- ратор h зрізом множини клітин поточного покоління, що описується рівнянням      pjjh NjhXfDXM :1,\| min   , (6) де pNh /1min - к – критична пристосованість клітини; D – область пошуку;   jXf – функція належності клітини множині якісних. Функція належності клітини визначається наступним чином: – рішення нормуються за значенням афінності на відрізок  1;0 ; – розраховується рейтинг кожного з них   kXa jj 1  , де k розмірність шкали (за умовчанням k 9); – будується матриця попарних порівнянь, для першого рядку якої застосовується вираз ii aab /11  , а для решти – ijij bbb 11 / ; – функції належності розраховуються як     j jii bXf /1 ; – клітини, з    minhXf j  , клонуються у кількості, пропорційній функції належ- ності   icc XfNn  , решта батьківського покоління відкидається. Для ефективної роботи подальших операторів кросовера та мутації, бажано, аби особини з високою афінністю продукували достатньо велику кількість клонів. Тому рекомендується обирати pc NN  20...10 . Клональний відбір за МАІ є однією з ключових відмінностей запропонованого алгоритму від решти відомих реалізацій, у яких застосовується турнірний, пропорцій- ний («рулетковий») чи рівномірний принципи розподілу кількості клонів між батьківсь- кими особинами. Крім того, що даний метод, на відміну від решти, є математично обґрунтованим, його практичне застосування забезпечує кращу збіжність при вирішенні типових задач у порівнянні з іншими операторами селекції. Оператор кросоверу. Іншою ключовою відмінністю запропонованого алгоритму є застосування до клонів адаптивного оператору кросоверу, що передбачає обмін ге- нетичною інформацією. Оскільки було запропоновано не кодувати дійсну інформацію Алгоритм моделювання штучної імунної системи з селективним оператором… «Штучний інтелект» 2013 № 4 107 2Ж двійковою, то для рекомбінації генів пропонується застосування модельованого двійко- вого кросоверу (Simulated binary crossover, SBX) [10], що дозволяє імунним клітинам виконувати склеювання векторів дійсних координат аналогічно двійковим векторам в генетичних алгоритмах. Оператор SBX передбачає три параметри, що задаються користувачем: – crossP – ймовірність, що для клона буде виконано оператор кросоверу (зазвичай має значення, близьке до 0,5); – indP – ймовірність того, що по даній координаті виконуватиметься схрещування (може варіюватися в широких межах від 0,4 до 1 – в останньому випадку кросовер вико- нується по всіх координатах одночасно); – індекс варіації  – показує, як сильно нащадок схрещування має бути схожий на окремого батька (значення 0 та 1 з великою ймовірністю дадуть нащадка, схожого на одного з батьків, значення 0,5 – максимальне змішування генів). Якщо випадкове число, рівномірно розподілене між 0 та 1 (тут і надалі позначає- мо  1;0U ) менше ймовірності crossP для двох випадкових клонів з номерами j та k , а інше випадкове число  1;0U менше indP , то поточна координата i клонів піддається схрещуванню за формулою                  ,11 2 1 ;11 2 1 ,,, ,,, ijikik ikijij xxx xxx   , (7) де  так званий ступінь схрещування, що обчислюється за формулою                                 11;0, 1;02 1 ; 1 1;0,1;0 1 1 1 1 Uif U UifU . (8) Параметр  визначається через ступінь відмінності j -ї та k -ї клітин по ко- ординаті i , а саме         ikijikij iikijikiji xxxx xxxxxx ,,,, min,,,,,max, ;min;max ;min;;maxmin 21 12     . Оператор мутації. Головним оператором, що відповідає за пошук рішення, в запропонованому алгоритмі, як і в більшості реалізацій методу штучних імунних систем, залишається оператор мутації. Пропонується адаптивний оператор, який ви- падковим чином застосовує наступну мутацію    nixxxx iiiij C ij :1,min,max,,,   , (9) де випадкова складова i може визначатися на основі Гаусового розподілу згід- но з (2) за формулою  ,1;01,0 Ni  (10) або поліноміального розподілу за формулою                   2 1,15,02121 ; 2 1,1212 1 1 1 1 1 1 iiii iiii i rifrr rifrr    , (11) де  1;0Uri  – випадкове число, рівномірно розподілене для кожної з коорди- нат;   ii iijiji i xx xxxx min,max, min,,,max, ;max    – відносне положення поточної клітини в області Желдак Т.А., Слєсарєв В.В. «Искусственный интеллект» 2013 № 4 108 2Ж пошуку по i -й координаті;  – показник щільності поліноміального розподілу (більші значення відповідають меншому розсіву мутації). Отримуючи на вході традиційні параметри min mutP – мінімальний рівень мутації, ratemut _ – відносне значення рівня мутації (частини генів, які попадуть під зміну опера- тором) та maxT – максимальну припустиму кількість поколінь, алгоритм на кожній іте- рації розраховує ступінь мутації генів                2 , ; 2 ,2__1 _ maxmin max max min TtifP Ttif T tratemutratemutP levelmut mut mut , (12) де t номер поточного покоління (ітерації). Якщо при переборі координат випадкове число менше levelmut _ , координата піддається тій чи іншій мутації, інакше – залишається без змін. Рекомендується задавати min mutP – на рівні 0,2…0,5, а ratemut _ – на рівні 0,5…1. Тоді незалежно від обраного часу роботи алгоритму на початкових ітераціях мутація буде виконуватися для всіх клонів, на кінцевих – менше, ніж для половини. Вибір – яку саме мутацію виконувати: широку за (10) чи стислу за (11) – здій- снюється на основі синтетичної оцінки поточної клітини в масштабі оцінок корисності на поточній ітерації по всій популяції. Остання визначається для кожної клітині інди- відуально за формулою  c j j Nj T tselectmut :1,1 2 1_ minmax max max              , (13) де 95,08,0  – максимальна припустима доля поліноміальних мутацій в за- гальній кількості. Якщо при зверненні до клона випадкове рівномірне число виявиться меншим selectmut _ , то для генів клона виконуватиметься лише мутація (10), інакше – (11). З аналізу (13) зрозуміло, що ширша мутація за Гаусом застосовуватиметься для клі- тин з низькою афінністю й частіше – на початкових кроках оптимізації. Кількість мутацій за Гаусом зменшуватиметься лінійно з кількістю ітерацій та пропорційно афінності клі- тини на користь поліноміальної мутації. Слід звернути увагу, що вибір типу мутації здій- снюється для всієї клітини, а лише потім перевіряється, чи буде виконуватись ця мутація для кожної з координат, за (12). Оператор локального пошуку. Аби інтенсифікувати локальний пошук рішення і зробити його ще більш цілеспрямованим, до клона, який пройшов кросовер і мутацію з ймовірністю 25,0...1,0lsP , застосовується оператор одновимірного локального пошуку методом золотого перетину (Фібоначчі), який складається з наступних операцій [12]: – рівноймовірно обирається одна з координат  nk :1 ; – рівноймовірно обирається напрямок пошуку – до нижньої границі області по- шуку iC jXmin чи верхньої iC jXmax ; – здійснюється одновимірний локальний пошук у напрямку від поточного роз- ташування клона у просторі iC jX до границі області пошуку. Якщо пошук покращує афінність рішення, знайдене рішення зберігають. Оператор стиснення. По закінченні усіх пошукових операторів клітини нового покоління оцінюються за якістю. Разом з попереднім поколінням вони утворюють конф- Алгоритм моделювання штучної імунної системи з селективним оператором… «Штучний інтелект» 2013 № 4 109 2Ж ліктну множину, з якої, використовуючи принцип (1), відбирають pN клітин з найкращою афінністю, що лежать не ближче, ніж у радіусі r одна від одної. Для цього виконуються наступні операції: – сортування клонів за зменшенням афінності; – циклічно від першої клітини до спустошення множини ще не розглянутих; – вилучення усіх клітин, близьких до поточної і гірших за неї. Слід наголосити також на необхідності вилучення після стиснення клітин, що мають вік, більший за визначену межу maxt . Пропонується знищувати клітину з 20...10maxt іте- рацій, незалежно від її афінності. Подібні клітини замінюються новими, у яких кож- на клітина генерується за (5). Аналіз результатів роботи алгоритму Для порівняння роботи запропонованого алгоритму з відомими реалізаціями методу моделювання штучних імунних систем та з іншими евристичними методами, що традиційно використовуються для вирішення задач багатовимірної оптимізації, було проведено тестування на ряді стандартних багатоекстремальних функцій. Також було порівняно роботу запропонованого алгоритму із відомими раніше при вирішенні практи- чної задачі – навчання нейронної мережі прямого розповсюдження. На рис. 2а представлений знімок екрана результатів виконання алгоритму при мінімізації функції Растрігіна    21 2 2 2 1 2cos102cos1020)( xxxxXF   . Для показовості на графік виведено не саму цільову функцію, а зворотну їй величину – афінність клітин. З рис. 2 легко можна побачити основну особливість методу моде- лювання імунних систем – отримання в результаті не одного рішення, а одразу пев- ної множини, до якої входять як глобальний оптимум, так і найближчі за афінністю локальні оптимуми. а) б) Рисунок 2 – Тестування запропонованого алгоритму на функції Растрігіна: (а) результат мінімізації 2n ; (б) зміна афінності клітин в часі 20n На рис. 2б показані залежності афінності кращої клітини (безперервна лінія) в по- колінні (безперервна лінія) та середньої афінності популяції (пунктир) від номера іте- рації при мінімізації функції Растрігіна 20 порядку. Графік, звичний для евристичних алгоритмів, має суттєву особливість: навіть найкращі рішення, якщо не були змінені протягом певного терміну тривалості життя, відкидаються й замінюються випадковими. Желдак Т.А., Слєсарєв В.В. «Искусственный интеллект» 2013 № 4 110 2Ж У табл. 1 наведені порівняльні результати роботи алгоритмів при розв’язанні типових задач. У якості задачі навчання нейронної мережі була використана задача іден- тифікації механічних властивостей сортового прокату від його хімічного складу у скоро- ченому та повному варіанті. Таблиця 1 – Порівняння роботи алгоритмів при розв’язанні Метод розв’язання задачі RC-GA HIA HINO-SF Показники якості реалізації алгоритму Тестова функція (задача) Розмірність задачі (кількість змінних) f ~f ~n f ~f ~n f ~f ~n 20 0 3,472 4,4106 0 6,626 2,4105 0 1,929 1,0105 Растрігіна 100 1,999 15,94 1,6107 0,999 13,33 8,6106 0 2,616 2,0106 20 0 0,142 2,0106 0 1,086 7,2105 0 0,007 8,1104 Еклі 100 1,258 21,42 2,1107 1,314 11,24 9,4106 1,101 7,240 2,1106 72 4,974 16,37 1,4106 2,994 11,33 2,4106 2,039 10,20 2,1105 Навчання нейромережі 144 14,94 39,52 5,1108 13,99 21,07 1,4108 12,07 16,75 4,1106 В табл. 1 прийняті позначення: f – мінімальне значення цільової функції, знайде- не методом за 10 повторних запусків; ~f – статистичне значення оцінки математичного очікування мінімального значення функції при випадковому запуску; *~n – статистичне значення оцінки математичного очікування кількості викликів цільової функції до за- вершення алгоритму при випадковому запуску. Як видно, запропонований алгоритм знаходить глобально оптимальні рішення частіше від аналогів, при цьому витрачаючи значно менше часу. На особливо склад- них задачах, як, наприклад, навчання нейронної мережі на реальних даних, виграш часу може становити майже два порядки. Аби зрозуміти ефективність кожного з операторів, що складають алгоритм, зве- демо у табл. 2 частоту, з якою вони покращують значення афінності клітин. Таблиця 2 – Ефективність операторів запропонованого алгоритму Оператор Мутація Гауса Поліноміальна му- тація Локальний по- шук Кросовер Випадки покращення цільової функції, % 23,33% 47,99% 17,23% 11,45% Слід відзначити, що отримані дані вповні відповідають теоретичним засадам, адже саме мутація є головним інструментом локального пошуку в методі моделювання штуч- них імунних систем. Відсутність у табл. 2 запропонованого оператора селекції пояснюєть- ся тим, що він не призводить до покращення рішень, а лише обирає кандидатів для кло- нування. Висновки Аналіз основних сучасних алгоритмів, що реалізують метод моделювання штучних імунних систем показав його переваги перед іншими методами багатовимірної умов- ної оптимізації у дійсному просторі. Запропоновано гібридний адаптивний імунний алгоритм, що використовує оператор клональної селекції, кросовер, адаптивну мута- цію і обмежений локальний пошук. Селекція здійснюється шляхом оцінки пристосованості рішень з використанням методу ієрархії Сааті. Запропонований оператор селекції ефективніший, ніж традиційні оператори, крім цього, він є єдиним математично обґрунтованим. Алгоритм моделювання штучної імунної системи з селективним оператором… «Штучний інтелект» 2013 № 4 111 2Ж Парний адаптивний кросовер клітин-клонів забезпечує інтенсифікацію локального пошуку, дозволяючи поєднувати кращі гени двох вдалих рішень з попередніх поколінь. Аби підвищити спрямованість пошуку, до випадкової координати клона застосовується оператор одновимірної оптимізації методом золотого перетину (Фібоначчі). Оператор покоординатної мутації застосовує нормальний або поліноміальний закони розподілу ймовірностей. При цьому, якщо клон породжений кліткою з висо- кою афінністю, вищою є ймовірність «вузької» поліноміальної мутації, що відповідає інтенсивному локального пошуку. Клон, породжений клітиною зі слабкою афінністю, має більшу ймовірність «широкої» мутації з відхиленням за законом Гауса. Результати дослідження показують високу ефективність запропонованого алгорит- му для стандартних цільових функцій, що мають розмірність до 100, а також при вирі- шенні завдань навчання нейронних мереж прямого поширення. Основні переваги запропонованого алгоритму полягають у тому, що він залишаєть- ся ефективним при зростанні розмірності задачі, знаходить не одне рішення, а їх множи- ну (альтернативи) та використовує значно менше часу (на порядок) для порівняного розв’язання задачі. Література 1. Lucinska M. Hybrid Immune Algorithm for Multimodal Function Optimization : [текст] / M. Lucinska, S.T. Wierzchon // Recent Advances in Intelligent Information Systems. – 2009. – Р. 301-313. 2. Rowan T.H. Functional Stability Analysis of Numerical Algorithms, Ph.D. Thesis, Department of Com- puter Sciences / T.H. Rowan [Електронний документ (ресурс)]. – University of Texas at Austin, 1990. – Режим доступу за URL : http://reference.kfupm.edu.sa/content/f/u/ func- tional_stability_analysis_of_numeric_1308737.pdf 3. De Castro L. An Artificial Immune Network for Multimodal Function Optimization : [текст] / L.N. De Castro, J. Timmis // Proceedings of IEEE Congress on Evolutionary Computation (CEC'02). – 2002. – Vol. 1. – Р. 699-674. 4. Yildiz A.R. A novel hybrid immune algorithm for global optimization in design and manufacturing : [текст] // Robotics and Computer-Integrated Manufacturing. – 2009. – Vol. 25. – Р. 261-270. 5. Brownlee J. Clonal Selection Algorithms : [Текст] / J. Brownlee // Technical Report 070209A, Complex Intelligent Systems Laboratory (CIS), Centre for Information Technology Research (CITR), Faculty of Information and Communication Technologies (ICT), Swinburne University of Technology, 2007. 6. Kelsey J. Immune Inspired Somatic Contiguous Hypermutation for Function Optimisation / J. Kelsey, J. Timmis [Електронний документ (ресурс)]. – 2003. – Режим доступу за URL : http://www.cs.york.ac.uk/rts/docs/ GECCO_2003/papers/2723/ 27230207.pdf. 7. Chen J. A hybrid immune multiobjective optimization algorithm : [текст] / Jianyong Chen, Qiuzhen Lin, Zhen Ji // European Journal of Operational Research. – 2010. – Vol. 204. – Р. 294-302. 8. Карпенко А.П. Гибридный метод глобальной оптимизации на основе искусственной иммунной системы : [текст] / А.П. Карпенко, Д.Л. Шуров // Инженерное образование. – 2012. – № 8. 9. de França F.O. An artificial immune network for multimodal function optimization on dynamic environ- ments : [текст] / F.O. de França, F.J.V. Zuben, L.N. de Castro // In: Proc. of GECCO. – ACM Press, New York. – 2005. – Р. 289-296. 10. Gong M. Multiobjective immune algorithm with nondominated neighbor-based selection / Maoguo Gong, Licheng Jiao, Haifeng Du, Liefeng Bo // Evolutionary Computation. – 2008. – Vol. 16(2). – Р. 225-255. 11. Снитюк В.Є. Спрямована оптимізація і особливості еволюційної генерації потенційних розв’язків : [текст] / В.Є. Снитюк // VI міжнародна школа-семінар «Теорія прийняття рішень», Ужгород, 1 – 6 жовтня 2012 р. – Ужгород : «Інвізор», 2012 – С. 182-183. 12. Желдак Т.А. Метод моделювання штучної імунної системи в задачах оптимізації мультимодальних функцій : [текст] / Т.А. Желдак // Обчислювальний інтелект (результати, проблеми, перспективи) : Матеріали 2-ї міжнар. наук.-техн. конф. 14 – 17 травня 2013 р. – Черкаси : Маклаут, 2013. – С. 33-36. Literaturа 1. Lucinska M., Wierzchon S.T. Recent Advances in Intelligent Information Systems, 2009, pp. 301-313. Желдак Т.А., Слєсарєв В.В. «Искусственный интеллект» 2013 № 4 112 2Ж 2. Rowan T.H. Ph.D. Thesis, Department of Computer Sciences, University of Texas at Austin, 1990. URL: http://reference.kfupm.edu.sa/content/f/u/functional_stability_analysis_of_numeric_1308737.pdf 3. De Castro L.N., Timmis J. Proceedings of IEEE Congress on Evolutionary Computation (CEC'02). 2002. – vol. 1. – Р. 699-674. 4. Yildiz A.R. Robotics and Computer-Integrated Manufacturing. – 2009. – vol. 25. – Р. 261-270. 5. Brownlee J. Technical Report 070209A, Complex Intelligent Systems Laboratory (CIS), Centre for In- formation Technology Research (CITR), Faculty of Information and Communication Technologies (ICT), Swinburne University of Technology, 2007. 6. Kelsey J., Timmis J. Immune Inspired Somatic Contiguous Hypermutation for Function Optimisation. 2003. URL: http://www.cs.york.ac.uk/rts/docs/GECCO_2003/papers/2723/27230207.pdf . 7. Chen J., Q. Lin, Zh. Ji European Journal of Operational Research. 2010. Vol. 204. pp. 294-302. 8. Karpenko A.P., Shurov D.L. Inzhenernoe obrazovanie. – 2012. – Vol. 8. 9. F.O. de França, F.J.V. Zuben, L.N. de Castro In: Proc. of GECCO. ACM Press, New York. 2005. pp. 289-296. 10. Gong, M., Jiao, L., Du, H., & Bo, L. Evolutionary Computation. – 2008. – Vol. 16(2). – Р. 225-255. 11. Snytyuk V.Y. VI Mizhnarodna shkola-seminar «Teorija pryjnjattja rishen». Uzhgorod, 1 – 6 zhovtnja 2012. – Uzhgorod, Invizor. – 2012. – s. 182-183. 12. Zheldak T.A. Obchysljuvalnyj Intelekt (rezultaty, problem, perspektyvy). Materialy 2d mizhnarodnoji konferenciji 14 – 17 travnja 2013 r. – Cherkasy : Maklaut, 2013. – s. 33-36. RESUME T.A. Zheldak, V.V. Slesarev The Algorithm of Artificial Immune System Simulation with Saaty Selection Operator and One-dimensional Local Search In the article the basic modern algorithm that implement the artificial immune systems simulation method is considered. Also advantages and disadvantages of this algorithms are ana- lyzed. Using a hybrid adaptive immune algorithm that includes the clonal selection, crossover, mutation and limited adaptive local search is proposed as a new algorithm. Selection is carried out by estimating the solutions suitability using the Saaty Analytic Hi- erarchy Process (AHP). The higher is the affinity of the cells, which describes the solution, the more number of clones, the cell will provide the next generation. The investigation shows that the proposed selection operator is more effective than the tra- ditional operators, such as the tournament, roulette and uniform with cut-off. Furthermore, this selection method is only mathematically justified. Twin adaptive cell clones crossover provides an intensification of local search and allows to combine the genes of two the best successful decisions of previous generations. To improve the focus of the search the one-dimensional optimization operator based on the method of golden ratio (named Fibonacci) is applied to a random coordinate of clone cells. The crossover and local search operators are applied to the clone cells with a certain prob- ability, which can also change adaptively during the work of the algorithm. Coordinatewise mutation operator with the normal and polynomial probability distribu- tions applies. Moreover, if a clone is generated by a cell with high affinity, narrow polynomial mutation is more likely for it. It corresponds to intensive local search. If a clone is generated by a cell with a weak affinity, a broad mutation with the Gaussian distribution is more tredible. The results show the high efficiency of the proposed algorithm for standard objective func- tions with less than 100 dimensions, as well as for solving the problem of feedforward neural networks training. Стаття надійшла до редакції 27.06.2013.

Алгоритм моделювання штучної імунної системи з селективним оператором Сааті та одновимірним локальним пошуком

Institution

Ähnliche Einträge