Algoritma Genetika: Pencarian dan Optimasi melalui Seleksi Alam

Diterbitkan: 2022-03-11

Apa Itu Algoritma Genetika?

Selama beberapa tahun terakhir, ada desas-desus hebat seputar Artificial Intelligence (AI). Perusahaan besar seperti Google, Apple, dan Microsoft secara aktif mengerjakan topik ini. Faktanya, AI adalah payung yang mencakup banyak tujuan, pendekatan, alat, dan aplikasi. Algoritma Genetika (GA) hanyalah salah satu alat untuk pencarian cerdas melalui banyak solusi yang mungkin.

GA adalah teknik pencarian dan optimasi metaheuristik berdasarkan prinsip-prinsip yang ada dalam evolusi alami. Itu milik kelas yang lebih besar dari algoritma evolusioner.

GA mempertahankan populasi kromosom —satu set solusi potensial untuk masalah tersebut. Idenya adalah bahwa "evolusi" akan menemukan solusi optimal untuk masalah tersebut setelah beberapa generasi berturut-turut—mirip dengan seleksi alam.

GA meniru tiga proses evolusi: seleksi, persilangan gen, dan mutasi.

Mirip dengan seleksi alam, konsep sentral seleksi GA adalah kebugaran. Kromosom yang lebih fit memiliki peluang lebih baik untuk bertahan hidup. Fitness adalah fungsi yang mengukur kualitas solusi yang diwakili oleh kromosom. Intinya, setiap kromosom dalam populasi mewakili parameter input. Misalnya, jika masalah Anda berisi dua parameter input, seperti harga dan volume dalam perdagangan, setiap kromosom secara logis akan terdiri dari dua elemen. Bagaimana elemen dikodekan dalam kromosom adalah topik yang berbeda.

Selama seleksi, kromosom membentuk pasangan orang tua untuk berkembang biak . Setiap anak mengambil karakteristik dari orang tuanya. Pada dasarnya, anak merupakan rekombinasi karakteristik dari orang tuanya: Beberapa karakteristik diambil dari satu orang tua dan beberapa dari yang lain. Selain rekombinasi, beberapa karakteristik dapat bermutasi .

Karena kromosom yang lebih bugar menghasilkan lebih banyak anak, setiap generasi berikutnya akan memiliki kebugaran yang lebih baik. Pada titik tertentu, generasi akan berisi kromosom yang akan mewakili solusi yang cukup baik untuk masalah kita.

GA sangat kuat dan dapat diterapkan secara luas untuk masalah yang kompleks. Ada kelas besar masalah optimasi yang cukup sulit untuk dipecahkan dengan teknik optimasi konvensional. Algoritma genetika adalah algoritma yang efisien yang solusinya mendekati optimal. Aplikasi terkenal termasuk penjadwalan, transportasi, perutean, teknologi grup, desain tata letak, pelatihan jaringan saraf, dan banyak lainnya.

Mempraktikkan Hal-hal

Contoh yang akan kita lihat dapat dianggap sebagai "Hello World" dari GA. Contoh ini awalnya diberikan oleh J. Freeman dalam Simulasi Jaringan Syaraf Tiruan dengan Mathematica . Saya mengambilnya dari Genetic Algorithms and Engineering Design oleh Mitsuo Gen dan Runwei Cheng.

Masalah Pencocokan Kata mencoba mengembangkan ekspresi dengan algoritme genetika. Awalnya, algoritme seharusnya "menebak" frasa "menjadi atau tidak" dari daftar huruf yang dibuat secara acak.

Karena ada 26 kemungkinan huruf untuk masing-masing dari 13 lokasi [tidak termasuk spasi] dalam daftar, probabilitas bahwa kita mendapatkan frasa yang benar dengan cara acak murni adalah (1/26)^13=4.03038×10-19, yaitu sekitar dua peluang dari [triliun] (Gen & Chong, 1997).

Kami akan mendefinisikan masalahnya sedikit lebih luas di sini, membuat solusinya semakin sulit. Mari kita asumsikan bahwa kita tidak terbatas pada bahasa Inggris atau frase tertentu. Kita bisa berurusan dengan alfabet apa pun, atau bahkan serangkaian simbol apa pun. Kami tidak memiliki pengetahuan tentang bahasa. Kami bahkan tidak tahu apakah ada bahasa sama sekali.

Katakanlah lawan kita memikirkan frasa sewenang-wenang, termasuk spasi. Kita tahu panjang frasa dan jumlah simbol dalam alfabet. Hanya itu pengetahuan yang kami miliki. Setelah setiap tebakan, lawan kami memberi tahu kami berapa banyak huruf yang ada.

Setiap kromosom adalah urutan indeks simbol dalam alfabet. Jika kita berbicara tentang alfabet bahasa Inggris, maka 'a' akan diwakili oleh 0, 'b' dengan 1, 'c' dengan 2, dan seterusnya. Jadi, misalnya, kata "menjadi" akan direpresentasikan sebagai [4, 1] .

Kami akan mendemonstrasikan semua langkah melalui potongan kode Java, tetapi pengetahuan tentang Java tidak diperlukan untuk memahami setiap langkah.

Inti Algoritma Genetika

Kita bisa mulai dengan implementasi umum dari algoritma genetika:

 public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } }

Ini adalah rangkaian langkah sederhana yang kurang lebih terdiri dari setiap GA. Pada langkah inisialisasi, kami menghasilkan populasi awal frasa. Ukuran populasi ditentukan oleh populationSize . Bagaimana frase dihasilkan tergantung pada implementasi supplier .

Dalam langkah iterasi, kami mengembangkan populasi hingga kondisi terminasi terpenuhi dalam pengujian loop while . Kondisi terminasi dapat mencakup jumlah generasi dan kecocokan yang tepat dari salah satu frasa dalam populasi. termination merangkum implementasi yang tepat.

Dalam setiap iterasi, kami melakukan langkah-langkah GA yang umum:

  1. Melakukan seleksi terhadap populasi berdasarkan fitness kromosom.
  2. Menghasilkan "generasi" baru melalui operasi crossover.
  3. Lakukan rekombinasi beberapa huruf dalam beberapa frasa.

Inti dari algoritma ini sangat sederhana dan domain-agnostik. Itu akan sama untuk semua masalah. Yang perlu Anda sesuaikan adalah penerapan operator genetika. Selanjutnya, kita akan melihat dari dekat masing-masing operator GA yang disebutkan sebelumnya.

Pilihan

Seperti yang sudah kita ketahui, seleksi adalah proses menemukan penerus kromosom saat ini—kromosom yang lebih cocok untuk masalah kita. Selama seleksi, kita perlu memastikan bahwa kromosom dengan kebugaran yang lebih baik memiliki kesempatan yang lebih baik untuk bertahan hidup.

 private List<T> selection(List<T> population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList()); }

Gagasan di balik implementasi ini adalah sebagai berikut: Populasi direpresentasikan sebagai rentang konsekuen pada sumbu numerik. Seluruh populasi adalah antara 0 dan 1.

Demonstrasi visual tentang bagaimana langkah seleksi dalam algoritma genetika kami bekerja

Potongan rentang yang diambil kromosom sebanding dengan kebugarannya. Ini menghasilkan kromosom yang lebih bugar mendapatkan potongan yang lebih besar. Kemudian kami secara acak mengintip angka antara 0 dan 1 dan menemukan rentang yang menyertakan angka tersebut. Jelas, rentang yang lebih besar memiliki peluang lebih tinggi untuk dipilih, dan karena itu kromosom yang lebih bugar memiliki peluang lebih baik untuk bertahan hidup.

Karena kita tidak mengetahui detail tentang fungsi fitness, kita perlu menormalkan nilai fitness. Fungsi fitness direpresentasikan dengan fitness , yang mengubah sebuah kromosom menjadi double arbitrer yang merepresentasikan fitness dari kromosom tersebut.

Dalam kode, kami menemukan tingkat kebugaran untuk semua kromosom dalam populasi, dan kami juga menemukan kebugaran total. Di dalam for loop, kita melakukan penjumlahan kumulatif atas probabilitas yang diperkecil dengan total fitness. Secara matematis, ini akan menghasilkan variabel akhir yang bernilai 1. Karena ketidaktepatan floating point, kami tidak dapat menjaminnya, jadi kami menetapkannya ke 1 hanya untuk memastikan.

Akhirnya, untuk beberapa kali sama dengan jumlah kromosom input, kami menghasilkan nomor acak, menemukan rentang yang mencakup nomor tersebut, dan kemudian memilih kromosom yang sesuai. Seperti yang mungkin Anda perhatikan, kromosom yang sama dapat dipilih beberapa kali.

pindah silang

Sekarang kita perlu kromosom untuk "berkembang biak."

 private void crossover(List<T> population) { final int[] indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes[2 * i]; final int index2 = indexes[2 * i + 1]; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); } }

Dengan probabilitas crossoverProbability yang telah ditentukan sebelumnya, kami memilih orang tua untuk pembiakan. Orang tua yang dipilih dikocok, memungkinkan kombinasi apa pun terjadi. Kami mengambil pasangan orang tua dan menerapkan operator crossover . Kami menerapkan operator dua kali untuk setiap pasangan karena kami perlu menjaga ukuran populasi tetap sama. Anak-anak menggantikan orang tua mereka dalam populasi.

Mutasi

Akhirnya, kami melakukan rekombinasi karakteristik.

 private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } } }

Dengan probabilitas mutationProbability telah ditentukan, kami melakukan "mutasi" pada kromosom. Mutasi itu sendiri didefinisikan dengan mutation .

Konfigurasi Algoritma khusus masalah

Sekarang mari kita lihat jenis parameter khusus masalah apa yang perlu kita sediakan untuk implementasi generik kita.

 private BiFunction<T, T, T> crossover; private double crossoverProbability; private ToDoubleFunction<T> fitness; private Function<T, T> mutation; private double mutationProbability; private int populationSize = 100; private Supplier<T> supplier; private Predicate<Collection<T>> termination;

Parameternya, masing-masing, adalah:

  1. Operator pindah silang
  2. Probabilitas pindah silang
  3. Fungsi kebugaran
  4. Operator mutasi
  5. Probabilitas mutasi
  6. Ukuran populasi
  7. Pemasok kromosom untuk populasi awal
  8. Fungsi penghentian

Berikut adalah konfigurasi untuk masalah kita:

 new GeneticAlgorithm<char[]>() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find()

Operator Crossover dan Probabilitas

 private char[] crossover(char[] value1, char[] value2) { final int i = (int) round(random() * value1.length); final char[] result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result; }

Probabilitas crossover adalah 0,25, jadi kami berharap bahwa rata-rata 25 persen dari kromosom akan dipilih untuk crossover. Kami melakukan prosedur sederhana untuk crossover sepasang kromosom. Kami menghasilkan nomor acak n dari rentang [0..length] , di mana length adalah panjang kromosom. Sekarang kita mengawinkan pasangan yang dipilih dengan mengambil n karakter pertama dari satu kromosom dan karakter yang tersisa setelah dari yang kedua.

Fungsi Kebugaran

 private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); }

Fungsi fitness hanya menghitung jumlah kecocokan antara frase target dan kromosom yang diberikan.

Operator Mutasi dan Probabilitas

 private char[] mutation(char[] value) { final char[] result = Arrays.copyOf(value, value.length); for (int i = 0; i < 2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result[location] = ALPHABET[letter]; } return result; }

Operasi mutasi dilakukan secara independen pada setiap kromosom. Probabilitas mutasi adalah 0,05, jadi kami berharap, rata-rata, lima persen dari populasi akan bermutasi. Kami bermutasi dengan memilih posisi huruf acak dan mengganti nilainya dengan huruf acak dari alfabet. Kami melakukannya dua kali untuk setiap kromosom yang bermutasi.

pemasok

 private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result[i] = ALPHABET[letter]; } return result; }

Pemasok menghasilkan frasa acak dengan mengambil huruf acak dari alfabet. Setiap frase memiliki panjang konstan yang telah ditentukan sebelumnya.

Fungsi Pemutusan

 private boolean termination(Collection<char[]> chars) { count++; final Optional<char[]> result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println("Count: " + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated; }

Fungsi penghentian menghitung jumlah panggilan dan mengembalikan nilai true jika ada kecocokan persis, atau jika jumlah generasi mencapai 3.000.

Eksekusi

Sekarang kita siap untuk menguji algoritma kita. Jika Anda menjalankannya beberapa kali, Anda akan melihat bahwa tidak semua proses berhasil. Setiap kali, jumlah iterasi akan berbeda. Itu karena sifat probabilistik dari algoritma. Algoritme memiliki beberapa poin yang dapat ditingkatkan. Anda dapat bermain dengan probabilitas crossover dan mutasi.

Menurunkan angka akan menghasilkan solusi yang stabil tetapi lambat. Jumlah kromosom yang lebih kecil akan dipengaruhi oleh operator genetik dan, oleh karena itu, lebih banyak iterasi akan diperlukan untuk solusi.

Meningkatkan angka akan mempercepat algoritma, tetapi juga akan membuat solusi tidak stabil. Kromosom yang fit tidak hanya akan dipertahankan, tetapi juga akan dipengaruhi oleh operator genetik. Karena itu, mereka akan kehilangan gen "baik" mereka.

Penting untuk menemukan keseimbangan yang baik. Peningkatan jumlah iterasi akan memberikan algoritma lebih banyak kesempatan untuk menemukan solusi tetapi, di sisi lain, akan membutuhkan lebih banyak waktu. Anda juga dapat menerapkan metode crossover dan mutasi yang berbeda. Pilihan yang baik dari operator ini akan secara drastis meningkatkan kualitas solusi.

Apa selanjutnya?

Kami baru saja membahas puncak gunung es di sini. Kami mengambil contoh yang hanya memiliki satu input, dan input tersebut dapat dengan mudah disajikan sebagai kromosom. Operator genetiknya sederhana dan sederhana.

Sangat menarik untuk mengambil masalah dunia nyata dan menerapkan algoritma genetika untuk itu. Anda akan menemukan pendekatan yang berbeda dalam pengkodean data input nyata serta implementasi crossover dan mutasi yang berbeda.

Jika suatu masalah dapat diekspresikan melalui serangkaian parameter yang harus kita tebak untuk mengoptimalkan metrik, kita dapat dengan cepat menyiapkan GA yang dapat kita gunakan untuk menyelesaikannya.

Salah satu masalah yang paling menarik adalah mengajar jaringan saraf tiruan. Kami dapat mengatur parameter yang dapat dioptimalkan menjadi kekuatan sinaps, dan metrik kebugaran menjadi persentase input yang jaringan saraf kami memberikan jawaban yang benar. Setelah itu, kita dapat duduk dan membiarkan jaringan saraf kita berkembang menjadi solusi ideal yang kita inginkan. Atau setidaknya sampai kita mendapatkan sesuatu yang cukup baik, karena evolusi membutuhkan waktu.