没找到用java写的模拟退火算法解决经典算法题——背包问题,这里做个记录。
参考资料:
/google19890102/article/details/45395257
全部代码:
package org.example.ai;public class SimulatedAnnealBag {public static final double T = 1000;// 初始化温度public static final double Tmin = 10;// 温度的下界public static final int k = 10;// 迭代的次数public static final double delta = 0.98;// 温度的下降率public static int[] weight = {1, 3, 4};//物品重量public static int[] value = {15, 20, 30};//物品价值public static int WW = 4;//最大背包重量public static void main(String args[]) {System.out.println("最优解为:" + getSA());}//获取一种方案的价值public static int getFuncResult(int[] solution) {int temp=0;for (int i = 0; i < weight.length; i++) {if(solution[i]==1){temp+=value[i];}}return temp;}//随机获取一种解决方案public static int[] getX() {int len = weight.length;int[] solution = new int[len];int temp = 0;while(true){for (int i = 0; i < len; i++) {if(Math.random() > 0.5){solution[i] = 1;}else{solution[i] = 0;}}temp=0;for (int i = 0; i < len; i++) {if(solution[i]==1){temp+=weight[i];}}if(temp <= WW){//找到符合要求的解决方案break;}}return solution;}/*** 模拟退火算法的过程* @return最优解*/public static int getSA() {int arr[][] = new int[k][weight.length];double t = T;// 初始化初始解for (int i = 0; i < k; i++) {arr[i] = getX();}// 迭代的过程while (t > Tmin) {for (int i = 0; i < k; i++) {// 计算此时的函数结果int funTmp = getFuncResult(arr[i]);// 在邻域内产生新的解int[] x_new = getX();double funTmp_new = getFuncResult(x_new); //邻居的值if (funTmp_new > funTmp ) { //邻居大// 替换arr[i] = x_new;} else {// 以概率替换double p = Math.exp((funTmp_new - funTmp) / t); //求最大值if (Math.random() < p) {arr[i] = x_new;}}}t = t * delta;}int result = getFuncResult(arr[0]);for (int i = 0; i < k; i++) {result = Math.max(result, getFuncResult(arr[i]));}return result;}}