Проблема распознавания образов

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

Геометрический подход распознавания образов

 Любое изображение, которое возникает в результате наблюдения какого-либо объекта в процессе обучения или экзамена, можно представить в виде вектора, а значит и в виде точки некоторого пространства признаков. Если утверждается, что при показе изображений возможно однозначно отнести их к одному из двух (или нескольких) образов, то тем самым утверждается, что в некотором пространстве существует две (или несколько) области, не имеющие общих точек, и что изображения - точки из этих областей. В ходе обучения предъявляются точки, случайно выбранные из этих областей, и сообщается информация о том, к какой области принадлежат предъявляемые точки. Цель обучения состоит либо в построении поверхности, которая разделяла бы не только показанные в процессе обучения точки, но и все остальные точки, принадлежащие этим областям, либо в построении поверхностей, ограничивающих эти области так, чтобы в каждой из них находились только точки одного образа.

 

 

Рисунок

Структурный подход распознавания образов (или лингвистический)

Сначала выделяется набор исходных понятий - типичных фрагментов, встречающихся на изображениях, и характеристик взаимного расположения фрагментов - "слева", "снизу", "внутри" и т. д. Эти исходные понятия образуют словарь, позволяющий строить различные логические высказывания, иногда называемые предположениями. Задача состоит в том, чтобы из большого количества высказываний, которые могли бы быть построены с использованием этих понятий, отобрать наиболее существенные для данного конкретного случая.

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

 

Эволюционные вычисления

Они имеют 3 основных направления:

1 часть: Эволюционные стратегии

2 часть: Эволюционное моделирование (генетические алгоритмы)

3 часть: Эволюционное программирование

 

Генетические алгоритмы (ГА)

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

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

ГА используют случайный направленный поиск и могут быть использованы для получения субоптимальных решений.

С помощью ГА получены решения следующих видов оптимизационных задач:

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

2. Стохастические задачи.

3. Динамические задачи с блуждающим оптимизмом.

4. Задача комбинаторной оптимизации большой размерности.

5. Задача прогнозирования и распознавания образов.

Каждое решение задачи (особь) в ГА представлено в виде хромосомы – стринга элементов (строки, генов). Хромосома может быть представлена в двоичном, десятичном (целом или вещественном)  представлении, что делает его применимым для широкого спектра задач, для которых не применимы или не эффективны строгие математические методы.

ГА характеризуются следующими основными параметрами:

ГА = (Р⁰, λ, L, S, P, f, t), где

Р⁰  = (а⁰_i …а⁰_λ) – исходная популяция (одно поколение решений, представленное хромосомами);

а⁰_i – решение задачи в виде одной хромосомы;

λ – размер популяции (целое число);

L – длина каждой хромосомы популяции (целое число);

S – оператор отбора (репродукции);

Р – отображение, определяющее оператор рекомбинации;

f – целевая функция (fitness функция);

t – критерий остановки алгоритма.

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

Выделяют следующие особенности алгоритма:

1. Каждая новая популяция состоит только из жизнеспособных хромосом.

2. Каждая новая популяция лучше в смысле целевой функции, чем предыдущая.

3. В процессе эволюции последующая популяция зависит от предыдущей.

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

1. Репродукция (оператор отбора);

2. Кроссинговер (скрещивание);

3. Мутация (воздействие внешней среды);

Простой ГА можно представить простой схемой:

 

 

   

 

 

1. Создание исходной популяции. На интервале поиска случайно формируется исходное решение.

2. Оператор репродукции. При операторе репродукции отбираются хромосомы согласно значениям их целевых функций. Хромосомы отбирают с использованием «колеса рулетки» или метода ранжирования. Для каждой хромосомы вычисляется значение целевой функции, затем все хромосомы представляют с помощью колеса рулетки:                                            Каждой хромосоме соответствует сектор. После этого имитирует вращение колеса и выбор хромосомы. Хромосомы с большим сектором имеют большее представительство в новом операторе.

3. Создание потомков выбранных пар. Оператор кроссинговера обычно   выполняется в 3 этапа:

1-й этап. Две хромосомы А = а₁  а₂…а_n  и В = b₁ b₂…b_n выбираются из текущей популяции с помощью оператора репродукции.

2-й этап. Случайно выбирается точка кроссинговера – число k, которая находится в пределах 1≤ k ≥ n, где n – длина хромосомы.

3-й этап. Хромосомы А и В обмениваются частями после k-позиции и образуют две новые хромосомы.

A' = a₁a₂…a_k b_k+1…b_L

B' = b₁b₂…b_k   a_k+1…a_L

A = 101 10101

B = 110 01010

A' = 10101010

               B' = 11010101

4. Оператор мутации. Случайным образом с заданной вероятностью изменяется 1ген в хромосоме. Оператор мутации выполняется в 2 этапа:

        1-й этап. В хромосоме А = a₁a₂…a_L-k…a_L-1a_L  определяется случайным образом позиция гена, который будет подвержен мутации, где L – длина хромосомы (количество генов в стринге), а k – случайная величина, которая изменяется в диапазоне 0 ≤ k ≥ L.

         2-й этап. Значение гена соответственного выбранной позиции заменяют противоположным (инверсным) тем самым формируя новую хромосому А' = a₁a₂…a_L-k'…a_L-1a_L  

                A = 10 0 10111

                A' =10 1 10111.

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

Далее происходит проверка условия остановки алгоритма. Самым простым критерием остановки алгоритма исполнение достижения количества повторений алгоритма.

Пример:

На отрезке от 0 до 31 найти экстремум функции (максимум) в функции y = x².

 

 

Начальный этап работы генетического алгоритма приведен в таблице:

№ хромосомы	Начальная популяция особей	Десятичное значение k	Значение f(x)		Среднее значение (x)	Максимальное значение
1	01101	13	169	0,14	293	576
2	11000	24	576	0,49
3	01000	8	64	0,06
4	10011	19	361	0,31

 

1. Сформирована исходная популяция хромосом случайным образом в заданном интервале. Количество хромосом на заданном интервале задается пользователем.

2. Переведем в десятичную систему каждую из хромосом и подставим в fitness – функцию, получив значение f(x).

3. Произведем оценку полученных хромосом с помощью вероятности попадания хромосомы в следующую популяцию

    P(j) =

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

M = P_j * N,  где P_j  - вероятность, а N – мощность популяции.

Число копий хромосомы, переходящих в следующее поколение иногда определяется по следующей формуле:

 = , где  - среднее значение хромосом в популяции.

Расчетные значения копий хромосом:

1.) 0,56

2.) 1,97

3.) 0,22

4.) 1,23

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

                                                                                             Кроссинговер

№ хромосомы	Популяция после репродукции	Пары хромосом для кроссинговера	Популяция после кроссинговера	Значение f (x)	Среднее значение (x)	Максимальное значение fmax(x)
1	01101	1 - 2	01100	144	439	729
2	11000	1 - 2	11001	625
3	11000	3 - 4	11011	729
4	10011	3 - 4	10000	256

 

Одноточечный оператор кроссинговера выполняется с заданной вероятностью Р_с ≈ 0,5, т.е. отобранные хромосомы не обязательно подвергнуты кроссинговеру и образуют потомков. Хромосомы, которые должны пройти кроссинговер или не пройти, отбирают из отобранных пар.

Для хромосом 1 и 2:

А = 01101

В = 11000

1 ≤ k ≤ 4, k = 4 – точка перед пятой позицией

А' = 01100

В' = 11001

Пары хромосом для оператора кроссинговера формируют на стадии моделирования вращения колеса рулетки. При первом вращении получают первую хромосому – родителя, при втором – вторую.

                                                                                   Оператор мутации

№ хромосомы	Популяция кроссинговера	Новая популяция после мутации	Десятичное значение x	Значение f (x)	Среднее значение (x)	Максимальное значение fmax(x)
1	01100	01100	12	144	496,5	961
2	11001	11001	25	625
3	11011	11111	31	961
4	10000	10000	16	256

 

Мутация произведена с третьей хромосомой с третьим разрядом. Оператор мутации также выполняется с заданной вероятностью Р_м ≈ 0,0001

Далее усекают популяцию до исходных размеров и повторяют алгоритм заданное количество раз.