package com.dam.heuristic.ils.test;
import java.util.*;
import static com.dam.heuristic.ils.ShuJuMoShuShi.City.CITY_SIZE;
/**
 * 迭代局部搜索
 */
public class IlsApi {
    //最大的迭代次数
    private int maxGen;
    //可接受最大没有提高解的次数
    private int acceptMaxNotImproveSolutionNum;
    //城市数量
    private int cityNum;
    //扰动最优序列时，可接受的新序列对应目标函数值和最优目标函数值之间的差值
    private double acceptDifferentLimit;
    //扰动最优序列时的代数
    private int genNum;
    //距离矩阵
    private double[][] distanceMatrix;
    public IlsApi(int maxGen, int acceptMaxNotImproveSolutionNum, double acceptDifferentLimit, int genNum, double[][] distanceMatrix) {
        this.maxGen = maxGen;
        this.acceptMaxNotImproveSolutionNum = acceptMaxNotImproveSolutionNum;
        this.distanceMatrix = distanceMatrix;
        this.acceptDifferentLimit = acceptDifferentLimit;
        this.genNum = genNum;
        this.cityNum = distanceMatrix[0].length;
    }
    public int[] solve() {
        定义变量
        long startTime = System.currentTimeMillis();
        ///最优解
        //最优代数
        int bestT = 0;
        //序列
        int[] localSequence = new int[this.distanceMatrix[0].length];
        //最优序列
        int[] bestSequence;
        //存储求得最优解的时间
        long bestTime = 0;
        //最优序列对应的目标函数值
        double bestObjectValue = 0;
        生成初始序列
        this.generateInitialSequence(localSequence);
        //初始化bestSequence，刚开始的最优序列为初始序列
        bestSequence = localSequence.clone();
        bestObjectValue = this.getObjectValue(bestSequence);
        初始搜索
        bestSequence = this.localSearch(bestSequence, bestObjectValue);
        bestObjectValue = this.getObjectValue(bestSequence);
        迭代优化
        for (int t = 0; t < this.maxGen; t++) {
            ///多次扰动最优序列，当得到的序列没那么差，或者到达this.genNum限制之后，停止扰动
            int[] tempSequence = new int[this.cityNum];
            double tempObjectValue = Double.MAX_VALUE;
            for (int i = 0; i < this.genNum; i++) {
                //扰动最优解产生新解
                tempSequence = this.perturbation(bestSequence);
                tempObjectValue = this.getObjectValue(tempSequence);
                if (tempObjectValue - bestObjectValue < this.acceptDifferentLimit) {
                    break;
                }
            }
            //对tempSequence进行局部搜索
            tempSequence = this.localSearch(tempSequence, tempObjectValue);
            tempObjectValue = this.getObjectValue(tempSequence);
            //更新最优解
            if (tempObjectValue < bestObjectValue) {
                bestObjectValue = tempObjectValue;
                bestSequence = tempSequence.clone();
                bestT = t;
                bestTime = System.currentTimeMillis() - startTime;
//                System.out.println("当前最优目标函数值:" + tempObjectValue);
//                System.out.println("计算时间为：" + bestTime + "ms");
            }
        }
        System.out.println("最佳迭代次数:" + bestT);
        System.out.println("最优目标函数值:" + bestObjectValue);
        System.out.println("最优解对应序列：" + Arrays.toString(bestSequence));
        System.out.println("计算时间为：" + (System.currentTimeMillis() - startTime) + "ms");
        System.out.println(this.getObjectValue(bestSequence));
        return bestSequence;
    }
    /**
     * 局部搜索更优解
     *
     * @param bestSequence
     * @param bestObjectValue
     * @return 当前所搜索到的最优解对应的目标函数值
     */
    public int[] localSearch(int[] bestSequence, double bestObjectValue) {
        int count = 0;
        while (count++ <= this.acceptMaxNotImproveSolutionNum) {
            for (int i = 0; i < this.cityNum - 1; i++) {
                for (int j = i + 1; j < this.cityNum; j++) {
                    //通过反转indexI和indexJ之间的元素，产生新的序列
                    int[] tempSequence = this.generateNewSequenceBySwapTwoElementWithTwoAppointIndex(bestSequence, i, j);
                    double tempObjectValue = this.getObjectValue(tempSequence);
                    //更新最优解
                    if (tempObjectValue < bestObjectValue) {
                        count = 0;
                        bestObjectValue = tempObjectValue;
                        bestSequence = tempSequence.clone();
                        break;
                    }
                }
            }
        }
        return bestSequence;
    }
    /**
     * 通过将bestSequence的元素分为四组，然后改变四个组的组序，获得新序列
     *
     * @param bestSequence
     */
    public int[] perturbation(int[] bestSequence) {
        Random random = new Random();
        int[] newSequence = new int[bestSequence.length];
        获取五个index，这五个index将bestSequence划分为四组(并非均分)
        //this.cityNum - 2的原因是：indexArr[0]和indexArr[4]都已经确定
        int elementNumInOneGroup = (this.cityNum - 2) / 3;
        int[] indexArr = new int[5];
        indexArr[0] = 0;
        indexArr[1] = random.nextInt(elementNumInOneGroup) + 1;
        indexArr[2] = random.nextInt(elementNumInOneGroup) + elementNumInOneGroup + 1;
        indexArr[3] = random.nextInt(elementNumInOneGroup) + elementNumInOneGroup * 2 + 1;
        indexArr[4] = this.cityNum;
        将组别[0,1,2,3]对应的元素赋值给newSequence
        ///将组序打乱
        List<Integer> groupCodeList = new ArrayList<>();
        //将[0,1,2,3]赋值给集合
        Collections.addAll(groupCodeList, 0, 1, 2, 3);
        //随机打乱
        Collections.shuffle(groupCodeList);
        ///赋值
        int index = 0;
        for (int i = 0; i < groupCodeList.size(); i++) {
            for (int j = indexArr[groupCodeList.get(i)]; j < indexArr[groupCodeList.get(i) + 1]; j++) {
                newSequence[index] = bestSequence[j];
                index++;
            }
        }
        return newSequence;
    }
    /**
     * 通过反转indexI和indexJ之间的元素，产生新的序列
     *
     * @param sequence
     * @param indexI
     * @param indexJ
     */
    public int[] generateNewSequenceBySwapTwoElementWithTwoAppointIndex(int[] sequence, int indexI, int indexJ) {
        //克隆出新序列
        int[] newSequence = sequence.clone();
        int temp;
        //不但交换indexI和indexJ对应的元素
        while (indexI < indexJ) {
            temp = newSequence[indexI];
            newSequence[indexI] = newSequence[indexJ];
            newSequence[indexJ] = temp;
            indexI++;
            indexJ--;
        }
        return newSequence;
    }
    /**
     * 生成初始序列
     */
    public void generateInitialSequence(int[] sequence) {
      /*  HashSet<Integer> sequenceSet = new HashSet<>();
        for (int i = 1; i < sequence.length; i++) {
            sequenceSet.add(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;
    }
}

package com.dam.heuristic.ils.test;
import com.alibaba.fastjson.JSON;
import com.dam.heuristic.ts.test.TsApi;
import com.dam.heuristic.util.paint.PaintTspResult;
import java.io.File;
import java.io.FileInputStream;
import java.lang.reflect.Method;
public class IlsMainRun {
    public static void main(String[] args) throws Exception {
        声明变量
        //距离矩阵，可以直接获取任意两个编号城市的距离
        double[][] distanceMatrix;
        //存储每个城市对应的x,y坐标
        double[][] cityPositionArr;
        读取数据
        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];
        cityPositionArr = new double[cityDataArr.length][2];
        for (int i = 0; i < cityDataArr.length; i++) {
            String[] city1Arr = cityDataArr[i].split(" ");
            cityPositionArr[i][0] = Double.valueOf(city1Arr[1]);
            cityPositionArr[i][1] = Double.valueOf(city1Arr[2]);
            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));
        }*/
        IlsApi ilsApi = new IlsApi(10, 50, 500, 5, distanceMatrix);
        int[] bestSequence = ilsApi.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) {
            }
        }
    }
}