Dalam dunia komputasi dan ilmu data, optimasi merupakan sebuah tantangan yang tak henti-hentinya dihadapi. Mencari solusi terbaik dari sekian banyak kemungkinan adalah tugas yang seringkali membutuhkan daya komputasi besar dan waktu yang lama. Di sinilah algoritma genetika hadir sebagai solusi yang elegan dan kuat. Terinspirasi dari proses evolusi alamiah, algoritma ini menawarkan pendekatan yang cerdas untuk menemukan solusi optimal dalam ruang pencarian yang kompleks.
Artikel ini akan membawa Anda menyelami lebih dalam tentang algoritma genetika, dengan fokus khusus pada implementasinya menggunakan bahasa pemrograman Python. Kita akan membahas konsep dasarnya, bagaimana komponen-komponen algoritma genetika bekerja, dan bagaimana Anda dapat mulai membangun solusi Anda sendiri dengan kode Python.
Algoritma genetika (AG) adalah algoritma pencarian heuristik yang meniru proses seleksi alam untuk menemukan solusi yang mendekati optimal untuk masalah optimasi atau pencarian. Ide dasarnya adalah bahwa solusi-solusi yang lebih "baik" (sesuai dengan kriteria tertentu) memiliki peluang lebih besar untuk bertahan hidup dan bereproduksi, mewariskan sifat-sifat unggulnya kepada generasi berikutnya.
Bayangkan sebuah populasi organisme. Setiap organisme merepresentasikan sebuah solusi potensial untuk masalah yang ingin dipecahkan. Organisme ini memiliki "genom" atau kromosom yang berisi informasi tentang solusi tersebut. Melalui proses seleksi, mutasi, dan persilangan (crossover), populasi ini berevolusi dari generasi ke generasi, secara bertahap menuju solusi yang semakin baik.
Ada beberapa komponen inti yang membentuk algoritma genetika:
Python adalah bahasa yang sangat cocok untuk mengimplementasikan algoritma genetika berkat sintaksisnya yang mudah dibaca, banyaknya library pendukung, dan komunitas yang aktif. Kita bisa memulai dengan mendefinisikan representasi kromosom, fungsi fitness, dan kemudian membangun loop evolusi yang mencakup seleksi, crossover, dan mutasi.
Sebagai contoh sederhana, mari kita bayangkan kita ingin menemukan kombinasi angka biner yang memaksimalkan jumlah '1' dalam sebuah string.
import random
# Parameter Algoritma Genetika
POPULASI_SIZE = 50
CHROMOSOME_LENGTH = 10
GENERATIONS = 100
MUTATION_RATE = 0.01
CROSSOVER_RATE = 0.8
# 1. Representasi Kromosom
def create_individual():
return [random.randint(0, 1) for _ in range(CHROMOSOME_LENGTH)]
def create_population():
return [create_individual() for _ in range(POPULASI_SIZE)]
# 2. Fungsi Fitness (Memaksimalkan jumlah '1')
def calculate_fitness(individual):
return sum(individual)
# 3. Seleksi (Roulette Wheel)
def select_parents(population, fitness_scores):
total_fitness = sum(fitness_scores)
selection_probs = [f / total_fitness for f in fitness_scores]
parents = random.choices(population, weights=selection_probs, k=2)
return parents[0], parents[1]
# 4. Persilangan (Single Point Crossover)
def crossover(parent1, parent2):
if random.random() < CROSSOVER_RATE:
crossover_point = random.randint(1, CHROMOSOME_LENGTH - 1)
child1 = parent1[:crossover_point] + parent2[crossover_point:]
child2 = parent2[:crossover_point] + parent1[crossover_point:]
return child1, child2
else:
return list(parent1), list(parent2) # Kembalikan salinan jika tidak crossover
# 5. Mutasi
def mutate(individual):
for i in range(CHROMOSOME_LENGTH):
if random.random() < MUTATION_RATE:
individual[i] = 1 - individual[i] # Balikkan bit
return individual
# --- Main Algoritma ---
def run_genetic_algorithm():
population = create_population()
for generation in range(GENERATIONS):
# Hitung fitness untuk setiap individu
fitness_scores = [calculate_fitness(ind) for ind in population]
# Cari individu terbaik di generasi ini
best_fitness = max(fitness_scores)
best_individual_index = fitness_scores.index(best_fitness)
best_individual = population[best_individual_index]
print(f"Generasi {generation}: Best Fitness = {best_fitness}, Individual = {best_individual}")
# Buat generasi baru
new_population = []
# Elitisme: Pertahankan individu terbaik
new_population.append(list(best_individual)) # Salin agar tidak termutasi
while len(new_population) < POPULASI_SIZE:
parent1, parent2 = select_parents(population, fitness_scores)
child1, child2 = crossover(parent1, parent2)
mutated_child1 = mutate(child1)
mutated_child2 = mutate(child2)
new_population.append(mutated_child1)
if len(new_population) < POPULASI_SIZE:
new_population.append(mutated_child2)
population = new_population
# Hasil akhir
final_fitness_scores = [calculate_fitness(ind) for ind in population]
final_best_fitness = max(final_fitness_scores)
final_best_individual_index = final_fitness_scores.index(final_best_fitness)
final_best_individual = population[final_best_individual_index]
print("\n--- Hasil Akhir ---")
print(f"Solusi Terbaik Ditemukan: {final_best_individual}")
print(f"Nilai Fitness Tertinggi: {final_best_fitness}")
if __name__ == "__main__":
run_genetic_algorithm()
Kode di atas adalah contoh minimalis. Dalam aplikasi nyata, Anda mungkin perlu menyesuaikan representasi kromosom, fungsi fitness, operator seleksi, crossover, dan mutasi sesuai dengan sifat masalah yang Anda hadapi. Library seperti DEAP (Distributed Evolutionary Algorithms in Python) dapat sangat membantu untuk implementasi yang lebih kompleks dan efisien.
Algoritma genetika sangat efektif untuk masalah-masalah yang memiliki karakteristik berikut:
Beberapa contoh aplikasi nyata termasuk penjadwalan (scheduling), optimasi rute, desain eksperimen, pelatihan jaringan saraf, dan penemuan obat.
Algoritma genetika menawarkan paradigma yang kuat dan fleksibel untuk mengatasi masalah optimasi. Dengan memanfaatkan prinsip-prinsip evolusi, kita dapat merancang algoritma yang mampu menemukan solusi yang baik untuk masalah-masalah yang kompleks. Python, dengan ekosistem library-nya yang kaya, menyediakan platform yang ideal untuk bereksperimen dan mengimplementasikan algoritma genetika. Memahami konsep dasar dan komponen-komponennya akan membuka pintu bagi Anda untuk mengeksplorasi solusi-solusi inovatif dalam berbagai bidang.