Янковская А. Е. Томский государственный архитектурно-строительный университет icon

Янковская А. Е. Томский государственный архитектурно-строительный университет



НазваниеЯнковская А. Е. Томский государственный архитектурно-строительный университет
Дата конвертации25.10.2012
Размер445 b.
ТипРеферат


Генетический алгоритм и его модификация для формирования оптимального подмножества тестов

  • Янковская А.Е.

  • Томский государственный архитектурно-строительный университет

  • yank@tsuab.ru

  • Цой Ю.Р.

  • Томский политехнический университет

  • qai@mail.ru


Содержание доклада

  • 1. Введение

  • 2. Постановка задачи

  • 3. Генетический алгоритм

  • 4. Результаты экспериментов

  • 5. Модифицированный алгоритм

  • 6. Заключение



1. Введение

  • Формирование и выбор «хороших» [1] безусловных безызбыточных диагностических тестов (ББДТ) является одним из наиболее важных при принятии решений в интеллектуальных системах, поскольку от свойств используемых тестов существенно зависит качество получаемых решений. Идея использования генетических алгоритмов (ГА) для построения ББДТ при большом признаковом пространстве предложена в статьях [2, 3, 4]. Первые алгоритмы построения ББДТ, описанные в [2, 3], программно реализованы и развиты в плане оптимизации построения в последующих работах Янковской А.Е. и Янковской А.Е. с Блейхер А.М. [5, 6].



1. Введение

  • Выбор «хороших» безызбыточных диагностических тестов является одним из наиболее важных при принятии решений в интеллектуальных системах. Однако, этот выбор не всегда приводит к оптимальному решению.



2. Основные понятия. Постановка задачи

  • Тестом называется совокупность признаков, различающих любые пары объектов, принадлежащих разным образам (классам).

  • Тест называется безызбыточным, если при удалении любого признака тест перестает быть тестом.

  • Признак называется обязательным, если он содержится во всех безызбыточных тестах.

  • Признак называется псевдообязательным, если он не является обязательным и входит во множество используемых при принятии решений безызбыточных тестов.



2. Основные понятия. Постановка задачи

  • Пусть – матрица ББДТ, n – количество ББДТ, m – количество характеристических признаков. соответствует i-му ББДТ (i-я строка матрицы Т). Обозначим через

  • – множество характеристических признаков, причем . Для каждого признака zj зададим весовой коэффициент wj и коэффициенты стоимости и ущерба (риска) .



2. Основные понятия.
Постановка задачи

  • Строки матрицы сопоставлены тестам, столбцы – признакам.

  • При решении практических задач количество тестов и признаков может принимать значения от нескольких десятков до нескольких десятков тысяч.



2. Основные понятия. Постановка задачи

  • Для данной матрицы Т с заданными весами, стоимостью и ущербами признаков, необходимо выделить такую подматрицу Т0, содержащую n0 строк, чтобы соответствующее ей множество тестов N0 обеспечивало выполнение следующих критериев в порядке их следования:

  • 1. В выбранном множестве тестов N0 мощности n0 должно содержаться максимальное число псевдообязательных признаков.

  • 2. Выбранное множество тестов N0 должно содержать минимальное общее число признаков.

  • 3. Выбранное множество тестов N0 должно иметь максимальный суммарный вес.

  • 4. Множество выбранных тестов N0 должно иметь наименьшую суммарную стоимость.

  • 5. Множество выбранных тестов N0 должно иметь наименьший суммарный ущерб.



3. Генетический алгоритм

  • Эволюционные вычисления (evolutionary computation) – раздел мягких вычислений (soft computing) и вычислительного интеллекта (computational intelligence), посвященный разработке методов и алгоритмов, опирающихся на эволюционные принципы наследственности, изменчивости и естественного отбора.

  • Генетический алгоритм (ГА) (genetic algorithm) – вид эволюционного алгоритма (evolutionary algorithm), в котором наибольшее внимание уделяется оператору рекомбинации (скрещивания) возможных решений.



3. Генетический алгоритм

  • Решение

  • Закодированное решение

  • Множество решений

  • Качество решения

  • Отбор решений

  • Рекомбинация решений

  • Вариации решений

  • Одна итерация (этап)



3. Генетический алгоритм



3. Генетический алгоритм



3. Генетический алгоритм



3. Генетический алгоритм

  • Поскольку необходимо максимизировать максимальное количество псевдообязательных признаков в искомом подмножестве ББДТ (критерий 1), а также его суммарный вес (критерий 3), но рассматривается задача минимизации целевой функции f , то в выражениях для соответствующих критериям функций штрафа и используется вычитание количества псевдообязательных признаков и веса от максимальных значений. Аналогичные рассуждения использовались при выборе вида функций штрафов для критериев 2, 4 и 5.

  • Отметим, что выбор значений штрафов зависит от рассматриваемой прикладной задачи.



4. Результаты экспериментов

  • Исследование особенностей использования ГА для решения поставленной задачи проведено с использованием псевдослучайных матриц тестов размерностями 1000х50, 1000х100, 1000х200, 1000х300, 1000х400, 1000х500, 2000х500. Мощность n0 подмножества ББДТ, которое необходимо сформировать из матрицы Т, для всех экспериментов равна 300.

  • Параметры ГА:

  • Длительность эволюционного поиска: 1000 поколений

  • Турнирная селекция, размер турнира равен 6 особям.

  • Оператор кроссинговера: двухточечный

  • Оператор мутации: битовый

  • Все результаты усреднены по 100 запускам.



4. Результаты экспериментов

  • Будем оценивать результаты как по полученному лучшему значению функции приспособленности, так и по следующим критериям [11], характеризующим стабильность решений, полученных в различных запусках:

  • 1. Критерий стабильности, учитывающий частоту pi встречаемости i-го теста во всех решениях, полученных по результатам 100 запусков ГА. Чем больше количество тестов, для которых значение pi равно или близко к 1, тем выше сходимость алгоритма.

  • 2. Суммарное количество Ω ББДТ, не вошедших в полученные решения. Чем больше Ω, тем выше сходимость алгоритма.



4. Результаты экспериментов



4. Результаты экспериментов



4. Результаты экспериментов



4. Результаты экспериментов



4. Результаты экспериментов



4. Результаты экспериментов



4. Результаты экспериментов



4. Результаты экспериментов



4. Результаты экспериментов



5. Модифицированный алгоритм

  • При увеличении количества строк в матрице тестов сходимость ГА существенно уменьшается.



5. Модифицированный алгоритм

  • Для повышения сходимости ГА предлагается следующая модификация с адаптацией к условиям эволюционного поиска.

  • Пусть (t) – количество ББДТ в матрице тестов в поколении t, (0) = n, и ’(t)– количество ББДТ, не входящих в закодированные в популяции решения за последние поколений и соответствующие неиспользуемым строкам из исходной матрицы тестов Т.

  • Представим пошагово модифицированный ГА:

  • Шаг 1. Инициализация.

  • Шаг 2. Осуществить t поколений эволюционного поиска.

  • Шаг 3. Если ’(t)>0 и (t) > n0, то удалить из матрицы Т строку с минимальным суммарным весом и провести коррекцию (t+1) = (t) – 1.

  • Шаг 4. Если не выполняются условия останова ГА, то перейти на Шаг 2. Иначе переход на Шаг 5.

  • Шаг 5. Конец.



5. Модифицированный алгоритм

  • Однако полученные результаты экспериментов не выявили улучшений качества решений. В ряде случаев наблюдалось ухудшение результатов. В качестве возможного объяснения предполагается, что удаление неиспользуемых строк может либо случайно удалить «хорошую» строку (в случае, если строка удаляется на первых поколениях), либо не влияет на результат (если удаление происходит после наступления сходимости ГА).

  • Тем не менее, авторы надеются, что возможно улучшение алгоритма с удалением строк, т.к. поскольку увеличение количества строк приводит к ухудшению сходимости, то, вполне вероятно, что должен наблюдаться и «обратный эффект», когда уменьшение количества строк способствует повышению сходимости алгоритма.



6. Заключение

  • В докладе рассматривалось применение ГА для решения задачи формирования оптимального подмножества ББДТ. Представленные результаты экспериментов показывают достаточно высокую сходимость ГА при решении поставленной задачи.

  • На основании полученных результатов и их анализа сделан вывод о возможности существенного уменьшения вычислительной сложности ГА при решении рассматриваемой задачи путем уменьшения размера популяции, а также количества запусков.

  • Отметим, что остается неясным вопрос о зависимости минимального допустимого размера популяции и количества запусков от размера и характеристик матрицы тестов, при которых возможно получение решения, близкого к оптимальному, поскольку необходимо проверить полученный результат на реальных данных.



6. Заключение

  • Дальнейшие исследования будут направлены на разработку более эффективных процедур эволюционного поиска оптимального подмножества ББДТ для решения задач принятия решений на основе тестового распознавания образов.



Благодарности

  • Исследование выполнено при поддержке грантов РФФИ (проект № 07-01-00452) и РГНФ (проект № 06-06-12603В)



Список источников

  • 1. Naidenova R.A., Plaksin M.V., Shagalov V.L. Inductive inferring all good classification test // Знание-Диалог-Решение. Сб. науч. тр. междунар.конф., том 1, Ялта, 1995. с.79-84.

  • 2. Янковская А.Е. Тестовое распознавание образов с использованием генетических алгоритмов // Распознавание образов и анализ изображений: новые информационные технологии (РОАИ-4-98). Труды IV Всероссийской с международным участием конференции. Часть I. -- Новосибирск, 1998. - С.195-199.

  • 3. Yankovskaya A.E. Test Pattern Recognition with the Use of Genetic Algorithms // Pattern Recognition and Image Analysis, vol. 9, no. 1, 1999, p. 121-123.

  • 4. Yankovskaya A.E. The Test Pattern Recognition with Genetic Algorithms Use // Proceedings of the Pattern Recognition and Image Understanding. 5th Open German-Russian Workshop. -- Germany, Herrshing, 1999. -- P. 47-54.

  • 5. Янковская А.Е., Блейхер А.М. Оптимизация синтеза безызбыточных диагностических тестов с использованием генетических алгоритмов и реализация ее в интеллектуальной системе // Искусственный интеллект. Научно-теоретический журнал. ISSN 1561-535. Донецк, № 2, 2000,

  • 6. Yankovskaya A.E., Bleikher A.M. Genetic Algorithms for the Synthesis Optimization of a Set of Irredundant Diagnostic Tests in the Intelligent System // Computer Science Journal of Moldova, vol. 9, no. 3(27), 2001, p. 336-349.

  • 7. Yankovskaya A.E. Bleikher A.M. Optimization of tests synthesis on the base of descent algorithms with the use of genetic transformations // Radioelectronics & Informatics, no. 3(24), 2003, p. 51-55.

  • 8. Yankovskaya A.E., Tsoy Y.R. Optimization of a set of tests selection satisfying the criteria prescribed using compensatory genetic algorithm // Proc. of IEEE EWDTW'05. Kharkov: SPD FL Stepanov V.V., 2005. P. 123-126.

  • 9. Журавлев Ю.И., Гуревич И.Б. Распознавание образов и анализ изображений // Искусственный интеллект: В 3-х кн. Кн.2. Модели и методы: Справ. / Под ред. Д.А.Поспелова. М.: Радио и связь, 1990.

  • 10. Янковская А.Е. Построение логических тестов с заданными свойствами и логико-комбинаторное распознавание на них // ИОИ-2002. Тез. докл. межд. науч. конф. -- Симферополь, 2002. -- С. 100-102.

  • 11. Янковская А.Е., Цой Ю.Р. Исследование эффективности генетического поиска оптимального подмножества безызбыточных тестов для принятия решений // Искусственный интеллект. Научно-теоретический журнал, 2006, с. 257-260.



Применение генетических алгоритмов в интеллектуальных распознающих системах

  • Янковская А.Е., Цой Ю.Р.

  • Томский государственный архитектурно-строительный университет

  • Томский политехнический университет

  • yank@tsuab.ru, qai@mail.ru






Похожие:

Янковская А. Е. Томский государственный архитектурно-строительный университет iconЛингвопрагматические характеристики англоязычного электронного лексикографического гипертекста (на материале словаря-энциклопедии «The Free Dictionary»)
Гоу впо «Самарский государственный архитектурно-строительный университет», кафедра лингвистики, межкультурной коммуникации и социально-культурного...
Янковская А. Е. Томский государственный архитектурно-строительный университет iconМинистерство образования и науки российской федерации государственное образовательное учреждение высшего профессионального образования «томский государственный университет систем управления и радиоэлектроники»
«томский государственный университет систем управления и радиоэлектроники» (тусур)
Янковская А. Е. Томский государственный архитектурно-строительный университет iconМинистерство образования и науки российской федерации государственное образовательное учреждение высшего профессионального образования «томский государственный университет систем управления и радиоэлектроники»
«томский государственный университет систем управления и радиоэлектроники» (тусур)
Янковская А. Е. Томский государственный архитектурно-строительный университет iconМинистерство образования и науки российской федерации государственное образовательное учреждение высшего профессионального образования «томский государственный университет систем управления и радиоэлектроники»
«томский государственный университет систем управления и радиоэлектроники» (тусур)
Янковская А. Е. Томский государственный архитектурно-строительный университет iconМинистерство образования российской федерации федеральное агенство по образованию московский государственный строительный университет и.
Беляев И. П., Капустян В. М. Системный анализ для разработки и внедрения информационных технологий. Методическое пособие. – М.: Мгсу,...
Янковская А. Е. Томский государственный архитектурно-строительный университет iconТомский государственный университет систем управления и радиоэлектроники
Определение Отображение L из линейного пространства в линейное пространство называется линейным отображением, или линейным оператором,...
Янковская А. Е. Томский государственный архитектурно-строительный университет iconСведения о специальностях и перечне вступительных испытаний в негосударственные (частные) образовательные учреждения среднего профессионального образования в 2009 году
Ейский коммерческий архитектурно-строительный техникум-предприятие (аккредитация в марте 2009 г.)
Янковская А. Е. Томский государственный архитектурно-строительный университет iconРеволюция 1917 г. И советская история в освещении русской религиозной эмигрантской мысли
Защита диссертации состоится 14 ноября 2008 г в 15. 00 на заседании диссертационного совета д 212. 267. 03 при гоу впо «Томский государственный...
Янковская А. Е. Томский государственный архитектурно-строительный университет iconРеволюция 1917 г. И советская история в освещении русской религиозной эмигрантской мысли
Защита диссертации состоится 14 ноября 2008 г в 15. 00 на заседании диссертационного совета д 212. 267. 03 при гоу впо «Томский государственный...
Янковская А. Е. Томский государственный архитектурно-строительный университет iconТомский государственный университет филологический факультет
Томском государственном университете состоится заседание регионального научно-методического совета по классической филологии, научно-методическая...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов