See the demo live!
The code for this post is contained in the Github repository
In my previous post, I examined the evolution of color via
genetic algorithm. Written in the
object-oriented language C#, the simulation was based upon objects and
states. I will elucidate on this concept
later. Today, a similar algorithm is
presented in the completely different, functional paradigm of the language F#.
The basis of the genetic algorithm is:
- You have a problem but don’t know what the exact answer is
- You may or may not have a candidate population of solutions
- Give a computer a set of rules to follow to figure out a solution
- Think about your solution. What characteristics do you want it to have?
(Example, you want to cure Alzheimer’s, so your solution will probably be a
chemical. What makes up a chemical? Elements, proteins, molecular bonds, etc.)
- Create a random population of possible
solutions. Each possible solution is a
citizen. Each citizen has desirable and
undesirable characteristics. Each characteristic
is a chromosome.
- Assess the “fitness” of each citizen. Those that exhibit the most desirable
characteristics are the most fit.
Quantify this value for each citizen.
- The top 15% of citizens by fitness are left
untouched (elitism). The bottom 85% are
mated with each other (combine parts of chromosomes).
- Randomly mutate chromosomes of 25% the entire
- Re-sort population based on fitness, and repeat
- This will converge to a solution.
The object-oriented version of the color genetic algorithm
is based on states. I have 2 objects: a
List<Color> ChildColors and List<Color> ParentColors.
Every Tick() is a new generation where the ChildColors
become the ParentColors and the ParentColors are mated and mutated to create
new ChildColors. Each Tick() rewrites
the values contained within the List<Color>, so these are mutable data
types that hold value for each state they express.
The functional version of this color genetic algorithm
expresses a completely different paradigm.
First, for a language to be considered “functional” it needs:
- Immutable data
- Ability to compose functions
- Functions can be treated as data
- Lazy Evaluation
- Pattern matching
- Read more (Smith, 2012)
F# contains all of these, however is not a “pure” functional
language. Data can be mutable here, as
we are in .NET/mono. Also, as far as I
know, do, for and while looping are generally discouraged in functional languages
in favor of recursion.
Writing an F# app in Xamarin iOS makes it so that the code
cannot be “purely” functional. The fundamental structure of the code was changed to
(partially) fit F#. Here, the Color type
is defined as :
In C#, the fitness of each Citizen within the
List<Color> was not an included property.
Instead, we obtained an overall population fitness of each state. In F#, each Citizen is a tuple: Color *
Fitness where Fitness is an int.
Defining each citizen as a tuple allowed for the Array<Citizen> to
be automatically sorted when initialized as so:
The reason I use the .NET/mono List<Citizen> object is
because I could not get random number generation to work properly if not for
adding objects. I am still scratching my
head on this one. If anything, from a
marketing perspective, this is a triumph of the .NET/mono framework that the
C#-experienced can (relatively) quickly convert.
Here, the equivalent of C#’s Tick() is the function
childGeneration, which produces a new Array<Citizen> on each
iteration. The argument for
childGeneration is a Citizen, which is equivalent to the “ParentColors”
concept. The mating, mutation, fitness
assessment and sorting are all handled at the array initialization of
childGeneration, and that is an extremely powerful ability, expressed in just
~25 lines of code
The control loop for starting the algorithm got a little
hairy. Yes, I used a while loop, and
some things are not ordered well.
Another issue I had was the concept of reference cells. In order to “break” out of the while loop,
the easiest method was to use a boolean reference as thus:
The reason for this was that I could not get a tail-recursive function to work with UIView.Animate or with this.InvokeOnMainThread. The while loop works, but I would like a more functional-paradigm version.
The same concept had to be applied to the changing of
GA_TARGET when the target population fitness was achieved. Setting GA_TARGET to a mutable Color gave odd
random generations that would sometimes mutate while the simulation was
Algorithm and the French Revolution
I largely finished the F# implementation Saturday (7/19/2014)
night. I have been watching it run
intently ever since. The basic
philosophy of genetic algorithm is present, however this is distinctly
different from its C# counterpart. The
one thing that strikes me as odd is the elitism concept.
In F#, the code gives you as exactly as you expect:
The first 15 members of the population, the elite (bourgeoisie),
are unchanged. It seems that a majority
population (proletariat) are attempting to conform to the target. Then randomly upon a threshold which I haven’t
been able to find, a citizen of the proletariat exhibiting the target invades
the bourgeoisie, and that color quickly spreads throughout the top 15. Within 3-4 generations following, the entire
population conforms to the invader’s color.
This concept is technically supposed to occur in the C# version as well,
but does not.
The concept of infiltrating and abolishing the elite sounds eerily
similar to human revolutions of past.
Even more interesting is the method in how the population will conform to
target color only after bourgeoisie is infiltrated. Also familiar is when a new target is
established, the “old elite” stays in power until it is invaded, and displaced
to the lower echelons of the population, where a new order is established. The name
of the app is Evolution++ & Artificial Life, and I would like to believe
that the “artificial life” of the citizens contained here experience the French
Revolution every 30-or so generations. I’ll
let you decide whether it’s a bug or a feature!
In closing, the experience of running Xamarin F# for iOS was pleasant. The tools are not as nearly
as developed as C#, but this is without a doubt production-ready. There are 2 things I would like to see in an
The other was the initial pain of learning a new language that culminates to a rewarding experience after. I still have a long way to go, but I am looking forward to it. F# may have been more deceptive than any other for me since it is .NET and I am in the (incorrect) mindset that "It all compiles to the same IL, so it's the same." No, no it's not.
- Visual Studio support since writing F# iOS is only for
- Built in support of .fsproj file order within the
IDE. I had to manually edit the .fsproj
file so that AppDelegate.fs was the last file, and every time I added a new
file I had to do this. Not sure if there’s
currently another way, but that was my solution. Luckily there aren’t too many files, but for
larger projects this can be a pain.