Uncategorized

Classical Test Functions for Genetic Algorithms

Recently, I was talking to a rather intelligent chap who was quizzing me on some research I did many years ago. I gave him a simplistic explanation of discrete optimization and genetic algorithms and he fired back a very good question... how do you measure how good a genetic optimization algorithm is? Clearly, you test it on something that you know the global optimum of and see if the algorithm can find it. But there is more to it than that. We also need to use a problem that makes it hard for the algo to get to the "global optima". There are 2 such functions that come to mind that are often used precisely for this purpose...

The Rastrigin Function


where x can range from -5.12 to +5.12.

But it's best visualised as a plot:

As you can see, the external variable A controls the amplitude of the peaks. It should also be clear that this is a non-linear, multimodal function that is not convex. In other words, this function has been custom made to contain many "local minima". A local minimum is a value that is the smallest value in a given area but is not the global minimum. These local minima are the blue-shaded "valleys" in the plot. The global minimum is obviously the smallest value of the function over the entire area. In the case of the Rastrigin function the global minimum is 0 at (0,0) in the two-dimension version of this function.

At any local minimum other than (0,0) the value of Rastrigin's function is greater than 0. In fact, the farther the local minimum is from the origin the larger the value of the function is at that point. The presence of all of these local minima is precisely why this function is often used to test genetic algorithms, because the numerous local minima make it difficult for standard, gradient-based methods to find the global minimum.

Rosenbrock Function

You can read more about it at Wikipedia but again it's best illustrated with a plot:

From Wikipedia, "The global minimum is inside a long, narrow, parabolic shaped flat valley. To find the valley is trivial, however to converge to the global minimum is difficult."

There are others, but these 2 functions are a damn good test for any genetic / evolutionary algo you need to shake out.

Uncategorized

The Brevity of Functional Languages

QuickSort is a well-known, efficient, sort algorithm. In previous posts I've discussed the runtime and space complexity of this algorithm, but there are some other factors that are rather important: brevity and clarity of code. Let's examine this by looking at the implementation of quicksort in C#, Java, C++ and F#.

Here is my version of quick sort in non-generic Java:

   1:      public static void quickSort(int[] input, int start, int finish)
   2:      {
   3:          if (finish-start < 2)
   4:              return;
   5:          
   6:          //pick a pivot
   7:          int pivotIndex = (finish+start)/2;
   8:          
   9:          //partition about the pivot
  10:          int i=start, j=finish;
  11:          while(i<=j)
  12:          {
  13:              while(input[i] < input[pivotIndex])
  14:                  i++;
  15:              
  16:              while(input[j] > input[pivotIndex])
  17:                  j--;
  18:              
  19:              if(i<=j)
  20:              {
  21:                  int temp = input[i];
  22:                  input[i]=input[j];
  23:                  input[j]=temp;
  24:                  i++;
  25:                  j--;
  26:              }
  27:          }
  28:          
  29:          if (start < i-1)
  30:              quickSort(input, start, i-1);
  31:          
  32:          if (i < finish)
  33:              quickSort(input, i, finish);        
  34:      }

And here it is in a generic C# flavour:

   1:          public static void QuickSort<T>(T[] input)
   2:                      where T : IComparable<T>
   3:          {
   4:              QuickSort(input, 0, input.Length - 1);
   5:          }
   6:   
   7:          public static void QuickSort<T>(T[] input, int start, int finish)
   8:              where T:IComparable<T>
   9:          {
  10:              if (finish - start < 2)
  11:                  return;
  12:   
  13:              //pick a pivot
  14:              int pivotIndex = (finish + start) / 2;
  15:   
  16:              //partition about the pivot
  17:              int i = start, j = finish;
  18:              while (i <= j)
  19:              {
  20:                  while (input[i].CompareTo(input[pivotIndex]) < 0)
  21:                      i++;
  22:   
  23:                  while (input[j].CompareTo(input[pivotIndex]) > 0)
  24:                      j--;
  25:   
  26:                  if (i <= j)
  27:                  {
  28:                      T temp = input[i];
  29:                      input[i] = input[j];
  30:                      input[j] = temp;
  31:                      i++;
  32:                      j--;
  33:                  }
  34:              }
  35:   
  36:              if (start < i - 1)
  37:                  QuickSort(input, start, i - 1);
  38:   
  39:              if (i < finish)
  40:                  QuickSort(input, i, finish);
  41:          }

Here's my C++ code :

   1:  void quickSort(int arr[], int left, int right) {
   2:        int i = left, j = right;
   3:        int tmp;
   4:        int pivot = arr[(left + right) / 2];
   5:   
   6:        /* partition */
   7:        while (i <= j) {
   8:              while (arr[i] < pivot)
   9:                    i++;
  10:              while (arr[j] > pivot)
  11:                    j--;
  12:              if (i <= j) {
  13:                    tmp = arr[i];
  14:                    arr[i] = arr[j];
  15:                    arr[j] = tmp;
  16:                    i++;
  17:                    j--;
  18:              }
  19:        };
  20:   
  21:        /* recursion */
  22:        if (left < j)
  23:              quickSort(arr, left, j);
  24:        if (i < right)
  25:              quickSort(arr, i, right);
  26:  }

Here's some Erlang code to do the same:

qsort([]) -> [];
qsort([Pivot|T]) ->
	qsort([X || X <- T, X =< Pivot])
	++ [Pivot] ++
	qsort([X || X <- T, X > Pivot]).

And finally, here's my F# code, that admittedly does it slightly differently in that it selects the first items as the pivot:

#light
open System
 
let rec quickSort ls =
  match ls with
  | [] -> []
  | p::r -> 
     quickSort [for i in r do if (compare i p) <= 0 then yield i] 
     @ [p] 
     @ quickSort [for i in r do if (compare i p) > 0 then yield i]          
 

I know I've mentioned it before on this site, but despite my deep admiration for C++ , Java and C# - they are all great languages - it's painfully clear that, with their advanced list comprehension syntax, functional languages are great at producing succinct code that is very easy to turn into highly parallelized code! With multi-core servers the norm these days these features of functional languages are extremely attractive.

Uncategorized

Google Code Jam 2010: Snapper Chain

Google Code JamCode Jam 2010 started with a qualification round that was harder than previous years. The first problem, Snapper Chain, involves a series of N switches arranged in sequence, that toggle when you snap your fingers if they are receiving power. The problem asks that you indicate if a light plugged into the end of the chain of N switches will be on after K toggles. A brute force evaluation of the state of the light would have a run time ~ O(NK). This isn't feasible since the upper limits on N and K are 30 and 108 respectively. That would take far too long to evaluate. Intuitively you know there must be some sort of pattern so in an effort to get clarity on it it's best to list the states for some toggles. So let's start with N=5 and see what we find...

K State
0 00000
1 10000
2 01000
3 11000
4 00100
5 10100
6 01100
7 11100
8 00010
9 10010
K State
10 01010
11 11010
12 00110
13 10110
14 01110
15 11110
16 00001
17 10001
18 01001
19 11001
K State
20 00101
21 10101
22 01101
23 11101
24 00011
25 10011
26 01011
27 11011
28 00111
29 10111
30 01111
31 11111

Now it becomes clear how things work. The first switch toggles with every snap so it's immediately obvious that after an even number of snaps the light cannot be on. Conversely, if N=1 then the light would be on for all odd values of K. If N=2, then we can see that the light would be on when K=3, 7, 11, 15, 19, 23 27,31. That seems to be a pattern with common increments of 4. If N=3, the light would be on when K=7,15, 23,31 - common increments of 8. And for N=4, the light is on when K=15,31 - an increment of 16. It seems that the increments are powers of two. In other words, for a given N and K we can hypothesize that the light is only on when K satisfies the following formula:

Here c is any non-negative integer. In other words, the light is on after a certain number of snaps and it comes back on after a cycle of 2N more snaps. Since N << K the summation term here is not a major concern. It is in fact the sum of a geometric progression so the summation could be replaced with a simpler term but since N is fairly small (<30) I didn't bother to optimise it further. I did add memoization to remember the sum of N items so we only ever need to calculate the sum of 30 items once. Here's some C# code to solve the problem:

   1:  using System;
   2:  using System.Collections.Generic;
   3:  using System.IO;
   4:   
   5:  namespace GoogleCodeJam2010.Qualificiation.SnapperChain
   6:  {
   7:      class Program
   8:      {
   9:          static void Main()
  10:          {
  11:              const string basePath = @"";
  12:              var infile = new StreamReader(basePath + "large.txt");
  13:              var outfile = new StreamWriter(basePath + "output.txt");
  14:   
  15:              var termSum = new Dictionary<int, ulong>();
  16:              var cycle = new ulong[31];
  17:              ulong sum = 0;
  18:              ulong current = 1;
  19:              for (int i = 0; i < 31; i++)
  20:              {
  21:                  sum = sum + current;
  22:                  termSum[i] = sum;
  23:                  current = current * 2;
  24:                  cycle[i] = current;
  25:              }
  26:              
  27:              int t = Int32.Parse(infile.ReadLine());
  28:              for (int caseNo = 1; caseNo <= t; caseNo++)
  29:              {
  30:                  var data = infile.ReadLine().Split(' ');
  31:                  int n = Int32.Parse(data[0]);
  32:                  ulong k = UInt64.Parse(data[1]);
  33:   
  34:                  string answer = "OFF";
  35:   
  36:                  if ((k - termSum[n-1]) % cycle[n-1] == 0)
  37:                      answer = "ON";
  38:   
  39:                  outfile.WriteLine("Case #{0}: {1}", caseNo, answer);
  40:              }
  41:              infile.Close();
  42:              outfile.Close();
  43:          }
  44:      }
  45:  }

Next »