Apakah Algoritma Genetika cocok untuk masalah seperti masalah Knuth?
Kita semua tahu bahwa Algoritma Genetika dapat memberikan solusi yang optimal atau mendekati optimal. Jadi, dalam beberapa masalah seperti NP-hard, dengan trade-off antara waktu dan solusi optimal, solusi yang mendekati optimal sudah cukup baik.
Karena tidak ada jaminan untuk menemukan solusi optimal, apakah GA dianggap sebagai pilihan yang baik untuk menyelesaikan masalah Knuth?
Menurut Kecerdasan Buatan: Pendekatan modern (edisi ketiga), bagian 3.2 (p.73):
Knuth menduga bahwa, dimulai dengan angka 4, urutan operasi faktorial, akar kuadrat, dan lantai akan mencapai bilangan bulat positif yang diinginkan.
Misalnya, 5 dapat dicapai dari 4:
lantai (sqrt (sqrt (sqrt (sqrt (sqrt ((4!)!))))))
Jadi, jika kita memiliki bilangan (5) dan kita ingin mengetahui urutan operasi dari 3 yang disebutkan untuk mencapai nomor yang ditentukan, setiap gen kromosom akan menjadi bilangan yang mewakili operasi tertentu dengan nomor tambahan untuk (tidak ada operasi) dan fungsi kebugaran akan menjadi perbedaan mutlak antara bilangan yang diberikan dan bilangan yang kita peroleh dari penerapan operasi dalam urutan tertentu untuk setiap kromosom (ke min). Mari kita pertimbangkan bahwa jumlah iterasi (generasi) dilakukan tanpa solusi optimal dan jumlah terdekat yang kita miliki adalah 4 (dengan fitness 1), masalahnya adalah kita bisa mendapatkan 4 dari penerapan tidak ada operasi pada 4 sedangkan untuk 5 kita perlu banyak operasi, sehingga solusi yang mendekati optimal bahkan tidak mendekati solusi.
Jadi, apakah GA tidak cocok untuk masalah seperti ini? Atau representasi kromosom yang disarankan dan fungsi kebugaran kurang baik?
Jawaban
Sebelum mencoba menjawab pertanyaan Anda lebih langsung, izinkan saya mengklarifikasi sesuatu.
Orang sering menggunakan istilah algoritme genetika (GAs), tetapi, dalam banyak kasus, yang dimaksud sebenarnya adalah algoritme evolusioner (EA), yang merupakan kumpulan algoritme pengoptimalan berbasis populasi (yaitu beberapa solusi dipertahankan pada saat yang sama) dan algoritme pengoptimalan dan pendekatan yang terinspirasi oleh Darwinisme dan survival of the fittest . GAs adalah salah satu pendekatan ini, di mana kromosomnya biner dan Anda memiliki operasi mutasi dan cross-over. Ada pendekatan lain, seperti strategi evolusi atau pemrograman genetik .
Seperti yang juga Anda perhatikan, EA adalah meta-heuristik, dan, meskipun ada beberapa penelitian tentang properti konvergensi [ 1 ], dalam praktiknya, mereka mungkin tidak bertemu. Namun, ketika pendekatan potensial lainnya gagal, EA pasti berguna.
Dalam kasus Anda, masalahnya sebenarnya adalah mencari ekspresi bentuk tertutup (atau analitis ) dari suatu fungsi, yang terdiri dari fungsi lain yang lebih kecil. Untuk itulah pemrograman genetik (khususnya, GP berbasis pohon) diciptakan. Faktanya, masalah Knuth adalah contoh khusus dari masalah regresi simbolis , yang merupakan masalah khas yang diterapkan GP. Jadi, GP mungkin adalah pendekatan pertama yang harus Anda coba.
Sementara itu, saya telah mengimplementasikan program sederhana di DEAP yang mencoba memecahkan masalah Knuth. Lihat di sini . Kesesuaian solusi terbaik yang telah ditemukan sejauh ini (dengan beberapa seed) adalah 4 dan solusinya adalah floor(sqrt(float(sqrt(4))))(di sini floathanya mengubah input menjadi bilangan floating-point, untuk memastikan keamanan tipe). Saya menggunakan perbedaan tersebut sebagai fungsi kebugaran dan menjalankan algoritme GP selama 100 generasi dengan 100 individu untuk setiap generasi (yang tidak banyak!). Saya tidak banyak men-tweak hyper-parameternya, jadi, mungkin, dengan seed dan hyper-parameter yang tepat, Anda dapat menemukan solusi yang tepat.
Untuk mengatasi masalah Anda, pada prinsipnya, Anda dapat menggunakan pengkodean itu, tetapi, seperti yang Anda perhatikan, GA memang bisa kembali $4$ sebagai solusi terbaik (yang sebenarnya tidak terlalu jauh dari $5$), yang dapat Anda hindari dari pembunuhan saya, pada setiap generasi, setiap individu yang memiliki nilai itu.
Saya tidak menghabiskan terlalu banyak waktu untuk implementasi saya dan memikirkan masalah ini, tetapi, seperti yang saya katakan di atas, bahkan dengan pemrograman genetik dan hanya menggunakan operasi Knuth, itu bisa terjebak dalam optimasi lokal. Anda dapat mencoba menambah implementasi saya (atau Anda) dengan operasi lain, seperti perkalian dan penjumlahan, dan melihat apakah ada yang membaik.