# From Requirements to Source Code: Evolution of Behavioral Programs
## 4 Method
### Grammar
For example, the strategy b-threads in Listing 3 have different priorities, thus defining an order for applying each strategy. As another example, consider the \"turns\" b-thread to be missing, in which case the program will not be able to generate correct game traces. The second observation relates to the method for selecting the node for performing crossover or mutation. It makes no sense to perform crossover in the middle of a behavior, since it is a single logical unit with a high correlation between its different lines. Similarly, replacing an entire behavior will most likely result in a behavior that does not work well with the other behaviors. Therefore, uninformed, domain-independent genetic operators (e.g., single point crossover) yield poor results. To keep the correlation between the different behaviors, we set the probabilities for applying mutation and crossover operators to be 70% and 5%, respectively. Thus, evolution was driven mostly by exploitation, rather then exploration. For selecting the nodes for the operators, we grouped the nodes into four types, and defined a different probability for selecting each type, depending on the operator. The operators first selected a group type, and then uniformly selected a node in the group. The node types and the probabilities for selecting them are summarized in Table 1. These probabilities were reached through empirical testing. After selecting the node, the mutation operator replaces its sub-tree by growing another sub-tree instead, and the crossover operator replaces the sub-tree with a sub-tree from the second individual. Since the grammar is strongly typed, the crossover operator has additional constraints for selecting the node in the second individual. ### \"Smart\" Test-Driven Genetic Operators

The first genetic operators served as a baseline for future enhancements and for presenting the capabilities of behavioral programming as a tool for evolving source code. In our second experiment, we proposed to evaluate tree nodes according to their contribution to the entire program--whether the contribution was \"good\" or \"bad\". Then, we used these evaluations for developing smart genetic operators, by selecting the nodes according to their evaluation values. Our smart, test-driven mutation and crossover operators are rooted in the field of _fault diagnosis_[26]. Fault diagnosis is the process of determining the type, size, location, and time of detection of a fault. We considered \"bad moves\" the generated program performed as faults in the code. We then applied diagnosis techniques to find \"faulty\" nodes in our program. Additionally, we used the same strategy to find \"good\" components in the code. For each win, win miss, block, and block miss, we noted the last node that was involved, and calculated each component's score accordingly--wins and blocks increased the score, while win misses and block misses decreased the score. For example, if the last event was Owin, then the win counter will be increased for the following nodes: the _Behavior\({}_{i}\)_ node that represents the b-thread that requested the last O event, the _Entity\({}_{i}\)_ node of the behavior (i.e., the context of the b-thread), and the _Query_ node that contains the entity and the behavior. We also added a small bonus for every move the component was involved in, in order to discourage \"timid\" components, which did nothing. The smart operators still selected the node type using the same probabilities, but the node inside the group was selected according to the component score, rather than uniformly, with contrastive formulas for mutation and recombination:

\[\textit{recombination\_score}(\textit{node})=2\cdot wins-2\cdot win_{v}+ \textit{blocks}-\textit{block}_{v}+0.25\cdot\textit{requests}\]

\[\textit{mutation\_score}(\textit{node})=-\textit{recombination\_score}( \textit{node})\]

The reason for this change is that in recombination we provide a higher chance for exchanging good nodes among individuals, and in mutation we provide a higher chance for replacing bad nodes.