Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package pkg8.queens;
- import java.util.*;
- import java.util.function.Supplier;
- import javafx.util.Pair;
- class Individual {
- boolean[][] gene;
- int number_of_attacks;
- Pair<Integer, Integer> subInterval;
- int fitness;
- final int number_of_queens = 8;
- public Individual() {
- number_of_attacks = 0;
- fitness = 0;
- subInterval = new Pair<>(0, 0);
- gene = new boolean[number_of_queens][number_of_queens];
- }
- public Individual(int number_of_attacks, int fitness, boolean[][] queens) {
- this.number_of_attacks = number_of_attacks;
- this.fitness = fitness;
- this.gene = queens;
- }
- }
- public class Queens {
- static int population_size = 30;
- static final int maxNumberOfClashes = 28;
- static float pro_mutation = 0.0005f;
- static ArrayList<Individual> population = new ArrayList<>();
- static ArrayList<Individual> fittest_individuals = new ArrayList<>();
- static final int number_of_queens = 8;
- static Random random = new Random();
- static int sumOfFit = 0;
- static void print_population() {
- System.out.println("-----------------------------------------------");
- System.out.println("-----------------------------------------------");
- population.stream().forEach((ind) -> {
- System.out.println("fitness:" + ind.fitness);
- System.out.println("from:" + ind.subInterval.getKey() + "\tto:" + ind.subInterval.getValue());
- for (boolean[] booleans : ind.gene) {
- System.out.println(Arrays.toString(booleans));
- }
- System.out.println("--------------------------------------------------------");
- });
- System.out.println("-----------------------------------------------");
- System.out.println("-----------------------------------------------");
- }
- static void init_population() {
- for (int i = 0; i < population_size; i++) {
- boolean queens[][] = new boolean[number_of_queens][number_of_queens];
- for (int j = 0; j < number_of_queens; j++) {
- for (int k = 0; k < number_of_queens; k++) {
- queens[j][k] = false;
- }
- queens[j][random.nextInt(number_of_queens)] = true;
- }
- population.add(new Individual(number_of_attacks(queens), fittnes(number_of_attacks(queens)), queens));
- }
- }
- static void subInterval(ArrayList<Individual> inds) {
- sumOfFit = population.stream().map((ind) -> ind.fitness).reduce(0, (a, b) -> a + b);
- int to = 0, from = 0;
- int i = 0;
- while (i < inds.size()) {
- to += inds.get(i).fitness;
- inds.get(i).subInterval = new Pair<>(from, to);
- from = to;
- i++;
- }
- }
- static int numberOfAttacksOfOneQueen(boolean[][] queens, Pair<Integer, Integer> pos) {
- int count = 0;
- if (!queens[pos.getKey()][pos.getValue()]) {
- return count;
- }
- //column
- for (boolean[] queen : queens) {
- if (queen[pos.getValue()]) {
- count++;
- }
- }
- //row
- for (int j = 0; j < queens.length; j++) {
- if (queens[pos.getKey()][j]) {
- count++;
- }
- }
- //left of principal
- for (int i = 0; i < queens.length; i++) {
- for (int j = 0; j < queens[i].length; j++) {
- if ((pos.getKey() + pos.getValue() == i + j) && queens[i][j] && pos.getKey() != i && pos.getValue() != j) {
- count++;
- }
- }
- }
- //right of principal up -part
- for (int k = pos.getKey() - 1, z = pos.getValue() - 1; k >= 0 && z >= 0; k--, z--) {
- if (queens[k][z]) {
- count++;
- }
- }
- //right of principal down -part
- for (int k = pos.getKey() + 1, z = pos.getValue() + 1; k < queens.length && z < queens.length; k++, z++) {
- if (queens[k][z]) {
- count++;
- }
- }
- return count - 2;
- }
- static int number_of_attacks(boolean[][] queens) {
- int count = 0;
- label:
- for (int i = 0; i < queens.length; i++) {
- for (int j = 0; j < queens[i].length; j++) {
- if (queens[i][j]) {
- count += numberOfAttacksOfOneQueen(queens, new Pair<>(i, j));
- continue label;
- }
- }
- }
- return count / 2;
- }
- static int fittnes(int count) {
- return maxNumberOfClashes - count;
- }
- static Pair<Individual, Individual> selection() {
- System.out.println("-----------------Selection------------------------");
- int rand_m = random.nextInt(sumOfFit);
- int rand_f = random.nextInt(sumOfFit);
- Individual father = null, mother = null;
- for (int i = 0; i < population.size(); ++i) {
- Individual ind = population.get(i);
- if (rand_f >= ind.subInterval.getKey() && rand_f < ind.subInterval.getValue()) {
- father = ind;
- // continue;
- }
- if (rand_m >= ind.subInterval.getKey() && rand_m < ind.subInterval.getValue()) {
- mother = ind;
- }
- }
- return new Pair<>(father, mother);
- }
- static Pair<Individual, Individual> crossover(Pair<Individual, Individual> selectedParents) {
- System.out.println("--------------Crossover---------------------------");
- int croosPoint = random.nextInt(number_of_queens);
- Individual father = selectedParents.getKey();
- Individual mother = selectedParents.getValue();
- boolean[][] father_cp = new boolean[number_of_queens][number_of_queens];
- boolean[][] mother_cp = new boolean[number_of_queens][number_of_queens];
- for (int i = 0; i < number_of_queens; i++) {
- System.arraycopy(father.gene[i], 0, father_cp[i], 0, father.gene[i].length);
- System.arraycopy(mother.gene[i], 0, mother_cp[i], 0, mother.gene[i].length);
- }
- for (int i = croosPoint; i < number_of_queens; i++) {
- System.arraycopy(mother_cp[i], 0, father.gene[i], 0, mother_cp[i].length);
- System.arraycopy(father_cp[i], 0, mother.gene[i], 0, father_cp[i].length);
- }
- return selectedParents;
- }
- static Pair<Individual, Individual> mutation(Pair<Individual, Individual> parents) {
- System.out.println("----------------Mutation-------------------------");
- Individual father = parents.getKey();
- Individual mother = parents.getValue();
- Supplier<Boolean> r = () -> random.nextFloat() < pro_mutation;
- for (int i = 0; i < number_of_queens; i++) {
- if (r.get()) {
- Arrays.fill(father.gene[i], false);
- father.gene[i][random.nextInt(number_of_queens)] = true;
- }
- }
- for (int i = 0; i < number_of_queens; i++) {
- if (r.get()) {
- Arrays.fill(mother.gene[i], false);
- mother.gene[i][random.nextInt(number_of_queens)] = true;
- }
- }
- father.number_of_attacks = number_of_attacks(father.gene);
- father.fitness = fittnes(father.number_of_attacks);
- mother.number_of_attacks = number_of_attacks(mother.gene);
- mother.fitness = fittnes(mother.number_of_attacks);
- return parents;
- }
- static void fittest() {
- for (int i = 0; i < population.size(); i++) {
- if (population.get(i).fitness == maxNumberOfClashes) {
- fittest_individuals.add(population.get(i));
- }
- }
- }
- static void printMatingPool(Pair<Individual, Individual> parents) {
- System.out.println("--------------------MatingPool-----------------");
- System.out.println("-------------------------------Father-------------------------------");
- for (boolean[] booleanses : parents.getKey().gene) {
- System.out.println(Arrays.toString(booleanses));
- }
- System.out.println("-------------------------------Mother-------------------------------");
- for (boolean[] booleanses : parents.getValue().gene) {
- System.out.println(Arrays.toString(booleanses));
- }
- System.out.println("-----------------------------------------------------------------");
- }
- public static void main(String[] args) {
- init_population();
- fittest();
- subInterval(population);
- if (!fittest_individuals.isEmpty()) {
- fittest_individuals.forEach((ind) -> {
- for (boolean[] booleanse : ind.gene) {
- System.out.println(Arrays.toString(booleanse));
- }
- System.out.println("-------------------------------------");
- });
- return;
- }
- int gen = 0;
- while (gen <= 90_000) {
- System.out.println("----------------Population--size:" + population.size() + "--------------------------");
- //print_population();
- System.out.println("-----------------------------------------");
- Pair<Individual, Individual> matingPool = selection();
- //printMatingPool(matingPool);
- matingPool = crossover(matingPool);
- //printMatingPool(matingPool);
- matingPool = mutation(matingPool);
- //printMatingPool(matingPool);
- fittest();
- subInterval(population);
- System.out.println("gen:" + gen++);
- }
- System.out.println("-----------------Fittest Individuals------------------------");
- Set<Individual> set = new HashSet<>();
- set.addAll(fittest_individuals);
- fittest_individuals.clear();
- fittest_individuals.addAll(set);
- set = null;
- fittest_individuals.forEach((ind) -> {
- for (boolean[] booleanse : ind.gene) {
- System.out.println(Arrays.toString(booleanse));
- }
- System.out.println("-------------------------------------");
- });
- /*
- boolean[][] q = {{false, false, false, false, false, false, true, false},
- {false, false, false, false, true, false, false, false},
- {false, false, true, false, false, false, false, false},
- {true, false, false, false, false, false, false, false},
- {false, false, false, false, false, true, false, false},
- {false, false, false, false, false, false, false, true},
- {false, true, false, false, false, false, false, false},
- {false, false, false, true, false, false, false, false}};
- System.out.println(number_of_attacks(q));
- */
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement