7.3. Исследование генетического алгоритма размещения

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

Здесь столбцы 5-9—это вероятности реализации операторов. В таблице столбец 11 — это условная начальная длина ребер графа, а столбец 12 —

конечная длина ребер графа. В столбце 13 приведено значение изменения суммарной длины ребер в процентах (А). На рис. 7.18 приведен график зависимости суммарной длины ребер графа от времени.

Из результатов исследования следует, что увеличение размера популяции и количества итераций алгоритма приводит к уменьшению суммарной длины, но только до некоторого предела. Для графа, описанного в таблице, были проведены испытания на основе классических последовательных, итерационных и релаксационных методов. При этом во всех случаях условная ЦФ была в среднем хуже чем в ГА с самоорганизацией на 40%, 30%, 20%

соответственно. Алгоритм позволяет в общем случае решать проблему предварительной сходимости и получать оптимальные результаты. В результате тестовых испытаний отметим следующее. Все теоретические предпосылки относительно преимуществ ГА с самоорганизацией подтвердились. Тогда ГА для размещения вершин графов позволяет всегда получать локальные оптимумы, иметь возможность выхода из них и приближаться к получению глобального оптимума, причем, что особенно важно, временная сложность алгоритма не уходит из области полиномиальной сложности (она приближенно равна 0{п logn)^O(n^)).