The Genetic Algorithm Framework – Part 3

UPDATE: This article has now been integrated into the GAF documentation. The documentation can be found here.

Genetic Operators

In the previous post I presented an example GA that solved the tricky Binary F6 function. In that example, three Genetic Operators were used. In this article I will look more closely at each of these.

In the previous article I created an initial population of 100 chromosomes (solutions), this represented the first generation of chromosomes. These were then subjected to three genetic operators in turn, once complete, we were left with a new generation. This process was repeated for many generations until an answer to the problem emerged. The order in which each operator is added to the process pipeline determines the order in which each operator is applied. The order was Elite, Crossover, Binary Mutate.

The initial population was created with the following line of code.

var population = new Population(PopulationSize, ChromosomeLength, false, false);

In the Binary F6 example, the population size was 100 and the chromosome length (number of binary digits or ‘Genes’) was 44. The remaining parameters (set to false in the example) can be ignored for now. They relate to noisy environments and Linear Normalisation. Both of these will be discussed in future articles.

Elite

Elitism allows the best solutions to pass through to the next generation without being modified. The Binary F6 example used a value of 5 percent, which, with a population of 100, means that the top 5 chromosomes form part of the next generation. This means that any future generation is at least as good as the current generation. Elitism helps protect good individuals. However, it can be shown that as the percentage of elites is increased, the number of duplicates within the population increases, thereby reducing the performance of the GA. This is normal behaviour for an approach that does not explicitly handle duplicates, and is simply due to the convergence of the algorithm. If you want to experiment with this value I would recommend a value somewhere between 5 and 10 percent as a starting point.

To create an Elite operator and add it to the GA, the following code can be used.

var elite = new Elite(elitismPercentage); 
ga.Operators.Add(elite );

The Elite operator takes a single parameter in its constructor, the percentage. Chromosomes identified as elite are marked as such. This means that operators later in the pipeline such as Mutate or any that you create yourself, know not to modify these chromosomes. The IsElite property returns the elite status of a chromosome.

bool eliteStatus = myChromosome.IsElite;

Crossover

The crossover operator within the GAF can handle singe or double point crossover. The example in the previous post crossed parent chromosomes at a single point. In many cases selecting two points and swapping the center section between parents is more appropriate. Single or double point can be selected via a property as shown below.

var crossover = new Crossover(crossoverProbability, true) 
{ 
    CrossoverType = CrossoverType.SinglePoint;
    ga.Operators.Add(crossover);
}

The crossover probability is simply a value between 0 and 1 that represents the probability of parents crossing over to produce children. A value of 1 means that all selected parents will crossover and create children. A value of 0.85 means that 85% will be crossed over and the remainder of parents will be pass through untouched to the new generation. The second parameter relates to duplicate handling and should be set to ‘true’ for now. When experimenting with crossover probability, a good starting point would be somewhere between 0.65 and 1.

Binary Mutate

This operator scans each bit (gene) of each chromosome and, based on a probability factor, will toggle the bit (from 1 to 0 or from 0 to 1). Typically the mutation probability is very low, for example 0.02, which means that mutation only occurs occasionally. The mutation operator is used to ensure there is some diversity in the population. Diversity will be covered later in the article.

var mutation = new BinaryMutate(mutationProbability, true); 
ga.Operators.Add(mutation);

The constructor of this operator accepts two parameters, the first is the mutation probability, the second relates to duplicate handling and should be set to ‘true’ for now.

The Binary Mutate operator will not mutate any chromosomes marked as ‘elite’. This ensures that the best solutions from the previous generation remain, unmodified, in the following generation.

Memory Operator

This operator maintains a ‘memory’ of solutions and ensures that the best solution in that memory is included in the GA population if it is better than the best in the population. The memory is kept up to date with good solutions during the GA run.

An Example

In an intelligent radio system such as the one described in the research detailed here, a GA is used to search for and track a radio signal that is jumping around the radio spectrum (channel hopping). A GA without the memory operator needs to re-converge on the new frequency for each channel hop of the radio transmitter. Adding the memory operator tries to ensures that if a channel is reused it will be found in memory and will be added to the population causing the GA to instantly converge on the new frequency. If the current channel hasn’t been used before, the GA will try and converge in the normal manner.

If the GA landscape is constantly changing such that the GA has to re-converge on a new solution, the memory operator could be used to improve the performance. As with all of these things experimentation will determine the best usage.

The following code adds the memory operator to the GA, sets the memory capacity to 100 ‘memories’ and specifies that the memory will be updated every 10 generations.

var memory = new Memory(100, 10);
ga.Operators.Add(memory);

Other Operators

The GAF contains other operators to those described above. These will be discussed in future articles.

Diversity

In order that a GA can find suitable solutions to the Binary F6 function it has to search amongst all the possible solutions. In order to do this, some level of diversity amongst the population is required.

In our example diversity was primarily maintained through the use of the Binary Mutate operator. By swapping a binary digit (gene) of the chromosome every now and then, the operator has the potential to change the solutions X and Y values significantly. This allows completely different values to be tested. If these turn out to be good, the chromosome will be selected as a parent and more similar solutions will be created for the next generation. Every time a mutation happens a new part of the search space is searched.

Maintaining a level of diversity is very important for a GAs performance. However, the level of diversity has to be balanced with the need to find suitable solutions through convergence.

Mutation is not the only way to maintain diversity. In later posts I will discuss other replacement and complimentary options.

The Genetic Algorithm Framework – Part 2

UPDATE: This article has now been integrated into the GAF documentation. The documentation can be found here.

Introduction

The GAF is a GA framework that makes it easy to create and modify Genetic Algorithms, It was written from first principles in 2013 in order to fully understand the workings of GA systems. The GAF was part of a project run in conjunction with the De Montfort University, Leicester, UK. The GAF brings all of that GA science and functionality to your project in an extremely easy to use form.

click here for further details.

Creating and Testing a GA

In order to create a simple GA and test it, we need a problem to solve. If we are testing the GA, we really need a problem that we already know the answer to. In line with many researchers, the problem we will solve with this example is the Binary F6 function. Details of the Binary F6 function can be found all over the internet, however, for our purposes all we need to understand is that this is a difficult problem to solve using traditional approaches.

Binary F6

Binary F6 3D Plot

A 3D plot of the Binary F6 function is shown here. It can be seen that there are many peaks and troughs within the overall plot. The mission for this example is to identify the values for X and Y that produces the minimum value for f(x,y). If all of this X,Y,Z stuff doesn’t make sense don’t worry it is not that important really.

I can tell you that a value of 0 for X and 0 for Y gives the minimum value for Z. Therefore, this is a problem that we know the answer to, this will allow us to test our GA.

If you are still puzzled as to why this is hard to solve and you are thinking, that you could just test each value for X and Y between the limits of -100 and +100 (as used in this example), i.e. use a ‘brute force’ approach, consider a situation where the range of X and Y lies somewhere between 0 and 23 billion. The non-linear shape of the curve (i.e. its ‘spikeyness’) means that other non-GA approaches struggle to identify the minimum and tend to get stuck in one of the other troughs (minima). Trust me, Binary F6 was made for GAs.

In order to test the GA I will be using three genetic operators. Elitism, Crossover and Mutation. It is worth noting that many systems often combine crossover and mutation into a single operator. The GAF treats them as two completely independent operators. In the next article I will describe these operators in more detail.

When developing GAs the fitness function is probably the single most important thing to get right. In future articles I will describe how to build fitness functions. However, for now at least, we will use the Binary F6 function as it helps us concentrate on developing the algorithm.

To get started, use the NuGet package manager to add the GAF to a project. In this example I used a Console Project.

PM> Install-Package GAF

The code below shows a Console Application that configures a GA to solve the Binary F6 function.

In example, two delegates are used. The first ‘EvaluateFitness’ is passed into the constructor of the GeneticAlgorithm class. The second, ‘TerminateAlgorithm’ is passed as an argument to the Run method. These delegate methods will be called when needed by the GAF.

In order to show the evolving solution, the example below subscribes to the GenerationComplete event. The code in this function displays X, Y and fitness from the best chromosome in each generation.

The results of the run show the final values for X and Y to be -0.00417 and -0.00069 respectively the final fitness value is 0.999982095862215.

The values for X and Y are very close to zero. Near enough is good enough in GA world. Enjoy!

Addendum:

Thanks to those who noticed that the BinaryF6 function as supplied in the original GAF Library is not actually all that good. The version shown in the Evaluation Function below is better.

This code and the supporting project is available from BitBucket.

using System;
using GAF;
using GAF.Operators;

namespace BinaryF6
{
  internal class Program
  {
    private static void Main(string[] args)
    {
      const double crossoverProbability = 0.85;
      const double mutationProbability = 0.08;
      const int elitismPercentage = 5;

      //create a Population of 100 random chromosomes of length 44
      var population = new Population(100, 44, false, false);

      //create the genetic operators 
      var elite = new Elite(elitismPercentage);

      var crossover = new Crossover(crossoverProbability, true)
      {
        CrossoverType = CrossoverType.SinglePoint
      };

      var mutation = new BinaryMutate(mutationProbability, true);

      //create the GA itself 
      var ga = new GeneticAlgorithm(population, EvaluateFitness);

      //subscribe to the GAs Generation Complete event 
      ga.OnGenerationComplete += ga_OnGenerationComplete;

      //add the operators to the ga process pipeline 
      ga.Operators.Add(elite);
      ga.Operators.Add(crossover);
      ga.Operators.Add(mutation);

      //run the GA 
      ga.Run(TerminateAlgorithm);
    }

    public static double EvaluateFitness(Chromosome chromosome) 
    {
      double fitnessValue = -1;
      if (chromosome != null)
      {
        //this is a range constant that is used to keep the x/y range between -100 and +100
        var rangeConst = 200 / (System.Math.Pow(2, chromosome.Count / 2) - 1);

        //get x and y from the solution
        var x1 = Convert.ToInt32(chromosome.ToBinaryString(0, chromosome.Count / 2), 2);
        var y1 = Convert.ToInt32(chromosome.ToBinaryString(chromosome.Count / 2, chromosome.Count / 2), 2);

        //Adjust range to -100 to +100
        var x = (x1 * rangeConst) - 100;
        var y = (y1 * rangeConst) - 100;

        //using binary F6 for fitness.
        var temp1 = System.Math.Sin(System.Math.Sqrt(x * x + y * y));
        var temp2 = 1 + 0.001 * (x * x + y * y);
        var result = 0.5 + (temp1 * temp1 - 0.5) / (temp2 * temp2);

        fitnessValue = 1 - result;
      }
      else
      {
        //chromosome is null
        throw new ArgumentNullException("chromosome", "The specified Chromosome is null.");
      }

      return fitnessValue;
    }

    public static bool TerminateAlgorithm(Population population, int currentGeneration, long currentEvaluation)
    {
      return currentGeneration > 1000;   
    }

    private static void ga_OnGenerationComplete(object sender, GaEventArgs e)
    {

      //get the best solution 
      var chromosome = e.Population.GetTop(1)[0];

      //decode chromosome

      //get x and y from the solution 
      var x1 = Convert.ToInt32(chromosome.ToBinaryString(0, chromosome.Count/2), 2);
      var y1 = Convert.ToInt32(chromosome.ToBinaryString(chromosome.Count/2, chromosome.Count/2), 2);

      //Adjust range to -100 to +100 
      var rangeConst = 200 / (System.Math.Pow(2, chromosome.Count / 2) - 1);
      var x = (x1 * rangeConst) - 100;
      var y = (y1*rangeConst) - 100;

      //display the X, Y and fitness of the best chromosome in this generation 
      Console.WriteLine("x:{0} y:{1} Fitness{2}", x, y, e.Population.MaximumFitness);
    }
  }
}

The Genetic Algorithm Framework – Part 1

Introduction

Genetic Algorithms (GAs) are the nearest thing a software developer can get to magic. Watching a solution to a problem ‘evolve’, is awesome.

This article is a very simple description of the techniques used when implementing Genetic Algorithm and is intended as a very simple introduction for those not familiar with the science. In future articles I will create GAs in C# using the Genetic Algorithm Framework for .Net (GAF). The GAF is a GA framework that makes it easy to create and modify GAs, It was written from first principles in 2013 in order to fully understand the workings of GA systems. The GAF was part of a project run in conjunction with the De Montfort University, Leicester, UK. The great thing is, as I have done all of the hard work, you don’t have to. The GAF brings all of that GA science and functionality to your project in an extremely easy to use form. However, I will leave details of the GAF for the next article. For now, we will look at a simple example, in order to understand some of the the concepts.

An Example

If you find yourself saying, “I have no idea how to solve this, but I will recognise a good solution when I see one”, then a GA could be the answer. Being able to identify a good solution is paramount to making them work.

Let’s have a look at an example. GAs have been known to improve the design of aeroplane wings. Aeroplane wings have a lot of different parameters, Leading edge shape, width length and another thousand or so that make little sense to me. The great thing is, that with each design of Aeroplane wing we can, within a few milliseconds, model it in software and give it a score that represents how good it is. We can leave all the wind tunnel stuff until much later in the design process. The point here is that we, with the help of modelling software, will recognise a good aeroplane wing when we see one.

So, for our example, we can use a GA to create wings and software to measure how good they are.

How the GA Works

The genetic algorithm is an evolutionary approach to computing, inspired by Darwin’s theory of evolution and biological reproduction, that has the power to determine approximate solutions to optimisation problems. Evolutionary computation has its roots in the 1960s. However, the genetic algorithm that is used as the basis for research today stems from the work of John Holland in the 1980s.

Holland believed that if the features of natural evolution could be incorporated into a computer algorithm, a new way to solve difficult problems could be created. Holland’s work involved manipulating strings of ’1’s and ’0’s which he called Chromosomes.

GA Flow

The basic process adopted by GAs typically involves creating an initial set of random solutions (population) and evaluating them. Following a process of selection, the better solutions are identified (parents) and used to generate new solutions (children). These can be used to replace lesser members of the population. This new population (generation), is re-evaluated and the process continues, reproducing new generations until either a final solution is determined or some other criterion is reached.

GAs borrow their terms from the biological world. For example, GAs use a representation for potential solutions referred to as a chromosome and the operators that are used to create new child solutions such as crossover and mutation are derived from nature.

In their original and most basic form, GAs were used mainly for single objective search and optimisation algorithms. Common to most GAs is the use of a chromosome, genetic operators, a selection mechanism and an evaluation mechanism.

In our case as Aeroplane wing designers, all we have to do is determine the parameters we need in order to build a wing (for this we ask an expert) and bundle them into a binary string, this will be the definition of our chromosome. Therefore, each chromosome will fully describe an aeroplane wing. The GA will do the rest.

Given that we have a definition of a chromosome, and that this describes an aeroplane wing, we can make aeroplane wings until the cows come home. We can, for example, create lots of random chromosomes in the hope that one of them make a useful wing. I know it sounds daft, the truth is this is kind of what we do.

A common approach when using GAs is to start by making a ‘population’ of random chromosomes (wings) perhaps a 100. You may remember earlier that we said we can test each one and score it, or to use the correct terminology, ‘evaluate its fitness’. Whilst it is very unlikely that any of our randomly created wings will actually be good enough to put on an aeroplane, some will be marginally better than others. Here is where the magic happens.

The Magic

Of our population of 100 chromosomes (aeroplane wings) we select some ‘parents’ and use them to make ‘children’. We then test these and add these to our population. Finally we remove all the worst chromosomes leaving our population back at 100. To be honest there are numerous ways to do what has just been described, but for now, we will keep it simple. The upshot is that our new ‘generation’ of aeroplane wings has become stronger. Do this a few hundred times and we end up with some pretty good aeroplane wings.

Making Children

There are many techniques for selecting parents and using them to make children. However, for the purposes of this description we will assume we have a mechanism for selecting two suitable chromosomes as parents. We then use these parents to make two new chromosomes (children). Remember that each chromosome, in this example, defines an aeroplane wing. We are making child wings from parent wings.

Crossover

As we have already stated each wing is defined by a chromosome. A chromosome can take many forms, however, typically a binary string is used. Creating a binary string chromosome can be as simple as converting all of the aeroplane wing parameters into binary numbers and joining them all together. One simple way to create two children from two parents is to pick a random position within the binary string and ‘crossover’ the chromosomes. This gives two new chromosomes, see Fig. 1.

With a population of 100, we would do this 50 times and perhaps keep the best 100 chromosomes the rest we delete or ‘kill’. We do not care if the chromosomes to be deleted are the new children, this is quite normal as many new children will be worse than their parents. We simply keep the best chromosomes, whoever they are. It can be a cruel GA world.

If the ability to create an aeroplane wing from simply carving up a few binary strings seems far fetched then you are in for a treat. As I said before, GAs are the nearest thing to magic that a software developer can get.

Further Reading

If all of this is interesting, stay tuned. In the next article I will start coding a simple GA in C# using the GAF. The GAF makes this a simple task. In addition the structure of the GAF and the way in which it is used, helps in understanding the concepts further.

If you want to dive straight in, the GAF is available as a NuGet package.

PM> Install-Package GAF

Taming the Twitter API in C#

Introduction

This MVC Web application accesses the Twitter API and shows a list of tweets within the standard footer displayed on most pages. This was accomplished by accessing the Twitter API, this brief article describes the approach I took in order that it may help others.

Authentication

Twitter uses OAuth, this is fairly simple to implement in .Net. All that is required is that a few components are in place.

For integrating Twitter into this Web Site, I logged on to the Twitter Developer site (http://dev.twitter.com) and created an Application called “johnnewcombe.net”. I was given an Access Token and its associated secret and a Consumer Key and its associated secret. Four values in total.

At this point it is worth pointing out that for my application I wanted to be able to create Tweets. This means that the Application has to have the appropriate permissions. This is easy to change in the Developer area but there is a GOTCHA!

When you create the Application in the Developer area the Consumer Key is set to ‘Read Only’. This is easy to change to ‘Read Write and Direct Messages’. However, if you do this you have to click the button at the bottom of the page to ‘Recreate my Access Token’. This is fine BUT the page does not always get refreshed, meaning that the permissions are shown as changed but the new tokens are not visible. By refreshing the page manually you will be able to see the new tokens.

After all of this malarky you will end up with four text strings. These are what are needed for the website to access the Twitter API using OAuth.

Whilst I am discussing Gotchas! there is another. Make sure that the clock on your server/dev machine is set to the same as Twitters otherwise you will get the Access Denied 401 message. Actually there is a neat trick you could do here. The returned exception includes the time, Twitters time, so you could catch the exception and retry the request with the time returned in the exception.

The Code

The Twitter class as described later, is extremely easy to use. The example below shows how to get the last five of my Tweets. Note that in this implementation I have included Latitude and Longitude for the Tweet. As these are optional, your implementation could be even simpler.

var twitter = new Twitter(MvcApplication.OauthConsumerKey,
                          MvcApplication.OauthConsumerKeySecret,
                          MvcApplication.OauthAccesToken,
                          MvcApplication.OauthAccessTokenSecret);

//twitter.PostStatusUpdate(status, 54.35,-0.2);
var response = twitter.GetTweets("johnnewcombeuk",5);

We create the class passing in our four keys/secrets and simply call the method we want. Result is a string containing a JSON object. To make this into a C# object all that is required is to convert it using classes in the MVC WebHelpers namespace. For example:

dynamic timeline = System.Web.Helpers.Json.Decode(response);

Naturally any JSON parser could be used.

Using the Dynamic C# object we can get at the properties of the Tweet. For example:

foreach (var tweet in timeline)
            {
                string text = timeLineMention["text"].ToString();
                model.Timeline.Add(text);
            }

In the above case I have created a View Model that has a property called Timeline of type List to hold the text of each tweet this is used in a Partial View that is dragged into the footer. If you look at the bottom of this page, you will see the results. Easy peasy!

The Implementation

Here is the code for the basic Class to use the REST API. It handles the OAuth stuff and each Method returns a JSON object as a string. It is not mean’t to be a complete implementation but will certainly get you going. Two GET Methods and a POST method are shown.

Points to note are that the requestParameters are stored in a Sorted Dictionary as parameters need to be in Alphabetical order for the API requests to be accepted. The other thing to note is that I have extended the SortedDictionary Class to add a ‘ToWebString()’ method. Although a rubbish name, it is a great help in creating a query string, a POST body and OAuth signatures. I am sure you can think of a better name.

Enjoy!

using System;
using System.IO;
using System.Net;
using System.Text;
using System.Diagnostics;
using System.Collections.Generic;
using System.Security.Cryptography;

namespace WebUI.Code
{
    public class Twitter
    {
        public const string OauthVersion = "1.0";
        public const string OauthSignatureMethod = "HMAC-SHA1";

        public Twitter(string consumerKey, string consumerKeySecret, string accessToken, string accessTokenSecret)
        {
            this.ConsumerKey = consumerKey;
            this.ConsumerKeySecret = consumerKeySecret;
            this.AccessToken = accessToken;
            this.AccessTokenSecret = accessTokenSecret;
        }

        public string ConsumerKey { set; get; }
        public string ConsumerKeySecret { set; get; }
        public string AccessToken { set; get; }
        public string AccessTokenSecret { set; get; }

        public string GetMentions(int count)
        {
            string resourceUrl =
                string.Format("http://api.twitter.com/1/statuses/mentions.json");

            var requestParameters = new SortedDictionary();
            requestParameters.Add("count", count.ToString());
            requestParameters.Add("include_entities", "true");

            var response = GetResponse(resourceUrl, Method.GET, requestParameters);

            return response;
        }

        public string GetTweets(string screenName, int count)
        {
            string resourceUrl =
                string.Format("https://api.twitter.com/1.1/statuses/user_timeline.json");

            var requestParameters = new SortedDictionary();
            requestParameters.Add("count", count.ToString());
            requestParameters.Add("screen_name", screenName);

            var response = GetResponse(resourceUrl, Method.GET, requestParameters);

            return response;
        }

        public string PostStatusUpdate(string status, double latitude, double longitude)
        {
            const string resourceUrl = "http://api.twitter.com/1/statuses/update.json";

            var requestParameters = new SortedDictionary();
            requestParameters.Add("status", status);
            requestParameters.Add("lat", latitude.ToString());
            requestParameters.Add("long", longitude.ToString());

            return GetResponse(resourceUrl, Method.POST, requestParameters);
        }

        private string GetResponse(string resourceUrl, Method method, SortedDictionary requestParameters)
        {
            ServicePointManager.Expect100Continue = false;
            WebRequest request = null;
            string resultString = string.Empty;

            if (method == Method.POST)
            {
                var postBody = requestParameters.ToWebString();

                request = (HttpWebRequest) WebRequest.Create(resourceUrl);
                request.Method = method.ToString();
                request.ContentType = "application/x-www-form-urlencoded";

                using (var stream = request.GetRequestStream())
                {
                    byte[] content = Encoding.ASCII.GetBytes(postBody);
                    stream.Write(content, 0, content.Length);
                }
            }
            else if (method == Method.GET)
            {
                request = (HttpWebRequest)WebRequest.Create(resourceUrl + "?" 
                    + requestParameters.ToWebString());
                request.Method = method.ToString();
            }
            else
            {
                //other verbs can be addressed here...
            }

            if (request != null)
            {

                var authHeader = CreateHeader(resourceUrl, method, requestParameters);
                request.Headers.Add("Authorization", authHeader);
                var response = request.GetResponse();

                using (var sd = new StreamReader(response.GetResponseStream()))
                {
                    resultString = sd.ReadToEnd();
                    response.Close();
                }
            }

            return resultString;
        }

        private string CreateOauthNonce()
        {
            return Convert.ToBase64String(new ASCIIEncoding().GetBytes(DateTime.Now.Ticks.ToString()));
        }

        private string CreateHeader(string resourceUrl, Method method,
                                    SortedDictionary requestParameters)
        {
            var oauthNonce = CreateOauthNonce();
                // Convert.ToBase64String(new ASCIIEncoding().GetBytes(DateTime.Now.Ticks.ToString()));
            var oauthTimestamp = CreateOAuthTimestamp();
            var oauthSignature = CreateOauthSignature(resourceUrl, method, oauthNonce, oauthTimestamp, requestParameters);

            //The oAuth signature is then used to generate the Authentication header. 
            const string headerFormat = "OAuth oauth_nonce=\"{0}\", oauth_signature_method=\"{1}\", " +
                                        "oauth_timestamp=\"{2}\", oauth_consumer_key=\"{3}\", " +
                                        "oauth_token=\"{4}\", oauth_signature=\"{5}\", " +
                                        "oauth_version=\"{6}\"";

            var authHeader = string.Format(headerFormat,
                                           Uri.EscapeDataString(oauthNonce),
                                           Uri.EscapeDataString(OauthSignatureMethod),
                                           Uri.EscapeDataString(oauthTimestamp),
                                           Uri.EscapeDataString(ConsumerKey),
                                           Uri.EscapeDataString(AccessToken),
                                           Uri.EscapeDataString(oauthSignature),
                                           Uri.EscapeDataString(OauthVersion)
                );

            return authHeader;
        }

        private string CreateOauthSignature(string resourceUrl, Method method, string oauthNonce, string oauthTimestamp,
                                            SortedDictionary requestParameters)
        {
            //firstly we need to add the standard oauth parameters to the sorted list
            requestParameters.Add("oauth_consumer_key", ConsumerKey);
            requestParameters.Add("oauth_nonce", oauthNonce);
            requestParameters.Add("oauth_signature_method", OauthSignatureMethod);
            requestParameters.Add("oauth_timestamp", oauthTimestamp);
            requestParameters.Add("oauth_token", AccessToken);
            requestParameters.Add("oauth_version", OauthVersion);

            var sigBaseString = requestParameters.ToWebString();

            var signatureBaseString = string.Concat(method.ToString(), "&", Uri.EscapeDataString(resourceUrl), "&",
                                                    Uri.EscapeDataString(sigBaseString.ToString()));

            //Using this base string, we then encrypt the data using a composite of the 
            //secret keys and the HMAC-SHA1 algorithm.
            var compositeKey = string.Concat(Uri.EscapeDataString(ConsumerKeySecret), "&",
                                             Uri.EscapeDataString(AccessTokenSecret));

            string oauthSignature;
            using (var hasher = new HMACSHA1(Encoding.ASCII.GetBytes(compositeKey)))
            {
                oauthSignature = Convert.ToBase64String(
                    hasher.ComputeHash(Encoding.ASCII.GetBytes(signatureBaseString)));
            }

            return oauthSignature;
        }

        private static string CreateOAuthTimestamp()
        {

            var nowUtc = DateTime.UtcNow;
            var timeSpan = nowUtc - new DateTime(1970, 1, 1, 0, 0, 0, 0, DateTimeKind.Utc);
            var timestamp = Convert.ToInt64(timeSpan.TotalSeconds).ToString();

            return timestamp;
        }

    }

    public enum Method
    {
        POST,
        GET
    }

    public static class Extensions
    {
        public static string ToWebString(this SortedDictionary source)
        {
            var body = new StringBuilder();

            foreach (var requestParameter in source)
            {
                body.Append(requestParameter.Key);
                body.Append("=");
                body.Append(Uri.EscapeDataString(requestParameter.Value));
                body.Append("&");
            }
            //remove trailing '&'
            body.Remove(body.Length - 1, 1);

            return body.ToString();
        }
    }

}