Memecahkan Masalah 5-Queen Menggunakan Algoritma Genetika – Menuju AI – Teknologi, Sains, dan Teknik Terbaik

Penulis: Arman Assankhanov

Ilmu Komputer

Apa masalah N-Queen?

Pertama-tama masalah N-Queen adalah masalah di mana kita perlu menemukan susunan ratu N di papan catur, sehingga tidak ada ratu yang dapat menyerang ratu lain di papan catur. Jadi dalam masalah 5-Ratu kita, kita perlu menempatkan 5 ratu catur pada papan catur 5 × 5 sehingga tidak ada dua ratu yang saling menyerang. Ketika kami menemukan semua kemungkinan kasus, akan terlihat seperti berikut:

Langkah-langkah yang perlu kita lakukan

Dalam tugas kita, kita perlu menyelesaikan masalah 5-Queen menggunakan Algoritma Genetika. Kita perlu menggunakan prinsip evolusi untuk menemukan solusi dari suatu masalah.

Untuk menyelesaikan masalah 5-Queen, diperlukan langkah-langkah berikut:

1) Desain kromosom
2) Inisialisasi
3) Evaluasi kebugaran
4) Seleksi
5) Crossover
6) Mutasi
7) Perbarui generasi
8) Kembali ke 3)

Mari kita jelaskan secara singkat setiap langkah dalam memecahkan masalah 5-Ratu menggunakan Algoritma Genetika.

1) Desain kromosom

Pertama, kita perlu membuat representasi kromosom. Untuk menunjukkan kromosom, cara terbaik adalah dengan merepresentasikannya sebagai daftar panjang N di mana dalam kasus kami N = 5. Nilai setiap indeks menunjukkan baris ratu dalam satu kolom. Nilai setiap indeks adalah dari 1 hingga 5.

2) Inisialisasi

Dalam proses inisialisasi, kita perlu menyusun populasi kromosom secara acak (solusi potensial) yang dibuat. Ini populasi awal, saya ambil 4 kromosom yang masing-masing memiliki panjang 5. Mereka

[5 2 4 3 5]

[4 3 5 1 4]

[2 1 3 2 4]

[5 2 3 4 1]

Secara khusus, kromosom ini dapat ditampilkan sebagai berikut di papan catur:

3) Evaluasi kebugaran

Pertama-tama, fungsi kebugaran adalah pasangan ratu yang tidak menyerang. Jadi, skor yang lebih tinggi lebih baik lebih baik bagi kita. Untuk menyelesaikan fungsi kebugaran untuk kromosom [5 2 4 3 5], Saya menetapkan setiap ratu secara unik sebagai Q1, Q2, Q3, Q4 dan Q5. Dan untuk mencari nilai fungsi fitness saya membuat persamaan sebagai berikut:

Fungsi kebugaran = F1 + F2 + F3 + F4 + F5

dimana:

F1 = jumlah pasang ratu yang tidak menyerang dengan ratu Q1.

F2 = jumlah pasang ratu yang tidak menyerang dengan ratu Q2.

F3 = jumlah pasang ratu yang tidak menyerang dengan ratu Q3.

F4 = jumlah pasang ratu yang tidak menyerang dengan ratu Q4.

F5 = jumlah pasang ratu yang tidak menyerang dengan ratu Q5.

Di sini misalnya jika kita sudah menghitung pasangan Q1 dan Q2 ke F1, sebaiknya kita tidak menghitung pasangan Q2 dan Q1 ke F2 yang sama.

Jadi kami menemukan itu untuk kromosom [5 2 4 3 5] fungsi kebugaran akan sama dengan 7.

Kita harus mengevaluasi semua individu populasi (kromosom) menggunakan fungsi kebugaran. Jadi fungsi kebugarannya adalah sebagai berikut:

[5 2 4 3 5] fungsi kebugaran = 7

[4 3 5 1 4] fungsi kebugaran = 6

[2 1 3 2 4] fungsi kebugaran = 6

[5 2 3 4 1] fungsi kebugaran = 5

Kemudian kita perlu menghitung probabilitas yang dipilih dari fungsi fitness. Ini akan diperlukan untuk langkah pemilihan berikutnya. Pertama, kita perlu menambahkan semua fungsi kebugaran yang akan sama seperti berikut ini:

7 + 6 + 6 + 5 = 24

Kemudian kita perlu menghitung probabilitas yang dipilih dari fungsi fitness. Kita perlu membagi fungsi fitness dengan menjumlahkan fungsi fitness dan mengalikannya menjadi 100%.

[5 2 4 3 5] probabilitas terpilih = 7/24 * 100% = 29%

[4 3 5 1 4] probabilitas terpilih = 6/24 * 100% = 25%

[2 1 3 2 4] probabilitas terpilih = 6/24 * 100% = 25%

[5 2 3 4 1] probabilitas terpilih = 5/24 * 100% = 21%

4) Seleksi

Pada langkah berikutnya, kami secara acak memilih dua pasangan untuk direproduksi berdasarkan probabilitas yang kami hitung pada langkah sebelumnya. Dengan kata lain, sejumlah kromosom akan bertahan ke generator berikutnya menggunakan operator seleksi. Di sini dipilih kromosom untuk berperan sebagai orang tua yang digabungkan menggunakan operator crossover untuk membuat anak. Selain itu, kami memilih titik persilangan per pasangan.

Di sini kami mengambil kromosom secara acak berdasarkan probabilitasnya:

[4 3 5 1 4]

[5 2 4 3 5]

[4 3 5 1 4]

[2 1 3 2 4]

Kita dapat melihat bahwa kita tidak mengambil kromosomnya [5 2 3 4 1] karena kemungkinannya untuk dipilih adalah yang paling kecil di antara kromosom.

Untuk pasangan pertama

[4 3 5 1 4]

[5 2 4 3 5]

Titik persilangan akan diambil setelah dua gen.

Dalam kasus pasangan kedua

[4 3 5 1 4]

[2 1 3 2 4]

Titik persilangan akan dipilih setelah tiga gen.

Di sini kita lanjut ke langkah selanjutnya karena nilai fitness kita tidak sama dengan Fmax yang merupakan nilai fitness bilangan maksimal pada kromosom yang memenuhi syarat penyelesaian masalah 5-Queen. Fmax sama dengan 10.

5) Crossover

Pada persilangan, kromosom terpilih berperan sebagai orang tua yang digabungkan menggunakan operator persilangan untuk membentuk anak. Dengan kata lain, ini menggabungkan informasi genetik dari dua orang tua untuk menghasilkan keturunan baru.

Di sini kita dapat melihat bahwa anak-anak yang dihasilkan dari pasangan pertama ([4 3 5 1 4] dan [5 2 4 3 5]) adalah sebagai berikut:

[4 3 4 3 5]

[5 2 5 1 4]

Dari pasangan kedua ([4 3 5 1 4] dan [2 1 3 2 4]) anak-anak adalah sebagai berikut:

[4 3 5 2 4]

[2 1 3 1 4]

Dengan kata lain, untuk membuat anak pertama dari pasangan dalam proses persilangan, diambil bagian pertama kromosom induk # 1 dan bagian kedua kromosom induk # 2 yang membentuk individu baru yang terdiri dari

[(first part of parent #1 chromosome) [(second part of parent #2 chromosome)]

Untuk membuat anak kedua dari pasangan yang sama kita mengambil bagian kedua kromosom induk # 1 dan bagian pertama kromosom induk # 2 yang membuat individu baru yang terdiri dari

[(second part of parent #1 chromosome) [(first part of parent #2 chromosome)]

Jadi dalam kasus kami saat kami membuat anak-anak berpasangan [4 3 5 1 4] dan [5 2 4 3 5], untuk menghasilkan anak pertama, kami ambil [(first part of parent #1 chromosome) [(second part of parent #2 chromosome)] = [ 4 3 4 3 5]

Untuk menghasilkan anak kedua, kami ambil [(second part of parent #1 chromosome) [(first part of parent #2 chromosome)] = [5 2 5 1 4]

Proses yang sama akan kita lakukan untuk pasangan kedua ([4 3 5 1 4] dan [2 1 3 2 4]).


6) Mutasi

Langkah selanjutnya adalah mutasi. Dalam proses mutasi, kami mengubah satu atau lebih nilai gen dalam kromosom yang kami temukan setelah persilangan. Jadi itu secara acak mengubah beberapa gen dan kemungkinan mutasinya rendah. Jadi dalam contoh kita, mutasi kita akan terlihat seperti berikut:

[4 3 4 3 5] →[4 3 1 3 5]

[5 2 5 1 4] →[5 2 3 1 4]

[4 3 5 2 4] →[4 3 5 2 4]

[2 1 3 1 4] →[2 1 3 5 4]

di mana kita dapat memperhatikan gen ketiga dalam kromosom [4 3 4 3 5] diubah dari 4 menjadi 1.

Juga gen ketiga dalam kromosom [5 2 5 1 4] berubah dari 5 menjadi 3. Selain itu, gen keempat dalam kromosom [2 1 3 1 4] diubah dari 1 menjadi 5.

Jadi sampai saat ini, algoritma genetika untuk menyelesaikan algoritma 5-Queen akan terlihat seperti berikut:

7) Perbarui generasi

Pada langkah selanjutnya, kita perlu memperbarui generasi. Kromosom baru akan memperbarui populasi tetapi jumlah populasi tidak akan berubah. Jadi kromosomnya

[4 3 1 3 5]

[5 2 3 1 4]

[4 3 5 2 4]

[2 1 3 5 4]

Akan menjadi populasi baru kita.

8) Kembali ke langkah 3

Jadi pada langkah selanjutnya, kita perlu kembali ke langkah 3 (evaluasi kebugaran) untuk menemukan fungsi kebugaran dari populasi yang diperbarui.

Langkah 3–7 diulangi sampai kromosom (larutan) memenuhi hal-hal berikut:

Nilai kebugaran == Fmax

Dimana Fmax sama dengan 10

Referensi:

[1]Memecahkan Masalah N Queen menggunakan Algoritma Genetika

[2] Video penjelasan pemecahan masalah 5 ratu dengan menggunakan algoritma genetika

Posting juga diterbitkan di:

Repositori Github

Jika Anda memiliki pertanyaan, saran atau pujian, tepuk atau tekan bagian di bawah ini😁👇

Memecahkan Masalah 5-Ratu Menggunakan Algoritma Genetika awalnya diterbitkan di Towards AI on Medium, di mana orang-orang melanjutkan percakapan dengan menyoroti dan menanggapi cerita ini.

Diterbitkan melalui Towards AI

Leave a Reply