Algoritma Genetika Sederhana dengan Pseudo Code C-Like

Permasalahan:

Diberikan fungsi di bawah ini:

Maksimalkan      f(x₁, x₂) = 21.5 + x₁ sin(4pix₁) + x₂ sin(20pix₂)

-3.0 < x₁ < 12.1

4.1 < x₂ < 5.8

Input:

jumlah populasi awal pop_size,

probabilitas crossover p_r,

probabilitas mutation p_m,

banyak iterasi

Fungsi-fungsi:

Fungsi yang harus ada dalam program:

initPop: untuk mendapatkan populasi awal sebanyak popsize

Evaluation: mengevaluasi nilai fitnes masing-masing kromosom

Selection:

menciptakan populasi baru dari populasi lama yang berhubungan dengan distribusi probabilitas pada nilai fitness-nya.

Crossover:

sebagai metode pemotongan kromosom, yang secara random memilih titik potong pada kromosom dan menggantinya dengan bagian kanan dari 2 kromosom induk (parent) untuk menghasilkan kromosom anak (offspring)

Mutation:

mengubah satu atau lebih gen dengan probabilitas sama dengan angka mutasi.

Fungsi tambahan:

printBitStr: mencetak bit string, baik populasi maupun substring.

BitRequired: mencari bit yang diperlukan untuk variable x₁ dan x₂.

decimal_substr: mendapatkan nilai decimal dari variable substring

decision: mendapatkan variable keputusan

separate:

memisahkan bitstring sumber sebanyak popsize pada bit ke batas bawah sampai batas atas kemudian dicopykan ke populasi bitstring tujuan, bisa juga untuk mengcopy semua bitstring sumber ke bitstring tujuan.

Eval: mengevaluasi fungsi obyektif.

Pilihan: mengatur mode output, mode adalah variable global.

Output:

Nilai maximum yang didapat, nilai x₁ dan x₂ saat kondisi maksimum.

max, x₁max, dan x₂max adalah variable global.

ALGORITMA:

Fungsi main

1.  Atur mode output yang ditampilkan

2.  hitung range

3.  hitung jumlah bit yang diperlukan oleh variable x1 dan x2

4.  input populasi, jumlah iterasi, peluang crossover, dan peluang mutasi.

5.  i<-0

6.  do

i.   evaluation

ii.   selection

iii.   crossover

iv.   mutation

7.  until i=jumlah iterasi

8. print nilai maximum fungsi, x₁ dan x₂ saat fungsi maximum

Fungsi printBitStr

Input: int bitstr[maxpop][maxbit]

1.  j=0, i=0

2.  while bitstr[i][j] not equal to -1

a.  do while bitstr[i][j] not equal to -1

i.   do print bitstr[i][j]

ii.   j <- j+1

b.  change to next row

c.  j=0

d.  i++

Fungsi bitRequired

Input: unit

1.  i<-0

2.  while unit/(2ⁱ) > 1

a.  do i <- i+1

3.  return i

Fungsi decimal_substr

Input: substr[maxbit]

1.  temp=0

2.  for j=number of bit – 2 down to 0

a.  temp <- temp+substr[j]*2^(i-1)-j

3.  return temp

Fungsi decision

Input: double aj, bj; long substrd; int mj

1.  d= convert substrd to double

2.  hasil = a_j+d*

3.  return hasil

Fungsi separate

Input: bitstr[maxpop][maxbit], substr[maxpop][maxbit], bawah, atas

1.  j<-bawah

2.  i<-0

3.  while bitstr[i][j-bawah]not equal to -1

a.  do while j<atas

i.   substr[i][j-bawah] <- bitstr[i][j]

ii.   j++

b.  substr[i][j-bawah] <- -1;

c.  substr[i][j-bawah+1] <- NIL;

d.  j <- bawah;

e.  i <- i+1

4.  substr[i][0] <- -1;

5.  substr[i][1] <- NIL;

Fungsi eval

Input: x[2]

1.  fx <- 21.5 + x[0]*sin(4*π*x[0]) + x[1]*cos(4*π*x[1])

2.  return fx

Fungsi Evaluation

Input parameter: double x[2][MAXPOP], int bitstr[MAXPOP][MAXBIT], int substr[2][MAXPOP][MAXBIT], int bit1, int bit2.

1.  x1bawah <- -3.0

2.  x1atas <- 12.1

3.  x2bawah <- 4.1

4.  x2atas <- 5.8

5.  for I = 0 to popsize

a.  substrd[0][i] <- decimal_substr(substr[0][i])

b.  substrd[1][i] <- decimal_substr(substr[1][i])

c.  x[0][i]<-decision(x1bawah,substrd[0][i],x1atas,bit1)

d.  x[1][i]<-decision(x2bawah,substrd[1][i],x2atas,bit2)

e.  xT[i][0]<-x[0][i];

f.  xT[i][1]<-x[1][i];

g.  V[i]=eval(xT[i]);

h.  If V[i]>max then

i.   Max<-V[i];

ii.   x1max<-x[0][i];

iii.   x2max<-x[1][i];

6.  substrd[0][i] <- ”;

7.  substrd[1][i] <- ”;

8.  x[0][i] <- ”;

9.  x[1][i] <- ”;

10.xT[i][0] <- ”;

Fungsi Selection

Input Parameter: double x[2][MAXPOP], int bitstr[MAXPOP][MAXBIT], int bit1, int bit2

1.  For i=0 to popsize

a.  xT[i][0] <- x[0][i];

b.  xT[i][1] <- x[1][i];

c.  V[i] <- eval(xT[i]);

d.  totalFitness <- totalFitness+V[i];

2.  For i=0 to popsize

a.  PK[i] <- V[i]/totalFitness;

b.  QK[i] <- 0;

c.  For j=0 to i

i.   QK[i] <- QK[i]+PK[j]

3.  For i=0 to popsize

a.  R=random number(double) between 0 to 1

b.  j <- 0

c.  While R > QK[j]

i.   j <- j+1

d.  For k=0 to totalbit

i.   DupBS[i][k] <- bitstr[j][k]

e.  DupBS[i][k] <- -1

4.  DupBS[i][0] <- -1

5.  separate(DupBS,bitstr,0,bit1+bit2);

Fungsi CrossOver

Input parameter: int bitstr[maxpop][maxbit], double Pc, int bit1, int bit2

1.  do

a.  k<-0;

b.  count<-0;

c.  while k<popsize do

i.   r=random number(double) between 0 to 1

ii.   if(r<Pc) then

1.  iSelected[count] <- k

2.  count <- count +1

iii.   end if

iv.   k <- k+1

2.  until count more than 1 and even (not odd)

3.  separate(bitstr,Vselected,0,bit1+bit2)

4.  i <- 0

5.  while i<count

a.  pos = random number between 0 to totalbit-1

b.  for k=pos to bit1+bit2

i.   temp <- Vselected[iSelected[i]][k];

ii.   Vselected[iSelected[i]][k]<-Vselected[iSelected[i+1]][k];

iii.   Vselected[iSelected[i+1]][k] <- temp;

c.  i <- i+2

6.  separate(Vselected,bitstr,0,bit1+bit2);

Fungsi Mutation

Input parameter: int bitstr[maxpop][maxbit], double Pm, int bit1, int bit2

1.  count <- 0

2.  for i=0 to popsize*(bit1+bit2)

a.  r = random number (double) between 0 to 1

b.  if r<Pm then

i.   BitPos[count]<-i

ii.   Count <- count + 1

c.  End if

3.  for i=0 to count

a.  ChromNo <- BitPos[i]/(bit1+bit2)

b.  BitNo <- BitPos[i]%(bit1+bit2)

c.  if(bitstr[ChromNo][BitNo]==0) then

i.   bitstr[ChromNo][BitNo] <- 1

d.  else

i.   bitstr[ChromNo][BitNo] <- 0

e.  end if