Masalah Penjual Keliling di Jawa

1. Perkenalan

Dalam tutorial ini, kita akan belajar tentang algoritma Simulated Annealing dan kita akan menunjukkan contoh implementasi berdasarkan Travelling Salesman Problem (TSP).

2. Simulasi Anil

Algoritma Simulated Annealing adalah heuristik untuk menyelesaikan masalah dengan ruang pencarian yang besar.

Inspirasi dan namanya berasal dari anil dalam metalurgi; itu adalah teknik yang melibatkan pemanasan dan pendinginan material yang terkontrol.

Secara umum, Simulated Annealing mengurangi kemungkinan menerima solusi yang lebih buruk karena ia mengeksplorasi ruang solusi dan menurunkan suhu sistem. Animasi berikut menunjukkan mekanisme untuk menemukan solusi terbaik dengan algoritma Simulated Annealing:

Seperti yang dapat kita amati, algoritme menggunakan rentang solusi yang lebih luas dengan suhu sistem yang tinggi, mencari optimal global. Saat menurunkan suhu, rentang pencarian menjadi lebih kecil, hingga menemukan optimal global.

Algoritme memiliki beberapa parameter untuk dikerjakan:

  • jumlah iterasi - kondisi berhenti untuk simulasi
  • suhu awal - energi awal sistem
  • Parameter laju pendinginan - persentase penurunan suhu sistem
  • suhu minimum - kondisi penghentian opsional
  • waktu simulasi - kondisi penghentian opsional

Nilai parameter tersebut harus dipilih dengan hati-hati - karena mungkin memiliki pengaruh signifikan terhadap kinerja proses.

3. Masalah Penjual Bepergian

The Travelling Salesman Problem (TSP) adalah masalah pengoptimalan ilmu komputer yang paling dikenal di dunia modern.

Dengan kata sederhana, ini adalah masalah menemukan rute optimal antar node dalam grafik. Jarak perjalanan total dapat menjadi salah satu kriteria pengoptimalan. Untuk detail lebih lanjut tentang TSP, lihat di sini.

4. Model Java

Untuk mengatasi masalah TSP ini, kita membutuhkan dua kelas model, yaitu City dan Travel . Yang pertama, kami akan menyimpan koordinat node di grafik:

@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)); } }

Konstruktor kelas City memungkinkan kita untuk membuat lokasi kota secara acak. The distanceToCity (..) logika bertanggung jawab untuk perhitungan mengenai jarak antara kota-kota.

Kode berikut bertanggung jawab untuk membuat model tur penjual keliling. Mari kita mulai dengan membuat urutan awal kota dalam perjalanan:

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

Selain menghasilkan urutan awal, kita membutuhkan metode untuk menukar dua kota secara acak dalam urutan perjalanan. Kami akan menggunakannya untuk mencari solusi yang lebih baik di dalam algoritme Simulated Annealing:

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); }

Selain itu, kami memerlukan metode untuk mengembalikan hasil swap pada langkah sebelumnya, jika solusi baru tidak akan diterima oleh algoritme kami:

public void revertSwap() { travel = previousTravel; }

Metode terakhir yang ingin kami bahas adalah penghitungan total jarak tempuh, yang akan digunakan sebagai kriteria pengoptimalan:

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; }

Sekarang, mari kita fokus pada bagian utama, implementasi algoritma Simulated Annealing.

5. Implementasi Simulasi Annealing

Dalam implementasi Simulated Annealing berikut, kita akan menyelesaikan masalah TSP. Sekadar pengingat, tujuannya adalah menemukan jarak terpendek untuk bepergian ke semua kota.

Untuk memulai proses, kita perlu menyediakan tiga parameter utama, yaitu startingTemperature , numberOfIterations dan coolingRate :

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

Sebelum simulasi dimulai, kami membuat urutan awal (acak) kota dan menghitung jarak total perjalanan. Karena ini adalah jarak yang dihitung pertama, kami menyimpannya di dalam variabel jarak terbaik , bersama dengan solusi saat ini.

Pada langkah selanjutnya kita memulai loop simulasi utama:

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

Perulangan akan menahan jumlah iterasi yang kita tentukan. Selain itu, kami menambahkan kondisi untuk menghentikan simulasi jika suhu akan lebih rendah atau sama dengan 0,1. Ini akan memungkinkan kita untuk menghemat waktu simulasi, karena pada suhu rendah perbedaan pengoptimalan hampir tidak terlihat.

Mari kita lihat logika utama dari algoritma Simulated Annealing:

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

Dalam setiap langkah simulasi, kami secara acak menukar dua kota dalam urutan perjalanan.

Selain itu, kami menghitung currentDistance . Jika baru dihitung currentDistance lebih rendah dari bestDistance , kita simpan sebagai yang terbaik.

Jika tidak, kami memeriksa apakah fungsi Boltzmann dari distribusi probabilitas lebih rendah dari nilai yang dipilih secara acak dalam rentang 0-1. Jika ya, kami mengembalikan pertukaran kota. Jika tidak, kami menjaga tatanan baru kota, karena dapat membantu kami menghindari minimum lokal.

Akhirnya, di setiap langkah simulasi kami mengurangi suhu dengan memberikan pendinginan

t *= coolingRate;

Setelah simulasi, kami mengembalikan solusi terbaik yang kami temukan menggunakan Simulated Annealing.

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

Dalam tutorial singkat ini kami dapat belajar tentang algoritma Simulated Annealing dan kami memecahkan Masalah Travelling Salesman . Mudah-mudahan ini menunjukkan betapa praktisnya algoritme sederhana ini, ketika diterapkan pada jenis masalah pengoptimalan tertentu.

Penerapan lengkap artikel ini dapat ditemukan di GitHub.