TimedProblemTest.java

import java.util.Arrays;
import java.util.Random;

import dist.DiscreteDependencyTree;
import dist.DiscretePermutationDistribution;
import dist.DiscreteUniformDistribution;
import dist.Distribution;
import opt.DiscreteChangeOneNeighbor;
import opt.EvaluationFunction;
import opt.GenericHillClimbingProblem;
import opt.HillClimbingProblem;
import opt.NeighborFunction;
import opt.RandomizedHillClimbing;
import opt.SimulatedAnnealing;
import opt.SwapNeighbor;
import opt.example.KnapsackEvaluationFunction;
import opt.example.TravelingSalesmanCrossOver;
import opt.example.TravelingSalesmanEvaluationFunction;
import opt.example.TravelingSalesmanRouteEvaluationFunction;
import opt.example.TravelingSalesmanSortEvaluationFunction;
import opt.ga.CrossoverFunction;
import opt.ga.DiscreteChangeOneMutation;
import opt.ga.GenericGeneticAlgorithmProblem;
import opt.ga.GeneticAlgorithmProblem;
import opt.ga.MutationFunction;
import opt.ga.StandardGeneticAlgorithm;
import opt.ga.SwapMutation;
import opt.ga.UniformCrossOver;
import opt.prob.GenericProbabilisticOptimizationProblem;
import opt.prob.MIMIC;
import opt.prob.ProbabilisticOptimizationProblem;
import shared.FixedIterationTrainer;
import shared.Trainer;

/**
 * A test using the flip flop evaluation function
 * @author Andrew Guillory gtg008g@mail.gatech.edu
 * @version 1.0
 */
public class TimedProblemTest {
    /** Random number generator */
    private static final Random random = new Random();
    /** The number of copies each */
    private static final int COPIES_EACH = 4;
    /** The maximum value for a single element */
    private static final double MAX_VALUE = 50;
    /** The maximum weight for a single element */
    private static final double MAX_WEIGHT = 50;
    
    /** The n value */
    public static void main(String[] args) {        
        for(int i = 40; i < 240; i += 40) {
            int NUM_ITEMS = i;
            double MAX_KNAPSACK_WEIGHT =
                    MAX_WEIGHT * NUM_ITEMS * COPIES_EACH * .4;
            
            int[] copies = new int[NUM_ITEMS];
            Arrays.fill(copies, COPIES_EACH);
            double[] values = new double[NUM_ITEMS];
            double[] weights = new double[NUM_ITEMS];
            for (int j = 0; j < NUM_ITEMS; j++) {
                values[j] = random.nextDouble() * MAX_VALUE;
                weights[j] = random.nextDouble() * MAX_WEIGHT;
            }
            int[] ranges = new int[NUM_ITEMS];
            Arrays.fill(ranges, COPIES_EACH + 1);

            EvaluationFunction ef = new KnapsackEvaluationFunction(values, weights, MAX_KNAPSACK_WEIGHT, copies);
            Distribution odd = new DiscreteUniformDistribution(ranges);
            NeighborFunction nf = new DiscreteChangeOneNeighbor(ranges);

            MutationFunction mf = new DiscreteChangeOneMutation(ranges);
            CrossoverFunction cf = new UniformCrossOver();
            Distribution df = new DiscreteDependencyTree(.1, ranges);

            HillClimbingProblem hcp = new GenericHillClimbingProblem(ef, odd, nf);
            GeneticAlgorithmProblem gap = new GenericGeneticAlgorithmProblem(ef, odd, mf, cf);
            ProbabilisticOptimizationProblem pop = new GenericProbabilisticOptimizationProblem(ef, odd, df);
            
            RandomizedHillClimbing rhc = new RandomizedHillClimbing(hcp);      
            TimedIterationTrainer fit = new TimedIterationTrainer(rhc, 2000);
            fit.train();
            double rhcOptimal = ef.value(rhc.getOptimal());
            
            SimulatedAnnealing sa = new SimulatedAnnealing(100, .95, hcp);
            fit = new TimedIterationTrainer(sa, 2000);
            fit.train();
            double saOptimal = ef.value(sa.getOptimal());
            
            StandardGeneticAlgorithm ga = new StandardGeneticAlgorithm(200, 150, 25, gap);
            fit = new TimedIterationTrainer(ga, 2000);
            fit.train();
            double gaOptimal = ef.value(ga.getOptimal());
            
            MIMIC mimic = new MIMIC(200, 100, pop);
            fit = new TimedIterationTrainer(mimic, 2000);
            fit.train();
            double mimicOptimal = ef.value(mimic.getOptimal());
            
            System.out.println(i + "," + rhcOptimal + "," + saOptimal + "," + gaOptimal + "," + mimicOptimal);
        }
    }
    
    public static class TimedIterationTrainer implements Trainer {
        private Trainer trainer;
        private long time;
        public TimedIterationTrainer(Trainer t, long t1) {
            trainer = t;
            time = t1;
        }
        
        public double train() {
            int iterations = 0;
            double sum = 0;
            long start = System.currentTimeMillis();
            while((System.currentTimeMillis()-start) < time) {
                sum += trainer.train();
            }
            return sum / iterations;
        }
    }
}