源程序：Github链接
Symmetric traveling salesman problem (TSP)
Given a set of n nodes and distances for each pair of nodes, find a roundtrip of minimal total length visiting each node exactly once. The distance from node i to node j is the same as from node j to node i.
旅行商问题
假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
附：TSPLIB上的旅行商问题标准测试用例
遗传算法
生物进化与遗传算法
遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。如二进制编码;
初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。
这个过程将导致种群像自然进化一样的新生代种群比前代更加适应于环境，最后一代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
1、选择过程：“轮盘赌”法
设群体的规模为 N ，F(xi)(i=1, …, N)是其中每个染色体的适应值。
（1）r=random(0, 1)，s=0，i=0；
（2）如果s≥r，则转（4）；
（3）s=s+p(xi)，i=i+1, 转（2）
（4）xi 即为被选中的染色体，输出i
（5）结束
2、交配过程：十进制交配。随机产生多个交配位，对于这些位置上的基因，子代1从父代2中直接得到，子代2从父代1中直接得到，其余位置保持不变。如果产生相同数字冲突，依次从父代中选取不重复的数字，替换掉重复位。
3、变异过程：十进制变异。同一条Dna的变异次数由变异比例决定，可调节。变异时，每次随机选择两个变异位，将两个位置的数字进行交换。
测试用例与求解结果
改进方向
根据测试，在不同参数组合下，算法收敛的速度不同。在上图所示参数状态下，算法性能较高。可进一步对参数的组合方式进行调节，优化算法性能。
关于适应函数的改进：
本算法直接选取问题的指标函数作为适应函数。如,求函数f(x)的最小值，就直接采用M-f(x)（M为自定义常数）为适应函数。
但有些时候，函数f(x)在最大值附近的变化可能会非常小，以至于他们的适应值非常接近，很难区分出那个染色体占优。此时，便需要定义新的适应函数，且要求该适应函数与问题的指标函数具有相同的变化趋势，但变化的速度更快。因此，可考虑使用线性加速适应函数，或非线性加速适应函数，对本算法进行优化。
求解结果截图
城市数量为16时，求解结果如下：
源程序
/* ----------------Init.java---------------- */package cn.hanquan.ai;import cn.hanquan.ai.pojo.CityBoard;/*** 用于初始化的全局变量* @author Buuug**/public class Init {/*** 城市总数*/public static final int CITYNUM = 16;/*** 种群规模*/public static final int LIVINGSIZE = 200;/*** 迭代次数*/public static final int GENERATION = 2000;/*** 交配概率(1)->(1)+(2)+(3)=1*/public static final double PC = 0.3;/*** 变异概率(2)->(1)+(2)+(3)=1*/public static final double PM = 0.3;/*** 直接保留父代比例(3)->(1)+(2)+(3)=1*/public static final double PS = 0.4;/*** 交配位比例*/public static final double PCRatio = 0.3;/*** 变异位比例*/public static final double PMRatio = 0.1;/*** 直接输入答案*/public static final Integer[] ANSWERDNA = new Integer[] {1, 22, 8, 26, 31, 28, 3, 36, 35, 20, 2, 29, 21, 16, 50,34, 30, 9, 49, 10, 39, 33, 45, 15, 44, 42, 40, 19, 41, 13, 25, 14, 24, 43, 7, 23, 48, 6, 27, 51, 46, 12, 47,18, 4, 17, 37, 5, 38, 11, 32 };/*** 城市坐标总图*/public static CityBoard CITYBOARD;public static double MAXADAPT = 200;}/* ----------------Main.java---------------- */package cn.hanquan.ai;import java.util.ArrayList;import org.apache.log4j.Logger;import cn.hanquan.ai.pojo.CityBoard;import cn.hanquan.ai.pojo.Dna;import cn.hanquan.ai.pojo.DnaPool;import cn.hanquan.ai.pojo.Node;import cn.hanquan.ai.util.CrossUtil;import cn.hanquan.ai.util.MutateUtil;import cn.hanquan.ai.util.Utils;/*** 遗传算法求解旅行商问题* （1）给定群体规模 N，交配概率 pc 和变异概率 pm，t＝0；（2）随机生成 N 个染色体作为初始群体；（3）对于群体中的每一个染色体 xi 分别计算其适应值 F(xi)；（4）如果算法满足停止准则，则转（10）；（5）对群体中的每一个染色体 xi 计算概率；（6）依据计算得到的概率值，从群体中随机地选取 N 个染色体，得到种群；（7）依据交配概率 pc 从种群中选择染色体进行交配，其子代进入新的群体，种群中未进行交配的染色体，直接复制到新群体中；（8）依据变异概率 pm 从新群体中选择染色体进行变异，用变异后的染色体代替新群体中的原染色体；（9）用新群体代替旧群体，t=t+1转（3）；（10）进化过程中适应值最大的染色体，经解码后作为最优解输出；（11）结束. * * @author luyang.gong**/public class Main {private static Logger logger = Logger.getLogger(Node.class);public static void main(String[] args) {int saveCount = (int) (Init.LIVINGSIZE * Init.PS);int crossCount = (int) (Init.LIVINGSIZE * Init.PC);int mutateCount = (int) (Init.LIVINGSIZE - saveCount - crossCount);System.out.println("Please input NODE_COORD_SECTION:");Init.CITYBOARD = Utils.readCityBoard();DnaPool dnaPool = new DnaPool(Init.LIVINGSIZE);//Dna dnaAns = Utils.genSolutionDna(); //已知最优解:74.10873595815309//Dna dnaAns = Utils.genSolutionDna(); //22城市，已知最优解:75.66514947135613//double answer = Utils.calTotalDistance(dnaAns);//logger.info("answer=" + answer);//return;double minDis = Double.POSITIVE_INFINITY;Dna bestDna = dnaPool.dnaList.get(0);for (int i = 0; i < Init.GENERATION; i++) {// 共进行GENERATION次迭代logger.info("第 " + i + "次迭代");DnaPool newPool = new DnaPool();Utils.updateAdaptValueForAll(dnaPool);Utils.updateProbForAll(dnaPool);//计算当前Dna池中数据for (int j = 0; j < Init.CITYNUM; j++) {// 当前旅行路径Dna curDna = dnaPool.dnaList.get(j);logger.info("curDna=" + curDna);double dis = Utils.calTotalDistance(curDna);if (dis < minDis) {minDis = dis;bestDna = curDna;logger.info("发生替换，替换后minDis=" + minDis);logger.info("发生替换，替换后bestDna=" + bestDna);}}// 直接进入下一代for (int j = 0; j < saveCount; j++) {Dna randDna = Utils.getRandCycleDna(dnaPool);newPool.dnaList.add(randDna);}// 交配产生的后代for (int j = 0; j < crossCount; j++) {Dna dna1 = Utils.getRandCycleDna(dnaPool);Dna dna2 = Utils.getRandCycleDna(dnaPool);ArrayList<Dna> twoDna = CrossUtil.doCross(dna1, dna2);newPool.dnaList.add(twoDna.get(0));newPool.dnaList.add(twoDna.get(1));}// 变异产生的后代for (int j = 0; j < mutateCount; j++) {Dna dna = Utils.getRandCycleDna(dnaPool);Dna newDna = MutateUtil.doMutate(dna);newPool.dnaList.add(newDna);}dnaPool = newPool;logger.info("当前迭代minDis=" + minDis);logger.info("当前迭代bestDna=" + bestDna);}logger.info("最终minDis=" + minDis);logger.info("最终bestDna=" + bestDna);}}/* ----------------CityBoard.java---------------- */package cn.hanquan.ai.pojo;import java.util.HashMap;import org.apache.log4j.Logger;/*** 城市坐标*/public class CityBoard {private static Logger logger = Logger.getLogger(CityBoard.class);/*** 需要走过的城市坐标: 0,不需要经过 1,需要经过*/public int[][] arr;public HashMap<Integer, Node> allCityMap;public CityBoard() {this.allCityMap = new HashMap();}@Overridepublic String toString() {return "CityBoard [allCityMap=" + allCityMap + "]";}}/* ----------------Dna.java---------------- */package cn.hanquan.ai.pojo;import java.util.Arrays;import org.apache.log4j.Logger;import cn.hanquan.ai.Init;import cn.hanquan.ai.util.Utils;/*** 染色体,对应一种旅行顺序,命名为Order应该更准确* * @author luyang.gong**/public class Dna {private static Logger logger = Logger.getLogger(Dna.class);/*** 采用整数编码 e.g. 5 9 2 4 6 1 10 7 3 8*/public Integer arr[];/*** 适应值,越大越利于后代生存*/public Double adaptValue;/*** 产生后代的概率*/public Double prob;@Overridepublic String toString() {return "Dna [arr=" + Arrays.toString(arr) + "]";}/*** 生成具有num个数的染色体,并按顺序赋初值* * @param num*/public Dna(int num) {Integer arr[] = new Integer[num];for (int i = 0; i < num; i++) {arr[i] = i + 1;}this.arr = arr;}}/* ----------------DnaPool.java---------------- */package cn.hanquan.ai.pojo;import java.util.ArrayList;import org.apache.log4j.Logger;import cn.hanquan.ai.util.Utils;public class DnaPool {private static Logger logger = Logger.getLogger(Dna.class);/*** Dna池*/public ArrayList<Dna> dnaList;/*** 初始化空的Dna池*/public DnaPool() {this.dnaList = new ArrayList<Dna>();}/*** 指定Dna个数的Dna池* @param size 初始Dna个数*/public DnaPool(int size) {this.dnaList = new ArrayList<Dna>();for(int i=0;i<size;i++) {Dna dna = Utils.genRandomDna();dnaList.add(dna);}}}/* ----------------Node.java---------------- */package cn.hanquan.ai.pojo;import org.apache.log4j.Logger;public class Node {private static Logger logger = Logger.getLogger(Node.class);public int num;public double posX;public double posY;@Overridepublic String toString() {return "Node [num=" + num + ", posX=" + posX + ", posY=" + posY + "]";}}/* ----------------ArrayUtils.java---------------- */package cn.hanquan.ai.util;import java.util.Arrays;import java.util.Random;public class ArrayUtils {private static Random rand = new Random();private static <T> void swap(T[] a, int i, int j) {T temp = a[i];a[i] = a[j];a[j] = temp;}public static <T> void shuffle(T[] arr) {int length = arr.length;for (int i = length; i > 0; i--) {int randInd = rand.nextInt(i);swap(arr, randInd, i - 1);}}public static void main(String[] args) {Integer[] arr = {1, 2, 3, 4, 5, 6, 7 };shuffle(arr);System.out.println(Arrays.toString(arr));}}/* ----------------CrossUtil.java---------------- */package cn.hanquan.ai.util;import java.util.ArrayList;import cn.hanquan.ai.Init;import cn.hanquan.ai.pojo.Dna;/*** 交配操作* * @author luyang.gong**/public class CrossUtil {/*** 进行交配* * @param d1* @param d2* @return 含有两个Dna的ArrayList*/public static ArrayList<Dna> doCross(Dna d1, Dna d2) {Dna d1_cpy = new Dna(Init.CITYNUM);Dna d2_cpy = new Dna(Init.CITYNUM);for (int i = 0; i < Init.CITYNUM; i++) {// 手动实现deepcopyd1_cpy.arr[i] = d1.arr[i];d2_cpy.arr[i] = d2.arr[i];}int crossCount = (int) (Init.CITYNUM * Init.PCRatio);// 交配位数for (int i = 0; i < crossCount; i++) {// 直接交换double rand = Math.random();int index = (int) (Init.CITYNUM * rand);int temp = d1_cpy.arr[index]; // 交换d1_cpy.arr[index] = d2_cpy.arr[index];d2_cpy.arr[index] = temp;}// 处理冲突while (true) {if(getConfIndex(d1_cpy.arr) == -1) {break;}int confIndex = getConfIndex(d1_cpy.arr);for (int i = 0; i < Init.CITYNUM; i++) {int curNum = d2_cpy.arr[i];if (notHasNum(d1_cpy.arr, curNum)) {d1_cpy.arr[confIndex] = curNum;break;}}}// 处理冲突while (true) {if(getConfIndex(d2_cpy.arr) == -1) {break;}int confIndex = getConfIndex(d2_cpy.arr);for (int i = 0; i < Init.CITYNUM; i++) {int curNum = d1_cpy.arr[i];if (notHasNum(d2_cpy.arr, curNum)) {d2_cpy.arr[confIndex] = curNum;break;}}}ArrayList<Dna> twoDna = new ArrayList<Dna>();twoDna.add(d1_cpy);twoDna.add(d2_cpy);return twoDna;}/*** 获取数组重复元素的索引，如果没有重复元素，返回-1* * @param arr* @return 重复元素的索引*/private static int getConfIndex(Integer[] arr) {Integer[] hasNum = new Integer[Init.CITYNUM + 1];for (int i = 0; i < Init.CITYNUM + 1; i++) {hasNum[i] = 0;}for (int i = 0; i < arr.length; i++) {if (0 == hasNum[arr[i]]) {// 当前没重复hasNum[arr[i]]++;} else {// 当前有重复return i;}}//for (int i = 0; i < arr.length; i++) {//System.out.print(arr[i] + " ");//}//System.out.println("没重复");return -1;// 整体没重复}/*** 数组中是否含有某个数* * @param arr* @param num* @return*/private static boolean notHasNum(Integer[] arr, int num) {for (int i = 0; i < arr.length; i++) {if (arr[i] == num) {return false;}}return true;}/*** 交换数组中指定两个位置数值* @param arr* @param n1* @param n2*/private static void swap(Integer[] arr, int n1, int n2) {int temp = arr[n1];arr[n1] = arr[n2];arr[n2] = temp;}public static void main(String[] args) {// 测试用Dna d1 = new Dna(Init.CITYNUM);swap(d1.arr, 2, 5);swap(d1.arr, 3, 6);swap(d1.arr, 8, 7);swap(d1.arr, 15, 11);swap(d1.arr, 3, 14);Dna d2 = new Dna(Init.CITYNUM);swap(d1.arr, 1, 2);swap(d1.arr, 5, 8);swap(d1.arr, 3, 11);swap(d1.arr, 4, 15);System.out.println(d1);System.out.println(d2);System.out.println(doCross(d1, d2));}}/* ----------------MutateUtil.java---------------- */package cn.hanquan.ai.util;import java.util.ArrayList;import cn.hanquan.ai.Init;import cn.hanquan.ai.pojo.Dna;/*** 变异操作* @author luyang.gong**/public class MutateUtil {/*** 选择几个位置进行交换* @param dna* @return*/public static Dna doMutate(Dna dna) {Dna dna_cpy = new Dna(Init.CITYNUM);for (int i = 0; i < Init.CITYNUM; i++) {// 手动实现deepcopydna_cpy.arr[i] = dna.arr[i];}int mutateCount = (int) (Init.CITYNUM * Init.PMRatio);// 变异位数for (int i = 0; i < mutateCount; i++) {int index1 = (int) (Init.CITYNUM * Math.random());int index2 = (int) (Init.CITYNUM * Math.random());swap(dna_cpy.arr, index1, index2);}return dna_cpy;}private static void swap(Integer[] arr, int n1, int n2) {int temp = arr[n1];arr[n1] = arr[n2];arr[n2] = temp;}public static void main(String[] args) {Dna d = new Dna(Init.CITYNUM);System.out.println(d);System.out.println(doMutate(d));}}/* ----------------Utils.java---------------- */package cn.hanquan.ai.util;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Random;import org.apache.log4j.Logger;import cn.hanquan.ai.Init;import cn.hanquan.ai.pojo.CityBoard;import cn.hanquan.ai.pojo.Dna;import cn.hanquan.ai.pojo.DnaPool;import cn.hanquan.ai.pojo.Node;/*** 用于计算的工具类* * @author luyang.gong**/public class Utils {private static Logger logger = Logger.getLogger(Utils.class);/*** 读取所有城市坐标* * @return cityBoard*/public static CityBoard readCityBoard() {CityBoard cityBoard = new CityBoard();BufferedReader br = new BufferedReader(new InputStreamReader(System.in));for (int i = 0; i < Init.CITYNUM; i++) {String str = "";try {str = br.readLine().trim();} catch (IOException e) {e.printStackTrace();}String[] arr = str.split(" ");int num = Integer.parseInt(arr[0]);Node node = new Node();node.num = num;node.posX = Double.parseDouble(arr[1]);node.posY = Double.parseDouble(arr[2]);System.out.println(node);cityBoard.allCityMap.put(num, node);}return cityBoard;}/*** 随机生成Dna* * @return*/public static Dna genRandomDna() {Dna dna = new Dna(Init.CITYNUM);ArrayUtils.shuffle(dna.arr);return dna;}/*** 直接输入答案* * @return*/public static Dna genSolutionDna() {Dna dna = new Dna(Init.CITYNUM);dna.arr = Init.ANSWERDNA;return dna;}/*** 计算旅行总距离* * @param dna* @return*/public static double calTotalDistance(Dna dna) {double totalDistance = 0;for (int i = 0; i < Init.CITYNUM - 1; i++) {Node n1 = Init.CITYBOARD.allCityMap.get(dna.arr[i]);Node n2 = Init.CITYBOARD.allCityMap.get(dna.arr[i + 1]);double dis = Utils.calDistance(n1, n2);totalDistance += dis;}Node firstNode = Init.CITYBOARD.allCityMap.get(dna.arr[0]);Node lastNode = Init.CITYBOARD.allCityMap.get(dna.arr[Init.CITYNUM-1]);//logger.info("firstNode="+firstNode);//logger.info("lastNode="+lastNode);double goBackDis = Utils.calDistance(firstNode, lastNode);totalDistance += goBackDis;logger.debug(totalDistance);return totalDistance;}/*** 根据旅行总距离，计算适应值。适应值越大，越利于繁衍。* @return*/public static double calAdaptValue(double totalDistance) {//double adaptVal = 1 / (Init.MAXADAPT - totalDistance);//if (adaptVal > Init.MAXADAPT) {//Init.MAXADAPT = adaptVal;//}double adaptVal = Init.MAXADAPT - totalDistance;return adaptVal;}/*** 计算并更新Dna池中所有Dna的适应值*/public static void updateAdaptValueForAll(DnaPool dnaPool) {ArrayList<Dna> dnaList = dnaPool.dnaList;for(int i=0;i<dnaList.size();i++) {Dna dna = dnaList.get(i);double totalDistance = calTotalDistance(dna);dna.adaptValue=calAdaptValue(totalDistance);}}private static double calProb(double curAdaptValue,double totalAdaptValue) {return curAdaptValue/totalAdaptValue;}/*** 计算并更新Dna池中所有Dna的繁衍概率* @param dnaPool*/public static void updateProbForAll(DnaPool dnaPool) {ArrayList<Dna> dnaList = dnaPool.dnaList;Double totalAdaptValue = 0.0;for (int i = 0; i < dnaList.size(); i++) {// 计算适应值之和Dna dna = dnaList.get(i);totalAdaptValue += dna.adaptValue;}for (int i = 0; i < dnaList.size(); i++) {// 计算个体适应值Dna dna = dnaList.get(i);dna.prob = calProb(dna.adaptValue, totalAdaptValue);}}/*** 计算两城市之间的距离* * @param n1 城市1* @param n2 城市2* @return*/public static double calDistance(Node n1, Node n2) {double square = (n1.posX - n2.posX) * (n1.posX - n2.posX) + (n1.posY - n2.posY) * (n1.posY - n2.posY);double distance = Math.pow(square, 0.5);logger.debug("(" + n1.posX + "," + n1.posY + ")" + "(" + n2.posX + "," + n2.posY + ")" + "distance=" + distance);return distance;}/*** 轮盘赌算法* @param dnaPool* @return*/public static Dna getRandCycleDna(DnaPool dnaPool) {double rand = Math.random();//logger.info("rand = "+rand);ArrayList<Dna> dnaList = dnaPool.dnaList;double curBegin = 0;double curEnd = 0;//for (int i = 0; i < dnaList.size(); i++) {//Dna curDna = dnaList.get(i);//logger.info("curDna.prob = "+curDna.prob);//}for (int i = 0; i < dnaList.size(); i++) {Dna curDna = dnaList.get(i);curEnd += curDna.prob;logger.debug("[" + curBegin + ", " + curEnd + "]");if (rand >= curBegin && rand <= curEnd) {return curDna;} else {curBegin += curDna.prob;}}logger.error("轮盘赌异常");return null;}}
如果觉得《【人工智能导论】遗传算法求解TSP问题（含源码github）》对你有帮助，请点赞、收藏，并留下你的观点哦！
