SHARE
TWEET

8-Queens-updated.java

HasanRasulov Dec 11th, 2019 95 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package pkg8.queens;
  2.  
  3. import java.util.*;
  4. import java.util.function.Supplier;
  5. import javafx.util.Pair;
  6.  
  7. class Individual {
  8.  
  9.     boolean[][] gene;
  10.     int number_of_attacks;
  11.     Pair<Integer, Integer> subInterval;
  12.     int fitness;
  13.     final int number_of_queens = 8;
  14.  
  15.     public Individual() {
  16.  
  17.         number_of_attacks = 0;
  18.         fitness = 0;
  19.         subInterval = new Pair<>(0, 0);
  20.         gene = new boolean[number_of_queens][number_of_queens];
  21.  
  22.     }
  23.  
  24.     public Individual(int number_of_attacks, int fitness, boolean[][] queens) {
  25.  
  26.         this.number_of_attacks = number_of_attacks;
  27.         this.fitness = fitness;
  28.         this.gene = queens;
  29.  
  30.     }
  31.  
  32. }
  33.  
  34. public class Queens {
  35.  
  36.     static int population_size = 30;
  37.  
  38.     static final int maxNumberOfClashes = 28;
  39.  
  40.     static float pro_mutation = 0.0005f;
  41.  
  42.     static ArrayList<Individual> population = new ArrayList<>();
  43.  
  44.     static ArrayList<Individual> fittest_individuals = new ArrayList<>();
  45.  
  46.     static final int number_of_queens = 8;
  47.  
  48.     static Random random = new Random();
  49.  
  50.     static int sumOfFit = 0;
  51.  
  52.     static void print_population() {
  53.  
  54.         System.out.println("-----------------------------------------------");
  55.         System.out.println("-----------------------------------------------");
  56.  
  57.         population.stream().forEach((ind) -> {
  58.             System.out.println("fitness:" + ind.fitness);
  59.             System.out.println("from:" + ind.subInterval.getKey() + "\tto:" + ind.subInterval.getValue());
  60.             for (boolean[] booleans : ind.gene) {
  61.                 System.out.println(Arrays.toString(booleans));
  62.             }
  63.             System.out.println("--------------------------------------------------------");
  64.  
  65.         });
  66.  
  67.         System.out.println("-----------------------------------------------");
  68.         System.out.println("-----------------------------------------------");
  69.     }
  70.  
  71.     static void init_population() {
  72.  
  73.         for (int i = 0; i < population_size; i++) {
  74.  
  75.             boolean queens[][] = new boolean[number_of_queens][number_of_queens];
  76.  
  77.             for (int j = 0; j < number_of_queens; j++) {
  78.  
  79.                 for (int k = 0; k < number_of_queens; k++) {
  80.  
  81.                     queens[j][k] = false;
  82.                 }
  83.  
  84.                 queens[j][random.nextInt(number_of_queens)] = true;
  85.  
  86.             }
  87.  
  88.             population.add(new Individual(number_of_attacks(queens), fittnes(number_of_attacks(queens)), queens));
  89.  
  90.         }
  91.  
  92.     }
  93.  
  94.     static void subInterval(ArrayList<Individual> inds) {
  95.  
  96.         sumOfFit = population.stream().map((ind) -> ind.fitness).reduce(0, (a, b) -> a + b);
  97.  
  98.         int to = 0, from = 0;
  99.         int i = 0;
  100.  
  101.         while (i < inds.size()) {
  102.  
  103.             to += inds.get(i).fitness;
  104.  
  105.             inds.get(i).subInterval = new Pair<>(from, to);
  106.             from = to;
  107.             i++;
  108.         }
  109.  
  110.     }
  111.  
  112.     static int numberOfAttacksOfOneQueen(boolean[][] queens, Pair<Integer, Integer> pos) {
  113.  
  114.         int count = 0;
  115.  
  116.         if (!queens[pos.getKey()][pos.getValue()]) {
  117.             return count;
  118.         }
  119.  
  120.         //column
  121.         for (boolean[] queen : queens) {
  122.             if (queen[pos.getValue()]) {
  123.                 count++;
  124.             }
  125.         }
  126.         //row
  127.         for (int j = 0; j < queens.length; j++) {
  128.  
  129.             if (queens[pos.getKey()][j]) {
  130.                 count++;
  131.             }
  132.  
  133.         }
  134.         //left of principal
  135.         for (int i = 0; i < queens.length; i++) {
  136.  
  137.             for (int j = 0; j < queens[i].length; j++) {
  138.  
  139.                 if ((pos.getKey() + pos.getValue() == i + j) && queens[i][j] && pos.getKey() != i && pos.getValue() != j) {
  140.                     count++;
  141.                 }
  142.  
  143.             }
  144.  
  145.         }
  146.         //right of principal up -part
  147.         for (int k = pos.getKey() - 1, z = pos.getValue() - 1; k >= 0 && z >= 0; k--, z--) {
  148.  
  149.             if (queens[k][z]) {
  150.                 count++;
  151.             }
  152.  
  153.         }
  154.         //right of principal down -part
  155.         for (int k = pos.getKey() + 1, z = pos.getValue() + 1; k < queens.length && z < queens.length; k++, z++) {
  156.  
  157.             if (queens[k][z]) {
  158.                 count++;
  159.             }
  160.  
  161.         }
  162.  
  163.         return count - 2;
  164.     }
  165.  
  166.     static int number_of_attacks(boolean[][] queens) {
  167.         int count = 0;
  168.  
  169.         label:
  170.         for (int i = 0; i < queens.length; i++) {
  171.             for (int j = 0; j < queens[i].length; j++) {
  172.                 if (queens[i][j]) {
  173.                     count += numberOfAttacksOfOneQueen(queens, new Pair<>(i, j));
  174.                     continue label;
  175.                 }
  176.             }
  177.  
  178.         }
  179.         return count / 2;
  180.     }
  181.  
  182.     static int fittnes(int count) {
  183.         return maxNumberOfClashes - count;
  184.     }
  185.  
  186.     static Pair<Individual, Individual> selection() {
  187.  
  188.         System.out.println("-----------------Selection------------------------");
  189.  
  190.         int rand_m = random.nextInt(sumOfFit);
  191.         int rand_f = random.nextInt(sumOfFit);
  192.  
  193.         Individual father = null, mother = null;
  194.  
  195.         for (int i = 0; i < population.size(); ++i) {
  196.  
  197.             Individual ind = population.get(i);
  198.  
  199.             if (rand_f >= ind.subInterval.getKey() && rand_f < ind.subInterval.getValue()) {
  200.                 father = ind;
  201.  
  202. //                continue;
  203.             }
  204.             if (rand_m >= ind.subInterval.getKey() && rand_m < ind.subInterval.getValue()) {
  205.  
  206.                 mother = ind;
  207.  
  208.             }
  209.  
  210.         }
  211.  
  212.         return new Pair<>(father, mother);
  213.  
  214.     }
  215.  
  216.     static Pair<Individual, Individual> crossover(Pair<Individual, Individual> selectedParents) {
  217.  
  218.         System.out.println("--------------Crossover---------------------------");
  219.  
  220.         int croosPoint = random.nextInt(number_of_queens);
  221.  
  222.         Individual father = selectedParents.getKey();
  223.         Individual mother = selectedParents.getValue();
  224.  
  225.         boolean[][] father_cp = new boolean[number_of_queens][number_of_queens];
  226.         boolean[][] mother_cp = new boolean[number_of_queens][number_of_queens];
  227.  
  228.         for (int i = 0; i < number_of_queens; i++) {
  229.  
  230.             System.arraycopy(father.gene[i], 0, father_cp[i], 0, father.gene[i].length);
  231.             System.arraycopy(mother.gene[i], 0, mother_cp[i], 0, mother.gene[i].length);
  232.  
  233.         }
  234.  
  235.         for (int i = croosPoint; i < number_of_queens; i++) {
  236.  
  237.             System.arraycopy(mother_cp[i], 0, father.gene[i], 0, mother_cp[i].length);
  238.             System.arraycopy(father_cp[i], 0, mother.gene[i], 0, father_cp[i].length);
  239.         }
  240.  
  241.         return selectedParents;
  242.     }
  243.  
  244.     static Pair<Individual, Individual> mutation(Pair<Individual, Individual> parents) {
  245.  
  246.         System.out.println("----------------Mutation-------------------------");
  247.  
  248.         Individual father = parents.getKey();
  249.         Individual mother = parents.getValue();
  250.  
  251.         Supplier<Boolean> r = () -> random.nextFloat() < pro_mutation;
  252.  
  253.         for (int i = 0; i < number_of_queens; i++) {
  254.  
  255.             if (r.get()) {
  256.                 Arrays.fill(father.gene[i], false);
  257.                 father.gene[i][random.nextInt(number_of_queens)] = true;
  258.             }
  259.  
  260.         }
  261.  
  262.         for (int i = 0; i < number_of_queens; i++) {
  263.  
  264.             if (r.get()) {
  265.                 Arrays.fill(mother.gene[i], false);
  266.                 mother.gene[i][random.nextInt(number_of_queens)] = true;
  267.             }
  268.  
  269.         }
  270.  
  271.         father.number_of_attacks = number_of_attacks(father.gene);
  272.         father.fitness = fittnes(father.number_of_attacks);
  273.  
  274.         mother.number_of_attacks = number_of_attacks(mother.gene);
  275.         mother.fitness = fittnes(mother.number_of_attacks);
  276.  
  277.         return parents;
  278.     }
  279.  
  280.     static void fittest() {
  281.  
  282.         for (int i = 0; i < population.size(); i++) {
  283.             if (population.get(i).fitness == maxNumberOfClashes) {
  284.                 fittest_individuals.add(population.get(i));
  285.             }
  286.         }
  287.  
  288.     }
  289.  
  290.     static void printMatingPool(Pair<Individual, Individual> parents) {
  291.  
  292.         System.out.println("--------------------MatingPool-----------------");
  293.         System.out.println("-------------------------------Father-------------------------------");
  294.         for (boolean[] booleanses : parents.getKey().gene) {
  295.             System.out.println(Arrays.toString(booleanses));
  296.         }
  297.  
  298.         System.out.println("-------------------------------Mother-------------------------------");
  299.         for (boolean[] booleanses : parents.getValue().gene) {
  300.             System.out.println(Arrays.toString(booleanses));
  301.         }
  302.         System.out.println("-----------------------------------------------------------------");
  303.     }
  304.  
  305.     public static void main(String[] args) {
  306.  
  307.         init_population();
  308.  
  309.         fittest();
  310.  
  311.         subInterval(population);
  312.  
  313.         if (!fittest_individuals.isEmpty()) {
  314.  
  315.             fittest_individuals.forEach((ind) -> {
  316.                 for (boolean[] booleanse : ind.gene) {
  317.                     System.out.println(Arrays.toString(booleanse));
  318.                 }
  319.                 System.out.println("-------------------------------------");
  320.             });
  321.             return;
  322.         }
  323.  
  324.         int gen = 0;
  325.  
  326.         while (gen <= 90_000) {
  327.  
  328.             System.out.println("----------------Population--size:" + population.size() + "--------------------------");
  329.             //print_population();
  330.             System.out.println("-----------------------------------------");
  331.  
  332.             Pair<Individual, Individual> matingPool = selection();
  333.             //printMatingPool(matingPool);
  334.  
  335.             matingPool = crossover(matingPool);
  336.             //printMatingPool(matingPool);
  337.  
  338.             matingPool = mutation(matingPool);
  339.             //printMatingPool(matingPool);
  340.  
  341.             fittest();
  342.             subInterval(population);
  343.  
  344.             System.out.println("gen:" + gen++);
  345.  
  346.         }
  347.  
  348.         System.out.println("-----------------Fittest Individuals------------------------");
  349.  
  350.         Set<Individual> set = new HashSet<>();
  351.         set.addAll(fittest_individuals);
  352.         fittest_individuals.clear();
  353.         fittest_individuals.addAll(set);
  354.         set = null;
  355.        
  356.        
  357.         fittest_individuals.forEach((ind) -> {
  358.             for (boolean[] booleanse : ind.gene) {
  359.                 System.out.println(Arrays.toString(booleanse));
  360.             }
  361.             System.out.println("-------------------------------------");
  362.         });
  363.  
  364.         /*
  365.         boolean[][] q = {{false, false, false, false, false, false, true, false},
  366.         {false, false, false, false, true, false, false, false},
  367.         {false, false, true, false, false, false, false, false},
  368.         {true, false, false, false, false, false, false, false},
  369.         {false, false, false, false, false, true, false, false},
  370.         {false, false, false, false, false, false, false, true},
  371.         {false, true, false, false, false, false, false, false},
  372.         {false, false, false, true, false, false, false, false}};
  373.  
  374.         System.out.println(number_of_attacks(q));
  375.  
  376.        
  377.          */
  378.     }
  379.  
  380. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top