A third approach to the NTP problem was to incorporate the network flow into the representation of the structure. Thus structures and solutions evolve together: instead of using a network flow algorithm to find a flow, the flow is uniquely encoded in the genetic code of the structure, and is allowed to evolve along with it.
With a few modifications we extended the genotype to represent not only the position of the bricks, but also a unique flow for each force into a sink. With this, a structure can evolve along with the flows that represent a solution to the NTP problem.
As seen in the previous sections, a set
of flows, one for
each force, determines the total torque demanded from each joint in the structure
(eq. 2.2). With the embedded solver, the evolutionary algorithm
searches both the space of structure layouts and the space of flows at the same
time. If the torques generated by the distribution of forces specified by the
genotype exceed the joints' capacities, the structure is considered invalid.
Our representation for bricks structures (see section 2.3) is a tree graph whose nodes represent bricks. All descendants of a node are bricks which are physically in contact with the parent. In a structure there may be multiple paths from a brick to the ground, but genetically, there is a unique branch from each brick to the root. The root node is always a brick that rests on the ground, so all paths that follow the tree structure terminate on the ground. The following extensions to the genotype allowed us to evolve a structure along with the solution to the NTP problem:
Loads flow only down from descendants to parents. This defines the positive
or negative sign of
for each joint and force. For the previous
algorithms we had an undirected graph. Now the graph is strictly directed: for
each brick pair a,b either joint j(a,b) exists or j(b,a),
but not both.
Instead of only one root, there can be multiple roots now situated at the grounds of the problem. Each load now has at least one possible path to flow to a sink, although it may or may not violate the joint's constraints.
When two bricks happen to be physically linked, but neither of them is a descendant of the other, the first one2.3 will become an ``adoptive'' parent, so the joint created flows from the lower-order brick to the higher-order.
A weight parameter wj was added to the representation of the joints.
When a joint is created, wj is initialized to 1, but then it may change
by random mutation or by recombination. The flow
for each
force and joint is determined by the joint size (number of knobs) and the flow
weight, as follows:
Let x be a brick in the path of force F. The flow of Finto x must equal its flow out of x, thus
The outgoing flow is uniquely determined by Fx and the proportion
that goes to each parent b of x (either ``adoptive''
or ``original'').
For each brick b that is a parent of x, let
be the size (in knobs) of the joint j(x,b) and w(x,b) the encoded
weight of the joint. Let
and
.
For each joint now we define the proportion of total flow that follows each
outgoing path as:
With this configuration, the flow of a force through brick x is by default proportional to the size of the joint -- stronger joints are asked to support proportionally more weight. But the genotype encodes weights w(x,b) for each joint so the flow of the force can be redistributed.
Two mutation operators were added to allow the structures to explore the space of possible flows: