Morphology GA

Table 2: Parameters used in the successful Morphology GA

Genome Encoding

The genome is encoded as a variable sized array of floating point numbers from 0.0 to 1.0. The array size is limited by the parameter described in Table 2. The maximum array size is small because I am more interested in simple morphologies, and because having a larger maximum array (120), caused the GA to run too slowly on my PC. 

Initially, three floats defined each block with equal probability to any case. The first float defined the type of block (normal, swivel-positive cut, swivel-negative cut or electromagnetic). The second float defined the x location of the block within a given bound and the third float described the y location of the block within a given bound. At the end of the array, if there were not enough elements to define a new block, the last elements were ignored. This encoding failed as the probability of creating a structure with an end-effector, or a moving electromagnetic block, was so low that the entire initial population had a fitness value of 0 and thus the GA was not able to start. 

A second successful encoding that defined each block using two floats was then attempted. This encoding starts with a cursor at the origin. The first float moves the cursor in one of the four cardinal directions, while the second float defines the type of block to try to place. If there is already a block at that position, the new block is ignored and the cursor continues to move as defined by the next element in the array. At the end of the array, if there are not enough elements to define a new block, the last elements are ignored.

Creating Successive Generations

The next generation is created by first taking the top percentage of the population (defined in Table 2) and copying those genomes directly into the new generation without mutation. Then, the rest of the new generation is filled by children created using the dual point crossover technique described in Genetic Algorithims who then undergo mutation. The parents to be used for each mating are chosen randomly with the probability of choosing a particular model to act as a parent being directly proportional to that model’s fitness.

Mutations

Whenever a child is created in a new generation, it undergoes a maximum of three types of mutation: modification, addition and subtraction. Modification and subtraction are both applied to each element in the array, whereas addition is only applied to the entire array. The probabilities of any of these mutations occurring are described in Table 2. Modification replaces a given element with a new random float. Subtraction removes a given element from the array and fills the empty space by pushing elements from the right. Addition appends a random float to the end of the array.

Fitness Function

The fitness function is based on the mathematical model developed by our group and described in section 5. To find the area reachable by the end-effectors, all possible swivel states of the model are iterated through. For each state, all of the locations adjacent only to end-effectors that do not contain another block are added to the area considered “reachable” by the machine. Once the map of all reachable locations is created, the swivel states are iterated through again. Then, for each configuration, we try to place as much of the model as possible in the reachable area by sliding it around. Then, the fitness function is defined as follows:

F(robot) = r/s

r = maximum number of blocks able to fit in the reachable area
s = number of blocks in the model