Apa itu Algoritma Genetika dan Contoh Programnya

Algortima genetika adalah algoritma komputasi yang diisnpirasi teori evolusi yang kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi suatu permasalahan dengan cara yang lebih ”Alamiah”. Salah satu aplikasi algoritma genetika adalah pada permasalah optimasi kombinasi, yaitu mendapatkan suatu nilai optimal terhadap suatu permasalah yang mempunyai banyak kemungkinan solusi.

Traveling Salesman Proble

Permasalahan TSP adalah permasalahan dimana seorang salesman harus mengunjungi semua kota dimana tiap kota hanya dikunjungi sekali, dan dia harus mulai dari dan kembali ke total asal. Tujuannya adalah menentukan rute dengan jarak total atau biaya yang paling minimum. Permaslaah TSP merupakan permasalahan yang mememang mudah untuk diselesaikan dengan algoritma brute force, tetapi hal itu hanya dapat dilakukan dengan jumlah kota atau simpul yang tidak banyak, kompleksitas algoritma untuk permasalahan TSP dengan algoritma Bruce Force adalah O(n!) dengan catatan n adalah jumlah kota atau simpul dan setipa kota atua simpul terhubung dengan semua kota atau simpul lainnya, dengan jumlah sebanyak 20 kota, maka banyak sirkuit Hamilton yang mungkin adalah sebanyak 6x 1016. Berikut Implementasi Program. Berikut adalah source code implementasi dari algoritma genetika :

1. buat file dan beri nama index.html

<!doctype HTML>

<html>

<head>

</head>

</html>

2. buat file dengan nama sketch.js

var cities = [];

var totalCities = 100;

var popSize = 500;

var population = [];

var fitness = [];

var recordDistance = Infinity;

var bestEver;

var currentBest;

var statusP;

function setup()

{

createCanvas(800, 800);

var order = [];

for(var i=0; i<totalCities; i++)

{

var v = createVector(random(width), random(height/2));

cities[i] = v;

order[i] = i;

}

for(var i=0; i<popSize; i++)

{

population[i] = shuffle(order);

}

statusP = createP('').style('font-size', '32pt');

}

function draw()

{

background(0);

calculateFitness();

normalizeFitness();

nextGeneration();

stroke(255);

strokeWeight(4);

noFill();

beginShape();

for(var i=0; i<bestEver.length; i++)

{

var n = bestEver[i];

vertex(cities[n].x, cities[n].y);

ellipse(cities[n].x, cities[n].y, 16, 16);

}

End shape();

translate(0, height/2);

stroke(255);

strokeWeight(4);

noFill();

beginShape();

for(var i=0; i<currentBest.length; i++)

{

var n = currentBest[i];

vertex(cities[n].x, cities[n].y);

ellipse(cities[n].x, cities[n].y, 16, 16);

}

endShape();

}

function swap(a, i, j)

{

var temp = a[i];

a[i] = a[j];

a[j] = temp;

}

function calcDistance(points, order)

{

var sum = 0;

for(var i=0; i<order.length-1; i++)

{

var cityAIndex = order[i];

var cityA = points[cityAIndex];

var cityBIndex = order[i+1];

var cityB = points[cityBIndex];

var d = dist(cityA.x, cityA.y, cityB.x, cityB.y);

sum += d;

}

return sum;

}

function calculateFitness()

{

var currentRecord = Infinity;

for(var i=0; i<population.length; i++)

{

var d = calcDistance(cities, population[i]);

if(d<recordDistance)

{

recordDistance = d;

bestEver = population[i];

}

if(d<currentRecord)

{

currentRecord = d;

currentBest = population[i];

}

fitness[i] = 1/(pow(d, 8)+1);

}

function normalizeFitness()

{

var sum = 0;

for(var i=0; i<fitness.length; i++)

{

sum += fitness[i];

}

for(var i=0; i<fitness.length; i++)

{

fitness[i] = fitness[i]/sum;

}

function nextGeneration()

{

var newPopulation = [];

for(var i=0; i<population.length; i++)

{

var orderA = pickOne(population, fitness);

var orderB = pickOne(population, fitness);

var order = crossOver(orderA, orderB);

mutate(order, 0.01);

newPopulation[i] = order;

}

population = newPopulation;

}

function pickOne(list, prob)

{

var index = 0;

var r = random(1);

while(r>0)

{

r = r-prob[index];

index++;

}

index--;

return list[index].slice();

}

function crossOver(orderA, orderB)

{

var start = floor(random(orderA.length));

var end = floor(random(start+1, orderA.length));

var newOrder = orderA.slice(start, end);

for(var i=0; i<orderB.length; i++)

{

var city = orderB[i];

if(!newOrder.includes(city))

{

newOrder.push(city);

}

return newOrder;

}

function mutate(order, mutationRate)

{

for(var i=0; i<totalCities; i++)

{

if(random(1)<mutationRate)

{

var indexA = floor(random(order.length));

var indexB = (indexA+1) % totalCities;

swap(order, indexA, indexB);

}

berikut adalah hasil programnya :

Pada gambar dibawah ini menggambarkan bahwa algoritma genetika itu mencari solusi dengan banyak pilihan dan algoritma ini akan memilih solusi yang paling baik.

Buat temen-temen yang males coding bisa langsung download aja DISINI filenya, untuk menjalankan aplikasi ini membutuhkan koneksi internet karena ada beberapa library yang harus terkoneksi ke internet.