Machine LearningLanjutFase E–FE4E6

Genetic Algorithm

Genetic Algorithm meniru evolusi alam untuk menemukan solusi bagus tanpa mencoba semua kemungkinan. Sekumpulan kandidat solusi (populasi) dinilai dengan fungsi fitness; yang terbaik digabung menghasilkan solusi baru dengan sedikit mutasi acak, generasi demi generasi. Perlahan populasi bergerak menuju solusi yang makin baik. Visualisasi mengevolusikan rute pengantaran sampai jaraknya jauh lebih pendek.

Example use case

Mencari urutan rute pengantaran Gojek yang mendekati paling pendek, ketika mencoba semua kombinasi butuh waktu terlalu lama.

Syllabus

Nilai sekumpulan solusi, gabungkan yang terbaik, mutasi sedikit, ulangi — evolusi menuju solusi bagus.

Objectives

·Memahami metode pencarian yang terinspirasi evolusi
·Menjelaskan peran fitness, crossover, dan mutasi
·Mengetahui kapan solusi cukup baik lebih realistis daripada sempurna

How It Works

·Mulai dari populasi solusi acak.
·Nilai tiap solusi dengan fungsi fitness (misalnya 1 dibagi panjang rute).
·Pilih solusi terbaik sebagai induk.
·Gabungkan induk (crossover) dan beri mutasi kecil untuk membentuk generasi baru, lalu ulangi.

Prerequisites

·Konsep fungsi penilaian (fitness)
·Bilangan acak dan array/daftar

Real-World Uses

·Optimasi rute dan jadwal pengantaran.
·Desain antena dan sirkuit (dipakai NASA).
·Menyetel strategi dan level dalam pengembangan game.

Complexity O(generasi x ukuran populasi)