Проблема коммивояжера на Java
Краткое введение в имитацию отжига для задачи коммивояжера на Java.
1. введение
В этом уроке мы узнаем об алгоритме имитации отжига и покажем пример реализации, основанный на задаче коммивояжера (TSP).
2. Имитация Отжига
Алгоритм имитационного отжига является эвристикой для решения задач с большим пространством поиска.
Вдохновение и название пришли от отжига в металлургии; это метод, который включает в себя нагрев и контролируемое охлаждение материала.
В целом, имитированный отжиг уменьшает вероятность принятия худших решений, поскольку он исследует пространство решений и снижает температуру системы. Следующая анимация показывает механизм поиска наилучшего решения с помощью алгоритма имитации отжига:
Как мы можем заметить, алгоритм использует более широкий диапазон решений с высокой температурой системы, ища глобальный оптимум. При снижении температуры диапазон поиска становится все меньше, пока не будет найден глобальный оптимум.
Алгоритм имеет несколько параметров для работы:
- количество итераций – условие остановки для моделирования
- начальная температура – начальная энергия системы
- параметр скорости охлаждения – процент, на который мы снижаем температуру системы
- минимальная температура – дополнительное условие остановки
- время моделирования – необязательное условие остановки
Значения этих параметров должны быть тщательно подобраны, поскольку они могут оказать существенное влияние на производительность процесса.
3. Проблема Коммивояжера
Задача коммивояжера (TSP) – самая известная задача оптимизации компьютерных наук в современном мире.
Проще говоря, это проблема поиска оптимального маршрута между узлами в графе. Общее расстояние перемещения может быть одним из критериев оптимизации. Для получения более подробной информации о TSP, пожалуйста, посмотрите здесь .
4. Модель Java
Чтобы решить проблему TSP, нам понадобятся два класса моделей, а именно City и Travel . В первом из них мы сохраним координаты узлов в графе:
@Data public class City < private int x; private int y; public City() < this.x = (int) (Math.random() * 500); this.y = (int) (Math.random() * 500); >public double distanceToCity(City city) < int x = Math.abs(getX() - city.getX()); int y = Math.abs(getY() - city.getY()); return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2)); >>
Конструктор класса City позволяет создавать случайные местоположения городов. Логика расстояние до города(..) отвечает за вычисления расстояния между городами.
Следующий код отвечает за моделирование тура коммивояжера. Давайте начнем с создания начального порядка городов в путешествиях:
public void generateInitialTravel()
В дополнение к генерации начального порядка нам нужны методы для замены случайных двух городов в порядке перемещения. Мы будем использовать его для поиска лучших решений внутри алгоритма имитации отжига:
Кроме того, нам нужен метод, чтобы отменить генерацию свопа на предыдущем шаге, если новое решение не будет принято нашим алгоритмом:
Последний метод, который мы хотим рассмотреть, – это расчет общего расстояния перемещения, который будет использоваться в качестве критерия оптимизации:
public int getDistance() < int distance = 0; for (int index = 0; index < travel.size(); index++) < City starting = getCity(index); City destination; if (index + 1 < travel.size()) < destination = getCity(index + 1); >else < destination = getCity(0); >distance += starting.distanceToCity(destination); > return distance; >
Теперь давайте сосредоточимся на основной части-реализации алгоритма имитации отжига.
5. Имитация Отжига
В следующей реализации имитационного отжига мы решим проблему TSP. Просто небольшое напоминание, цель состоит в том, чтобы найти кратчайшее расстояние для путешествия по всем городам.
Для того, чтобы запустить процесс, нам нужно предоставить три основных параметра, а именно начальная Температура , количество итераций и Скорость охлаждения :
public double simulateAnnealing(double startingTemperature, int numberOfIterations, double coolingRate) < double t = startingTemperature; travel.generateInitialTravel(); double bestDistance = travel.getDistance(); Travel currentSolution = travel; // . >
Перед началом моделирования мы генерируем начальный (случайный) порядок городов и вычисляем общее расстояние для путешествия. Поскольку это первое вычисленное расстояние, мы сохраняем его в переменной best Distance вместе с CurrentSolution.
На следующем шаге мы запускаем основной цикл моделирования:
Цикл будет длиться указанное нами количество итераций. Кроме того, мы добавили условие, чтобы остановить моделирование, если температура будет ниже или равна 0,1. Это позволит нам сэкономить время моделирования, так как при низких температурах различия в оптимизации почти не видны.
Давайте рассмотрим основную логику алгоритма имитации отжига:
currentSolution.swapCities(); double currentDistance = currentSolution.getDistance(); if (currentDistance < bestDistance) < bestDistance = currentDistance; >else if (Math.exp((bestDistance — currentDistance) / t)
На каждом этапе моделирования мы случайным образом меняем местами два города в порядке перемещения.
Кроме того, мы вычисляем текущее расстояние . Если вновь рассчитанное текущее расстояние меньше , чем лучшее расстояние , мы сохраняем его как лучшее.
В противном случае мы проверяем, является ли функция распределения вероятностей Больцмана ниже случайно выбранного значения в диапазоне от 0 до 1. Если да, мы отменяем обмен городами. Если нет, мы сохраняем новый порядок городов, так как это может помочь нам избежать локальных минимумов.
Наконец, на каждом этапе моделирования мы снижаем температуру на скорость охлаждения:
После моделирования мы возвращаем лучшее решение, которое мы нашли с помощью имитационного отжига.
Пожалуйста, обратите внимание на несколько советов о том, как выбрать лучшие параметры моделирования:
- для небольших пространств решений лучше снизить начальную температуру и увеличить скорость охлаждения, так как это сократит время моделирования без потери качества
- для больших пространств решения, пожалуйста, выберите более высокую начальную температуру и небольшую скорость охлаждения, так как будет больше локальных минимумов
- всегда предоставляйте достаточно времени для моделирования от высокой до низкой температуры системы
Не забудьте потратить некоторое время на настройку алгоритма с меньшим экземпляром задачи, прежде чем приступать к основному моделированию, так как это улучшит конечные результаты. Настройка алгоритма имитационного отжига была показана на примере в этой статье .
6. Заключение
В этом кратком уроке мы смогли узнать об алгоритме имитации отжига и мы решили проблему Коммивояжера . Надеюсь, это покажет, насколько удобен этот простой алгоритм при применении к определенным типам задач оптимизации.
Полную реализацию этой статьи можно найти на GitHub .
Задача коммивояжера
Думаю будет полезно выложить решение задачи на java.
А то на мою просьбу дать пример, сказали, что на всех языках все уже 100 раз решено, скинули ссылку на c++ и статью с википедии.
Задача ориентировалась для теста грид вычислений, но код прост и понятен.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
import java.io.IOException; import java.util.Stack; public class Kamnevoyager { private static class State{ public int cityNum; public int nextIndex; public boolean isStartPoint; public State prev; public State(State prev,int city){ this.prev=prev; cityNum=city; isStartPoint=false; } public State(State prev,int city,boolean start){ this.prev=prev; cityNum=city; isStartPoint=start; } public int calculateLength(Graph graph){ State current=this; int sum=0; while(current.prev!=null){ sum+=graph.getEdge(current.prev.cityNum,current.cityNum); current=current.prev; } return sum; } @Override public String toString(){ if(prev==null)return Integer.toString(cityNum); else{ return prev.toString()+" "+Integer.toString(cityNum); } } } public static final void main(String args[]) throws IOException{ String filename=args[0]; Graph graph=Graph.load(filename); StackState> states=new Stack<>(); State state=null; for(int i=1;iargs.length;i++){ state=new State(state,Integer.parseInt(args[i]),true); states.push(state); graph.enter(state.cityNum); } State shortest=null; state=states.pop(); while(!state.isStartPoint||!(state.nextIndex>=graph.getCount())){ int index=state.nextIndex++; if(index>=graph.getCount()){ graph.leave(state.cityNum); state=states.pop(); }else if(graph.hasEdge(state.cityNum,index)&&graph.enter(index)){ states.push(state); state=new State(state,index); } if(graph.allVisited()){ if(shortest==null){ shortest=state; }else{ if(shortest.calculateLength(graph)>state.calculateLength(graph)){ shortest=state; } } } } System.out.println(shortest); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
import java.io.File; import java.io.IOException; import java.util.Scanner; public class Graph { private int count; private int[][] matrix; private boolean[] marks; public Graph(int count){ this.count=count; matrix=new int[count][count]; marks=new boolean[count]; } public void setEdge(int a,int b,int weight){ matrix[a][b]=weight; matrix[b][a]=weight; } public int getEdge(int a,int b){ return matrix[a][b]; } public boolean hasEdge(int a,int b){ return matrix[a][b]!=0; } public static Graph load(File file) throws IOException { Scanner sc=new Scanner(file); Graph graph=new Graph(sc.nextInt()); while(sc.hasNext()){ int a=sc.nextInt(); int b=sc.nextInt(); int weight=sc.nextInt(); graph.setEdge(a,b,weight); } return graph; } public static Graph load(String filename) throws IOException { return load(new File(filename)); } public boolean enter(int pos){ if(marks[pos]){ return false; }else{ marks[pos]=true; return true; } } public void leave(int pos){ marks[pos]=false; } public int getCount(){ return count; } public boolean allVisited(){ for(int i=0;imarks.length;i++){ if(!marks[i])return false; } return true; } }