State - Value, Successor, Neighbor

Back to IF3170 Inteligensi Artifisial

Topic

Questions/Cues

• Apa itu ‘state’ dalam Local Search?

• Bagaimana nilai sebuah ‘state’ ditentukan?

• Apa contoh fungsi heuristik (h)?

• Apa itu ‘successor’?

• Apa itu ‘neighbor’?

• Apa saja jenis-jenis ‘neighbor’?

Reference Points

• IF3170_LocalSearch.pdf (Slide 9-17)

Konsep State dalam Local Search

Dalam konteks Local Search, sebuah state merepresentasikan sebuah konfigurasi solusi yang lengkap (complete configuration). Ini berbeda fundamental dari Classical Search di mana state bisa bersifat parsial atau inkremental.

• Prinsip: Algoritma hanya menyimpan satu current state dan berupaya memperbaikinya.

• Contoh (8-Queens Problem): Sebuah state bukanlah papan catur dengan 1, 2, atau 3 ratu, melainkan sebuah papan catur di mana selalu ada 8 ratu yang sudah ditempatkan (misalnya, satu ratu di setiap kolom). Solusi akhir (final state) adalah tujuan dari pencarian ini.

State Value (Nilai Heuristik, h)

Setiap state memiliki nilai yang mengukur “kualitas” atau “seberapa bagus” konfigurasi tersebut. Nilai ini dihitung menggunakan fungsi heuristik (h) atau objective function. Tujuannya adalah mencari state dengan nilai global optimum (maksimum atau minimum).

• Tujuan: Untuk memaksimalkan nilai. Oleh karena itu, kita sering mendefinisikan heuristik sebagai nilai negatif dari “biaya” atau “kesalahan”.

• Contoh (8-Queens Problem):

  • $h=$ - (jumlah pasangan ratu yang saling menyerang)

  • Jika ada 1 pasang ratu yang saling menyerang, maka $h=-1$.

  • Jika tidak ada ratu yang saling menyerang, maka $h=0$. Ini adalah global maximum dan merupakan solusi dari masalah tersebut.

Pada gambar di atas, hanya ada satu pasang ratu yang saling serang (Q4 dan Q7), sehingga nilai heuristik untuk state ini adalah h = -1.

Aksi: Pindah ke Neighbor

Aksi dalam Local Search adalah bergerak dari current state ke state tetangganya (neighbor state). Untuk memahami neighbor, kita harus terlebih dahulu memahami konsep successor.

• Successor: adalah semua kemungkinan state yang dapat dihasilkan dari current state dengan melakukan satu aksi sederhana.

  • Contoh (8-Queens): Aksi didefinisikan sebagai “memindahkan satu ratu ke kotak lain di dalam kolom yang sama”. Karena ada 8 ratu, dan setiap ratu bisa pindah ke 7 kotak lain di kolomnya, maka setiap state memiliki $8\times 7=56$ successors.

• Neighbor: adalah successor yang dipilih oleh algoritma untuk menjadi kandidat state berikutnya. Definisi neighbor bergantung pada strategi algoritma yang digunakan. Ada dua pendekatan umum:

  1. Neighbor sebagai Highest-Valued Successor:
     • Definisi: Algoritma akan mengevaluasi semua 56 successor, dan yang memiliki nilai h tertinggi akan dipilih sebagai neighbor.
     • Karakteristik: Ini adalah pendekatan “serakah” (greedy). Jika ada beberapa successor dengan nilai tertinggi yang sama, salah satunya bisa dipilih secara acak.
     • Penggunaan: Umumnya digunakan dalam algoritma Steepest-Ascent Hill Climbing.
  2. Neighbor sebagai Random Successor:
     • Definisi: Algoritma tidak mengevaluasi semua successor, melainkan hanya memilih satu successor secara acak sebagai neighbor.
     • Karakteristik: Pendekatan ini tidak greedy dan memungkinkan eksplorasi yang lebih luas, meskipun tidak selalu memilih langkah terbaik.
     • Penggunaan: Umumnya digunakan dalam algoritma Stochastic Hill Climbing dan Simulated Annealing.

Summary

Dalam Local Search, sebuah state adalah konfigurasi solusi yang lengkap dan dievaluasi menggunakan nilai heuristik (h). Perpindahan antar-state terjadi dengan memilih sebuah neighbor, yang merupakan state terpilih dari himpunan semua kemungkinan successor (hasil dari satu langkah perubahan). Cara pemilihan neighbor ini—apakah sebagai successor dengan nilai terbaik atau sebagai successor acak—menentukan strategi dan sifat dari algoritma pencarian yang digunakan.

Additional Information

Pentingnya Desain Fungsi Heuristik (h)

Kualitas dan kecepatan Local Search sangat bergantung pada desain fungsi heuristik. Fungsi h yang baik harus:

• Cepat Dihitung: Karena akan dievaluasi berulang kali untuk banyak successor.

• Berkorelasi Kuat dengan Solusi Sebenarnya: Nilai h harus secara akurat mencerminkan seberapa “dekat” sebuah state dengan solusi optimal. Lanskap yang diciptakan oleh fungsi h harus “mulus” dan mengarahkan pencarian ke arah global maximum. Heuristik yang buruk dapat menciptakan banyak local maxima yang menipu.

Trade-off: Highest-Valued vs. Random Successor

• Highest-Valued Successor (Greedy): Cepat dalam menemukan puncak bukit (solusi), tetapi sangat rentan terjebak di local maximum pertama yang ditemui. Eksplorasinya terbatas.

• Random Successor (Stochastic): Lebih lambat untuk mencapai puncak karena bisa jadi mengambil langkah yang tidak optimal. Namun, kemampuannya untuk “melompat” secara acak memberinya kesempatan lebih baik untuk menghindari dan keluar dari local maxima.

Eksplorasi Mandiri

• Perhatikan gambar papan catur di bawah ini dari slide materi. Coba hitung secara manual nilai h (jumlah pasangan ratu yang saling serang) untuk konfigurasi tersebut.

• Pikirkan masalah lain, misalnya Traveling Salesperson Problem (TSP). Apa yang akan menjadi representasi state yang lengkap? Bagaimana Anda mendefinisikan successor dan neighbor? Apa fungsi heuristik (h) yang masuk akal untuk TSP?