模拟退火算法SA原理及python、java、php、c++语言代码实现TSP旅行商问题，智能优化算法，随机寻优算法，全局最短路径

2023-05-06 05:31| 来源: 网络整理| 查看: 265

模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

它是基于Monte-Carlo(蒙特卡洛)迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。　　根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：　　　　P(dE) = exp( dE/(kT) )　　其中k是一个常数，exp表示自然指数，且dE

调用过程：

$map = array( array(0,3,6,7), array(5,0,2,3), array(6,4,0,2), array(3,7,5,0), ); $n = 4; $T = 20; $L = 100; $SA = new SimulatedAnnealing($map,$n,$T,$L); $SA->calculate();

结果输出：

0->1->2->3->0->The min cost is 10

=========================

TSP问题JAVA实现代码：

package noah; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.Random; public class SA { private int cityNum; // 城市数量，编码长度 private int N;// 每个温度迭代步长 private int T;// 降温次数 private float a;// 降温系数 private float t0;// 初始温度 private int[][] distance; // 距离矩阵 private int bestT;// 最佳出现代数 private int[] Ghh;// 初始路径编码 private int GhhEvaluation; private int[] bestGh;// 最好的路径编码 private int bestEvaluation; private int[] tempGhh;// 存放临时编码 private int tempEvaluation; private Random random; public SA() { } /** * constructor of GA * * @param cn * 城市数量 * @param t * 降温次数 * @param n * 每个温度迭代步长 * @param tt * 初始温度 * @param aa * 降温系数 * **/ public SA(int cn, int n, int t, float tt, float aa) { cityNum = cn; N = n; T = t; t0 = tt; a = aa; } // 给编译器一条指令，告诉它对被批注的代码元素内部的某些警告保持静默 @SuppressWarnings("resource") /** * 初始化Tabu算法类 * @param filename 数据文件名，该文件存储所有城市节点坐标数据 * @throws IOException */ private void init(String filename) throws IOException { // 读取数据 int[] x; int[] y; String strbuff; BufferedReader data = new BufferedReader(new InputStreamReader( new FileInputStream(filename))); distance = new int[cityNum][cityNum]; x = new int[cityNum]; y = new int[cityNum]; for (int i = 0; i < cityNum; i++) { // 读取一行数据，数据格式1 6734 1453 strbuff = data.readLine(); // 字符分割 String[] strcol = strbuff.split(" "); x[i] = Integer.valueOf(strcol[1]);// x坐标 y[i] = Integer.valueOf(strcol[2]);// y坐标 } // 计算距离矩阵 // ，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628 for (int i = 0; i < cityNum - 1; i++) { distance[i][i] = 0; // 对角线为0 for (int j = i + 1; j < cityNum; j++) { double rij = Math .sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) / 10.0); // 四舍五入，取整 int tij = (int) Math.round(rij); if (tij

【本文地址】

公司简介

联系我们