letsthinkabout.us

technology, healthcare, people

Genetics, Evolution of Color, and the French Revolution in F# Xamarin iOS

See the demo live!

   


The code for this post is contained in the Github repository here


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:

  1. You have a problem but don’t know what the exact answer is
  2. You may or may not have a candidate population of solutions 
  3.  Give a computer a set of rules to follow to figure out a solution

The implementation:

  1. 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.)
  2. 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.
  3. Assess the “fitness” of each citizen.  Those that exhibit the most desirable characteristics are the most fit.  Quantify this value for each citizen.
  4. The top 15% of citizens by fitness are left untouched (elitism).  The bottom 85% are mated with each other (combine parts of chromosomes).
  5. Randomly mutate chromosomes of 25% the entire population
  6. Re-sort population based on fitness, and repeat 3-6.
  7. This will converge to a solution.

C# Implementation

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.


F# Implementation

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. 


Other Issues

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 running.

This Genetic 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!

 

Overall Experience

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 upcoming update: 

  1. Visual Studio support since writing F# iOS is only for Xamarin Studio 
  2. 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.
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.

Comments (2) -

  • Dave Thomas

    7/25/2014 10:22:38 PM | Reply

    Hi, nice post, did you know you can drag and drop files in Xamarin studio?

  • Bernard Hsu

    7/26/2014 6:09:57 AM | Reply

    Dave,
    Thanks.  I was thinking more of Visual Studio's Alt+Up/Down for reordering, but didn't realize the solution is the easiest one!

Loading