Penjelasan Algoritma Genetik

Sebenarnya kalo membahas algoritma genetik (GA), maka ini semata-mata persoalan bagaimana mereduksi waktu dalam pencarian solusi dari persoalan optimisasi. Jadi ketimbang kita melakukan brute-force terhadap semua kemungkinan pemecahan masalah (yang menghasilkan nilai optimal) yang tentunya membutuhkan waktu yang sangat lama, yakni O(n!) dengan n menyatakan jumlah input, maka dengan algoritma genetik kita membatasi solusi persoalannya dengan menerapkan metode yang analog dengan apa yang diterapkan oleh alam terhadap makhluk hidup. Solusi yang diberikan oleh algoritma genetik bisa jadi bukan solusi yang benar-benar optimal, namun solusi ini dirasa sudah cukup  untuk keperluan praktis. Artinya ketimbang kita menghabiskan waktu untuk sekian iterasi hanya untuk mencari tahu semua kemungkinan dari solusi, maka dengan algoritma genetik, kita hanya mengambil sebagian dari seluruh kemungkinan namun tetap dengan tujuan mencari nilai optimal. Terdapat 5 bagian utama dari algoritma genetik yakni 1) pemilihan populasi awal, 2) Evaluasi nilai “fitness”, 3) seleksi, 4) crossover, dan 5) mutasi. Populasi awal dipilih secara random dari ruang sampel yang memenuhi solusi persoalan. Evaluasi kemudian diterapkan pada solusi untuk kemudian dikenakan pembobotan berdasarkan tujuan optimisasi (maksimum atau minimum). Seleksi dilakukan untuk memilih mana dari populasi yang layak masuk pada tahap iterasi selanjutnya (dalam terminologinya disebut sebagai generasi berikutnya) dan mana yang dibuang/disingkirkan.  Crossover merupakan pemilihan populasi generasi berikutnya (solusi anak) berdasarkan pertukaran informasi antara populasi sebelumnya  yang melewati tahap seleksi (solusi induk)---karena jumlah populasi harus tetap sementara sebagian sudah disingkirkan dalam tahap seleksi. Sementara mutasi merupakan perubahan informasi pada solusi (solusi anak) secara acak untuk menjaga diversitas dari solusi.

Saya akan memberikan contoh kasus kegunaan algoritma genetik dalam memecahkan persoalan optimisasi traveling salesman. Pernyataan traveling salesman adalah terdapat kumpulan kota yang berjarak tertentu satu sama lain. Dan kita diharuskan untuk mengunjungi seluruh kota-kota tersebut satu persatu di mana satu kota hanya boleh dikunjungi sekali. Kemudian dihitung rute mana yang menghasilkan jarak tempuh yang paling singkat. Dengan metode brute force (mencari semua kemungkinan) tentu saja akan sangat tidak efisien. Misalnya saja ketika jumlah kota nya ada 4, maka ada 24 kemungkinan rute yang bisa ditempuh, dan kita harus mencari tahu jarak pada semua rute tersebut. Bagaimana kalo kotanya ada 100, kan tidak mungkin.

Untuk implementasi algoritma genetik dari kasus ini sudah diberikan oleh sebuah blog yang beralamat di sini. Jadi saya tidak perlu mengulangi apa yang disampaikan pada blog tersebut. Intinya adalah terdapat kota yang harus dikunjungi dengan peta sebagai berikut:



Source dari blog tersebut juga sudah saya host di github.
Dari keseluruhan source code tersebut, saya akan memberikan sedikit penjelasan mengenai mana bagian yang paling penting atau yang menjadi bagian inti dari algoritma genetik dalam menyelesaikan persoalan tersebut. Yakni dapat dilihat pada potongan script berikut

package com.fjr.genetic.main;

public class GA {

    /* GA parameters */
    private static final double mutationRate = 0.015;
    private static final int tournamentSize = 5;
    private static final boolean elitism = true;

    // Evolves a population over one generation
    public static Population evolvePopulation(Population pop) {
        Population newPopulation = new Population(pop.populationSize(), false);

        // Keep our best individual if elitism is enabled
        int elitismOffset = 0;
        if (elitism) {
            newPopulation.saveTour(0, pop.getFittest());
            elitismOffset = 1;
        }

        // Crossover population
        // Loop over the new population's size and create individuals from
        // Current population
        for (int i = elitismOffset; i < newPopulation.populationSize(); i++) {
            // Select parents
            Tour parent1 = tournamentSelection(pop);    // bagian 1
            Tour parent2 = tournamentSelection(pop);
            // Crossover parents
            Tour child = crossover(parent1, parent2);
            // Add child to new population
            newPopulation.saveTour(i, child);
        }

        // Mutate the new population a bit to add some new genetic material
        for (int i = elitismOffset; i < newPopulation.populationSize(); i++) {
            mutate(newPopulation.getTour(i));    // bagian 2
        }

        return newPopulation;
    }

    // Applies crossover to a set of parents and creates offspring
    public static Tour crossover(Tour parent1, Tour parent2) {
        // Create new child tour
        Tour child = new Tour();

        // Get start and end sub tour positions for parent1's tour
        int startPos = (int) (Math.random() * parent1.tourSize());     // bagian 3
        int endPos = (int) (Math.random() * parent1.tourSize());

        // Loop and add the sub tour from parent1 to our child
        for (int i = 0; i < child.tourSize(); i++) {       // bagian 4
            // If our start position is less than the end position
            if (startPos < endPos && i > startPos && i < endPos) {
                child.setCity(i, parent1.getCity(i));
            } // If our start position is larger
            else if (startPos > endPos) {
                if (!(i < startPos && i > endPos)) {
                    child.setCity(i, parent1.getCity(i));
                }
            }
        }

        // Loop through parent2's city tour
        for (int i = 0; i < parent2.tourSize(); i++) {        // bagian 5
            // If child doesn't have the city add it
            if (!child.containsCity(parent2.getCity(i))) {
                // Loop to find a spare position in the child's tour
                for (int ii = 0; ii < child.tourSize(); ii++) {
                    // Spare position found, add city
                    if (child.getCity(ii) == null) {
                        child.setCity(ii, parent2.getCity(i));
                        break;
                    }
                }
            }
        }
        return child;
    }

    // Mutate a tour using swap mutation
    private static void mutate(Tour tour) {       //bagian 6
        // Loop through tour cities
        for(int tourPos1=0; tourPos1 < tour.tourSize(); tourPos1++){
            // Apply mutation rate
            if(Math.random() < mutationRate){
                // Get a second random position in the tour
                int tourPos2 = (int) (tour.tourSize() * Math.random());

                // Get the cities at target position in tour
                City city1 = tour.getCity(tourPos1);
                City city2 = tour.getCity(tourPos2);

                // Swap them around
                tour.setCity(tourPos2, city1);
                tour.setCity(tourPos1, city2);
            }
        }
    }

    // Selects candidate tour for crossover
    private static Tour tournamentSelection(Population pop) {     // bagian 7
        // Create a tournament population
        Population tournament = new Population(tournamentSize, false);
        // For each place in the tournament get a random candidate tour and
        // add it
        for (int i = 0; i < tournamentSize; i++) {
            int randomId = (int) (Math.random() * pop.populationSize());
            tournament.saveTour(i, pop.getTour(randomId));
        }
        // Get the fittest tour
        Tour fittest = tournament.getFittest();
        return fittest;
    }
}

Pada keterangan yang ditandai dengan bagian 1 dari potongan script di atas, akan dilakukan pemilihan 5 anggota populasi secara acak dari seluruh populasi awal  untuk diseleksi. Seleksi kemudian akan mencari rute yang memiliki jarak tempuh paling singkat. Hasilnya kemudian akan dilakukan penerapan operasi crossover yang akan menghasilkan anggota populasi anak untuk dimasukkan ke dalam populasi dari generasi berikutnya. Hal ini di-loop untuk seluruh total populasi.  Bagian 2 menandakan operasi mutasi terhadap seluruh anggota populasi baru generasi berikutnya (populasi anak). Bagian 3 merupakan sub-bagian dari operasi crossover. Di mana akan dipilih secara acak pada bagian string/list/kromosom dari anggota populasi induk (yakni dua anggota populasi induk) yang ditandai sebagai bagian awal (start) dan bagian akhir (end) dari kromosom untuk diterapkan operasi crossover. Untuk bagian elemen string/list/kromosom ke-i dari rute yang masuk dalam rentang start sampai ke end dengan start < end, maka set element ke-i dari kromosom anak  sebagai elemen dari kromosom  rute induk 1. Jika end < start, maka set elemen ke-i dari kromosom anak sebagai  bagian dari kromosom induk 1 jika nilai i tersebut berada di luar rentang start sampai end. Bagian 5 menandakan operasi untuk mengisi elemen dari kromosom anak dengan mengambil dari element kromosom rute induk 2. Yakni dengan mengisi bagian yang belum di-isi oleh elemen dari rute induk 1

Bagian 6 merupakan implementasi dari operasi mutasi di mana akan akan diadakan pertukaran letak kota dalam kromosom rute jika bilangan random yang dihasilkan melampaui nilai laju mutasi. Bagian 7 menandakan pemilihan rute-rute dari populasi induk yang diterapkan operasi crossover. Di mana yang dikeluarkan adalah rute yang memiliki jarak tempuh paling singkat (highest fitness).

Jika Anda melakukan tes pada source code yang diberikan tersebut, maka akan didapati bahwa nilai optimal itu bergantung pada pemilihan populasi awal. Jadi pendekatan algoritma genetik sama sekali tidak mencari mana solusi eksak (urutan kota dalam rute yang menghasilkan nilai jarak tempuh paling singkat), akan tetapi hanya mencari solusi yang sekedar bisa mereduksi jarak tempuh.