Draw with ants: gambar prosedural menggunakan algoritma optimisasi koloni semut

Kenapa aku ingin menggambar dengan semut

Saya ingin membuat karya seni mengeksplorasi kompleksitas desain perangkat lunak. Ketika saya menyajikan basis kode besar, saya berpikir tentang kompleksitas yang timbul secara independen dan bagian-bagian yang saling terkait dan saling terkait. Bentuk umumnya, demikian, muncul dari tindakan banyak kepribadian individu.

Saya berpikir tentang bagaimana menyajikan ini secara grafis, dan salah satu gambar yang menemukan respons dalam diri saya adalah gambar koloni semut. Semut adalah contoh yang bagus dari kompleksitas yang muncul (muncul). Tidak ada satu pun semut yang menjadi arsitek, tetapi bersama-sama mereka membangun struktur rumit yang luar biasa.

Skema formicaria. Sumber: Wikimedia Commons .

Saya mulai dengan mencari informasi tentang simulasi koloni semut. Jelas, ada literatur tentang ini, dan itu indah . Tetapi triknya adalah bahwa anthill muncul sebagian tergantung pada fisika pasir dan bumi di mana mereka dibangun - karena penciptaan mereka tergantung pada bagaimana partikel akan ditempatkan ketika semut meletakkannya. Saya ingin membuat sesuatu dalam 2D, jadi saya mencoba langsung ke simulasi tanpa menulis kode fisika pasir, yaitu, saya harus meninggalkan simulasi fisik sarang semut.

Karena itu, saya mulai mencari lagi, dan mereka membawa saya ke kelas simulasi semut yang sama sekali berbeda :algoritma optimasi koloni semut (algoritma koloni semut) .

Optimalisasi koloni semut adalah algoritma agen yang digunakan untuk memecahkan masalah menemukan jalur terpendek antara dua titik grafik. "Agen" berarti bahwa algoritma terdiri dari prosedur terpisah (dalam hal ini, "semut"), perilaku yang muncul yang memecahkan masalah.

Ini bekerja sangat sederhana. Setiap semut meninggalkan jejak "feromon" di jalurnya. Semut meninggalkan satu jenis feromon setelah meninggalkan sarang semut dan yang lainnya ketika mereka menemukan makanan. Semut pencari makanan mencari jejak feromon “makanan”, sementara mereka yang mencari sarang semut mencari jejak feromon “rumah”.

Semut yang menemukan dirinya di jalur yang lebih pendek dapat menempuh rute lebih cepat dari rumah ke makanan dan sebaliknya. Ini berarti mereka akan membuat lapisan feromon yang lebih jenuh. Semut yang bergerak lebih lama akan lebih memilih lintasan yang lebih kaya dan bergerak di lintasan yang lebih pendek. Setiap semut individu bekerja sesuai dengan aturan yang sangat sederhana, tetapi seiring waktu semut menemukan jalur yang lebih optimal antara dua titik.

Simulasi

Saya menulis simulator semut saya pada Pemrosesan 3. Saya memulai implementasi saya sendiri dengan mensimulasikan kode dari pos luar biasa ini oleh Gregory Brown .

Setelah semut mulai bergerak, saya mulai memperluas dan memodifikasi kode sehingga berfungsi lebih baik di grid piksel yang lebih besar. Saya ingin mendapatkan simulasi yang terlihat menarik (belum tentu efektif ) dan itu menentukan pekerjaan saya pada kode. Saya membuat visi yang sangat mendasar untuk semut sehingga setiap semut dapat melihat beberapa piksel di depan. Saya menambahkan kematian dan kelahiran kembali semut agar mereka tidak secara acak menyebar ke seluruh ruang. Akhirnya, saya membuat semut sedikit bodoh: mereka meninggalkan feromon terus-menerus, bahkan jika pencarian tidak berhasil, yang mirip dengan perilaku nyata semut.

Di sini Anda dapat memainkan port simulasi di p5.js tepat di browser Anda!

Anda juga dapat melihat kode sumber porting di Github.

Yang paling penting dalam simulasi, saya terpesona oleh bentuk yang indah, aneh dan kompleks yang diciptakan oleh semut. Mereka tidak berbaris dalam garis lurus, tetapi membentuk lingkaran, belokan dan cabang. Yang lebih menarik lagi adalah Anda dapat mengontrol tampilan gambar yang dibuat oleh semut dengan mengubah berbagai variabel dunianya. Misalnya, Anda dapat mengubah laju penguapan feromon dan kisaran visi semut dalam piksel.

Ubah semut menjadi seni

Setelah simulasi mulai bekerja, langkah selanjutnya adalah mempelajari data yang dihasilkannya. Tujuan saya adalah menciptakan semacam gambar dua dimensi, yaitu, saya perlu menangkap dan menggambar angka-angka yang dibuat oleh semut.

Pada akhirnya, saya menulis berbagai jenis output: beberapa jenis output raster dan satu vektor. Untuk menangkap hasil raster, saya melacak sel-sel yang dikunjungi oleh semut dan frekuensi kunjungan mereka. Setelah bermain dengan filter kesimpulan ini, Anda bisa mendapatkan jejak hantu dari tempat-tempat semut mengunjungi.

Contoh output raster. Jalurnya jauh lebih luas di sepanjang jalur semut yang populer dan tempat semut berkeliaran di sekitar bukit semut.

Output raster menarik, tetapi saya ingin melihat jalur individual lebih jelas, jadi saya menjelajahi kemungkinan mengekspor ke svg. Untuk hasil vektor, saya menyelamatkan sejarah setiap semut, dan ketika mereka mencapai makanan atau sarang semut, saya menuliskan cerita ini di daftar. Untuk rendering, saya mencicipi setiap jalur yang disimpan dan menjadikannya sebagai serangkaian kurva.

Contoh keluaran vektor. Di sini Anda dapat melihat jalur individual semut. Di mana ada banyak semut, garis yang sedikit tumpang tindih membentuk jalur yang lebih luas.

Hubungkan titik-titik

Saya tahu bahwa saya ingin menggambar semut yang bepergian di antara banyak titik, jadi kode untuk menghubungkan beberapa simulasi ke dalam satu gambar adalah yang pertama. Tapi lalu apa yang harus saya gambar?

Pada awalnya saya memutuskan untuk membuat grafik yang sangat literal: dimulai dengan pohon biner sederhana, kemudian beralih ke visualisasi yang lebih kompleks. Ini tampak seperti langkah alami, karena optimalisasi koloni semut memecahkan masalah menemukan jalur dalam grafik. Saya juga berpikir bahwa ini akan menjadi cara yang menarik untuk memvisualisasikan kompleksitas kode: mengapa tidak mengambil diagram UML atau grafik dependensi dan membuatnya dengan semut?

Saya sudah terbiasa dengan Graphviz , jadi saya memutuskan untuk menggunakan toolkit ini dan bahasa deskripsi grafik DOTuntuk menentukan node dan tepi simulasi saya. Graphviz memiliki mode yang menghasilkan file DOT dengan anotasi koordinat piksel. Saya menulis file parser DOT yang sangat jelek dan menggunakannya dengan file DOT beranotasi untuk mensimulasikan lokasi sarang semut dan makanan.

Eksperimen dengan pohon biner tampak menjanjikan dan memberikan tampilan organik yang sangat alami.

Pohon biner sederhana. Saya diberitahu bahwa itu seperti angiogram.

Pohon yang sedikit lebih rumit, sudah cukup dalam.

Kemudian saya mulai membuat lebih banyak grafik menggunakan berbagai basis kode sebagai input. Saya menulis beberapa skrip Python sederhana: satu mengubah pohon git menjadi file DOT, yang lain mengubah dependensi impor C menjadi file DOT.

Grafik objek di pohon objek git yang ditarik oleh semut.

Ketergantungan antara file di kernel Linux. Node dan edge dibuat menggunakan gaya grafik Graphviz persegi. Bahkan, tidak jauh lebih menarik daripada grafik acak.

Meskipun semua grafik ini menarik dan pasti rumit, saya kecewa karena sebenarnya mereka tidak mengatakan apa-apa tentang bentuk umum dari basis kode tempat mereka dibuat. Semakin saya bereksperimen dengan visualisasi kode, semakin saya menyadari bahwa membangun grafik yang menarik dari basis kode itu sendiri adalah tugas yang terpisah dan lebih sulit. Namun, saya menyukai kompleksitas grafik yang sangat besar dan kemudian saya kembali lagi ke sini.

Eksperimen saya berikutnya adalah permainan dengan bentuk sederhana. Saya membuat grafik dari garis, lingkaran, sinusoid, dan bentuk lain yang mudah dijelaskan dengan simpul dan tepi.

Poin di segmen, di sisi kanan segmen, poin lebih dekat satu sama lain.

Frekuensi gelombang sinus berbeda. Saya kira osiloskop yang cukup bagus akan keluar dari semut.

Bagi saya ruang triangulasi paling sederhana adalah yang paling menarik. Saya menghasilkan banyak titik yang terdistribusi secara merata - baik secara acak atau dengan menggambar bentuk - dan kemudian menggunakan perpustakaan pemrosesan untuk mengubah titik-titik ini menjadi triangulasi Delaunay atau diagram Voronoi. Kemudian, tulang rusuk yang dihasilkan digunakan untuk mensimulasikan semut, di mana setiap tulang rusuk menunjukkan satu "bukit semut" atau "makanan".

Digambar oleh diagram semut Voronoi.

Hal ini menyebabkan munculnya ruang penuh seluk-beluk kompleks semut yang indah, yang menggambarkan kompleksitas yang menarik minat saya jauh lebih baik.

Akhirnya, saya mendekati tugas dari sudut yang lain. Seorang teman melihat simulasi dan bertanya apa yang akan terjadi ketika semut bertabrakan dengan dinding - dapatkah mereka menghindari rintangan sederhana? Kode saya sudah tahu bagaimana menangani dinding sebagai case batas, jadi saya hanya menambahkan dinding internal, dan kemudian menghabiskan banyak waktu untuk mengajar semut bagaimana memecahkan labirin.

Jalur semut mencoba memecahkan labirin sederhana. Anda dapat melihat bentuk labirin dengan memperhatikan di mana semut tidak bisa pergi.

Saya punya ide bahwa jika semut dapat memecahkan labirin sederhana, maka Anda dapat menggabungkan mereka bersama untuk membuat karya yang lebih besar. Saya menghabiskan banyak waktu untuk menyiapkan variabel simulasi sehingga semut dapat menyelesaikannya, tetapi saya masih tidak bisa membuat mereka menyelesaikan labirin secara stabil. Pada akhirnya, semua ini berubah menjadi hanya ikal jalur semut, dibatasi oleh bentuk labirin itu sendiri.

Karya seni yang sudah jadi

Pada tahap ini, saya memutuskan untuk mengambil langkah mundur dan mempertimbangkan hasil dari semua eksperimen saya. Saya menyadari bahwa gambar yang paling menarik diperoleh dari bidang besar titik dan tepi semi-acak, dan saya memutuskan untuk membuat ini keputusan akhir saya dengan membuat simulasi untuk menggambar garis antara triangulasi Delaunay dari titik acak.

Simulasi berjalan selesai. Ini berisi banyak jalur yang dilapiskan dari tempat bintik fuzzy diperoleh.

Masalah terakhir adalah bagaimana mengubah tikungan SVG menjadi pekerjaan selesai. Dari percobaan, saya tahu bahwa saya ingin menyortir jalur dengan cara tertentu untuk menyoroti jalur dengan bentuk yang indah. Tetapi proses simulasi yang telah selesai memakan waktu satu hingga dua jam, itulah sebabnya mengapa tidak nyaman untuk mengubah variabel pada setiap percobaan.

Saya memutuskan untuk menulis diagram Pemrosesan kedua yang akan memuat hasil simulasi ke dalam SVG dan kemudian menerapkan efek visual yang saya butuhkan. Selain itu, saya ingin membuat script post-processing interaktif sehingga saya bisa bereksperimen dengan berbagai bobot dan warna garis, serta menyortir ambang batas.

Saya mencoba beberapa cara berbeda untuk mengevaluasi jalur yang seharusnya ada di latar depan dan di latar belakang. Beberapa faktor yang berbeda dihitung: jumlah persimpangan-sendiri dari garis, jumlah persimpangan dengan garis garis kemiringannya, dan kemungkinan bahwa garis akan mengikuti kemiringan yang diprediksi oleh dua titik sebelumnya.

Saya menggunakan skrip pasca pemrosesan untuk percobaan dengan bobot dan nilai estimasi yang berbeda, sampai saya mendapatkan tampilan yang saya butuhkan.

Pengaturan ambang batas untuk garis depan dan latar belakang.

Pada titik ini, menyimpan gambar ketika mengubah setiap variabel sangat membantu. Ketika saya mendekati gambar yang saya butuhkan, jauh lebih mudah untuk membandingkan sejumlah variasi kecil daripada mengubah beberapa faktor sekaligus.

Setelah pengaturan panjang dan membuat perubahan kecil, saya membuat gambar berikut dari simulasi saya:

Saya memperbesar area yang tampaknya paling menarik bagi saya, dan memotongnya untuk menciptakan keseimbangan yang baik antara ruang kosong dan diisi.

Langkah terakhir adalah pilihan bagaimana mengubah gambar ini menjadi objek fisik. Saya biasa mencetaknya secara digital sebagai poster berukuran 40 × 50 cm dan berusaha (tidak berhasil) mencetak layar pada kertas berwarna. Poster yang dicetak secara digital terlihat bagus, tetapi di masa depan saya ingin menyalin gambar sebagai bagian dari gambar. Saya menemukan gambar-gambar rumit yang bersifat meditatif dan saya pikir saya dapat mencapai efek menarik dengan menggambarnya secara manual.

Lebih banyak waktu yang dihabiskan untuk proyek ini daripada yang saya harapkan, dan ternyata lebih rumit daripada yang tampak di awal. Tetapi ini adalah cara yang bagus untuk bereksperimen dengan semua jenis komputasi geometri dan masalah algoritmik. Saya pikir ini sangat ironis bahwa saya menulis beberapa ribu baris kode untuk mengerjakan kompleksitas, tetapi saya senang itu terlihat keren dan berbicara sendiri.

Source: https://habr.com/ru/post/undefined/