一.模拟退火算法概述
模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
二.流程图
伪码描述:
Simulated-Annealing()
Create initial solution S
repeat
for i=1 to iteration-length do
Generate a random transition from S to Si
If ( C(S) <= C(Si) ) then
S=Si
else if( exp(C(S)-C(Si))/kt > random[0,1) ) then
S=Si
Reduce Temperature t
until ( no change in C(S) )
C(S): Cost or Loss function of Solution S
三.旅行商问题上的应用
旅行商问题就是指旅行商按一定的顺序访问N个城市的每个城市,使得每个城市都能被访问且仅能被访问一次,最后回到起点,而使花费的代价最小。本例中从第0个城市开始然后回到原点.
示例代码:
/**
*
*/
package anneal.tsp;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Random;
/**
* @author Dukie 下午02:22:13 2010
*
*/
public class Anneal {
private static double[][] city;
private static int[] currPath;
private static int[] bestPath;
private static double shortesDistance;
private static int numOfCity = 20;
//trace item
private static int iterator = 0;
public void printInfo() {
System.out.println("bestPath: " + Arrays.toString(bestPath));
System.out.println("shortest distance: " + shortesDistance);
System.out.println("iterator times: " + iterator);
}
private void init() throws IOException {
city = new double[numOfCity][numOfCity];
currPath = new int[numOfCity];
bestPath = new int[numOfCity];
shortesDistance = 0;
loadCity();
int lenth = currPath.length;
for (int i = 0; i < lenth; i++) {
currPath[i] = i;
}
}
private void loadCity() throws IOException {
//DistanceMatrix.csv" a file stores the distance info.
File file = new File("E:\\TSP\\DistanceMatrix.csv");
inputGraph(file, city);
}
private void inputGraph(File file, double[][] city) throws IOException {
BufferedReader in = new BufferedReader(new FileReader(file));
String str = "";
int length = 0;
while ((str = in.readLine()) != null) {
str = str.replaceAll(", ", ",");
String[] line = str.split(",");
for (int j = 0; j < numOfCity; j++)
// ten cities
city[length][j] = Double.parseDouble(line[j]);
length++;
}
}
/**
* key function
* @throws IOException
*/
public void anneal() throws IOException {
double temperature = 10000.0D;
double deltaDistance = 0.0D;
double coolingRate = 0.9999;
double absoluteTemperature = 0.00001;
init();
double distance = getToatalDistance(currPath);
int[] nextPath;
Random random = new Random();
while (temperature > absoluteTemperature) {
nextPath = generateNextPath();
deltaDistance = getToatalDistance(nextPath) - distance;
if ((deltaDistance < 0)
|| (distance > 0 &&
Math.exp(-deltaDistance / temperature) > random.nextDouble())) {
currPath = Arrays.copyOf(nextPath, nextPath.length);
distance = deltaDistance + distance;
}
temperature *= coolingRate;
iterator++;
System.out.println("iterator: " + iterator + " path: " + Arrays.toString(currPath));
}
shortesDistance = distance;
System.arraycopy(currPath, 0, bestPath, 0, currPath.length);
}
/**
* calculate total distance
* @param currPath
* @return
*/
private double getToatalDistance(int[] currPath) {
int length = currPath.length;
double totalDistance = 0.0D;
for (int i = 0; i < length - 1; i++) {
totalDistance += city[currPath[i]][currPath[i + 1]];
}
totalDistance += city[currPath[length - 1]][0];
return totalDistance;
}
/**
* swap two elements in the old array to genreate new array
* @return
*/
private int[] generateNextPath() {
int[] nextPath = Arrays.copyOf(currPath, currPath.length);
Random random = new Random();
int length = nextPath.length;
int fistIndex = random.nextInt(length - 1) + 1;
int secIndex = random.nextInt(length - 1) + 1;
while (fistIndex == secIndex) {
secIndex = random.nextInt(length - 1) + 1;
}
int tmp = nextPath[fistIndex];
nextPath[fistIndex] = currPath[secIndex];
nextPath[secIndex] = tmp;
return nextPath;
}
}
20个城市测试数据:
0, 11893, 14633, 10172, 8078, 12843, 10079, 14395, 8056, 14232, 11714, 9309, 12517, 11574, 9720, 13727, 13852, 14330, 10660, 8138
11893, 0, 10568, 9031, 11050, 9039, 10622, 14138, 8738, 9122, 8817, 13099, 9984, 13063, 11546, 11379, 8850, 14111, 13775, 8073
14633, 10568, 0, 14174, 13338, 12629, 14418, 10391, 14444, 12956, 14040, 12835, 13486, 14249, 14039, 8186, 14730, 8886, 12862, 12365
10172, 9031, 14174, 0, 9422, 11814, 14133, 11645, 10495, 13099, 14712, 14988, 11662, 14561, 13350, 10781, 14886, 11549, 13044, 11194
8078, 11050, 13338, 9422, 0, 9868, 11492, 12416, 14672, 12894, 11181, 14310, 9231, 12697, 12617, 8856, 11850, 13302, 12558, 11165
12843, 9039, 12629, 11814, 9868, 0, 10069, 10605, 8799, 9295, 14078, 12349, 14367, 9501, 11379, 13431, 10723, 8845, 10427, 14821
10079, 10622, 14418, 14133, 11492, 10069, 0, 12734, 8656, 13830, 12681, 13165, 11583, 8610, 9202, 9838, 10755, 10674, 13881, 13024
14395, 14138, 10391, 11645, 12416, 10605, 12734, 0, 11980, 13753, 11174, 14603, 13478, 12543, 12974, 11059, 8799, 11781, 13797, 9287
8056, 8738, 14444, 10495, 14672, 8799, 8656, 11980, 0, 11108, 8725, 11253, 12277, 13086, 9476, 12513, 9597, 11850, 13866, 8605
14232, 9122, 12956, 13099, 12894, 9295, 13830, 13753, 11108, 0, 14301, 8065, 13706, 9212, 8301, 8258, 14817, 9277, 12742, 14550
11714, 8817, 14040, 14712, 11181, 14078, 12681, 11174, 8725, 14301, 0, 8133, 13841, 9062, 10704, 13366, 13779, 13710, 12832, 12812
9309, 13099, 12835, 14988, 14310, 12349, 13165, 14603, 11253, 8065, 8133, 0, 8079, 9554, 9760, 11617, 10566, 9382, 12105, 11755
12517, 9984, 13486, 11662, 9231, 14367, 11583, 13478, 12277, 13706, 13841, 8079, 0, 9991, 14717, 13082, 11787, 14614, 11698, 10970
11574, 13063, 14249, 14561, 12697, 9501, 8610, 12543, 13086, 9212, 9062, 9554, 9991, 0, 14363, 8175, 12309, 9042, 11251, 9250
9720, 11546, 14039, 13350, 12617, 11379, 9202, 12974, 9476, 8301, 10704, 9760, 14717, 14363, 0, 12291, 12173, 10971, 9000, 9868
13727, 11379, 8186, 10781, 8856, 13431, 9838, 11059, 12513, 8258, 13366, 11617, 13082, 8175, 12291, 0, 14291, 12915, 9583, 9671
13852, 8850, 14730, 14886, 11850, 10723, 10755, 8799, 9597, 14817, 13779, 10566, 11787, 12309, 12173, 14291, 0, 13657, 8621, 9089
14330, 14111, 8886, 11549, 13302, 8845, 10674, 11781, 11850, 9277, 13710, 9382, 14614, 9042, 10971, 12915, 13657, 0, 9709, 10960
10660, 13775, 12862, 13044, 12558, 10427, 13881, 13797, 13866, 12742, 12832, 12105, 11698, 11251, 9000, 9583, 8621, 9709, 0, 13131
8138, 8073, 12365, 11194, 11165, 14821, 13024, 9287, 8605, 14550, 12812, 11755, 10970, 9250, 9868, 9671, 9089, 10960, 13131, 0
在我机上对20个顸城市进行测试后,效果比较好. 对10城市时,在几秒钟来就达到全局最优解.
注意:模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。
分享到:
相关推荐
模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法
基于遗传算法和模拟退火算法改进的混合模拟退火算法(解决求函数极值问题,MATLAB代码已实现)混合模拟退火算法时遗传算法和模拟退火算法的结合,在混合模拟退火算法中使用了大量的样本作为问题的可能解决方案而不是...
MATLAB模拟退火算法求解VRPTW带时间窗的车辆路径规划问题。还有改进模拟退火算法,禁忌搜索蚁群算法等,以及各种算法的改进,数据可以更改,文章已经写好,需要可以联系我,可以直接用。 MATLAB模拟退火算法求解...
模拟退火算法(Simulate Anneal,SA)是一种通用概率演算法,用来在一个大的搜寻空间内找寻命题的最优解。模拟退火是由S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所发明的。V.Černý在1985年也独立发明...
模拟退火算法算法简介及程序 模拟退火算法算法简介及程序 模拟退火算法算法简介及程序 模拟退火算法算法简介及程序 模拟退火算法算法简介及程序 模拟退火算法算法简介及程序 模拟退火算法算法简介及程序
模拟退火算法讲义 模拟退火算法讲义 模拟退火算法讲义
智能优化算法————》模拟退火算法————》C++实现
利用模拟退火算法求解已知函数的最小值,即模拟退火算法寻优问题,可以广泛推广。
模拟退火算法模拟退火算法模拟退火算法模拟退火算法
模拟退火算法和遗传算法-模拟退火算法和遗传算法.rar 模拟退火算法和遗传算法讲稿
模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火...
有关于模拟退火算法的源程序及matlab代码实现的具体例子
Matlab的模拟退火算法工具箱11111
模拟退火算法模型实例,基于matlab的模拟退火算法说明解释及介绍,
该代码采用python编写模拟退火算法,整个过程中可以根据更改代码求解最大值与最小值。 1. 模拟退火算法的原理: 输入:温度T、退火控制参数k、初始点x0 输出:最优的自变量值、最大/最小值 (1)给定初始值温度T,...
模拟退火算法的过程及实现,介绍的比较详细。
C++模拟退火算法求旅行商问题,用康立山等人的方法
使用matlab语言编程的模拟退火算法对测试函数进行测试
模拟退火算法解决置换流水车间调度问题(python实现) Use Simulated Annealing Algorithm for the basic Job Shop Scheduling Problem With Python 作业车间调度问题(JSP)是计算机科学和运筹学中的一个热门优化问题...