首页 > 专题系列 > 算法分析 > 旅行商(TSP)问题-遗传算法
2014
05-10

旅行商(TSP)问题-遗传算法

旅行商问题(Traveling Salesman Problem,TSP)描述

又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。

分析

TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间,搜索空间是n个点的所有排列的集合,大小为(n-1)!。可以形象地把解空间看成是一个无穷大的丘陵地带,各山峰或山谷的高度即是问题的极值。求解TSP,则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。

在前面一讲,介绍了遗传算法的入门,这一篇将用遗传算法解决TSP问题。

根据上一讲的程序,下面的几个函数需要做修改:

1)评价。这个评价算法应该比较简单了,就是找计算总距离,小的为优。

2)突变。为了防止重复访问,不能随机的进行突变。因为每个城市只能访问一次,我们只需要任意的交换两个城市即可。

上一行是突变之前,下面一行是突变之后的。

3)交叉。这个操作是个比较关键的步骤,怎样交叉才能才能父母的优秀基因呢?对于TSP问题,我们要找的是一个最优的排列,其中排列的顺序应该是最重要的。

因此在交叉的时候,分别随机的取 父母的部分序列,要保持原有的顺序。

Parents

先随机的选取 Parent1 的 一部分,例如 678 部分,。然后把剩下的城市 安装 Parent2 中的顺序,遗传下去。

Chlid

代码实现

下面的代码,包括上一篇入门代码,已经上传到github:https://github.com/gaotong2055/Advanced-Algorithm (genetic-algorithm)

1: City.java  城市的简单封装类。

package tsp;

public class City {
    int x;
    int y;

    //构造一个随机的city
    public City(){
        this.x = (int)(Math.random()*200);
        this.y = (int)(Math.random()*200);
    }

    public City(int x, int y){
        this.x = x;
        this.y = y;
    }

    public int getX(){
        return this.x;
    }

    public int getY(){
        return this.y;
    }

    // 计算到给定 city的距离
    public double distanceTo(City city){
        int xDistance = Math.abs(getX() - city.getX());
        int yDistance = Math.abs(getY() - city.getY());
        double distance = Math.sqrt( (xDistance*xDistance) + (yDistance*yDistance) );

        return distance;
    }

    @Override
    public String toString(){
        return getX()+", "+getY();
    }
}

2: Population.java  旅行路径 的一个集合。主要方法,获取种群中最优的的一个路径

package tsp;

public class Population {

    // 保持 路径的 集合 即为种群
    Tour[] tours;
    // Construct a population
    public Population(int populationSize, boolean initialise) {
        tours = new Tour[populationSize];
        // If we need to initialise a population of tours do so
        if (initialise) {
            // Loop and create individuals
            for (int i = 0; i < populationSize(); i++) {
                Tour newTour = new Tour();
                newTour.generateIndividual();
                saveTour(i, newTour);
            }
        }
    }

    // Saves a tour
    public void saveTour(int index, Tour tour) {
        tours[index] = tour;
    }

    // Gets a tour from population
    public Tour getTour(int index) {
        return tours[index];
    }

    // 获取当前种群 中 最优的个体
    public Tour getFittest() {
        Tour fittest = tours[0];
        // Loop through individuals to find fittest
        for (int i = 1; i < populationSize(); i++) {
            if (fittest.getFitness() <= getTour(i).getFitness()) {
                fittest = getTour(i);
            }
        }
        return fittest;
    }

    // Gets population size
    public int populationSize() {
        return tours.length;
    }
}

3. Tour.java

package tsp;

import java.util.ArrayList;
import java.util.Collections;

//每个Tour就是一个旅行路径,种群的一个  个体
public class Tour{

    // 保持所有城市的路径
    private ArrayList tour = new ArrayList<City>();
    // Cache
    private double fitness = 0;
    private int distance = 0;

    // Constructs a blank tour
    public Tour(){
        for (int i = 0; i < TSP_GA.destinationCities.size(); i++) {
            tour.add(null);
        }
    }

    public Tour(ArrayList tour){
        this.tour = tour;
    }

    //创建一个随机的 个体(路径)
    public void generateIndividual() {
        // Loop through all our destination cities and add them to our tour
        for (int cityIndex = 0; cityIndex < TSP_GA.destinationCities.size(); cityIndex++) {
          setCity(cityIndex, TSP_GA.destinationCities.get(cityIndex));
        }
        // 打乱顺序
        Collections.shuffle(tour);
    }

    // Gets a city from the tour
    public City getCity(int tourPosition) {
        return (City)tour.get(tourPosition);
    }

    // 讲城市加入到路径中
    public void setCity(int tourPosition, City city) {
        tour.set(tourPosition, city);
        // If the tours been altered we need to reset the fitness and distance
        fitness = 0;
        distance = 0;
    }

    // 距离小的 适应值较大
    public double getFitness() {
        if (fitness == 0) {
            fitness = 1/(double)getDistance();
        }
        return fitness;
    }

    // 获取当前路径的总距离
    public int getDistance(){
        if (distance == 0) {
            int tourDistance = 0;
            for (int cityIndex=0; cityIndex < tourSize(); cityIndex++) {
                City fromCity = getCity(cityIndex);
                City destinationCity;
                if(cityIndex+1 < tourSize()){
                    destinationCity = getCity(cityIndex+1);
                }
                else{
                    destinationCity = getCity(0);
                }
                tourDistance += fromCity.distanceTo(destinationCity);
            }
            distance = tourDistance;
        }
        return distance;
    }

    //一个路径中 城市的个数
    public int tourSize() {
        return tour.size();
    }
    //当前路径中是否包含该city
    public boolean containsCity(City city){
        return tour.contains(city);
    }

    @Override
    public String toString() {
        String geneString = "|";
        for (int i = 0; i < tourSize(); i++) {
            geneString += getCity(i)+"|";
        }
        return geneString;
    }
}

4. GA.java 算法的实现

package tsp;

public class GA {

    /* GA 算法参数 */
    private static final double mutationRate = 0.015;
    private static final int tournamentSize = 5;
    private static final boolean elitism = true;

    // 进化种群
    public static Population evolvePopulation(Population pop) {
        Population newPopulation = new Population(pop.populationSize(), false);
        // 第一个位置 保持最优个体
        int elitismOffset = 0;
        if (elitism) {
            newPopulation.saveTour(0, pop.getFittest());
            elitismOffset = 1;
        }

        // 种群交叉操作
        // 从当前的种群pop 来 创建下一代种群 newPopulation
        for (int i = elitismOffset; i < newPopulation.populationSize(); i++) {
            // 选择较优的parent
            Tour parent1 = tournamentSelection(pop);
            Tour parent2 = tournamentSelection(pop);
            // 交叉 parents
            Tour child = crossover(parent1, parent2);
            // 将产生的child放入到 新种群 newPopulation
            newPopulation.saveTour(i, child);
        }

        // 进行突变操作,给基因来点good luck
        for (int i = elitismOffset; i < newPopulation.populationSize(); i++) {
            mutate(newPopulation.getTour(i));
        }
        return newPopulation;
    }

    // 对parent1和parent2进行交叉操作,生成新的 tour 路径
    public static Tour crossover(Tour parent1, Tour parent2) {
        // Create new child tour
        Tour child = new Tour();

        // startPos endPos之间的序列,会被遗传到下一代。 (如果startPos<endPos,就是取反)
        int startPos = (int) (Math.random() * parent1.tourSize());
        int endPos = (int) (Math.random() * parent1.tourSize());

        // Loop and add the sub tour from parent1 to our child
        for (int i = 0; i < child.tourSize(); i++) {
            // If our start position is less than the end position
            if (startPos < endPos && i > startPos && i < endPos) {
                child.setCity(i, parent1.getCity(i));
            } // If our start position is larger
            else if (startPos > endPos) {
                if (!(i < startPos && i > endPos)) {
                    child.setCity(i, parent1.getCity(i));
                }
            }
        }

        // 由于child已经继承了parent1的部分city. 下面就是找 parent2中还被child继承的那些city
        // 要保证city的唯一性
        for (int i = 0; i < parent2.tourSize(); i++) {
            // If child doesn't have the city add it
            if (!child.containsCity(parent2.getCity(i))) {
                // Loop to find a spare position in the child's tour
                for (int ii = 0; ii < child.tourSize(); ii++) {
                    // Spare position found, add city
                    if (child.getCity(ii) == null) {
                        child.setCity(ii, parent2.getCity(i));
                        break;
                    }
                }
            }
        }
        return child;
    }

    // 突变操作。随机交换
    private static void mutate(Tour tour) {
        // Loop through tour cities
        for(int tourPos1=0; tourPos1 < tour.tourSize(); tourPos1++){
            // Apply mutation rate
            if(Math.random() < mutationRate){
                // Get a second random position in the tour
                int tourPos2 = (int) (tour.tourSize() * Math.random());
                // Get the cities at target position in tour
                City city1 = tour.getCity(tourPos1);
                City city2 = tour.getCity(tourPos2);

                // Swap them around
                tour.setCity(tourPos2, city1);
                tour.setCity(tourPos1, city2);
            }
        }
    }

    // Selects candidate tour for crossover
    private static Tour tournamentSelection(Population pop) {
        // Create a tournament population
        Population tournament = new Population(tournamentSize, false);
        // For each place in the tournament get a random candidate tour and
        // add it
        for (int i = 0; i < tournamentSize; i++) {
            int randomId = (int) (Math.random() * pop.populationSize());
            tournament.saveTour(i, pop.getTour(randomId));
        }
        // Get the fittest tour
        Tour fittest = tournament.getFittest();
        return fittest;
    }
}

5 TSP_GA.java  测试

package tsp;

import java.util.ArrayList;

public class TSP_GA {

	public static ArrayList<City> destinationCities = new ArrayList<City>();

    public static void main(String[] args) {

        // Create and add our cities
        City city = new City(60, 200);
        destinationCities.add(city);
        City city2 = new City(180, 200);
        destinationCities.add(city2);
        City city3 = new City(80, 180);
        destinationCities.add(city3);
        City city4 = new City(140, 180);
        destinationCities.add(city4);
        City city5 = new City(20, 160);
        destinationCities.add(city5);
        City city6 = new City(100, 160);
        destinationCities.add(city6);
        City city7 = new City(200, 160);
        destinationCities.add(city7);
        City city8 = new City(140, 140);
        destinationCities.add(city8);
        City city9 = new City(40, 120);
        destinationCities.add(city9);
        City city10 = new City(100, 120);
        destinationCities.add(city10);
        City city11 = new City(180, 100);
        destinationCities.add(city11);
        City city12 = new City(60, 80);
        destinationCities.add(city12);
        City city13 = new City(120, 80);
        destinationCities.add(city13);
        City city14 = new City(180, 60);
        destinationCities.add(city14);
        City city15 = new City(20, 40);
        destinationCities.add(city15);
        City city16 = new City(100, 40);
        destinationCities.add(city16);
        City city17 = new City(200, 40);
        destinationCities.add(city17);
        City city18 = new City(20, 20);
        destinationCities.add(city18);
        City city19 = new City(60, 20);
        destinationCities.add(city19);
        City city20 = new City(160, 20);
        destinationCities.add(city20);

        // Initialize population
        Population pop = new Population(50, true);
        System.out.println("Initial distance: " + pop.getFittest().getDistance());

        // 进化到100代就停止程序
        for (int i = 0; i < 100; i++) {
            pop = GA.evolvePopulation(pop);
        }

        // 打印最终的结果
        System.out.println("Finished");
        System.out.println("Final distance: " + pop.getFittest().getDistance());
        System.out.println("Solution:");
        System.out.println(pop.getFittest());
    }
}

输出结果(不确定,非最优解):

Initial distance: 1934
Finished
Final distance: 890
Solution:
|140, 140|140, 180|180, 200|200, 160|180, 100|180, 60|200, 40|160, 20|100, 40|60, 20|20, 20|20, 40|60, 80|120, 80|100, 120|40, 120|20, 160|60, 200|80, 180|100, 160|

英文原文:http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts