nqueenrunner.java

This is a java implementation for solving NQueen problem using genetic algorithm.Enjoy it!

package ir.ac.iust.evoalgs.nqueen;

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

import org.apache.log4j.Logger;

public class NQueenRunner {

	protected static int MAX_ITER = 10000;
	protected static int POPULATION_SIZE = 25;
	protected static int DIM = 24;
	private static Logger logger = Logger.getLogger(NQueenRunner.class);

	public static void main(String[] args) {
		for (int i = 1; i <= 20; i++) {
//			DIM = 4*i;
			IGeneticNQueenSolver solver = new GeneticNQueenSolver();
			solver.setSolutionHelper(new INQueenSolutionHelper() {

				@Override
				public double getCrossOverProb() {
					return 0.9;
				}

				@Override
				public double getMutationProb() {
					return 0.3;
				}

				@Override
				public int[] getTheBest(List<Gene> population) {

					Gene theBest = null;
					double minCost = Double.MAX_VALUE;
					for (Gene gene : population) {
						double tmp = 0;
						if ((tmp = getCost(gene)) <= minCost) {
							minCost = tmp;
							theBest = gene;
						}
					}

					return theBest.getString();
				}

				@Override
				public boolean hasBeenEnded(List<Gene> population, int iterNo) {

					if (iterNo >= MAX_ITER) {
						return true;
					}

					double cost = Double.MAX_VALUE;
					for (Gene gene : population) {
						double tmpCost = getCost(gene);
						if (tmpCost < cost) {
							cost = tmpCost;
							if (cost == 0)
								break;
						}
					}

					return cost == 0;
				}

				@Override
				public void initPopulation(List<Gene> population) {
					for (int i = 0; i < POPULATION_SIZE; i++)
						population.add(new Gene(DIM, true));
				}

				@Override
				public void onCompelete(NQueenProblem problem, NQueenSolution solution, int iterCnt) {
					logger.info("$ITER $COST".replace("$ITER", "" + iterCnt).replace("$COST",
									"" + getCost(new Gene(solution.getResult()))));
//					logger.info("{$ITER} : {$COST} : $P has been solved with $S.".replace("$P", problem.toString())
//							.replace("$S", solution.toString()).replace("$ITER", "" + iterCnt).replace("$COST",
//									"" + getCost(new Gene(solution.getResult()))));
				}

				@Override
				public void onProgress(int[] theBest, int iterNo) {
//					if (iterNo == 0) {
//						StringBuffer sb = new StringBuffer("");
//						sb.append(getCost(new Gene(theBest))).append(" is the best at start.");
//						logger.info(sb.toString());
//					}
				}

				@Override
				public Gene selectParent(List<Gene> population) {
					Random rand = new Random();
					int rand1 = rand.nextInt(POPULATION_SIZE);
//					int rand2 = rand.nextInt(POPULATION_SIZE);
//					int rand3 = rand.nextInt(POPULATION_SIZE);
//					int rand4 = rand.nextInt(POPULATION_SIZE);

					Gene g1 = population.get(rand1);
//					Gene g2 = population.get(rand2);
//					Gene g3 = population.get(rand3);
//					Gene g4 = population.get(rand4);

//					double cost1 = getCost(g1);
//					double cost2 = getCost(g2);
//					double cost3 = getCost(g3);
//					double cost4 = getCost(g4);

//					return (cost1 <= cost2 && cost1 <= cost3 && cost1 <= cost4) ? g1 : (cost2 <= cost1 && cost2 <= cost3 && cost2 <= cost4) ? g2 : cost3 <= cost4 ? g3 : g4;
					return g1;
				}

				@Override
				public void replacment(List<Gene> population, Gene[] genes) {
					for (Gene gene : genes) {
						double cost = getCost(gene);

						int worstIdx = -1;
						double tmpCost = 0;
						for (int i = 0; i < POPULATION_SIZE; i++) {
							double c1 = getCost(population.get(i));

							if (c1 > tmpCost) {
								tmpCost = c1;
								worstIdx = i;
							}
						}

						if (cost < getCost(population.get(worstIdx))) {
							population.remove(worstIdx);
							population.add(worstIdx, gene);
						}
					}
				}

				@Override
				public int getSleepSize() {
					return POPULATION_SIZE / 2;
				}
			});

			solver.solve(new NQueenProblem(DIM));
		}
	}

	protected static double getCost(Gene gene) {
		int dim = gene.getString().length;

		// diagonal collision
		int diag1Collision = 0;
		for (int j = 0; j < dim; j++) {
			int tmpCollision = 0;
			for (int i = 0; i <= j; i++) {
				if (gene.getString()[i] == (j - i)) {
					tmpCollision++;
				}
			}
			diag1Collision += (tmpCollision > 0 ? (tmpCollision - 1) : 0);
		}

		// XX revise shod
		int diag2Collision = 0;
		for (int j = dim - 1; j > 0; j--) {
			int tmpCollision = 0;
			for (int i = dim - 1; i >= j; i--) {
				if (gene.getString()[i] == (j + dim - 1 - i)) {
					tmpCollision++;
				}
			}
			diag2Collision += (tmpCollision > 0 ? (tmpCollision - 1) : 0);
		}

		int diag3Collision = 0;
		for (int j = 0; j < dim; j++) {
			int tmpCollision = 0;
			for (int i = dim - 1; i >= dim - 1 - j; i--) {
				if (gene.getString()[i] == (i + j - dim + 1)) {
					tmpCollision++;
				}
			}
			diag3Collision += (tmpCollision > 0 ? (tmpCollision - 1) : 0);
		}

		// XX revise shod
		int diag4Collision = 0;
		for (int j = dim - 1; j > 0; j--) {
			int tmpCollision = 0;
			for (int i = 0; i <= dim - 1 - j; i++) {
				if (gene.getString()[i] == (j + i)) {
					tmpCollision++;
				}
			}
			diag4Collision += (tmpCollision > 0 ? (tmpCollision - 1) : 0);
		}

		return diag1Collision + diag2Collision + diag3Collision + diag4Collision;
	}
}