About Genetic Algorithms ยท Updated 14 December 2005, by Jason
This section describes how the programs posted to this site work. The descriptions on this page are made in reference to the general description of how genetic algorithms work on the "Algorithms" page.
Setup
All the programs in this investigation work with a population of fifty cities, the fittest of which is displayed to the screen at the start of the next generation.
1. Encode the Problem in a Binary String. Each city is composed of a 50 x 50 grid of land plots. These plots can hold residential buildings, city amenities, or remain empty. The residential buildings can be a row of townhouses, a mini-Tower apartment building, or a high-Tower apartment building. If a plot of land holds an amenity, it could be library, supermarket, restaurant, fire station, police station, or school. Those are the actors.
2. Create a Random Initial State. When a program starts a random distribution of townhouses is applied across each of the 50 cities. This creates the first population of cities. No limits are imposed on the distribution; no target number of residences are used, and no amenities are placed. The randomizer is a sophisticated algorithm tied to the computer's system clock, creating unique distributions and densities each time. The resultant cities are usually a field of evenly distributed residences.
3. Evaluate Fitness. A value for fitness is assigned to each city. Every time the program is begun, the set of rules that the cities are measured against is defined. These rules are applied to every city, each generation. If the rules are "off" the score returned by the rule is zero. If the user turns the score "on" with the buttons on the interface, the rule measures each city and returns a score between zero and one. A score of one represents a perfect solution of the rule, and is almost impossible. In some cases, so many penalties are scored against a city that rules return negative scores.
The rules each have equal weight in the scoring procedure, assuming they're
turned "on." The list of rules are as follows:
I. Have Amenities. If a critical mass of citizens inhabits the city,
create amenities to serve the citizens. A table is provided below to illustrate
the proper number of citizens required to provide patronship per amenity.
The program adds and removes amenity structures as the citizen population
swells and contracts. Amenities are placed and selectively removed randomly,
and are illustrated with a yellow ring to approximate how far their infleunce
is felt.
II. Prefer the Specified Number of Buildings. Cities with the same
number of buildings as the value on the "Number of Buildings"
Slider receive a perfect score. All others receive a score decremented proportionally
to the difference between the two values.
III. Prefer the Specified Number of Citizens. Cities with the same
number of citizens as the value on the "Number of Citizens" Slider
receive a perfect score. All others receive a score decremented proportionally
to the difference between the two values. Each row of townhouses is considered
to have 36 inhabitants, each mini-Tower is assigned 270 inhabitants, and
each high-Tower is assigned 540. These values are adjustable on the interface.
IV. Prefer Residences near Amenities. At the time of scoring, each
residence queries the distance to each amenity on the game board. It remembers
the shortest distance. After each building completes it's query, the city
tallies all "shortest distances" and receives a score based on
the average distance per building.
V. Prefer mini-Towers that have FAR. Each mini-Tower should have three
contiguous neighboring spaces that are empty. There are four scenarios that
satisfy this condition, only one of which is necessary. If the city is
penalized per offending mini-Tower.
VI. Prefer high-Towers that have FAR. Each high-Tower should have five
contiguous neighboring spaces that are empty. There are sixteen scenarios
that satisfy this condition, only one of which is necessary. If the city
is penalized per offending high-Tower.
VII. Prefer Townhouses with Zero Neighbors.
VIII. Prefer Townhouses with One Neighbor.
IX. Prefer Townhouses with Two Neighbors.
X. Prefer Townhouses with Three Neighbors.
XI. Prefer Townhouses with Four Neighbors.
XII. Prefer mini-Towers with Zero Neighbors.
XIII. Prefer mini-Towers with One Neighbor.
XIV. Prefer mini-Towers with Two Neighbors.(Any more is impossible
with the FAR restrictions in Rule V.)
XV. Prefer high-Towers with Zero Neighbors.
XVI. Prefer high-Towers with One Neighbor.
XVII. Prefer high-Towers with Two Neighbors.(Any more is impossible with the FAR restrictions in Rule VI.)
4. Reproduce (& Mutate Children) Each rule returns one score. All the individual city's scores are added and divided by the number of active rules. The result is a single number, the city's final score. The ten cities with the highest scores are selected to breed the next generation. In order to reproduce the next generation, the memory for fifty empty cities is allocated. Like a typewriter, each address's structure, amenity, or blank plot is copied over to each new city individually from on of the parents. At the start of each plot's copy procedure, a dice is rolled, and the parent of that plot is selected based on the dice roll. There is roughly a 30% chance the best scoring city will be selected. Then roughly a 15% chance the second best scoring city will be selected. The chances diminish as the city's score get worse. In this way, each offspring is a unique product of the ten fathers and mothers, whose composition consists of a combination of genes from them. At every plot's copy, there is a chance for mutation. Mutation rate is handled at the interface, and if a mutation occurs, the selected plot may change from a structure to an empty plot, or from one type of residential typology to another. The results of these mutations are scored in the next generation.
5. Next Generation If the new high-scoring city contains a solution that produces an output that is close enough or equal to the desired answer then the problem has been solved, and the cities begin to fall into equilibrium. If this is not the case, then the new generation will go through the same process as their parents did (Steps 3 through 5). This will continue until a solution is reached.