N Queen Problem
16
Problema damelor: fiind dată o tablă de şah de dimensiuni nXn, să se aranjeze n dame (regine) astfel încât nici una să nu fie ameninţată de o altă damă (să nu fie poziţionate pe aceeaşi linie, coloană sau diagonală) cu ajutorul algorimtilor genetici. REZOLVARE: - Pentru rezolvare s-a folosit Metoda Fitness si Metoda incrucisarii; - Atasat sunt afisate print-uri cu programul ruland. - Comment-urile sunt colorate cu ROSU; NOTA !: - Codul sursa nu imi apartine in totalitate, am luat o problema n-queens rezolvata in algoritmi genetici si cu metoda fitness- ului, AM REFACTORIZAT-O (pentru a o intelege mai bine si a o putea explica cu ajutorul commenturi-lor). package georgiu.ioan.finder.adapters; import java.util.ArrayList; import java.util.Random; public class NQueen1 { /** *Se initializeaza numarul populatie la start. */ private static final int START_SIZE = 75; /** *Se allege un numar arbitrar pentru ciclurile de test. */ private static final int MAX_EPOCHS = 1000; /** *Probabilitatea ca 2 cromozomi sa formeze o pereche. Probabilitatea variaza intre 0.0 si MATING_PROBABILITY < 1.0 */ private static final double MATING_PROBABILITY = 0.7; /** *Se selecteaza rata mutatiei. Aceasta variaza intre 0.0 < MUTATION_RATE < 1.0 */ private static final double MUTATION_RATE = 0.001; /** *Se allege numarul minim de “parinti” pentru selectie. */ private static final int MIN_SELECT = 10; /** * Se allege numarul maxim de “parinti” pentru selectie. Acesta variaza intre: MIN_SELECT < MAX_SELECT < START_SIZE */
description
test
Transcript of N Queen Problem
-
Problema damelor: fiind dat o tabl de ah de dimensiuni nXn, s se aranjeze n dame (regine) astfel
nct nici una s nu fie ameninat de o alt dam (s nu fie poziionate pe aceeai linie, coloan sau
diagonal) cu ajutorul algorimtilor genetici.
REZOLVARE:
- Pentru rezolvare s-a folosit Metoda Fitness si Metoda incrucisarii;
- Atasat sunt afisate print-uri cu programul ruland.
- Comment-urile sunt colorate cu ROSU;
NOTA !:
- Codul sursa nu imi apartine in totalitate, am luat o problema n-queens rezolvata in algoritmi genetici si cu metoda fitness-
ului, AM REFACTORIZAT-O (pentru a o intelege mai bine si a o
putea explica cu ajutorul commenturi-lor).
package georgiu.ioan.finder.adapters;
import java.util.ArrayList;
import java.util.Random;
public class NQueen1 {
/**
*Se initializeaza numarul populatie la start.
*/
private static final int START_SIZE = 75;
/**
*Se allege un numar arbitrar pentru ciclurile de test.
*/
private static final int MAX_EPOCHS = 1000;
/**
*Probabilitatea ca 2 cromozomi sa formeze o pereche.
Probabilitatea variaza intre 0.0 si MATING_PROBABILITY < 1.0
*/
private static final double MATING_PROBABILITY = 0.7;
/**
*Se selecteaza rata mutatiei. Aceasta variaza intre 0.0 <
MUTATION_RATE < 1.0
*/
private static final double MUTATION_RATE = 0.001;
/**
*Se allege numarul minim de parinti pentru selectie.
*/
private static final int MIN_SELECT = 10;
/**
* Se allege numarul maxim de parinti pentru selectie. Acesta
variaza intre: MIN_SELECT < MAX_SELECT < START_SIZE
*/
-
private static final int MAX_SELECT = 50;
/* Apar noi copii generatii create prin procesul generare.
Variaza intre 0 < OFFSPRING_PER_GENERATION < MAX_SELECT.
*/
private static final int OFFSPRING_PER_GENERATION = 20;
/**
* Se randomizeaza procesul de start al cromozomilor.
*/
private static final int MINIMUM_SHUFFLES = 8;
private static final int MAXIMUM_SHUFFLES = 20;
/**
*Prin procesul de Crossover(incrucisare), se alege maximul
pozitiei. Aceasta variaza intre 0 < PBC_MAX < 8 (> 8 nu este bun
pentru noi).
*/
private static final int PBC_MAX = 4;
/**
*Se allege latimea tablei de sah.
*/
private static final int MAX_LENGTH = 10;
private static int epoch = 0;
private static int childCount = 0;
/**
*Se allege procedura necesara pentru mutare.
*/
private static int nextMutation = 0;
private static int mutations = 0;
private static ArrayList population = new
ArrayList();
private static void algorithm() {
int popSize = 0;
boolean done = false;
Chromosome thisChromo = null;
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.getConflicts() == 0) || epoch ==
MAX_EPOCHS) {
done = true;
}
}
-
// Se calculeaza FITNESS-ul pentru fiecare individ in parte
initFitness();
// Se selecteaza o parte dintre indivizii calculate prin
metoda Fittness-ului
rouletteSelection();
// Se creeaza o o noua generatie de indivizi
mating(true);
// Se pregateste noua generatie de indivizi resetand pozitia
false
prepNextEpoch();
epoch++;
// Se afiseaza un counter in care se prezinta statusul.
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.getConflicts() == 0) {
printBestSolution(thisChromo);
}
}
}
System.out.println("Completed " + epoch + " epochs.");
System.out.println("Encountered " + mutations + " mutations in
" + childCount + " offspring.");
}
/**
* Se evalueaza fiecare membru selectat al populatiei si se
calculeaza metoda getFitness pentru fiecare individ in parte.
* Metoda getFitness se calculeaza in functie de cat de bine se
potriveste aceasta cu cerintele problemei.
*/
private static void initFitness() {
// Eroare cea mai mica = 100%, Cea mai ridicata = 0%
double bestScore = 0;
double worstScore = 0;
Chromosome thisChromo = null;
// Cel mai slab scor ar fi cel in care ar avea cea mai mare
energie, cel mai bun este cu cea mai putina energie.
worstScore = population.get(maximum()).getConflicts();
-
// Se face conversia cu un procentaj pe care in putem stabili
bestScore = worstScore -
population.get(minimum()).getConflicts();
for (Chromosome chromosome : population) {
thisChromo = chromosome;
thisChromo.setFitness((worstScore -
thisChromo.getConflicts()) * 100.0 / bestScore);
}
}
/**
* Aceasta metoda imbunatateste per total Fitness-ul populatiei
prin
* eliminarea indiviziilor nepotriviti si pastrarea doar a celor
potriviti pentru problema
*/
private static void rouletteSelection() {
int j = 0;
int popSize = population.size();
int maximumToSelect = getRandomNumber(MIN_SELECT, MAX_SELECT);
double genTotal = 0.0;
double selTotal = 0.0;
double rouletteSpin = 0.0;
boolean done = false;
Chromosome thisChromo = null;
Chromosome thatChromo = null;
for (Chromosome chromosome : population) {
thisChromo = chromosome;
genTotal += thisChromo.getFitness();
}
genTotal *= 0.01;
for (Chromosome chromosome : population) {
thisChromo = chromosome;
thisChromo.setSelectionProbability(thisChromo.getFitness()
/ genTotal);
}
// Se itereaza si se selecteaza numarul maxim dorit de indivizi
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.getSelectionProbability();
if (selTotal >= rouletteSpin) {
if (j == 0) {
thatChromo = population.get(j);
} else if (j >= popSize - 1) {
// daca j depaseste numarul de indivizi
// get ultimul individ
thatChromo = population.get(popSize - 1);
-
} else {
// daca j nu depasteste numarul de indivizi
// si nu este ultimul individ
// get ultimul individ de la pozitia j-1 pentru
ca
// numaratoarea incepe de la 0
thatChromo = population.get(j - 1);
}
thatChromo.setSelected(true);
done = true;
} else {
j++;
}
}
}
}
/**
* Aceasta metoda creeaza noi indivizi prin combinarea asptectelor
diecarui individ selectat. Se presupune ca prin combinarea anumitor
elemente din doi sau mai multi indivizi se va crea un offsping care
va mosteni cele mai bune parti ale ambilor parinti *
* @param mappedMating true este un parametru folosit pentru metoda
crossover mapped partial si false pentru metoda crossover
pozitionata.
*/
private static void mating(boolean mappedMating) {
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++) {
// Se alege random un parinte eligibil
parentA = chooseParent();
// Se alege random probabilitatea de a se crea o pereche
getRand = getRandomNumber(0, 100);
// Se testeaza probabilitatea de a se crea o pereche
if (getRand
-
partiallyMappedCrossover(parentA, parentB,
newIndex1, newIndex2);
} else {
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;
// Se programeaza o noua mutare.
if (childCount % (int) Math.round(1.0 / MUTATION_RATE)
== 0) {
nextMutation = childCount + getRandomNumber(0,
(int) Math.round(1.0 / MUTATION_RATE));
}
}
}
}
private static void partiallyMappedCrossover(int chromA, int
chromB, int child1, int child2) {
int j = 0;
int item1 = 0;
int item2 = 0;
int pos1 = 0;
int pos2 = 0;
int crossPoint1 = getRandomNumber(0, MAX_LENGTH - 1);
int crossPoint2 = getExclusiveRandomNumber(MAX_LENGTH - 1,
crossPoint1);
Chromosome thisChromo = population.get(chromA);
Chromosome thatChromo = population.get(chromB);
Chromosome newChromo1 = population.get(child1);
Chromosome newChromo2 = population.get(child2);
if (crossPoint2 < crossPoint1) {
j = crossPoint1;
crossPoint1 = crossPoint2;
crossPoint2 = j;
}
// Copy Parent genereaza noi indivizi.
for (int i = 0; i < MAX_LENGTH; i++) {
newChromo1.setData(i, thisChromo.getData(i));
newChromo2.setData(i, thatChromo.getData(i));
}
for (int i = crossPoint1; i
-
item2 = thatChromo.getData(i);
// Selecteaza itemii in offspring.
for (j = 0; j < MAX_LENGTH; j++) {
if (newChromo1.getData(j) == item1) {
pos1 = j;
} else if (newChromo1.getData(j) == item2) {
pos2 = j;
}
} // j
// Se efectueaza schimbarea.
if (item1 != item2) {
newChromo1.setData(pos1, item2);
newChromo1.setData(pos2, item1);
}
// Selecteaza itemii in offspring.
for (j = 0; j < MAX_LENGTH; j++) {
if (newChromo2.getData(j) == item2) {
pos1 = j;
} else if (newChromo2.getData(j) == item1) {
pos2 = j;
}
}
// Se efectueaza schimbarea.
if (item1 != item2) {
newChromo2.setData(pos1, item1);
newChromo2.setData(pos2, item2);
}
}
}
private static void positionBasedCrossover(int chromA, int chromB,
int child1, int child2) {
int k = 0;
int numPoints = 0;
int tempArray1[] = new int[MAX_LENGTH];
int tempArray2[] = new int[MAX_LENGTH];
boolean matchFound = false;
Chromosome thisChromo = population.get(chromA);
Chromosome thatChromo = population.get(chromB);
Chromosome newChromo1 = population.get(child1);
Chromosome newChromo2 = population.get(child2);
// Selectarea si alegerea crosspoints.
numPoints = getRandomNumber(0, PBC_MAX);
int crossPoints[] = new int[numPoints];
for (int i = 0; i < numPoints; i++) {
crossPoints[i] = getRandomNumber(0, MAX_LENGTH - 1,
crossPoints);
} // i
//Prin Get se aleg itemii care nu au fost alesi pentru al
doilea parinte.
k = 0;
for (int i = 0; i < MAX_LENGTH; i++) {
-
matchFound = false;
for (int j = 0; j < numPoints; j++) {
if (thatChromo.getData(i) ==
thisChromo.getData(crossPoints[j])) {
matchFound = true;
}
} // j
if (!matchFound) {
tempArray1[k] = thatChromo.getData(i);
k++;
}
} // i
// Se insereaza itemii alesi in child 1.
for (int i = 0; i < numPoints; i++) {
newChromo1.setData(crossPoints[i],
thisChromo.getData(crossPoints[i]));
}
// Se completeaza itemii care nu au fost alesi in child 1.
k = 0;
for (int i = 0; i < MAX_LENGTH; i++) {
matchFound = false;
for (int j = 0; j < numPoints; j++) {
if (i == crossPoints[j]) {
matchFound = true;
}
} // j
if (!matchFound) {
newChromo1.setData(i, tempArray1[k]);
k++;
}
} // i
//Prin Get se aleg itemii care nu au fost alesi pentru primul
parinte.
k = 0;
for (int i = 0; i < MAX_LENGTH; i++) {
matchFound = false;
for (int j = 0; j < numPoints; j++) {
if (thisChromo.getData(i) ==
thatChromo.getData(crossPoints[j])) {
matchFound = true;
}
} // j
if (!matchFound) {
tempArray2[k] = thisChromo.getData(i);
k++;
}
} // i
// Se insereaza itemii alesi in child 2.
for (int i = 0; i < numPoints; i++) {
newChromo2.setData(crossPoints[i],
thatChromo.getData(crossPoints[i]));
}
-
// Se completeaza itemii nealesi in child 2.
k = 0;
for (int i = 0; i < MAX_LENGTH; i++) {
matchFound = false;
for (int j = 0; j < numPoints; j++) {
if (i == crossPoints[j]) {
matchFound = true;
}
} // j
if (!matchFound) {
newChromo2.setData(i, tempArray2[k]);
k++;
}
} // i
}
/**
* Metoda adauga optiunea de random in genetica populatiei
* @param index este Index pentru cromozomi
* @param exchanges Number face schimbul numarului de cromozomi
*/
private static void exchangeMutation(final int index, final int
exchanges) {
int i = 0;
int tempData = 0;
int gene1 = 0;
int gene2 = 0;
boolean done = false;
Chromosome thisChromo = null;
thisChromo = population.get(index);
while (!done) {
gene1 = getRandomNumber(0, MAX_LENGTH - 1);
gene2 = getExclusiveRandomNumber(MAX_LENGTH - 1, gene1);
// Exchange the chosen genes.
tempData = thisChromo.getData(gene1);
thisChromo.setData(gene1, thisChromo.getData(gene2));
thisChromo.setData(gene2, tempData);
if (i == exchanges) {
done = true;
}
i++;
}
mutations++;
}
/**
* Aceasta metoda allege random un parinte
* @return A alege random un individ din lista
*/
private static int chooseParent() {
return chooseParent(-1);
}
private static int chooseParent(final int parentA) {
-
int parent = 0;
boolean done = false;
Chromosome thisChromo = null;
while (!done) {
// Se allege un parinte potrivit.
parent = getRandomNumber(0, population.size() - 1);
// Daca parentA este egal cu -1 atunci inseamna ca
// trebuie sa alegem primul parinte
if (parentA == -1) {
thisChromo = population.get(parent);
// see if the individual is one of the
// previously selected ones
// and finish the loop
if (thisChromo.isSelected()) {
done = true;
}
// daca parentA nu etse egal cu -1 atunci inseamna ca
// trebuie sa alegem al doilea parinte
// si trebuie sa verificam daca parintele selectat
// nu este la fel cu primul parinte selectat
} else if (parent != parentA) {
thisChromo = population.get(parent);
// Se verifica daca individul selectat este unul dintre
// indivizii selectati anterior
if (thisChromo.isSelected()) {
done = true;
}
}
}
return parent;
}
/**
* Aceasta metoda reseteaza informatia pentru fiecare individ
selectat.
*/
private static void prepNextEpoch() {
int popSize = 0;
Chromosome thisChromo = null;
// Se reseteaza informatia prin isSelected indivizi.
popSize = population.size();
for (int i = 0; i < popSize; i++) {
thisChromo = population.get(i);
thisChromo.setSelected(false);
}
}
private static void printBestSolution(Chromosome bestSolution) {
String board[][] = new String[MAX_LENGTH][MAX_LENGTH];
// Se sterge, curate table de sah.
for (int x = 0; x < MAX_LENGTH; x++) {
for (int y = 0; y < MAX_LENGTH; y++) {
-
board[x][y] = "";
}
}
for (int x = 0; x < MAX_LENGTH; x++) {
board[x][bestSolution.getData(x)] = "Q";
}
// Se afiseaza tabela de sah.
System.out.println("Board:");
for (int y = 0; y < MAX_LENGTH; y++) {
for (int x = 0; x < MAX_LENGTH; x++) {
if (board[x][y].equals("Q")) {
System.out.print("Q ");
} else {
System.out.print(". ");
}
}
System.out.print("\n");
}
}
private static int getRandomNumber(final int low, final int high) {
return (int) Math.round((high - low) * new
Random().nextDouble() + low);
}
private static int getExclusiveRandomNumber(final int high, final
int except) {
boolean done = false;
int getRand = 0;
while (!done) {
getRand = new Random().nextInt(high);
if (getRand != except) {
done = true;
}
}
return getRand;
}
private static int getRandomNumber(int low, int high, int[] except)
{
boolean done = false;
int getRand = 0;
if (high != low) {
while (!done) {
done = true;
getRand = (int) Math.round((high - low) * new
Random().nextDouble() + low);
for (int anExcept : except) {
if (getRand == anExcept) {
done = false;
}
} // i
}
-
return getRand;
} else {
return high; // sau low (nu conteaza care dintre cele 2
variabile).
}
}
private static int minimum() {
// Returneaza un array index.
int popSize = 0;
int winner = 0;
boolean foundNewWinner = false;
boolean done = false;
Chromosome thisChromo = null;
Chromosome thatChromo = null;
while (!done) {
foundNewWinner = false;
popSize = population.size();
for (int i = 0; i < popSize; i++) {
if (i != winner) { // Avoid self-
comparison.
thisChromo = population.get(i);
thatChromo = population.get(winner);
if (thisChromo.getConflicts() <
thatChromo.getConflicts()) {
winner = i;
foundNewWinner = true;
}
}
}
if (!foundNewWinner) {
done = true;
}
}
return winner;
}
private static int maximum() {
// Returneaza un array index.
int popSize = 0;
Chromosome thisChromo = null;
Chromosome thatChromo = null;
int winner = 0;
boolean foundNewWinner = false;
boolean done = false;
while (!done) {
foundNewWinner = false;
popSize = population.size();
for (int i = 0; i < popSize; i++) {
if (i != winner) { // Avoid self-
comparison.
thisChromo = population.get(i);
thatChromo = population.get(winner);
if (thisChromo.getConflicts() >
thatChromo.getConflicts()) {
winner = i;
-
foundNewWinner = true;
}
}
}
if (!foundNewWinner) {
done = true;
}
}
return winner;
}
/**
* Aceasta metoda initializeaza cromozomii prin folosirea {@link
START_SIZE}
* ca si marime a populatiei
*/
private static void initializeChromosomes() {
int shuffles = 0;
int chromoIndex = 0;
Chromosome newChromo = null;
for (int i = 0; i < START_SIZE; i++) {
newChromo = new Chromosome();
population.add(newChromo);
chromoIndex = population.indexOf(newChromo);
// Se allege random numarul de iteratii care sa fie
realizate.
shuffles = getRandomNumber(MINIMUM_SHUFFLES,
MAXIMUM_SHUFFLES);
//Se adauga informatii pentru fiecare cromozom ales
individual
exchangeMutation(chromoIndex, shuffles);
population.get(chromoIndex).computeConflicts();
}
}
private static class Chromosome {
private int mConflicts = 0;
private int mData[] = new int[MAX_LENGTH];
private double mFitness = 0.0;
private double mSelectionProbability = 0.0;
private boolean mSelected = false;
/**
* Constructor
* Creeaza data de la 1 la {@link MAX_LENGTH}
*/
public Chromosome() {
for (int i = 0; i < MAX_LENGTH; i++) {
this.mData[i] = i;
}
}
public void computeConflicts() {
-
int x = 0;
int y = 0;
int tempx = 0;
int tempy = 0;
int conflicts = 0;
int dx[] = new int[]{-1, 1, -1, 1};
int dy[] = new int[]{-1, 1, 1, -1};
boolean done = false;
String board[][] = new String[MAX_LENGTH][MAX_LENGTH];
// Se face clear la table de sah.
for (int i = 0; i < MAX_LENGTH; i++) {
for (int j = 0; j < MAX_LENGTH; j++) {
board[i][j] = "";
}
}
for (int i = 0; i < MAX_LENGTH; i++) {
board[i][this.mData[i]] = "Q";
}
// Se trece prin fiecare din Queens de pe table si se
calculeaza numarul de conflicte.
for (int i = 0; i < MAX_LENGTH; i++) {
x = i;
y = this.mData[i];
// Se verifica fiecare diagonal daca exista sau nu
conflicte.
for (int j = 0; j = MAX_LENGTH) ||
(tempy < 0 || tempy >= MAX_LENGTH)) {
done = true;
} else {
if
(board[tempx][tempy].compareToIgnoreCase("Q") == 0) {
conflicts++;
}
}
}
}
}
this.mConflicts = conflicts;
}
public void setConflicts(int value) {
this.mConflicts = value;
}
public int getConflicts() {
return this.mConflicts;
-
}
public double getSelectionProbability() {
return this.mSelectionProbability;
}
public void setSelectionProbability(final double SelProb) {
this.mSelectionProbability = SelProb;
}
public boolean isSelected() {
return this.mSelected;
}
public void setSelected(final boolean sValue) {
this.mSelected = sValue;
}
public double getFitness() {
return this.mFitness;
}
public void setFitness(final double score) {
this.mFitness = score;
}
public int getData(final int index) {
return this.mData[index];
}
public void setData(final int index, final int value) {
this.mData[index] = value;
}
}
public static void main(String[] args) {
algorithm();
}
}
-
ScreenShots:
