ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2008, № 3, с. 125-132
СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 519.144.1+519.16
ЭВОЛЮЦИОННАЯ МОДЕЛЬ ДЛЯ ЕВКЛИДОВОЙ ЗАДАЧИ ШТЕЙНЕРА С ПОТОКАМИ И ЗАВИСЯЩИМИ ОТ НИХ ВЕСАМИ
© 2008 г. В. Д. Кукин
Петрозаводск, ИПМИ КарНЦ РАН Поступила в редакцию 5.05.06 г., после доработки 12.09.07 г..
Обсуждается эволюционная модель, разработанная для решения евклидовой задачи Штейнера с потоками и зависящими от них весами. Поиск решения задачи моделируется как процесс эволюции на двух взаимосвязанных уровнях: случайного видообразования и эволюции популяций отдельных видов. Для этого используются оригинальные генетические операторы.
Введение. На практике часто встречается следующая задача. Требуется построить сеть для транспортировки продукта в фиксированную точку из источников, расположенных в других фиксированных точках, с минимальными затратами на строительство и транспортировку. Для минимизации затрат разрешается вводить дополнительные точки. Это содержательная формулировка обобщения евклидовой задачи Штейнера [1] на случай с потоками и зависящими от них весами. Для краткости будем называть ее потоковой задачей Штейнера.
Проблема Штейнера относится к ^Р-трудным [2]. Для поиска решений таких задач используются приближенные и эвристические методы. Обзор методов, разработанных для проблемы Штейнера и некоторых ее обобщений в 70-90-е годы, приводится в [1, 3]. Их дополняет [4], где обсуждаются методы решения задачи для транспортной сети, основанные на синтезе топологии. Примерно в то же время нами был создан оригинальный алгоритм исчерпывающего и неизбыточного перебора полных топологий. Он находил точные решения задачи Штейнера небольшой размерности. Однако методология, заложенная в алгоритме, и эвристики, используемые для перестройки топологии, позволили организовать эффективный поиск приближенных решений задач большой размерности в интерактивном режиме [5, 6].
В настоящее время для решения комбинаторных задач активно применяются методы эволюционного моделирования. Ни монография [7], содержащая обзор этих методов и обширную библиографию, ни другие источники не подтвердили их применения к потоковой задаче Штейнера. Поэтому мы начали разработку эволюционной модели и генетических операторов для нее [8, 9]. В процессе эксперимента уточнялись структура модели и параметры операторов. В статье представлены модель, схема одного из алгоритмов, реализованных на ее основе, а также результаты вычислительного эксперимента.
1. Постановка задачи. Используя терминологию теории графов, обозначим: У0 - заданное множество вершин ориентированного графа (орграфа), называемых терминальными, |У0| = п; г0 е У0 -выделенная терминальная вершина, называемая стоком; М0 = (тг е Я+1 г е УМг'о}} - множество мощностей источников, расположенных в терминальных вершинах, за исключением стока; Х0 = ((хг, у) хг, у1 е Я+; г е У0}- заданное множество координат терминальных вершин; У, - множество дополнительных свободно размещаемых вершин орграфа, называемых точками Штейнера (ТШ), У, = я; X,. = ((х;,у) хг, у1 е Я+, г е У,} - множество координат ТШ; Ъ = {(г,;)| г,] е У0и У,} - множество дуг орграфа; I - евклидова метрика, 1(г, ;) = ((х; - х) -(уг - У,)2)1/2 - длина дуги (г, ;); - весовая функция, - значение весовой функции, зависящее от величины q(г,) потока на дуге, или вес дуги (г, ;); ь(г,}) = к,;) А?а ;)) - взвешенная длина дуги (г, ;).
В графовой постановке потоковая задача Штейнера - это следующий объект:
WSTР = (в0, М0,1, №, О, Яь) , где С0 = (У0, 0) - исходный орграф без дуг; О = (У, Ъ) решение задачи. Это орграф с множествами вершин У и дуг Ъ со свойствами:
1) О - дерево, ориентированное к корню г0,
2) У = У0 и У,,
3) сумма взвешенных длин Ь(г,) дуг орграфа минимальна
= X ЬС. Ш1П
(г,;)е Ъ
при следующих ограничениях на потоки: (Уг е ^М^Ь V; е V) q(¡,л - ^ 0 = тг>
к: (к, г)е Ъ
(Уг е У,, V; е У) q(¡, л - ^ q(k, I) =
к:(к, г) е Ъ
Граф с перечисленными свойствами является ориентированным деревом Штейнера (ДШ). Мно-
жеству О дуг орграфа соответствует некоторая топология т, определяющая порядок соединения его вершин т е Т, где Т - множество всех топологий на множестве вершин V. И наоборот, если на множестве точек V задана произвольная топология Т, то ей соответствует орграф со множеством дуг О = От. Можно дать комбинаторную постановку задачи, эквивалентную графовой.
В комбинаторной постановке потоковая задача Штейнера - это следующий объект:
~ЩБТР* = V Мо, Хо, I,№, (т, X,),
где (т, X,) - решение задачи. Для этой пары при заданных ограничениях на потоки сумма взвешенных длин дуг орграфа минимальна
= X Ь(Л ~* Мп-
те Т:(>, Де Ох
Здесь ДШ - дерево с минимальной для данной топологии суммой взвешенных длин. Оно имеет оптимальные координаты ТШ. Задача состоит в поиске минимального ДШ (МДШ), у которого есть минимальная сумма взвешенных длин дуг для всех возможных топологий.
Решая потоковую задачу в комбинаторной постановке, мы рассматриваем только деревья с полными топологиями [1], т.е. с максимальным числом ТШ (, = п - 2). Это не нарушает общности подхода, так как вырожденные дуги (нулевой длины), которые могут получаться при оптимизации положения ТШ, считаем полноправными элементами деревьев. Число вершин в них всегда равно N = 2п - 2. Это позволило унифицировать представление топологии и кодировать ее строкой фиксированной длины [8]. Достоинство такого подхода - уменьшение числа рассматриваемых топологий на много порядков [1].
Предполагается, чтоположительная вещественная вогнутая весовая функция. Она характерна для задач проектирования транспортных сетей, в которых минимизируются затраты на строительство и транспортировку грузов, и обычно интерполируется кусочно-линейной функцией
м = Щ) +
где К(#), Т^) - ступенчатые (кусочно-постоянные) функции, зависящие от потока на дуге. В транспортных сетях К(д) и Тт^) принято называть капитальной и транспортной составляющими соответственно. Дискретные значения этих функций определяются технологическими категориями коммуникаций. В большинстве таких задач из-за специфики коммуникаций весовая функция имеет разрывы первого рода в тех узлах, где при суммировании входящих потоков необходима смена категорий. Тогда при ограничениях на потоки минимизируется функция
й'ь = X [ К (?(, о) +
те Т:(>, }) е О,
+ Тт(( ?(,-, ^ ?(/, Л)1т^.
2. Эволюционная модель. Ориентация на современные представления об эволюционных процессах [10-13] позволила разработать модель для решения потоковой задачи Штейнера. При описании модели используются биологические термины и аналогии. Вид трактуется как совокупность популяций особей, имеющих сходные свойства и способных скрещиваться. Строка, кодирующая топологию дерева, интерпретируется как хромосома. Пара (т, Xs), представляющая топологию дерева и координаты ТШ, - особь. Множество особей одного вида образуют популяцию на ареале, заданном входными данными: (V0, X0, М0, l, Дq)). Конкретное дерево - особь на этом ареале: (V0, X0, M0, Vs, Xs, т). Качественные признаки дерева (потоки, значения весовой функции и взвешенные длины дуг) характеризуют фенотип особи. Он оценивается фитнес-функцией, соответствующей целевой функции задачи. В таком контексте поиску МДШ отвечает поиск особи с наилучшим фенотипом для заданной фитнес-функции.
2.1. Описание модели. Эволюционная модель - объект вида:
EM = {Str, Par, fit).
Структурные компоненты модели
Str = (ar, rp, P ,G, rmt, smt, cr, mat, pl, es),
где ar - ареал; rp - случайный родитель вида; P - популяция особей порожденного вида; G - элитная группа; rmt - оператор случайных мутаций; smt -оператор селективных мутаций; cr - оператор крос-синговера; mat - оператор развития; pl - оператор отбора в новое поколение популяции; es - оператор отбора в элитную группу.
Параметры модели
Par = (Л g, Z H, kn ksb ^ km1, km2),
где r - размер популяции; g - размер элитной группы; Z - параметр видообразования; H - параметр эволюции популяции; kr - норма оператора случайных мутаций; ks1 и k^ - нормы оператора селективных мутаций соответственно для глобального и локального действия; kc - норма оператора кроссин-говера; km1 и km2 - нормы оператора развития соответственно для глобального и локального действия.
Фитнес-функция: fit.
Для модели разработаны оригинальные генетические операторы [8]. Для отбора в новое поколение популяции и элитную группу можно использовать любые операторы отбора по фитнес-функции, применяемые в генетических алгоритмах (ГА) [7].
Обобщенная схема модели представлена на рис. 1. Поиск решения рассматривается как процесс эволюции на двух взаимосвязанных уровнях с разными временными шкалами. На верхнем уровне имитируется филогенез, т.е. историческое развитие видов. В дискретные моменты времени про-
исходит случайное видообразование без дивергенции видов, т.е. побочные линии их развития исключаются. Процесс начинается с особи предко-вого вида. В качестве нее можно задать любое дерево, но удобнее автоматически строить прародителя - дерево со специальной топологией [8]. Из особи предкового вида с помощью оператора rmt случайных мутаций генерируется первый случайный родитель rp, который дает начало популяции P этого вида. (Потом с помощью этого же оператора из первого родителя будет порожден основатель популяции следующего вида и т.д.) Начальная популяция формируется с помощью оператора smt селективных мутаций.
На нижнем уровне на заданном ареале ar моделируется эволюция популяции P порожденного вида. Оператор smt селективных мутаций и оператор cr кроссиноговера применяются для генерации нового поколения популяции. Селекция особей в новое поколение выполняется с помощью оператора pl отбора. Смена поколений происходит в дискретные моменты времени шкалы этого уровня. На обоих уровнях действует также оператор развития (maturation operator) - некий аналог онтогенеза (индивидуального развития особи). Вообще говоря, это более низкий уровень моделирования, не отраженный на схеме ради ее прозрачности. Элитная группа G обновляется за счет лучших особей, найденных в эволюционирующих популяциях разны
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.