Mendesain Algoritma Genetika di Java

1. Perkenalan

Seri ini bertujuan untuk menjelaskan gagasan tentang algoritma genetika .

Algoritme genetik dirancang untuk memecahkan masalah dengan menggunakan proses yang sama seperti di alam - algoritme tersebut menggunakan kombinasi seleksi, rekombinasi, dan mutasi untuk mengembangkan solusi bagi suatu masalah.

Mari kita mulai dengan menjelaskan konsep dari algoritma tersebut menggunakan contoh algoritma genetika biner yang paling sederhana.

2. Bagaimana Algoritma Genetika Bekerja

Algoritme genetik adalah bagian dari komputasi evolusioner , yang merupakan bidang kecerdasan buatan yang berkembang pesat.

Algoritme dimulai dengan sekumpulan solusi (diwakili oleh individu ) yang disebut populasi . Solusi dari satu populasi diambil dan digunakan untuk membentuk populasi baru , karena ada kemungkinan populasi baru akan lebih baik dari populasi lama.

Individu yang dipilih untuk membentuk solusi baru ( keturunan ) dipilih sesuai dengan kebugaran mereka - semakin cocok mereka, semakin besar peluang mereka untuk bereproduksi.

3. Algoritma Genetika Biner

Mari kita lihat proses dasar untuk algoritma genetika sederhana.

3.1. Inisialisasi

Pada langkah inisialisasi, kami menghasilkan Populasi acak yang berfungsi sebagai solusi pertama . Pertama, kita perlu memutuskan seberapa besar Populasi nantinya dan apa solusi akhir yang kita harapkan:

SimpleGeneticAlgorithm.runAlgorithm(50, "1011000100000100010000100000100111001000000100000100000000001111");

Dalam contoh di atas, ukuran Populasi adalah 50, dan solusi yang benar diwakili oleh string bit biner yang dapat kami ubah kapan saja.

Pada langkah selanjutnya kita akan menyimpan solusi yang kita inginkan dan membuat Populasi acak :

setSolution(solution); Population myPop = new Population(populationSize, true);

Sekarang kita siap menjalankan loop utama program.

3.2. Pemeriksaan Kebugaran

Dalam putaran utama program, kita akan mengevaluasi setiap individu berdasarkan fungsi kebugaran (dengan kata sederhana, semakin baik Individu , semakin tinggi nilai fungsi kebugaran yang didapat):

while (myPop.getFittest().getFitness() < getMaxFitness()) { System.out.println( "Generation: " + generationCount + " Correct genes found: " + myPop.getFittest().getFitness()); myPop = evolvePopulation(myPop); generationCount++; }

Mari kita mulai dengan menjelaskan bagaimana kita mendapatkan Individu terkuat :

public int getFitness(Individual individual) { int fitness = 0; for (int i = 0; i < individual.getDefaultGeneLength() && i < solution.length; i++) { if (individual.getSingleGene(i) == solution[i]) { fitness++; } } return fitness; }

Seperti yang dapat kita amati, kita membandingkan dua objek Individual sedikit demi sedikit. Jika kita tidak dapat menemukan solusi yang tepat, kita perlu melanjutkan ke langkah berikutnya, yaitu evolusi Populasi .

3.3. Keturunan

Pada langkah ini, kita perlu membuat Populasi baru . Pertama, kita perlu memilih dua objek individu induk dari Populasi, sesuai dengan kesesuaiannya. Harap dicatat bahwa adalah bermanfaat untuk memungkinkan Individu terbaik dari generasi saat ini untuk melanjutkan ke generasi berikutnya, tanpa perubahan. Strategi ini disebut Elitisme:

if (elitism) { newPopulation.getIndividuals().add(0, pop.getFittest()); elitismOffset = 1; } else { elitismOffset = 0; }

Untuk memilih dua objek Individu terbaik , kami akan menerapkan strategi pemilihan turnamen :

private Individual tournamentSelection(Population pop) { Population tournament = new Population(tournamentSize, false); for (int i = 0; i < tournamentSize; i++) { int randomId = (int) (Math.random() * pop.getIndividuals().size()); tournament.getIndividuals().add(i, pop.getIndividual(randomId)); } Individual fittest = tournament.getFittest(); return fittest; }

Pemenang dari setiap turnamen (yang paling fit) akan dipilih untuk tahap selanjutnya, yaitu Crossover :

private Individual crossover(Individual indiv1, Individual indiv2) { Individual newSol = new Individual(); for (int i = 0; i < newSol.getDefaultGeneLength(); i++) { if (Math.random() <= uniformRate) { newSol.setSingleGene(i, indiv1.getSingleGene(i)); } else { newSol.setSingleGene(i, indiv2.getSingleGene(i)); } } return newSol; }

Dalam persilangan, kami menukar bit dari setiap Individu yang dipilih di tempat yang dipilih secara acak. Seluruh proses berjalan di dalam loop berikut:

for (int i = elitismOffset; i < pop.getIndividuals().size(); i++) { Individual indiv1 = tournamentSelection(pop); Individual indiv2 = tournamentSelection(pop); Individual newIndiv = crossover(indiv1, indiv2); newPopulation.getIndividuals().add(i, newIndiv); }

Seperti yang bisa kita lihat, setelah persilangan, kita menempatkan keturunan baru dalam Populasi baru . Langkah ini disebut Penerimaan.

Akhirnya, kita bisa melakukan Mutasi . Mutasi digunakan untuk mempertahankan keragaman genetik dari satu generasi suatu Populasi ke generasi berikutnya. Kami menggunakan jenis mutasi bit inversi , di mana bit acak dibalik:

private void mutate(Individual indiv) { for (int i = 0; i < indiv.getDefaultGeneLength(); i++) { if (Math.random() <= mutationRate) { byte gene = (byte) Math.round(Math.random()); indiv.setSingleGene(i, gene); } } }

Semua jenis Mutasi dan Persilangan dijelaskan dengan baik dalam tutorial ini.

Kami kemudian mengulangi langkah-langkah dari sub-bagian 3.2 dan 3.3, hingga kami mencapai kondisi penghentian, misalnya, solusi terbaik.

4. Tips dan Trik

In order to implement an efficient genetic algorithm, we need to tune a set of parameters. This section should give you some basic recommendations how to start with the most importing parameters:

  • Crossover rate – it should be high, about 80%-95%
  • Mutation rate – it should be very low, around 0.5%-1%.
  • Population size – good population size is about 20-30, however, for some problems sizes 50-100 are better
  • Selection – basic roulette wheel selection can be used with the concept of elitism
  • Crossover and mutation type – it depends on encoding and the problem

Harap dicatat bahwa rekomendasi untuk penyetelan seringkali merupakan hasil dari studi empiris pada algoritma genetika, dan mungkin berbeda-beda, berdasarkan masalah yang diajukan.

5. Kesimpulan

Tutorial ini memperkenalkan dasar-dasar algoritma genetika . Anda dapat belajar tentang algoritma genetika tanpa pengetahuan sebelumnya tentang bidang ini, hanya memiliki keterampilan dasar pemrograman komputer.

Kode sumber lengkap untuk potongan kode dalam tutorial ini tersedia di proyek GitHub.

Perlu diketahui juga bahwa kami menggunakan Lombok untuk menghasilkan getter dan setter. Anda dapat memeriksa cara mengkonfigurasinya dengan benar di IDE Anda di artikel ini.

Untuk contoh lebih lanjut dari algoritma genetika, lihat semua artikel dari seri kami:

  • Bagaimana Mendesain Algoritma Genetika? (yang ini)
  • Masalah Penjual Keliling di Jawa