Java版旅行商遗传算法

目录

1.主函数

2.geneticalgorithm 遗

传算法

3.individual个体

4.population种群

5.City城市

6.Route

7.多个遗传算法Java版源代码下载

1.主函数

package chapter1_TSP;

public class TSP {
    public static int maxGenerations = 500;
    public static double tolerance = 1e-5;
    public static void main(String[] args)
    {
        long startTimes = System.currentTimeMillis();
        // maxToleranceTimes
        double pre_best_distance = 0;
        int times = 0 ;   //差值小于tolerance 的次数
        int tolerance_maxTimes = 100;

        // Create cities
        int numCities = 10000;
        City[] cities = new City[numCities];
        // Loop to create random cities
        for (int cityIndex = 0; cityIndex < numCities; cityIndex++) {
            // Generate x,y position
            int xPos = (int) (100 * Math.random());
            int yPos = (int) (100 * Math.random());
            // Add city
            cities[cityIndex] = new City(xPos, yPos);
        }  //当然这个1w城市有点夸张了

//		// loop to create certain cities
//		 int[][] positions={ {1,2},{3,5},{9,6},{6,3},{53,15},{56,21},{26,18},{28,29},{9,24},{32,18},
//		 				{43,4},{23,7},{17,20},{30,6},{10,12},{38,20},{99,100},{0,0},{19,27},{56,32}
//		 				,{0,100},{100,0},{50,50},{12,12},{24,24}};
//		 City[] cities=new City[positions.length];
//		 for(int cityIndex=0;cityIndextolerance_maxTimes)
                break;
            pre_best_distance = route.getDistance();   //update pre_distance
        }
        // ************************** end of the loop ******************************

        System.out.println("Stopped after " + (generation-1) + " generations.");
        Route route = new Route(population.getFittest(0), cities);
        System.out.println("Best distance: " + route.getDistance());
        System.out.println("route: ("+population.getFittest(0).toString()+")");
        System.out.println("用时"+(double)(System.currentTimeMillis()-startTimes)/1000+"s");
    }
}

2.geneticalgorithm 遗

传算法

package chapter1_TSP;

import java.util.Arrays;
import java.util.stream.IntStream;

// GA的方法用以 "操作" "种群"
public class GeneticAlgorithm
{
    //    public cross
    // @param
    private int populationSize;
    private double crossrate;
    private double mutationrate;
    private int elitismCount;
    protected int tournamentSize;
    public GeneticAlgorithm(int populationSize,double crossrate,double mutationrate,
                            int elitismCount,int tournamentSize)
    {
        this.populationSize=populationSize;
        this.crossrate=crossrate;
        this.mutationrate=mutationrate;
        this.elitismCount=elitismCount;
        this.tournamentSize=tournamentSize;
    }
    public Population initPopulation(int chromosomeLength)
    {
        return new Population(populationSize,chromosomeLength);
    }
    public double calcFitness(Individual individual,City[] cities)//个体适应度
    {
        Route route = new Route(individual,cities);
        double fitness = 1/route.getDistance();
        individual.setFitness(fitness);
        return fitness;
    }
    public final void evalPopulation(Population population, City[] cities)
    {
        double populationFitness=0;

        IntStream.range(0,populationSize).parallel().forEach(i-> this.calcFitness(population.getIndividual(i),cities) );

        for(Individual individual:population.getIndividuals())
        {
//            Thread.sleep();
            populationFitness += individual.getFitness();
        }

//        for(Individual individual:population.getIndividuals())
//            populationFitness += this.calcFitness(individual,cities);
        double avgFitness = populationFitness/population.size();
        population.setPopulationFitness(avgFitness);
    }
    public Individual selectParent(Population population)// 锦标赛选择
    {
        Population tournament = new Population(this.tournamentSize);
        // 打乱 population
        population.shuffle();
        for(int i=0;i Math.random() && index >= elitismCount)  //精英群体保存，不交叉
            {
                Individual parent2 = selectParent(population);
                // 顺序交叉
                int substirng1 = (int) (Math.random() * (parent1.getChromosomeLength()));
                int substring2 = (int) (Math.random() * (parent1.getChromosomeLength()));
                int startPostion = Math.min(substirng1, substring2);
                int finalPostion = Math.max(substirng1, substring2);

                for (int i = startPostion; startPostion < finalPostion; startPostion++)
                    offspring.setGene(i, parent1.getGene(i));
                for (int i = 0; i < parent2.getChromosomeLength(); i++)
                {
                    int parent2Gene = i + finalPostion;
                    if (parent2Gene >= parent2.getChromosomeLength())
                        parent2Gene -= parent2.getChromosomeLength();
                    if (offspring.containsGene(parent2.getGene(parent2Gene)) == false)//若无则添加
                    {
                        for(int off_i=0;off_i=elitismCount)
            {
                // 遍历 个体的基因
                for(int genIndex=0;genIndex Math.random())
                    {
                        int mutatePos = (int) (Math.random()* individual.getChromosomeLength());
                        int gene1 = individual.getGene(genIndex);
                        int gene2= individual.getGene(mutatePos);
                        individual.setGene(genIndex,gene2);
                        individual.setGene(mutatePos,gene1);
                    }
                }
            }
            newPopulation.setIndividual(index,individual);
        }
        return newPopulation;
    }
    public boolean isTerminationConditionMet(int generation, int MaxGenerarion)
    {
        return generation>MaxGenerarion;
    }
}

3.individual个体

package chapter1_TSP;

import java.util.Random;

public class Individual
{
    private int[] chromosome;
    private double fitness=-1;
    public Individual(int chromosomeLength)
    {
      this.chromosome=new int[chromosomeLength];
      for(int gene=0;gene0)
            str+= this.chromosome[0];
        for(int gene=1;gene< chromosome.length;gene++)
            str+=","+chromosome[gene];
        return str;
    }
    public boolean containsGene(int gene)
    {
        for(int Gene:this.chromosome)
            if (Gene==gene)
                return true;
        return false;
    }
}

4.population种群

package chapter1_TSP;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

public class Population
{
    private Individual[] population;
    private double populationFitness=-1;
    public Population(int populationSize)
    {
        this.population=new Individual[populationSize];
    }
    public Population(int populationSize,int chromosomeLength)
    {
        this(populationSize);
        for(int individualCount=0;individualCount() {
            @Override
            public int compare(Individual o1, Individual o2)
            {
                return Double.compare(o2.getFitness(), o1.getFitness());
            }
        });
        return this.population[offset];
    }
    public void shuffle()
    {
        Random rnd = new Random();
        for(int individ=population.length-1 ; individ>0 ; individ--)
        {
            int randi = rnd.nextInt(individ+1);
            Individual temp=this.population[individ];
            this.population[individ] = this.population[randi];
            this.population[randi] = temp;
        }
    }


}

5.City城市

package chapter1_TSP;

public class City
{
    private double x;
    private double y;
    public City(double x,double y)
    {
        this.x=x;
        this.y=y;
    }
    public City(City city)
    {
        this(city.x, city.y);
    }

    public double distanceFrom(City city)
    {
        double Distance=0;
        double delta_x=Math.pow(this.getX()-city.getX(),2);
        double delta_y=Math.pow(this.getY()-city.getY(),2);

        Distance = Math.sqrt(Math.abs(delta_x+delta_y));
        return Distance;
    }
    public double getX()
    {
        return this.x;
    }
    public double getY()
    {
        return this.y;
    }
}

6.Route

package chapter1_TSP;

public class Route {
    public City[] route;
    public double distance;

    public Route(Individual individual, City[] cities) {
        this.distance = 0;
        int[] chromosome = individual.getChromosome();
        this.route = new City[cities.length];
        for (int gene = 0; gene < chromosome.length; gene++)
            this.route[gene] = cities[chromosome[gene]];
    }

    public double getDistance() {
        if (this.distance > 0)
            return this.distance;
        double distance = 0;
        for (int CityIndex = 0; CityIndex < route.length; CityIndex++)
            distance += route[CityIndex].distanceFrom(route[(CityIndex + 1) % route.length]);
        this.distance = distance;
        return this.distance;
    }
}

---

当然这不是题主原创的，推荐一本书，叫Java版遗传算法，这本书讲的挺详细，几个外国人写的，这个代码是学完后半写半抄的。书上有源代码，建议买，二手就够了，便宜实惠。

7.多个遗传算法Java版源代码下载

Java版遗传算法源代码下载

提取码：1111