Algoritma Genetika dengan Python: Panduan Lengkap

Algoritma genetika (AG) adalah salah satu teknik kecerdasan buatan yang terinspirasi dari proses evolusi biologis. Ia termasuk dalam keluarga algoritma komputasi evolusioner yang mampu menemukan solusi optimal atau mendekati optimal untuk masalah optimasi yang kompleks. Dengan Python, implementasi algoritma genetika menjadi lebih mudah diakses berkat ekosistem library yang kaya. Artikel ini akan membahas dasar-dasar algoritma genetika dan bagaimana memulainya dengan Python.

Visualisasi sederhana proses evolusi dalam algoritma genetika.

Prinsip Dasar Algoritma Genetika

Algoritma genetika beroperasi berdasarkan tiga prinsip utama yang terinspirasi dari biologi:

1. Populasi: Kumpulan dari berbagai solusi potensial untuk sebuah masalah. Setiap solusi ini disebut sebagai individu atau kromosom.
2. Seleksi (Fitness Function): Setiap individu dalam populasi dievaluasi berdasarkan seberapa baik ia menyelesaikan masalah. Fungsi ini disebut fungsi kebugaran (fitness function). Individu dengan kebugaran lebih tinggi memiliki peluang lebih besar untuk dipilih melanjutkan ke generasi berikutnya.
3. Operator Genetika:
   • Crossover (Persilangan): Menggabungkan informasi genetik dari dua individu terpilih untuk menciptakan individu baru.
   • Mutasi: Mengubah sebagian kecil dari materi genetik individu secara acak. Ini membantu menjaga keragaman populasi dan mencegah terjebak dalam solusi suboptimal.

Proses ini berulang dari generasi ke generasi, di mana populasi yang lebih baik secara bertahap berevolusi, menuntun pada solusi yang semakin optimal.

Implementasi Algoritma Genetika dengan Python

Python menawarkan beberapa library yang sangat membantu dalam mengimplementasikan algoritma genetika. Salah satu yang paling populer adalah `DEAP` (Distributed Evolutionary Algorithms in Python). Library ini menyediakan kerangka kerja yang fleksibel dan kuat untuk membangun berbagai jenis algoritma evolusioner, termasuk algoritma genetika.

Langkah-langkah Dasar Menggunakan DEAP:

1. Instalasi DEAP:

   pip install deap

2. Definisikan Ruang Pencarian (Search Space): Tentukan bagaimana solusi akan direpresentasikan (misalnya, sebagai list angka biner, integer, atau float). Ini akan menjadi struktur `creator.Individual`.
3. Buat Fungsi Kebugaran (Fitness Function): Tulis fungsi Python yang menerima sebuah individu sebagai input dan mengembalikan nilai kebugarannya. Semakin tinggi nilainya, semakin baik solusinya.
4. Atur Operator Genetika: Gunakan fungsi bawaan DEAP atau definisikan operator kustom Anda sendiri untuk persilangan (misalnya, `tools.cxOnePoint`, `tools.cxTwoPoint`), mutasi (misalnya, `tools.mutGaussian`, `tools.mutFlipBit`), dan seleksi (misalnya, `tools.selTournament`).
5. Inisialisasi Populasi: Gunakan `toolbox.population(n=jumlah_populasi)` untuk membuat populasi awal.
6. Jalankan Algoritma: Gunakan fungsi `algorithms.eaSimple()` atau `algorithms.eaMuPlusLambda()` dari DEAP untuk menjalankan siklus evolusi selama sejumlah generasi.

Contoh Sederhana (Representasi Biner):

Misalkan kita ingin mencari konfigurasi terbaik dari sekumpulan bit untuk memaksimalkan jumlah '1'.

Pertama, kita perlu mendefinisikan beberapa hal:

from deap import base, creator, tools, algorithms
        import random

        # 1. Definisikan Ruang Pencarian (kromosom biner)
        # Kita ingin memaksimalkan, jadi bobotnya 1.
        creator.create("FitnessMax", base.Fitness, weights=(1.0,))
        # Individu adalah list dari bit (0 atau 1)
        creator.create("Individual", list, fitness=creator.FitnessMax)

        # Atur generator untuk kromosom
        toolbox = base.Toolbox()
        # Atribut '0' atau '1' secara acak
        toolbox.register("attr_bool", random.randint, 0, 1)
        # Kromosom adalah urutan 10 atribut boolean
        toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, 10)
        # Populasi adalah kumpulan individu
        toolbox.register("population", tools.initRepeat, list, toolbox.individual)

        # 2. Buat Fungsi Kebugaran
        def evalOneMax(individual):
            return sum(individual), # Mengembalikan nilai kebugaran tunggal
        toolbox.register("evaluate", evalOneMax)

        # 3. Atur Operator Genetika
        toolbox.register("mate", tools.cxTwoPoint) # Persilangan dua titik
        toolbox.register("mutate", tools.mutFlipBit, indpb=0.05) # Mutasi flip bit dengan probabilitas 5%
        toolbox.register("select", tools.selTournament, tournsize=3) # Seleksi turnamen

        # 4. Inisialisasi Populasi
        pop = toolbox.population(n=50)

        # 5. Jalankan Algoritma
        stats = tools.Statistics(lambda ind: ind.fitness.values)
        stats.register("avg", numpy.mean) # Perlu numpy terinstal
        stats.register("std", numpy.std)
        stats.register("min", numpy.min)
        stats.register("max", numpy.max)

        hof = tools.HallOfFame(1) # Simpan individu terbaik

        pop, log = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=40, stats=stats, halloffame=hof, verbose=True)

        print("Individu terbaik:", hof[0])
        print("Nilai kebugaran terbaik:", hof[0].fitness.values[0])
        

Kode di atas adalah contoh dasar. Dalam kasus nyata, fungsi kebugaran bisa jauh lebih kompleks, merefleksikan tujuan optimasi yang spesifik. Panjang kromosom, ukuran populasi, probabilitas persilangan dan mutasi, serta jenis operator semuanya adalah parameter yang dapat disesuaikan untuk mencapai kinerja terbaik.

Kasus Penggunaan Algoritma Genetika

Algoritma genetika sangat berguna untuk berbagai jenis masalah, termasuk:

• Optimasi Kombinatorial: Seperti masalah penugasan (assignment problem), penjadwalan, dan routing kendaraan.
• Penjadwalan: Mengoptimalkan jadwal produksi, jadwal kuliah, atau jadwal kerja.
• Desain Teknik: Menemukan desain optimal untuk komponen mekanis, sirkuit, atau antena.
• Pembelajaran Mesin: Memilih fitur terbaik, menyetel hyperparameter model, atau bahkan merancang arsitektur jaringan saraf.
• Perencanaan: Merencanakan strategi permainan, urutan operasi, atau alokasi sumber daya.

Kekuatan utama algoritma genetika terletak pada kemampuannya untuk menjelajahi ruang pencarian yang luas dan kompleks, serta menemukan solusi yang mungkin tidak terpikirkan oleh pendekatan deterministik tradisional. Dengan Python, Anda memiliki alat yang ampuh untuk menerapkan algoritma genetika dan memecahkan berbagai tantangan optimasi.

Ingatlah bahwa keberhasilan algoritma genetika sangat bergantung pada perancangan representasi kromosom dan fungsi kebugaran yang tepat, serta penyetelan parameter operator genetika.