Применение линейных деревьев для формирования графа заданной структуры с помощью эволюционного программирования
В настоящий момент существует большое количество оптимизационных задач, решаемых с помощью генетического программирования. В качестве функциональной единицы в таких задачах чаще всего выступают деревья. При «выращивании» графа заданной структуры в качестве функциональных единиц – хромосом, которые представляют собой потенциальные решения, являются графы. Такое кодирование хромосом является не совсем тривиальной задачей. Особую сложность в данном случае составляет применение основных генетических операторов: кроссовера и мутации. В отличие от строк и деревьев, в которых точку кроссовера можно выбирать в произвольном месте, для графа необходимо выбирать точку разрыва таким образом, чтобы структура результирующих графов была допустимая: не образовывалось циклов, и граф оставался связным.
Возникает задача проектирования эффективного внутреннего представления графов (хромосом), к которым можно было бы легко применить основные генетические операторы, а также использовать простой алгоритм формирования начальной популяции, обеспечить высокую скорость вычисления фитнес-функции, иметь разумные требования к оперативной памяти и вычислительным ресурсам ЭВМ. То есть в целом необходимо уменьшить ресурсоемкость алгоритма формирования графа заданной структуры и, как следствие, увеличить эффективность получаемых решений. Мы рассмотрим подход с применение линейных деревьев. Он состоит из двух этапов: формирование наборов деревьев и последующего объединения этих деревьев в граф.
Необходимым условием применимости данного подхода является возможность выделения трех групп вершин в результирующем графе: исходных, промежуточных и целевых, а также возможность задания правил для формирования путей в графе. Исходные вершины определяют начальные вершины путей по графу, целевые вершины – это конечные вершины путей, а промежуточные вершины берутся из заданного набора и определяют непосредственно структуру графа.
Следующим шагом является формирование деревьев, у которых корневой вершиной является одна из целевых вершин, а листовыми будут все исходные вершины результирующего графа. Задача формирования дерева для заданных условий в генетическом программировании является достаточно простой и в случае использования линейного представления деревьев не требует больших вычислительных ресурсов.
После отработки генетического алгоритма получаем наборы деревьев для каждой целевой вершины графа. Обычно по окончании работы генетического алгоритма мы имеем несколько оптимальных решений, а также большое число «хороших», близких к оптимальным. Во множестве полученных решений рекомендуется оставить и те и другие.
Следующим этапом построения графа является этап объединения деревьев из разных наборов за счет общих фрагментов с одновременной оптимизацией результата объединения. То есть на данном этапе мы ищем наилучшие сочетания деревьев из разных наборов для построения графа. Данная процедура может быть выполнена как обычным перебором, так и еще одним генетическим алгоритмом.
Описанные выше подход показал высокую эффективность при проектировании комбинационных схем с разветвлениями при заданных ограничениях на сложность и время срабатывания. В качестве проверочной задачи была рассмотрена задача формирования полного одноразрядного двоичного сумматора по заданной таблице истинности. Логическая схема сумматора была представлена графом с 2-мя целевыми и 3-мя исходными вершинами. В качестве множества промежуточных вершин выступали элементы «И», «НЕ». Для каждого выхода сумматора был получен набор деревьев (схем) по заданной таблице истинности, после объединения которых получался граф, описывающий логическую структуру полного одноразрядного сумматора. Полученное решение отличалось от оптимального на один функциональный элемент.
Г.В. Земсков, НГТУ, 2006