APLIKASI PENGENALAN KATA DENGAN ALGORITMA GENETIKA


Setelah satu bulan lebih vakum sama sekali, tidak menulis satu tulisan pun di blog. Dikesempatan ini, setelah sempat mengutak-atik algoritma genetika sederhana untuk mengenali kata, maka sekalian saja menulis dan dishare di blog kesayangan.

Algoritma genetika merupakan teknik pencarian dan optimasi yang terinspirasi oleh prinsip dari genetika dan seleksi alam (teori evolusi Darwin). Algoritma ini digunakan untuk mendapatkan solusi yang tepat untuk masalah optimasi dari satu variabel atau multi variabel.

Berbeda dengan teknik pencarian konvensional, algoritma genetika bermula dari himpunan solusi yang dihasilkan secara acak. Himpunan ini disebut populasi. Sedangkan setiap individu dalam populasi disebut kromosom yang merupakan representasi dari solusi. Kromosom-kromosom berevolusi dalam suatu proses iterasi yang berkelanjutan yang disebut generasi. Pada setiap generasi, kromosom dievaluasi berdasarkan suatu fungsi evaluasi (Gen dan Cheng, 1997). Setelah beberapa generasi maka algoritma genetika akan konvergen pada kromosom terbaik, yang diharapkan merupakan solusi optimal (Goldberg,1989).

Pertama kali, sebelum algoritma genetika dijalankan, maka perlu didefinisikan fungsi fitness sebagai masalah yang ingin dioptimalkan. Jika nilai fitness semakin besar, maka sistem yang dihasilkan semakin baik. fungsi fitness ditentukan dengan metode heuristik.

Algoritma genetika sangat tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan sukar diselesaikan dengan menggunakan metode konvensional. Sebagaimana halnya proses evolusi di alam, suatu algoritma genetika yang sederhana umumnya terdiri dari tiga operasi yaitu: operasi reproduksi, operasi crossover (persilangan), dan operasi mutasi. Struktur umum dari suatu algoritma genetika dapat didefinisikan dengan langkah-langkah sebagai berikut:

  • Membangkitkan populasi awal secara random.
  • Membentuk generasi baru dengan menggunakan tiga operasi diatas secara berulang-ulang sehingga diperoleh kromosom yang cukup untuk membentuk generasi baru sebagai representasi dari solusi baru.
  • Evolusi solusi yang akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom hingga kriteria berhenti terpenuhi. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah 2. beberapa kriteria berhenti yang sering digunakan antara lain:
    • berhenti pada generasi tertentu
    • berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi/terendah (tergantung persoalan) tidak berubah.
    • berhenti bila dalam n generasi berikutnya tidak diperoleh nilai fitness yang lebih tinggi/rendah.

Aplikasi berikut ini adalah aplikasi pengenalan huruf menggunakan algoritma genetika.

Jumlah Populasi yang digunakan : 32

Mutation rate : 15%

String Target : ‘PRASETYO’

Karena yang akan dikenali adalah string yang terdiri dari karakter, maka untuk kromosom yang digunakan adalah angka decimal konversi karakter, misalnya A menjadi 1, B menjadi 2, …., Z menjadi 26. Sehingga interpretasi target adalah : [16 18 1 19 5 20 25 15].

Sedangkan kromosom pada populasi, misalnya hasil generate populasi awal adalah : HNRVEZMQIS, maka bentuk kromosomnya adalah : [8 26 1 3 9 1 9 16].

Sehingga untuk mendapatkan nilai fitnessnya adalah dengan mendapatkan selisih masing-masing gen hasil dengan target dan menjumlahkan semua selisih itu. Hasilnya menjadi pengurang bagi 26 * (jumlah gen dalam 1 kromosom). Diambil 26 karena 26 adalah nilai terbesar dalam abjad dan dijadikan patokan inverse untuk mendapatkan nilai fitnet terbesar.

Fungsi fitness yang digunakan :

F = (26 * jumlahgentiapkromosom) – (jumlah(selisih gen hasil dengan target))

Misalnya untuk kasus contoh diatas :

F = (26*8) – (|8-16|+|26-18|+|1-1|+|3-19|+|9-5|+|1-20|+|9-25|+|16-15|)

F = 208 – (8+8+0+16+4+19+16+1)

F = 208 – 72

F = 136

Seleksi dilakukan dengan sistem turnamen yaitu diambil setengah dari jumlah populasi dengan nilai fitness terbesar (1/2 jumlah populasi dengan fitness terbesar pertama).

Untuk crossover dilakukan dengan sistem single string. Untuk posisi string tersebut dipilih dengan memilih bilangan acak antara 1 hingga ½ jumlah populasi. Untuk kromosom pertama di cross dengan kromosom kedua, kedua dengan ketiga,dst. Sedangkan kromosom terakhir dengan kromosom pertama. Dilakukan pemilihan bilangan acak sebanyak ½ jumlah populasi, sehingga didapatkan turunan sebanyak jumlah populasi hasil dari proses crossover.

Untuk mutasi, yang menggunakan mutasion rate 15%, maka jika menggunakan 32 dan jumlah gen tiap koromoson 8, berarti jumlah gen yang mengalami mutasi tiap generasi adalah : 0.15*8*32 = 38.4 atau dibulatkan 39. Jumlah gen tiap generasi adalah 8*32 = 256. Maka dibangkitkan bilangan acak antara 1 – 256 sebanyak 39 kali. Kemudian kromosom-kromosom disusun secara berurutan dari kiri ke kanan sehingga menjadi 1 baris. Gen yang nilai indeknya sama dengan hasil bilangan acak tersebut akan dimutasi dengan nilai acak antara 1 – 26. Kemudian susunan kromosom dikembalikan seperti semula.

Proses 1 generasi telah selesai.

Proses tersebut dilakukan sebanyak iterasi yang ditentukan atau jika nilai fitness yang mencapai nilai maksimal.

Misalnya :

Populasi awal yang dibangkitkan :

Generasi 1

KROMOSOM                                     SEL   FIT

————————————————  —-  —-

8    26     1     3     9     1     9    16    72   136

14     9    22     7     5    23    17    22    62   146

18     5     4    19     2    25     7    10    49   159

22     5    16    24     1    21    26    16    46   162

5    12     3    24     7     2    15    25    64   144

26     3    26    15    16     6    21    20    88   120

13     7     2    19    23     7    11    19    64   144

17     6    16    10    15    10    10     4    83   125

9    25    23    11    25    11     7    16    92   116

19     4    15    11     4    13     7     3    77   131

2    23    22    19    10     4    17    13    71   137

16     7    19     6     2    23    20    11    57   151

1    19     2     8     7    22     7    10    55   153

10    12    17    18    17    12    22    21    58   150

19    22     6     9     8     5    24    10    46   162

25    23    17     1    24    16    26    21    78   130

5     7    15     2    26     6    10    11   107   101

18     2    14    23    14    21    21    25    59   149

14     1    18    11    21    16    15     1    88   120

21     7     8    15    16    10    21     8    59   149

23     7     1    13    22     2    16    21    74   134

21    17    21    15    22     9     8    22    82   126

10    18     4    15     2    22     8    10    40   168

5    24    21    25    24    10     2    17    97   111

15    17    18    12    24     1    13    20    81   127

20    14     7    18     6    22    16    23    35   173

16    14    19    22     7    12    15     2    58   150

12    23    24     1    16    13     5    16    89   119

3     2    24    14    18    16    21    24    87   121

3    23    23     9    12    21    17     1    80   128

10    20     8    17    22    23    22     9    46   162

9    24     4     9    15    16     3    19    66   142

 

Generasi 2

KROMOSOM                                     SEL   FIT

————————————————  —-  —-

13    14     7    15     2    22    17    10    35   173

10    18     4    18     6    22    16    23    30   178

10    24     8    17    22    23    22     9    50   158

10    18     4    15     3    22     8    10    39   169

10    20     8     9     8     5    24    25    54   154

19    22     6    17    22    23    22     9    43   165

10     5    16    24     1    21    26    16    46   162

22    22     6     9     8     5    24    10    49   159

22     5    21    19     3    25     7    10    69   139

18     5    16    24    11    21    26     8    50   158

18    19     2     8     7    22    14    12    33   175

1     5     4    19     2    25     7    10    62   146

1     7    19     6     2    23    20     6    77   131

16    19     2     6     7    22     7    10    42   166

16     7    19    22    19    12    15     2    77   131

16    14    19     6     2    23    20    11    50   158

12    14    17    18    17    12    22    21    54   154

10    12    19    22     7    12    15     7    61   147

10    12     8     7    16    10    21     8    63   145

21     7    17    18    20    12    22    21    65   143

21     2    14    23    14    21    21    25    62   146

18     2     8    15    16    10    21     8    61   147

18     2    14    23    10    23    17    22    58   150

14     9    22     7    11    21    21    25    65   143

14     9    22    19    23     7    11    19    81   127

13     7     2     7     7    23    17    22    47   161

13    12     3    24     7    23    15    25    41   167

5     7     2    19    17     7    11    19    66   142

4    15     3    24    15    16     6    19    59   149

2    24     4     9     7     6    20    18    57   151

26    24     4     9     6    22    16    23    49   159

20    13    14    22    15    16     3    19    65   143

Generasi 3

KROMOSOM                                     SEL   FIT

————————————————  —-  —-

13    19     2     8     7    22    14    12    34   174

19    18     4    18     6    22    16    23    27   181

11    19     2    15    12    22    17    10    33   175

13    14     7     8     7    22    14    12    42   166

21    14     4    15     3    22     8    10    42   166

10    18     9    14     2    22    17    10    37   171

10    18     3    24    21    23    15    25    52   156

13    12     4    15     3    22     8    10    42   166

13    12     3     2     7    22     7    10    55   153

16    19     2    24     7    23     6    25    41   167

16    19     2    17    22    13    22     9    37   171

22    22     6     6    22    22     7    10    70   138

19    22    16    24     1    21    26    16    34   174

10     5     6    17    22    23    22     1    63   145

10     5    16    24     7    23    17    22    59   149

13     7     2     7     1    24    26    16    37   171

13     7     2     9     6    22    16    23    45   163

5    24     4     7     7    23    17    22    52   156

26    24     4     9    20     5    24    10    65   143

22    22     6     9     6    22    16     1    51   157

22    22     6     9     2    21    20     2    47   161

16    14    16     6     8     5    24    10    56   152

16     8     8     6    11    21    22     8    47   161

18     5    16    24    12    23    20    11    54   154

10    24     8    17    10    23    22     9    38   170

10     5    21    24    11    21    26     8    59   149

19    19    17     6    17    12    22    21    62   146

12    24    23    17    22    23    22     9    63   145

12    20     8     9     8     5    24    25    52   156

10    14    17    18    17    12    22    21    56   152

10    20     4    18    17    22    24    23    35   173

10    18     8     9     8     5    24    25    52   156

 

Berikut ini adalah kromosom terbaik dari generasi 1 sampai generasi 958 (terbaik)

Generasi               KROMOSOM                  SEL  FIT RTFIT   KATA

——– ————————————— — —- —– ——–

1     20   14    7   18    6   22   16   23   35  173  139  TNGRFVPW

2     10   18    4   18    6   22   16   23   30  178  153  JRDRFVPW

3     19   18    4   18    6   22   16   23   27  181  160  SRDRFVPW

4     19   22    2   15   12   22   17   10   34  174  162  SVBOLVQJ

5     10   19    2   17    2   13   22    9   29  179  164  JSBQBMVI

.

.

.

956     16   18    1   18    5   20   25   15    1  207  193  PRARETYO

957     15   18    1   18    5   20   25   15    2  206  192  ORARETYO

958     16   18    1   19    5   20   25   15    0  208  192  PRASETYO

 

Kromosom terbaik mempunyai nilai fitness maksimal yaitu 208 dengan kata : ‘PRASETYO’ yang didapat pada populasi dengan generasi ke 958.

Berikut ini source codenya (MATLAB) :

target = ‘PRASETYO’; jmlPop = 32; mut = 0.15;

 

[M,N] = size(target);

targetdec = [];

for i=1:N

tmp = cast(target(i),’uint8′)-64;

%targetdec = cat(2,targetdec,tmp);

targetdec(i) = tmp;

end

Popangka = []; Pophuruf = [];

for i=1:jmlPop

for j=1:N

Popangka(i,j) = ceil(rand()*26);

end

end

clear Krombest;clear RataFit, clear Hasil;

for iterasi = 1:2000

% Melakukan hitung fitness

% 26(N) – f

maks = 26*N;

%Fit = []; Sel = [];

for i=1:jmlPop

nilaiF = 0;

for j=1:N

nilaiF = nilaiF + abs(targetdec(j)-Popangka(i,j));

end

Popangka(i,N+1) = nilaiF’;

Popangka(i,N+2) = abs(maks-nilaiF)’;

end

%Popangka

Popangka2 = flipud(sortrows(Popangka,N+2))

Krombest(iterasi,:) = Popangka2(1,:);

RataFit(iterasi) = mean(Popangka(:,N+2));

Hasil{iterasi} = huruf(Krombest(iterasi,1:N));

Pop{iterasi} = Popangka;

if Krombest(iterasi,N+2) == maks

break;

end

 

% Seleksi, pakai turnamen

% Hitung prop dan kumulasinya

Popangka = flipud(sortrows(Popangka,N+2));

Popbaru = Popangka(1:ceil(jmlPop/2),:);

 

% Lakukan crossover

% pakai single point

% titik antara 2 sampai N/2

clear Popbaru2;

tengah = ceil(jmlPop/2);

for i=1:tengah

acak = ceil(rand()*ceil(N/2))+1;

if i == tengah

j = 1;

else

j = i+1;

end

tmp11 = Popbaru(i,1:acak-1);

tmp21 = Popbaru(j,1:acak-1);

tmp12 = Popbaru(j,acak:N);

tmp22 = Popbaru(i,acak:N);

tmp = cat(2,tmp11,tmp12);

Popbaru2(2*i-1,:) = tmp;

tmp = cat(2,tmp21,tmp22);

Popbaru2(2*i,:) = tmp;

end

SeqKrom = reshape(Popbaru2′,[N*jmlPop 1])’;

 

% Mutasi

% 25% dilakukan mutasi shg 0.25*N*jmlPop

jmlMut = mut*N*jmlPop;

for i=1:jmlMut

acak = ceil(rand()*N*jmlPop);

SeqKrom(acak) = ceil(rand()*26);

end

Popangka = reshape(SeqKrom,[N jmlPop])’;

end

Krombest(:,N+3) = RataFit’;

 

11 Responses to APLIKASI PENGENALAN KATA DENGAN ALGORITMA GENETIKA

  1. rama says:

    Boz masih bingung….bisa dintu ngak????????

  2. klm says:

    trimakasih pak. saya jadi ada sedikit pencerahan dari tulisan bapak ini. pusing tujuh keliling dengan algen ini. menurut saya algen ini ilmu nya serba terserah.hehehe. apalagi untuk representasi kromosom…itu yang paling pusing. share lagi ya pak kalo ada contoh kasus algen lain.

    • prasetyo2008 says:

      #klm : dalam pembentukan struktur kromosom memang kebanyakan ditentukan secara mandiri oleh programmer, tetapi hal ini adalah bagian paling sulit karena bentuk kromosom harus nantinya harus bisa dilakukan crossover dan mutasi sesuai aturan, meskipun operand crossover dan mutasi tidak harus sesuai standart, tetapi prinsip crossover dan mutasi sudah dijalankan sesuai prinsip utama.

  3. klm says:

    pak, apakah suatu penyelesaian yang didalamnya ada crossover dan mutasi saja sudah bisa dibilang algoritma genetik? ataukah harus lengkap dia ada representasi kromosom,seleksi,penentuan fitness, crossover, mutasi dll (lengkap) baru bisa dibilang algoritma genetik? pernah membaca sebuah jurnal yang dia kriptosystem dengan menggunakan algoritma genetik dan ternyata di dalamnya hanya ada crossover dan mutasi saja.
    ada trik2 tertentu ga pak untuk menentukan representasi kromosom ?
    terima kasih sekali. semoga tidak bosan untuk share nya😀

    • prasetyo2008 says:

      umumnya, minimal ALgoritma Genetika mempnyai komponen : kromosom, fitness, seleksi dan mutasi. Tanpa crossover pun gak papa, sudah bisa disebut Al-Gen. tidak ada mutasi juga boleh. tetapi biasanya tanpa mutasi akan sulit dan lama untuk mencapai konvergensi. Dengan elitisme, crossover dan mutasi diharapkan AL-Gen akan berkerja dengan lebih baik (lebih mirip teori evolusi) dan cepat dalam mencapai konvergensi. Jumlah populasi dan mutation ratejuga berpengaru pada jumlah generasi yang dicapai saat mendapatkan titik konvergen.

      Saya tidak ada trik khusus dalam membuat kromosom. Karena hal ini sifat kontekstual (sangat dipengaruhi kasusnya). Hanya saja usahakan struktur kromosomnya usahakan dapat memenuhi tujuan prhitngan fitness, mutasi, dan crossover dengan baik.
      Semoga membantu.

  4. nanda says:

    mas, saya sdh coba program di atas tapi masih error kok?
    errornya di
    Hasil{iterasi} = huruf(Krombest(iterasi,1:N));

    di kata hurufnya error
    ??? Undefined function or method ‘huruf’ for input arguments of type ‘double’.

    mohon d balas segera ya mas, saya perlu sekali ini….😦

    • Eko Prasetyo says:

      Variabel huruf itu isinya harus array 1 dimensi yang isinya karakter A-Z. Mudah2an bisa membantu.

  5. Putry says:

    Maaf mas,, boleh kirim project’a ke email saya??

  6. trinil says:

    Terima kasih atas share Ilmunya, moga Ilmu yang di share dapat bermanfaat bagi orang lain.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: