Using genetic algorithms in intelligent recognition systems.pdf В интеллектуальных системах формирование и выбор «хороших» [1] безус-ловных безызбыточных диагностических тестов (ББДТ) являются одними из наи-более важных шагов при принятии решений, поскольку от свойств используемыхтестов существенно зависит качество получаемых решений. Идея использованиягенетических алгоритмов (ГА) для построения ББДТ при большом признаковомпространстве предложена в статьях [2 - 4]. Первые алгоритмы построения ББДТ,описанные в [2 - 4], программно реализованы и развиты в плане оптимизации по-строения в последующих работах Янковской А.Е., Блейхер А.М. и др. [5 - 7].Однако выбор «хороших» ББДТ не всегда приводит к оптимальному решению,поскольку общее количество признаков в выбранном множестве тестов можетбыть слишком большим, так же как временные и стоимостные затраты или ущерб(риск) [8], наносимый в результате выявления значений признаков исследуемогообъекта, например в медицине. В связи с этим предложено применение ГА дляпостроения ББДТ, a также и для формирования субоптимального относительновыбранных критериев подмножества ББДТ.1. Определения и обозначенияВоспользуемся определениями и обозначениями, необходимыми для поста-новки задачи и при дальнейшем изложении [3, 4].Тестом называется совокупность признаков, различающих любые пары объек-тов, принадлежащих разным образам (классам). Тест называется безызбыточным,если при удалении любого признака тест перестает быть таковым. Признак назы-вается обязательным, если он содержится во всех безызбыточных тестах. При-знак называется псевдообязательным, если он не является обязательным и входитво множество используемых при принятии решений безызбыточных тестов.Пусть T = {tij : i = 1,...,n, j = 1,...,m} - матрица ББДТ, n - количество ББДТ, m -количество характеристических признаков, булевой строкой Ti представлен i-й1 Работа выполнена при поддержке РФФИ (проект № 07-01-00452) и РГНФ (проект № 06-06-12603В).Применение генетических алгоритмов в интеллектуальных распознающих системах 77ББДТ. Тем же символом Ti будем обозначать подмножество характеристическихпризнаков, вошедших в ББДТ. Обозначим через z = {z j : j = 1,...,m} - множествохарактеристических признаков, причем tij = 1Ўк z j ЎфTi , иначе tij равно нулю. Длякаждого признака zj зададим весовой коэффициент wj и коэффициенты стоимостиwЎЗj и ущерба (риска) wЎЗjЎЗ [8]. Далее будем использовать термины «вес», «стои-мость» и «ущерб» признака вместо соответственно «весовой коэффициент при-знака, характеризующий его разделяющую способность», «коэффициент стоимо-сти признака, определяющий стоимость выявления его значения» и «коэффициентущерба, причиняемого в результате выявления значения признака».Определим вес i-го теста:i jijjW =ҐТw t .Аналогично определяются значения стоимости и ущерба теста.2. Постановка задачиДана матрица тестов T с заданными весами, стоимостью и ущербами призна-ков. Необходимо выделить такую подматрицу T0, содержащую n0 строк, чтобысоответствующее ей множество тестов N0обеспечивало выполнение следующихкритериев в порядке их следования:1) во множестве N0 должно содержаться максимальное число псевдообяза-тельных признаков;2) множество N0 должно содержать минимальное общее число признаков;3) множество N0 должно иметь максимальный суммарный вес;4) множество N0 должно иметь наименьшую суммарную стоимость;5) множестве N0 должно иметь наименьший суммарный ущерб.Поскольку критерии могут противоречить друг другу в зависимости от рас-сматриваемой прикладной задачи, то искомая подматрица может включать субоп-тимальное подмножество ББДТ. Приоритеты критериев также зависят от рас-сматриваемой задачи.3. Генетический алгоритмДля решения поставленной задачи предлагается использовать ГА, представ-ляющий итерационный вероятностный эвристический алгоритм поиска. Отличи-тельной особенностью ГА является одновременная работа со множеством точек(популяцией) из пространства потенциальных решений. Каждое возможное реше-ние представлено булевой хромосомой (строкой) длины n, каждый i-й символ ко-торой кодирует включение i-го диагностического теста в итоговое подмножество.Будем вычислять приспособленность k-й особи fk c хромосомой h путемоценки качества соответствующей подматрицы T0 (h) в соответствии с выраже-нием [8]:( )5( ) 201v k 100 ( )k k hkf e U n==ҐТ + h − , f Ўжmin ,где vk - весовой коэффициент k-го критерия, соответствующий его значимости;U(h) - количество единичных разрядов в булевой строке h ; M(c) - количествоединичных столбцов в подматрице T0 (h) , M(d) - количество ненулевых столбцов78 А.Е. Янковская, Ю.Р. Цойв подматрице T0 (h) ; (k )eh - функция штрафа за невыполнение k-го критерия:(1) ( )he m M c ,m−= (2) ( )he M d ,m= (3) ( ) ( 0 ( ))( )W WhWS Se ,S−= T ThT(4) ( 0 ( ))( )WhWSe ,SЎЗЎЗ= T hT(5) ( 0 ( ))( )WhWSeSЎЗЎЗЎЗЎЗ= T hT,где SW (ƒ), SWЎЗ (ƒ) и SWЎЗЎЗ (ƒ) - соответственно суммарный вес, стоимость иущерб по всем тестам множества, соответствующего матрице ƒ (ƒЎф{T,T0 (h)}).Отметим, что выбор значений штрафов зависит от рассматриваемой приклад-ной задачи.4. Результаты экспериментовИсследование особенностей использования ГА для решения поставленной за-дачи проведено с использованием псевдослучайных матриц тестов размерностями1000  50, 1000  100, 1000  200, 1000  300, 1000  400, 1000  500, 2000  500.Элементы матриц определяются псевдослучайным образом, после чего произво-дится удаление поглощающих строк. Значения весов, стоимостей и ущербов при-знаков также определяются как псевдослучайные величины, равномерно распре-деленные в интервале [0; 1]. Мощность n0 искомого подмножества тестов для всехэкспериментов примем равной 300, что соответствует опыту решения задач в рядепроблемных и междисциплинарных областей (медицина, геология, экобиомеди-цина, экономика, психология и др.).Отметим, что псевдослучайное заполнение матриц тестов соответствует отсут-ствию корреляции между характеристическими признаками, что приводит к ми-нимизации числа возможных закономерностей в исходной матрице тестов. В силуэтого использование псевдослучайных матриц тестов представляет более слож-ную по сравнению с реальной задачу.Значения штрафов установлены следующим образом: v1 = 40, v2 = 30, v3 = 15,v4 = 10, v5 = 5. Отметим, что используемые значения штрафов выбраны безотно-сительно прикладной задачи. Основным критерием их выбора является соответст-вие приоритету критериев оптимизации, сформулированных выше. Рассматрива-ется ГА с турнирной селекцией при размере турнира равном 6, двухточечнымоператором кроссинговера, битовой мутацией и 1 элитной особью. По итогам 100независимых запусков для каждой из рассматриваемых матриц будем оцениватьрезультаты как по полученному лучшему значению функции приспособленности,так и по следующим критериям, сформулированным в [9] и характеризующимстабильность решений, полученных в различных запусках:1. Критерию стабильности, учитывающему частоту pi встречаемости i-го тес-та во всех решениях, полученных по результатам 100 запусков ГА. Чем большеколичество тестов, для которых значение pi равно или близко к 1, тем выше схо-димость алгоритма.2. Суммарному количеству ҐШ ББДТ, не вошедших в полученные решения.Чем больше ҐШ , тем выше сходимость алгоритма.Представленные критерии стабильности и сходимости будут использоватьсядля оценки работы ГА, и их введение не продиктовано особенностями используе-мых матриц ББДТ.Применение генетических алгоритмов в интеллектуальных распознающих системах 79Полученные лучшие значения целевой функции, усредненные по 100 запускам,для различных матриц ББДТ в зависимости от размера популяции показаны нарис. 1. Поскольку рассматривается задача минимизация целевой функции, то можноотметить улучшение результатов при увеличении размера r популяции, однакоэто улучшение весьма незначительно, в большинстве случаев порядка 10-2.83,683,88484,284,484,684,885Размерность матрицы тестовЗначение целевой функцииr = 20 84,35 84,6 84,8 84,86 84,86 84,88 84,92r = 50 84,14 84,51 84,66 84,77 84,76 84,8 84,88r = 100 84,1 84,48 84,64 84,75 84,74 84,79 84,85r = 200 84,08 84,47 84,63 84,75 84,74 84,78 84,841000Ўї50 1000Ўї100 1000Ўї200 1000Ўї300 1000Ўї400 1000Ўї500 2000Ўї500Рис. 1. Результаты решения поставленной задачи в зависимости от размера популяциидля псевдослучайных матриц различной размерностиОтметим, что время работы ГА в зависимости от размера популяции зависитлинейно (рис. 2). Исходя из этого, при решении рассматриваемой задачи повыше-ние размера популяции во многих случаях приводит к неоправданному росту вы-числительной сложности.05010015020025050 100 150 200 250Размер популяцииВремя работы запуска, сРис. 2. Зависимость времени работы запуска ГА от размера популяции80 А.Е. Янковская, Ю.Р. ЦойЗависимость количества тестов от частоты их встречаемости для матриц1000  50 и 1000  500 в полученных решениях представлена на рис. 3, r - обо-значает размер популяции. По оси абсцисс отложен процент встречаемости тес-тов, а по оси ординат - соответствующее количество тестов. Видно, что с ростомразмера популяции сходимость увеличивается, так как растет количество тестов,встречающихся во всех решениях.Отметим, что в случаях, когда количество тестов, встречающихся в большин-стве решений, существенно меньше мощности n0 искомого подмножества тестов,размер популяции является недостаточным. Примером является случай использо-вания популяции из 20 особей при исходной матрице 1000  500, график для ко-торого показан на рис. 3, б. Также заметим, что с увеличением количества при-знаков в исходной матрице тестов сложность задачи увеличивается, что видно изсравнения графиков на рис. 3, а и б.100% >=95% >=90% >=80% >=70% >=60% >=50% =95% >=90% >=80% >=70% >=60% >=50% =95% >=90% >=80% >=70% >=60% >=50% =95% >=90% >=80% >=70% >=60% >=50%

Скачать электронную версию публикации