Главная Контакты Добавить в избранное Авторы Вопросы и ответы
,

УДК 519.71

КОМПЬЮТЕРНАЯ СИСТЕМА ДЛЯ РЕШЕНИЯ ЗАДАЧ КЛАССИФИКАЦИИ НА ОСНОВЕ МОДИФИЦИРОВАННЫХ ИММУННЫХ АЛГОРИТМОВ

Литвиненко В.И., Дидык А.А., Захарченко Ю.А.

Введение. Искусственные иммунные системы (ИИС) являются новым направлением в исследованиях вычислительного интеллекта (ВИ). В настоящее время существует определенное число моделей ИИС, которые используются для решения задач распознавания образов, обнаружения отказов, компьютерной безопасности и многих других приложений [1]. Среди различных механизмов биологической иммунной системы при разработке ИИС наиболее часто используются модель иммунной сети и клональный отбор [2].

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

Искусственные иммунные системы для решения задач распознавания. В настоящее время существует ряд компьютерных систем предназначенных для решения задач классификации на основе иммунных алгоритмов. К наиболее известным можно отнести WEKA (Waikato Environment for Knowledge Analysis) [5]. Система, основанная на использовании нейронной сети и искусственной иммунной сети для решения задач классификации (http://wekaclassalgos.sourceforge.net/), также включает реализованный на данной платформе Джейсоном Браунли [6] алгоритм клонального отбора. Система реализована на языке Java.

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

Постановка задачи классификации. Для формальной постановки задачи классификации вектор признаков  является описанием объектов, которое является модулем преобразования. Классом называется некоторое подмножество  множества . Обучающей выборкой называется набор , для которых , то есть это известная информация об отображении . Задача классификации заключается в построении функции классификации, приближающей отображение , основываясь на обучающей выборке .

В ИИС антитела (детекторы) и антигены (данные) имеют формальное представление в виде векторов координат (атрибутов):  для антитела и  для антигена. Без потери общности допустим, что данные вектора имеют одинаковый размер. В этом случае под аффинностью связей антител друг с другом или антител с антигенами понимается расстояние между соответствующими векторами атрибутов, которое выражается в виде скалярного неотрицательного значения: , определяющего степень соответствия между молекулами (векторами атрибутов). Причем, при использовании оговоренной выше степени подобия форм, получается, что чем меньше расстояние между индивидуумами, тем выше их аффинность друг к другу. Значение расстояния может быть вычислено при помощи любой из приведенных ниже метрик:

- евклидово расстояние  (используется при вещественном или целочисленном кодировании атрибутов)

;

(1)

- манхэттенское расстояние  (также используется при вещественном или целочисленном кодировании)

.

(2)

Более детально теория  клонального отбора и искусственной иммунной сети, их формальное представление и алгоритмы описаны в работах [2,3,4].

Модифицированный алгоритм клонального отбора. Пошаговая реализация алгоритма клонального отбора представлена на рис.1. Основным отличием данной реализации алгоритма от классической для решения задач классификации есть оператор мутации. В связи с большим объемом данных при решении задач распознавания мы столкнулись с проблемой быстроты работы алгоритма.

 

 

Рис. 1 Алгоритм клонального отбора для решения задач классификации

 

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

 

(3)

(4)

Формула (3) используется в случае, если расстояние между антителом и антигеном вычисляется как Евклидово расстояние, формула (4) – если расстояние вычисляется как Манхеттеновское расстояние. Весовой коэффициент назначается гену на каждом шаге мутации: – ген антитела , для которого определяется вес; – ген антитела ; – ген антигена ; – ген антитела , который не соответствует гену  (т.е. ; ; ). С целью оптимизации процесса обучения иммунной сети и формирования клеток памяти, а также для ускорения работы алгоритма клонального отбора, для формирования пула клонов при выполнении операции клонирования использовался фактор умножения. В нашей реализации n антител с самой высокой афинностью перед процессом клонирования сортировались в порядке возрастания. Таким образом, общее количество клонов, сгенерированных для всех этих n выбранных антител, устанавливалась в соответствии с формулой (5):

,

(5)

где Nc – общая сумма клонов, произведенных для каждого из антигенов; b - фактор умножения; N – общая сумма антител; round – оператор, который округляет аргумент к самому близкому целому числу. Каждый слагаемый этой суммы соответствует размеру клона каждого отобранного антитела, например, для N=100 и b=1, антитело с самой высокой афинностью (i=1) производит 100 клонов, в то время как второе по афинности антитело производит 50 клонов и т.д.

Модифицированный алгоритм иммунной сети. Иммунная сеть математически может быть представлена в виде графа, причем необязательно полносвязного, который состоит из множества узлов - клеток сети (антител) и множества взвешенных ребер, означающих связи между клетками. Значение веса ребра соответствует аффинности связи клеток друг с другом. В иммунных сетях различают два вида аффинности:

- аффинность связи «антиген-антитело» (Ag-Ab) – степень различия;

- аффинность связи «антитело-антитело» (Ab-Ab) – степень подобия.

Структура компьютерной системы. Блок интерфейсов. Включает интерфейс оператора (системного программиста). Данный блок выполняет следующие основные функции:

- ввод данных;

- вывод информации о результатах тестирования;

- управление процессом тестирования;

- настройку параметров подсистемы обучения искусственной иммунной сети.

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

Блок обработки результатов обучения ИИС. Осуществляет формирование статистической отчетности по результатам обучения искусственной иммунной сети на всех его этапах и созданию пула клеток памяти. К такой отчетности относится статистика созревания аффинности на каждой итерации обучения сети, количество клеток памяти сети и т.д.

 

 

 

Рис. 2 Алгоритм искусственной иммунной сети для решения задач классификации.

 

База данных ИИС. База данных хранит следующие элементы:

- клетки памяти искусственной иммунной сети для соответствующей задачи классификации;

- статистические данные, полученные в процессе обучения искусственной иммунной сети.

Блок диспетчера тестирования ИИС. Блок имеет следующие функциональные характеристики:

- загрузка тестирующих записей из внешней базы данных;

- прогонка работы ИИС на загруженных данных;

- формирование отчетности по результатам решения задачи классификации.

Модульная структура системы. На рис. 4 показана модульная структура ИС для решения задачи классификации.

 

Рис. 3 Концептуальная структура компьютерной системы

 

Рис. 4 Модульная структура системы

 

Модуль ais.dll содержит библиотеку классов ИИС. Каждый контролируемый параметр системы использует отдельный экземпляр ИИС. Модуль td.dll выполняет задачу проведения проверки работы ИИС на решение задачи классификации. В его функции входит получение и обработка записей для классификации из внешней базы данных и формирование результатов тестирования. Данные накапливаются в базе и выбираются оттуда по мере необходимости посредством запросов из модуля ais.dll. Модуль ui.dll является графическим интерфейсом ИС. Для хранения баз данных используются электронные таблицы в формате CSV.

Функционирование программы и параметры настройки. Используются следующие параметры для обучения :

The size of population – размер популяции антител, формируемый на каждом шаге итерации для каждого индивидуума из обучающей выборки;

 

 

Рис.5 Общий вид интерфейса системы

 

Number of the best individums – число антител с наилучшей афинностью из популяции антител, которое не будет заменено на следующем шаге итерации случайными числами. Расачитывается как процентное соотношение от размера популяции антител.

Number of generations – число генераций для каждого антитела из обучающей выборки.

 Mutation factor – фактор мутации антитела, который влияет на скорость приближения генерируемого антитела к обучающему. Допускается значение фактора в пределе 1-30. Чем больше значение фактора мутации, тем больше значение, на которое изменяется антитело на шаге мутации:

 

(5)

 

где ρ – параметр контролирующий сглаживание инверсии экспоненциала, D* - норамлизированная афинность, расчитанная как D*=D/Dmax.

Input e – нормированный порог аффинности.

Mutation percent – параметр, задающий процент гипермутации антитела. Задается в процентном соотношении. Указывает число генов антитела, которые подлежат мутации. Количество изменяемых генов расчитывается следующим образом:

 

(6)

 

где MG – количество изменяемых генов, МР – заданный процент от общего количества генов антитела, round – оператор, который округляет аргумент к самому близкому целому числу.

Beta koef – фактор умножения для операции клонирования. Общее количество клонов, сгенерированных для всех n выбранных антител, устанавливалась в соответствии с формулой (5).

Mutation updating – включатель процедуры модифицированной мутации антител. Для ускорения процесса мутации было предложено для каждого гена антитела устанавливать весовой коэффициент формулы (3) и (4).

 

 

Рис.6 Интерфейс настройки основных параметров
клонального алгоритма и искусственной иммунной сети

 

Affinity updating – включатель процедуры модифицированного расчета афинности антител. Афинность расчитывается по следующей формуле:

(10)

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

Distance – вычисление расстояний между антителами:

Evklid – Эвклидово расстояние (1); Manhetten – Манхеттеновское расстояние (2).

The mutation formula – формула, по которой производится мутация антитела. Имеет следующие варианты выбора:

Fast convergence : ;

– Affinity proportional mutation: ;

– Somatic mutation : ;

где сj – мутируемый антиген, α – коэффициент мутации, N(0, α) – функция случайного распределения в диапазоне (0, α); Td () – порог смертности для антител в клетках памяти иммунной сети; Ts () – порог суппрессии.

 

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

 

In article the computer system for the decision of problems of classification on the basis of the modified algorithms of an immune network and algorithm clonal selection is described. The architecture of system, program modules and parametres of adjustment of algorithms of training is described.

 

1.         De Castro, L. N. & Timmis, J. I. Artificial Immune Systems: A New Computational Intelligence Approach, , London: Springer-Verlag 200o), September,  357 p.

2.         Бідюк П.І. Литвиненко В.І. Фефелов. А.О. Формалізація методів побудови штучних імунних мереж// Наукові вісті НТУУ “КПІ”. 2007 р.–C.29-41

3.         Литвиненко В.И. Искусственные иммунные системы как средство индуктивного построения оптимальных моделей сложных объектов // Проблемы управления и информатики. –. 2008.– № 3.– с. 43-61.

4.         Литвиненко В. И.  Иммунный классификатор для решения задач бинарной классификации (теоретические основы) //Системні технології. Регіональний міжвузівський збірник наукових праць. Випуск 1(42). –Дніпропетровськ, 2006. с.114-130.

5.         http://sourceforge.net/projects/weak

6.         Brownlee J. Clonal Selection Theory & CLONALG - The Clonal Selection Classification Algorithm (CSCA) // Victoria, Australia: Centre for Intelligent Systems and Complex Processes (CISCP), Faculty of Information and Communication Technologies (ICT), Swinburne University of Technology; 2005 Jan; Technical Report ID: 2-01.

 

 





Ответы на вопросы [_Задать вопроос_]

Информационно-измерительные системы

Ковальов О.І. Вимірювання у процесно-орієнтованих стандартах

Полякова М.В., Ищенко А.В., Худайбердин Э.И. Порогово-пространственная сегментация цветных текстурированных изображений на основе метода JSEG

Дзюбаненко А. В. Организация компьютерных систем для анализа изображений

Гордеев Б.Н., Зивенко А.В., Наконечный А.Г. Формирование зондирующих импульсов для полиметрических измерительных систем

Богданов А.В., Бень А.П., Хойна С.И. Релаксация обратного тока диодов Шоттки после их магнитно-импульсной обработки (МИО)

Тверезовский В.С., Бараненко Р.В. Проектирование измерителя добротности варикапов

Тверезовский В.С., Бараненко Р.В. Оптимизированная модель измерителя доб-ротности варикапов

Руднєва М.С., Кочеткова О.В., Задорожній Р.О. Принципи побудови оптимальної структури інформаційно-вимірювальної системи геометричних розмірів об’єктів в діапазоні від 1 нм до 1000 нм

Биленко М.С., Рожков С.А., Единович М.Б. Идентификация деформаций пе-риодических структур с использованием систем технического зрения

Рашкевич Ю.М., Ковальчук А.М., Пелешко Д.Д. Афінні перетворення в модифікаціях алгоритму RSA шифрування зображень

Дидык А.А., Фефелов А.А, Литвиненко В.И., Шкурдода С.В., Синяков Ф. В. Классификация масс-спектров с помощью кооперативного иммунного алгоритма

Клименко А.K. Обратная модель для решения задач в системах с многосвязными динамическими объектами

Завгородній А.Б. Порівняльне дослідження твердотільних і рідиннофазних об'єктів методом газорозрядної візуалізації

Голощапов С.С., Петровский А.В., Рожко Ж.А., Боярчук А.И. Измерение доб-ротности колебательного контура на основе метода биения частот

Кириллов О.Л., Якимчук Г.С. Диагностирование критерия безопасности при заполнении замкнутых объемов СПЖ косвенным методом

Долина В.Г. Проблеми підвищення точності рефрактометра на основі прозорих порожнистих циліндрів.

Самков О.В., Захарченко Ю.А. Застосування алгоритму клонального відбору для побудови планів модернізації авіаційної техніки

Попов Д.В. Метод формування регламентів технічного обслуговування повітряних суден

Казак В.М., Чорний Г.П., Чорний Т.Г. Оцінювання готовності технічних об’єктів з урахуванням достовірності їх контролю

Тверезовский В.С., Бараненко Р.В. Технические аспекты проектирования цифрового измерителя добротности варикапов

Тверезовский В.С., Бараненко Р.В. Технические аспекты проектирования устройства для разбраковки варикапов по емкостным параметрaм и добротности

Сосюк А.В. Інтелектуальний автоматизований контроль знань в системах дистанційного навчання

Соколов А.Є. Деякі аспекти систезу комп’ютеризованої адаптивної системи навчання

Полякова М.В., Волкова Н.П., Іванова О.В. Сегментація зображень стохастичних текстур амплітудно-детекторним методом у просторі вейвлет-перетворення

Луцкий М.Г., Пономаренко А.В., Филоненко С.Ф. Обработка сигналов акустической эмиссии при определении положения сквозных дефектов

Лубяный В.З., Голощапов С.С. Прямоотсчетные измерители расхождений емкостей

Беляев А.В. Построение навигации для иерархических структур в WEB-системах и системах управления WEB-сайтом

Терновая Т.И., Сумская О.П., Слободянюк И.И., Булка Т.И. Контроль качества тканей специального назначения с помощью автоматических систем.

Шеховцов А.В. Інформаційний аспект: розпізнавання образів індивідуума.

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

Литвиненко В.И. Прогнозирования нестационарных временных рядов с помощью синтезируемых нечетких нейронных сетей

Ковриго Ю.М., Мисак В.Ф., Мовчан А.П., Любицький С.В. Автоматизована система діагностики генераторів електростанцій

Браїловський В.В., Іванчук М.М., Ватаманюк П.П., Танасюк В.С. Керований детектор імпульсного ЯКР спектрометра

Забытовская О.И. Построение функции полезности по экспериментальным данным.

Шиманські З. Апаратні засоби сегментації мовного сигналу

Хобин В.А., Титлова О.А. К вопросу измерения парожидкостного фронта в дефлегматоре абсорбционно-диффузионной холодильной машины (АДХМ)

Фефелов А. А. Использование байесовских сетей для решения задачи поиска места и типа отказа сложной технической системы

Слань Ю. М., Трегуб В. Г. Оперативна нейромережна ідентифікація складних об’єктів керування

Ролик А.И. Модель управления перераспределением ресурсов информационно-телекоммуникационной системы при изменении значимости бизнес-процессов

Кириллов О.Л., Якимчук Г.С., Якимчук С.Г. Изучение электрического поля с помощью датчика измерителя электростатического потенциала на модели замкнутого металлического объема

Грицик В.В. Застосування штучних нейронних мереж при проектуванні комп’ютерного зору.

Гасанов А.С. Информационные технологии построения систем прогнозирования отказов

Шеховцов А.В., Везумский А.К., Середа Е.С. Алгоритм сжатия информации без потерь: модифицированный алгоритм LZ77

Ходаков В.Е., Жарикова М.В., Ляшенко Е.Н. Методы и алгоритмы визуализации пространственных данных на примере моделирования распространения лесных пожаров.

Полякова М.В., Крылов В.Н. Обобщённые масштабные функции с компактным носителем в задаче сегментации изображений упорядоченных текстур. – C. 75 – 84.

Полторак В.П., Дорогой Я.Ю. Система распознавания образов на базе нечеткого нейронного классификатора.

Литвиненко В.И. Синтез радиально-базисных сетей для решения задачи дистанционного определения концентрации хлорофилла.

Бражник Д.А. Управление совмещением изображения объекта в сцене и эталонного изображения.

Бабак В.П., Пономаренко А.В. Локализация места положения сквозных дефектов по сигналам акустической эмиссии.

Мороз В. В. R-D проблема и эффективность систем сжатия изображений.

Крылов В.Н., Полякова М.В., Волкова Н.П. Контурная сегментация в пространстве гиперболического вейвлет-преобразования с использованием математической морфологии.

Квасников В.П., Баранов А.Г. Анализ влияния дестабилизирующих факторов на работу биканальной координатно-измерительной машины.

Казак В.М., Гальченко С.М., Завгородній С.О. Аналіз можливості застосування імовірнісних методів розпізнавання для виявлення пошкоджень зовнішнього обводу літака.

Тищенко И.А., Лубяный В.З. Управление коммутационными процессами в интегрированных сетях связи.

Корниенко-Мифтахова И.К.,Филоненко С.Ф. Информационно-измерительная система для анализа характеристик динамического поведения конструкций.

Тверезовский В.С., Бараненко Р.В. Модель измерителя емкости с линейной шкалой измерений.

Полякова М.В., Крылов В.Н. Мультифрактальный метод автоматизированного распознавания помех на изображении.

Рожков С.О., Федотова О.М. Алгоритм розпізнавання дефектів тканин для автоматичної системи контролю якості.

Бражник Д.А. Использование проективного преобразования для автоматизации обнаружения объектов.

Ходаков В.Є., Шеховцов А.В., Бараненко Р.В. Математичні аспекти створення автоматизованої системи „Реєстр виборців України”