Kecerdasan Artifisial

Pertemuan 04

Pencarian Lokal dan Optimisasi

Mata Kuliah: Kecerdasan Artifisial (AI401) | 3 SKS

🎯 Capaian Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

Menjelaskan perbedaan pencarian lokal dengan pencarian sistematis
Mengimplementasikan algoritma Hill Climbing dan variasinya
Mengimplementasikan Simulated Annealing
Menerapkan algoritma genetika untuk optimisasi
Mengaplikasikan pencarian lokal pada N-Queens dan TSP

📋 Agenda Hari Ini

Bagian 1

Konsep Pencarian Lokal
Hill Climbing
Simulated Annealing

Bagian 2

Local Beam Search
Algoritma Genetika
Aplikasi: N-Queens & TSP

📚 Review: Pencarian Sistematis

Pada Pertemuan 2-3, kita mempelajari:

Uninformed Search: BFS, DFS, UCS
Informed Search: Greedy, A*
Menyimpan banyak state dalam memori
Menyimpan jalur ke solusi

⚠️ Bagaimana jika ruang pencarian SANGAT BESAR?

🔍 Pencarian Lokal

Pencarian Lokal (Local Search) adalah algoritma yang hanya menyimpan satu state saat ini dan bergerak ke state tetangga tanpa menyimpan jalur.

Kapan digunakan?

Yang penting solusi, bukan jalur
Masalah optimisasi
Ruang pencarian sangat besar

📊 Perbandingan Pendekatan

Aspek	Sistematis	Lokal
Memori	O(b^d)	O(1)
Jalur	Tersimpan	Tidak
Completeness	Ya (umumnya)	Tidak
Cocok untuk	Path finding	Optimisasi

🏔️ Landscape dalam Pencarian

Gambar 1: Landscape dengan global maximum, local maximum, dan plateau

Fitur-fitur Landscape

Fitur	Deskripsi	Masalah
Global Max/Min	Titik optimal sejati	Tujuan kita! ✅
Local Max/Min	Optimal di area lokal	Bisa terjebak ⚠️
Plateau	Area datar	Arah tidak jelas 😕
Ridge	Puncak sempit	Sulit navigasi 🧗

⛰️ Hill Climbing

Hill Climbing adalah algoritma yang terus bergerak ke arah nilai yang lebih baik dan berhenti ketika tidak ada tetangga yang lebih baik.

Disebut juga Greedy Local Search

Selalu pilih langkah terbaik secara lokal

Hill Climbing: Algoritma


def hill_climbing(problem):
    current = problem.initial_state()
    
    while True:
        neighbors = current.get_neighbors()
        best_neighbor = max(neighbors, 
                           key=problem.value)
        
        if problem.value(best_neighbor) <= \
           problem.value(current):
            return current  # Stuck!
        
        current = best_neighbor

Variasi Hill Climbing

Gambar 2: Steepest Ascent, Stochastic, dan First-Choice

Tiga Variasi Hill Climbing

Steepest Ascent

Evaluasi SEMUA tetangga, pilih terbaik

Stochastic

Pilih ACAK dari yang lebih baik

First-Choice

Pilih PERTAMA yang lebih baik

🔄 Random Restart Hill Climbing

Jalankan Hill Climbing berkali-kali dari titik awal acak, pilih hasil terbaik.

Probabilitas sukses:

P(sukses setelah k restart) = 1 - (1-p)^k

p = probabilitas sukses satu kali

⚠️ Masalah Hill Climbing

Keterbatasan:

Terjebak di Local Maximum
Stuck di Plateau
Kesulitan di Ridge

Solusi:

Random Restart
Simulated Annealing
Genetic Algorithm

🧠 Quiz Time!

Pertanyaan 1:

Jika Hill Climbing memiliki probabilitas 25% untuk menemukan global optimum, berapa kali restart minimal agar probabilitas sukses ≥ 90%?

Jawaban:

1 - (0.75)^k ≥ 0.90 → k ≥ 8

Minimal 8 restart

🔥 Simulated Annealing

Simulated Annealing terinspirasi dari proses annealing dalam metalurgi - memanaskan logam lalu mendinginkan perlahan untuk struktur kristal optimal.

💡 Ide Kunci: Kadang-kadang menerima langkah LEBIH BURUK untuk keluar dari local optima!

Proses Simulated Annealing

Gambar 3: Temperatur tinggi → eksplorasi, Temperatur rendah → eksploitasi

Probabilitas Penerimaan

P(terima) = e^ΔE/T

Kondisi	Probabilitas
T tinggi (panas)	Mendekati 1 → hampir selalu terima
T rendah (dingin)	Mendekati 0 → jarang terima
ΔE kecil (sedikit buruk)	Lebih tinggi

Simulated Annealing: Algoritma


def simulated_annealing(problem, schedule):
    current = problem.initial_state()
    
    for t in range(1, MAX_ITER):
        T = schedule(t)  # Temperatur
        if T == 0:
            return current
        
        next = random.choice(current.neighbors())
        delta_E = value(next) - value(current)
        
        if delta_E > 0:  # Lebih baik
            current = next
        elif random.random() < exp(delta_E/T):
            current = next  # Terima yg lebih buruk!

📉 Jadwal Pendinginan

Jenis	Formula	Karakteristik
Linear	T(t) = T₀ - αt	Sederhana
Exponential	T(t) = T₀ × α^t	Paling umum (α≈0.95)
Logarithmic	T(t) = T₀ / ln(t+1)	Sangat lambat

🧠 Quiz Time!

Pertanyaan 2:

Nilai saat ini = 100, tetangga = 95, T = 5. Berapa probabilitas menerima tetangga?

Jawaban:

ΔE = 95 - 100 = -5

P = e^-5/5 = e^-1 = 0.368 (36.8%)

Hill Climbing vs Simulated Annealing

Aspek	Hill Climbing	Simulated Annealing
Langkah buruk	❌ Tidak pernah	✅ Bisa diterima
Escape local optima	❌ Tidak bisa	✅ Bisa
Kecepatan	✅ Cepat	⚠️ Lebih lambat
Hasil	Local optimum	Mendekati global

🔦 Local Beam Search

Local Beam Search memelihara k state secara bersamaan, bukan hanya satu.

Proses:

Generate semua successors dari k state
Pilih k terbaik dari SEMUA successors
Ulangi

Local Beam Search (k=3)

Gambar 4: k state dipertahankan, pilih k terbaik dari semua successors

🧬 Algoritma Genetika

Genetic Algorithm terinspirasi dari evolusi biologis: seleksi alam, crossover, dan mutasi.

Biologi	GA
Chromosome	Solusi kandidat
Gen	Komponen solusi
Fitness	Nilai objective
Populasi	Kumpulan solusi

Alur Algoritma Genetika

Gambar 5: Populasi → Seleksi → Crossover → Mutasi → Populasi Baru

Seleksi: Roulette Wheel

P(individu i) = fitness(i) / Σ fitness(j)

Contoh:

Individu	Fitness	Probabilitas
A	30	30%
B	50	50%
C	20	20%

Crossover (Rekombinasi)

Gambar 6: Single-point, Two-point, dan Uniform Crossover

Contoh Single-Point Crossover


Parent 1: [1, 1, 1, 1 | 1, 1, 1, 1]
Parent 2: [0, 0, 0, 0 | 0, 0, 0, 0]
              ↑ Titik potong

Offspring 1: [1, 1, 1, 1, 0, 0, 0, 0]
Offspring 2: [0, 0, 0, 0, 1, 1, 1, 1]

Mutasi

Mutasi: Perubahan acak kecil untuk mempertahankan keragaman genetik.


Sebelum: [1, 0, 1, 1, 0, 0, 1, 0]
                   ↑ mutasi
Setelah: [1, 0, 0, 1, 0, 0, 1, 0]

💡 Mutation rate biasanya rendah (1-5%)

GA: Algoritma Lengkap


def genetic_algorithm(problem, pop_size, generations):
    population = [random_chromosome() 
                  for _ in range(pop_size)]
    
    for gen in range(generations):
        # Evaluasi fitness
        fitness = [problem.fitness(ind) 
                   for ind in population]
        
        # Buat populasi baru
        new_pop = [best_individual]  # Elitism
        
        while len(new_pop) < pop_size:
            p1, p2 = select(population, fitness)
            off1, off2 = crossover(p1, p2)
            new_pop.extend([mutate(off1), mutate(off2)])
        
        population = new_pop

👑 N-Queens Problem

Tempatkan N ratu pada papan N×N sehingga tidak ada yang saling menyerang.

Gambar 7: Contoh solusi 8-Queens

N-Queens: Representasi

Array 1D:

state = [0, 4, 7, 5, 2, 6, 1, 3]

Index = kolom, Value = baris

Heuristic h:

h = jumlah pasangan ratu yang saling menyerang

Goal: h = 0

N-Queens: Perbandingan Algoritma

Algoritma	Success Rate (8-Queens)
Hill Climbing	~14%
Random Restart HC (100x)	~100%
Simulated Annealing	~94%
Genetic Algorithm	~90%

🗺️ Traveling Salesman Problem

TSP: Cari rute terpendek yang mengunjungi setiap kota tepat satu kali dan kembali ke asal.

Representasi: Permutasi kota

[0, 3, 1, 4, 2]  # Urutan kunjungan

TSP: Operator 2-opt

Gambar 8: 2-opt membalik segmen untuk menghilangkan crossing

🎖️ Aplikasi Pertahanan

Rute Patroli

TSP untuk optimisasi checkpoint

Sensor Radar

Maksimalkan coverage area

Penjadwalan Misi

Alokasi resource optimal

🧠 Quiz Time!

Pertanyaan 3:

Untuk masalah dengan banyak local optima dan constraint kompleks, algoritma mana yang paling sesuai?

A. Steepest Ascent Hill Climbing

B. First-Choice Hill Climbing

C. Genetic Algorithm ✅

D. Local Beam Search

📊 Perbandingan Algoritma

Algoritma	Escape Local?	Memori	Best For
Hill Climbing	❌	O(1)	Landscape smooth
Random Restart	✅	O(1)	Multiple local optima
Simulated Annealing	✅	O(1)	General optimization
Local Beam	⚠️	O(k)	Parallel problems
Genetic Algorithm	✅	O(pop)	Complex landscapes

📝 Ringkasan

Konsep	Poin Kunci
Pencarian Lokal	Hanya simpan state saat ini, O(1)
Hill Climbing	Greedy, bisa stuck di local optima
Simulated Annealing	Terima langkah buruk dengan P = e^ΔE/T
Genetic Algorithm	Populasi + Seleksi + Crossover + Mutasi
Aplikasi	N-Queens, TSP, Penjadwalan

📅 Pertemuan Berikutnya

Pertemuan 05: Pencarian Adversarial

Game Playing dengan AI

Karakteristik game two-player
Algoritma Minimax
Alpha-Beta Pruning
Fungsi Evaluasi

📚 Referensi

Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th Ed.). Pearson. Chapter 4.1-4.2
Ertel, W. (2017). Introduction to Artificial Intelligence (2nd Ed.). Springer. Chapter 5.
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.

Terima Kasih

🤖 Kecerdasan Artifisial

Pertemuan 04: Pencarian Lokal dan Optimisasi

Ada pertanyaan?