Cтраница 3
Решение одной и той же задачи может быть получено с помощью различных алгоритмов. Чтобы выбрать из множества алгоритмов наиболее подходящий, необходимо иметь способ их оценки. По-видимому, наиболее важными характеристиками алгоритма являются время и объем памяти, требуемые для получения решения. И то, и другое зависит от исходных данных, например от их размера. Время, затрачиваемое алгоритмом, как функция размера задачи называется временной сложностью алгоритма. [31]
Приведены основные критерии определения планарности графов. Описаны эвристические методы определения планарности и плоской укладки графов. Проанализирован генетический подход для решения данной задачи. Описан метод кодирования альтернативных решений и приведены операторы кроссинговера, мутации и инверсии, ориентированные на знания об исследуемых графах. Для непланарных графов рассмотрен ГА определения максимально планарной части графа и минимизации пересечений ребер. Временная сложность алгоритма близка к линейной зависимости. [32]
Первый подход заключается в следующем. Сначала формируется популяция решений, обычно случайным образом. Далее в каждом элементе популяции выполняется оператор мутации. Затем вычисляется ЦФ, производится сортировка решений и назначение элементов в заданные позиции. В случае необходимости производится возврат к ОМ, и вся процедура продолжается аналогично до преждевременной сходимости или пока не выполнится заданное число итераций. Данный подход является простым в реализации и имеет временную сложность алгоритма линейного типа, но получаемые локальные оптимумы далеки от глобального. Это связано с большим упрощением ЭМ и неиспользованием всей многогранности и широких возможностей моделей эволюции. [33]
Приведем структурную схему генетического поиска для решения переборных комбинаторно логических задач на графах ( рис. 6.74) на основе информирующих обратных связей и концепции объединенной эволюции. После реализации ГА на рисунке 6.74 компенсатор при взаимодействии с внешней средой реализует синергетические принципы, а фильтр хромосом поддерживает гомеостаз. При этом лучшие хромосомы отправляются для смешивания популяций и выхода из локальных оптимумов. Редуктор уменьшает размер популяции, устраняя хромосомы со значением ЦФ ниже средней. Блоки сумматор, редуктор и фильтр хромосом позволяют повысить эффективность реализации эволюции и скорость распознавания изоморфизма графов. Следует отметить, что в графах большой размерности с нетривиальными автоморфизмами ( К 100) процесс установления изоморфизма резко усложняется, но использование таких схем поиска на порядок снижает временную сложность алгоритма. [34]