GA.rar_GA_algorithms

import java.util.ArrayList; import java.util.Random; public class NQueen1 { private static final int START_SIZE = 75; // Population size at start. private static final int MAX_EPOCHS = 1000; // Arbitrary number of test cycles. private static final double MATING_PROBABILITY = 0.7; // Probability of two chromosomes mating. Range: 0.0 < MATING_PROBABILITY < 1.0 private static final double MUTATION_RATE = 0.001; // Mutation Rate. Range: 0.0 < MUTATION_RATE < 1.0 private static final int MIN_SELECT = 10; // Minimum parents allowed for selection. private static final int MAX_SELECT = 50; // Maximum parents allowed for selection. Range: MIN_SELECT < MAX_SELECT < START_SIZE private static final int OFFSPRING_PER_GENERATION = 20; // New offspring created per generation. Range: 0 < OFFSPRING_PER_GENERATION < MAX_SELECT. private static final int MINIMUM_SHUFFLES = 8; // For randomizing starting chromosomes private static final int MAXIMUM_SHUFFLES = 20; private static final int PBC_MAX = 4; // Maximum Position-Based Crossover points. Range: 0 < PBC_MAX < 8 (> 8 isn't good). private static final int MAX_LENGTH = 10; // chess board width. private static int epoch = 0; private static int childCount = 0; private static int nextMutation = 0; // For scheduling mutations. private static int mutations = 0; private static ArrayList<Chromosome> population = new ArrayList<Chromosome>(); private static void algorithm() { int popSize = 0; Chromosome thisChromo = null; boolean done = false; initializeChromosomes(); mutations = 0; nextMutation = getRandomNumber(0, (int)Math.round(1.0 / MUTATION_RATE)); while(!done) { popSize = population.size(); for(int i = 0; i < popSize; i++) { thisChromo = population.get(i); if((thisChromo.conflicts() == 0) || epoch == MAX_EPOCHS){ done = true; } } getFitness(); rouletteSelection(); mating(); prepNextEpoch(); epoch++; // This is here simply to show the runtime status. System.out.println("Epoch: " + epoch); } System.out.println("done."); if(epoch != MAX_EPOCHS){ popSize = population.size(); for(int i = 0; i < popSize; i++) { thisChromo = population.get(i); if(thisChromo.conflicts() == 0){ printbestSolution(thisChromo); } } } System.out.println("Completed " + epoch + " epochs."); System.out.println("Encountered " + mutations + " mutations in " + childCount + " offspring."); return; } private static void getFitness() { // Lowest errors = 100%, Highest errors = 0% int popSize = population.size(); Chromosome thisChromo = null; double bestScore = 0; double worstScore = 0; // The worst score would be the one with the highest energy, best would be lowest. worstScore = population.get(maximum()).conflicts(); // Convert to a weighted percentage. bestScore = worstScore - population.get(minimum()).conflicts(); for(int i = 0; i < popSize; i++) { thisChromo = population.get(i); thisChromo.fitness((worstScore - thisChromo.conflicts()) * 100.0 / bestScore); } return; } private static void rouletteSelection() { int j = 0; int popSize = population.size(); double genTotal = 0.0; double selTotal = 0.0; int maximumToSelect = getRandomNumber(MIN_SELECT, MAX_SELECT); double rouletteSpin = 0.0; Chromosome thisChromo = null; Chromosome thatChromo = null; boolean done = false; for(int i = 0; i < popSize; i++) { thisChromo = population.get(i); genTotal += thisChromo.fitness(); } genTotal *= 0.01; for(int i = 0; i < popSize; i++) { thisChromo = population.get(i); thisChromo.selectionProbability(thisChromo.fitness() / genTotal); } for(int i = 0; i < maximumToSelect; i++) { rouletteSpin = getRandomNumber(0, 99); j = 0; selTotal = 0; done = false; while(!done) { thisChromo = population.get(j); selTotal += thisChromo.selectionProbability(); if(selTotal >= rouletteSpin){ if(j == 0){ thatChromo = population.get(j); }else if(j >= popSize - 1){ thatChromo = population.get(popSize - 1); }else{ thatChromo = population.get(j - 1); } thatChromo.selected(true); done = true; }else{ j++; } } } return; } // This is where you can choose between options: // To choose between crossover options, uncomment one of: // partiallyMappedCrossover(), // positionBasedCrossover(), while keeping the other two commented out. // Keep in mind that the code will still run if(you try combinations or uncomment all of them, // but this might hinder the algorithm in general. // Of course, I could always be wrong, try it and find out! private static void mating() { int getRand = 0; int parentA = 0; int parentB = 0; int newIndex1 = 0; int newIndex2 = 0; Chromosome newChromo1 = null; Chromosome newChromo2 = null; for(int i = 0; i < OFFSPRING_PER_GENERATION; i++) { parentA = chooseParent(); // Test probability of mating. getRand = getRandomNumber(0, 100); if(getRand <= MATING_PROBABILITY * 100){ parentB = chooseParent(parentA); newChromo1 = new Chromosome(); newChromo2 = new Chromosome(); population.add(newChromo1); newIndex1 = population.indexOf(newChromo1); population.add(newChromo2); newIndex2 = population.indexOf(newChromo2); // Choose either, or both of these: partiallyMappedCrossover(parentA, parentB, newIndex1, newIndex2); //positionBasedCrossover(parentA, parentB, newIndex1, newIndex2); if(childCount - 1 == nextMutation){ exchangeMutation(newIndex1, 1); }else if(childCount == nextMutation){ exchangeMutation(newIndex2, 1); } population.get(newIndex1).computeConflicts(); population.get(newIndex2).computeConflicts(); childCount += 2; // Schedule next mutation. if(childCount % (int)Math.round(1.0 / MUTATION_RATE) == 0){ nextMutation = childCount + getRandomNumber(0, (int)Math.round(1.0 / MUTATION_RATE)); } } } // i return; } private static void partiallyMappedCrossover(int chromA, int chromB,