WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 || 3 | 4 |   ...   | 8 |

Коэффициенты составляют матрицу, обратную ковариационной матрице. Для вычисления коэффициентов используется стандартная формула, (2) где минор определителя, получаемый из него вычеркиванием й строки и го столбца.

Выражение, фигурирующее в показателе экспоненты функции плотности нормального распределения векторов VСi, является положительноопределенной квадратичной формой. Поверхности, на которых эта форма постоянна, являются поверхностями равных плотностей вероятностей в Nмерном пространстве и представляют собой гиперэллипсоиды, которые группируются вокруг точки (x1, x2, …, xN).

Обозначая указанную форму через k2, получим = k2. (3) Константа k задает коэффициент пропорциональности между длинами aj главных полуосей гиперэллипсоида и соответствующими среднеквадратическими отклонениями sj:

a1 = k·s1; a2 = k·s2; …, aN = k·sN.

Для единичного гиперэллипсоида k=1. Начальную границу интегральной области «все чужие» зададим в виде коэффициента Стьюдента, исходя из величины ошибки первого рода (вероятности P1 ложного отказа «своему» пользователю):, [1].

В результате можно получить искомое выражение для дискриминантной функции g(V), разделяющей области «свой» и «все чужие»:

g(V) = (4) Уравнение g(V)=0 в этом случае будет определять искомую разделяющую поверхность, а знак функции g(V) принадлежность входного вектора V к одному из двух классов: «свой» или «чужой» (попадание в область «все чужие»):

g(V) < 0, если VОVC, g(V) > 0, если VОVЧ.

Таким образом, процедура аутентификации сводится теперь к проверке: попадает ли предъявленный пользователем вектор биометрических параметров V в область, описываемую, выражением (4).

Иллюстрация метода для двухмерного пространства (N=2) показана на рисунке.

Рис. 1. Иллюстрация метода биометрической аутентификации пользователя на основе параметрического обучения классификатора Биометрическая аутентификация пользователя на основе параметрического обучения классификатора по сравнению с геометрическими методами и методами, основанными на использовании ИНС, обладает рядом преимуществ.

По сравнению с геометрическими методами распознавания точность аутентификации возрастает вследствие более точной аппроксимации области распределения векторов VС. Повышение точности при этом «оплачивается» дополнительным объемом вычислений, связанным с получением функции (4). Вместе с тем, эти вычисления производятся по стандартным, фиксированным по времени выполнения процедурам, и могут быть реализованы в масштабе времени, близкому к реальному.

По сравнению с методами распознавания на основе ИНС исчезает необходимость неопределенно длительного обучения распознающей системы в классическом его понимании (как подбор дискриминантной функции g(V)). Как следствие, исчезают проблемы возникновения тупиков, состояния «паралича» сети, а также принципиальная проблема обучения ИНС на всех возможных «чужих» пользователей [2].

Изложенный метод реализован в программных пакетах BioSing и BioKey, использующих параметры рукописного и клавиатурного почерков соответственно [4, 5]. После экспериментальной проверки на основе этих пакетов был разработан и поставлен лабораторный практикум по учебному курсу «Защита информационных процессов в компьютерных системах» для студентов специальности 075400 [6]. По результатам лабораторных работ осеннего семестра 2003/2004 учебного года были получены статистические данные, демонстрирующие работоспособность и эффективность метода. В испытаниях участвовало 50 пользователей. На этапе обучения каждый пользователь 20 раз вводил свой уникальный пароль. Коэффициенты, влияющие на точность системы, пользователь выбирал сам. После обучения системы пользователи проходили процедуру аутентификации. Каждый пользователь делал 20 попыток аутентификации (для вычисления ошибки первого рода). После этого другой пользователь из группы испытуемых делал 20 попыток пройти аутентификацию, подделывая этот пароль. Полученные результаты сведены в табл.1 и 2.

Таблица Результаты испытаний программы BioSing (аутентификация по рукописному почерку) Кто проходил аутентификацию Число пользователей Число попыток Число ошибок «свой» «чужой» Таблица Результаты испытаний программы BioKey (аутентификация по клавиатурному почерку) Кто проходил аутентификацию Число пользователей Число попыток Число ошибок «свой» «чужой» На основании приведенных экспериментальных данных ошибки 1го и 2го рода для рукописного почерка составили d Ј 0,003, для клавиатурного почерка d Ј 0,004.

Библиографический список 1. Иванов А.И. Биометрическая идентификация личности по динамике подсознательных движений. – Пенза Издво Пенз. гос. унта, 2000. 188 с.

2. Брюхомицкий ю.а., казарин м.н. Метод обучения нейросетевых биометрических систем на основе копирования областей / Перспективные информационные технологии и интеллектуальные системы. – Электронный журнал. – 2003. №3 (15). С. 1723. – http://pitis.tsure.ru.

3. Нильсон Н. Обучающиеся машины/Пер. с англ. – М.: Мир, 1967.– 180 с.

4. Брюхомицкий Ю.А., Казарин М.Н. Программа аутентификации личности по динамике рукописного почерка / Программа для ЭВМ. Рег. № 2003611145 (16.05.2003). ОБ «Программы для ЭВМ, базы данных, топологии интегральных микросхем», № 2, 2003.

5. Брюхомицкий Ю.А., Казарин М.Н. Программа аутентификации личности по динамике клавиатурного почерка / Программа для ЭВМ. Рег. № 2003610944 (17.04.2003). ОБ «Программы для ЭВМ, базы данных, топологии интегральных микросхем», № 2, 2003.

6. Брюхомицкий Ю.А., Казарин М.Н. Учебнометодическое пособие к циклу лабораторных работ «Исследование биометрических систем динамической аутентификации пользователей ПК по рукописному и клавиатурному почеркам» по курсу: «Защита информационных процессов в компьютерных системах». Таганрог: Издво ТРТУ, 2004. № 3531. 40 с.

А.Ф. Чипига, Р.А. Воронкин, В.А. Галкина Россия, г. Ставрополь, СевКавГТУ ХАРАКТЕРИСТИКИ ПОПУЛЯЦИИ, ОПРЕДЕЛЯЮЩИЕ МЕРУ СХОДИМОСТИ ЭВОЛЮЦИОННОГО ПРОЦЕССА Генетические алгоритмы находят применение при решении задач криптоанализа, проектирования, оптимизации нейронных сетей, исследования графов и т.д. При решении оптимизационных задач с помощью мажоритарного генетического алгоритма встает вопрос о мере сходимости эволюционного процесса и критерии останова его работы.

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

, (1) или максимального значения степени приспособленности. (2) где – размер популяции;

– величина приспособленности для особи.

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

, (3) где – число нулей в м бите хромосомного набора популяции ;

– численность популяции.

Тогда побитовое разнообразие по всем битам хромосомы. (4) При наблюдается максимальное разнообразие генотипов; при все генотипы в хромосомном наборе совпадают между собой.

Для мажоритарного генетического алгоритма, у которого каждый локус содержит два аллельных гена и, а также один признак доминантности, величина генетического разнообразия находится следующим образом, (5) где (6) определяют побитовое разнообразие по каждому аллельному и опорному генам локуса; – количество особей, у которых в локусе признак доминантности равен нулю; – количество особей, которых в локусе под номером аллельный ген равен нулю; – количество особей, которых в локусе под номером аллельный ген равен нулю; – размер популяции. При наблюдается максимальное разнообразие генотипов по популяции ; при все генотипы популяции совпадают между собой.

Для мажоритарного генетического алгоритма допустимо ввести величину фенотипического разнообразия, (7) равен нулю; – размер популяции. При наблюдается максимальное фенотипическое разнообразие по популяции ; при все фенотипы популяции совпадают между собой.

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

А.Ф. Чипига, Р.А. Воронкин Россия, г. Ставрополь, СевКавГТУ РЕШЕНИЕ ЗАДАЧИ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ С ПОМОЩЬЮ МАЖОРИТАРНОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА С ИЗНАЧАЛЬНО ВЫРОЖДЕННОЙ ПОПУЛЯЦИЕЙ Для того чтобы продемонстрировать явные преимущества использования диплоидного способа кодирования генетической информации, реализованного в мажоритарном генетическом алгоритме (МГА) [1, 2], над гаплоидным в простом генетическом алгоритме (ПГА) [3], необходимо провести экспериментальные исследования процесса сходимости генетических алгоритмов для изначально вырожденной популяции [4].

Пусть начальный момент рассматриваемого периода эволюции совпал с внезапным изменением рельефа целевой функции. Предполагается также, что предыдущий период был стабильным и настолько длительным, что обе популяции (как гаплоидная ПГА, так и диплоидная МГА) выродились фенотипически вокруг начала координат в пространстве. Для гаплоидной популяции данное условие означает, что все гены хромосомы в случае использования двоичнодесятичного кода равны нулю. Для диплоидной популяции МГА это предположение выполняется, если во всех гомологичных парах генов будут доминировать нули независимо от того, какую информацию несут рецессивные гены [4].

Пусть в начале эволюции целевая функция приобретает вид:

(1) где,.

График целевой функции показан на рис. 1.

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

Рис. 1 График целевой функции в области поиска глобального экстремума а) б) Рис. 2. Динамика изменения среднего и максимального значений функции оптимальности в процессе эволюции для а) ПГА; б) МГА В начальный момент времени особи гаплоидной и диплоидной популяций расположены в начале координат. Если исходным источником генетического разнообразия у вырожденной гаплоидной популяции является мутация, а кроссинговер только усиливает последствия ее воздействия, то в диплоидной популяции выполнение оператора кроссинговера на первых этапах эволюции приводит к появлению нескольких доминантных единиц в генотипе потомка за счет проявления в фенотипе рецессивных генов [1, 3, 4]. На рис. 2 изображены графики динамики изменения среднего и максимального значений функции оптимальности. Очевидна сходимость простого генетического алгоритма к локальному экстремуму целевой функции, из которого происходит старт. Для популяции мажоритарного генетического алгоритма наблюдается сходимость к субглобальному экстремуму целевой функции. Сходимость гаплоидной популяции к локальному экстремуму целевой функции обусловлена постоянной численностью и действием отбора на элиминирование. Постоянный отток генетического материала на первых шагах эволюции компенсируется изменчивостью потомства, пока приспособленность по всей популяции остается однородной. Постепенно особи с большим значением приспособленности вытесняют менее приспособленных, вклиниваясь в иерархию популяции. Популяция стягивается в найденный локальный экстремум, который в рамках поставленной задачи находится в начале координат [4]. Таким образом, проведенные экспериментальные исследования показали преимущества использования диплоидного способа кодирования генетической информации мажоритарного генетического алгоритма за счет повышения качества решения задач глобальной оптимизации.

Pages:     | 1 || 3 | 4 |   ...   | 8 |




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.