//Genetic Algorithm
//Author: Andrew Guandique
//Objective: Solve N-queens puzzle game using GA
//Objective: Solve N-queens puzzle game using GA
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;
public class Genetic {
/* Genetic Algorithm:
* This implementation ensures that from the outset there are
* individuals with repeated genes. Based on this fact, the
* method uses PMX crossover operation.
* An implementation that allows repeated genes should
* use a new type of mixing (eg. one point, two point, etc.)
* /
*/
private static Random rand = new Random();
private static final int NUM_QUEENS = 8;
private static final int POP_DIM = 50;
private static int num_generation = 0;
public Genetic() {
// 1. create the initial population of randomly
Individual population [] = new Individual [POP_DIM];
for(int i=0;i<population.length;++i) {
int a[] = new int[NUM_QUEENS];
for(int j=0;j<NUM_QUEENS;++j) {
int k = rand.nextInt(NUM_QUEENS) + 1; // nextInt =[0,8[ + 1 = [1,8]
if(contains(k,a)) { --j; } // if(repeated) re-roll
else { a[j] = k; }
}
population[i] = new Individual(a);
}
// kick off
begin(population);
}
/**
* Begin.
*/
private void begin (Individual []population) {
// 2. Evaluate each individual through the function of adaptability
int TotalFitness = 0;
for(int i = 0; i < POP_DIM; ++i) {
int adapt = fitness(population[i]);
population[i].setAdaptability(adapt);
TotalFitness += adapt;
}
// 3. repeat
// 3.1. select the most suitable individuals for reproduction
Individual parents[] = selection(population,TotalFitness);
// 3.2. generate the new population by crossover and mutation
Individual offspring[] = crossover(parents);
offspring = mutation(offspring);
// 3.3. population replacement
Individual new_generation[] = replace(population, parents, offspring);
// 4. end
for(Individual i : new_generation) {
if(perfect(i.getGenes())) {
System.out.println(i);
return;
}
}
System.out.println("Generation nº: "+(++num_generation));
begin(new_generation);
}
/**
* Method that performs the function of adaptability
*
* @param e - evaluate individual
* @return - value of adaptability between [0, 100]
*/
private int fitness(Individual e) {
int g[] = e.getGenes();
int fitness = 99; // assume that the individual is perfect
// Redundant, is not permitted to start and the mutation does not replicate genes
// If (horizontal_intersection (g))
// Fitness -= 99;
// Discounts the number of imperfections (max. 49)
fitness -= diagonal_intersection(g);
// if(fitness < 0)
// fitness = 0;
// fitness € [50,99]
return fitness;
}
/**
* Method of the individuals responsible for selecting parents
* is performed using the method of roulette
* @param pop - population from which individuals are chosen
* @param TotalFitness - the value used for normalization
* @return - array dimension with the parents NUM_parents
*/
private Individual[] selection(Individual pop[], int TotalFitness) {
final int NUM_parents = (int)(((double)POP_DIM)*0.6);
Individual parents[] = new Individual[NUM_parents];
for(int i=0;i<NUM_parents;++i) {
int r = rand.nextInt(TotalFitness);
int s = 0;
for(Individual idv : pop) {
s += idv.getadaptability();
if(s>=r) { parents[i] = idv; break; }
}
}
return parents;
}
/**
* Method that performs the crossing between the parents
*
* @param progs - parents
* @return - the result of crossing parent
*/
private Individual[] crossover(Individual progs[]) {
Individual xover_result[] = new Individual[progs.length];
// 2 offspring for each pair of parents
for(int i=0,k=0;i<progs.length/2;++i) {
// randomly choose two parents
Individual p1 = (Individual)Array.get(progs,rand.nextInt(progs.length));
Individual p2 = (Individual)Array.get(progs,rand.nextInt(progs.length));
// Make the crossing between the two
int pmx1 = rand.nextInt(NUM_QUEENS); // select the first point of intersection
int pmx2 = rand.nextInt(NUM_QUEENS); // select the second point of intersection
if(pmx1>pmx2) {
int aux = pmx1;
pmx1 = pmx2;
pmx2 = aux;
}
// Get the genes from each parent
int e1[] = p1.getGenes();
int e2[] = p2.getGenes();
// Initialize the individuals of the new genes
int a1[] = new int[NUM_QUEENS];
int a2[] = new int[NUM_QUEENS];
// Fill the new individuals with:
// inner values of the points of intersection
for(int j=pmx1;j<pmx2;++j) {
a1[j] = e1[j];
a2[j] = e2[j];
}
// values of the left of the first crossing point
for(int j=0;j<pmx1;++j) {
a1[j] = pmx(e2[j],a1,e2,pmx1,pmx2);
a2[j] = pmx(e1[j],a2,e1,pmx1,pmx2);
}
// values of the right of the second crossing point
for(int j=pmx2;j<NUM_QUEENS;++j) {
a1[j] = pmx(e2[j],a1,e2,pmx1,pmx2);
a2[j] = pmx(e1[j],a2,e1,pmx1,pmx2);
}
// Create two individuals with the genetic code of the intersection
Individual idv1 = new Individual(a1);
Individual idv2 = new Individual(a2);
xover_result[k++] = idv1;
xover_result[k++] = idv2;
}
return xover_result;
}
/**
* Randomly select three individuals who will suffer a mutation in its Genome
*/
private Individual[] mutation(Individual []desc) {
for(int i=0;i<3;++i) {
int k = rand.nextInt(desc.length);
int g[] = desc[k].getGenes();
int m = g[0];
for(int j=0;j<g.length-1;++j) {
g[j] = g[j+1];
}
g[g.length-1] = m;
desc[k].setGenes(g);
}
return desc;
}
/**
* Replacement of the old population by new generation
* We use a mix of crossover and direct promotion of the most adaptable of the older generation
*/
private Individual[] replace(Individual pop[], Individual progs[], Individual desc[]) {
Individual []new_generation = new Individual[POP_DIM];
for(int i=0;i<desc.length;++i) {
new_generation[i] = desc[i];
}
// Direct promotion of the best 40% of the older generation
Arrays.sort(pop); // sort in ascending order
for(int i=desc.length;i<pop.length;++i) {
new_generation[i] = pop[i];
}
return new_generation;
}
/**
* Helper method that indicates whether a value is present in a given array
*/
private static boolean contains(int i, int a[]) {
for(int k=0;k<a.length;++k) {
if(a[k]==i) return true;
}
return false;
}
/**
* Method that validates the value of integration according to the technique PMX
*/
private static int pmx(int i, int a[], int b[], int pmx1, int pmx2) {
if(!contains(i,a)) {
return i;
}
else {
int v=0;
for(int k=pmx1;k<pmx2;++k) {
if(a[k]==i) {
v = b[k];
break;
}
}
if(!contains(v,a))
return v;
else
return pmx(v,a,b,pmx1,pmx2);
}
}
/**
* Self-describing
*/
private static boolean horizontal_intersection(int g[]) {
for(int i=0;i<g.length;++i) {
for(int j=0;j<g.length;++j) {
if(i!=j && g[i]==g[j]) {
return true;
}
}
}
return false;
}
/**
* Method that calculates the number of existing intersections diagonal
*/
public static int diagonal_intersection(int g[]) {
int ret=0;
for(int i=0;i<g.length;++i) {
int x0 = i, y0 = g[i];
int xminus = x0-1, xplus = x0+1;
int yminus = y0-1, yplus = y0+1;
while(xminus>=0) {
if((yminus>=0 && g[xminus]==yminus) || (yplus<g.length && g[xminus]==yminus))
++ret;
--xminus;
--yminus;
++yplus;
}
yminus = y0-1; yplus = y0+1;
while(xplus<g.length) {
if((yminus>=0 && g[xplus]==yminus) || (yplus<g.length && g[xplus]==yplus))
++ret;
++xplus;
--yminus;
++yplus;
}
}
return ret;
}
/**
* Method that defines perfection (stop condition)
*
* @param - an individual's genes
* @return - true if the individual's genes are perfect
*/
private boolean perfect(int g[]) {
// Check if they are on the same line
if(horizontal_intersection(g))
return false;
// Check if they are on the same diagonal
if(diagonal_intersection(g)!=0)
return false;
return true;
}
public static void main(String []args) {
new Genetic();
}
}
class Individual implements Comparable {
private int genes[];
private int adaptability;
Individual(int i[]) { genes = i; }
public void setAdaptability(int adaptability) {
this.adaptability = adaptability;
}
public int getadaptability() {
return adaptability;
}
public void setGenes(int[] genes) {
this.genes = genes;
}
public int[] getGenes() {
return genes;
}
public String toString() {
StringBuffer sb = new StringBuffer("Genome Winner: ");
for(int i : genes) { sb.append(i); }
return sb.toString();
}
public int compareTo(Object arg0) {
Individual e = (Individual)arg0;
if(this.adaptability == e.getadaptability()) return 0;
else if(this.adaptability < e.getadaptability()) return -1;
else return 1;//if(>)
}
}
No comments:
Post a Comment