Algoritma genetika (atau Klien selalu raja - dan seringkali bodoh)

(versi 2, dengan kesalahan ketik yang diperbaiki - Saya harap semua orang ...)

Halo, Habr!

Sekarang dia sedang duduk, membuat prototipe dari algoritma genetika untuk seorang teman. Terinspirasi untuk membagikannya, dan beberapa pemikiran lain ...

Diberikan (dipesan pelanggan): di kerajaan tertentu , gudang memiliki 100 sel. Barang ada di dalamnya. Bagaimana cara mengambil kuantitas X untuk mengosongkan semua sel yang terlibat sampai akhir? Yaitu, Anda memiliki jenis sel [34, 10, 32, 32, 33, 41, 44, 4, 28, 23, 22, 28, 29, 14, 28, 15, 38, 49, 49, 30, 24, 18, 9, 15, 8, 17, 9, 2, 7, 30, 29, 29, 2, 28, 23, 19, 4, 15, 30, 38, 3, 14, 21, 43, 50, 50, 29, 14, 17, 12, 25, 15, 23, 28, 47, 38, 29, 7, 36, 45, 25, 6, 25, 11, 10, 1, 19, 37, 24, 27, 50, 12, 1, 1, 44, 22, 48, 13, 46, 49, 11, 33, 29, 4, 19, 33, 12, 3, 47, 27, 26, 45, 40, 37, 21, 2, 8, 41, 5, 1, 9, 5] - cara memutar, katakan, 40

Nah, Anda bisa gagal, pasti ada sesuatu yang pintar, tetapi Anda bisa menyelesaikannya dengan algoritma genetika ...


Pertanyaan pertama: mengapa mengeringkan otak Anda, karena jika Anda hanya memeriksa daftar, Anda perlu mengambil dari dua sel pertama untuk ini - yang kedua, bagaimanapun, akan menjadi sisanya. Dan Anda tidak perlu pergi jauh. Tetapi untuk melihat, klien adalah perfeksionis, ia ingin seperti di apotek. Mungkin di gudang sel bernilai emas. Itu terjadi.

Pertanyaan kedua: jika Anda mengurutkannya dalam urutan menaik, maka Anda pasti bisa menggesek lebih banyak sel ... Dalam contoh kami, ada banyak sel dengan kurang dari sepuluh sel. Mungkin, klien juga tidak mau;) Saya juga bertemu orang-orang seperti itu: Saya bos di sini. Mereka memberi tahu Anda - lakukan, jangan bertanya.

(Yah, bukan klien saya, kalau tidak saya akan kehilangan kepercayaan lagi pada pikiran manusia ...)

Ya Tuhan, bersamanya, semua orang memiliki prioritas mereka sendiri ... Kemudian kita akan berbicara tentang algoritma genetika - kita harus entah bagaimana menyelesaikan ini ... Kita akan menulis di Jawa.

Bagi mereka yang belum benar-benar mendengar tentang mereka sebelumnya: meniru Alam.

1. Encode Behaviors
2. Kami memeriksa seberapa baik setiap opsi bekerja dengan bantuan tolok ukur yang sesuai
3. Atribut terbaik mereka diteruskan ke generasi berikutnya

Pada langkah terakhir di alam, ada dua komponen: menyeberang (pertukaran karakter antara bagian yang sama dari kromosom) dan mutasi (perubahan spontan dalam kode genetik). Hai, SMA;)

Itu mungkin saja. Kami akan mengkodekan dari mana sel akan diambil, dan dari mana tidak. Kami memiliki 100 sel, jadi kromosom kami terdiri dari 100 elemen benar / salah, untuk ini saya mengambil String di mana nol dan yang akan ditulis. Mereka, tentu saja, akan menjadi 100.

Tolok ukur adalah hal terpenting dalam proses ini. Alam mencari ceruk, dan alam komputer akan mencari lubang dalam patokan Anda untuk mengelabui dan bertahan hidup. Luar biasa, jujur ​​...

Dengan semua yang dikatakan, kira-kira seperti ini:

private static int benchmark(String chromosome, boolean verbose) { int sum = 0; char[] cArr = chromosome.toCharArray(); for (int i = 0; i < cnt_bins; i++) { if (cArr[i] == '1') { sum += stock[i]; if (verbose) System.out.println("storage bin " + i + ":\t+" + stock[i] + "\t= " + sum); } if (sum == target_qty) { return 0; } } return Math.abs(target_qty - sum); } 

Idenya adalah bahwa semakin jauh kita dari angka yang diinginkan, semakin buruk. Jika kami mencetak 40, maka kami tidak melangkah lebih jauh pada kromosom, kami menang. Kami akan menyortir, tentu saja, dalam peningkatan urutan - semakin sedikit poin penalti, semakin baik.

Generasi pertama dibuat secara acak:

 // create 1st generation for (int i = 0; i < generation_size; i++) { StringWriter sw = new StringWriter(); for (int j = 0; j < cnt_bins; j++) { // take stock from this bin? sw.append(rnd.nextBoolean() ? "1" : "0"); } chromosomes.add(sw.toString()); sw.close(); } 

Karena algoritma genetika, pada kenyataannya, mendekati tujuannya, tetapi tidak selalu mencapainya, penting untuk membatasi jumlah generasi.

 for (int generationNo = 0; generationNo < maxGenerationCnt; generationNo++) { // evaluate List<SimpleEntry<String, Integer>> evaluated = new ArrayList<>(); for (int i = 0; i < chromosomes.size(); i++) { evaluated.add( new SimpleEntry<String, Integer>(chromosomes.get(i), benchmark(chromosomes.get(i), false))); } // ...    , .  ... } System.out.println("No solution found after " + maxGenerationCnt + " iterations"); 

Sortir, tinggalkan yang terbaik:

 ... // sort evaluated = evaluated.stream().sorted((e1, e2) -> Integer.compare(e1.getValue(), e2.getValue())) .collect(Collectors.toList()); System.out.println("Generation " + generationNo + "; Best / last parent / worst: " + evaluated.get(0).getValue() + " / " + evaluated.get(best_size).getValue() + " / " + evaluated.get(evaluated.size() - 1).getValue()); if (evaluated.get(0).getValue() == 0) { System.out.println("Solution found"); benchmark(evaluated.get(0).getKey(), true); System.exit(0); } // leave only the best evaluated = evaluated.subList(0, best_size); ... 

Kami membiakkan dan memperbanyak, mengembalikan ukuran populasi. Artinya, kami secara acak memilih orang tua, menggabungkan tanda-tanda yang sama (jika Anda beruntung - lihat bendera pertukaran), mutasi (bendera mutasi), tunggu keajaiban ...

 // replication List<String> parents = evaluated.stream().map(e -> e.getKey()).collect(Collectors.toList()); chromosomes.clear(); while (chromosomes.size() < generation_size) { int parent1 = rnd.nextInt(evaluated.size()); int parent2 = rnd.nextInt(evaluated.size()); char[] cArr1 = parents.get(parent1).toCharArray(); char[] cArr2 = parents.get(parent2).toCharArray(); for (int i = 0; i < cnt_bins; i++) { boolean exchange = rnd.nextDouble() < exchange_rate; if (exchange) { char c1 = cArr1[i]; char c2 = cArr2[i]; // exchange both values cArr1[i] = c2; cArr2[i] = c1; } // mutation boolean mutation = rnd.nextDouble() < mutation_rate; if (mutation) { cArr1[i] = rnd.nextBoolean() ? '1' : '0'; } mutation = rnd.nextDouble() < mutation_rate; if (mutation) { cArr2[i] = rnd.nextBoolean() ? '1' : '0'; } } chromosomes.add(new String(cArr1)); chromosomes.add(new String(cArr2)); } 

Dan akhirnya: jika Anda bingung dengan parameter - terlalu banyak mutasi, ukuran populasi terlalu kecil, dll. - Akan mandek atau bahkan memberikan semua hasil terburuk.

Ngomong-ngomong, tugas ini sering diselesaikan secara acak dan generasi berikutnya tidak diperlukan :) Jika Anda ingin menyulitkan kehidupan komputer, hapus pengembalian ini dari patokan:

 if (sum == target_qty) { return 0; } 

Ini akan menyulitkan tugas dan membuat komputer sedikit menderita ...

Semoga beruntung

m_OO_m