Разработка и исследование генетических алгоритмов обучения в моделях вычисления оценок (стр. 2 )

Количество признаков	Количество объектов
5	10	16	24
2	3, 1, 3	5, 7, 8	15, 9, 9	19, 19, 21
5	3, 5, 1	9, 5, 4	33, 34, 24	89, 75, 114
10	1, 1, 1	4, 5, 4	37, 14, 50	307, 241, 144
15	1, 1, 1	1, 1, 3	7, 1, 10	149, 115, 295
25	1, 1, 1	1, 1, 1	1, 3, 1	8, 31, 16
50	1, 1, 1	1, 1, 1	1, 1, 1	1, 1, 1

Таблица 2. Значения экспериментального количества локальных экстремумов при различных параметрах и . В каждой из ячеек таблицы содержатся 3 значения, полученные в трех независимых запусках (на трех различных случайно сгенерированных выборках).

Также в главе 2 предлагается адаптированный к задаче метод кроссовера, основная идея которого заключается в следующем – каждый раз при процедуре кроссовера хромосомы меняются не просто случайными участками, а некоторой группой объектов, которые в признаковом пространстве располагаются близко друг от друга. Предлагается проводить однородный кроссовер, для которого вероятность обмена битами зависит от нормированного на единицу расстояния от текущего объекта/бита до некоторого фиксированного для данной пары хромосом объекта, являющегося «центром кластера». Данный «центр кластера» выбирается каждый раз заново для каждой скрещиваемой пары. Предлагаются формулы для определения функции расстояния и вероятности обмена битами. Тестирование на искусственных наборах данных и на практических задачах показало надежность данного метода кроссовера и его преимущество перед другими, классическими схемами.

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

Описывается разработанный “ЭСС-критерий” остановки ГА, который принимает решение об остановке генетического алгоритма исходя из динамики средней ЦФ популяции. При превышении экпоненциального скользящего среднего средней ЦФ популяции над средней ЦФ популяции генетический алгоритм переходит в состояние с пониженной дизруптивностью оператора мутации. В случае, если в данном состоянии в течение десяти итераций не происходит роста наилучшей ЦФ популяции, алгоритм прекращает работу. Экспериментально показано, что данный критерий остановки ГА адаптируется к сложности задачи и работает лучше, чем традиционные критерии, использующиеся для генетических алгоритмов.

Глава 3 содержит описание алгоритма распознавания. Результатом процесса обучения на обучающей выборке является построение покрытий классов некоторым набором допустимых предикатов . Процесс распознавания некоторого нового объекта , чья принадлежность тому или иному классу неизвестна, сводится в простейшем случае к процедуре взвешенного голосования по предикатам. В рамках данной процедуры вначале вычисляются оценки предиката за каждый из классов задачи , где – некоторые параметры. После расчета оценок за классы по этим оценкам проводится процедура голосования. Объект относится к тому классу, оценка за который превышает все оценки данного объекта за другие классы, либо, если такого класса не существует, алгоритм выдает «отказ» от распознавания объекта. Данный метод расчета оценки можно считать каноническим.

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

Первый из методов назван оценкой «по принадлежности снаружи»

В рамках данного метода рассчитывается оценка

Здесь предикат определяется следующим образом:

(3.1)

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

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

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

(3.2)

где функция определяется как , а – некоторое пороговое значение, не зависящее от номера класса. На практике формула рассчитывает количество признаков, по которым объект находится внутри ограничений, задаваемых предикатом. Пороговое значение – это количество признаков, начиная с которого можно считать, что объект «частично принадлежит» предикату. Экспериментальные исследования показали, что для наиболее эффективной работы алгоритма значение порога для количества признаков следует брать в пределах . При меньших значениях порога качество распознавания несколько ухудшается, а при больших существует опасность потерять «уникальность» данной оценки, так как она практически повторяет «каноническую» оценку (3.1), переходя в нее при .

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

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

- Если голосование по оценкам двух типов относит объект к некоторому классу, объект следует отнести к этому классу.

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

- Если все 3 метода дали отказ от распознавания, алгоритм дает отказ от распознавания.

Наилучшим порядком приоритетности предлагается считать в порядке убывания.

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

(3.3)

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

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

Голосование по оценке
Отнесено в класс:	1	2	3	4	5	6	7	отказы
Из класса 1	133	0	0	0	0	0	0	17
Из класса 2	0	129	0	1	0	0	0	20
Из класса 3	0	0	117	8	11	0	1	13
Из класса 4	0	0	1	135	1	0	1	12
Из класса 5	0	0	3	1	134	0	2	10
Из класса 6	0	0	0	0	0	142	0	8
Из класса 7	0	0	1	2	0	0	137	10
Ошибочно отнесено	0	0	5	12	12	0	4	90

Голосование по оценке
Отнесено в класс:	1	2	3	4	5	6	7	отказы
Из класса 1	63	0	0	0	0	0	0	87
Из класса 2	0	133	0	0	0	0	0	17
Из класса 3	26	2	95	12	8	0	2	5
Из класса 4	17	7	1	115	0	5	1	4
Из класса 5	29	0	2	0	114	1	0	4
Из класса 6	0	0	0	0	0	149	0	1
Из класса 7	7	0	0	0	0	0	106	37
Ошибочно отнесено	79	9	3	12	8	6	3	155

Голосование по оценке
Отнесено в класс:	1	2	3	4	5	6	7	отказы
Из класса 1	146	1	0	1	1	0	0	1
Из класса 2	0	146	0	4	0	0	0	0
Из класса 3	1	1	109	20	9	0	7	3
Из класса 4	0	1	2	143	0	0	4	0
Из класса 5	0	0	13	2	131	0	2	2
Из класса 6	0	0	0	0	0	150	0	0
Из класса 7	0	0	1	9	0	0	140	0
Ошибочно отнесено	1	3	16	36	10	0	13	6

Итого, первой оценкой допущена 121 ошибка, второй оценкой допущено 120 ошибок и третьей оценкой допущено 85 ошибок.