Membandingkan dua algoritma genetika

9

Saya memiliki dua implementasi dari algoritma genetika yang seharusnya berperilaku setara. Namun karena batasan teknis yang tidak dapat diselesaikan outputnya tidak persis sama, diberi input yang sama.

Tetap saya ingin menunjukkan bahwa tidak ada perbedaan kinerja yang signifikan.

Saya memiliki 20 kali berjalan dengan konfigurasi yang sama untuk masing-masing dari dua algoritma, menggunakan berbagai biji nomor acak awal. Untuk setiap lari dan generasi , kesesuaian kesalahan minimum dari individu terbaik dalam populasi dicatat. Algoritme menggunakan mekanisme pengawet elit, sehingga kebugaran individu terbaik menurun secara monoton. A run terdiri dari 1000 generasi, jadi saya memiliki 1000 nilai per run. Saya tidak bisa mendapatkan lebih banyak data, karena perhitungannya sangat mahal.

Tes mana yang harus saya pakai? Cara mudah mungkin hanya dengan membandingkan kesalahan pada generasi terakhir (sekali lagi, tes mana yang akan saya gunakan di sini)? Tetapi orang mungkin juga berpikir tentang membandingkan perilaku konvergensi secara umum.

nisc
sumber
Sama seperti klarifikasi: bukankah itu kasus suatu algoritma genetika mencari solusi secara acak, sehingga segmen awal dari setiap proses tidak akan menghasilkan solusi yang bermanfaat? Juga, apa yang sebenarnya Anda maksud dengan "kesalahan minimum dalam populasi"? Jika Anda maksudkan perbedaan minimum antara nilai sebenarnya yang diketahui dan solusi apa pun dari 1000 nilai dalam satu run, maka bukankah itu indikasi bias dari hasil run? Lagi pula, dalam praktiknya Anda akan menerima solusi terakhir di setiap lari dan menolak semua yang mendahuluinya, kan?
Whuber
Secara tidak sengaja saya maksudkan 1 / kebugaran, jadi saya berbicara tentang nilai individu terbaik dalam satu generasi. Saya telah mencatat nilai kebugaran individu terbaik untuk setiap generasi. Jadi saya punya 1000 * 20 * 2 angka, masing-masing sesuai dengan "kebugaran" individu terbaik dalam generasi tertentu dari lari tertentu.
Nisc
Saya kira pertanyaan awal salah, saya telah menambahkan beberapa klarifikasi ..
nisc

Jawaban:

9

Menguji algoritma stokastik bisa agak rumit!

Saya bekerja dalam sistem biologi dan ada banyak simulator stokastik tersedia untuk digunakan untuk mensimulasikan model. Menguji simulator ini rumit karena dua realisasi dari model tunggal biasanya akan berbeda.

Dalam dsmts kami telah menghitung (secara analitik) nilai dan varian yang diharapkan dari model tertentu. Kami kemudian melakukan tes hipotesis untuk menentukan apakah simulator berbeda dari kebenaran. Bagian 3 dari userguide memberikan detailnya. Pada dasarnya kami melakukan uji-t untuk nilai rata-rata dan uji chi-square untuk varian.

Dalam kasus Anda, Anda membandingkan dua simulator sehingga Anda hanya perlu menggunakan uji-t dua sampel saja.

csgillespie
sumber
Bagaimana cara saya menggunakan informasi dari semua generasi?
Nisc
Cara termudah adalah dengan melakukan beberapa tes, yaitu tes di setiap generasi, lalu gunakan Bonferroni atau koreksi fdr.
csgillespie
Ketika membandingkan pada setiap generasi, saya harus menguji pada tingkat signifikansi 1/1000 * 0,05? Bukankah itu agak kasar?
Nisc
Benar, tetapi Anda juga melakukan banyak pengujian - tidak dapat memiliki segalanya;) Anda dapat memberi peringkat nilai-p, menggunakannya sebagai panduan untuk melihat di mana kesalahan yang mungkin terjadi.
csgillespie
1
Alih-alih koreksi bonferroni, Anda selalu dapat menggunakan bonferroni holm yang lebih kuat. Lihat jawaban saya di sini: stats.stackexchange.com/questions/575/…
Henrik
4

Mungkin Anda bisa mengukur perbedaan rata-rata antara dua proses dari algoritma yang sama dengan perbedaan rata-rata antara dua proses dari algoritma yang berbeda. Tidak memecahkan masalah bagaimana mengukur perbedaan itu, tetapi mungkin merupakan masalah yang lebih mudah ditangani. Dan nilai-nilai individual dari deret waktu akan dimasukkan ke dalam perhitungan perbedaan daripada harus diperlakukan sebagai titik data individual untuk dievaluasi satu sama lain (saya juga tidak berpikir bahwa perbedaan khusus pada langkah ke-n adalah apa yang Anda benar-benar ingin membuat pernyataan tentang).

Perbarui Rincian yang berkaitan - baik fitur seri waktu mana yang Anda minati, di luar kesalahan terakhir? Saya kira Anda benar-benar memiliki tiga pertanyaan berbeda untuk dipecahkan:

  1. Apa kesamaan konstituen untuk Anda, yaitu apa yang Anda maksud ketika Anda mengatakan Anda tidak percaya dua metode berbeda?
  2. Bagaimana Anda mengukurnya - dapat dijawab setelah 1, dan
  3. Bagaimana Anda bisa menguji perbedaan yang signifikan antara kedua metode Anda?

Yang saya katakan di posting pertama adalah bahwa jawaban untuk (1) mungkin tidak mempertimbangkan perbedaan individu pada masing-masing 1000 generasi. Dan saya menyarankan untuk memberikan nilai skalar untuk setiap deret waktu atau setidaknya kesamaan antara deret waktu. Hanya dengan begitu Anda sampai pada pertanyaan statistik aktual (yang saya tahu paling sedikit tentang ketiga poin tersebut, tetapi saya disarankan untuk menggunakan uji-t berpasangan dalam pertanyaan serupa yang baru saja saya tanyakan, ketika memiliki nilai skalar per elemen).

pengguna979
sumber
terdengar masuk akal, ada lagi detail?
Nisc