Contoh Algoritma Hill Climbing di Jawa

1. Ikhtisar

Dalam tutorial ini, kami akan menunjukkan algoritma Hill-Climbing dan implementasinya. Kami juga akan melihat manfaat dan kekurangannya. Sebelum langsung terjun ke dalamnya, mari kita bahas pendekatan algoritma generate-and-test secara singkat.

2. Hasilkan-Dan-Uji Algoritma

Ini adalah teknik yang sangat sederhana yang memungkinkan kita untuk membuat algoritma dalam mencari solusi:

  1. Tentukan keadaan saat ini sebagai keadaan awal
  2. Terapkan operasi apa pun yang mungkin pada status saat ini dan buat solusi yang memungkinkan
  3. Bandingkan solusi yang baru dibuat dengan status tujuan
  4. Jika tujuan tercapai atau tidak ada keadaan baru yang dapat dibuat, berhentilah. Jika tidak, kembali ke langkah 2

Ini bekerja sangat baik dengan masalah sederhana. Karena ini adalah pencarian yang melelahkan, tidak mungkin untuk mempertimbangkannya saat berhadapan dengan ruang masalah yang besar. Ini juga dikenal sebagai algoritma British Museum (mencoba menemukan artefak di British Museum dengan menjelajahinya secara acak).

Itu juga merupakan gagasan utama di balik Serangan Mendaki Bukit dalam dunia biometrik. Pendekatan ini dapat digunakan untuk menghasilkan data biometrik sintetis.

3. Pengantar Algoritma Mendaki Bukit Sederhana

Dalam teknik Hill-Climbing, dimulai dari dasar bukit, kita berjalan menanjak hingga mencapai puncak bukit. Dengan kata lain, kita mulai dari keadaan awal dan terus kita perbaiki solusinya hingga optimal.

Ini adalah variasi dari algoritme hasil dan uji yang membuang semua status yang tidak terlihat menjanjikan atau tampaknya tidak mungkin mengarahkan kita ke status tujuan. Untuk mengambil keputusan seperti itu, ia menggunakan heuristik (fungsi evaluasi) yang menunjukkan seberapa dekat keadaan saat ini dengan keadaan tujuan.

Dengan kata sederhana, Hill-Climbing = generate-and-test + heuristics

Mari kita lihat algoritma pendakian Bukit Sederhana:

  1. Tentukan keadaan saat ini sebagai keadaan awal
  2. Ulangi hingga keadaan tujuan tercapai atau tidak ada lagi operator yang dapat diterapkan pada keadaan saat ini:
    1. Menerapkan operasi ke status saat ini dan dapatkan status baru
    2. Bandingkan negara bagian baru dengan tujuan
    3. Berhenti jika keadaan tujuan tercapai
    4. Evaluasi keadaan baru dengan fungsi heuristik dan bandingkan dengan keadaan saat ini
    5. Jika keadaan yang lebih baru lebih dekat ke tujuan dibandingkan dengan keadaan saat ini, perbarui keadaan saat ini

Seperti yang bisa kita lihat, itu mencapai keadaan tujuan dengan perbaikan berulang. Dalam algoritma Hill-Climbing, menemukan tujuan setara dengan mencapai puncak bukit.

4. Contoh

Algoritma Hill Climbing dapat dikategorikan sebagai pencarian informasi. Jadi kita dapat mengimplementasikan pencarian berbasis node atau masalah seperti masalah n-queens yang menggunakannya. Untuk memahami konsep dengan mudah, kami akan mengambil contoh yang sangat sederhana.

Mari kita lihat gambar di bawah ini:

Poin kunci saat menyelesaikan masalah mendaki bukit adalah memilih fungsi heuristik yang sesuai.

Mari kita definisikan fungsi seperti itu h:

h (x) = +1 untuk semua balok pada struktur penyangga jika posisi balok dengan benar sebaliknya -1 untuk semua balok pada struktur penyangga.

Di sini, kami akan memanggil blok mana pun yang diposisikan dengan benar jika memiliki struktur pendukung yang sama dengan status tujuan. Sesuai prosedur pendakian bukit yang dibahas sebelumnya, mari kita lihat semua iterasi dan heuristiknya untuk mencapai status target:

5. Implementasi

Sekarang, mari kita terapkan contoh yang sama menggunakan algoritma Hill-Climbing.

Pertama-tama, kita membutuhkan kelas Negara yang akan menyimpan daftar tumpukan yang mewakili posisi blok di setiap negara bagian. Ini juga akan menyimpan heuristik untuk status tertentu tersebut:

public class State { private List
    
      state; private int heuristics; // copy constructor, setters, and getters }
    

Kami juga membutuhkan metode yang akan menghitung nilai heuristik negara.

public int getHeuristicsValue( List
    
      currentState, Stack goalStateStack) { Integer heuristicValue; heuristicValue = currentState.stream() .mapToInt(stack -> { return getHeuristicsValueForStack( stack, currentState, goalStateStack); }).sum(); return heuristicValue; } public int getHeuristicsValueForStack( Stack stack, List
     
       currentState, Stack goalStateStack) { int stackHeuristics = 0; boolean isPositioneCorrect = true; int goalStartIndex = 0; for (String currentBlock : stack) { if (isPositioneCorrect && currentBlock.equals(goalStateStack.get(goalStartIndex))) { stackHeuristics += goalStartIndex; } else { stackHeuristics -= goalStartIndex; isPositioneCorrect = false; } goalStartIndex++; } return stackHeuristics; } 
     
    

Selanjutnya, kita perlu mendefinisikan metode operator yang akan memberi kita status baru. Untuk contoh kami, kami akan menentukan dua metode ini:

  1. Pecahkan blok dari tumpukan dan dorong ke tumpukan baru
  2. Pecahkan balok dari tumpukan dan dorong ke salah satu tumpukan lainnya
private State pushElementToNewStack( List
    
      currentStackList, String block, int currentStateHeuristics, Stack goalStateStack) { State newState = null; Stack newStack = new Stack(); newStack.push(block); currentStackList.add(newStack); int newStateHeuristics = getHeuristicsValue(currentStackList, goalStateStack); if (newStateHeuristics > currentStateHeuristics) { newState = new State(currentStackList, newStateHeuristics); } else { currentStackList.remove(newStack); } return newState; }
    
private State pushElementToExistingStacks( Stack currentStack, List
    
      currentStackList, String block, int currentStateHeuristics, Stack goalStateStack) { return currentStackList.stream() .filter(stack -> stack != currentStack) .map(stack -> { return pushElementToStack( stack, block, currentStackList, currentStateHeuristics, goalStateStack); }) .filter(Objects::nonNull) .findFirst() .orElse(null); } private State pushElementToStack( Stack stack, String block, List
     
       currentStackList, int currentStateHeuristics, Stack goalStateStack) { stack.push(block); int newStateHeuristics = getHeuristicsValue(currentStackList, goalStateStack); if (newStateHeuristics > currentStateHeuristics) { return new State(currentStackList, newStateHeuristics); } stack.pop(); return null; }
     
    

Sekarang setelah kita memiliki metode pembantu, mari kita tulis metode untuk menerapkan teknik mendaki bukit.

Di sini, kami terus menghitung status baru yang lebih dekat dengan tujuan daripada pendahulunya. Kami terus menambahkan mereka di jalur kami sampai kami mencapai tujuan.

Jika kami tidak menemukan status baru, algoritme diakhiri dengan pesan kesalahan:

public List getRouteWithHillClimbing( Stack initStateStack, Stack goalStateStack) throws Exception { // instantiate initState with initStateStack // ... List resultPath = new ArrayList(); resultPath.add(new State(initState)); State currentState = initState; boolean noStateFound = false; while ( !currentState.getState().get(0).equals(goalStateStack) || noStateFound) { noStateFound = true; State nextState = findNextState(currentState, goalStateStack); if (nextState != null) { noStateFound = false; currentState = nextState; resultPath.add(new State(nextState)); } } return resultPath; }

Selain itu, kita juga memerlukan metode findNextState yang menerapkan semua kemungkinan operasi pada status saat ini untuk mendapatkan status berikutnya:

public State findNextState(State currentState, Stack goalStateStack) { List
    
      listOfStacks = currentState.getState(); int currentStateHeuristics = currentState.getHeuristics(); return listOfStacks.stream() .map(stack -> { return applyOperationsOnState( listOfStacks, stack, currentStateHeuristics, goalStateStack); }) .filter(Objects::nonNull) .findFirst() .orElse(null); } public State applyOperationsOnState( List
     
       listOfStacks, Stack stack, int currentStateHeuristics, Stack goalStateStack) { State tempState; List
      
        tempStackList = new ArrayList(listOfStacks); String block = stack.pop(); if (stack.size() == 0) tempStackList.remove(stack); tempState = pushElementToNewStack( tempStackList, block, currentStateHeuristics, goalStateStack); if (tempState == null) { tempState = pushElementToExistingStacks( stack, tempStackList, block, currentStateHeuristics, goalStateStack); stack.push(block); } return tempState; }
      
     
    

6. Algoritma Mendaki Bukit Tertajam

Steepest-Ascent Hill-Climbing algorithm (gradient search) is a variant of Hill Climbing algorithm. We can implement it with slight modifications in our simple algorithm. In this algorithm, we consider all possible states from the current state and then pick the best one as successor, unlike in the simple hill climbing technique.

In other words, in the case of hill climbing technique we picked any state as a successor which was closer to the goal than the current state whereas, in Steepest-Ascent Hill Climbing algorithm, we choose the best successor among all possible successors and then update the current state.

7. Disadvantages

Hill Climbing is a short sighted technique as it evaluates only immediate possibilities. So it may end up in few situations from which it can not pick any further states. Let's look at these states and some solutions for them:

  1. Local maximum: It's a state which is better than all neighbors, but there exists a better state which is far from the current state; if local maximum occurs within sight of the solution, it is known as “foothills”
  2. Plateau: In this state, all neighboring states have same heuristic values, so it's unclear to choose the next state by making local comparisons
  3. Ridge: It's an area which is higher than surrounding states, but it can not be reached in a single move; for example, we have four possible directions to explore (N, E, W, S) and an area exists in NE direction

There are few solutions to overcome these situations:

  1. We can backtrack to one of the previous states and explore other directions
  2. We can skip few states and make a jump in new directions
  3. We can explore several directions to figure out the correct path

8. Conclusion

Even though hill climbing technique is much better than exhaustive search, it's still not optimal in large problem spaces.

Kami selalu dapat menyandikan informasi global ke dalam fungsi heuristik untuk membuat keputusan yang lebih cerdas, tetapi kompleksitas komputasi akan jauh lebih tinggi daripada sebelumnya.

Algoritma pendakian bukit bisa sangat bermanfaat jika dipukul dengan teknik lain. Seperti biasa, kode lengkap untuk semua contoh dapat ditemukan di GitHub.