next up previous
Next: SMART Operator Fitness Up: Intelligent Recombination Previous: SMART Recombination Primitive Actions

SMART Operator Example

A trivial SMART operator will be explained here as a foothold for the imagination. It is important to understand that the example pictured in Figure 3.2 is smaller than a typical SMART recombination operator by almost two orders of magnitude. In addition this example program is readable and concise in a way that never happens under normal evolution conditions. To begin to understand the SMART recombination example pictured in Figure 3.2, let us start by writing its operation in English pseudo-code:

Figure 3.2: An extremely simplified SMART operator program example.

  1. Set tex2html_wrap_inline985 to a random subset of nodes from tex2html_wrap_inline987 . (Nodes 1 and 2)
  2. Get the number of arcs whose source and destination is tex2html_wrap_inline989 . (Nodes 3,4,5 and 6)
  3. Get the number of nodes in tex2html_wrap_inline991 . (Nodes 7 and 8)
  4. if (result of 3 < result of 2) then STOP, otherwise goto step 1. (Node 9)

The next question is, what does this really do? The answer is:

Keep picking random subset of tex2html_wrap_inline995 for tex2html_wrap_inline997 until more than half the children of nodes in tex2html_wrap_inline999 are in tex2html_wrap_inline1001 . In other words, keeping picking subsets for tex2html_wrap_inline1003 until it passes the 50% intra-connectivity threshold (i.e. the point at which more than half the outgoing arcs from nodes in the set point back to nodes in the set).

The branch-decision function can, in general, be different for each node. For the sake of simplicity, Nodes 1 through 8 all have the same function (see Figure 3.2). This function, for all eight nodes, will always pick tex2html_wrap_inline1005 as the control transfer arc. Neither the number of arcs, where they point, nor the branch-decision function need exhibit this kind of regularity. Now here is a blow-by-blow account of each of the ten nodes and what they actually do:

Node 0: This is the stop node. Generally, when PADO reaches this node, the PADO program's current state is recorded and then, providing the time-threshold has not yet been reached, the program is restated at node 1 (q). In this case, the stop node happens to executes Special Action 13 (SA-13), which signals that the SMART operator has made its choice and need not be restarted.

Node 1: This is the start node. It places a 0 on the program's argument stack.

Node 2: This node executes Special Action 8 (SA-8). This action takes one argument V and sets the SMART recombination operator's tex2html_wrap_inline1009 to a random subset of nodes in tex2html_wrap_inline1011 . In this case V will be 0 since that is what is on top of the argument stack.

Node 3: This node places a 0 on the argument stack.

Node 4: This node places a 1 on the argument stack.

Node 5: This node places a 1 on the argument stack.

Node 6: This node executes SA-11. SA-11 takes three parameters (Z,Y,V) ( tex2html_wrap_inline1017 ) and returns the number of arcs whose source node is in tex2html_wrap_inline1019 (if Y>0) or out of tex2html_wrap_inline1023 (if Y=0) and whose destination node is in tex2html_wrap_inline1027 (if Z>0) or out of tex2html_wrap_inline1031 (if Z=0). Generally, this action can measure the intra- or inter-connectivity of tex2html_wrap_inline1035 or tex2html_wrap_inline1037 . In this case Y and Z are 1 and V is 0, so the effect of this action is to place on the argument stack the number of arcs with source nodes in tex2html_wrap_inline1045 and destination nodes in tex2html_wrap_inline1047 .

Node 7: This node places a 0 on the argument stack.

Node 8: This node executes SA-9. SA-9 takes one parameter (V) and returns the number of nodes in tex2html_wrap_inline1051 . In this case, 0 is on the top of the argument stack, so this action puts the number of nodes in tex2html_wrap_inline1053 onto the argument stack.

Node 9: This node executes the standard PADO action ``less-than'', which takes the top two values off the argument stack (X,Y) and puts a 1 on the argument stack if X is less than Y and a 0 otherwise. In this case, the top two values on the argument stack are the results of the actions from nodes 6 and 8. This node's branch-decision function is ``If RESULT > 0 then tex2html_wrap_inline1063 else tex2html_wrap_inline1065 '' (see Figure 3.2). RESULT is the result of this node's action.

When this SMART operator program finishes, the environment will take tex2html_wrap_inline1067 (the tex2html_wrap_inline1069 nodes to be exchanged) and tex2html_wrap_inline1071 (the tex2html_wrap_inline1073 nodes to be exchanged, left empty in this example) and exchange and recombine them as described in section 3.4.

next up previous
Next: SMART Operator Fitness Up: Intelligent Recombination Previous: SMART Recombination Primitive Actions

Eric Teller
Tue Oct 29 17:04:55 EST 1996