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

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

Ключевые слова: поток данных, адаптация, эволюция, оптимизация, эволюционный поиск.

Введение

При построении статической модели задачи о потоке минимальной стоимости постоянными являются данные о смежности вершин графа и стоимости передачи сообщений. Две вершины графа i и j соединяются дугой (i, j) только в том случае если из вершины Ai можно передать данные в вершину Aj. Каждой такой дуге назначается вес, соответствующий времени передачи единицы информации от Ai к Aj. Таким образом, матрица смежности ||ai, j||n, m описывает возможные направления передачи данных, матрица ||ci, j||n, m предельно допустимое количество данных передаваемых от вершины Ai к Aj. Матрица ||xi, j||n, m отражает количество данных фактически передаваемых в единицу времени.

Граф, описываемый матрицей ||ai, j||n, m является ориентированным и может быть циклическим. Так как при решении задач оптимизации удобнее использовать граф, не содержащий циклов, имеющийся циклический граф можно привести к эквивалентной ациклической форме. Графы подразумеваются эквивалентными в контексте однозначности описываемых ими маршрутов передачи данных. Задачу получения ациклического графа в терминах целочисленного линейного программирования можно трактовать как задачу о покрытии. Из полученного ациклического графа можно получить последовательный, т. е. удовлетворяющий трем свойствам [1,2]:

• — граф обладает порядковой функцией Р (х) со значениями 0, 1,…, n, где n — количество слоев, на которые разбит граф;
• — вершины, находящиеся в одном слое не инциденты друг другу;
• — количество дуг, исходящих из слоя Si, i=1,., n-1 совпадает с количеством дуг, входящих в слой Si+1, i=1,., n, причем в слой Si могут входить лишь дуги из слоев Sk с номерами k<i, k =1, 2,. .,i-1.

Модернизируем матрицу ||ai, j||n, m, добавив в качестве (m+1) -го столбца вектор столбец, координаты которого вычисляются на основе формулы:

где i=1,2,.,n.

Вершины k для которых ak, m+1 =0 не имеют исходящих дуг и образуют первый слой S1 для которого справедливо P(S1)=1.

Элементы вектора столбца ak, m+2 определяются по формуле:

где i=1,2,.,n.

Второй слой S2 составляют нулевые значения столбца ak, m+2. Для вершин, образующих слой S2, справедливо P(S2)=2. Аналогично вычисляются последующие слои, общее количество всех слоев не превышает n.

На основе матрицы ||ai, j||n, m и функции P вводятся фиктивные вершины и дуги. Если ai, j =1, т. е. от вершины ai дуга ведет к вершине aj и P(ai)< P(aj), то во все промежуточные слои вводятся вершины соединяемые дугами нулевого веса. Первая фиктивная дуга, идущая от ai к первой фиктивной вершине, обретает вес ci, j. Фиктивные дуги и вершины не вводятся в случае, если вершинам i и j соответствуют значения порядковой функции P, отличающиеся на единицу.

В полученном последовательном графе, двудольный граф разбивается на два подграфа. К полученным подграфам применяется метод Форда, исходя из которого, образуются подпопуляции, А 1, …А_Count формирующие начальные решения. [2,3].