代码
个体类
package com.dam.heuristic.ga.test;
import java.io.Serializable;
import java.util.*;
/**
* 个体
*/
public class Individual implements Serializable {
//基因序列
private int[] genes;
//路程
private double distance;
//适应度(在tsp问题中,路程越短越好,即路程越短,适应度越高,取fitness=1.0/distance)
private double fitness;
//生存率(适应度越高,生存率越高)
private double survivalRate;
public Individual(int cityNum) {
this.genes = new int[cityNum];
this.initGenesByRandom();
}
/**
* 随机初始化基因
*/
public void initGenesByRandom() {
List<Integer> cityCodeList = new ArrayList<>();
for (int i = 0; i < this.genes.length; i++) {
cityCodeList.add(i);
}
//随机打乱集合的元素
Collections.shuffle(cityCodeList);
for (int i = 0; i < cityCodeList.size(); i++) {
this.genes[i] = cityCodeList.get(i);
}
}
/**
* 计算个体的tsp回路路程距离和适应值
*/
public void calculateDistanceAndFitness(double[][] distanceMatrix) {
///计算路程距离
//计算从第0个城市到最后一个城市的路程
this.distance = 0;
for (int i = 0; i < this.genes.length - 1; i++) {
this.distance += distanceMatrix[this.genes[i]][this.genes[i + 1]];
}
//计算最后一个城市到第0个城市的路程
this.distance += distanceMatrix[this.genes[0]][this.genes[this.genes.length - 1]];
///计算适应值
this.fitness = 1.0 / this.distance;
}
/**
* 对个体基因中的两个元素进行交换
*/
public void swapTwoElement() {
//对序列中的元素进行打乱,即可产生新的序列
Random random = new Random();
int i = random.nextInt(this.genes.length);
int j = random.nextInt(this.genes.length);
while (i == j) {
j = random.nextInt(this.genes.length);
}
int temp = this.genes[i];
this.genes[i] = this.genes[j];
this.genes[j] = temp;
}
public int[] getGenes() {
return genes;
}
public void setGenes(int[] genes) {
this.genes = genes;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
public double getFitness() {
return fitness;
}
public void setFitness(double fitness) {
this.fitness = fitness;
}
public double getSurvivalRate() {
return survivalRate;
}
public void setSurvivalRate(double survivalRate) {
this.survivalRate = survivalRate;
}
@Override
public String toString() {
return "Individual{" +
"genes=" + Arrays.toString(genes) +
", distance=" + distance +
'}';
}
}
遗传算法
package com.dam.heuristic.ga.test;
import com.dam.heuristic.ga.shuJuMoShuShi.TSPData;
import java.io.*;
import java.util.*;
/**
* 遗传算法
*/
public class GaApi {
private int cityNum; //城市数
//种群的基因个数
private int populationNum = 100;
//迭代次数
private int maxGen = 20000; //进化代数
private double crossRate= 0.98f;//交叉概率
private double mutateRate = 0.4f;//变异概率
private double[][] distanceMatrix; //地图数据
public GaApi(double[][] distanceMatrix) {
this.cityNum = distanceMatrix[0].length;
this.distanceMatrix = distanceMatrix;
}
public void solve() {
变量声明
//种群
List<Individual> population = new ArrayList<>();
//随机数工具
Random random = new Random();
//开始计算时间
long startTime = System.currentTimeMillis();
//存储最优个体
Individual bestIndividual = null;
求解
//初始化种群
this.initPopulation(population);
//迭代优化
for (int t = 0; t < maxGen; t++) {
//选择
Individual localBestIndividual = this.select(population, random);
if (bestIndividual == null || localBestIndividual.getDistance() < bestIndividual.getDistance()) {
bestIndividual = localBestIndividual;
System.out.println("最短距离:" + bestIndividual.getDistance());
}
//交叉
this.crossover(population, random);
//变异
this.mutate(population, random);
}
//获取最优解
System.out.println("最短距离:" + bestIndividual.getDistance());
System.out.println("最优路径:"+ Arrays.toString(bestIndividual.getGenes()));
System.out.println("运行时间:" + (System.currentTimeMillis() - startTime) + "ms");
}
/**
* 初始化种群
*/
public void initPopulation(List<Individual> population) {
for (int i = 0; i < this.populationNum; i++) {
population.add(new Individual(this.cityNum));
}
}
/**
* 计算种群中每个个体的适应度和生存率
* 选择出最优个体(适应值最高)
*
* @param population
*/
public Individual calculateFitnessAndSurvivalRateOfIndividualAndChooseBestOne(List<Individual> population) {
///变量声明
//存储种群中所有个体的总适应值
double totalFitness = 0;
//存储最优适应值
double bestFitness = -Double.MAX_VALUE;
//存储最优个体
Individual bestIndividual = null;
///计算个体的适应值,并选择出最优个体
for (Individual individual : population) {
individual.calculateDistanceAndFitness(this.distanceMatrix);
totalFitness += individual.getFitness();
if (individual.getFitness() > bestFitness) {
bestFitness = individual.getFitness();
bestIndividual = individual;
}
}
//将最优个体从种群中移除
population.remove(bestIndividual);
//删除最优个体对应的适应值
totalFitness -= bestIndividual.getFitness();
///计算种群中剩余个体的生存率
for (Individual individual : population) {
//个体生存率=个体适应值/种群总适应值
individual.setSurvivalRate(individual.getFitness() / totalFitness);
}
return bestIndividual;
}
/**
* 选择优秀个体,选择出适应值最高的个体,将个体复制几个,剩余的名额使用轮盘赌从种群剩余个体中选出
*
* @param population
*/
public Individual select(List<Individual> population, Random random) {
变量声明
//新的种群
List<Individual> newPopulation = new ArrayList<>();
//将最优个体复制几次
int cloneNumOfBestIndividual = 3;
//至少有一次,否则不会被添加到新种群
// cloneNumOfBestIndividual = cloneNumOfBestIndividual == 0 ? 1 : cloneNumOfBestIndividual;
选择个体,选择方式:1、选择种群的最优个体,然后复制几次;2、轮盘赌选择剩余的个体
//计算种群中每个个体的适应度和生存率并选择出最优个体
Individual bestIndividual = this.calculateFitnessAndSurvivalRateOfIndividualAndChooseBestOne(population);
///1、选择种群的最优个体,然后复制几次,将最优个体复制多个,存到新的集合中
for (int i = 0; i < cloneNumOfBestIndividual; i++) {
//deepClone对对象进行深拷贝,否则,改变一个属性,其他几个的属性会跟着变化
newPopulation.add((Individual) this.deepClone(bestIndividual));
}
///2、轮盘赌确定剩余个体
for (int i = 0; i < (this.populationNum - cloneNumOfBestIndividual); i++) {
double p = random.nextDouble();
double sumP = 0;
for (Individual individual : population) {
sumP += individual.getSurvivalRate();
if (sumP >= p) {
//选择个体
newPopulation.add((Individual) this.deepClone(individual));
break;
}
}
}
//用newPopulationt替换population
population.clear();
population.addAll(newPopulation);
return bestIndividual;
}
/**
* 交叉
* 当随机数>pcl,小于pch时,随机找两个个体出来进行基因交叉互换
*/
public void crossover(List<Individual> population, Random random) {
double p = random.nextDouble();
if ( p < this.crossRate) {
//随机找两个索引
int i = random.nextInt(population.size());
int j = random.nextInt(population.size());
while (i == j) {
j = random.nextInt(population.size());
}
Individual individualI = population.get(i);
Individual individualJ = population.get(j);
// System.out.println("执行交叉前-----------------------------------");
// System.out.println(Arrays.toString(individualI.getGenes()));
// System.out.println(Arrays.toString(individualJ.getGenes()));
//使用LinkedHashSet存储元素,方便替换元素时,对元素进行删减
LinkedHashSet<Integer> hashSetI = new LinkedHashSet<>();
LinkedHashSet<Integer> hashSetJ = new LinkedHashSet<>();
for (int k = 0; k < this.cityNum; k++) {
hashSetI.add(individualI.getGenes()[k]);
hashSetJ.add(individualJ.getGenes()[k]);
}
//开始交换的位置,一直交换到尾部,即单点交叉(begin至少要从1开始,否则没有意义)
int begin = random.nextInt(this.cityNum - 1) + 1;
for (int k = begin; k < this.cityNum; k++) {
//交换两个基因的对应位置
int temp = individualI.getGenes()[k];
individualI.getGenes()[k] = individualJ.getGenes()[k];
individualJ.getGenes()[k] = temp;
//删除对应的元素,该元素已经在k位置了
hashSetI.remove(individualI.getGenes()[k]);
hashSetJ.remove(individualJ.getGenes()[k]);
}
//重新填充非交叉区域的元素
begin = 0;
for (Integer element : hashSetI) {
individualI.getGenes()[begin++] = element;
}
begin = 0;
for (Integer element : hashSetJ) {
individualJ.getGenes()[begin++] = element;
}
// System.out.println("执行交叉后-----------------------------------");
// System.out.println(Arrays.toString(individualI.getGenes()));
// System.out.println(Arrays.toString(individualJ.getGenes()));
// System.out.println();
}
}
/**
* 变异:随机交换个体基因的两个元素
*/
public void mutate(List<Individual> population, Random random) {
for (Individual individual : population) {
//当随机数小于变异概率时,对个体的基因进行变异
if (random.nextDouble() < this.mutateRate) {
//对个体基因中的两个元素进行交换
individual.swapTwoElement();
}
}
}
/**
* 深拷贝对象
*
* @param srcObject
* @return
*/
public Object deepClone(Object srcObject) {
ByteArrayOutputStream bos = null;
ObjectOutputStream oos = null;
ByteArrayInputStream bis = null;
ObjectInputStream ois = null;
Object result = null;
try {
bos = new ByteArrayOutputStream();
oos = new ObjectOutputStream(bos);
//将对象写到流里
oos.writeObject(srcObject);
//从流里读回来
bis = new ByteArrayInputStream(bos.toByteArray());
ois = new ObjectInputStream(bis);
result = ois.readObject();
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
bos.close();
oos.close();
bis.close();
ois.close();
} catch (IOException e) {
e.printStackTrace();
}
}
return result;
}
}
测试
package com.dam.heuristic.ga.test;
import com.dam.heuristic.ts.test.TsApi;
import java.io.File;
import java.io.FileInputStream;
public class GaMainRun {
public static void main(String[] args) throws Exception {
声明变量
//距离矩阵,可以直接获取任意两个编号城市的距离
double[][] distanceMatrix;
读取数据
String data = read(new File("src/main/java/com/data/tsp/att48.txt"), "GBK");
String[] cityDataArr = data.split("\n");
//初始化数组
distanceMatrix = new double[cityDataArr.length][cityDataArr.length];
for (int i = 0; i < cityDataArr.length; i++) {
String[] city1Arr = cityDataArr[i].split(" ");
int cityOne = Integer.valueOf(city1Arr[0]);
for (int j = 0; j < i; j++) {
String[] city2Arr = cityDataArr[j].split(" ");
int cityTwo = Integer.valueOf(city2Arr[0]);
if (cityOne == cityTwo) {
distanceMatrix[cityOne - 1][cityTwo - 1] = 0;
} else {
distanceMatrix[cityOne - 1][cityTwo - 1] = getDistance(Double.valueOf(city1Arr[1]), Double.valueOf(city1Arr[2]), Double.valueOf(city2Arr[1]), Double.valueOf(city2Arr[2]));
//对称赋值
distanceMatrix[cityTwo - 1][cityOne - 1] = distanceMatrix[cityOne - 1][cityTwo - 1];
}
}
}
GaApi gaApi = new GaApi( distanceMatrix);
gaApi.solve();
}
/**
* 给定两个城市坐标,获取两个城市的直线距离
*
* @param x1
* @param y1
* @param x2
* @param y2
* @return
*/
private static double getDistance(double x1, double y1, double x2, double y2) {
return Math.sqrt((Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2))/10);
}
private static String read(File f, String charset) throws Exception {
FileInputStream fstream = new FileInputStream(f);
try {
int fileSize = (int) f.length();
if (fileSize > 1024 * 512) {
throw new Exception("File too large to read! size=" + fileSize);
}
byte[] buffer = new byte[fileSize];
fstream.read(buffer);
return new String(buffer, charset);
} finally {
try {
fstream.close();
} catch (Exception e) {
}
}
}
}
最短距离:12163.007870412615
最优路径:[18, 36, 5, 27, 32, 11, 10, 46, 20, 12, 24, 13, 22, 2, 21, 15, 0, 7, 8, 37, 30, 43, 17, 6, 35, 45, 14, 39, 33, 40, 28, 1, 3, 25, 34, 44, 9, 23, 41, 4, 47, 38, 31, 19, 29, 26, 42, 16]
运行时间:12451ms
更多推荐
数学建模常用算法:遗传算法求解tsp问题+att48算例测试【java实现--详细注释】
发布评论