Эволюционные механизмы формирования з-областей - Эволюционные процедуры решения комбинаторных задач на графах
Формирование З-областей в матрице R осуществляется в процессе ее эволюционной модификации. Эволюционная модификация матрицы R производится путем выборочных групповых перестановок соседних столбцов и строк, что обеспечивает направленное последовательное перемещение элементов матрицы R с нулевым значениями и объединение их в З-области.
Адаптивный процесс состоит из повторяющихся шагов, каждый из которых представляет собой переход от одного решения (состояния матрицы R) к другому - лучшему [Лебедев, 1999].
На каждом шаге анализируются пары (I, i+1) соседних строк матрицы. Анализ осуществляется в два такта. На первом такте анализируются все пары (I, i+1), у которых первый элемент I-нечетное число. На втором такте анализируются пары, у которых первый элемент I-четное число.
Например: пусть N=9, тогда на первом такте рассматриваются пары строк {(1,2),(3,4),(5,6),(7,8)}. На втором такте - {(2,3),(4,5),(6,7),(8,9)}.
Пары строк анализируются независимо друг от друга. По результатам анализа принимается решение о перестановке соседней пары строк.
Локальная цель перестановок - перемещение нулевых элементов матрицы снизу-вверх и справа-налево. Глобальная цель - формирование з-области Pi(l, m) с максимальным значением параметра m, то есть выделение максимального внутренне-устойчивого множества.
Пусть для анализа выбрана пара строк (I, i+1) матрицы R=||rIj|| Размером N*n .В строках выделяют две части: 1 - (j=1чi-1); 2 - J=i+2чn).Суть анализа заключается в определении истинностного значения трех нижеприведенных условий.
1. > - 1-я часть.
2. = - 1-я часть, и> - 2-я часть.
3. = - 1-я часть, и= - 2-я часть.
Ответ "да", то есть - переставлять, вырабатывается, если выполняются условия 1 и 2 . В случае выполнения условия 3 ответ "да" вырабатывается с вероятностью P, задаваемой априорно. В остальных случаях вырабатывается ответ "нет".
Адаптивная поисковая процедура продолжается, пока существуют пары, для которых выполняются условия 1 и 2. в результате будет сформирована З-область P1(1,m) и в графе GD определено максимальное внутренне-устойчивое подмножество X1D.
Если целью поиска было нахождение максимального паросочетания, то работа алгоритма на этом завершается.
Если же решается задача раскраски, то в графе GD удаляется подмножество вершин X1D, а из матрицы R удаляются M столбцов и строк, покрывающих область P1(1,m). Образуя граф G1D и матрицаR. Далее над полученной матрицей R1 производится аналогичные действия, то есть в G1D Выделяется максимальное внутренне-устойчивое подмножество X2D .Выше перечисленные действия продолжаются, пока матрица смежности не станет пустой, т. е. все вершины будут окрашены.
Пример. Пусть дан граф G , представленный на рис. 1. Двойственный к графу G граф GD представлен на рис. 2.
Матрица смежности графа GD представлена на рис. 3.
На каждом шаге, на первом такте рассматриваются пары {(1,2),(3,4),(5,6), (7,8)}, на втором такте - пары {(2,3),(4,5),(6,7), (8,9)}. Пара строк и столбцов переставляется, если выполняется одно из трех вышеперечисленных условий. В исходной матрице R столбцы и строки помечены номерами вершин графа GD. Перестановка соседней пары строк (I, i+1) или столбцов приводит также к перестановке их меток. Будем в дальнейшем для идентификации строк и столбцов использовать их метки.
Шаг 1, такт 1: (1,2) - нет; (3,4) - да (по условию 1); (5,6) - нет, (7,8) - нет. Итак, на 1-м такте 1-го шага осуществляется перестановка пары (3,4). Модифицированная матрица R после шага 1,1 представлена на рис. 5.
Шаг 1, такт 2: (2,4) - да (по условию 1), (3,5) - да (по условию 1), (6,7) - да (по условию 1), (8,9) - да (по условию 1). Модифицированная матрица R после шага 1,2 представлена на рис. 6.
Шаг 2, такт 1: (1,4) - нет; (2,5 ) - да (по условию 1); (3,7) - да (по условию 1); (6,9) - да (по условию 1). Модифицированная матрица R после шага 2,1 представлена на рис. 7.
Шаг 2, такт 2: (4,5) - нет; (2,7) - да (по условию 1); (3,9) - да (по условию 1); (6,8) - да (по условию 1). Модифицированная матрица R после шага 2,2 представлена на рис. 8.
Шаг 3, такт 1: (1,4) - нет; (5,7) - да (по условию 1); (2,9) - да (по условию 1); (3,8) - да ( по условию 1). Модифицированная матрица R представлена на рис. 9.
Шаг 3, такт 2: (4,7) - нет; (5,9) - да (по условию 1), (2,8) - нет; (3,8) - нет. Модифицированная матрица R представлена на рис. 10.
После выполнения трех шагов в модифицированной матрице сформировано три -Области: P1(1,4), P2(5,3), P3(8,2). Поскольку в исходном графе G содержится 8 вершин, то максимальное паросочетание может включать четыре ребра. -Области P1(1,4) соответствуют четыре вершины графа GD , которым в исходном графе G соответствует паросочетание из четырех ребер - (1,4,7,9).
Рис. 5. Матрица R после 1,1 шага Рис. 6. Матрица R после 1,2 шага
Рис. 7. Матрица R после 2,1 шага Рис. 8. Матрица R после 2,2 шага
Рис. 9. Матрица R после 3,1 шага Рис. 10. Матрица R после 3,2 шага
Сформированные области P1(1,4), P2(5,3), P3(8,2) покрывают все столбцы и строки матрицы R. Следовательно, граф GD можно раскрасить в 3 цвета: 1 цвет - вершины 1,4,7,9; 2 цвет - вершины 5,2,8; 3 цвет - вершины 3,6.
Для преодоления локального барьера, используются подходы, основанные на сочетании различных видов эволюции.
В первом подходе используются идеи метода моделирования отжига. Если в процессе анализа обнаруживается, что условия 1,2,3 не выполняются, то перестановка осуществляется с вероятностью P=exp(-?F/kT), где T - температура, ?F - Разница между суммами значений элементов анализируемых строк.
Во втором подходе используется одна из структур генетического поиска [Лебедев, 2000]. Популяция представляет собой множество матриц смежности (закодированных в виде хромосом). Декодирование, т. е. получение решения, осуществляется с помощью вышеописанной адаптивной процедуры.
Временная сложность адаптивной процедуры на одном шаге - О(n). Сравнение с известными алгоритмами показало, что при меньшем времени работы новый алгоритм дает более качественные решения.
Похожие статьи
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
-
Приведем систему ограничений к каноническому виду, для этого необходимо неравенства преобразовать в равенства, с добавлением дополнительных переменных....
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейного функционала при линейных ограничениях. В литературе...
-
Любое частное решения уравнения (1) на координатной плоскости х0у изображено в виде графика функции у=у (х, с) (с=const). В теории дифференциальных...
-
Симплекс-метод - Приложение интегрального и дифференциального исчисления к решению прикладных задач
Теория: Другой способ решения задач линейного программирования - симплекс-метод. Он, в отличие от геометрического, является полностью аналитическим, что...
-
Введение - Приложение интегрального и дифференциального исчисления к решению прикладных задач
Целью данной курсовой работы является самостоятельное изучение следующих разделов высшей математики: задачи линейного программирования (симплексный и...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
Так как целевая функция не является линейной, то эта задача является задачей нелинейного программирования. Найдем ее решение, используя геометрическую...
-
Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции P1 P2 P3 P4 S1 4 1 1 1 3 S2 18 2 4 6 1 Прибыль от единицы...
-
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
Рассмотрим взвешенный предфрактальный граф, порожденный затравкой и K процессоров, где. Параллельный алгоритм выделения дольного графа основан на...
-
Матрицы и определители - Методы решения системы линейных уравнений
Определение. Матрицей размера mn, где m - число строк, n - число столбцов, называется таблица чисел, расположенных в определенном порядке. Эти числа...
-
Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G...
-
Определители (детерминанты) - Методы решения системы линейных уравнений
Определение. Определителем квадратной матрицы А= называется число, которое может быть вычислено по элементам матрицы по формуле: Det A = , где (1) М1к -...
-
Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й...
-
Процедура решения задач минимизации издержек - Модель оценки издержек в системе складского комплекса
Пусть Z есть вектор, компонентами которого являются все переменные, по которым проводится оптимизация, то есть все компоненты вектора Z . В соответствии...
-
Технология разработки формы для ввода исходных данных средствами VBA Для разработки формы ввода исходных данных необходимо отобразить вкладку...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Пусть на некотором отрезке [a, b] задана кусочно-монотонная функция f(x). Покажем, что данную функцию в точках ее непрерывности можно представить в виде...
-
Исследуем на экстремум функцию: 1. С помощью необходимого существования экстремума, т. е. из системы Найдем координаты стационарных (критических) точек:...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Решение задачи графическим методом - Математическое моделирование в менеджменте и маркетинге
Необходимо найти максимальное значение целевой функции L(x)= 2x1+2x2 > max, при системе ограничений: 6x1+8x2?48, (1) 8x1+11x2?88, (2)...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Известно оптимальное решение X*=(0;0;1;1) задачи линейного программирования: Составьте двойственную задачу и найдите ее оптимальное решение по теореме...
-
При написании программ численного интегрирования желательно, чтобы для любой функции распределение узлов являлось оптимальным или близким к нему. Однако...
-
Теория: Применяется, как правило, для задач линейного программирования, содержащих не более 2 переменных. Суть геометрического метода сводится к...
-
Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...
-
Иногда необходимо управлять сложными комплексами взаимосвязанных работ, направленных на достижение определенных целей. Примерами таких комплексов в...
-
Исторические сведения о производной - Применение производной в решении геометрических задач
Ряд задач дифференциального счисления был решен еще в древности. Такие задачи можно найти у Евклида и у Архимеда, но само понятие производной функции...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
Задача Джонсона о двух станках Рассмотрим задачу последовательной обработки на двух машинах N различных деталей, если известно время Ai и Bi обработки...
Эволюционные механизмы формирования з-областей - Эволюционные процедуры решения комбинаторных задач на графах