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

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.