GA/GP subtree crossover/mutation with all items present?

Question

I have a genetic algorithm/programming problem where I need the best arrange of items in a binary tree. My question is the best way to mutate/cross this binary tree subject to constraints described below.

All items need to be leaves in this binary tree and there are no nodes with only one branch populated. That is, all nodes are attached to two items and/or branches. So for example, this could work where 8, 9, 5, 6, 7 are items and all nodes have two branches:

This would not work because node 10 has only one branch:

My goal is to find the best binary tree arrangement of the items subject to an evaluation function, so all items have to be present.

For mutation, I thought about swapping nodes in this tree, but what would be a good algorithm for this? Clearly, we pick two nodes, and swap their attachments. But it is tricky, because one node cannot be the parent of another, otherwise attachment does not work.

Are there established algorithms for crossover/mutation for this problem setup where a binary tree needs to be mutated assuming all items are leaves and must be present?

Answer 1

You have at least the following 2 options.

Option 1: use local moves

You can use 2 moves: rotations and local swaps. Both can be implemented in $O(1)$ assuming you keep a list of pointers to all non-leaf nodes and each node has 3 pointers: parent, left, and right.

Rotation

1. Pick any non-leaf non-root node B.
2. Let A = *B.parent.

• 3a: If A.left points to B let D=*B.right. Point A.left to D and B.right to A.
• 3b: Otherwise A.right points to B, let D=*B.left. Point A.right to D and B.left to A.

4. Point B.parent to *A.parent, A.parent to B, and D.parent to A.

Local swaps

1. Pick any non-leaf node A.
2. Swap A.left and A.right.

These two operations are both $O(1)$ and are sufficient to transform any tree to any other tree preserving the set of leafs, non-leaf nodes, and the condition that any non-leaf node has exactly 2 children.

Option 2: implement swaps correctly

You can implement a function is_descendant which takes node and ancestor and calls node.parent until you either reach a root of the tree (return False) or reach ancestor (return True; also (optionally) provide which link (left or right) leads from the ancestor to node).

In the swapping move you can handle the case is_descendant(node1, node2) or is_descendant(node2, node1) as you wish. The easiest is to skip the move, but you can also, e.g., swap with the other child of node2 if node2 is an ancestor of node1.