Проблемът с пътуващия продавач в 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 ни позволява да създаваме произволни местоположения на градовете. В distanceToCity (..) Логиката е отговорен за изчисления по отношение на разстоянието между градовете.

Следният код отговаря за моделирането на обиколка на пътуващ продавач. Нека започнем с генериране на първоначален ред на градовете в пътуване:

public void generateInitialTravel() { if (travel.isEmpty()) new Travel(10); Collections.shuffle(travel); }

В допълнение към генерирането на първоначалната поръчка, ние се нуждаем от методите за размяна на произволни два града в пътуващата поръчка. Ще го използваме за търсене на по-добрите решения в алгоритъма за симулирано отгряване:

public void swapCities() { int a = generateRandomIndex(); int b = generateRandomIndex(); previousTravel = travel; City x = travel.get(a); City y = travel.get(b); travel.set(a, y); travel.set(b, x); }

Освен това се нуждаем от метод за връщане на суап генерирането в предишната стъпка, ако новото решение няма да бъде прието от нашия алгоритъм:

public void revertSwap() { travel = previousTravel; }

Последният метод, който искаме да покрием, е изчисляването на общото разстояние на пътуване, което ще се използва като критерий за оптимизация:

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. Само кратко напомняне, целта е да се намери най-краткото разстояние за пътуване до всички градове.

За да започнете процеса, ние трябва да осигури три основни параметри, а именно startingTemperature , numberOfIterations и coolingRate :

public double simulateAnnealing(double startingTemperature, int numberOfIterations, double coolingRate) { double t = startingTemperature; travel.generateInitialTravel(); double bestDistance = travel.getDistance(); Travel currentSolution = travel; // ... }

Преди началото на симулацията генерираме първоначален (произволен) ред на градовете и изчисляваме общото разстояние за пътуване. Тъй като това е първото изчислено разстояние, ние го запазваме в променливата bestDistance , заедно с currentSolution.

В следващата стъпка започваме основен цикъл на симулации:

for (int i = 0; i  0.1) { //... } else { continue; } }

Цикълът ще продължи броя на итерациите, които сме посочили. Освен това добавихме условие за спиране на симулацията, ако температурата ще бъде по-ниска или равна на 0,1. Това ще ни позволи да спестим времето на симулации, тъй като при ниски температури разликите в оптимизацията почти не се виждат.

Нека разгледаме основната логика на алгоритъма за симулирано отгряване:

currentSolution.swapCities(); double currentDistance = currentSolution.getDistance(); if (currentDistance < bestDistance) { bestDistance = currentDistance; } else if (Math.exp((bestDistance - currentDistance) / t) < Math.random()) { currentSolution.revertSwap(); }

Във всяка стъпка на симулация на случаен принцип сменяме два града в реда за пътуване.

Освен това изчисляваме currentDistance . Ако новоизчисленото currentDistance е по-ниско от bestDistance , ние го запазваме като най-доброто.

В противен случай проверяваме дали функцията на Boltzmann за разпределение на вероятностите е по-ниска от произволно избраната стойност в диапазон от 0-1. Ако отговорът е „да“, ние връщаме размяната на градовете. Ако не, запазваме новия ред на градовете, тъй като това може да ни помогне да избегнем местните минимуми.

И накрая, във всяка стъпка от симулацията намаляваме температурата чрез осигурено охлажданеRate:

t *= coolingRate;

След симулацията връщаме най-доброто решение, което намерихме, използвайки симулирано отгряване.

Please note the few tips on how to choose the best simulation parameters:

  • for small solution spaces it's better to lower the starting temperature and increase the cooling rate, as it will reduce the simulation time, without lose of quality
  • for bigger solution spaces please choose the higher starting temperature and small cooling rate, as there will be more local minima
  • always provide enough time to simulate from the high to low temperature of the system

Don't forget to spend some time on the algorithm tuning with the smaller problem instance, before you start the main simulations, as it will improve final results. The tuning of the Simulated Annealing algorithm was shown for example in this article.

6. Conclusion

В този бърз урок успяхме да научим за алгоритъма за симулирано отгряване и решихме проблема с пътуващия продавач . Това се надяваме да покаже колко удобен е този прост алгоритъм, когато се прилага към определени видове проблеми с оптимизацията.

Пълното изпълнение на тази статия може да бъде намерено в GitHub.