Bagaimana cara mengklasifikasikan masalah optimisasi input emulator saya, dan dengan algoritma apa saya harus mendekatinya?

Karena sifat pertanyaan, saya harus memasukkan banyak informasi latar belakang (karena pertanyaan saya adalah: bagaimana saya mempersempit ini?) Yang mengatakan, itu dapat diringkas (sesuai pengetahuan saya) sebagai:

Metode apa yang ada untuk menemukan optimum lokal pada ruang pencarian kombinatorial yang sangat besar?

Latar Belakang

Dalam komunitas superplay yang dibantu alat, kami berupaya memberikan input yang dibuat secara khusus (tidak dihasilkan secara langsung) ke konsol video game atau emulator untuk meminimalkan biaya (biasanya penyelesaian waktu). Cara ini saat ini dilakukan adalah dengan memainkan permainan frame-by-frame dan menentukan input untuk masing-masing frame, sering mengulangi bagian dari run berkali-kali (misalnya, menjalankan baru - baru ini diterbitkan untuk The Legend of Zelda: Ocarina of Time memiliki total 198.590 coba lagi).

Membuat lari ini mendapatkan tujuan mereka biasanya datang ke dua faktor utama: perencanaan rute dan traversal. Yang pertama jauh lebih "kreatif" daripada yang terakhir.

Perencanaan rute menentukan arah mana pemain harus menavigasi secara keseluruhan untuk menyelesaikan permainan, dan seringkali merupakan bagian terpenting dari proses. Ini analog dengan memilih metode penyortiran mana yang akan digunakan, misalnya. Jenis gelembung terbaik di dunia tidak akan mengungguli jenis cepat pada 1 juta elemen.

Namun, dalam hasrat untuk kesempurnaan, traversal (bagaimana rute dilakukan) juga merupakan faktor yang sangat besar. Melanjutkan analoginya, ini adalah bagaimana algoritma pengurutan diimplementasikan. Beberapa rute bahkan tidak dapat dilakukan tanpa kerangka input yang sangat spesifik. Ini adalah proses bantuan alat yang paling membosankan dan inilah yang membuat produksi proses yang lengkap membutuhkan waktu berbulan-bulan atau bahkan bertahun-tahun. Ini bukan proses yang sulit (bagi manusia) karena harus mencoba variasi yang berbeda dari ide yang sama sampai seseorang dianggap yang terbaik, tetapi manusia hanya dapat mencoba begitu banyak variasi dalam rentang perhatian mereka. Penerapan mesin untuk tugas ini tampaknya tepat di sini.

Tujuan saya sekarang adalah mencoba mengotomatiskan proses traversal secara umum untuk sistem Nintendo 64 . Ruang pencarian untuk masalah ini adalah jauh terlalu besar untuk menyerang dengan pendekatan brute-force. Segmen n-frame dari N64 run memiliki 2 ^30N masukan mungkin, yang berarti hanya 30 frame dari input (kedua di 30fps) memiliki 2 ⁹⁰⁰ input mungkin; mustahil untuk menguji solusi potensial ini, apalagi solusi untuk jangka waktu dua jam penuh.

Namun, saya tidak tertarik untuk mencoba (atau lebih tepatnya, saya bahkan tidak akan mencoba untuk mencoba) total optimasi global yang berjalan penuh. Sebaliknya, saya ingin, diberi masukan awal, perkiraan lokal optimum untuk tertentu segmen dari run (atau yang terdekat n lokal optimums, untuk semacam optimasi semi-global) . Yaitu, diberi rute dan lintasan awal dari rute itu: cari tetangga dari lintasan itu untuk meminimalkan biaya, tetapi jangan turun untuk mencoba semua kasing yang bisa menyelesaikan masalah.

Program saya karena itu harus mengambil keadaan awal, aliran input, fungsi evaluasi, dan output optimum lokal dengan meminimalkan hasil evaluasi.

Kondisi saat ini

Saat ini saya memiliki semua kerangka kerja yang diurus. Ini termasuk mengevaluasi aliran input melalui manipulasi emulator, setup dan teardown, konfigurasi, dll. Dan sebagai pengganti, pengoptimal adalah algoritma genetika yang sangat mendasar. Ini hanya mengevaluasi populasi aliran input, menyimpan / menggantikan pemenang, dan menghasilkan populasi baru dengan memutasikan aliran pemenang. Proses ini berlanjut hingga beberapa kriteria arbitrer dipenuhi, seperti waktu atau nomor generasi.

Perhatikan bahwa bagian paling lambat dari program ini adalah, sejauh ini, evaluasi aliran input . Ini karena ini melibatkan meniru permainan untuk n bingkai. (Jika saya punya waktu saya akan menulis emulator saya sendiri yang menyediakan kait ke hal-hal semacam ini, tetapi untuk sekarang saya pergi dengan mensintesis pesan dan memodifikasi memori untuk emulator yang ada dari proses lain.) Di komputer utama saya, yang cukup modern, mengevaluasi 200 frame membutuhkan sekitar 14 detik. Karena itu, saya lebih suka algoritma (diberi pilihan) yang meminimalkan jumlah evaluasi fungsi.

Saya telah membuat sistem dalam kerangka kerja yang mengelola emulator secara bersamaan. Dengan demikian saya dapat mengevaluasi sejumlah aliran sekaligus dengan skala kinerja linier, tetapi secara praktis jumlah emulator yang berjalan hanya bisa 8 hingga 32 (dan 32 benar-benar mendorongnya) sebelum kinerja sistem menurun. Ini berarti (diberi pilihan), suatu algoritma yang dapat melakukan pemrosesan saat evaluasi berlangsung akan sangat bermanfaat, karena pengoptimal dapat melakukan beberapa pekerjaan berat sambil menunggu evaluasi.

Sebagai ujian, fungsi evaluasi saya (untuk game Banjo Kazooie ) adalah untuk menjumlahkan, per frame, jarak dari pemain ke titik tujuan. Ini berarti solusi optimal adalah sedekat mungkin ke titik itu. Membatasi mutasi hanya pada stik analog, butuh waktu sehari untuk mendapatkan solusi yang oke . (Ini sebelum saya menerapkan konkurensi.)

Setelah menambahkan konkurensi, saya mengaktifkan mutasi dari penekanan tombol A dan melakukan fungsi evaluasi yang sama di area yang membutuhkan lompatan. Dengan 24 emulator berjalan, kira-kira 1 jam untuk mencapai tujuan dari aliran input yang awalnya kosong, tetapi mungkin perlu berjalan selama berhari-hari untuk mencapai apa pun yang mendekati optimal.

Masalah

Masalah yang saya hadapi adalah saya tidak cukup tahu tentang bidang optimisasi matematis untuk mengetahui cara memodelkan masalah optimasi saya dengan benar ! Saya kira-kira dapat mengikuti ide konseptual dari banyak algoritma seperti yang dijelaskan di Wikipedia, misalnya, tetapi saya tidak tahu bagaimana mengkategorikan masalah saya atau memilih algoritma canggih untuk kategori itu.

Dari apa yang bisa saya katakan, saya memiliki masalah kombinatorial dengan lingkungan yang sangat besar . Selain itu, fungsi evaluasi sangat diskontinyu, tidak memiliki gradien, dan memiliki banyak dataran tinggi . Juga, tidak ada banyak kendala, meskipun saya dengan senang hati akan menambahkan kemampuan untuk mengungkapkannya jika itu membantu menyelesaikan masalah; Saya ingin mengizinkan menetapkan bahwa tombol Start tidak boleh digunakan, misalnya, tetapi ini bukan kasus umum.

Pertanyaan

Jadi pertanyaan saya adalah: bagaimana saya memodelkan ini? Apa masalah optimasi yang saya coba selesaikan? Algoritma mana yang harus saya gunakan? Saya tidak takut membaca makalah penelitian, jadi beri tahu saya apa yang harus saya baca!

Secara intuitif, algoritma genetika tidak bisa menjadi yang terbaik, karena sepertinya tidak benar-benar belajar. Misalnya, jika menekan Mulai tampaknya selalu membuat evaluasi menjadi lebih buruk (karena itu menghentikan permainan), harus ada semacam desainer atau otak yang belajar: "menekan Mulai pada titik mana pun tidak berguna." Tetapi bahkan tujuan ini tidak sepele kedengarannya, karena kadang-kadang menekan awal adalah optimal, seperti dalam apa yang disebut "jeda mundur panjang-melompat" di Super Mario 64 ! Di sini otak harus belajar pola yang jauh lebih kompleks: "menekan Mulai tidak berguna kecuali ketika pemain berada dalam keadaan yang sangat spesifik ini dan akan melanjutkan dengan beberapa kombinasi penekanan tombol ."

Sepertinya saya harus (atau mesin bisa belajar) mewakili input dengan cara lain yang lebih cocok untuk modifikasi. Input per-bingkai tampaknya terlalu terperinci, karena yang benar-benar dibutuhkan adalah "aksi", yang dapat menjangkau beberapa frame ... namun banyak penemuan dibuat berdasarkan frame-by-frame, jadi saya tidak dapat sepenuhnya mengesampingkannya (yang jeda yang disebutkan sebelumnya mundur-lompat jauh membutuhkan presisi tingkat-bingkai). Sepertinya fakta bahwa input diproses secara serial harus menjadi sesuatu yang dapat dikapitalisasi, tapi saya tidak yakin bagaimana caranya.

Saat ini saya sedang membaca tentang Pencarian Tabu (Reaktif), Pencarian Lingkungan Sangat Besar, Optimasi Berbasis Pembelajaran, dan Optimasi Koloni Semut.

Apakah masalah ini terlalu sulit untuk diatasi dengan apa pun selain algoritma genetika acak? Atau apakah itu sebenarnya masalah sepele yang sudah dipecahkan sejak lama? Terima kasih telah membaca dan terima kasih sebelumnya atas segala tanggapan.

Dari informasi yang Anda berikan dalam pertanyaan Anda, saya tidak dapat melihat bagaimana menerapkan metode optimasi standar (yang saya tahu). Objek Anda tidak terlalu rumit (lebih lanjut tentang itu nanti) tetapi fungsi target Anda adalah buruk: nilainya ditentukan oleh sistem eksternal di luar kendali Anda, tidak mungkin memiliki sifat yang bagus, dan sebagainya. Karena itu, saya pikir menggunakan algoritma genetika bukanlah pendekatan yang tidak mungkin dan bahkan mungkin pendekatan yang baik di sini; mereka sering bekerja lebih baik daripada metode lain jika Anda tidak memiliki petunjuk tentang struktur masalah Anda. Ada banyak yang perlu dipertimbangkan

• ruang objek,
• fungsi target dan
• parameter dari algoritma genetika Anda,

jadi izinkan saya menguraikan.

Apa objekmu

Anda telah menjawabnya: Anda sedang melihat serangkaian tindakan, yang masing-masing mengambil satu bingkai. Saya pikir ini mungkin terlalu halus; mungkin mencoba urutan tindakan, masing-masing dengan durasi (dalam jumlah bingkai). Ini akan memungkinkan untuk memiliki mutasi seperti "berjalan sedikit lebih lama" untuk memiliki probabilitas yang berbeda dari "memasukkan pers A" dengan cara alami. Cobalah yang terbaik; Anda mungkin harus mengunjungi kembali item ini setelah memikirkan bahan-bahan lainnya.

Apa fungsi target Anda?

Yang ini sangat penting. Apa yang ingin Anda optimalkan? Waktu untuk tujuan? Jumlah tindakan berbeda? Jumlah bintang yang dikumpulkan? Kombinasi beberapa faktor? Segera setelah Anda mendapatkan beberapa target, segalanya menjadi berbulu - di sana (biasanya) tidak ada lagi optima!

Anda menyebutkan waktu ke tujuan. Ini sepertinya bukan fungsi target yang baik sama sekali. Mengapa? Karena sebagian besar urutan bahkan tidak akan mencapai tujuan sehingga mereka akan bottom-line ke beberapa konstan, menciptakan lanskap kebugaran seperti ini (sketsa konseptual dalam satu dimensi):

^{[ sumber ]}

$0$$0$

$\qquad \displaystyle \frac{1}{1 + \text{final distance to goal}} + \frac{1}{1 + \text{time to goal}}$

$0$$1$$1$

Jadi, bagaimana Anda mengukur jarak? Jarak linear mungkin terlihat menggoda tetapi memiliki masalah; lagi, sinyal yang salah dapat dikirim. Pertimbangkan skenario sederhana ini:

^{[ sumber ]}

Setiap urutan yang dimulai dengan lompatan ke koridor atas meningkat hingga mencapai tempat tepat di atas gawang, tetapi itu tidak pernah benar-benar dapat mencapai tujuan! Lebih buruk lagi, di antara semua urutan yang tidak mencapai tujuan, yang naik sama baiknya dengan yang turun, sehingga GA tidak bisa menolak urutan yang jelas-jelas hancur. Dengan kata lain, jarak linear menciptakan optima lokal yang sangat buruk yang dapat menjebak GA jika ada jalan buntu di tingkat tersebut.

Oleh karena itu, saya sarankan Anda overlay grid di atas level Anda dan hubungkan poin tetangga jika karakter game dapat berpindah dari satu ke yang lain. Kemudian Anda menghitung jarak-dari-tujuan dengan panjang jalur terpendek dari titik terdekat ke tempat urutan karakter ke titik terdekat dengan tujuan. Ini mudah untuk dihitung dan berjalan ke deadend (optima lokal) segera dihukum¹. Tentu saja Anda memerlukan akses ke data level, tetapi saya menganggap Anda memilikinya.

Bagaimana cara kerja GA Anda?

Sekarang kita bisa sampai ke algoritma genetika yang sebenarnya. Pertimbangan utama adalah populasi, seleksi, reproduksi / mutasi dan kriteria berhenti.

Populasi

Berapa besar populasi Anda nantinya? Jika terlalu kecil, mungkin tidak memberikan keragaman yang diperlukan untuk mencapai solusi yang baik. Jika terlalu besar, Anda cenderung membawa sampah tak berguna, memperlambat proses.

Bagaimana Anda menginisialisasi populasi Anda? Apakah Anda memilih urutan tindakan acak? Jika demikian, dengan panjang berapa? Apakah Anda memiliki (kecil) sejumlah solusi yang masuk akal dan dihasilkan secara manual, mungkin sedemikian sehingga mencapai tujuan?

Pilihan

$k$

Konsep inti di sini adalah tekanan seleksi : seberapa sulit untuk bertahan hidup? Buat terlalu kecil dan Anda tidak membuang solusi omong kosong. Buat terlalu tinggi dan Anda membuat perubahan (khususnya bergerak di antara optima lokal) sulit.

Reproduksi dan Mutasi

Setelah Anda memilih selamat dari satu putaran, Anda harus membuat generasi berikutnya dari mereka (apakah orang tua bertahan dan merupakan bagian dari generasi berikutnya?). Ada dua strategi utama: mutasi dan rekombinasi.

Mutasi cukup jelas, meskipun spesifiknya dapat berbeda. Untuk setiap posisi dalam urutan individu, mutasikan dengan beberapa probabilitas. Anda dapat melakukan ini secara independen untuk setiap posisi, atau memilih jumlah mutasi secara acak, atau Anda dapat melakukan mutasi berbeda dengan probabilitas yang berbeda (seperti memasukkan elemen baru, menghapus satu, mengubah satu, ...). Mutasi biasanya tentang perubahan kecil .

Rekombinasi, yang menggabungkan aspek dari dua atau lebih solusi untuk yang baru, lebih rumit tetapi dapat memungkinkan langkah besar , yaitu meninggalkan satu "gunung kebugaran" dan bergerak langsung ke lereng yang lain (yang mungkin lebih tinggi). Ide klasik adalah crossover ; Saya tidak tahu apakah itu masuk akal di sini (bagi saya tampaknya menukar awalan dari urutan yang diberikan untuk sesuatu yang lain kemungkinan besar akan merendahkan sufiks). Mungkin Anda bisa menggunakan pengetahuan tentang level dan posisi karakter gim di berbagai titik dalam urutan untuk memandu ini, yaitu membuat titik crossover hanya di mana karakter berada di posisi yang sama di kedua urutan.

Penghentian

$N$$k$$1$$n$

Seperti yang Anda lihat, semua hal ini saling terkait untuk mempengaruhi kinerja yang sebenarnya. Jika Anda menjalankan beberapa populasi secara paralel, Anda bahkan dapat berpikir tentang menerapkan pergeseran genetik akibat migrasi dan / atau bencana. Ada sedikit teori untuk memandu jalan Anda, jadi Anda harus mencoba pengaturan yang berbeda dan mencari tahu di mana Anda mendapatkannya. Semoga apa yang berhasil untuk satu level juga akan bekerja untuk orang lain. Selamat bermain-main!

Nota bene: Lihat BoxCar 2D dalam terang di atas. Mereka melakukan beberapa hal dengan cukup baik (yang lain, tidak begitu) dan Anda bisa mendapatkan intuisi tentang bagaimana parameter GA dapat mempengaruhi kinerjanya.

1. Sebenarnya, membangun urutan dengan rakus menggunakan kebugaran ini, yaitu memilih tindakan yang meminimalkan jarak ke sasaran dari semua tindakan selanjutnya yang mungkin, dapat bekerja dengan cukup baik. Coba itu sebelum menggunakan GA!
2. Tentu saja, Anda sebagai pengamat selalu mengingat solusi terbaik yang pernah ada.

Untuk perincian lebih lanjut tentang metode pengoptimalan berbasis pengajaran-pembelajaran (TLBO) dan kode-kodenya, lihat makalah berikut ini:

Algoritme optimasi pembelajaran berbasis pembelajaran elitis untuk memecahkan masalah optimisasi terbatas yang rumit oleh R. Venkata Rao dan V. Patel; Jurnal Internasional Komputasi Teknik Industri 3 (4): 535–560 (2012)

Untuk bacaan tambahan:

• Algoritma optimasi pembelajaran berbasis pembelajaran untuk masalah optimasi parameter nyata tidak dibatasi dan dibatasi oleh R. Venkata Rao, VJ Savsani dan J. Balic; Rekayasa Optimasi (2012)
• Optimalisasi Desain Mekanis Menggunakan Teknik Optimasi Tingkat Lanjut oleh R. Venkata Rao, JV Savsani; Springer-Verlag London (2012); ISBN 978-1-4471-2747-5
• Optimalisasi multi-objektif dari penukar panas menggunakan algoritma optimasi berbasis pembelajaran yang dimodifikasi oleh R. Venkata Rao dan V. Patel; Pemodelan Matematika Terapan (2012)
• Optimalisasi multi-objektif dari dua tahap pendingin termoelektrik menggunakan algoritma optimisasi berbasis pengajaran-pembelajaran yang dimodifikasi oleh R. Venkata Rao dan V. Patel; Aplikasi Rekayasa Kecerdasan Buatan (2012)