How to generate and encode (for use in GA), random, strict, binary rooted trees with N leaves?

Question

First, I am an engineer, not a computer scientist, so I apologize in advance for any misuse of nomenclature and general ignorance of CS background.

Here is the motivational background for my question: I am contemplating writing a genetic algorithm optimizer to aid in designing a power divider network (also called a beam forming network, or BFN for short). The BFN is intended to distribute power to each of N radiating elements in an array of antennas. The fraction of the total input power to be delivered to each radiating element has been specified. Topologically speaking, a BFN is a strictly binary, rooted tree. Each of the (N-1) interior nodes of the tree represents the input port of an unequal, binary power splitter. The N leaves of the tree are the power divider outputs. Given a particular power divider topology, one is still free to map the power divider outputs to the array inputs in an arbitrary order. There are N! such permutations of the outputs. There are several considerations in choosing the desired ordering: 1) The power ratio for each binary coupler should be within a specified range of values. 2) The ordering should be chosen to simplify the mechanical routing of the transmission lines connecting the power divider.

The number of ouputs N of the BFN may range from, say, 6 to 22.

I have already written a genetic algorithm optimizer that, given a particular BFN topology and desired array input power distribution, will search through the N! permutations of the BFN outputs to generate a design with compliant power ratios and good mechanical routing.

I would now like to generalize my program to automatically generate and search through the space of possible BFN topologies. As I understand it, for N outputs (leaves of the binary tree), there are $C_{N-1}$ different topologies that can be constructed, where $C_N$ is the Catalan number.

I would like to know how to encode an arbitrary tree having N leaves in a way that is consistent with a chromosomal description for use in a genetic algorithm. Also associated with this is the need to generate random instances for filling the initial population, and to implement crossover and mutations operators for this type of chromosome. Any suggestions will be welcome. Please minimize the amount of CS lingo in your reply, since I am not likely to be acquainted with it.

Thanks in advance, Peter

Answer 1

Wow, you're in luck. Eric Lippert just blogged about this not two weeks ago... :)

Answer 2

A tree is a special type of graph. Graphs can be represented as a connection matrix.

A connection matrix answers the question, "is node x connected to node y". There are n rows and columns, corresponding to each node. A 1 on the intersection of row/column x/y denotes connection (this can be used in weighting schemes).

Of course, a matrix can be rewritten as a vector, with the metadata 'length of row'.

I would suggest generating the binary trees in some fashion, e.g., the Lippert method tzaman mentioned, then converting to matrix form and defining the GA operators on the matrix.