[image of digits]

Evolutionary Computation
Enhancing our applications by invoking the most powerful creative force in nature.

Go Directly to the Apps

Wikipedia on Evolutionary Art


You may have to lower your JAVA security settings temporarily for these applets:


Fitness Landscapes

Fitness landscapes are conceptual representations of the fitness of an individual (shown as the z-axis or elevation) varying as a function of two different traits (along the x and y axes). Let's imagine that the x axis is body weight and the y axis is height. For any particular culture there is probably an optimum for each which may define your social attractiveness, your potential to succeed and your health. Taken all together in that context, they define your fitness. This would be a simple landscape with one gently sloping hill. We call this a fitness landscape with one global optimum. Now let's consider a more complex story, one which describes potential fitnesses for a variety of roles in a complex society. Perhaps a small person would be successful as a jocky, a tall one as a basketball player, an obese one as a sumo wrestler. An Eskimo or Innuit in the Arctic Circle would be short and squat; a Masai in Equatorial Africa would be tall and thin. In such a situation we would have a complex landscape with several hills. One may be the highest in which case we would describe it as having one global optimum and several local optima. We can visualize such a fitness surface with two variables, but in reality there are many variables which define the fitness of a person or an agent. We could, perhaps, visualize a fitness solid with three variables. Each variable would be one side of a cube and the fitness could be represented by a spectrum of colors going from low values colored blue to high values colored red. Still it would be difficult to see into this solid. With four or more variables it becomes nearly impossible to craft a convincing visualization. Even though we may conceive of a fitness surface as a static landscape, in reality it may be more like a seascape, always changing with the winds and tides. Our landscapes, or seascapes, are conceptualized in three dimensions for two traits. In the real world many traits may interact to influence fitness. Moreover, fitness changes in coevolutionary situations. We will settle on a two trait visualization since it is easier to understand.


Any individual may be located at one point on that landscape. Genetically close individuals will be located nearby in the x and y directions. Since inheritance produces offspring similar to parents, an individual's children will be spread out to points nearby. Evolution works by "hill-climbing." Offspring higher on the slope of the hill are by definition more fit. As a consequence succeeding generations climb. Since there are high peaks and lower peaks, global optima and local optima, the success of "hill-climbing" depends on the watershed of the topography and on magnitude of the variation between parent and child. Quite often, populations may become stuck on local maxima and thus be unable to climb to the global maximum.

What does the fitness landscape look like for a correct launch code?
What does the fitness landscape look like for a pin tumbler lock?
Brian's Laetoli Walker
Inspired by the discovery of hominid footprints south of Olduvai Gorge, Brian evolved several proof-of-concept walking gaits incorporating 3d hip movement and rotation.

An Evolutionary Sequence Optimizer
in the tradition of Evolutionary Programming

EVOCRYPT optimizes a sequence of cleartext characters paired with a cryptotext alphabet to maximize intelligibility.
EVOTRADES optimizes a sequence of stock market trades to maximize profit.
EVOIMAGE optimizes a sequence of horizontal lines of pixels to reconstruct a scrambled image.
EVOLUTIONARY CONCERT TOUR (ECT) a.k.a. TRAVELING SALESMAN PROBLEM (TSP) optimizes the shortest route through 30 cities.

How the ECT Works
(The other simulations hide much of this detail.)

After you initialize the application with the appropriate data, you can run evolution once SLOWLY to study it in detail, or run it 100 times QUICKLY to study the local optima.

SLOWLY: In "Run...generation(s)" press "FIRST" first (sic). It will create one beginning population of 100 random solutions to the problem, sort them by their fitness and plot them in a histogram. The most fit are those with the shortest bars on the left. The lest fit are those with the tallest bars on the right. They are also colored, from left to right, in a spectrum from cool to hot colors. When you press "Next" the 50 worst individuals are deleted and the 50 best, along with one child for each of them, each child inheriting its parent's traits with some modification, pass into the next generation. There they are again sorted by their fitness and plotted in a histogram. To aid in understanding how efficiently evolution is proceeding in each generation, we introduce bar width and color to the visualization. Those individuals with wide bars were present as parents in the prededing generation; those with narrow bars are children of those parents. Their colors tell you how successful they,or their parents, were in the previous generation. You can run through additional generations by pressing the appropriate buttons. The routes of each 100 members of each generation flash by quickly on the screen. It takes considerable computer time to draw all this to the display. So you may choose to show only the "Best" paths and histograms in the boxes below.

QUICKLY: Since the code for one run of evolution has already been written, why not wrap it in a loop and run evolution 100 times from a random "primordial soup" and see what happens? "100 Runs of ... generations" allows you to do just that. It is important to realize that evolution will not always find the "best" solution. The fitness landscape is complex and evolutionary hill climbing will often lead the population up dead-end local optima. The global optimum is rarely found.

A compelling but unanswered question:
How can we trace back in time, from the best individual at the end of a run of generations,
to its parents, and its parents' parents, in order to discover its lineage, it's ancestral heritage?

Vector Essentials:
random_shuffle(), rotate(), reverse() and sort()

An atonal, chromatic, 12-tone melody generator.

XE6 Vector Essentials - September 26, 2015

The essential vector operations for evolutionary recombination are included in a small application which operates on a sequence of choices made for each of a number of items. These operations are visualiaed as numeric data and simultaneously as colors and musical notes using colorRamp() and midiRamp(). In addition, a sequence of rests or intervals, which are set by the user, modify the tempo of the music. A sample tune and rhythm play when the mouse enters the window.

Evocrypt - A monoalphabetic substitution cipher cryptanalyzer

XE6 EvoCrypt - Adaptation by Trey Bagley - 21 April 2015

Enter a cryptotext (you can input the one that appears by default), open the two dictionaries and begin the run(s). 100 runs of 100 generations will complete in one minute. 100 runs of 1000 generations will complete in 17 minutes. You can help this evolutionary algorithm by locking in specific Cryptext to Cleartext associations. This application sets a fitness for a substitution cipher key alphabet by the number of correct English words it produces. How might that change if the fitnesses were based on n-grams which included blank spaces, sub-words, word pairs and/or grammar?

Lock in the second and third words as "we are."
Lock "H" to "e"
Lock "K" to "w"
Lock "P" to ""a"
Lock "X" to "r"

With these associations locked in, 100 runs of 500 generations will produce interesting results in a short time!

Stock Market Profit Optimizer
Buy and sell one stock each month for each of the four years during the "economic downturn" from 2007 to 2010.
Once you've bought a stock you must sell it and buy another. You cannot buy the same stock twice.
See how you could have profited from the chaos if you knew the future...
"I shoulda, coulda, woulda..."

Evolutionary runs of 100,000 generations (70 min) yielded a max of $847,557.31 dollars. (9/23/2017)
Top score trading sequence.
Evolutionary runs of 20,000 generations (10 min) yielded a max of 510 thousand dollars.
Evolutionary runs of 10,000 generations (4 min) yielded a max of 337 thousand dollars.
Evolutionary runs of 5,000 generations (150 sec) yielded a max of 336 thousand dollars.
Evolutionary runs of 2,000 generations (60 sec) yielded a max of 89 thousand dollars.
Evolutionary runs of 1,000 generations (30 sec) yielded a max of 54 thousand dollars.

XE6 EvoTrades: Speculation Game (revised 22 September 2015)
Module 1, Level 5 - Stock Trading from 2007-2010

This application displys actual monthly stock prices over the four years of the recent financial crisis. Using this information, players begin with $1000 and sell and buy a new stock every month, with the goal of making over $125,000. How much can you make over those four years?

There are 48! (48 * 47 * 46...) possible trading scenarios (sequences), a number, close to 1061. Since the origin of the Universe, only 4.35 * 1017 seconds have passed, which is equivalent to 4.35 * 1029 picoseconds, 4.35 * 1032 femtoseconds, 4.35 * 1035 attoseconds, 4.35 * 1038 zeptoseconds, or 4.35 * 1041 yoctoseconds.

Since the Big Bang, 2.34 * 1062 units of Planck time, the smallest meaningful units of time, have elapsed. This is roughly equivalent to the number of different trading sequences in our game.

Today's fastest computer, China's Tianhe-2, performs at 33.86 * 1015 petaflops, (floating point operations per second). In the age of the universe, it could perform only 1.47 * 1034 floating-point-operations. We would need 1037 of these machines, working continually since the Big Bang, to compute all the possible trading alternatives.

The DARPA Shredder Challenge - A Prize of $50,000




Some observations are detailed below, assuming a single linear shredding which has not been cross-cut.
Cross-shredded pictures or documents will present a much more complex problem.

  1. A shredding which is parallel to the lines of text will be more difficult to reconstruct, since there will be blank edges which will fit perfectly with many other blank edges.
  2. A shredding which is diagonal to the lines of text will provide more clues for proper reassembly.
  3. A shredding which is perpendicular to the lines of text should also provide more clues, unless the font is Courier.
  4. The relationship between the height of the shred and the height of the font will determine the method of attack:
  5. If the shred height is less than the font height, the evolutionary procedure should follow the procedure in the application because the "fitness landscape" will have sufficient slopes for hill-climbing. Evolution will be appropriate. In this case, sub-sequences of lines or shreds which have low dissimilarity should be preserved in the inheritance process.
  6. If the font height is less than the shred height, there will be a different pattern of ink at the top and bottom of the shred and a juxtaposition of two shreds will either have perfect registration or it will not. In other words, the "fitness landscape" will consist of spikes with no slopes for hill-climbing. Evolution will be inappropriate. Every perfect registration between shreds should be preserved. In effect, shreds will grown into larger "registered" shreds until the puzzle is completed.

Our Evolutionary Concert Tour (ECT) application, stripped-down, can find the shortest path among 200 cities. In EvoImage 14, we modified it to reorder a sequence of 200 scrambled lines in a shredded image.

DARPA Shredder Challenge (archive).

Our reconstructions and observations.

A 200 Line Image Descrambler

The 200 horizontal lines in a 200x200 pixel bitmap (.bmp) are first scrambled. The scrambled image is then evolved by creating a first generation of 100 randomly scrambled images. The individuals in this first generation are then individually scored on the basis of how similar the Red, Green and Blue components of each pixel on each line are to the respective R, G and B pixels on the line above and below it. Each individual is then ranked according to its "line-to-line similarity" score, with those rating highest in similarity first in the list of 100. The 50 worst individuals are deleted. The 50 best individuals move to the next generation along with their 50 children, which are similar to their parents but are not exact copies. This is continued for 5000 generations.

XE6 EvoImage 14
24 February 2015

EvoImage 14
29 February 2012

an Evolutionary Image Reconstructor
Adapted from ECT Version 13 stripped.

Open a scrambled picture (it must be a 200x200 .bmp).
The original image will appear at top-left. The line-to-line dis-similarity of the original image will appear at bottom-left. A scrambled line version of the original image will appear at top-right.

Set "100 Runs of ... generations" to 5000 and press "Go."
Every few seconds an evolved de-scrambled image will appear at bottom-right. If you wait a few minutes for 100 de-scrambled images to appear you can scroll through them using the TrackBar at bottom.

The point of this application is NOT to completely restore an image. After all, EvoImage may evolve an arrangement of lines that has greater line-to-line similarity than the original. The point of this application is to show that A SIMPLE FITNESS FUNCTION working with SIMPLE EVOLUTIONARY MECHANISM can do surprisingly well. Moreover, it visually replicates many of the artifacts that arise in biological evolution: Hill-climbing to a local peak on a fitness landscape and missing the global optimum as evidenced by highly fit sequences from a local perspective (see the eyes) but which are reversed with respect to one another at a global perspective.

200x200 bitmap (.bmp) images to unscramble:

Meteoritics set:



Current events set:



200x200 bitmap (.bmp) images to scramble and unscramble:


Version 14 - "Afghan Girl," Thirteen best reconstructions. Top left image is original. Moving to the right is a line-to-line dissimilarity plot
and then the image with its lines scrambled (randomized). The thirteen images which follow are the "best" results of 100 runs of 5000
generations of evolution. Note the similarities of these results to those of biological evolution:

Long sequences of lines are correctly grouped together, but as the sequences grow, they are more likely to be disrupted by recombination.

The "Afghan Girl"

Botacelli's "Cestello"

Slanted text

Posts in perspective

Contrasing shapes in perspective

A swoosh

Complex detail

An easy reconstruction
A Generalized Application for Evolving Sequences of 200 Items
The "cities" metaphor rule tweaks in the Evolutionary Concert Tour application have been stripped away. The process of evolution has been retained.
This should simplify adapting the application to solve other sequencing problems and will handle sequences of 200 events and 100 runs of 5000 generations each.
Since it packs more power, it runs correspondingly more slowly than the "city" versions.

Evolutionary Sequence Optimizer (ESO): Version 13-S
(Stripped and extended to 100 cities in preparation for EvoImage)
13 October 2011
This version is a stripped down from Version 13 with the ability to take any number of cities (but with 100 set as its default). The second window and all the constraints, boundaries and bonuses have been removed. The visualizations of the evolutionary process have been retained for convenience. The visualization of the specific problem, which is assumed not to be the TSP, will need to be rebuilt. The variable names have been changed in order to facilitate adapting the application to other sequence-based evolutionary problems.

Some candidate applications include:

  1. To Do: Cryptanalysis of a monoalphabetic cipher: Each individual solution will be a plaintext-to-ciphertext key. Each individual solution will use this key to attempt a decryption. The decryption will be evaluated on the basis of the number of common English language digraphs, trigraphs and quadragraphs it contains.
  2. Done (see EVOIMAGE above): A deshredder. Reconstructing an image which has been sliced into rows and randomly reassembled. Each individual's row ordering will be evaluated on its similarity to adjacent rows. All the pixels in the row may be evaluated for their Red, Green and Blue similarities, or only one or two columns may be evaluated. It will be interesting to know how many columns need to be sampled to find a valid reconstruction. This procedure is directly relevant for archaeological seriation, biological cladistics and many other multivariable problems.

Evolutionary Concert Tour / Traveling Salesman / Traveling Ferenghi Problem

Given 30 cities (or any other entities in space), there are on the order of 30! different ways of connecting them.
30! is approximately 10^29. Compare this number to the age of the Universe which is 10^17 seconds.
A computer, beginning at the Big-Bang and evaluating 10^12 pathways per second, might just now have finished an exhaustive search for the shortest path.

Wikipedia on the Traveling Salesman problem
Wikipedia on the Vehicle Routing Problem

The Traveling Ferenghi Problem - a 3D Visualization

Evolutionary Concert Tour (ECT) with 3D Anaglyph Enhancement

XE6 ECT 3D Version H - 24 February 2015

Version G - 2 November 2008 - (derived directly from version F)

Converting the application to 3D required no change in the basic evolutionary algorithm. A "z" dimension was added to the the city[] array and the distance computation was changed accordingly. Consequently city values range from 0 to 100 in each of three dimensions. Fogel's cities and Random cities select the "z" dimension randomly.

The "Yours" city placement button allows you to choose the "z" component before you MouseDown on the PaintBox.
Once you click this button, a SetFocus() command returns focus to the "z" TrackBar which allows you to either move the cursor with the wheel or to move the cursor with the mouse. The detents on the wheel have a value of 1 (on my mouse), so it is possible to draw points which progressively sink into or out of the screen by rolling the mouse about 3 detents between mouse. (Three detents times 30 points give a depth difference of 90.)

In a correct anaglyph, when cyan overlays red the result should be rendered white. This could be done by drawing the cyan and red views onto the appropriate layers of a bitmap, using the color channels, but the coding would require substantial modification. Instead, I stayed with the PaintBox which draws red over the top of cyan and cyan over the top of red instead of combining them to yield white. Consequently, in order to avoid "collisions" of cyan and red, I made the dots much smaller. In placing your own cities you should also avoid placing two nearby cities on the same "y" value, since any line drawn between them will be either red or cyan, and not white. For the same reason, the lines connecting the dots have been thinned and the colorRamp() coloring of the lines has been eliminated.

The user may also select the background. It is interesting that with a white background, the rendering appears below the screen while with a black background the rendering is reversed and appears above the screen.

Some initial configurations are below:



xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxect-3d-cone.txtxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ect-3d-cylinder.txtxxxx
Evolutionary Concert Tour / Traveling Salesman Problem
Some additional rules to try:
Evolve for maximum and minimum areas.
Shortest travel distance in a toroidal (wrap-around) world.
You must travel clockwise (or various directions) from quadrant to quadrant.

Red cities must be entered from the NW, Green cities from the SE, or variants for all four city types...
Red cities must be entered from the center, Green cities from the periphery,
or variants for all four city types...

FAST: XE6 Evolutionary Concert Tour (ECT)
Version 20,
26 Sep 2015

For the background, two TImage objects are created:

ImageBackground, which is not visible, is never drawn upon and takes its Picture property from a 500 x 500 bitmap.

ImageToDrawOn, which is visible, its Canvas is drawn upon and to refresh itself takes its Picture property from ImageBackground.

Once ImageToDrawOn is completed, it is sent to the PaintBox in one statement.

Download the zipped file into a newly created folder. Unzip the .zip file into that folder. (By default the browser will want to add a deeper folder. Delete that default folder from the path.)
Open Embarcadero. Open the project file.
Use "View/Units" to bring "Unit1" and "Unit2" into the IDE if necessary.
Use "View/Forms" to bring the Forms into view if necessary.
You should now be able to modify the GUI and the code...

SLOW: Evolutionary Concert Tour (ECT)
Compact Version 15 - 25 February 2013

This version contains added constraints.
The target and radial plots are individually useful for evaluating the results of several different rules. .

Evolutionary Concert Tour - Matt Newcomb - March 2010
Bitmap added to represent terrains with different mobilities
A* ("a-star") maze-solving shortest-path algorithm added
allowing meandering paths

  • Executable
  • Source Code (not portable)
  • Project Files Zipped (not portable)

Import terrain as a bitmap:

Import cities as a text file:

Evolutionary Concert Tour (ECT) - Compact Version 13 - 24 February 2011
This version is the same as Version 12 but with a "left loops" constraint.

Evolutionary Concert Tour (ECT) - Compact Version 12 - 22 February 2011
This version is essentially the same as Version 11 Compact. Some functionality has been improved and constraints have been added for movement Eastward and for Equidistance (not changing the successive path lengths by more than 33).

An example of a variety of experiments to test these fitness functions using a configuration of cities that would be sensitive to the Equidistance constraint is here, followed by the test pattern for cities:

  2. ect-equidistance.txt

Evolutionary Concert Tour (ECT) - Compact Version 11 - 17 February 2011
This version is essentially the same as Version 11. The Classroom #6 lecturer's station, display and classroom projector no longer accommodate the size of the previous version 11. In this version, much of the real estate has been moved to a second Window (Unit2 and Form2). The remaining primary Window has been shrunk-to-fit (hopefully). Let me know if there are any bugs...

Evolutionary Concert Tour (ECT) - Version 11 - 1 November 2010
Sequence penalties added:
Visit 24 satellites from 6 bases with 4 satellites between bases
Visit cities radiating outwards from center (get out of town)
Visit cities clockwise around center (twister)

Other improvements include:

  • Three 30-city patterns are included below to test "4 Red 1 Green" satellite/base rule.
  • TrackBar facilitates examining close examination of each of 100 solutions.
  • TrackBar selection is mapped onto histogram with a red ShapeDot object.
  • Floating point numbers have been formatted to two decimal places.
  • Variable, function and object names as well as captions and labels have been modified to more intuitively reflect the internal operation of the application.


spacer spacer

Notes: Interrupting 100 Runs with fitness changes may produce spurious results.
File formats are specific to each version.

Evolutionary Concert Tour (ECT)
Version 10a (Obstacle problem corrected.)
11 March 2010
Multiple City Types, File Save/Open Cities & Multiple Obstacles.
This version creates 2 city types by default. The user may place cities with of up to 4 types by combining the Right and Left mouse clicks (how to do it) with the pressed and not pressed Shift key. Any distribution of cities may be reassigned 4 types randomly, or geographically by quadrant or by vertical bar. Type colors will NOT show if "ANY" is chosen, since with that option, city type is irrelevant. Otherwise, fitness preference can be assigned for visiting different or same types of cities in sequence, or visiting cities in rank descending order (e.g. 3, 2, 1, 0). Users can add new rule-based fitness functions easily in the calcPathFitness() function beginning at about line 459.
Up to 4 obstacles may be added to define geographically-based fitness allocations. The cities, city types, obstacle locations and obstacle penalties can be saved and opened. This will be convenient for anyone wishing to experiment with different combinations of rule-based and geographically-based fitnesses for given distributions of cities and city types.
Controls have been regrouped in a more logical fashion. Some variable, function and object names have been changed to better represent their functions.


In Engineering, one heuristic for solving large complex problems is to decompose them into smaller simpler parts. One solves those parts separately. Finally one reassembles them back into the larger whole. This does not always work well and we can illustrate that by the following experiments:
Decomposing the ECT cities into "4 Types Quads" by quadrants and selecting "Same" works reasonably well except it fails dramatically with "C-shaped" city distributions.
Decomposing the ECT cities into "4 Types Bars" by vertical bars and selecting "Same" does not work well.
In large complex systems whose interactions and interrelationships are largely unknown in advance; problem solving by "decomposition" is not a reliable approach.

Evolutionary Concert Tour (ECT)
Version I - 9
4 March 2010
Multiple City Types, Multiple Obstacles, Separation of Fitness from Distance
In Engineering, one heuristic for solving large complex problems is to decompose them into smaller simpler parts, solve those parts separately, and recompose them back into the whole. This works well if the structural interrelationships of the large complex problem are known so that it can be separated into meaningfully different modules. It does not work well if the process of decomposition "cuts into" the natural clusters of interrelationships of the original problem. Decomposing the ECT into quadrants works reasonably well for most distributions of cities. It fails with "C-shaped" distributions. Decomposing the ECT into parallel slices does not work well. With the ECT, the "natural" solution is a loop, so a decomposition into quadrants is a better fit. Multiple city types (2 or 4) have been added. Four bonus/penalty border/boundaries have been added. The concepts of "fitness" and "distance" have been logically separated and "distance" is shown as white dots on the "Histogram of Current Population Fitness." Save and Open do NOT save penalty boxes.

Evolutionary Concert Tour (ECT)
Version H - 8
1 October 2009
Variable Parent/Child ratios
Variable MultiRun Generations
The population histogram has also been modified to identify each of the parents (wide bars with a different color for each parent) and each of the children (narrow bars showing the parent's color) for each generation. Note that in early generations, the children are generally more fit than the parents, compared to the later generations in which the parents are generally more fit than the children. As evolution progresses we would probably like to decrease the variability.

Table of results of 500 generations for runs of each Parent/Child ratio.


Evolutionary Concert Tour (ECT) with Political Enhancement
Version G - 29 October 2008 - (derived directly from version F)
Suppose the dots represent households and not cities. Also suppose that you are not only interested in minimizing the physical distance of canvassing all the households, but you have a preference reasons for visiting:
a) Only Republicans first and then Democrats (so you don't have to change your interviewing style), or
b) Alternating between Republicans and Democrats (to stay attuned to contrasts).
The application will now allow you to place a varying "penalty" on deviating from your preference.
The penalty is added to the length of your circuit.
If you have no preference, you may select "Any" which is chosen by default.

To do:
The standardized configurations below confirm that the different fitness criteria do work. Create some standard configurations to run in "Any," "Same" and "Different" mode, with and without physical border penalties. Play with the penalty value (it is probably set too high). Vary it to discover the "tipping points" with all other parameters set the same. The code may now be easily modified to expand the "city" types to three or more and to develop various complex valuation schemes for different circuits through the cities.

Thanks to Kathleen Schaefer and "IT" Itohan Aghayere for their efforts in thinking their ways down this road to enhancing the functionality of the application.

Some standardized configurations are below:

Party affiliations are RED for Republican and BLUE for Democrat.
When you select YOURS cities, left-click places RED and right-click places BLUE.
The party affiliation of FOGEL'S and RANDOM cities are chose randomly
FileSave and FileOpen have been modified to record the party affiliation of cities (or households),
thus FileSave and FileOpen are NOT compatible with previous versions.

Select for ANY party. xxxxxxxxxxxxxxxxxx
xxxxxxSelect for SAME party. xxxxxxxxxxxxxxxxxxxxxxxxSelect for DIFFERENT party.

Evolutionary Concert Tour (ECT) May 2007 - Version F
For from 4 to 30 Cities w/Borders
Any number of cities may be introduced, from 4 to 30. The MouseWheel has been introduced and the sensitivity of the "100 Runs" plots to MouseMove has been changed. Many improvements could still be made. The file open and file save functions expect the first data element to be the number of cities, so the old configurations will need to be edited to work with the new version of the program.

Some standardized configurations are below:

5arm-nebula.txt x x 6arm-nebula.txt x x cross15.txt xx difficult30.txt xx subtle20.txt

The borders of the green region at the bottom confer bonus points as a multiple of the path length that crosses them. Consequently, cities in the green region connect to the most distant cities. See the differences between the bonus, no-border and penalty examples below:

Evolutionary Concert Tour (ECT) 2007 - February

w/ Bonus or Penalties for Crossing Borders
You may introduce a rectangular area. Crossing its border will either confer a bonus or extract a penalty as a multiple of the length of the path segment that crosses it. Click on "Border" and then MouseDown, Drag and MouseUp to create the bounded region. Use the TrackBar to set the bonus or penalty multiplier. All possible path segment distances (including penalties) are recalculated every time you selecting the 30 cities or change the bonus/penalty.

Some standardized configurations are below:

spiral.txt x x circle.txt x x squares.txt xx clusters.txt xx dispersed.txt xx d-configuration.txt xx targets.txt
x x xxxxxxxxx x
Bonus xxxxxxxxxxxxxxx No Borderxxxxxxxxxxxxxx Penaltyxxxxxxxxxxxxxxxxxxxxxxxx Bonusxxxxxxxxxxxxxxx No Borderxxxxxxxxxxxxxx Penalty

Some EXPERIMENTS using "squares.txt" with and without the
border-crossing penalty are shown below:

2006 - December
Evolutionary Concert Tour (ECT)

with Penalties for Crossing Borders
You may introduce a rectangular area as an obstacle. Crossing its border will extract a toll (penalty) equal to a multiple of the length of the path segment that crosses it. Click on "Border" and then MouseDown, Drag and MouseUp to create the bounded region. Use the TrackBar to set the penalty multiplier (2 or higher). All possible path segment distances (including penalties) are calculated on selecting the 30 cities or on changing the penalty.

x x x x x
Rank 0 xxxxxxxxxxxxxxxRank 11 xxxxxxxxxxxxxxxRank 19 xxxxxxxxxxxxxxxxxRank 37 xxxxxxxxxxxxxxxRank 42 xxxxxxxxxxxxxxxxxRank 57
Rankings of evolved solutions with a 10-FOLD TOLL extracted on crossing the border.
x x x x x
Rank 0 xxxxxxxxxxxxxxxxxxRank 14 xxxxxxxxxxxxxxxxxRank 35 xxxxxxxxxxxxxxxRank 61 xxxxxxxxxxxxxxxxxRank 81 xxxxxxxxxxxxxxRank 93
Rankings of evolved solutions with NO TOLL extracted on crossing the border.

No obstacle (left) and penalty (right).

2006 - November
Evolutionary Concert Tour (ECT)

File Save/Open and Obstacles
In addition to the functionality of the previous version, this version will open and save the user's configuration of 30 cities.

It will also introduce a vertical obstacle which extracts a penalty of up to 20 times the distance for the path legs which cross it. You may consider this to be a toll extracted for crossing a bridge over a river or a customs tariff charged for moving goods across a border.

Notice that the penalty is multiplied by the length of the leg that crosses the line. Consequently, not only must evolution minimize the number of crossings, but it must minimize the lengths of the legs which cross as well.

2006 - Evolutionary Concert Tour (ECT)
Multiple Runs
In addition to the functionality of the previous version, this version will collect and display statistics on 100 runs of 1000 generations each (10,000,000 individuals). In addition, the path and distance of the best solution of each run is stored . As each run is completed, a black dot is displayed showing its best solution distance along the X axis. Consecutive runs are plotted below the previous ones along the Y axis. The maximum and minimum distances are calculated and the scatter plot in black is then rescaled and replotted as a histogram in black, the number of occurrences at each distance shown against the blue scale as the absolute number out of one hundred, or percentage. By mousing over the histogram, you can recall the pathway that gave that distance as well as the rank of that distance. From the difference in successive ranks you can calculate the height of each histogram spike.

This version will also select for the longest (as opposed to the shortest) path, which we might call "The New York Taxi Driver's Problem."

2006 - Evolutionary Concert Tour (ECT)
Showing the Best of Each Generation.
A new plot has been added which shows the course of evolution - the best individual's path distance for each generation. Additionally, the path of the best individual's distance is shown for each generation, which provides a visual indication of the "progress" of evolution.
The application has been changes so that it only shows information relevant to Fogel's cities when Fogel's cities are chosen.


Some other progressions towards local maxima.

2005 - Evolutionary Concert Tour (ECT)
The old "Traveling Salesman's Problem" (TSP) recast in contemporary terms. How can one travel to all cities and return home covering the least distance? There are 1,409,286,144 (30!) possible paths, or loops, through the 30 cities. However, many are the same length: For every forward loop there is a reversed loop and for every loop there are 30 possible starting points. Consequently we must divide the total by 2x30 to get the number of different paths, which is 23,488,102. An exhaustive search of all possible paths is impractical, but we can use Darwinian/Wallacian evolution through natural selection to find the optimal path.

The user may select David Fogel's published arrangement of 30 cities, a random one or select her own. A first generation of one hundred agents are created, each representing one random path. In subsequent generations, the best half of the population serves as parents, replacing the worst half with variant offspring by asexual reproduction. The vector operations of shuffle, rotate and reverse are used to resequence the paths. For each agent, the best path is shown as well as the lengths of the best, average and worst paths. These visualizations may be switched off to speed the simulation. Thumbnails show some near optimal solutions to a spiral arrangement of cities.


Daisuke Imai's EVOcuation with Obstacles
During emergencies under panic conditions, spaces can be evacuated with maximal speed and minimal injury by introducing obstacles near the exit. This highly original and sophisticated project simulates evacuation with no, one and three obstacles, calculating both speed and injury. Additionally, both genetic algorithms and random search may be used to optimize obstacle configurations. Individual agent perceptions and behaviors are complex.

Source Code Unit1
Source Code Unit2

After 66 generations.

Saeid Atoofi's Language Evolution
(on the assimilation of language elements)

2006 Evolutionary Iterated Prisoners Dilemma
An evolutionary enhanced version of the classic game.
Evolution is achieved by randomly changing the strategy of the worst player every 100 games.
Devolution is achieved by randomly changing the strategy of the best player every 100 games.
Evolution changes the screen to a pale green.
Devolution changes the screen to a pale pink.
A high not is played when an evolutionary change is made. A lower note is played when a devolutionary change is made.

Garret's Evolutionary Iterated Prisoners Dilemma
An evolutionary enhanced version of the classic game.

2005 - Adam Skory's Evolutune
Evolutune is a program to evolve little musical loops. Each loop consists of four measures of beeps and boops. These loops are created based on sets of parameters, or genotypes, that define their characteristics. By selecting those loops that sound best, and reproducing them with slight mutations in their genotypes, a user can direct the evolution of the loops into being "more fit" for their environment (i.e. your ear).

The green triangle button is PLAY.
The black square button is STOP.
The red RECORD button is not implemented.

Rearranging a 1-D ARRAY using a VECTOR
This program shows how to use a 1-D VECTOR and the mutation and sorting algorithms in the Standard Template Library in order to manipulate a 1-D ARRAY directly. This is the first step in manipulating a 2-D ARRAY.

Rearranging a 2-D ARRAY using a VECTOR
This program shows how to use a 1-D VECTOR and the mutation and sorting algorithms in the Standard Template Library in order to manipulate the indices to a 2-D ARRAY. The result is that the ARRAY can be subjected to the same mutations as the VECTOR.

Rearranging a TPoint ARRAY using a VECTOR
This program shows how to use a VECTOR of TPoint ARRAY structure and the mutation and sorting algorithms in the Standard Template Library in order to manipulate its contents. The VECTOR may than be copied back into the TPoint ARRAY.

Tim's A* Maze Solving Algorithm
Recompiled with Embarcadero, 25 February 2013.
The "A-Star" search algorithm finds the shortest path between source and target cells (red) in a maze. The path is traced in cyan, if a path is possible at all.

Tim's A* Maze with Bitmap
Recompiled with Embarcadero, 25 February 2013.
Instead of creating random mazes, this version allows you to import a 61 by 61 cell bitmap image drawn in black-and-white. Two such images are included. Pictorial images may be reduced in PhotoShop for different effects.

Two bitmaps: