ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2010, № 2, с. 61-67
== КОМПЬЮТЕРНЫЕ МЕТОДЫ =
УДК 519.144.1+519.16
ГЕНЕТИЧЕСКИЕ ОПЕРАТОРЫ ЭВОЛЮЦИОННОЙ МОДЕЛИ ДЛЯ ПОТОКОВОЙ ЗАДАЧИ ШТЕЙНЕРА
© 2010 г. В. Д. Кукин
Петрозаводск, ИПМИ КарНЦ РАН Поступила в редакцию 30.06.09 г.
Рассматриваются оригинальные генетические операторы, применяемые в эволюционной модели для решения задачи Штейнера с потоками и зависящими от них весами. Ключевым моментом в их разработке стало кодирование хромосомы, основанное на представлении полной топологии дерева в виде унифицированной строки фиксированной длины.
Введение. Настоящая статья — естественное продолжение [1], где представлена эволюционная модель для задачи Штейнера с потоками и зависящими от них весами. Эта задача, называемая потоковой, является обобщением евклидовой задачи Штейнера [2]. Ее можно рассматривать в приложении к различным коммуникационным сетям: она инварианта относительно ориентации потоков. Для транспортной сети задача формулируется следующим образом.
На евклидовой плоскости надо построить сеть в виде ориентированного корневого дерева, дуги которого соединяют п фиксированных терминальных вершин (одна из которых корень) и произвольное число ж дополнительных свободно размещаемых вершин, называемых точками Штей-нера (ТШ). В п — 1 терминальных вершинах находятся источники с заданными мощностями, а в корне — единственный сток. Топология дерева описывает порядок соединения его вершин. Источники порождают потоки по дугам, на которых задается весовая функция — положительная действительная вогнутая функция от величины потока. Значение весовой функции на дуге интерпретируется как ее вес, а длина дуги, умноженная на ее вес, — как взвешенная длина. Ищется минимум целевой функции — суммы взвешенных длин всех дуг дерева. Размерность задачи — число терминальных вершин: п > 4.
Дерево Штейнера (ДШ) — это относительно минимальное дерево для данной топологии, т.е. дерево с оптимальными значениями координат ТШ. Оптимальное решение задачи — минимальное ДШ, оно имеет минимальное значение целевой функции среди всех ДШ на заданном множестве терминальных вершин.
Многие задачи комбинаторной оптимизации, в частности, задача Штейнера, относятся к классу ^Р-трудных [3]. Для их решения применяются различные приближенные методы. Для потоковой задачи Штейнера нами принят подход, осно-
ванный на методологии эволюционного моделирования [4]. Любой эволюционный метод характеризуют три составляющие: способ представления хромосомы и принцип ее кодирования/декодирования; генетические операторы; эволюционная модель. В предложенном методе все эти составляющие оригинальные. В [1] основное внимание уделяется эволюционной модели и композитному алгоритму. Настоящая статья представляет принцип кодирования/декодирования топологии дерева, отождествляемой с хромосомой, и эвристические генетические операторы.
1. Представление топологии. Решая потоковую задачу Штейнера, мы приняли основанное на позиционном способе компактное представление топологии дерева в виде строки. Оно давно известно и неоднократно "открывалось" разными исследователями. Иногда такое представление связывают с методом Прюфера [5], разработанным в начале XX в. Условимся нумеровать вершины дерева натуральными числами. Пусть терминальные вершины имеют номера от 1 до п и номер корня всегда 1, а ТШ — номера от п + 1 до N. Топология ориентированного дерева представляется в виде следующей строки:
Т = (11, ¡2, Н, "• ¡1, ••• 1п -1, 1п, ¡п + 1, — ••• Здесь индексы элементов строки соответствуют номерам начальных вершин дуг дерева, а значения элементов есть номера конечных вершин этих дуг. Смысл позиционного представления такой: если 1-й элемент строки Т имеет значение 11 = = т, то в моделируемом дереве есть дуга (/, т), т.е. дуга с начальной вершиной I и конечной вершиной т. Такое представление топологии однозначно определяет дерево, а разным деревьям соответствуют разные представления.
Длина строки топологии равна числу всех вершин моделируемого дерева N = п + ж, где число точек Штейнера ж может быть от 0 до п — 2. Топология с максимальным числом ТШ ж = п — 2 называется полной топологией [2]. Мы работаем толь-
Рис. 1. Дерево с топологией То
ко с такими топологиями. Это не нарушает общности подхода: при оптимизации положения ТШ некоторые дуги могут стать вырожденными (нулевой длины), но они считаются полноправными элементами дерева, и его топология формально остается полной. Такой подход позволил перейти к представлению топологии в виде строки фиксированной длины N = 2п — 2
т = (Л, ¡2, Н, ••• ¡¡, ••• 4-1,
П ¡п + 1, ••• ] ••• ¡2п-4, ¡2п-3, ¡2п — 2).
В дереве с полной топологией все внутренние вершины - точки Штейнера, а терминальные вершины всегда концевые. В ТШ входят две дуги, а выходит одна. Тогда очевидно, что элементы строки, за исключением первого и последнего,
есть номера ТШ, т.е. принимают значения от п + 1 до 2п — 2. Каждый из номеров присутствует в строке дважды. Поясним смысл исключений. Корню дерева всегда присваивается номер 1, а поскольку из первой вершины нет выходящей дуги, вводится фиктивная вершина 0 и фиксируется значение = 0, что соответствует фиктивной дуге (1, ¡1) = (1, 0). Далее, начальной вершине корневой дуги (последней в дереве) всегда можно присвоить номер 2п — 2, т.е. номер последней ТШ. Конечная вершина последней дуги - корень дерева: вершина с номером 1, т.е. 12п — 2 = 1. Так фиксируется дуга (2п — 2, 12п -2) = (2п — 2, 1).
Кроме этих двух исключений можно закрепить в представлении топологии еще один элемент. Рассматриваются задачи для п > 4, поэтому одна из двух дуг, входящих в последнюю ТШ (ближайшую к корню), обязательно должна быть внутренней. Значит, всегда можно присвоить ее начальной вершине постоянный номер 2п — 3 — номер предпоследней ТШ. Так как предпоследняя дуга входит в последнюю ТШ, то 12п _ 3 = 2п — 2, т.е. зафиксирована дуга (2п — 3, 12п — 3) = (2п — 3, 2п — 2). Унифицированная строка, представляющая топологию, имеет вид
T = (0, ¡2, ¡3, ... 4, ... 1п- 1,
¡п, ¡п+1, ... ] ... ¡2п — 4, 2п — 2, 1).
Для примера рассмотрим дерево с топологией То', показанное на рис. 1.
В этом дереве п = 10 терминальных вершин. Они пронумерованы натуральными числами от 1 (корень) до 10, а ТШ — числами от 11 до 18. Топология Т0 представлена строкой длины N = = 2п—2 = 18
- = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
0 (0, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 1) .
Здесь верхняя строка, приведенная для наглядности, показывает индексы элементов ТО. Эти индексы соответствуют номерам начальных вершин дуг дерева (они же считаются и номерами дуг). Элементы ТО — номера конечных вершин этих дуг, — это номера ТШ, за исключением первого и последнего элементов. Три элемента (первый и два последних) фиксированы. Смысл позиционного представления Т0' следующий. Дуги 2 и 3 дерева идут в точку Штейнера 11, и этот номер стоит в позициях 2 и 3 в ТО; дуги 4 и 5 идут в ТШ 12, и ее номер занимает позиции 4 и 5 и т.д. Дуга 18 идет в корень 1, а фиктивная дуга 1 — в фиктивную вер-
шину 0, поэтому значения 1 и 0 находятся соответственно в позициях 18 и 1 этой строки.
2. Генерация полных топологий с помощью перестановок. Опираясь на описанное представление, сформулируем принцип кодирования полных топологий и их генерации с помощью перестановок. Абстрагируясь от природы элементов, кодируем топологию T строкой, элементы р х которой принадлежат множеству Р = {1, 2, ... 2п — 2}. Следующая запись строки топологии под строкой перестановки устанавливает соответствие между их элементами, которое используется при кодировании/декодировании (переходе от топологии к перестановке и обратно)
Т =
(Р1 Р2 Р3 ••• Р1 — Рп - 1 Рп Рп + 1 ••• Р Р2п - 4 Р2п - 3 Р2п - 2)
(о, ?2, (з, ... ь, ... гп-1, п 1«+1, • ь, ... I
2п -4
2п - 2, 1).
Если в кодирующей строке элементр! = к, а в строке топологии 11 = т, то при декодировании топологии вместо к будет подставляться конкретное значение т номера ТШ. Временная сложность такого кодирования/декодирования 0(Щ, где N = 2п — 2.
Ниже показано правило кодирования/декодирования, применяемое при генерации топологий.
В качестве начальной перестановки взята единичная перестановка, которая оставляет все элементы на месте. В качестве начальной топологии выбрана топология Т0, в представлении которой номера ТШ расположены в неубывающем порядке. Дерево с такой топологией будем называть прародителем. Получим следующее соответствие
- (1
5 ... к к + 1 ... 2п - 4 2« - 3 2п - 2)
(0, п + 1, п + 1, п + 2, п + 2, ... т, т, ... 2п - 2, 2п - 2, 1).
Из множества перестановок, кодирующих топологии, выбираются только те, в которых остаются на своих местах три элемента: р1 = 1; р2п — 3 = = 2п — 3; р2п — 2 = 2п — 2. Таким образом, в перестановках участвуют только N — 3 = 2п — 5 элементов. Число всех перестановок, удовлетворяющих этому условию, равно (2п — 5)! После декодирования многие перестановки дают представления топологий изоморфных деревьев. Во-первых, номер каждой ТШ соответствует двум разным элементам перестановки, поэтому появляются одинаковые представления топологий. Во-вторых, некоторые перестановки порождают разные представления, которые соответствуют изоморфным деревьям с точностью до перенумерации ТШ. Число таких "излишеств" при увеличении размерности задачи п растет катастрофически быстро.
Число неповторяющихся топологий с разным числом ж ТШ значительно меньше (2п — 5)!. При работе только с полными топологиями число просматриваемых топологий сокращается на много порядков. Используя формулу числа всех топологий, приведенную в [2], или рекуррентный вывод, нетрудно показать, что число полных топологий для задачи размерности п выражается формулой М = (2п — 5)!! Как видим, в ней фигурирует число 2п — 5, т.е. количество элементов, фактически участвующих в перестановках. Это подтверждает оптимальность принятого принципа кодирования полных топологий.
В свое время автору удалось создать алгоритм исчерпывающего и неизбыточного перебора полных топологий [6], основанный на перестановках. Топология
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.