Tree Network Design with Genetic Algorithms-An Investigation in the Locality of thePruefernumber Encoding

When handling tree networks, a number of researchers have tried using the pruefernumberrepresentation for encoding the network, but GAs often degraded or broke down when used onthis encoding. This paper investigates the locality of the pruefernumber, which can be describedas the relatedness of the phenotype (the tree) and the genotype (the pruefernumber) of trees.It is shown that the locality is highly irregular on the entire solution space. We demonstratethat for star and list networks small changes of the pruefernumber lead to small changes in thetree, whereas for all other networks the locality of the pruefernumber is low.[...]