Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package javaGenetyczny;
- import java.io.File;
- import java.lang.reflect.Array;
- import java.util.Scanner;
- import java.util.stream.Collector;
- import java.util.stream.Collectors;
- import javax.jws.Oneway;
- import javax.swing.plaf.metal.MetalIconFactory.FolderIcon16;
- import java.util.Collections;
- import java.util.HashMap;
- import java.util.List;
- import java.util.Map.Entry;
- import java.util.Random;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.Collection;
- public class Main {
- private static final int NUMBER_OF_ITERATIONS = 400000;
- private static final int NUMBER_OF_TOURISTS = 20;
- public static void main(String[] args) throws Exception {
- String fileName = "berlin52.txt";
- String logRecord;
- File dataFile = new File(fileName);
- String[] splitLine = null;
- Scanner scanner = new Scanner(dataFile);
- int rowSize = Integer.valueOf(scanner.nextLine()); // pierwsza linia
- // wczytanego
- // dokumentu (ilosc
- // wierszy w pliku)
- int[][] tab = new int[rowSize][rowSize];
- int[][] tourist = new int[NUMBER_OF_TOURISTS][rowSize];
- int[] distance = new int[NUMBER_OF_TOURISTS];
- shuffleArrayList(rowSize, tourist);
- int i = 0;
- while (scanner.hasNextLine()) {
- logRecord = scanner.nextLine();
- splitLine = logRecord.split("\\s");
- for (int j = 0; j < splitLine.length; j++) {
- if (!"0".equals(splitLine[j])) {
- tab[i][j] = Integer.valueOf(splitLine[j]);
- tab[j][i] = Integer.valueOf(splitLine[j]);
- }
- }
- i++;
- }
- // ---------------------------------------------------------------------------------------------------------------------------------------
- for (int d = 0; d < NUMBER_OF_TOURISTS; d++) {
- System.out.printf("Wiersz %2d. ", d + 1); // numerowanie wierszy
- for (int j = 0; j < rowSize; j++) {
- System.out.printf("%5d", tourist[d][j]); // wypisanie
- // pojedynczego
- // miasta
- // (dlugosci)???
- }
- distance[d] = countDistance(tab, tourist[d]);
- System.out.printf(" :: %s ", distance[d]);
- System.out.println();
- }
- System.out.println("\nOceny: ");
- for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {
- System.out.printf("%5d ", distance[j]);
- }
- System.out.println("\n");
- System.out.println("Najkrótsza route: " + getMin(distance) + "\n\n");
- // ----------------------------------------------------------------------------------------------------------
- // ----------------------------------------------------------------------------------------------------------
- int[][] touristTMP = tourist;
- int tmpdistance = Integer.MAX_VALUE;
- int[] selectionIndex = new int[NUMBER_OF_TOURISTS];
- for (int k = 0; k < NUMBER_OF_ITERATIONS; k++) {
- /* if (k < 100000) {
- selectionIndex = competitionSelection(distance);
- } else if(k<150000) {
- selectionIndex = rouletteSelection(distance);
- } else if(k<200000){
- selectionIndex = competitionSelection(distance);
- } else if(k<250000) {
- selectionIndex = rouletteSelection(distance);
- }
- else if(k<300000){
- selectionIndex = competitionSelection(distance);
- }
- else if(k<350000){
- selectionIndex = rouletteSelection(distance);
- }*/
- if(k%20000<10000){
- selectionIndex = competitionSelection(distance);
- System.out.println("Turniej");
- } else {
- selectionIndex = rouletteSelection(distance);
- System.out.println("Ruletka");
- }
- //selectionIndex = competitionSelection(distance);
- //selectionIndex = rouletteSelection(distance);
- System.out.printf("\nIteracja: "+(k+1)+" ::: ");
- for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {
- System.out.printf("%5d", selectionIndex[j]);
- }
- System.out.println();
- int[][] touristChild = new int[NUMBER_OF_TOURISTS][rowSize];
- touristChild = crossOver(selectionIndex, touristChild, touristTMP); /// mamy
- /// pokrzyzowana
- /// populacje
- /// (wynik
- /// tablica[][])
- touristChild = mutation(selectionIndex, touristChild);
- for (int d = 0; d < NUMBER_OF_TOURISTS; d++) {
- distance[d] = countDistance(tab, touristChild[d]);
- }
- if (getMin(distance) < tmpdistance) {
- tmpdistance = getMin(distance);
- }
- touristTMP = touristChild;
- System.out.println("Iteracja: "+(k+1)+" -> Najkrótsza trasa: " +
- tmpdistance + "\n\n");
- }
- }
- // --------------------------METODY----------------------------------------
- private static void printMultiArr(int[][] crossOverArr) {
- for (int[] val : crossOverArr) {
- for (int v : val) {
- System.out.print(v + " ");
- }
- System.out.println();
- }
- }
- // Mieszanie wartości w tablicy
- private static void shuffleArrayList(int rowSize, int[][] tourist) {
- for (int i = 0; i < tourist.length; i++) {
- ArrayList<Integer> numbers = new ArrayList<>();
- for (int q = 0; q < rowSize; q++) {
- numbers.add(q + 1);
- }
- Collections.shuffle(numbers);
- for (int j = 0; j < rowSize; j++) {
- tourist[i][j] = numbers.get(j);
- }
- }
- }
- // Znajdź min z tablicy[]
- public static int getMin(int[] inputArray) {
- int minValue = inputArray[0];
- for (int i = 1; i < inputArray.length; i++) {
- if (inputArray[i] < minValue) {
- minValue = inputArray[i];
- }
- }
- return minValue;
- }
- public static int getMax(int[] inputArray) {
- int maxValue = inputArray[0];
- for (int i = 1; i < inputArray.length; i++) {
- if (inputArray[i] > maxValue) {
- maxValue = inputArray[i];
- }
- }
- return maxValue;
- }
- // Licz distans
- private static int countDistance(int[][] tab, int[] user) {
- int route = 0;
- int a, b;
- for (int i = 0; i < user.length; i++) {
- a = user[i];
- if (i == (user.length - 1)) {
- b = user[0];
- } else {
- b = user[i + 1];
- }
- route += tab[a - 1][b - 1];
- }
- return route;
- }
- private static int[] competitionSelection(int distance[]) {
- Random r = new Random();
- int k = 4; // skacz co dwie oceny
- int[] competitionIndexes = new int[NUMBER_OF_TOURISTS];
- for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {
- int distanceMin = Integer.MAX_VALUE; // największa możliwa wartość,
- // zamiast tego 9999
- int indexMin = -1; // -1 b ona pewno go nie ma, deklaracja
- for (int i = 0; i < k; i++) {
- int randIndeks = r.nextInt(NUMBER_OF_TOURISTS);
- if (distance[randIndeks] < distanceMin) {
- indexMin = randIndeks;
- distanceMin = distance[randIndeks];
- }
- }
- competitionIndexes[j] = indexMin;
- }
- return competitionIndexes;
- }
- // ----------------------Koło ruletki----------------------
- private static int[] rouletteSelection(int distance[]) {
- int max = getMax(distance);
- int[] tmpDistance = new int[NUMBER_OF_TOURISTS];
- for (int i = 0; i < distance.length; i++) {
- tmpDistance[i] = max + 1 - distance[i];
- }
- int propabilitySum = 0;
- for (int i = 0; i < tmpDistance.length; i++) {
- propabilitySum += tmpDistance[i];
- }
- int[] rouletteIndexes = new int[NUMBER_OF_TOURISTS];
- Random r = new Random();
- for (int i = 0; i < NUMBER_OF_TOURISTS; i++) {
- int numberRand = r.nextInt(propabilitySum);
- int j = 0;
- while (numberRand > 0) {
- numberRand = numberRand - tmpDistance[j];
- j++;
- if(j==20){
- j=j-1;
- }
- }
- rouletteIndexes[i] = j;
- }
- return rouletteIndexes;
- }
- // ----------------------Krzyżowanie----------------------
- // indexOf
- private static int indeksOf(int[] tab, int el) {
- for (int i = 0; i < tab.length; i++) {
- if (tab[i] == el)
- return i;
- }
- return -1;
- }
- // Krzyzowanie
- private static int[][] crossOver(int[] selectionIndex, int[][] touristChild, int[][] tourist) {
- Random rand = new Random();
- int crossOverPropability = 100;
- if(rand.nextInt(1000) < crossOverPropability){
- for (int i = 0; i < selectionIndex.length; i += 2) {
- int p1 = selectionIndex[i];
- int p2 = selectionIndex[i + 1];
- Random r = new Random();
- int cross1 = r.nextInt(tourist[0].length - 3) + 1;
- int cross2 = r.nextInt(tourist[0].length - 1 - cross1) + cross1 + 1;
- // zamiana środka
- for (int j = cross1; j <= cross2; j++) {
- touristChild[i][j] = tourist[p1][j];
- touristChild[i + 1][j] = tourist[p2][j];
- }
- // krzyżowanie PMX
- for (int j = 0; j < cross1; j++) {
- int city1 = tourist[p2][j];
- int ind;
- // zamiana nieistniejących środka
- while ((ind = indeksOf(touristChild[i], city1)) != -1) {
- city1 = tourist[p2][ind];
- }
- touristChild[i][j] = city1;
- }
- for (int j = cross2 + 1; j < tourist[0].length; j++) {
- int city1 = tourist[p2][j];
- int ind;
- // zamiana nieistniejących środka
- while ((ind = indeksOf(touristChild[i], city1)) != -1) {
- city1 = tourist[p2][ind];
- }
- touristChild[i][j] = city1;
- }
- for (int j = 0; j < cross1; j++) {
- int city1 = tourist[p1][j];
- int ind;
- // zamiana nieistniejących środka
- while ((ind = indeksOf(touristChild[i + 1], city1)) != -1) {
- city1 = tourist[p1][ind];
- }
- touristChild[i + 1][j] = city1;
- }
- for (int j = cross2 + 1; j < tourist[0].length; j++) {
- int city1 = tourist[p1][j];
- int ind;
- // zamiana nieistniejących środka
- while ((ind = indeksOf(touristChild[i + 1], city1)) != -1) {
- city1 = tourist[p1][ind];
- }
- touristChild[i + 1][j] = city1;
- }
- }
- }
- return touristChild;
- }
- // mutation
- private static int[][] mutation(int[] selectionIndex, int[][] touristChild) {
- int mutationPropability = 35;
- Random rand = new Random();
- if(rand.nextInt(1000) < mutationPropability){
- // losowanie przeciec
- int cross1 = 0;
- int cross2 = 0;
- for (int i = 0; i < selectionIndex.length; i++) {
- Random r = new Random();
- cross1 = r.nextInt(touristChild[0].length - 3) + 1;
- cross2 = r.nextInt(touristChild[0].length - 1 - cross1) + cross1 + 1;
- ArrayList<Integer> touristChildTmpCenterPart = new ArrayList<>();
- // przypisujemy srodek z touristCHild
- for (int j = cross1; j <= cross2; j++) {
- touristChildTmpCenterPart.add(touristChild[i][j]);
- }
- Collections.reverse(touristChildTmpCenterPart);
- int tmpIndex = 0;
- for (int j = cross1; j <= cross2; j++) {
- touristChild[i][j] = touristChildTmpCenterPart.get(tmpIndex);
- tmpIndex++;
- }
- }
- }
- return touristChild;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement