Untitled

import java.util.*;

class City {
    private int x;
    private int y;
    
    public City(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public double distanceTo(City other) {
        int dx = x - other.x;
        int dy = y - other.y;
        return Math.sqrt(dx*dx + dy*dy);
    }
    
    public int getX() { return x; }
    public int getY() { return y; }
}

class Route {
    private List<City> cities;
    private double fitness;
    private double distance;
    
    public Route(List<City> cities) {
        this.cities = new ArrayList<>(cities);
        calculateFitness();
    }
    
    private void calculateFitness() {
        distance = 0;
        for (int i = 0; i < cities.size() - 1; i++) {
            distance += cities.get(i).distanceTo(cities.get(i + 1));
        }
        distance += cities.get(cities.size()-1).distanceTo(cities.get(0));
        fitness = 1 / distance;
    }
    
    public double getFitness() { return fitness; }
    public double getDistance() { return distance; }
    public City getCity(int index) { return cities.get(index); }
    public void setCity(int index, City city) {
        cities.set(index, city);
        calculateFitness();
    }
    public int routeSize() { return cities.size(); }
}

class Population {
    private List<Route> routes;
    
    public Population(int populationSize, List<City> cities) {
        routes = new ArrayList<>(populationSize);
        for (int i = 0; i < populationSize; i++) {
            List<City> shuffledCities = new ArrayList<>(cities);
            Collections.shuffle(shuffledCities);
            routes.add(new Route(shuffledCities));
        }
    }
    
    public Route getRoute(int index) { return routes.get(index); }
    
    public void saveFittest(Route route) {
        int worstIndex = 0;
        double worstFitness = routes.get(0).getFitness();
        
        for (int i = 1; i < routes.size(); i++) {
            if (routes.get(i).getFitness() < worstFitness) {
                worstFitness = routes.get(i).getFitness();
                worstIndex = i;
            }
        }
        
        if (route.getFitness() > worstFitness) {
            routes.set(worstIndex, route);
        }
    }
    
    public int populationSize() { return routes.size(); }
}

class GeneticAlgorithm {
    private double mutationRate;
    private int tournamentSize;
    private Random random;
    
    public GeneticAlgorithm(double mutationRate, int tournamentSize) {
        this.mutationRate = mutationRate;
        this.tournamentSize = tournamentSize;
        this.random = new Random();
    }
    
    public Population evolvePopulation(Population pop) {
        Population newPopulation = new Population(pop.populationSize(), new ArrayList<>());
        
        for (int i = 0; i < pop.populationSize(); i++) {
            Route parent1 = tournamentSelection(pop);
            Route parent2 = tournamentSelection(pop);
            Route child = crossover(parent1, parent2);
            mutate(child);
            newPopulation.saveFittest(child);
        }
        
        return newPopulation;
    }
    
    private Route crossover(Route parent1, Route parent2) {
        List<City> childCities = new ArrayList<>(Collections.nCopies(parent1.routeSize(), null));
        
        int startPos = random.nextInt(parent1.routeSize());
        int endPos = random.nextInt(parent1.routeSize());
        
        for (int i = 0; i < parent1.routeSize(); i++) {
            if (startPos < endPos && i > startPos && i < endPos) {
                childCities.set(i, parent1.getCity(i));
            }
            else if (startPos > endPos) {
                if (!(i < startPos && i > endPos)) {
                    childCities.set(i, parent1.getCity(i));
                }
            }
        }
        
        for (int i = 0; i < parent2.routeSize(); i++) {
            if (!childCities.contains(parent2.getCity(i))) {
                for (int j = 0; j < childCities.size(); j++) {
                    if (childCities.get(j) == null) {
                        childCities.set(j, parent2.getCity(i));
                        break;
                    }
                }
            }
        }
        
        return new Route(childCities);
    }
    
    private void mutate(Route route) {
        for (int pos1 = 0; pos1 < route.routeSize(); pos1++) {
            if (random.nextDouble() < mutationRate) {
                int pos2 = random.nextInt(route.routeSize());
                
                City city1 = route.getCity(pos1);
                City city2 = route.getCity(pos2);
                
                route.setCity(pos2, city1);
                route.setCity(pos1, city2);
            }
        }
    }
    
    private Route tournamentSelection(Population pop) {
        Population tournament = new Population(tournamentSize, new ArrayList<>());
        
        for (int i = 0; i < tournamentSize; i++) {
            int randomId = random.nextInt(pop.populationSize());
            tournament.saveFittest(pop.getRoute(randomId));
        }
        
        double bestFitness = 0;
        Route bestRoute = null;
        
        for (int i = 0; i < tournament.populationSize(); i++) {
            if (tournament.getRoute(i).getFitness() > bestFitness) {
                bestFitness = tournament.getRoute(i).getFitness();
                bestRoute = tournament.getRoute(i);
            }
        }
        
        return bestRoute;
    }
}