Во-первых, я инженер, а не компьютерный ученый, поэтому заранее извиняюсь за любое злоупотребление номенклатурой и общее незнание 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