2010-05-07 2 views
1

Во-первых, я инженер, а не компьютерный ученый, поэтому заранее извиняюсь за любое злоупотребление номенклатурой и общее незнание CS-фона.Как генерировать и кодировать (для использования в GA), случайные, строгие, двоичные корни деревьев с N листьями?

Вот мотивирующий фон для моего вопроса: Я рассматриваю возможность написания оптимизатора генетического алгоритма, чтобы помочь в проектировании сети делителей мощности (также называемой сетью формирования луча или короткой BFN). BFN предназначен для распределения мощности по каждому из N излучающих элементов в массиве антенн. Определена доля полной входной мощности, которая должна быть доставлена ​​на каждый излучающий элемент. Топологически говоря, BFN является строго двоичным, корневым деревом. Каждый из (N-1) внутренних узлов дерева представляет входной порт неравного бинарного разветвителя мощности. N листьев дерева являются выходными делителями мощности. Учитывая определенную топологию делителя мощности, можно по-прежнему свободно отображать выходы делителя мощности на входы массива в произвольном порядке. Нет! такие перестановки выходов. Существует несколько соображений при выборе желаемого порядка: 1) Отношение мощности для каждого бинарного ответвителя должно быть в пределах определенного диапазона значений. 2) Для упрощения механической прокладки линий передачи, соединяющих делитель мощности, необходимо выбрать порядок.

Число Н от Выходы БФПА может находиться в интервале от, скажем, от 6 до 22.

Я уже писал генетический алгоритм оптимизатор, что данный конкретный BFN топологию и желаемый массив распределение мощности на вход, будет искать через N! перестановки выходов BFN для генерации дизайна с соответствующими коэффициентами мощности и хорошей механической маршрутизацией.

Теперь я хотел бы обобщить свою программу, чтобы автоматически генерировать и искать в пространстве возможных топологий BFN. Насколько я понимаю, для N выходов (листьев двоичного дерева) существуют $ C_ {N-1} $ различные топологии, которые могут быть построены, где $ C_N $ - каталонское число.

Я хотел бы знать, как кодировать произвольное дерево, имеющее N листьев, таким образом, чтобы оно соответствовало хромосомному описанию для использования в генетическом алгоритме. Также связано с этим необходимостью генерировать случайные экземпляры для заполнения начальной совокупности, а также для реализации операторов кроссовера и мутаций для этого типа хромосомы. Любые предложения будут приветствоваться. Пожалуйста, уменьшите количество CS lingo в своем ответе, так как я вряд ли буду знаком с ним.

Заранее спасибо, Peter

ответ

0

Дерево - особый тип графика. Графы могут быть представлены как connection matrix.

Матрица соединения отвечает на вопрос, «является узел х подключенный к узлу у». Существует n строк и столбцов, соответствующих каждому узлу. A 1 на пересечении строки/столбца x/y обозначает соединение (это можно использовать в схемах взвешивания).

Конечно, матрица может быть переписана как вектор с метаданными «длина строки».

Я бы предложил генерировать двоичные деревья каким-либо образом, например, упомянутый метод Lippert tzaman, затем преобразованный в матричную форму и определяющий GA-операторы на матрице.

 Смежные вопросы

  • Нет связанных вопросов^_^