Evaluation-Time Bias in Evolutionary Algorithms – Menuju AI – The Best of Tech, Science, and Engineering

Penulis: Rutuja Shivraj Pawar

Kecerdasan Buatan, Pengoptimalan

Tinjauan singkat dengan karya penelitian awal dari literatur

Foto oleh Jon Tyson di Unsplash

Algoritma Evolusioner (EA) adalah bagian dari komputasi evolusioner dalam kecerdasan buatan. Komputasi evolusioner adalah sekumpulan algoritma untuk pengoptimalan global yang terinspirasi oleh evolusi biologis. Perkembangan pesat era informasi dengan Big Data telah menyebabkan peningkatan ukuran dan kompleksitas masalah pengoptimalan. Dalam konteks EA, ini pada akhirnya menghasilkan perluasan ruang pencarian dengan evaluasi kebugaran (digunakan untuk pencarian solusi optimal) biaya komputasi individu menjadi sangat tinggi. [1].

Menyelami jauh ke dalam varian EA, kami mengamati berbagai jenis di bawah ini,

Sumber: Gambar oleh penulis

Pada artikel ini, kami akan fokus pada varian Parallel EA dengan dua jenisnya dan kemudian mendalami pemahaman masalah bias waktu evaluasi.

EA generasi tradisional diturunkan dari EA sekuensial tetapi diformulasikan untuk menginduksi paralelisme [2]. Namun, algoritma ini membutuhkan sinkronisasi dan sering dihadapkan pada masalah waktu idle ketika ada perbedaan waktu antar individu untuk mengevaluasi nilai fitnessnya. Hal ini sering kali mengakibatkan pemborosan sumber daya CPU dan menghambat paralelisasi. Untuk mengatasi masalah ini kami memiliki EA asynchronous [2] yang didasarkan pada model kondisi-mapan di mana generasi satu per satu dari keturunan individu berlangsung diikuti dengan evaluasi kebugaran mereka. Begitu evaluasi kesesuaian untuk seorang individu selesai, ia dapat segera bersaing untuk mendapatkan tempat dalam populasi yang ada tanpa perlu sinkronisasi. Proses ini pada akhirnya membantu dalam pemanfaatan sumber daya komputasi yang efektif dan menginduksi pemrosesan paralel yang efisien. Namun, EA asinkron dihadapkan pada apa yang disebut masalah bias Waktu Evaluasi.

Evaluasi-Bias Waktu [3] adalah fenomena yang dapat diwariskan di mana individu yang dengan cepat mengevaluasi dirinya sendiri dibandingkan dengan individu lain dalam suatu populasi memiliki keunggulan reproduktif dalam suatu EA. Hal ini pada akhirnya menempatkan individu yang mengevaluasi lama pada posisi yang tidak menguntungkan karena individu yang mengevaluasi cepat memiliki lebih banyak kesempatan untuk menghasilkan keturunan. Hal ini juga mengarah pada pencarian solusi yang bias ke daerah evaluasi cepat dan jauh dari daerah evaluasi ruang pencarian yang lama dan dengan demikian menghasilkan konvergensi prematur. Namun, terkadang bias waktu evaluasi terbukti berguna dalam algoritme jika semua individu yang mengevaluasi lebih cepat lebih baik, tetapi pada saat yang sama dapat menghalangi konvergensi jika semuanya lebih buruk. [4]. Patut diperhatikan, dalam eksperimen yang dilakukan di lanskap kebugaran datar, evaluasi tidak menunjukkan bukti adanya bias terhadap wilayah yang lebih cepat atau lebih lambat, yang menunjukkan bahwa bias tersebut mungkin kecil atau dapat diabaikan dalam kondisi tertentu. [2]. Sebagai solusi dan bergantung pada skenario, terkadang menghukum solusi berkualitas tinggi dengan menetapkannya dengan waktu evaluasi yang lama dapat membantu mencegah konvergensi dini dari EA dan meningkatkan kinerjanya. [5].

Diilustrasikan di bawah ini adalah dua pekerjaan penelitian awal yang dilakukan untuk memecahkan masalah bias waktu evaluasi dan meletakkan dasar untuk arah penelitian lebih lanjut,

Quasi-Generational Asynchronous Evolutionary Algorithm (QGEA)

QGEA [6] menggabungkan beberapa aspek EA sinkron dan asinkron sebagai algoritme baru untuk yang terbaik dari kedua dunia. Algoritma yang diusulkan ini berfungsi sebagai solusi perantara yang tidak akan menimbulkan waktu idle atau bias yang signifikan terhadap solusi cepat. QGEA menggunakan skema evaluasi asinkron untuk mengevaluasi individu dalam populasi yang meminimalkan waktu idle. Namun, individu yang dievaluasi tidak ditambahkan langsung ke populasi induk. Sebaliknya, populasi anak yang terpisah dibuat dan mereka ditambahkan di sana satu per satu. Setelah kapasitas penuh dari populasi anak tercapai, itu menggantikan populasi induk, dan populasi anak baru kemudian dibuat. Perbedaan antara algoritme ini dan EA tradisional terletak pada kenyataan bahwa algoritme ini menghasilkan lebih banyak anak dari setiap kumpulan orang tua, yang selanjutnya membantu menjaga semua prosesor tetap sibuk. Perubahan populasi terjadi secara generasi dengan penggantian populasi sepenuhnya setelah setiap langkah jumlah yang ditentukan.

Algoritma Evolusioner dengan Generasi Interleaving (IGEA)

IGEA [4] setara dengan EA generasi standar tetapi memungkinkan pemanfaatan yang lebih baik dari sumber daya komputasi dengan menyisipkan evaluasi kesesuaian dari generasi yang berbeda, sehingga menghindari bias waktu evaluasi dan menunjukkan potensi paralelisasi yang lebih baik. Ide utama dari algoritme terletak pada kenyataan bahwa beberapa individu dari generasi berikutnya dapat dihasilkan sebelum generasi saat ini dievaluasi sepenuhnya. Alih-alih menimbulkan waktu idle CPU seperti pada EA standar, IGEA mencoba menghilangkan ini melalui evaluasi individu yang dihasilkan oleh CPU idle dan dengan demikian tidak memerlukan node prosesor untuk menunggu hingga individu yang mengevaluasi yang lebih lambat menyelesaikan evaluasi mereka. Ada dua varian IGEA yaitu versi koma (λ, λ) dan versi plus (λ + λ). Versi koma memiliki populasi λ dan pada setiap generasi menghasilkan keturunan λ untuk digunakan pada generasi berikutnya. Versi plus menghasilkan λ keturunan dari induk λ, kemudian λ individu dari gabungan keturunan dan populasi induk dipilih untuk generasi selanjutnya.

Namun berdasarkan evaluasi eksperimental mereka, kedua pendekatan awal menunjukkan keterbatasan tertentu, pendekatan QGEA tidak memecahkan masalah bias waktu evaluasi serta menunjukkan tingkat konvergensi yang sangat rendah. Pendekatan IGEA tidak didasarkan pada skema EA asinkron dan karenanya tidak menunjukkan bias waktu evaluasi. Interleaving dari generasi hanya dapat bekerja jika pemilihan individu tidak mengharuskan semua individu untuk dievaluasi sebelum pelaksanaan. Oleh karena itu, pendekatan IGEA bertujuan untuk menghilangkan masalah bias waktu evaluasi dengan menyisipkan generasi EA generasi standar, tetapi pada saat yang sama tidak memungkinkan untuk penggunaan paralelisme tak terbatas seperti EA asinkron.

Baru-baru ini pada tahun lalu, kami memiliki dua karya penelitian lagi yang diterbitkan di bidang ini. Strategi pemilihan induk baru untuk mengurangi efek bias waktu evaluasi dengan mempertimbangkan kemajuan pencarian setiap solusi yang diusulkan [7]. Metode yang diusulkan ini ketika dievaluasi secara eksperimental menggunakan asynchronous NSGA-III [8], Membantu mengurangi waktu komputasi dan efek bias waktu evaluasi. Pekerjaan penelitian lain [9] dibangun di atas IGEA [4] dan mengusulkan solusi yang difokuskan pada peningkatan penggunaan CPU melalui konsep evaluasi prioritas dari keturunan tentatif di IGEA.

Meringkas, seperti yang diamati dari literatur, tidak ada solusi konkret yang diidentifikasi terhadap penghapusan total bias waktu evaluasi. Oleh karena itu, penelitian tentang metode yang efisien untuk penghapusan yang efektif dari masalah bias waktu evaluasi dalam asynchronous EA dan studi tentang pertanyaan penelitian terbuka untuk memprediksi bagaimana bias waktu evaluasi akan mempengaruhi kinerja EA mengingat jenis masalah tertentu dan kondisi tetap a topik penelitian hotspot.

Referensi

[1] Gong, YJ, Chen, WN, Zhan, ZH, Zhang, J., Li, Y., Zhang, Q. dan Li, JJ, 2015. Mendistribusikan algoritme evolusioner dan modelnya: Survei state-of-the- seni. Komputasi Lunak Terapan, 34, hlm. 286–300.

[2] Scott, EO dan De Jong, KA, 2015, Januari. Memahami algoritma evolusioner asinkron sederhana. Dalam Prosiding Konferensi ACM 2015 tentang Dasar-dasar Algoritma Genetik XIII (hlm. 85–98).

[3] Scott, EO dan De Jong, KA, 2015, Juli. Bias waktu evaluasi dalam algoritme evolusioner asinkron. Dalam Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation (hlm. 1209–1212).

[4] Pilát, M. dan Neruda, R., 2017, Juli. Algoritma evolusi paralel dengan generasi interleaving. Dalam Proceedings of the Genetic and Evolutionary Computation Conference (pp. 865-872).

[5] Yagoubi, M., Thobois, L. dan Schoenauer, M., 2011, June. Algoritma multi-tujuan evolusioner asynchronous dengan biaya evaluasi yang heterogen. Pada tahun 2011 Kongres IEEE dari Evolutionary Computation (CEC) (hlm. 21-28). IEEE.

[6] Scott, EO dan De Jong, KA, 2016, Juli. Bias waktu evaluasi dalam algoritme evolusioner asinkron semu generasi dan kondisi mapan. Dalam Proceedings of the Genetic and Evolutionary Computation Conference 2016 (hlm. 845–852).

[7] Harada, T., 2020, Desember. Kemajuan Pencarian Pemilihan Induk Bergantung untuk Menghindari Bias Waktu Evaluasi dalam Algoritma Evolusi Multi-Objektif Paralel Asinkron. Pada 2020 Seri Simposium IEEE tentang Kecerdasan Komputasi (SSCI) (hlm. 1013-1020). IEEE.

[8] Deb, K. dan Jain, H., 2013. Algoritme pengoptimalan banyak tujuan evolusioner menggunakan pendekatan pengurutan nondominated berbasis referensi, bagian I: memecahkan masalah dengan batasan kotak. Transaksi IEEE pada komputasi evolusioner, 18 (4), pp.577-601.

[9] Noguchi, H., Sonoda, A., Harada, T. dan Thawonmas, R., 2020, September. Algoritma Evolusi Generasi Interleaving dengan Evaluasi Prioritas dari Keturunan Tentatif. Pada Konferensi Tahunan ke-59 Society of Instrument and Control Engineers of Japan (SICE) tahun 2020 (hlm. 832–837). IEEE.

Evaluation-Time Bias in Evolutionary Algorithms awalnya diterbitkan di Towards AI on Medium, di mana orang-orang melanjutkan percakapan dengan menyoroti dan menanggapi cerita ini.

Diterbitkan melalui Towards AI