close

Вход

Забыли?

вход по аккаунту

?

Решение обобщенной задачи поиска оптимальной ER-модели на основе генетического алгоритма.

код для вставкиСкачать
УДК 004.021
РЕШЕНИЕ ОБОБЩЕННОЙ ЗАДАЧИ ПОИСКА ОПТИМАЛЬНОЙ ER-МОДЕЛИ
НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА
А.В. Шалиткин, Н.А. Тюкачев, П.А. Цветков
В статье поставлена общая задача оптимизации ER-модели и предложен способ ее решения на основе
генетического алгоритма, приведен анализ выбора параметров алгоритма
Ключевые слова: оптимальность ER-модели, генетический алгоритм, модель ГИС
В работах [1] и [2] был рассмотрен
способ определения оптимальности ERмодели для ГИС систем для 3 и 4 сущностей.
ER-модель представляется в виде планарного
графа. Зная количество ребер в данной модели
и набор алгоритмов, которые будут затем
использованы, можно определить какой объем
памяти требуется для хранения такой модели,
а также ее мощностную характеристику, то
есть насколько эффективно можно будет
применить предполагаемые алгоритмы.
Этот метод может быть обобщен на
большее количество сущностей. Сущностями
могут быть не обязательно графические
объекты, а объекты любой предметной
области. Однако, так как количество вариантов
2
моделей равно 2n , решения такой задачи
прямым перебором представляется очень
трудоемкой задачей.
Будем говорить, что задача поиска
оптимальной ER модели задана, если на
направленном планарном графе выполняются
следующие условия:
1. Задан набор сущностей xi ∈ S , i = 1.2...n .
Каждая сущность ассоциируется с вершиной
графа.
2. Для
каждой
сущности
задано
максимальное количество ее экземпляров
c( xi ) .
3. Для каждой сущности задан набор
весов входящих ребер vij ( xi ), j = 1..n, j ≠ i . То
есть
количество
экземпляров
данной
сущности, которое может быть связано с
каждой из оставшихся сущностей.1
Шалиткин Андрей Владимирович - ВГУ, аспирант,
e-mail: andrey.shalitkin@mail.ru
Тюкачев Николай Аркадьевич - ВГУ, канд. физ.-мат.
наук, доцент, e-mail: nik@cs.vsu.ru
Цветков Павел Александрович – ООО “Люксофт
Профешнл”,
старший
разработчик,
e-mail:
adastral@yandex.ru
4. Семейства функций c и v являются
многочленами одной переменной p .
Проблема заключается в том, что
количество комбинаций связей, которые
2
нужно перебрать будет равно 2n . То есть при
большом количестве сущностей, решение
простым перебором может быть неприемлемо.
Ниже предложен эвристический способ поиска
оптимальной
модели,
основанной
на
генетическом алгоритме [3].
Можно выделить следующие этапы
генетического алгоритма:
1. Задать
целевую
функцию
(приспособленности) для особей популяции
2. Создать
начальную
популяцию,
состоящую из случайно сгенерированных
решений, равномерно распределенных в
пространстве возможных решений.
3. Повторять в цикле шаги 4-6 пока не
выполнится условие останова
4. Вычисление целевой функции для вновь
порожденных особей, и сортировка в порядке
убывания приспособленности
5. Скрещивание
наиболее
приспособленных особей для порождения
нового поколения решений
6. Мутация.
Будем считать одним из критериев
остановки выполнение заданного количества
итераций, тогда для реализации генетического
алгоритма необходимо определить следующее:
• Целевую функцию;
• Стратегию создания начальной
популяции;
• Стратегию скрещивания;
• Стратегию мутации;
• Размер популяции и количество
итераций.
Кроме того, необходимо определиться с
моделью данных. Информация о возможном
количестве экземпляров сущностей в ERмодели и кратности связей является
статичной, то есть не меняется от итерации к
итерации. Количество сущностей определено.
Таким
образом,
элементом
популяции
является
направленный
граф
без
дополнительной информации, а с точки зрения
программирование это матрица, то есть
двумерный массив со значением ложь или
истина (0 или 1) в каждой ячейке.
Двумя оценками ER-модели являются
мощность
выполняемых
алгоритмов
и
использование
памяти.
Способы
их
вычисления приведены в [2]. Если посчитать
мощности
для
некоторого
множества
алгоритмов, которое будет использовано, и
взять их линейную комбинацию, то получим
мощностную характеристику модели. Таким
образом, функцию мощности и объема
использованной памяти можно считать
оценками модели.
За результирующую целевую функцию
берется линейная комбинация описанных
выше оценок.
На стадии селекции вновь полученное
поколение упорядочивается по возрастанию.
В качестве примера рассмотрим модель
из пяти элементов. В данном случае возможно
всего 225 вариантов модели, что является уже
достаточно большим для перебора всех
вариантов. Четыре элемента и связи между
ними возьмем из трехмерной модели для ГИС.
Пусть пятый элемент имеет связи со всеми
другими 1:n, а максимальное количество
экземпляров данной сущности будет N. Такая
модель изображена на рисунок.
Избыточная модель
Будем использовать целевую функцию,
полученную в главе 3, дополнив ее
отношением пятого элемента ко второму, то
есть функция будет выглядеть следующим
образом:
P = K 0 P0,2 P0,1 P1,0 + K 0 P0,2 + K 2 P2.2 + K 2 P2,1
+ K 3 P3,2 + K1 P1,2 + K 0 P0,1 + K 4 P4,1
(1)
Для исследования различных стратегий
будем использовать статистическую плотность
распределения
количества
итераций,
необходимых
для
поиска
наилучшего
решения. Наилучшее значение целевой
функции для модели, изображенной на рис. 1
складывается из мощности
и объема
используемой памяти, оно равно: P=65N,
U=39N. Если полученное решение близко к
описанному выше, то будем считать его
оптимальным.
Для каждого рассматриваемого типа
стратегии будем производить 1000 запусков и
определять на какой итерации была получена
оптимальная модель. С точки зрения всех
стратегий все связи являются одинаковыми, а
потому во всех случаях, где необходим выбор
генов, нужно использовать равномерный закон
распределения.
Размер популяции и количество итераций
определяется
вычислительными
возможностями, применимыми к конкретной
задаче. Очевидно, что чем больше размер
популяции и больше количество итераций, тем
лучший результат мы должны получить,
однако для ряда задач попадание в минимум
происходит достаточно скоро, а потому
дальнейшее выполнение алгоритма ни к чему
не приведет. Следовательно, при большом
потенциальном
количестве
итераций,
необходимо ввести дополнительный критерий,
который бы проверял изменение лидера. Если
за несколько итераций лидер остался без
изменений,
то
алгоритм
должен
останавливаться.
Введем также понятие элиты – элементы
популяции, которые формируют новое
поколение, при сами они также входят в новое
поколение. Таким образом, популяция состоит
из некоторого количества элиты и вновь
созданных и мутированных элементов. Для
обеспечения
достаточного
многообразия
определим размер популяции равным 100 и
количество элитарных элементов – nEl.
Последняя величина является предметом
оптимизации и будет рассмотрена ниже. Так
как
стратегия
порождения
начальной
популяции не слишком важна, то будем
генерировать матрицу, где каждый элемент
пронимает значение ложь или истина с равной
вероятностью.
Опишем селективную стратегию. Пусть
N - количество элитарных элементов. Все
элементы находятся в списке, упорядоченном
по возрастанию целевой функции. Поставим
каждому i -му элементу элиты в соответствие
вероятность
i
Pi =
.
N
∑k
k =1
(2)
На основе описанной выше вероятности
из элиты выбирается два элемента, происходит
скрещивание и новый элемент помещается в
пул популяции. Это действие происходит до
тех пор, пока не будет заполнен весь пул.
Назовем данную стратегию стратегией с
линейно убывающей вероятностью.
Следующем этапом является применение
стратегии мутации. Зададим две вероятности.
На основе первой для каждого элемента будем
принимать решение, проводить мутацию или
нет. На основе второй вероятности будем
определять мутирует ли конкретный элемент
матрицы или нет. Зададим эти вероятности
равными 0.1 и 0.3 соответственно. Стоит
заметить, что, для ускорения работы
алгоритма, вместо того, чтобы проводить
мутацию каждого гена
с некоторой
вероятностью, будем выбирать на основе этой
вероятности некоторое количество генов и
проводить мутацию для всех них. Так, при
второй вероятности равной 0.3, для каждого
элемента, выбранного для мутации, 30% всех
генов будет изменено.
Ниже в табл. 1 приведено распределение
итераций, на которых было получено
оптимальное решение. Множество итераций
разбито по 50 элементов, считается статистика
попаданий в тот или иной отрезок такого
разбиения. При этом максимальное количество
итераций – 500.
Таблица 1
Количество элитарных элементов
Отрезок
0<i<50
50<i<100
100<i<150
150<i<200
200<i<250
250<i<300
300<i<350
350<i<400
400<i<450
450<i<500
Количество попаданий
nEl=10
nEl=20
nEl=30
nEl=50
285
326
164
82
42
34
28
15
12
11
316
302
148
85
60
22
23
22
6
15
316
281
174
98
54
22
16
22
5
11
342
228
144
88
63
50
30
23
21
11
Анализ
таблицы
показывает,
что
результаты не сильно отличаются, однако при
nEl=30
результаты
можно
считать
наилучшими по двум параметрам. Во-первых,
достаточно малое количество запусков давали
чемпиона на больших итерациях. При nEl=50
мы
получили
наибольшее
количество
оптимальных решений уже на первых
итерациях, однако в этом случае достаточно
много решений получается на больших
итерациях, поэтому этот вариант является
менее предпочтительным. Во-вторых, чем
больше элита, тем быстрее работает алгоритм,
так как на каждой итерации количества новых
элементов будет меньше. Таким образом, на
фоне почти одинаковых результатов во втором
и третьем столбцам, nEL=30 является
предпочтительным.
Далее будем рассматривать оптимальное
nEl=30 и будем варьировать вероятности в
стратегии мутации. Обозначим их как prob1 и
prob2.
Из
табл. 3 хорошо видно,
что
комбинация prob1=0.1 и prob2=0.3 является
оптимальной.
Рассмотрим
еще
одну
стратегию,
проанализируем ее на предмет выбора
оптимальной nEl и сравним с полученными
ранее результатами. Стратегия заключается в
том, что на основе равномерного закона
распределения
выбирается
две
пары
элементов, затем из каждой пары выбирается
элемент с лучшим значением целевой функции
и полученные два элемента скрещиваются.
Будем называть данную стратегию турнирной.
В табл. 2 приведены результаты.
Таблица 2
Размер элиты для турнирной стратегии
Отрезок
0<i<50
50<i<100
100<i<150
150<i<200
200<i<250
250<i<300
300<i<350
350<i<400
400<i<450
450<i<500
Количество попаданий
nEl=10
nEl=20
nEl=30
nEl=50
285
317
171
75
33
31
31
24
14
19
301
305
188
79
43
27
20
13
13
11
318
290
148
101
47
24
25
19
13
15
358
213
156
81
61
46
30
25
14
15
Сравнивая табл. 1 и 2 можно сказать, что
обе стратегии дают почти одинаковые
результаты,
причем
все
тенденции
сохраняются, из чего можно сделать вывод,
что выбор между описанными стратегиями в
данном случае не важен.
Исходя из исследований, описанных
выше можно рекомендовать следующие
параметры алгоритма (таб 4).
Таблица 4
Рекомендуемые параметры
Параметр
Размер пула
Размер элиты
Вероятность мутации
элемента
Вероятность мутации гена
Селективная стратегия
расчетное
время
выполнения
прямого
перебора 20 ч (на использованном
компьютере). В то же время, приложение,
использующее
эволюционный
алгоритм,
выдавало результат за среднее время - 1 с.
Значения
100
30
0.1
0.3
Не важно
Литература
1. Тюкачев Н.А.; Выбор ER-модели для описания
поверхности трехмерных тел // Вестник ВГТУ, 2009. С.
14-24.
Подход, описанный в данной статье, был
экспериментально апробирован для решения
рассматриваемой задачи. Для этого было
написано два приложения: одно решало задачу
методом прямого перебора всех возможных
вариантов,
другое
использовало
эволюционный алгоритм.
Для случаев, когда число узлов не
превышает 4-х, оба приложения выдают
результаты примерно за одинаковое время – не
более одной секунды.
В случае же 5-ти узлов, количество
вариантов решения возрастает на столько, что
2. Шалиткин А.В.; Поиск оптимальной ER модели
для
некоторых
алгоритмов
триангуляции.
X
международная
научно-методическая
конференция
«Информатика: проблемы, методология, технологии»,
2010, с. 34-38.
3. Mitchell M. An Introduction to Genetic
Algorithms. A Bradford Book The MIT Press. Cambridge,
Massachusetts. 1999, p. 733.
4. Rothlauf F. Representations for Geneticand
Evolutionary Algorithms. Springer-Verlag Berlin Heidelberg.
2006, p. 89.
Таблица 3
Распределение итерация для различных параметров селективной стратегии
Отрезок
Количество попаданий
prob1
prob2
0<i<50
50<i<100
100<i<150
150<i<200
200<i<250
250<i<300
300<i<350
350<i<400
400<i<450
450<i<500
0.1
0.1
0.1
0.2
0.2
0.2
0.3
03.
0.3
0.1
0.2
0.3
0.1
0.2
0.3
0.1
0.2
0.3
164
168
142
128
102
69
75
64
47
40
245
253
168
107
71
58
42
29
10
16
316
281
174
98
54
22
16
22
5
11
175
101
115
102
120
93
88
72
74
60
155
153
147
125
106
89
67
57
56
45
208
198
167
145
88
72
41
31
28
21
176
86
98
88
86
99
106
96
85
77
172
117
117
108
109
107
83
78
61
48
181
165
133
116
108
99
67
48
47
35
Воронежский государственный университет
ООО “Люксофт Профешнл”
SOLUTION OF AN OPTIMAL ER-MODEL SEARCH TASK BASED ON GENETIC ALGOTIHM
A.V. Shalitkin, N.A. Tuykachev, P.A. Tsvetkov
A general task of optimal ER-model search is introduced in the article. In order to solve the task, the genetic algorithm
is used. Different parameter combinations are analyzed and the optimal one is proposed
Key words: ER-model optimization, genetic algorithm, GIS data model
Документ
Категория
Без категории
Просмотров
10
Размер файла
245 Кб
Теги
оптимальное, решение, генетического, алгоритм, обобщенные, основы, задачи, поиск, модель
1/--страниц
Пожаловаться на содержимое документа