SHARE
TWEET

ga #2

a guest May 25th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. import java.util.*;
  3.  
  4. public class Main {
  5.     static int M = 2; //number of the machines
  6.     static int N; //number of the jobs excluding dummy job
  7.     static Job[] jobs;
  8.     static int machineCapacity;
  9.     static Random random = new Random();
  10.     static List<int[]> population = new ArrayList<>();
  11.     static int populationSize = 20;
  12.     static int iterations = 500;
  13.  
  14.     public static void main(String[] args) {
  15.         jobs = new Job[]{
  16.                 new Job(0, 0, 0),
  17.                 new Job(1, 3, 3),
  18.                 new Job(2, 3, 5),
  19.                 new Job(3, 5, 8),
  20.                 new Job(4, 4, 6)};
  21.         N = jobs.length - 1;//number of the jobs excluding dummy job
  22.         machineCapacity = N + 1;
  23.  
  24.         initPopulation();
  25.         int[] best = getBestChromosome();
  26.  
  27.         for (int i = 0; i < iterations; i++) {
  28.             List<int[]> newPopulation = new ArrayList<>();
  29.  
  30.             for (int j = 0; j < populationSize; j++) {
  31.                 int[] chromosome1 = tournamentSelection();
  32.                 int[] chromosome2 = tournamentSelection();
  33.  
  34.                 if (shouldCrossover()) {
  35.                     int[] child = crossover(chromosome1, chromosome2);
  36.  
  37.                     if (shouldMutateJobs())
  38.                         mutateJobs(child, jobs);
  39.  
  40.                     if (shouldMutateMachines())
  41.                         mutateMachines(child);
  42.  
  43.                     newPopulation.add(child);
  44.                 } else {
  45.                     if (shouldMutateJobs())
  46.                         mutateJobs(chromosome1, jobs);
  47.  
  48.                     if (shouldMutateMachines())
  49.                         mutateMachines(chromosome1);
  50.  
  51.                     newPopulation.add(chromosome1);
  52.                 }
  53.             }
  54.             population = newPopulation;
  55.             int[] populationBest = getBestChromosome();
  56.  
  57.             if (getMaximumLateness(populationBest) < getMaximumLateness(best)) {
  58.                 best = Arrays.copyOf(populationBest, populationBest.length);
  59.             }
  60.         }
  61.  
  62.         displayChromosome(best);
  63.         printJobs();
  64.         System.out.println(getMaximumLateness(best));
  65.     }
  66.  
  67.     static int[] tournamentSelection() {
  68.         int size = 5;
  69.         List<int[]> selected = new ArrayList<>();
  70.         for (int i = 0; i < size; i++) {
  71.             selected.add(population.get(random.nextInt(populationSize)));
  72.         }
  73.  
  74.         Collections.sort(selected, (ints, t1) -> {
  75.             int a = getMaximumLateness(ints);
  76.             int b = getMaximumLateness(t1);
  77.  
  78.             return Integer.compare(a, b);
  79.         });
  80.  
  81.         return Arrays.copyOf(selected.get(0), selected.get(0).length);
  82.     }
  83.  
  84.     static void initPopulation() {
  85.         for (int i = 0; i < populationSize; i++) {
  86.             int[] chromosome = createChromosome();
  87.             population.add(chromosome);
  88.         }
  89.     }
  90.  
  91.     static int[] getBestChromosome() {
  92.         int[] best = population.get(0);
  93.         int bestFitness = getMaximumLateness(best);
  94.         for (int[] chromosome : population) {
  95.             int fitness = getMaximumLateness(chromosome);
  96.             if (fitness < bestFitness) {
  97.                 best = chromosome;
  98.             }
  99.         }
  100.         return Arrays.copyOf(best, best.length);
  101.     }
  102.  
  103.     static void printJobs() {
  104.         for (Job job : jobs) System.out.print(job.number + " ");
  105.         System.out.println();
  106.     }
  107.  
  108.     private static int[] createChromosome() {
  109.         int[] chromosome = new int[machineCapacity * M];
  110.  
  111.         //set dummy job
  112.         for (int i = 0; i < chromosome.length; i += machineCapacity)
  113.             chromosome[i] = 1;
  114.  
  115.         //assign each job to the random machine
  116.         for (int i = 1; i <= N; i++) {
  117.             int machine = getRandomMachine();
  118.             chromosome[i + machine * machineCapacity] = 1;
  119.         }
  120.  
  121.         return chromosome;
  122.     }
  123.  
  124.     private static void displayChromosome(int[] chromosome) {
  125.         for (int i = 0; i < M; i++) {
  126.             for (int j = 0; j < machineCapacity; j++)
  127.                 System.out.print(j);
  128.  
  129.             System.out.print('|');
  130.         }
  131.         System.out.println();
  132.  
  133.         for (int i = 0; i < chromosome.length; i++) {
  134.             System.out.print(chromosome[i]);
  135.             if ((i + 1) % machineCapacity == 0 && i < chromosome.length - 1) {
  136.                 System.out.print('|');
  137.             }
  138.         }
  139.         System.out.println();
  140.     }
  141.  
  142.     private static void mutateJobs(int[] chromosome, Job[] jobs) {
  143.         //First, a machine is randomly selected then two jobs are selected at random on that
  144.         // machine and replaced with each other (i.e., they are swapped)
  145.         int machine = getRandomMachine();
  146.         int firstJobOnMachine = machine * machineCapacity + 1;
  147.  
  148.         //before swapping check if there are at least 2 jobs on machine
  149.         if (areAtLeast2JobsOnMachine(machine, chromosome)) {
  150.             int job1Index = getRandomJobNumber(firstJobOnMachine, N);
  151.             int job2Index = getRandomJobNumber(firstJobOnMachine, N);
  152.  
  153.             // (we have to swap initial jobs (change its order), because chromosome can only hold
  154.             // position info, not job values)
  155.             if (doesJobExist(chromosome, job1Index) && doesJobExist(chromosome, job2Index)) {
  156.                 int job1RealIndex = job1Index % machineCapacity;
  157.                 int job2RealIndex = job2Index % machineCapacity;
  158.  
  159.                 Job temp = jobs[job1RealIndex];
  160.                 jobs[job1RealIndex] = jobs[job2RealIndex];
  161.                 jobs[job2RealIndex] = temp;
  162.             }
  163.         }
  164.     }
  165.  
  166.     static int getRandomMachine() {
  167.         return random.nextInt(M);
  168.     }
  169.  
  170.     static int getRandomJobNumber(int begin, int range) {
  171.         return random.nextInt(range) + begin;
  172.     }
  173.  
  174.     static boolean doesJobExist(int[] chromosome, int jobNumber) {
  175.         return chromosome[jobNumber] == 1;
  176.     }
  177.  
  178.     static boolean areAtLeast2JobsOnMachine(int machine, int[] chromosome) {
  179.         int startIndex = machine * machineCapacity + 1;
  180.         int sum = 0;
  181.  
  182.         for (int i = startIndex; i < startIndex + N; i++)
  183.             if (chromosome[i] == 1) sum++;
  184.  
  185.         return sum > 1;
  186.     }
  187.  
  188.     private static void mutateMachines(int[] chromosome) {
  189.         //First, a job number is randomly selected
  190.         //ensure job is not dummy job -> start from `1` index
  191.         int jobNumber = getRandomJobNumber(1, N);
  192.  
  193.         // then two machines are selected at random.
  194.         int machine1 = getRandomMachine();
  195.         int machine2 = getRandomMachine();
  196.  
  197.         // The selected job is replaced on two machines
  198.         int machine1JobNumber = machine1 * machineCapacity + jobNumber;
  199.         int machine2JobNumber = machine2 * machineCapacity + jobNumber;
  200.  
  201.         int temp = chromosome[machine1JobNumber];
  202.         chromosome[machine1JobNumber] = chromosome[machine2JobNumber];
  203.         chromosome[machine2JobNumber] = temp;
  204.     }
  205.  
  206.     private static int[] crossover(int[] chromosome1, int[] chromosome2) {
  207.         // A random value, r, is created in the range of [1, (N+1)*M]
  208.         int r = getRandomJobNumber(1, machineCapacity * M);
  209.  
  210.         int[] child1 = Arrays.copyOf(chromosome1, chromosome1.length);
  211.         int[] child2 = Arrays.copyOf(chromosome2, chromosome2.length);
  212.  
  213.         //All digits from the first one to the r th one are replaced on two chromosomes.
  214.         for (int i = 0; i < r; i++) {
  215.             int temp = child1[0];
  216.             child1[i] = child2[i];
  217.             child2[i] = temp;
  218.         }
  219.  
  220.         // Then, both offspring are checked with the rule to create feasible chromosomes.
  221.         repair(child1);
  222.         return child1;
  223.     }
  224.  
  225.     private static void repair(int[] chromosome) {
  226.         Map<Integer, Integer> jobsOccurrence = new HashMap<>();
  227.  
  228.         //store job positions
  229.         for (int i = 0; i < machineCapacity; i++) {
  230.             jobsOccurrence.put(i, 0);
  231.         }
  232.  
  233.         //count all jobs
  234.         for (int i = 0; i < chromosome.length; i++) {
  235.             int jobPosition = i % machineCapacity;
  236.             int occurrence = jobsOccurrence.get(jobPosition);
  237.             jobsOccurrence.put(jobPosition, occurrence + chromosome[i]);
  238.         }
  239.  
  240.         for (Integer jobPosition : jobsOccurrence.keySet()) {
  241.             if (jobPosition != 0) {
  242.                 int occurrence = jobsOccurrence.get(jobPosition);
  243.                 if (occurrence < 1) {
  244.                     chromosome[jobPosition] = 1;
  245.                 }
  246.                 if (occurrence > 1) {
  247.                     boolean removed = false;
  248.                     for (int i = jobPosition; i < chromosome.length && !removed; i += machineCapacity) {
  249.                         if (chromosome[i] == 1) {
  250.                             chromosome[i] = 0;
  251.                             removed = true;
  252.                         }
  253.                     }
  254.                 }
  255.             }
  256.         }
  257.     }
  258.  
  259.     private static class Job {
  260.         int number;
  261.         int processingTime;
  262.         int deadLine;
  263.  
  264.         public Job(int number, int processingTime, int deadLine) {
  265.             this.number = number;
  266.             this.processingTime = processingTime;
  267.             this.deadLine = deadLine;
  268.         }
  269.  
  270.         public Job(Job other) {
  271.             this.number = other.number;
  272.             this.processingTime = other.processingTime;
  273.             this.deadLine = other.deadLine;
  274.         }
  275.     }
  276.  
  277.     static int getMaximumLateness(int[] chromosome) {
  278.         int maxLateness = 0;
  279.         int elapsedTime = 0;
  280.         for (int machine = 0; machine < M; machine++) {
  281.             int machineFirstJobNumber = machine * machineCapacity + 1;
  282.  
  283.             for (int i = machineFirstJobNumber; i < machineFirstJobNumber + N; i++) {
  284.                 if (chromosome[i] == 1) {
  285.                     int realJobIndex = i % machineCapacity;
  286.                     Job job = jobs[realJobIndex];
  287.  
  288.                     elapsedTime += job.processingTime;
  289.  
  290.                     int jobLateness = elapsedTime - job.deadLine;
  291.  
  292.                     maxLateness = Math.max(maxLateness, jobLateness);
  293.                 }
  294.             }
  295.             elapsedTime = 0;
  296.         }
  297.         return maxLateness;
  298.     }
  299.  
  300.     static boolean shouldCrossover() {
  301.         return random.nextDouble() <= 0.75;
  302.     }
  303.  
  304.     static boolean shouldMutateJobs() {
  305.         return random.nextDouble() <= 0.03;
  306.     }
  307.  
  308.     static boolean shouldMutateMachines() {
  309.         return random.nextDouble() <= 0.03;
  310.     }
  311. }
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
 
Top