7.5. Задачи построения независимыж множеств, раскраски графа

Задача построения независимых (внутренне устойчивых) подмножеств множества вершин графа неформально может быть сформулирована сле- дугош,им образом. В заданном графе определяется семейство подмножеств вершин. Внутри каждого подмножества вершины графа между собой не соединены ребрами. Добавление любой вершины графа к такому подмножеству делает его не внутренне устойчивым. Задачи такого рода актуальны, когда необходимо определить наибольшее число групп независимых объектов. Например, в отряде космонавтов определить наибольшее число групп совместимых людей для работы в космосе.

Для экспериментального исследования описанных алгоритмов построения независимых подмножеств были проведены тестовые испытания графов. На их основе построена таблица 7.4, в которую внесены результаты испытания алгоритмов определения независимых подмножеств. Количество вершин графа п = 100, количество ребер т = 400. В таблице в столбце 2 указан размер популяции, в 3 — число итераций, в 4, 5 — вероятности ОК, ОМ, в 6, 7 — приведены значения условной ЦФ как отношение количества определенных и суш,ествуюш,их независимых множеств и время решения в (сек) для ПГА. В 8, 9 — значения условной ЦФ и время для ГА с самоорганизацией.

На рисунке 7.23 показаны графики зависимости числа итераций от условной ЦФ при Р(ОК) = 0,8; Р(ОМ) = 0,2 и постоянном Np = 50 для ПГА и ГА с самоорганизацией. Как видно из графика, после двух тысяч итераций наступает насыщение, т. е. увеличение числа итераций не улучшает значение ЦФ для ПГА. Это говорит о том, что получен локальный или глобальный минимум для данной задачи. Управляя процессом генетического поиска, с помощью адаптации и обратных связей удалось найти параметры, при которых условная ЦФ имеет наилучшее значение. На рисунке 7.24 приведены графики зависимости времени решения от числа итераций. Заметим, что, как и в других задачах оптимизации на графах, время решения практически линейно зависит от числа итераций.

 

Временная сложность алгоритма, полученная на основе экспериментов, практически совпадает с теоретическими предпосылками. Для рассмотренных тестовых задач она в лучшем случае 0(п2 logn), а в худшем слу-

Задача раскраски графа — это разбиение множества вершин графа на подмножества несвязанных вершин. Количество подмножеств таких разбиений определяет число «цветов» для раскраски графа. Для экспериментального исследования описанных алгоритмов раскраски графов были проведены тестовые испытания. На их основе построена таблица 7.5, в которую сведены данные о тестовых задачах раскраски графов: количество вершин графа п = 100, количество ребер т = 400. В таблице в столбце 2 указан размер популяции, в 3 — число итераций, в 4, 5 — вероятности ОК, ОМ, в 6 и 7 приведены значения условной ЦФ как отношение количества определенных и суш,ествуюш,их цветов и время решения в (сек) для ПГА. В 8 и 9 столбцах — значения условной ЦФ и время для ГА с самоорганизацией.

На рисунке 7.25 приведены графики зависимости значения условной ЦФ от числа генераций, а на рисунке 7.26 — график зависимости времени решения при Np = 50 от числа итераций. Как следует из графиков, количество итераций почти не влияет на качество решения. Зато вероятность

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

Для тестовых графов на 100, 200, 300, 400 и 500 вершин были проведены испытания на основе классических последовательных, итерационных и комбинированных методов. При этом во всех случаях условная ЦФ была в среднем хуже чем в ГА с самоорганизацией, на 30%, 25%, 15% соответственно. Для рассмотренных тестовых задач временная сложность алгоритма в лучшем случае 0(п2 ), а в худшем случае 0(п"^). Эксперименты показали, что не всегда увеличение размера популяции улучшает ЦФ. Очевидно, что существует какой-то определенный размер популяции, соответствующий оптимальному значению ЦФ, отыскать который чрезвычайно трудно.