Make everything as simple as possible, but not simpler. -Albert Einstein 

formats

Let JGAP select your next movie!

Published on June 21, 2012 by in JGAP

Summary: In this post, we use JGAP (pronounced “jay-gap”), an open source Genetic Algorithm (GA) framework, to select an optimal set of movies based on our interests. A Genetic algorithm (GA) is a type of search algorithm that simulates the process of natural evolution. This type of algorithm is used to select an optimal solution among potentially thousands (or more) solutions for a problem domain.

Prerequisites: If you would like to obtain this article’s complete sample, it may be obtained from our GitHub repository. All samples are Maven based java projects.

Let’s Get Started! Before we can begin, let’s examine the high level steps JGAP performs:

    1. Choose the initial population of individuals.
    2. Evaluate the fitness of each individual in that population
    3. Repeat the following until some termination condition (time limit, sufficient fitness,etc.):
      a. Select the best-fit individuals for reproduction.
      b. Create new individuals through crossover and mutation
      c. Evaluate the individual fitness of new individual.
      d. Remove least-fit individuals from population.

In order to use JGAP, there are five basic tasks you should perform. These steps will be covered in the subsequent sections

Step1: Define Chromosome   The Chromosome is the central abstraction used within the JGAP framework, as it represents a potential solution. A Chromosome is divided into a multiple genes. Gene objects in JGAP represent the distinct parts of a solution. In our sample, we want the optimal selection of 3 movies that fulfill our viewing interest. A potential solution (Chromosome) in this example consists of a list of indexes where each index represents a Movie in the movie array. In order to represent the index, we use an IntegerGene. Our Movie object contains the following properties: name, genre, imdb rating, and year. These properties will help us implement a suitable fitness function in our next step.

Listing 1: Movie.java

package techbysample.jgap3.sample1.model;

import java.util.List;

/**
 *
 * @author TechBySample.com
 *
 */

public class Movie {

	private String name;
	private List genre;
	private String rating;

	private double imdbRating;
	private String year;

	public String getYear() {
		return year;
	}
	public void setYear(String year) {
		this.year = year;
	}

	public double getImdbRating() {
		return imdbRating;
	}
	public void setImdbRating(double imdbRating) {
		this.imdbRating = imdbRating;
	}

	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public List getGenre() {
		return genre;
	}
	public void setGenre(List genre) {
		this.genre = genre;
	}
	public String getRating() {
		return rating;
	}
	public void setRating(String rating) {
		this.rating = rating;
	}
	@Override
	public String toString() {
		return "Movie [name=" + name + ", genre=" + genre + ", rating="
				+ rating + ", imdbRating=" + imdbRating + ", year=" + year
				+ "]";
	}

}

Step 2: Define a Fitness function      JGAP is intelligent enough to perform a majority of the process of natural selection. However, the framework has no knowledge of the problem domain. For this reason, we need to define a fitness function. We will need to extend JGAP’s FitnessFunction class. This class has only one method, evaluate(Chromosome). This method is responsible for calculating a score for a potential Chromosome (group of Movie genes).  In GA terminology, this score is called a ‘fitness score’ and is used to determine how optimal the solution is relative to other potential solutions in the population.

Reference Listing 2 : MovieFitnessFunction.java for the following:

In line 24, a list of available movie rentals, preferred genres (ie: Action, Romance, Comedy) is passed in to constructor.

In line 31 , the evaluate(Chromosome) method determines a Chromosome’s individual fitness value. In our sample, the best fit solution (chromosome) contains movies that have the highest IMDB movie rating and match the preferred genres.

In lines 43-46, to eliminate potential solutions that contain duplicate movies, we return a fitness value of 0.

In lines 52-56, to eliminate potential solutions that do not  match any of our preferred genres, we return a fitness value of 0.

Listing 2: MovieFitnessFunction.java

package techbysample.jgap3.sample1.fitness;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import org.jgap.FitnessFunction;
import org.jgap.IChromosome;
import org.jgap.impl.IntegerGene;

import techbysample.jgap3.sample1.model.Movie;

/**
 *
 * @author TechBySample.com
 *
 */

public class MovieFitnessFunction extends FitnessFunction{

	List movies = new ArrayList();
	List genres = new ArrayList();

	public MovieFitnessFunction(List movies, List genres)
	{
		this.movies= movies;
		this.genres= genres;
	}

	@Override
	protected double evaluate(IChromosome chromosome) {
		double score=0;
        double imdbScore =0;

        List dups = new ArrayList();
        int badSolution = 1;

		for (int i = 0; i < chromosome.size(); i++) {

			IntegerGene agene =  (IntegerGene)chromosome.getGene(i);
			int index = (Integer) chromosome.getGene(i).getAllele();

		    if (dups.contains(index))
		     {
		      badSolution = 0;
		     }
		    else{
		      dups.add(index);
		    }

			Movie movie = movies.get(index);
			double genreScore = getGenreScore(movie);
			if (genreScore==0)
			{
			 badSolution = 0;
			}
			score = (score + movie.getImdbRating()) + (genreScore);

			}
		return (score*badSolution) ;
	}

	private double getGenreScore(Movie movie)
	{
		double genreScore= 0;
		Iterator it = this.genres.iterator();

		while (it.hasNext())
		{
			String genre = (String) it.next();
			if (movie.getGenre().contains(genre))
			{
			  genreScore = genreScore + 1;
			}
		}
	  return genreScore;
	}

}

Step 3: Create a Configuration Object    JGAP‘s architecture is extremely flexible.  As a result, JGAP supports injecting custom genetic operators, random number generators, natural selectors by implementing a Configuration object. The Configuration object must be created with all of the appropriate settings prior to use. For the purpose of our sample, we will use JGAP’s DefaultConfiguration object. This will be more than sufficient to accommodate our demonstration. In order to properly initialize the Configuration object we will need to set the appropriate fitness function, define a Chromosome, and specify the number of chromosomes we want to have in our population.

Reference Listing 3 : TestMovieFitness.java for the following:

In line 60, we use the DefaultConfiguration object with the JGAP engine.

In line 68, we specify our configuration to have a population 1000 Chromosomes.  As a result, JGAP will maintain and evaluate 1000 potential solutions.

In lines 71-73, we instruct JGAP to use our MovieFitnessFunction object

In lines 75-84, we define our Chromosome to contain 3 IntegerGenes (movies). As a reminder, the value of the IntegerGenes represents an index into the list of available movies.

Listing 3: TestMovieFitness.java

package techbysample.jgap3.sample1;

import java.util.ArrayList;

import java.util.List;
import java.util.Random;
import java.util.StringTokenizer;

import junit.framework.Assert;

import org.jgap.Chromosome;
import org.jgap.Configuration;
import org.jgap.DefaultFitnessEvaluator;
import org.jgap.Gene;
import org.jgap.Genotype;
import org.jgap.IChromosome;
import org.jgap.impl.DefaultConfiguration;
import org.jgap.impl.IntegerGene;
import org.jgap.impl.SwappingMutationOperator;
import org.junit.Before;
import org.junit.Test;

import techbysample.jgap3.sample1.fitness.MovieFitnessFunction;
import techbysample.jgap3.sample1.model.Movie;

/**
 *
 * @author TechBySample.com
 *
 */

public class TestMovieFitness {

    private Configuration conf;
    private SwappingMutationOperator swapper;
    private MovieFitnessFunction fitnessFunction=null;
    private List movies = new ArrayList();
    private List genres = new ArrayList();

    private  static final int MAX_ALLOWED_EVOLUTIONS = 1500;
    private Chromosome movieChromosome = null;

    @Before
    public void initialize() throws Exception
    {

     String sGenres = System.getProperty("GENRES");
     Assert.assertNotNull("GENRES System property not set. Please provide GENRES information.", sGenres );

      StringTokenizer st = new StringTokenizer(sGenres, ",");

       while (st.hasMoreElements())
        {
           String genre = st.nextToken();
           genres.add(genre);
        }

       movies = this.loadMovies();

       conf = new DefaultConfiguration();
       Configuration.resetProperty(Configuration.PROPERTY_FITEVAL_INST);
       conf.setFitnessEvaluator(new DefaultFitnessEvaluator());
       conf.getGeneticOperators().clear();

       swapper = new SwappingMutationOperator(conf);
       conf.addGeneticOperator(swapper);
       conf.setPreservFittestIndividual(true);
       conf.setPopulationSize(1000);
       conf.setKeepPopulationSizeConstant(false);

       fitnessFunction = new MovieFitnessFunction(movies,genres);

       conf.setFitnessFunction( fitnessFunction );

       Gene[] movieGenes = new Gene[ 3 ];

       movieGenes[0] = new IntegerGene(conf, 0, movies.size()-1 );
       movieGenes[1] = new IntegerGene(conf, 0, movies.size()-1);
       movieGenes[2] = new IntegerGene(conf, 0, movies.size()-1);

       movieChromosome = new Chromosome(conf, movieGenes );
       movieGenes[0].setAllele(new Integer(0));
       movieGenes[1].setAllele(new Integer(1));
       movieGenes[2].setAllele(new Integer(3));

       conf.setSampleChromosome( movieChromosome );

    }

    private List loadMovies()
    {
         List list = new ArrayList();

          Movie movie1 = new Movie();
          movie1.setName("The Matrix");
          movie1.setImdbRating(7);
          List genre1 = new ArrayList();
          genre1.add("SciFi");
          genre1.add("Action");
          movie1.setGenre(genre1);
          movie1.setRating("PG-13");
          movie1.setYear("1999");

          Movie movie2 = new Movie();
          movie2.setName("The Dark Knight");
          movie2.setImdbRating(9.6);
          List genre2 = new ArrayList();
          genre2.add("Action");
          movie2.setGenre(genre2);
          movie2.setRating("PG-13");
          movie2.setYear("2008");

          Movie movie3 = new Movie();
          movie3.setName("The Avengers");
          movie3.setImdbRating(9.6);
          movie3.setYear("2012");

          List genre3 = new ArrayList();
          genre3.add("Action");
          movie3.setGenre(genre3);
          movie3.setRating("PG-13");

          Movie movie4 = new Movie();
          movie4.setName("The Hangover");
          movie4.setImdbRating(7.6);
          List genre4 = new ArrayList();
          genre4.add("Comedy");
          movie4.setGenre(genre4);
          movie4.setRating("R");
          movie4.setYear("2009");

          Movie movie5 = new Movie();
          movie5.setName("The Hangover 2");
          movie5.setImdbRating(9.6);
          List genre5 = new ArrayList();
          genre5.add("Comedy");
          movie5.setGenre(genre5);
          movie5.setRating("R");
          movie5.setYear("2012");

          Movie movie6 = new Movie();
          movie6.setName("This Means War");
          movie6.setImdbRating(6.4);
          List genre6 = new ArrayList();
          genre6.add("Comedy");
          genre6.add("Action");
          genre6.add("Romance");
          movie6.setGenre(genre6);
          movie6.setRating("PG-13");
          movie6.setYear("2012");

          Movie movie7 = new Movie();
          movie7.setName("Hitch");
          movie7.setImdbRating(10);
          List genre7 = new ArrayList();
          genre7.add("Comedy");
          genre7.add("Romance");
          movie7.setGenre(genre7);
          movie7.setRating("PG-13");
          movie7.setYear("2005");

          Movie movie8 = new Movie();
          movie8.setName("21 Jump Street");
          movie8.setImdbRating(6.7);
          List genre8 = new ArrayList();
          genre8.add("Comedy");
          genre8.add("Action");
          movie8.setGenre(genre8);
          movie8.setRating("R");
          movie8.setYear("2012");

          Movie movie9 = new Movie();
          movie9.setName("Killers");
          movie9.setImdbRating(5.1);
          List genre9 = new ArrayList();
          genre9.add("Comedy");
          genre9.add("Action");
          genre9.add("Romance");
          movie9.setGenre(genre9);
          movie9.setRating("PG-13");
          movie9.setYear("2010");

          Movie movie10 = new Movie();
          movie10.setName("What to Expect When You're Expecting");
          movie10.setImdbRating(5.1);
          List genre10 = new ArrayList();
          genre10.add("Comedy");
          genre10.add("Romance");
          movie10.setGenre(genre10);
          movie10.setRating("PG-13");
          movie10.setYear("2012");

          Movie movie11 = new Movie();
          movie11.setName("Anchorman");
          movie11.setImdbRating(6.9);
          List genre11 = new ArrayList();
          genre11.add("Comedy");
          movie11.setGenre(genre11);
          movie11.setRating("R");
          movie11.setYear("2009");

          Movie movie12 = new Movie();
          movie12.setName("Safe House");
          movie12.setImdbRating(8);
          List genre12 = new ArrayList();
          genre12.add("Action");
          movie12.setGenre(genre12);
          movie12.setRating("R");
          movie12.setYear("2012");

          Movie movie13 = new Movie();
          movie13.setName("Bridesmaids");
          movie13.setImdbRating(6.9);
          List genre13 = new ArrayList();
          genre13.add("Comedy");
          genre13.add("Romance");
          movie13.setGenre(genre13);
          movie13.setRating("R");
          movie13.setYear("2011");

          Movie movie14 = new Movie();
          movie14.setName("American Reunion");
          movie14.setImdbRating(7.4);
          List genre14 = new ArrayList();
          genre14.add("Comedy");
          movie14.setGenre(genre14);
          movie14.setRating("R");
          movie14.setYear("2012");

          Movie movie15 = new Movie();
          movie15.setName("Love Happens");
          movie15.setImdbRating(5.5);
          List genre15 = new ArrayList();
          genre15.add("Romance");
          movie15.setGenre(genre15);
          movie15.setRating("PG-13");
          movie15.setYear("2009");

          list.add(movie1);
          list.add(movie2);
          list.add(movie3);
          list.add(movie4);
          list.add(movie5);
          list.add(movie6);
          list.add(movie7);
          list.add(movie8);
          list.add(movie9);
          list.add(movie10);
          list.add(movie11);
          list.add(movie12);
          list.add(movie13);
          list.add(movie14);
          list.add(movie15);

          return list;

    }

    @Test
    public void testSelectFittestMovies() throws Exception
    {

        movies = this.loadMovies();

        Genotype population = Genotype.randomInitialGenotype( conf );

        IChromosome bestSolutionSoFar=movieChromosome;

        for( int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++ )        {          	population.evolve();          	IChromosome candidateBestSolution = population.getFittestChromosome();        	if (candidateBestSolution.getFitnessValue()>bestSolutionSoFar.getFitnessValue())
            {
                bestSolutionSoFar = candidateBestSolution;
            }
        }
          printSolution(bestSolutionSoFar,movies);
    }

    public void printSolution(IChromosome solution, List movies)
    {
        System.out.println("#################################################################################################################");
        System.out.println("Fitness value: " + solution.getFitnessValue());

            for (int i = 0; i < solution.size(); i++) {
                int index = (Integer) solution.getGene(i).getAllele();
                  Movie movie = movies.get(index);
                  System.out.println(movie.toString());
                }
        System.out.println("#################################################################################################################");
    }
}

Step 4: Initialize the Population    The the first step in a GA  is to initialize the population of chromosomes (potential solutions).  A Genotype is defined as  a population of Chromosomes.  In JGAP, this the genotype is represented by a Genotype object.  This  object provides the capability to randomly initialize a population of Chromosomes.

Reference Listing 3 : TestMovieFitness.java for the following:

In line 265, we use the Genotype object to randomly initialize our sample of Chromosomes based on criteria we specified in         lines 75-79

Step 5: Evolve the Population    The final step is to evolve the population.  In this step we iterate over the population for a  specified number of times based on the  MAX_ALLOWED_EVOLUTIONS constant.  During evolution, JGAP evaluates  each Chromosome in the current population to determine a ‘best fit’ solution.  The best Chromosome in our problem space will have the highest fitness score.   The  fitness score is a rating based on genre preferences and IMDB rating.

Reference Listing 3 : TestMovieFitness.java for the following:

In line 270, we evolve the population.  During this process, JGAP will internally swap Genes with respective Chromosomes and ‘less fit’ Chromosomes will be discarded from the population.

Unit Testing JGAP    A JUnit test is utilized to demonstrate our GA using JGAP.

Change directory to the project’s root folder.

In order to run, we must specify a value for the GENRES system variable to indicate our movie preferences.

Type:
mvn clean test -DGENRES=Action,Comedy

You should now see results similar to the following:

As a result, based on genre preferences and IMDB ratings, JGAP determines the best collection of movies to be “Hitch”, “The Dark Knight”, and “The Hangover 2”.  

——————————————————-
T E S T S
——————————————————-
Running techbysample.jgap3.sample1.TestMovieFitness
#################################################################################################################
Fitness value: 32.2
Movie [name=Hitch, genre=[Comedy, Romance], rating=PG-13, imdbRating=10.0, year=2005]
Movie [name=The Dark Knight, genre=[Action], rating=PG-13, imdbRating=9.6, year=2008]
Movie [name=The Hangover 2, genre=[Comedy], rating=R, imdbRating=9.6, year=2012]
#################################################################################################################
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 15.174 sec

Make it a JGAP movie night!

Resources:

Official JGAP website

Official TechBySample GitHub repository

 
 Share on Facebook Share on Twitter Share on Reddit Share on LinkedIn
No Comments  comments 
© Techbysample.com, all rights reserved.