tsp genetic

 import java.util.*;


class TravellingSalesmanGenetic {

    // Constants
    static final int POPULATION_SIZE = 100; // Size of population
    static final int NUM_GENERATIONS = 1000; // Number of generations
    static final double MUTATION_RATE = 0.05; // Mutation rate

    // Cities' coordinates (e.g., a small example for TSP)
    static final int[][] cities = {
        {0, 0}, {1, 3}, {4, 3}, {6, 1}, {3, 2}, {5, 4}, {7, 8}
    };

    public static void main(String[] args) {
        TravellingSalesmanGenetic tsp = new TravellingSalesmanGenetic();
        tsp.solveTSP(cities);
    }

    // Solve TSP using Genetic Algorithm
    public void solveTSP(int[][] cities) {
        List<int[]> population = initializePopulation(cities.length);

        for (int generation = 0; generation < NUM_GENERATIONS; generation++) {
            population = evolvePopulation(population, cities);
        }

        // After the final generation, get the best solution
        int[] bestSolution = getBestSolution(population, cities);
        System.out.println("Best Path: " + Arrays.toString(bestSolution));
        System.out.println("Total Distance: " + calculatePathLength(bestSolution, cities));
    }

    // Initialize population with random paths
    public List<int[]> initializePopulation(int numCities) {
        List<int[]> population = new ArrayList<>();
        for (int i = 0; i < POPULATION_SIZE; i++) {
            int[] path = new int[numCities];
            for (int j = 0; j < numCities; j++) {
                path[j] = j;
            }
            shuffleArray(path);
            population.add(path);
        }
        return population;
    }

    // Shuffle array to create a random path
    public void shuffleArray(int[] array) {
        Random rand = new Random();
        for (int i = 0; i < array.length; i++) {
            int randomIndex = rand.nextInt(array.length);
            int temp = array[i];
            array[i] = array[randomIndex];
            array[randomIndex] = temp;
        }
    }

    // Evolve population through selection, crossover, and mutation
    public List<int[]> evolvePopulation(List<int[]> population, int[][] cities) {
        List<int[]> newPopulation = new ArrayList<>();

        // Selection: select best individuals (elitism) and add them to the new population
        Collections.sort(population, (a, b) -> Integer.compare(calculatePathLength(a, cities), calculatePathLength(b, cities)));
        for (int i = 0; i < POPULATION_SIZE / 2; i++) {
            newPopulation.add(population.get(i)); // Keep the top half
        }

        // Crossover: Generate offspring from selected parents
        while (newPopulation.size() < POPULATION_SIZE) {
            int[] parent1 = newPopulation.get(new Random().nextInt(POPULATION_SIZE / 2));
            int[] parent2 = newPopulation.get(new Random().nextInt(POPULATION_SIZE / 2));
            int[] child = crossover(parent1, parent2);
            newPopulation.add(child);
        }

        // Mutation: Apply random mutation
        for (int i = 0; i < newPopulation.size(); i++) {
            if (Math.random() < MUTATION_RATE) {
                mutate(newPopulation.get(i));
            }
        }

        return newPopulation;
    }

    // Crossover between two parents to generate a child
    public int[] crossover(int[] parent1, int[] parent2) {
        int[] child = new int[parent1.length];
        Set<Integer> visited = new HashSet<>();
       
        // Start by taking a random segment from parent1
        int crossoverPoint1 = new Random().nextInt(parent1.length);
        int crossoverPoint2 = new Random().nextInt(parent1.length);

        if (crossoverPoint1 > crossoverPoint2) {
            int temp = crossoverPoint1;
            crossoverPoint1 = crossoverPoint2;
            crossoverPoint2 = temp;
        }

        // Copy a segment from parent1
        for (int i = crossoverPoint1; i <= crossoverPoint2; i++) {
            child[i] = parent1[i];
            visited.add(parent1[i]);
        }

        // Fill the rest of the child from parent2
        int currentIndex = 0;
        for (int i = 0; i < parent2.length; i++) {
            if (!visited.contains(parent2[i])) {
                while (child[currentIndex] != 0) {
                    currentIndex++;
                }
                child[currentIndex++] = parent2[i];
            }
        }

        return child;
    }

    // Mutation by swapping two cities in the path
    public void mutate(int[] path) {
        Random rand = new Random();
        int i = rand.nextInt(path.length);
        int j = rand.nextInt(path.length);
        int temp = path[i];
        path[i] = path[j];
        path[j] = temp;
    }

    // Get the best solution from the population
    public int[] getBestSolution(List<int[]> population, int[][] cities) {
        int[] bestSolution = null;
        int bestCost = Integer.MAX_VALUE;

        for (int[] path : population) {
            int cost = calculatePathLength(path, cities);
            if (cost < bestCost) {
                bestCost = cost;
                bestSolution = path;
            }
        }

        return bestSolution;
    }

    // Calculate the total distance of a path
    public int calculatePathLength(int[] path, int[][] cities) {
        int totalDistance = 0;
        for (int i = 0; i < path.length - 1; i++) {
            int cityA = path[i];
            int cityB = path[i + 1];
            totalDistance += calculateDistance(cities[cityA], cities[cityB]);
        }
        totalDistance += calculateDistance(cities[path[path.length - 1]], cities[path[0]]); // Return to start
        return totalDistance;
    }

    // Calculate the Euclidean distance between two cities
    public int calculateDistance(int[] cityA, int[] cityB) {
        int xDistance = cityA[0] - cityB[0];
        int yDistance = cityA[1] - cityB[1];
        return (int) Math.sqrt(xDistance * xDistance + yDistance * yDistance);
    }
}

Comments

Post a Comment

Popular posts from this blog

q3part b

  import java . util . Random ; public class TSPMutation {     public static void main( String [] args ) {         // Example cities (0, 1, 2, 3, 4)         int [] chromosome = { 0 , 1 , 2 , 3 , 4 }; // A possible solution (tour)                 System .out.println( "Original Chromosome:" );         printChromosome(chromosome);                 // Apply Mutation (Swap two cities in the path)         mutate(chromosome);                 System .out.println( "Mutated Chromosome:" );         printChromosome(chromosome);     }     // Mutation function: Swap two cities' positions     public static void mutate( int [] chromosome ) {         Random rand = new Random();           ...
Read more

Literal table

 #code import java.util.*; class Literal {     String value;     int address;     public Literal(String value) {         this.value = value;         this.address = -1; // not assigned yet     } } public class Ass2{     // Check if a literal already exists in the list     public static boolean literalExists(List<Literal> list, String value) {         for (Literal l : list) {             if (l.value.equals(value)) return true;         }         return false;     }     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         List<String> code = new ArrayList<>();         List<Literal> literalTable = new ArrayList<>();         Lis...
Read more

quicksort 1

 import java.util.Random; public class QuicksortExample {     public static void main(String[] args) {         int N = 500; // Number of elements to sort         // Initialize an array of random integers         int[] arr = new int[N];         Random rand = new Random();         for (int i = 0; i < N; i++) {             arr[i] = rand.nextInt(1000); // Random integers between 0 and 999         }         // Displaying the unsorted array (optional)         System.out.println("Unsorted array:");         printArray(arr);         // Start measuring time         long startTime = System.nanoTime();         // Call the quicksort method         quicksort(arr, 0, N - 1);       ...
Read more