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

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

Известно, что эволюционные, в частности - генетические, алгоритмы способны эффективно решать многоэкстремальные задачи оптимизации с целевыми функциями, заданными неявно (таблично, алгоритмически и т. п.) на сложных структурах данных (дискретных, комбинаторных, смешанных) [2]. Генетические алгоритмы являются стохастическими процедурами прямого поиска на множестве бинарных переменных и упомянутые трудности оптимизации не создают для них дополнительных проблем.

В данной работе рассматривается применение гибридного генетического алгоритма для синтеза

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

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

Библиографические ссылки

1. Gorban A. N., Kegl B., Wunsch D., Zinovyev A. Y. (Eds.), Principal Manifolds for Data Visualisation and Dimension Reduction, Series: Lecture Notes in Computational Science and Engineering 58, Springer, Berlin -Heidelberg - New York, 2007.

2. Goldberg, D. E. Genetic algorithms in search, optimization and machine learning. Reading, MA : Ad-dison-Wesley, 1989.

© Гасанова Т. О., Семенкин Е. С., 2010

УДК 519.68

Т. К. Гулакова Научный руководитель - С. С. Бежитский Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Красноярск

ИССЛЕДОВАНИЕ ЗАВИСИМОСТИ ЭФФЕКТИВНОСТИ РАБОТЫ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ОТ ВЫБОРА ПАРАМАТРОВ ОПЕРАТОРОВ АЛГОРИТМА НА МНОГОЭКСТРЕМАЛЬНЫХ ТЕСТОВЫХ ФУНКЦИЯХ

Проводится исследование работы ГА в зависимости от выбора параметров при нахождении глобального оптимума многоэкстремальных функций вещественных переменных. Исследуется эффективность новых видов оператора рекомбинации.

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

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

Исследование заключается в сравнении результатов работы алгоритма на принципиально разных по свойствам многоэкстремальных функциях Грин-вака, Растригина и Розенброка при вариации различных параметров. Вариабельные параметры алгоритма представлены в табл. 1.

Область поиска изменяется в зависимости от выбранной функции. При этом такие параметры как размерность популяции, число поколений и вероятность скрещивания остаются неизменными в процессе исследования. Эти данные представлены в табл. 2.

Агрегированные результаты исследования приведены на рис. 1.

Таблица 1

Тип рекомбинации Вероятность мутации Тип селекции Размерность задачи

1. Одноточечная 1. Сильная 1. Пропорциональная 1. 2

2. Двуточечная 2. Средняя 2. Турнирная 2. 3

3. Равномерная 3. Слабая 3. Ранговая 3. 4

4. Побитовое сравнение 4. Элитарная

5. Псевдо-митоз

Актуальные проблемы авиации и космонавтики. Информационные технологии

Таблица 2

Функция Левая граница Правая граница Число индивидов X поколений Вероятность скрещивания Точность поиска

Гринванка -512 512 150x150 1 1 1 0,1

Растригина -5 5 60x60 0,01

Розенброка -2 2 100x100 0,01

0,5 0,4

л

У 0,3

0,2 0,1 0

Сводная диаграмма

ГИ-п!

5 6 7 8 9 10 11 Комбинация параметров

12 13 14 15

пропорциональная

турнирная

ранговая

элитарная

1,2 1

ё о,8 о

5 0,6

0,2 0

Сводная диаграмма

пропорциональная

турнирная

ранговая

элитарная

5 6 7 8 9 10 11 12 13 14 15 Комбинация параметров

б

1,2 1

(З 0,8 о

5 0,6

0,2 0

Сводная диаграмма

Ш

а

пропорциональная

турнирная

ранговая

элитарная

5 6 7 8 9 10 11 12 13 14 15 Комбинация параметров

в

Агрегированные результаты для тестовых функций при раличных типах рекомбинации: 1-3 - одноточечная, 4-6 - двухточечная; 7-9 - равномерная; 10-12 - побитовое сравнение; 13-15 - псевдо-митоз; а - для функции Гринавка; б - для функции Растригина; в - для функции Розенброка

а

га 0,4

ГС 0,4

Из результатов видно, что рекомбинация «побитовое сравнение» оказалось эффективной для всех тестовых функций особенно при средней и сильной степени мутации. В то же время новый вид рекомбинации «псевдно-митоз» не оправдал надежд на высокую эффективность.

Библиографическая ссылка

1. Holland J. H. Adaptation in natural and artificial systems. MI: University of Michigan Press, 1975.

© Гулакова Т. К., Бежитский С. С., 2010

УДК 519.68

Т. К. Гулакова, Р. И. Кузьмич Научный руководитель - И. С. Масич Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Красноярск

ПОИСК ЗАКОНОМЕРНОСТЕЙ В ЗАДАЧЕ КЛАССИФИКАЦИИ

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

Закономерностью называется предикат, определенный на множестве объектов X ф: X ^ {0,1}, если он выделяет достаточно много объектов одного класса с, и практически не выделяет объекты других классов. Всякая закономерность классифицирует лишь некоторую часть объектов. Объединив определённое количество закономерностей в композицию, получим решающее правило, способное классифицировать любые объекты.

Пространство поиска, на котором следует искать информативные закономерности, в случае, если все признаки являются бинарными, легко описать с помощью Булевых функций. Любая такая функция может быть представлена в виде дизъюнктивных нормальных форм (ДНФ). Более того, в качестве закономерностей можно брать только конъюнкции признаков и их отрицаний, а дизъюнкцию реализовать как корректирующую операцию, например, как голосование по большинству или старшинству.

Закономерностями являются предикаты, отвечающие критерию максимума информативности. Критерий информативности может быть представлен в любой из следующих форм: Эвристический критерий. Статистический критерий. Энтропийный критерий. Взвешенная информативность. Для выявления наиболее информативных предикатов пространство поиска следует разбить на области. Наиболее употребительные из них: Гиперпараллелепипеды

Р( х) = [а < f (х) < а']

Шары

ф(х) ^^ х0 )< Г0 ] Полуплоскости

ф(х )=[( х га)<Юо] Области, описываемые ядром

ф(х)=[[ (х, Хо )< Ко ] Методы порождения бинарных предикатов:

- Градиентный алгоритм синтеза конъюнкций. Варьируя параметры алгоритма (информативность и окрестность конъюнкции) можно получать различные алгоритмы поиска или улучшения данных конъюнкций - Жадный алгоритм синтеза конъюнкции, Стохастический локальный поиск, Процедура стабилизации, Процедура редукции.

- Генетический алгоритм синтеза конъюнкций. Генетические алгоритмы отличаются большим разнообразием всевозможных эвристик.

- Поиск информативных конъюнкций как задача отбора признаков. Функционал качества в задачах отбора признаков заменяется на максимум информативности.

- Построение решающих правил на основе выявленных закономерностей: После нахождения множества логических закономерностей в форме конъюнкций строятся решающие правила в виде ДНФ.

1. Решающие списки. Решающий список закономерностей представляет собой частный случай алгоритмической композиции с голосованием по старшинству.

2. Решающие деревья. При синтезе деревьев решений строятся все конъюнкции одновременно.

Классификация a: X ^ Y записывается в виде простого голосования конъюнкций

a(x) = arg max ^ Kv (x), где Т - множество всех

yeY

veT cv = У

терминальных вершин дерева; Kv (x) - конъюнкция, составленная из всех предикатов, приписанных внутренним вершинам дерева на пути от корня v0 до вершины v.

3. Голосование правил

- Алгоритм простого и взвешенного голосования.

- Алгоритм КОРА.

- Алгоритм ТЭМП.

- Алгоритм Бустинга.

Один из алгоритмов логического анализа данных был применен при решении следующей задачи