Kesederhanaan matematis mungkin mendasari kecepatan evolusi.

Ilmuwan komputer beralih ke biologi evolusi untuk mendapatkan inspirasi untuk menemukan solusi optimal dalam set dimensi astronomi

Mempelajari ruang luas dari solusi yang mungkin untuk masalah ini, kita dihadapkan dengan kenyataan bahwa sebagian besar jalan akan buntu. Tetapi evolusi mungkin telah menemukan cara untuk meningkatkan peluang keberhasilan.

Para kreasionis senang menegaskan bahwa evolusi harus mengumpulkan hingga 300 asam amino dalam urutan yang benar, hanya untuk menciptakan satu protein manusia berukuran sedang. Dan karena pada setiap posisi salah satu dari 20 asam amino yang mungkin dapat ditemukan, akan tampak bahwa ada lebih dari ^20.300 opsi pencarian, yang banyak urutan besarnya lebih tinggi daripada jumlah atom di Alam Semesta yang dapat diamati. Sekalipun kita menemukan redundansi di mana beberapa dari opsi ini akan setara, kemungkinan evolusi tersandung pada kombinasi yang tepat secara kebetulan dan mutasi acak tampak sangat kecil, bahkan dengan miliaran tahun yang lalu.

Kelemahan utama dari argumen semacam itu adalah bahwa evolusi tidak mengalami urutan ini secara kebetulan: proses seleksi alam menghilangkan yang tidak perlu. Selain itu, ada kemungkinan bahwa alam telah menemukan solusi lain, cara untuk mempersempit sejumlah besar probabilitas menjadi himpunan bagian kecil yang dapat dipelajari yang lebih mungkin memberikan solusi yang bermanfaat.

Ilmuwan komputer memiliki masalah serupa, yang meliputi menemukan solusi optimal di antara banyak pilihan ukuran astronomi. Beberapa dari mereka beralih ke biologi untuk mendapatkan inspirasi - terlepas dari kenyataan bahwa ahli biologi sendiri hanya mencoba memahami bagaimana hasilnya di alam.

Algoritma genetika, metode optimasi yang telah populer selama beberapa dekade, menggunakan prinsip seleksi alam untuk membuat desain baru (untuk robot, obat-obatan dan sistem transportasi, antara lain), melatih jaringan saraf, atau mengenkripsi dan mendekripsi data. Teknologi ini dimulai dengan fakta bahwa solusi acak untuk masalah tersebut dianggap sebagai beberapa "organisme" yang memiliki karakteristik tertentu, atau elemen yang "secara genetik" didefinisikan dalam kode mereka. Solusi ini tidak terlalu baik, tetapi kemudian mereka mengalami berbagai mutasi acak (dan kadang-kadang perubahan lain yang menyalin proses pengocokan gen) dan menghasilkan organisme generasi kedua, yang pada gilirannya menguji kegunaannya dalam menyelesaikan masalah. Sebagai hasilnya, setelah banyak pengulangan, proses ini mengarah pada kemunculan individu atau keputusan yang sangat beradaptasi.

Beberapa ahli membawa metode ini ke tingkat berikutnya, melakukan pemrograman genetika untuk mendapatkan program yang dapat menulis program dan menghasilkan solusi yang efektif (di sini "gen" dapat menjadi baris kode). Tujuan ini ternyata sangat sulit dicapai, karena peneliti harus mempertimbangkan jenis data dan struktur tertentu, serta banyak kondisi lainnya.

Menariknya, metode berpikir yang didasarkan pada evolusi (khususnya, pemrograman genetika) secara konseptual berpotongan dengan teori matematika yang selalu berada di suatu tempat di pinggiran biologi dan ilmu komputer. Baru-baru ini, beberapa ilmuwan telah mencoba menggunakannya untuk memahami bagaimana evolusi, alami dan buatan, dapat bekerja secara efisien, menciptakan sesuatu yang baru dan belajar cara belajar. Hal utama di sini adalah konsep khusus kompleksitas, keacakan dan informasi, yang tidak memiliki aplikasi praktis - hingga saat ini.

Monyet di belakang keyboard

Teori ini, ditemukan pada 1960-an, bekerja dengan apa yang disebut informasi algoritmik. Ini dimulai dari cara berpikir intuitif tentang probabilitas dan kompleksitas: gagasan bahwa untuk beberapa data input akan lebih sulit secara komputasi untuk menggambarkan cara membuat sesuatu daripada membuatnya. Ambil analogi yang terkenal dengan monyet, menekan tombol secara acak. Kemungkinan bahwa dia akan mencetak 15.000 digit pertama dari angka π sangat kecil - dan mereka secara eksponensial berkurang dengan meningkatnya jumlah digit.

Tetapi jika kita mengartikan penekanan tombol sebagai teks acak untuk program komputer yang menampilkan angka π, maka peluang keberhasilan, atau "probabilitas algoritmik" meningkat secara radikal. Kode untuk menampilkan 15.000 digit pertama dari angka π dalam bahasa C, misalnya, Anda dapat menyusutkan total hingga 133 karakter.

Dengan kata lain, teori informasi algoritmik mengatakan bahwa probabilitas memberikan beberapa jenis output jauh lebih tinggi ketika proses acak beroperasi pada tingkat program yang menggambarkan data ini daripada pada tingkat data itu sendiri, karena program akan pendek. Dalam pengertian ini, struktur kompleks - misalnya, fraktal - jauh lebih mudah didapat secara tidak sengaja.

Namun, masalah segera muncul dengan pendekatan ini: matematikawan menemukan bahwa kompleksitas algoritmik (juga dikenal sebagai kompleksitas Kolmogorov , dinamai setelah Andrei Nikolaevich Kolmogorov , salah satu pendiri teori) dari data keluaran yang diberikan - panjang dari program terpendek yang mungkin akan menghasilkannya - tidak dapat dihitung . Oleh karena itu, para ilmuwan komputer tidak dapat menemukan cara sempurna untuk mengompres string atau objek lain.


Kompleksitas algoritmik dari jaringan di sebelah kiri adalah tinggi, karena untuk menggambarkannya, Anda perlu membuat daftar semua sisi yang menghubungkan simpul. Di tengah, kompleksitasnya kurang, karena ketika menggambarkan jaringan ini, kita dapat menulis bahwa simpul A terhubung ke yang lain. Jaringan yang tepat memiliki paling sedikit kesulitan, karena uraiannya terdiri dari kenyataan bahwa semua simpul terhubung berpasangan oleh tepi.

Akibatnya, teori informasi algoritmik dikembangkan terutama di bidang matematika murni, di mana ia digunakan untuk mempelajari teorema terkait dan menentukan konsep keacakan dan struktur. Penggunaan praktisnya tampaknya tidak dapat diakses. "Secara matematis, ini adalah ukuran kompleksitas yang sederhana dan indah," kata ahli matematika terkenal Gregory Chaitin, salah satu pendiri teori, yang bekerja di Thomas J. Watson IBM Center dan Universitas Federal Rio de Janeiro. "Tapi dari sudut pandang penerapan di dunia nyata, itu terlihat tak tertembus."

Tapi ini tidak membuatnya mundur. Dia berharap bahwa teori ini dapat digunakan untuk memformalkan gagasan bahwa DNA berperilaku seperti program. Pada 2012, ia menerbitkan sebuah buku di mana ia menggambarkan bagaimana evolusi dapat direpresentasikan sebagai perjalanan acak melalui ruang program. Mutasi yang terjadi di sepanjang jalan ini, tulisnya, tidak tunduk pada distribusi probabilitas acak secara statistik; mereka mematuhi distribusi berdasarkan kompleksitas Kolmogorov. Tetapi dia tidak bisa memverifikasinya.

Sekarang, beberapa ilmuwan berharap untuk menghidupkan kembali teori ini dalam konteks ini, dan untuk menghubungkannya dengan biologi dan ilmu komputer secara bersamaan.

Keinginan untuk kesederhanaan

Hector Zenil , seorang spesialis IT di Institut Karolinska di Swedia, adalah salah satu dari mereka yang mencoba menghidupkan kembali teori ini. Dia bekerja bersama dengan peneliti lain untuk menggunakan kompleksitas Kolmogorov sebagai metrik untuk menganalisis kompleksitas jaringan biologis - misalnya, jaringan pengatur gen atau interaksi protein dalam sel. Para peneliti secara kasar memperkirakan konten algoritmik jaringan (nilai pastinya tidak dapat dihitung), kemudian mereka memutasikan jaringan dan memeriksa seberapa besar dampaknya terhadap kompleksitas Kolmogorov. Mereka berharap bahwa metode ini akan memberi mereka gagasan tentang kepentingan relatif berbagai elemen jaringan, dan respons fungsionalnya terhadap perubahan yang disengaja.


Ahli matematika terkenal Gregory Chaitin, salah satu pendiri teori informasi algoritmik

Dalam sebuah karya terbaru yang diposting di arxiv.org, mereka menggambarkan bahwa jika Anda membuat jaringan bergerak menuju peningkatan kompleksitas Kolmogorov - memperkenalkan mutasi yang membuat program yang menggambarkan jaringan tumbuh lebih besar - ini biasanya mengarah pada peningkatan jumlah fungsi yang dapat dilakukan jaringan, sekaligus membuatnya lebih sensitif terhadap gangguan. Ketika mereka memaksa jaringan untuk menjadi lebih sederhana, fungsi menjadi kurang, dan stabilitas meningkat.

Namun, masih belum jelas apakah kompleksitas Kolmogorov dapat memainkan peran yang lebih besar daripada alat sederhana - misalnya, seperti yang diyakini Chaytin, sebagai kekuatan pendorong utama perubahan. Terlepas dari semua masalah, informasi algoritmik tampak seperti teori biologi yang menarik. Secara tradisional, untuk menggambarkan dinamika evolusi, matematika digunakan dalam bidang genetika populasi - model statistik yang menggambarkan frekuensi gen dalam populasi. Namun, genetika populasi memiliki keterbatasannya sendiri: genetika tidak menggambarkan asal usul kehidupan dan proses transien biologis dasar lainnya, atau penampakan gen yang sama sekali baru. "Dalam teori matematika yang indah ini, ide kreativitas biologis entah bagaimana hilang," kata Chaitin. Tetapi jika kita memperhitungkan informasi algoritmik, katanya, "maka kreativitas secara alami cocok dengan gambaran besarnya."

Serta gagasan bahwa proses evolusi meningkat seiring waktu dan meningkatkan efisiensi. "Saya yakin evolusi sedang belajar," kata Daniel Polanyi , seorang spesialis IT dan profesor kecerdasan buatan di University of Hertfordshire di Inggris. "Saya tidak akan terkejut jika ini dapat diekspresikan melalui penurunan kompleksitas algoritmik asimptotik."

Zenil dan tim memutuskan untuk secara eksperimental menguji konsekuensi biologis dan komputasi dari pengaruh platform kompleksitas algoritmik. Menggunakan teknik yang sama untuk memperkirakan kompleksitas yang mereka gunakan untuk menganalisis dan mengganggu jaringan, mereka melakukan "evolusi" jaringan genetik buatan menuju tujuan spesifik - matriks nol dan yang menunjukkan interaksi gen - memilih mutasi yang menghasilkan matriks dengan kompleksitas algoritma kurang. Dengan kata lain, mereka memilih bangunan yang lebih besar.


Hector Zenil, Spesialis Ilmu Komputer, Caroline Institute

Baru-baru ini, mereka mempublikasikan hasil dalam jurnal Royal Society Open Science, dari mana mengikuti, dibandingkan dengan mutasi acak secara statistik, pemilihan mutasi mereka menyebabkan percepatan yang signifikan dalam pengembangan jaringan menuju solusi. Ciri-ciri lain juga muncul, misalnya, struktur konstan dan teratur - bagian matriks yang telah mencapai tingkat kesederhanaan tertentu, yang sulit diperbaiki oleh generasi baru. “Masing-masing daerah lebih atau kurang rentan terhadap mutasi hanya karena mereka telah mencapai tingkat kesederhanaan tertentu,” kata Zenil. "Itu sangat mirip dengan gen." Memori genetik ini telah membantu struktur besar untuk muncul lebih cepat - peneliti percaya bahwa itu mengikuti bahwa kemungkinan mutasi algoritmik dapat menyebabkan wabah keanekaragaman dan kepunahan.

"Ini berarti," kata Zenil, "bahwa akan cukup bermanfaat untuk mempertimbangkan proses komputasi dalam studi evolusi." Dia berharap untuk menggunakan pemahaman tentang keacakan dan kompleksitas ini untuk mengidentifikasi jalur pertukaran yang mungkin lebih rentan terhadap mutasi, atau untuk memahami mengapa interaksi gen tertentu dapat dikaitkan dengan penyakit seperti kanker.

Evolusi program

Zenil berharap untuk memahami jika evolusi biologis bekerja dengan aturan komputasi yang sama, tetapi sebagian besar ahli ragu. Tidak jelas mekanisme alami mana yang bertanggung jawab atas estimasi kasar kompleksitas algoritmik atau memaksa mutasi untuk berkembang dengan sengaja. Selain itu, "percaya bahwa kehidupan dikodekan sepenuhnya dalam empat huruf akan salah," kata Giuseppe Longo , seorang ahli matematika di Pusat Nasional Perancis untuk Riset Ilmiah. "DNA sangat penting, tetapi tidak masuk akal di luar sel, organisme, ekosistem." Interaksi lain berfungsi, dan penggunaan informasi algoritmik tidak dapat mencakup semua kompleksitas ini.

Namun demikian, konsep ini membangkitkan minat - khususnya karena pandangan tentang evolusi dan proses komputasi memiliki kesamaan, setidaknya tema yang sama, dengan tujuan pemrograman genetika - untuk mendapatkan program yang dapat berkembang.

Sudah ada sindiran yang cukup menarik tentang hubungan potensial antara gagasan Chaitin dan Zenil terkait dengan kompleksitas Kolmogorov dan metode pemrograman genetika. Sebagai contoh, pada tahun 2001, tim peneliti melaporkan bahwa kompleksitas output dari program genetik dibatasi oleh kompleksitas Kolmogorov dari program asli.

Tetapi sebagian besar, kompleksitas Kolmogorov tidak berperan dalam upaya para ilmuwan komputer untuk memahami ide-ide ini. Mereka mencoba cara lain untuk mengubah genetika dan mutasi. Beberapa kelompok mengubah kecepatan mutasi, yang lain memaksa sistem untuk cenderung mutasi yang menggantikan potongan kode besar. "Orang-orang telah menghasilkan puluhan, dan mungkin ratusan, versi mutasi dan genotipe yang berbeda," kata Lee Spector , seorang spesialis IT di Hampshire College di Massachusetts. Spector baru-baru ini memimpin sebuah tim yang menunjukkan manfaat dari menambahkan dan menghilangkan mutasi di seluruh genom tubuh dibandingkan penggantian langsung satu gen dengan gen lainnya. Jenis operator genetik baru ini secara eksponensial meningkatkan jumlah jalur melalui ruang pencarian genetik dan akhirnya menghasilkan solusi yang lebih baik.


Lee Spector, Spesialis Komputer di Hampshire College, Massachusetts

Namun, banyak peneliti pergi ke arah yang berlawanan, dalam mencari cara cerdik untuk mempercepat proses, mempersempit bidang pencarian, tetapi tidak membatasi begitu banyak sehingga pencarian akan kehilangan hasil yang optimal. Satu ide adalah untuk membuat kesederhanaan menjadi tujuan: pada 1960-an, Eugene Wigner mencatat "efektivitas matematika yang tidak masuk akal dalam ilmu alam," dan ilmuwan komputer menemukan bahwa model yang lebih sederhana dan lebih elegan lebih efisien dan lebih sering diterapkan. "Pertanyaannya adalah," kata Spector, "apakah fakta ini memberi tahu kita sesuatu yang dalam tentang struktur Semesta, atau tidak?" Dan apakah itu akan bermanfaat bagi kita? "

Dia juga memperingatkan bahwa upaya untuk mendorong program yang berevolusi ke kesederhanaan dapat merusak: program yang memberi penghargaan untuk keringkasan dapat mengurangi apa yang tampak seperti sampah sekarang, tetapi dapat berguna bagi generasi mendatang, yang menghasilkan solusi optimal yang dikorbankan. "Dan kita terjebak," katanya.

Namun, kesederhanaan tetap menjadi tujuan yang menggiurkan, yang, apalagi, telah menunjukkan kegunaannya. Dalam sebuah makalah yang diterbitkan tahun lalu, Spector dan rekan menemukan bahwa jika Anda mengurangi ukuran program - kadang-kadang hanya sebesar 25% dari panjang aslinya - setelah menerapkan teknik pemrograman genetika, maka program-program tersebut mengatasi dengan lebih baik data baru dan dapat digunakan pada kisaran umum masalah.

Secara khusus, karena ini, ia memantau pekerjaan di bidang teori informasi algoritmik, meskipun ia mengatakan bahwa dampaknya pada bidang penelitian ini belum terlihat.

Belajar dari kehidupan

Mungkin tim Zenil mengambil langkah pertama dalam mencari pengaruh ini - namun, untuk aplikasi realistis dari pekerjaan mereka, pertama-tama mereka perlu menguji metode mereka pada jenis masalah pencarian lainnya.

Namun, "mereka secara meyakinkan menunjukkan perlunya kendala berdasarkan pada struktur," kata Larisa Albantakis , seorang ilmuwan saraf dan ahli teori di University of Wisconsin, yang juga bekerja untuk mempercepat algoritma genetika dengan membatasi ruang pencarian. "Alam terstruktur, dan jika Anda menganggap ini sebagai titik awal, bodoh jika mencoba menguji semua kemungkinan mutasi yang homogen." Dan dia menambahkan: "Segala sesuatu yang masuk akal bagi kami entah bagaimana terstruktur."

Dan meskipun Spector skeptis bahwa karya Zenil dapat diterapkan pada sesuatu di luar ruang lingkup tugas khusus yang ia pelajari, "teori informasi yang mendasari konsep mereka menarik dan berpotensi sangat penting," katanya. "Tampaknya menarik bagiku sebagian karena terlihat entah bagaimana asing." Mungkin ada ide yang tidak diketahui oleh kawan-kawan dari komunitas kami. ” Memang, informasi algoritmik berkaitan dengan beragam gagasan yang mungkin tidak dimasukkan oleh beberapa pakar pemrograman genetika dalam karya mereka, misalnya, sifat evolusi yang tidak terbatas.

"Saya memiliki perasaan kuat akan sesuatu yang penting di bidang ini," kata Spector. Namun, ia menambahkan, sejauh ini "ada jarak yang sangat besar antara pekerjaan mereka dan aplikasi praktis."

"Gagasan membayangkan hidup sebagai program yang berkembang sangat bermanfaat," kata Chaitin, meskipun nilainya masih terlalu dini untuk ditentukan. Apakah kita berbicara tentang kehidupan buatan, atau biologis, "kita perlu melihat sejauh mana kita bisa melangkah."