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

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

Все выше приведенные рассуждения, ограничения и экспериментальные данные объясняют постулированное в самом начале главное ограничение. Удаление ребра, обе вершины которого глобальные вершины, абсолютно неэффективная процедура.

Для максимального улучшения дерева можно добавить также процедуру объединения вершины и свободного ребра: сначала в качестве самостоятельного этапа, а затем в составе процедуры перестроения поддеревьев (стратегия K приложения). Этот метод аналогичен процедуре объединения двух свободных ребер (рисунок 3.8).

Рисунок 3.8 - Процесс объединения свободного ребра и вершины

(a) исходная конфигурация;

(b) в дерево добавляется ребро CD, соединяющее свободное ребро AB и вершину C;

(c) в возникшем цикле удаляется самое длинное ребро.

Выигрыш в данном случае составляет 1 условную единицу длины.

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

- новые свободные ребра - все вершины поддерева;

- все новые и измененные вершины поддерева - все старые и новые свободные ребра.

3.5 Стратегии алгоритма

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

Стратегия A - локальное перестроение дерева для всех глобальных точек.

Стратегия B - локальное перестроение дерева для всех дополнительных точек.

Стратегия C - объединение двух вышеописанных стратегий A и B.

Стратегии D, E, F аналогичны стратегиям A, B, C соответственно, но в каждом случае локального перестроения дерева включены в рассмотрение инцидентные точки второго уровня.

Все нижеследующие стратегии содержат стратегию C в качестве первого этапа (кроме специально оговоренного случая).

Стратегия G - процедура объединения свободных ребер.

Стратегия H - процедура объединения всех ребер (горизонтальных, вертикальных и свободных).

Все нижеследующие стратегии содержат стратегию G в качестве второго этапа.

Стратегия I - процедура удаления ребер с дополнительными точками. В качестве процедуры перестроения поддеревьев используется локальное перестроение дерева для глобальных и дополнительных точек.

Стратегия J - то же самое, что и стратегия I, но в процедуру перестроения поддеревьев добавлена процедура объединения свободных ребер.

Стратегия K - то же самое, что и стратегия J, но добавлена процедура объединения точек и свободных ребер в качестве отдельного этапа и в составе процедуры перестроения поддеревьев.

Стратегия L - стратегия максимального улучшения начального дерева Штейнера. Включает в себя все процедуры стратегии K, но во всех местах своего использования метод локального перестроения дерева заменен той же процедурой, но с использованием точек второго уровня инцидентности.

3.6 Заключительный вид алгоритма

Исходный алгоритм последовательного введения дополнительных точек в дерево ПримаКраскала выглядит теперь следующим образом:

- 1 этап: предварительная отбраковка дополнительных вершин;

- 2 этап: последовательное введение дополнительных вершин в дерево Прима;

- 3 этап: динамическое перестроение дерева Штейнера.

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

Для этапа перестроения предлагается использовать стратегию J. Эта стратегия в сравнении с другими имеет лучшее соотношение числа положительных исходов ко времени счета. Среднее число положительных исходов при применении данного метода составляет несколько процентов для задач с 6-ю - 7-ю точками, уже около двух десятков процентов для задач с 10-ю точками и больше 90% для задач с 60-ю точками.

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

3.7 Генетические алгоритмы

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

Популяция - набор решений.

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

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

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

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

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

Оператор мутации случайно выбирает ген в хромосоме и обменивает его на рядом расположенный ген.

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

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

3.8 Результат работы алгоритма

В итоге работы второго этапа алгоритма построения маршрута должна быть получена структура (маршрут рассылки), соответствующая конкретному случаю. Т.е. определены связи, ведущие к нужным абонентам и затрачивающие на это минимум ресурсов. В этом случае могут использоваться соединения между абонентами, минуя промежуточные узлы, к тому же не всегда в рассылке должны быть задействованы все абоненты.

Пример полученного маршрута для схемы сети, представленной на предыдущем этапе, показан на рисунке 3.9.

Рисунок 3.9 - Пример построенного маршрута рассылки

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

4 РЕАЛИЗАЦИЯ АЛГОРИТМА

4.1 Постановка задачи разработки программного продукта

Задача разработки программного продукта состоит в том, чтобы он предоставлял необходимые возможности. А именно:

- возможность создания и редактирования сети, т.е. добавление и удаление узлов и связей;

- визуализация схемы построенного маршрута;

- вывод результатов расчетов для пересылки по построенному маршруту;

- возможность настраивать параметры алгоритма для получения наиболее оптимального результата;

- предоставление необходимой информации о программе и правилах работы с ней (помощь);

- удобный пользовательский интерфейс.

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

Структура ПП должна учитывать все перечисленные выше технические и функциональные требования.

Сложность генетических алгоритмов при решении задачи Штейнера состоит в кодировке исходных данных. В то же время эта кодировка не применима при создании структуры сети и ее отображении.

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

4.2 Описание структур данных

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

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

Структура узлов:

Point = record

x,y:integer;

t:boolean;

end;

Здесь x и y - координаты узла на плоскости сети, t - его тип (активный или неактивный).

Структура связей:

Link = record

b,e:byte;

t:boolean;

p:real;

end;

Поля b и e обозначают номера начального и конечного узлов связи соответственно, t - тип связи (используется ли она в построенном маршруте), p - стоимость пересылки данных по этой связи.

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

Конкретный механизм совмещения обработки и представления хромосом будет разработан в соответствии с выбранным алгоритмом.

4.3 Настройки алгоритма

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

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

В данном ПП предполагается предоставить такие возможности по настройке алгоритма построения маршрута:

- выбор метода отбора предков: равномерный, пропорциональный;

- выбор оператора кроссинговера: одноточечный или двухточечный;

- выбор оператора мутации: сколько генов будет изменяться и как будет происходить их отбор;

- выбор степени элитизма: какой процент наилучших хромосом попадет в следующую популяцию без изменения.

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

ВЫВОДЫ

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Дюк В., Самойленко А. Data Mining: учебный курс. - СПб: Питер, 2001. - 386с.

2. Калашников Р.С. Построение дерева Штейнера методом генетического поиска // Перспективные информационные технологии и интеллектуальные системы. - 2005. - № 2 (22).

3. Курейчик В.М. Генетические алгоритмы. - Таганрог: изд-во ТРТУ, 1998. - 242 с.

4. Маршалл У. Берн, Рональд Л. Грэм Поиск кратчайших сетей. // Scientific American (издание на русском языке). - 1989. - № 3. - С. 64-70.

5. Панченко Т.В. Генетические алгоритмы: Учебно-методическое пособие / под ред. Ю.Ю. Тарасевича. - Астрахань: АГУ, 2007. - 87 с.

6. Рыженко Н.В. Алгоритм построения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики. Труды ИМВС РАН, 2002.