УДК 681.3
Калиниченко Ю.В.
ПОСТРОЕНИЕ ДЕРЕВА ШТАЙНЕРА ГЕНЕТИЧЕСКИМ АЛГОРИТМОМ
Луганский национальный университет имени Тараса Шевченка
The rectilinear tree of Shtajnera is used in telecommunications by optimization of routes of transfer of the multimedia data. The modified genetic algorithm Is offered. The algorithm uses coding of trees of candidates in which symbols from binary and not binary alphabets occupy alternative positions. The algorithm is realized by the new operator crossover.
Key words: rectilinear tree of Shtajnera , genetic algorithm , crossover
Прямолінійне дерево Штайнера використовується в телекомунікаціях при оптимізації маршрутів передачі мультимедійних даних. Пропонується модифікований генетичний алгоритм. Алгоритм використовує кодування дерев кандидатів, в якому символи з двійкового і недвійкового алфавітів займають альтернативні положення. Алгоритм реалізує новий оператор кросинговеру.
Ключові слова: прямолінійне дерево Штайнера, генетичний алгоритм, оператор кросинговеру.
Прямолинейное дерево Штайнера (ПДШ) используется в телекоммуникациях при оптимизации маршрутов передачи мультимедийных данных. Предлагается модифицированный генетический алгоритм. Алгоритм использует кодирование деревьев кандидатов, в котором символы из двоичного и недвоичного алфавитов занимают альтернативные положения. Алгоритм реализует новый оператор кроссинговера[1].
Кодирование хромосомы. На n точках существует 2n-1nn-2 прямолинейных деревьев Штайнера. Это означает следующее: n-1 двоичный символ, чередующийся с n-2 символами, выбранными из алфавита из n символов. Рассмотрим алгоритм кодировки для некоторого порядка вершин v1, v2 … vn.
1. Инициализируем переменную i равную 1. Инициализируем степени вер- шин.
2. Указываем первую вершину v0 (в соответствии с порядком) её степень равна 1. (v0, ai) есть ребро в покрывающем дереве. Уменьшение степени v0 и ai, и увеличение i.
3. Повторять шаг 2 пока степень каждой вершины не станет равной 0, кроме 2 вершин, чьи степени равны 1. Последнее ребро в покрывающем дереве соединяет эти две вершины.
Строка, которая кодирует ПДШ, включает двоичные символы. Эти символы определяют для каждого ребра покрывающего дерева ту точку из двух возможных, которая включена в дерево точки значение 0 указывает на то, что это левая точка Штайнера, а значение 1 – правая точка Штайнера. Первый двоичный символ указывает ту точку Штайнера из первого ребра, которая определяется хромосомой. Последний двоичный символ, являющийся последним символом в хромосоме, указывает на ту точку Штайнера, которая ассоциирована с ребром покрывающего дерева, которое выбирается алгоритмом в последнюю очередь [2].
Целевая функция. Целевая функция – это суммарная длинна ребер ПДШ. Задача алгоритма – минимизация целевой функции.
Оператор кроссинговера. Предлагаются два принципа оператора кроссин говера для этой задачи: потомки должны содержать структурные особенности (ребра, точки Штейнера) их обоих родителей; потомки должны сохранять любые ребра, являющиеся общими для двух родителей. Результирующий оператор кроссинговера генерирует одного потомка их двух родителей. Оператор копирует в потомка все пары прямолинейных ребер, соответствующих ребрам покрывающего дерева, которые делят между собой родители. Если ребра покрывающего дерева различаются только лишь в одной точке Штайнера, то оператор включает эти ребра покрывающего дерева и выбирает точку Штейнера произвольно. Затем выбирает пары прямолинейных ребер произвольно из двух родителей до тех пор, пока он не закончит формирование потомка ПДШ. Оператор отбрасывает любые пары ребер, которые создают циклы в потомках. Так как каждый родитель кодирует ПДШ, то для построения потомка ПДШ всегда берутся ребра их двух родителей. Нет необходимости вставлять произвольные ребра.
Оператор мутации модифицирует каждую позицию независимо с вероятностью в один процент. Затем мутация изменяет символ, новое значение которого выбирается из отличных от старого. Алгоритм применяет два оператора раздельно и каждый получает одного потомка. Генетический алгоритм использует строки со смешанным кодированием с альтернативными двоичными и не двоичными символами для представления эле- ментов пространства решения задачи.
Программа реализована на языке C++. Проведенные экспериментальные исследования показали преимущество использования генетического поиска при построении ПДШ по сравнению с итерационными методами. Они показали, что разработанный алгоритм позволяет получать не одно, а набор оптимальных, или квазиоптимальных результатов. На основе полученных данных определено, что экспериментальная временная сложность алгоритма ориентировочно составляет О(αn3), где α-коэффициент, n-число вершин графа. Применение новых и модифицированных методов поиска позволяет ускорить процедуру построения оптимального ПДШ.
Литература:
1. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования — М: Физматлит, 2003. — c. 432
2. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte — 2-е изд.. — М: Горячая линия-Телеком, 2008. — c. 452.