Mengapa penelitian tentang algoritma genetika melambat?

45

Saat membahas beberapa topik tingkat intro hari ini, termasuk penggunaan algoritma genetika; Saya diberitahu bahwa penelitian sangat lambat di bidang ini. Alasan yang diberikan adalah bahwa kebanyakan orang berfokus pada pembelajaran mesin dan data mining.
Pembaruan: Apakah ini akurat? Dan jika demikian, apa kelebihan ML / DM jika dibandingkan dengan GA?

Fosil Karat
sumber
2
Harap rumuskan kembali pertanyaan sehingga meminta lebih sedikit pendapat tetapi lebih banyak fakta (mis., Kerugian GA / EA yang semakin nyata dari waktu ke waktu).
Raphael
1
Sejauh yang saya tahu, jika banyak algoritma yang diberikan yang dapat memecahkan masalah tertentu, GA tidak akan menjadi yang terbaik dalam banyak kasus.
Strin

Jawaban:

33

Nah, pembelajaran mesin dalam arti pengenalan pola statistik dan penambangan data jelas merupakan area yang lebih panas, tapi saya tidak akan mengatakan penelitian dalam algoritma evolusioner telah melambat. Kedua area umumnya tidak diterapkan pada jenis masalah yang sama. Tidak segera jelas bagaimana pendekatan yang didorong oleh data membantu Anda, misalnya, mencari tahu cara menjadwalkan perpindahan pekerja atau paket rute terbaik dengan lebih efisien.

Metode evolusi paling sering digunakan pada masalah optimasi keras daripada pengenalan pola. Pesaing yang paling langsung adalah pendekatan riset operasi, pada dasarnya pemrograman matematika, dan bentuk lain dari pencarian heuristik seperti pencarian tabu, anil simulasi, dan puluhan algoritma lain yang secara kolektif dikenal sebagai "metaheuristik". Ada dua konferensi tahunan yang sangat besar tentang perhitungan evolusioner (GECCO dan CEC), sejumlah konferensi yang lebih kecil seperti PPSN, EMO, FOGA, dan Evostar, dan setidaknya dua jurnal berkualitas tinggi utama (Transaksi IEEE tentang Komputasi Evolusi dan MIT Press) jurnal Evolution Computation) serta sejumlah yang lebih kecil yang memasukkan EC bagian dari fokus mereka yang lebih luas.

Semua yang mengatakan, ada beberapa keuntungan bidang yang lebih umum dianggap sebagai "pembelajaran mesin" memiliki perbandingan "panas". Pertama, cenderung lebih kuat pada landasan teori, yang selalu disukai oleh para ahli matematika. Dua, kita berada dalam zaman keemasan untuk data, dan banyak metode pembelajaran mesin yang mutakhir benar-benar baru mulai bersinar ketika diberi banyak data dan banyak daya komputasi, dan dalam kedua hal, waktu dalam arti tertentu "Baik".

deong
sumber
Bisakah Anda menjelaskan / menyoroti apa jawaban Anda atas pertanyaan itu?
Raphael
Saya tidak yakin apa yang ingin Anda jelaskan secara spesifik.
deong
Jawab pertanyaan OP dengan jelas: Apa kelebihan (sulit) dari ML dibandingkan GA / EA? Atau apakah Anda mengusulkan sesuatu yang ortogonal?
Raphael
2
Saya mengatakan mereka tidak (kebanyakan) tidak berlaku untuk masalah yang sama. Keuntungan ML adalah ia bekerja sangat baik untuk pengenalan pola dan klasifikasi; keuntungan dari GAS adalah mereka bekerja pada masalah optimasi keras. Di luar itu, itu seperti meminta keuntungan mobil versus rumah. Banyak algoritma ML melibatkan penyelesaian masalah optimisasi sebagai langkah pelatihan, dan ada pendekatan pembelajaran berbasis GA (sistem pengklasifikasi pembelajaran), tetapi sebagian besar, mereka hanya area yang sepenuhnya berbeda.
deong
21

Beberapa dekade yang lalu, orang-orang berpikir bahwa algoritma genetika dan evolusi adalah swiss-army-pisau, didorong oleh hasil awal yang spektakuler. Pernyataan seperti hipotesis dasar dibuat dalam upaya untuk membuktikan bahwa mereka pada umumnya strategi yang baik.

Namun, hasil yang keras datang lambat dan sering kali serius, yang paling menonjol adalah Teorema Tanpa Makan Siang Gratis . Itu menjadi jelas bahwa algoritma genetika / evolusi sering heuristik yang layak tetapi tidak pernah optimal dalam arti apapun.

Hari ini kita tahu bahwa semakin banyak kita tahu tentang masalah masing-masing strukturnya, semakin tidak masuk akal untuk menggunakan algoritma genetik / evolusi sebagai metode lain yang menggunakan pengetahuan ini mengungguli mereka dengan besarnya. Namun, dalam kasus-kasus di mana sedikit yang diketahui tentang masalah yang dihadapi, mereka masih tetap menjadi alternatif yang layak karena mereka bekerja sama sekali.

Raphael
sumber
8
Saya merasa perlu ditekankan bahwa NFLT menetapkan "batasan" tidak hanya pada GAS, tetapi pada semua algoritma pencarian heuristik. Tak satu pun dari mereka yang hebat dalam setiap contoh, dan dalam pengertian Anda, tak satu pun dari mereka yang optimal dalam arti apa pun.
Juho
Saya ingat menggunakan algoritma genetika untuk menyelesaikan masalah aerodinamika, dan setelah berminggu-minggu perhitungan, hasilnya jauh lebih buruk daripada hasil yang diberikan oleh teori aerodinamika paling kasar. Saya memiliki kesan bahwa kecerdasan buatan dan similars sama sekali bukan pengganti untuk pengetahuan domain
user5193682
@ user9589 Keduanya tidak saling eksklusif. Pengetahuan domain dapat membantu Anda memilih dan mengatur metode heuristik.
Raphael
@ Raphael Saya akan mengatakan bahwa kecerdasan buatan membantu Anda menyesuaikan pengetahuan domain.
user5193682
13

Bagian penting dari cerita ini, seperti yang saya lihat, hilang dari jawaban lain sejauh ini:

Algoritma genetika sebagian besar berguna untuk masalah pencarian brute force.

Dalam banyak konteks, strategi optimasi yang lebih sederhana atau model inferensi (apa yang secara luas Anda sebut pembelajaran mesin) dapat bekerja dengan sangat baik, dan melakukannya jauh lebih efisien daripada pencarian brute force.

Algoritma genetika, seperti annealing yang disimulasikan, paling efektif sebagai strategi untuk menangani masalah yang sama baiknya dengan yang kita ketahui dengan masalah pencarian yang sulit (mis. NP lengkap). Domain ini cenderung sangat dibatasi oleh kekerasan intrinsik dari masalah yang mengutak-atik dan mengulangi pada faktor-faktor sederhana dalam strategi solusi, dengan meningkatkan algoritma genetika secara bertahap, sering kali tidak terlalu banyak digunakan, dan jadi tidak terlalu menarik.

jrk
sumber
12

Sampai batas tertentu, pembelajaran mesin menjadi lebih matematis dan dengan algoritma dapat 'terbukti' bekerja. Dalam beberapa hal, GAS sangat "dengan yang terjadi di sana" dan Anda tidak dapat dengan sempurna menjawab pertanyaan "jadi apa yang program Anda lakukan?" (baik di mata sebagian orang, sih).

Saya pribadi menganjurkan menggabungkan jaring saraf dan GA = GANNs. Dalam tesis kehormatan saya, saya menghasilkan algoritma prediksi obat yang pertama menggunakan NNs, kemudian GA, dan akhirnya GANN yang mengambil yang terbaik dari kedua dunia dan mengungguli kedua set lainnya. YMMV, namun.

Mark Mayo
sumber
2
Tolong beri contoh sederhana di mana keuntungan "ML" menjadi jelas untuk memberikan beberapa bukti klaim Anda. Juga, tolong berikan referensi / tautan yang tepat untuk tesis Anda.
Raphael
terkait: Neuroevolution
Franck Dernoncourt
4

Pembelajaran mesin memperkenalkan sebagian besar peralatan matematika untuk dikembangkan dan diterapkan. Algoritma genetika banyak dilakukan oleh heuristik.

om-nom-nom
sumber
2
Anda dapat membuktikan hal-hal tentang GA / EA. Tapi itu sulit. Sementara ML memiliki dasar yang kuat, mereka yang menerapkan teknik ML sering melakukannya secara ad-hoc. Jadi apakah argumen Anda hanya ada di atas kertas, atau apakah ada perbedaan dalam praktik?
Raphael