# 代码

package com.dam.heuristic.sa.test;
import java.util.Arrays;
import java.util.Random;
/**
* 模拟退火
*/
public class SaApi {
//序列长度
private int sequenceLen;
//初始温度
private double startT;
//结束温度
private double endT;
//每个温度的迭代次数
private int timeInPerTemperature;
//公式中的常数k
private double k;
//降温系数
private double coolingCoefficient;
//距离矩阵
private double[][] distanceMatrix;
/**
* 构造函数，用于创建对象
*/
public SaApi(double startT, double endT, int timeInPerTemperature, double k, double coolingCoefficient, double[][] distanceMatrix) {
this.sequenceLen = distanceMatrix[0].length;
this.startT = startT;
this.endT = endT;
this.timeInPerTemperature = timeInPerTemperature;
this.k = k;
this.coolingCoefficient = coolingCoefficient;
this.distanceMatrix = distanceMatrix;
}
/**
* 模拟退火算法接口
*/
public void solve() {
定义变量
long startTime = System.currentTimeMillis();
//当前温度
double curT = this.startT;
///最优解
//最优温度
double bestT = this.startT;
//序列
int[] localSequence = new int[this.sequenceLen];
//最优序列
int[] bestSequence;
//存储求得最优解的时间
long bestTime = 0;
//最优序列对应的目标函数值
double bestObjectValue = 0;
//上一序列的目标函数值
double lastObjectValue = Double.MAX_VALUE;
///对象
Random random = new Random();
生成初始序列
this.generateInitialSequence(localSequence);
//初始化bestSequence，刚开始的最优序列为初始序列
bestSequence = localSequence.clone();
bestObjectValue = this.getObjectValue(bestSequence);
//        System.out.println("初始序列：" + Arrays.toString(bestSequence));
//        System.out.println("初始目标函数值：" + bestObjectValue);
对序列进行迭代优化
while (curT > this.endT) {
//            System.out.println("当前温度：" + curT + ",--------------------------------------------------------------");
for (int i = 0; i < this.timeInPerTemperature; i++) {
int[] tempSequence = this.generateNewSequence(localSequence);
double tempObjectValue = this.getObjectValue(tempSequence);
double de = tempObjectValue - lastObjectValue;
//                System.out.println("温度：" + bestT);
if (de < 0) {
localSequence = tempSequence.clone();
lastObjectValue = tempObjectValue;
if (tempObjectValue<bestObjectValue){
//更新最优解
bestT = curT;
bestObjectValue = tempObjectValue;
bestSequence = tempSequence.clone();
//                    bestTime = (System.currentTimeMillis() - startTime);
//                        System.out.println("找到更优解：" + bestObjectValue + ",计算时间：" + bestTime + "ms");
}
} else {
double p = Math.exp(-de / (this.k * curT));
if (p > random.nextDouble()) {
//                        System.out.println("当前接受差解为：" + tempObjectValue);
//替换序列
localSequence = tempSequence.clone();
lastObjectValue = tempObjectValue;
} else {
//                        System.out.println("不接受");
}
}
}
curT *= this.coolingCoefficient;
}
System.out.println("-----------------------------------------------------------------------------------------------------------------------------------");
System.out.println("最佳温度:" + bestT);
System.out.println("最优目标函数值:" + bestObjectValue);
System.out.println("最优解对应序列：" + Arrays.toString(bestSequence));
System.out.println("求解时间：" + (System.currentTimeMillis() - startTime) + "ms");
}
/**
* 生成初始序列
*/
public void generateInitialSequence(int[] sequence) {
//        HashSet<Integer> sequenceSet = new HashSet<>();
//        for (int i = 1; i < sequence.length; i++) {
//        }
//
//        //贪婪算法获取初始序列，从城市0开始旅行，即城市0为起点城市
//        sequence[0] = 0;
//        //每次获取离当前城市最近的城市，并加入到sequence
//        for (int i = 1; i < sequence.length; i++) {
//            //寻找离i-1城市最近的城市，即确定第i个城市是哪个
//            double smallDistance = Double.MAX_VALUE;
//            int curCity = 0;
//            for (Integer j : sequenceSet) {
//                if (this.distanceMatrix[sequence[i - 1]][j] < smallDistance && j != sequence[i - 1]) {
//                    smallDistance = this.distanceMatrix[sequence[i - 1]][j];
//                    curCity = j;
//                }
//            }
//            sequence[i] = curCity;
//            sequenceSet.remove(curCity);
//        }
for (int i = 0; i < sequence.length; i++) {
sequence[i] = i;
}
}
/**
* 根据当前序列获取目标函数值
*
* @param sequence
* @return
*/
public double getObjectValue(int[] sequence) {
double objectValue = 0;
//计算从第0个城市到最后一个城市的路程
for (int i = 0; i < sequence.length - 1; i++) {
objectValue += this.distanceMatrix[sequence[i]][sequence[i + 1]];
}
//计算最后一个城市到第0个城市的路程
objectValue += this.distanceMatrix[sequence[0]][sequence[sequence.length - 1]];
return objectValue;
}
/**
* 生产新序列
*
* @param sequence
* @return
*/
public int[] generateNewSequence(int[] sequence) {
int[] sequenceClone = sequence.clone();
//对序列中的元素进行打乱，即可产生新的序列
Random random = new Random();
int i = random.nextInt(sequence.length);
int j = random.nextInt(sequence.length);
while (i == j) {
j = random.nextInt(sequence.length);
}
int temp = sequenceClone[i];
sequenceClone[i] = sequenceClone[j];
sequenceClone[j] = temp;
return sequenceClone;
}
}

# 测试

package com.dam.heuristic.sa.test;
import com.dam.heuristic.sa.improve.ImproveSaApi;
import java.io.File;
import java.io.FileInputStream;
public class SAMainRun {
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];
}
}
}
/*   System.out.println("输出距离矩阵-------------------------------------------------------------------");
for (double[] matrix : distanceMatrix) {
System.out.println(Arrays.toString(matrix));
}*/
System.out.println("saApi求解----------------------------------------------------------------------------");
SaApi saApi = new SaApi(100000, 1e-8, 3000, 10000.0, 0.98, distanceMatrix);
saApi.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];
return new String(buffer, charset);
} finally {
try {
fstream.close();
} catch (Exception e) {
}
}
}
}


saApi求解----------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------------

Process finished with exit code 0

|
11天前
|

Java语言实现最短路径算法（Shortest Path）
Java语言实现最短路径算法（Shortest Path）
20 3
|
6天前
|
Java 测试技术 API

【8月更文挑战第3天】本文将引导读者通过JUnit框架的镜头，探索单元测试的奥秘。我们将一起揭开单元测试的神秘面纱，了解其在软件开发中的关键作用，并具体学习如何在Java项目中应用JUnit进行有效的单元测试。文章不仅会涉及理论概念，还将通过具体的代码示例，展示如何编写和运行单元测试，以确保软件质量。让我们开始吧，一起踏上这段提升代码质量和开发效率的旅程。
|
14天前
|
Java 数据库 Spring
Java编程问题之在测试中使用CGLIB创建代理类如何解决
Java编程问题之在测试中使用CGLIB创建代理类如何解决
30 0
|
18天前
|

15 0
|
18天前
|

Java演进问题之标记-复制算法导致更多的内存占用如何解决
Java演进问题之标记-复制算法导致更多的内存占用如何解决
33 0
|
18天前
|

21 0
|
18天前
|

23 0
|
18天前
|

27 0
|
18天前
|

22 0
|
18天前
|

21 0