Creating People Groups Using Genetic Algorithm

update: check out https://github.com/serdary/GroupPeople for source code.

Genetic Algorithm is great, it is lots of fun to write GA codes.

GA is very useful on optimization problems, but in many cases, you won’t get a huge optimization if you use only GA on a problem (at least that is my experience).
I started adding a Local Search Algorithm (2-opt) with Genetic Algorithm (thanks to AI Prof. Ugur), and the results are better now.

I am not gonna go into detail on Genetic Algorithm here. Cause there are already lots of great resource about Genetic Algorithm. Instead I’ll share some of my experience on GA.

Here, I shared one of my Genetic Algorithm project that is written with Ruby.
It is not a simple program, so you may find this a little complex if you are new to GA.

Group People

Shortly, it finds sub-groups that have similar people from a large group.

Let’s say you have a list of 100 people, and want to create sub groups that have most similar people to each other.

There are various ways to achieve that, and GA is one of them.

So here is the details..

I created a test class (group_people_test.rb) to test the program. As you can in that file, I created random people and interests (all configurable).

With these people, I created an instance of GroupPeople class and let that run and find the sub-groups.

In GroupPeople class (group_people.rb), there are various Constant values that you can play and see the difference of results.

Some of them are: Population size, Generation count, crossover type, selection type and muration rate.

In this class, I created an initial population with some chromosomes include random people.

After this simple step, program generates new generations as much as the specified generation count.

In each generation process, there are lots of things going on, but mainly;

  1. Choose the elitist chromosome (if ELITISM is activated on GroupPeople)
  2. Select 2 parent chromosomes by a selection type to apply crossover. (selection type is specified on GroupPeople)
  3. Apply crossover according to crossover type. (crossover type is specified on GroupPeople)
  4. Apply mutation to new chromosomes according to mutation rate if mutation is activated
  5. Eliminate worst chromosomes if population size is bigger than old population size (this may occur if elitism is active)

For each step, execution may be changed according to Genetic Algorithm parameters that are defined in GroupPeople class.

There are 2 different chromosome selection type, rank_selection and random.

random is just for experimental, it perform *really* not good on big populations.

There are 3 different crossover types, 1point, 2point and uniform

You can try them all and decide what best fits for your project.

Mutation rate is 3% as default, it may be disabled by changing to zero or a different value.

The last step is actually about elitism.

When you choose the best chromosome in a population as elitist, there will be 1 additional chromosome at the end of all chromosomes are crossoverred. So I removed the worst chromosome from population if elitism is active.

Currently, it only performs crossover on people. My initial thought was to apply all actions (crossover, mutation and elitism) on groups as well.

i.e: chromosome1: Group1 (FitnessValue=5) , Group2 (FV=3), Group3 (FV=1), Group4 (FV=2.5), Group5 (FV=2)

Choose Group1 as elitist group, apply crossover and mutation over groups etc.

Maybe I can add that feature in future version to see the differences and possible improvements.

So what is the result?

As you can see there is varying improvement on latest fitness values of chromosomes. But not as much as I thought.

I already mentioned about applying a local search algorithm (2-opt, 3-opt..) increases the effect of algorithm but I did not apply here.

Crossover Type                  Initial Fitness Value         Improved Fitness Value     Generation Count            Group Size          RunningTime (secs)

As always, you can fork the source code on github, and feel free to browse my repo.

Any feedback { :question / :comment / :correction / :etc } is highly appreciated, thanks for reading.

 

 

Tags: , , , , , , , ,

Comments: 3

Leave a reply »

 
  • Merhaba Serdar Bey,
    Lisans bitirme projemi genetik algoritmalar ile ilgili yapıyorum. Bu yüzden sizin programınızı da incelemek istedim. Ruby için tavsiye edebileceğiniz bir derleyici var mı ?

     
     
     
    • ruby interpreted yani yorumlamali bir dil. surdan download edip, irb ile kurcalamaya baslamani tavsiye ederim.

       
  • berna

    benim de yüksek lisans tezim genetik algoritma kullanarak robot kol optimizasyonu sağlamaktı. Ben de Delphi 6 kullanmıştım.

     
     
     
  • Leave a Reply
     
    Your gravatar
    Your Name