CityBreeder: City Design with Evolutionary Computation

Cities are complex entities which play important roles in the lives of the many people who inhabit them. The process of creating city designs is a complex, time-consuming endeavour, pursued by several di erent groups. Though procedural techniques have been developed to speed up this process, virtually none enable the creation of designs based on multiple existing designs. This thesis presents CityBreeder, a system which enables the rapid, userguided development of city designs based on the blending of multiple existing city designs. Almost no previous research has been conducted regarding this capability.This capability is achieved through the use of Evolutionary Computation, which is used to discover the genetic representation of existing city designs derived from real city data obtained from OpenStreetMap. Once discovered, these cities can be `bred' together, creating new o spring designs. More of this thesis is concerned with the rst portion of this task: the discovery of the genetic representations of real city designs. The combination of these cities is given less attention, but is explored through several demonstrations which show this capability is achieved.More speci cally, CityBreeder employs Genetic Programming on a layered quadtree genotype representation to create phenotype city designs consisting of road layouts comprised of nodes and edges. Additionally, a genotype-to-phenotype expression mechanism, genetic operators and a tness function employing computational geometry techniques are presented and tested, all of which are tailored to the city design context. Experiments and examples are shown which analyze the system's representation and operators using simple, arti cially constructed data, as well as through experiments showing the system functioning with data derived from real cities.