Optimasi Ant Colony dengan Contoh Java

1. Perkenalan

Tujuan dari seri ini adalah untuk menjelaskan ide dari algoritma genetika dan menunjukkan implementasi yang paling dikenal .

Dalam tutorial ini, kami akan menjelaskan konsep optimasi koloni semut (ACO), diikuti dengan contoh kode.

2. Bagaimana ACO Bekerja

ACO adalah algoritma genetika yang terinspirasi oleh perilaku alami semut. Untuk memahami algoritma ACO sepenuhnya, kita perlu membiasakan diri dengan konsep dasarnya:

  • semut menggunakan feromon untuk menemukan jalur terpendek antara rumah dan sumber makanan
  • feromon menguap dengan cepat
  • semut lebih suka menggunakan jalur yang lebih pendek dengan feromon yang lebih padat

Mari kita tunjukkan contoh sederhana ACO yang digunakan dalam Masalah Penjual Perjalanan. Dalam kasus berikut, kita perlu menemukan jalur terpendek antara semua node dalam grafik:

Mengikuti perilaku alami, semut akan mulai menjelajahi jalur baru selama eksplorasi. Warna biru yang lebih kuat menunjukkan jalur yang lebih sering digunakan daripada yang lain, sedangkan warna hijau menunjukkan jalur terpendek saat ini yang ditemukan:

Hasilnya, kita akan mencapai jalur terpendek di antara semua node:

Alat berbasis GUI yang bagus untuk pengujian ACO dapat ditemukan di sini.

3. Implementasi Java

3.1. Parameter ACO

Mari kita bahas parameter utama untuk algoritma ACO, yang dideklarasikan di kelas AntColonyOptimization :

private double c = 1.0; private double alpha = 1; private double beta = 5; private double evaporation = 0.5; private double Q = 500; private double antFactor = 0.8; private double randomFactor = 0.01;

Parameter c menunjukkan jumlah lintasan asli, di awal simulasi. Selanjutnya, alfa mengontrol kepentingan feromon, sedangkan beta mengontrol prioritas jarak. Secara umum, parameter beta harus lebih besar dari alfa untuk hasil terbaik.

Selanjutnya, variabel penguapan menunjukkan persen berapa banyak feromon yang menguap di setiap iterasi, sedangkan Q memberikan informasi tentang jumlah total feromon yang tertinggal di jalur oleh setiap Semut , dan antFaktor memberi tahu kita berapa banyak semut yang akan kita gunakan per kota.

Akhirnya, kita perlu memiliki sedikit keacakan dalam simulasi kita, dan ini ditutupi oleh randomFactor .

3.2. Buat Semut

Setiap Semut akan dapat mengunjungi kota tertentu, mengingat semua kota yang dikunjungi, dan melacak panjang jalur:

public void visitCity(int currentIndex, int city) { trail[currentIndex + 1] = city; visited[city] = true; } public boolean visited(int i) { return visited[i]; } public double trailLength(double graph[][]) { double length = graph[trail[trailSize - 1]][trail[0]]; for (int i = 0; i < trailSize - 1; i++) { length += graph[trail[i]][trail[i + 1]]; } return length; } 

3.3. Setup Semut

Pada awalnya, kita perlu menginisialisasi implementasi kode ACO kita dengan menyediakan matriks trails dan ants:

graph = generateRandomMatrix(noOfCities); numberOfCities = graph.length; numberOfAnts = (int) (numberOfCities * antFactor); trails = new double[numberOfCities][numberOfCities]; probabilities = new double[numberOfCities]; ants = new Ant[numberOfAnts]; IntStream.range(0, numberOfAnts).forEach(i -> ants.add(new Ant(numberOfCities)));

Selanjutnya, kita perlu menyiapkan matriks semut untuk memulai dengan kota acak:

public void setupAnts() { IntStream.range(0, numberOfAnts) .forEach(i -> { ants.forEach(ant -> { ant.clear(); ant.visitCity(-1, random.nextInt(numberOfCities)); }); }); currentIndex = 0; }

Untuk setiap iterasi loop, kami akan melakukan operasi berikut:

IntStream.range(0, maxIterations).forEach(i -> { moveAnts(); updateTrails(); updateBest(); });

3.4. Pindahkan Semut

Mari kita mulai dengan metode moveAnts () . Kita perlu memilih kota berikutnya untuk semua semut, mengingat setiap semut mencoba mengikuti jejak semut lainnya:

public void moveAnts() { IntStream.range(currentIndex, numberOfCities - 1).forEach(i -> { ants.forEach(ant -> { ant.visitCity(currentIndex, selectNextCity(ant)); }); currentIndex++; }); }

Bagian terpenting adalah memilih kota berikutnya dengan benar untuk dikunjungi. Kita harus memilih kota berikutnya berdasarkan logika probabilitas. Pertama, kita dapat memeriksa apakah Ant harus mengunjungi kota secara acak:

int t = random.nextInt(numberOfCities - currentIndex); if (random.nextDouble()  i == t && !ant.visited(i)) .findFirst(); if (cityIndex.isPresent()) { return cityIndex.getAsInt(); } }

Jika kita tidak memilih kota secara acak, kita perlu menghitung probabilitas untuk memilih kota berikutnya, mengingat semut lebih suka mengikuti jejak yang lebih kuat dan lebih pendek. Kita bisa melakukan ini dengan menyimpan kemungkinan pindah ke setiap kota dalam array:

public void calculateProbabilities(Ant ant) { int i = ant.trail[currentIndex]; double pheromone = 0.0; for (int l = 0; l < numberOfCities; l++) { if (!ant.visited(l)){ pheromone += Math.pow(trails[i][l], alpha) * Math.pow(1.0 / graph[i][l], beta); } } for (int j = 0; j < numberOfCities; j++) { if (ant.visited(j)) { probabilities[j] = 0.0; } else { double numerator = Math.pow(trails[i][j], alpha) * Math.pow(1.0 / graph[i][j], beta); probabilities[j] = numerator / pheromone; } } } 

Setelah kami menghitung probabilitas, kami dapat memutuskan kota mana yang akan dituju dengan menggunakan:

double r = random.nextDouble(); double total = 0; for (int i = 0; i = r) { return i; } }

3.5. Perbarui Jejak

Pada langkah ini, kita harus memperbarui lintasan dan feromon kiri:

public void updateTrails() { for (int i = 0; i < numberOfCities; i++) { for (int j = 0; j < numberOfCities; j++) { trails[i][j] *= evaporation; } } for (Ant a : ants) { double contribution = Q / a.trailLength(graph); for (int i = 0; i < numberOfCities - 1; i++) { trails[a.trail[i]][a.trail[i + 1]] += contribution; } trails[a.trail[numberOfCities - 1]][a.trail[0]] += contribution; } }

3.6. Perbarui Solusi Terbaik

Ini adalah langkah terakhir dari setiap iterasi. Kami perlu memperbarui solusi terbaik untuk menjaga referensi ke sana:

private void updateBest() { if (bestTourOrder == null) { bestTourOrder = ants[0].trail; bestTourLength = ants[0].trailLength(graph); } for (Ant a : ants) { if (a.trailLength(graph) < bestTourLength) { bestTourLength = a.trailLength(graph); bestTourOrder = a.trail.clone(); } } }

Setelah semua iterasi, hasil akhir akan menunjukkan jalur terbaik yang ditemukan oleh ACO. Harap dicatat bahwa dengan meningkatkan jumlah kota, kemungkinan menemukan jalur terpendek berkurang.

4. Kesimpulan

Tutorial ini memperkenalkan algoritme Ant Colony Optimization . Anda dapat belajar tentang algoritma genetika tanpa pengetahuan sebelumnya tentang bidang ini, hanya memiliki keterampilan dasar pemrograman komputer.

Kode sumber lengkap untuk potongan kode dalam tutorial ini tersedia di proyek GitHub.

Untuk semua artikel dalam seri ini, termasuk contoh lain dari algoritma genetika, lihat tautan berikut:

  • Bagaimana Mendesain Algoritma Genetika di Java
  • Masalah Penjual Keliling di Jawa
  • Pengoptimalan Koloni Semut (ini)