JAVA

package com.company;

import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;

public class Main {

    public static void main(String[] args) {

        //region variables
        // iteration variables
        int i, j, g;

        //main variables
        int[][] population, arrayOfDistance;
        int numberOfCities, numberOfSubjects = 40, numberOfLoopTimes = 100000, numberOfGroupMemberOfTournament = 4, numberOfFinal = 1;
        int pmxProbability = 80, inversionMutationProbability = 5, swapMutationProbability = 993;

        //various additional variables
        Boolean whichSelection = true; //true - tournament, false - roulette
        Scanner s = null; //variable to scan file
        String line; //variable to readLine
        String[] lineArray; //array variable to line.split
        Random rnd = new Random();
        long startTime, stopTime;

        //file variable
        File file = new File("berlin52.txt");
        // URL url = new URL("http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/berlin52.tsp");

        //endregion

        //region checking if file exists
        {
            if (!file.exists()) {
                System.out.println("There is no file with name: '" + file.getName() + "'.");
                return;
            }
        }
        //endregion

        //region main program
        for (int z = 0; z < numberOfFinal; z++) {
            startTime = System.currentTimeMillis();
            try {
                //region open a file
                //s = new Scanner(url.openStream());
                s = new Scanner(file);
                line = s.nextLine();
                numberOfCities = Integer.parseInt(line);
                arrayOfDistance = new int[numberOfCities][numberOfCities];

                for (i = 0; i < numberOfCities; i++) {
                    line = s.nextLine();
                    lineArray = line.split(" ");
                    for (j = 0; j < lineArray.length; j++) {
                        arrayOfDistance[i][j] = Integer.parseInt(lineArray[j]);
                        arrayOfDistance[j][i] = Integer.parseInt(lineArray[j]);
                    }
                }
                //endregion

                //region creating a population
                population = createPopulation(numberOfCities, numberOfSubjects);
                //endregion

                System.out.println("Calculating...");

                //region tournament/roulette + crossing + mutation
                for (g = 0; g < numberOfLoopTimes; g++) {
                    //region tournament or roulette
                    int[] bestSubjectsIndex = new int[population.length];

                    if (whichSelection) {

                        //region tournament
                        int[] tournamentSubjectGroup = new int[numberOfGroupMemberOfTournament];
                        int minSubjectIndex, minSubjectLength;

                        for (i = 0; i < population.length; i++) {
                            tournamentSubjectGroup = returnOneTournamentGroup(numberOfSubjects, numberOfGroupMemberOfTournament);
                            minSubjectIndex = -1;
                            minSubjectLength = Integer.MAX_VALUE;
                            for (j = 0; j < tournamentSubjectGroup.length; j++) {
                                if (returnOneSubjectLength(population[tournamentSubjectGroup[j]], arrayOfDistance) < minSubjectLength) {
                                    minSubjectLength = returnOneSubjectLength(population[tournamentSubjectGroup[j]], arrayOfDistance);
                                    minSubjectIndex = tournamentSubjectGroup[j];
                                }
                            }
                            bestSubjectsIndex[i] = minSubjectIndex;
                        }


                        //endregion

                        //region print best subject after tournament
//                    for (int x = 0; x < population.length; x++) {
//                        printOneSubject(population, bestSubjectsIndex[x]);
//                    }
//                    System.out.println();
                        //endregion

                    } else {

                        //region roulette
                        int worstSubjectLength = returnWorstSubjectLength(population, arrayOfDistance);
                        int[] subjectsGrades = new int[population.length];
                        int sumOfAllGrades = 0, tempSum, tempIndex, randomNumberForGrade;
                        for (i = 0; i < population.length; i++) {
                            subjectsGrades[i] = worstSubjectLength + 1 - returnOneSubjectLength(population[i], arrayOfDistance);
                            sumOfAllGrades += subjectsGrades[i];
                        }

                        for (i = 0; i < bestSubjectsIndex.length; i++) {
                            randomNumberForGrade = rnd.nextInt(sumOfAllGrades);
                            tempSum = 0;
                            tempIndex = 0;
                            tempSum += subjectsGrades[tempIndex];
                            while (tempSum <= randomNumberForGrade) {
                                tempIndex++;
                                tempSum += subjectsGrades[tempIndex];
                            }
                            bestSubjectsIndex[i] = tempIndex;
                        }

                        //endregion

                        //region print best subject after roulette
//                    for (int x = 0; x < population.length; x++) {
//                        printOneSubject(population, bestSubjectsIndex[x]);
//                    }
//                    System.out.println();
                        //endregion

                    }
                    //endregion

                    //region update population
                    int[][] tempPopulation = new int[numberOfSubjects][numberOfCities];
                    for (i = 0; i < tempPopulation.length; i++) {
                        for (j = 0; j < tempPopulation[i].length; j++) {
                            tempPopulation[i][j] = population[bestSubjectsIndex[i]][j];
                        }
                    }
                    population = returnArray1toArray2(tempPopulation);
                    //endregion

                    //region crossing
                    int startRandomPMX, stopRandomPMX, tempCityPMX, tempIndexPMX;
                    int[] childX1 = new int[numberOfCities], childX2 = new int[numberOfCities];

                    if (rnd.nextInt(100) < pmxProbability) {
                        for (i = 0; i < population.length; i += 2) {
                            startRandomPMX = rnd.nextInt(numberOfCities);
                            stopRandomPMX = rnd.nextInt(numberOfCities - startRandomPMX) + startRandomPMX;

                            //region fill childs with -1
                            Arrays.fill(childX1, -1);
                            Arrays.fill(childX2, -1);
                            //endregion

                            //region fill random range with original value of population
                            for (j = startRandomPMX; j <= stopRandomPMX; j++) {
                                childX1[j] = population[i][j];
                                childX2[j] = population[i + 1][j];
                            }
                            //endregion

                            //region child 1

                            //region from 0 to start
                            for (j = 0; j < startRandomPMX; j++) {
                                tempCityPMX = population[i + 1][j];
                                tempIndexPMX = returnIndex(childX1, tempCityPMX);
                                while (tempIndexPMX != -1) {
                                    tempCityPMX = population[i + 1][tempIndexPMX];
                                    tempIndexPMX = returnIndex(childX1, tempCityPMX);
                                }
                                childX1[j] = tempCityPMX;
                            }
                            //endregion

                            //region from stop to end
                            for (j = stopRandomPMX + 1; j < childX1.length; j++) {
                                tempCityPMX = population[i + 1][j];
                                tempIndexPMX = returnIndex(childX1, tempCityPMX);
                                while (tempIndexPMX != -1) {
                                    tempCityPMX = population[i + 1][tempIndexPMX];
                                    tempIndexPMX = returnIndex(childX1, tempCityPMX);
                                }
                                childX1[j] = tempCityPMX;
                            }
                            //endregion

                            //endregion

                            //region child 2

                            //region from 0 to start
                            for (j = 0; j < startRandomPMX; j++) {
                                tempCityPMX = population[i][j];
                                tempIndexPMX = returnIndex(childX2, tempCityPMX);
                                while (tempIndexPMX != -1) {
                                    tempCityPMX = population[i][tempIndexPMX];
                                    tempIndexPMX = returnIndex(childX2, tempCityPMX);
                                }
                                childX2[j] = tempCityPMX;
                            }
                            //endregion

                            //region from stop to end
                            for (j = stopRandomPMX + 1; j < childX1.length; j++) {
                                tempCityPMX = population[i][j];
                                tempIndexPMX = returnIndex(childX2, tempCityPMX);
                                while (tempIndexPMX != -1) {
                                    tempCityPMX = population[i][tempIndexPMX];
                                    tempIndexPMX = returnIndex(childX2, tempCityPMX);
                                }
                                childX2[j] = tempCityPMX;
                            }
                            //endregion

                            //endregion

                            //region update population
                            for (j = 0; j < population[i].length; j++) {
                                population[i][j] = childX1[j];
                                population[i + 1][j] = childX2[j];
                            }
                            //endregion

                        }
                    }
                    //endregion

                    //region mutation inverse
                    int chanceOfMutation, startMutation, stopMutation;
                    for (i = 0; i < population.length; i++) {
                        chanceOfMutation = rnd.nextInt(100);
                        if (chanceOfMutation < inversionMutationProbability) {
                            startMutation = rnd.nextInt(population[i].length);
                            stopMutation = rnd.nextInt(population[i].length - startMutation) + startMutation;
                            int[] tempArray = new int[stopMutation - startMutation];
                            for (j = 0; j < tempArray.length; j++) {
                                tempArray[j] = population[i][startMutation + j];
                            }
                            tempArray = reverseArray(tempArray);
                            for (j = 0; j < tempArray.length; j++) {
                                population[i][startMutation + j] = tempArray[j];
                            }
                        }
                    }
                    //endregion

                    //region mutation swap
//                    int chanceOfMutation, tempCityMutation, tempRandomCityMutation;
//                    for (i = 0; i < population.length; i++) {
//                        for (j = 0; j < population[i].length; j++) {
//                            chanceOfMutation = rnd.nextInt(1000);
//                            if (chanceOfMutation > swapMutationProbability) {
//                                tempRandomCityMutation = rnd.nextInt(population[i].length);
//                                while (tempRandomCityMutation == j) {
//                                    tempRandomCityMutation = rnd.nextInt(population[i].length);
//                                }
//                                tempCityMutation = population[i][j];
//                                population[i][j] = population[i][tempRandomCityMutation];
//                                population[i][tempRandomCityMutation] = tempCityMutation;
//                            }
//                        }
//                    }
                    //endregion
                }
                //endregion

                printBestSubjectLength(population, arrayOfDistance);

                printToFile(population,arrayOfDistance, "wynik.txt");
                //printWorstSubjectLength(population, arrayOfDistance);
            } catch (IOException io) {
                System.out.println("blad bliku");
            } finally {
                if (s != null)
                    s.close();
            }
            stopTime = System.currentTimeMillis();
            System.out.printf("Time: %6d", (stopTime-startTime));
            System.out.println();
        }
        //endregion
    }

    //return statement methods
    private static int[][] createPopulation(int tempNumberOfCities, int tempNrSubjects) {
        //creating population
        int[][] tempPopulation = new int[tempNrSubjects][tempNumberOfCities];
        Random rnd = new Random();
        int j, tempRandomSubject;
        List<Integer> tempCities = new ArrayList<Integer>();
        for (int i = 0; i < tempNrSubjects; i++) {
            for (j = 0; j < tempNumberOfCities; j++)
                tempCities.add(j);
            for (j = 0; j < tempNumberOfCities; j++) {
                tempRandomSubject = rnd.nextInt(tempCities.size());
                tempPopulation[i][j] = tempCities.get(tempRandomSubject);
                tempCities.remove(tempRandomSubject);
            }
        }
        return tempPopulation;

//        for (int i = 0; i < nrSubjects; i++) {
//            for (j = 0; j < nrCities; j++)
//                subjectBoolean[i] = true;
//            for (j = 0; j < nrCities; j++) {
//                randomSubject=rnd.nextInt(nrCities);
//                if (subjectBoolean[randomSubject]) {
//                    population[i][j] = randomSubject;
//                    subjectBoolean[randomSubject] = false;
//                } else {
//                    do {
//                        randomSubject = rnd.nextInt(nrCities);
//                    } while (!subjectBoolean[randomSubject]);
//                    population[i][j] = randomSubject;
//                    subjectBoolean[randomSubject] = false;
//                }
//
//            }
//        }

    }

    private static int returnOneSubjectLength(int[] tempSubject, int[][] tempArrayOfDistance) {
        int tempSubjectLength = 0;
        for (int j = 0; j < tempSubject.length - 1; j++) {
            tempSubjectLength += tempArrayOfDistance[tempSubject[j]][tempSubject[j + 1]];
        }
        tempSubjectLength += tempArrayOfDistance[tempSubject[0]][tempSubject[tempSubject.length - 1]];
        return tempSubjectLength;
    }

    private static int returnBestSubjectLength(int[][] tempPopulation, int[][] tempArrayOfDistance) {
        int tempBestSubjectLength = Integer.MAX_VALUE;
        for (int i = 0; i < tempPopulation.length; i++) {
            if (returnOneSubjectLength(tempPopulation[i], tempArrayOfDistance) < tempBestSubjectLength)
                tempBestSubjectLength = returnOneSubjectLength(tempPopulation[i], tempArrayOfDistance);
        }
        return tempBestSubjectLength;
    }

    private static int returnWorstSubjectLength(int[][] tempPopulation, int[][] tempArrayOfDistance) {
        int tempWorstSubjectLength = Integer.MIN_VALUE;
        for (int i = 0; i < tempPopulation.length; i++) {
            if (returnOneSubjectLength(tempPopulation[i], tempArrayOfDistance) > tempWorstSubjectLength)
                tempWorstSubjectLength = returnOneSubjectLength(tempPopulation[i], tempArrayOfDistance);
        }
        return tempWorstSubjectLength;
    }

    private static int[] returnOneTournamentGroup(int tempNumberOfSubjects, int tempNumberOfTournamentGroupMember) {
        int[] tempGroup = new int[tempNumberOfTournamentGroupMember];
        int tempRandomSubject;
        Random rnd = new Random();
        List<Integer> tempSubjects = new ArrayList<Integer>();

        for (int j = 0; j < tempNumberOfSubjects; j++)
            tempSubjects.add(j);
        for (int j = 0; j < tempNumberOfTournamentGroupMember; j++) {
            tempRandomSubject = rnd.nextInt(tempSubjects.size());
            tempGroup[j] = tempSubjects.get(tempRandomSubject);
            tempSubjects.remove(tempRandomSubject);
        }
        return tempGroup;
    }

    private static int returnIndex(int[] tempChild, int tempCity) {
        for (int i = 0; i < tempChild.length; i++)
            if (tempChild[i] == tempCity) return i;
        return -1;
    }

    private static int[][] returnArray1toArray2(int[][] tempArray) {
        int[][] tempFinalArray = new int[tempArray.length][tempArray[0].length];
        for (int i = 0; i < tempArray.length; i++) {
            for (int j = 0; j < tempArray[i].length; j++) {
                tempFinalArray[i][j] = tempArray[i][j];
            }
        }
        return tempFinalArray;
    }

    private static int[] reverseArray(int[] tempArray) {
        int[] tempReverseArray = new int[tempArray.length];
        for (int i = 0; i < tempArray.length / 2; i++) {
            int temp = tempArray[i];
            tempArray[i] = tempArray[tempArray.length - i - 1];
            tempArray[tempArray.length - i - 1] = temp;
        }
        for (int i = 0; i < tempArray.length; i++) {
            tempReverseArray[i] = tempArray[i];
        }
        return tempReverseArray;
    }

    //print methods
    private static void printOneDimensionArray(int[] tempArray, Boolean oneLine) {
        //printing array with formatting
        for (int i = 0; i < tempArray.length; i++) {
            System.out.printf("%6d", tempArray[i]);
            if (!oneLine) System.out.println();
        }
        System.out.println();
    }

    private static void printTwoDimensionArray(int[][] tempArray) {
        //printing array with formatting
        for (int i = 0; i < tempArray.length; i++) {
            for (int j = 0; j < tempArray[i].length; j++) {
                System.out.printf("%6d", tempArray[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }  // print all subjects

    private static void printOneSubject(int[][] tempPopulation, int tempIndex) {

        for (int i = 0; i < tempPopulation[tempIndex].length; i++) {
            System.out.printf("%6d", tempPopulation[tempIndex][i]);
        }
        System.out.println();
    }

    private static void printOneSubjectLength(int[] tempSubject, int[][] tempArrayOfDistance) {
        System.out.println("Length of the subject: " + returnOneSubjectLength(tempSubject, tempArrayOfDistance));
        System.out.println();
    }

    private static void printSubjectsLength(int[][] tempPopulation, int[][] tempArrayOfDistance) {
        for (int i = 0; i < tempPopulation.length; i++) {
            System.out.println(i + ". " + returnOneSubjectLength(tempPopulation[i], tempArrayOfDistance));
        }
        System.out.println();
    }

    private static void printBestSubjectLength(int[][] tempPopulation, int[][] tempArrayOfDistance) {
        System.out.println("Best subject length: " + returnBestSubjectLength(tempPopulation, tempArrayOfDistance));
    }

    private static void printWorstSubjectLength(int[][] tempPopulation, int[][] tempArrayOfDistance) {
        System.out.println("Worst subject length: " + returnWorstSubjectLength(tempPopulation, tempArrayOfDistance));
    }

    private static void printToFile(int[][] tempPopulation, int[][] tempArrayOfDistance, String fileName) {
        PrintWriter tempFile = null;
        try {
            tempFile = new PrintWriter(fileName);
            for (int i = 0; i < tempPopulation.length; i++) {
                for (int j = 0; j < tempPopulation[i].length; j++) {
                    if (j == (tempPopulation[i].length - 1))
                        tempFile.printf("%d", tempPopulation[i][j]);
                    else
                        tempFile.printf("%d-", tempPopulation[i][j]);

                }
                tempFile.println(" " + returnOneSubjectLength(tempPopulation[i], tempArrayOfDistance));
            }
        } catch (IOException io) {
            System.out.println("blad");
        } finally {
            if (tempFile != null)
                tempFile.close();
        }
    }



}