Vol. 14, No. 1,  19-27,  Juli  2017
Pemaksimalan Papan Sirkuit Di Pandang Sebagai Masalah Planarisasi Graf 2-Layer Menggunakan Algoritma Genetika
Jusmawati Massalesse  dan Muh. Ali Imran 

## Abstrak
Tulisan  ini  dimaksudkan  untuk  menyelesaikan  permasalahan  pencetakan  papan  sirkuit  2-layer melalui suatu algoritma pencarian yang dikenal sebagai Algoritma Genetika. Tujuannya adalah mendapatkan  jumlah  jalur  terbanyak  yang  dapat  dicetak  pada  sebuah  papan  sirkuit  2  layer. Algoritma  Genetika  melakukan pencarian melalui  proses  evolusi  tiruan  dengan  menggunakan suatu  fungsi  ukuran  yang  disebut  fungsi  fitness.  Proses  evolusi  dilakukan  melalui  simulasi dengan  bantuan  komputer  menggunakan  software  Mathlab.  Representasi  permasalahan dinyatakan dalam graf K n . Di dalam tulisan ini, diambil graf K 10 sebagai contoh kasus. Setelah dilakukan iterasi  sejumlah 1500 kali diperoleh hasil bahwa nilai  fitness tertinggi dicapai  mulai pada iterasi ke 1000. Subgraf planar maksimal diperoleh dengan menghilangkan 7 sisi dari graf K 10 . Hal ini berarti bahwa apabila terdapat 10 konektor yang akan dicetak pada papan sirkuit 2- layer  maka  jumlah  jalur  maksimal  yang  dapat  dicetak  adalah  jumlah  sisi  K 10 dikurangi  7  (45- 7=38).
Kata Kunci : Algoritma Genetika, fungsi obyektif, fungsi fitness, graf planar.

## 1. Pendahuluan
Masalah  planarisasi  sampai  sejauh  ini  masih  merupakan  masalah  terbuka  mengingat belum  ditemukan  suatu  metode  atau  algoritma  standar  untuk  menyusun  kembali  sisi-sisi  graf menjadi tidak saling berpotongan.
Planarisasi graf satu layer telah dilakukan melalui penelitian sebelumnya yang berjudul Planarisasi graf dengan Algoritma Genetika. Berangkat dari hasil yang diperoleh pada penelitian tersebut, algoritma yang sama akan digunakan untuk  menyelesaikan masalah planarisasi graf 2- layer.  Pada  masalah  planarisasi  graf  dua  layer,  Algoritma  Genetika  bekerja  menemukan  cara dalam  menyusun  sisi-sisi  graf  ke  dalam  dua  layer  dengan  himpunan  simpul  yang  sama  pada kedua layer. Kromosom yang mewakili solusi memuat informasi mengenai peletakan sisi-sisi graf dan cara pemilihan sisi graf sehingga menjadi 2 subgraf planar dengan jumlah sisi maksimum.
Masalah  planarisasi  graf  2-layer  terkait  dengan  penyusunan  papan  sirkuit  elektronik, sehingga hasil yang diperoleh melalui penelitian ini di harapkan memberikan kontribusi di bidang teknologi, khususnya industri elektronik.
Metode  yang  digunakan  banyak  dikembangkan  pada  dekade  belakangan  ini,  karena metode pencariannya hanya melibatkan fungsi obyektif dari permasalahan yang akan dikaji. Sifat
 Staf pengajar  pada Jurusan Matematika  F.MIPA Universitas Hasanuddin  Makassar Jusmawati2004@yahoo.com
 Lulusan program studi Matematika Jurusan Matematika F.MIPA Universitas  Hasanuddin  Makassar

## Jusmawati Massalesse, Muh. Ali Imran
pencariannya yang probabilistik juga memungkinkan untuk menemukan solusi pendekatan untuk permasalahan yang tidak memiliki solusi eksak.

## 2. Algoritma Genetika

## 2.1 Konsep dasar
Secara  umum  penyelesaian  masalah  melalui  Algoritma  Genetika  diawali  dengan mengkode  parameter  permasalahan  menjadi  individu  yang  selanjutnya  disebut  kromosom. Kromosom  ini  akan  berevolusi  melalui  operator-operator  genetika  sampai  diperoleh  kromosom terbaik,  yaitu  kromosom  dengan  nilai  fitness  paling  tinggi.  Disini,  nilai  fitness  merupakan  nilai yang  menyatakan  kesanggupan  kromosom  untuk  eksis  atau  bertahan  hidup  sepanjang  proses evolusi.
Operator  genetika  yang  digunakan  dalam  penelitian  ini  adalah  operator  reproduksi, crossover  dan  mutasi.  Dalam  prakteknya,  terdapat  banyak  metode  reproduksi,  crossover  dan mutasi yang dapat digunakan, tetapi pada prinsipnya memiliki tujuan sebagai berikut:

## a. Reproduksi
Operator  reproduksi  dimaksudkan  untuk  mempertahankan  dan  menggandakan  individu terbaik  di  dalam  populasi.  Prosedur  reproduksi  dilakukan  dengan  menghitung  nilai  fitness, total fitness, peluang fitness dan peluang kumulatif untuk masing-masing kromosom di dalam populasi melalui rumus berikut:
- Total fitnes =   p i fit i f 1 ) ( ,
p = ukuran populasi.
- Peluang fitnes(j) =   p i fit fit i f j f 1 ) ( ) ( - Peluang kumulatif(j) =    j i i j fitnes
Peluang 1 ) (

## b. Crossover atau penyilangan
Operator ini dikenakan terhadap populasi hasil reproduksi.  Melalui operator ini diharapkan muncul individu baru yang masih memiliki sifat-sifat induknya.
c. Mutasi
Operator mutasi diperlukan untuk menampilkan keragaman individu yang kemungkinan tidak muncul melalui operator reproduksi dan persilangan saja.
Populasi yang telah melewati operator mutasi adalah populasi yang telah melewati satu kali proses evolusi. Populasi ini selanjutnya disebut Populasi Generasi Pertama. Proses evolusi dilakukan secara terus menerus sampai nilai fitness konvergen ke satu titik.

## 2.2  Planarisasi Graf Dengan Algoritma Genetika
Diberikan  sebuah  graf  lengkap  K n .  Pengambilan  ini  didasarkan  pada  pertimbangan bahwa graf sederhana yang terdiri dari n simpul yang memiliki sisi terbanyak adalah K n . Tujuan penelitian adalah mereduksi sisi K n menjadi dua subgraf planar dengan himpunan n simpul yang sama  dengan jumlah  sisi terbanyak.
Proses  ini  dimulai  dengan  mengkonstruksi  dua  graf,  yaitu  G 1 (V 1 ,E 1 )  dan  G 2 (V 2 ,E 2 ) yang memenuhi syarat berikut:
1 10 - V 1 = V 2 =V(K n ) - E 1  E 2 =  - E 1  E 2 =E(K n ),  E 1 ,E 2  E(K n )
Graf G 1 dan G 2 masing-masing merupakan graf pada layer pertama dan layer kedua. Pada proses pencarian yang menggunakan Algoritma Genetika, pengkodean parameter merupakan  masalah  utama  yang  harus  diselesaikan  terlebih  dahulu  sebelum  mengenakan oparator-operator  genetika.  Jadi  permasalahan  pertama  yang  harus  diselesaikan  dalam memplanarkan  graf  adalah  bagaimana  mengkodekan  graf  menjadi  parameter  berbentuk kromosom. F. Comellas (1992) dalam jurnalnya yang berjudul “ Using Genetic Algorithms for planarization  Problem ”    menulis  bahwa  untuk  melakukan  pengkodean  parameter,  graf digambarkan dengan metode straight line sebagaimana diperlihatkan pada Gambar 1.

## Gambar 1
Sisi-sisi dari graf diletakkan di sebelah atas (selanjutnya disebut sisi atas) atau di sebelah bawah (selanjutnya  disebut  sisi  bawah).  Sisi  atas  (i,j)  dikodekan  sebagai  gen  yang  bernilai  ”1” sedangkan sisi bawah (i,j) dikodekan sebagai gen yang bernilai ”-1”. Jika pasangan simpul (i,j) bukan sisi maka nilai gen yang bersesuaian adalah ”0”.
Kromosom  dibangun  dengan  cara  sebagai  berikut:  misalkan  diberikan  sebuah  graf dengan  himpunan  simpul  V(G)={1,2,...n}  maka  sebuah  kromosom  tersusun  atas  sisi-sisi  (i,j) sebagai gen dengan urutan sebagai berikut:
Di mana (i,j) bernilai ”1” atau ”-1” tergantung posisi sisi sebagai sisi atas atau sisi bawah.

## 3. Pembahasan
Simulasi proses evolusi oleh Algoritma Genetika dikenakan terhadap K 10 sebagaimana diperlihatkan pada Gambar 2. Pemilihan graf ini tentu saja dapat dilakukan terhadap graf lengkap yang  mempunyai  simpul  lebih  banyak,  disesuaikan  dengan  kemampuan  komputer  yang digunakan.
    …  
1                 2                 3               4                                 n-1                 n
(1,2)(1,3)...(1,n)(2,3)(2,4)...(2,n)..........(n-2,n-1)(n-2,n)(n-1,n) 9 6 4 2 3 7 8 5 Gambar 2. Graf K 10

## Jusmawati Massalesse, Muh. Ali Imran

## 1. Kode Parameter.
Dengan  metode straight-line ,  graf  pada  Gambar  2  dapat  digambarkan  menjadi 4 45 =1.23794 x 10 27 cara yang berbeda, salah satu diantaranya sebagaimana diperlihatkan berikut ini:
Gambar 3. K 10 dengan metode straight-line
Kromosom yangbersesuaian dengan graf pada Gambar 3 adalah
Jadi terdapat 1.23794 x 10 27 kombinasi kromosom berbeda yang dapat dibangkitkan dari graf K 10 . Sepanjang proses, apabila terdapat sisi yang berpotongan maka sisi tersebut akan dihilangkan dari graf. Nilai gen yang bersesuaian dengan sisi yang dihilangkan dari graf adalah “0”. Sehingga ruang solusi merupakan himpunan semua kromosom yang terdiri dari susunan 45 gen bernilai -2, -1,  0,  1  atau  2.  Jadi  ruang  solusi  terdiri  dari  24 5 =  184528125  kromosom.  Proses  evolusi  akan melakukan pencarian pada ruang solusi untuk menemukan kromosom terbaik.
Proses  evolusi  diawali  dengan  membangkitkan  populasi  awal  berukuran  100.  Populasi  awal  ini dibangkitkan  secara  acak  melalui  program  Matlab.  Tabel  1  menampilkan  10  individu  pertama pada populasi tersebut.
Tabel 1.  Populasi Awal
1 2 4 5 6 7 3 8 9 10
2-2-2-21-1-1-1-2-112211-2-11-1-1-1-111-2-2-211-1-12122-1121-12-22-21 Kromosom Populasi Awal 1 -2    -1     1     2     1    -2     1    -2    -2     1     1     2     1     1    -1    -2    -2    -1     1    -1     1    -1    -1     1     1     1    -2     2    -2    -2    -1    -1     2    -2    -2    -2    -2     2     1     1    -2    -1     1     2    -1 2 2     1     2    -2    -2     2    -2    -2    -2     1     2    -2     1     2     1    -2    -2    -2     2     2    -2    -1    -2    -1     2    -2     1    -1     2    -2    -1     2    -2    -2     1    -1    -1    -1     2     1     2    -1     2     1     1 3 2     2    -2     2     1     1    -1    -1    -1     1     1     2     1     1    -2    -1    -2    -2    -2    -1     1     1    -2    -1     2    -1     1     1    -2    -1     1    -2    -2     1     1     1     1    -2     2    -2    -2     1    -1    -2     2 4 2     2    -2    -2     1    -1     1    -2     1    -2    -2    -1    -2    -1    -1     1     2     2     2     2     1    -2    -2     1    -1    -1     1     1    -2    -2     1     1    -2    -2    -2     2    -1    -1     2     2     1    -2    -1     1    -2 5 -1    -2    -1     1     2    -1     1     2    -1     2     1     1     2     2     1    -1     2    -2     2    -1     1    -1    -1    -1     2    -1    -2     2     2    -1    -1    -2     2     1     1    -1     2    -2    -2     2    -2    -1     1    -2    -1 6 -1    -2    -2    -1     1    -2    -1     1    -2    -1    -1    -2    -2    -1     1     2     2    -2     1    -2    -1     1    -2    -2    -2    -2     2     2    -2    -2    -1     2     1     2     1     1     1    -2    -1     2    -1     1     2    -1     2 7 1     2     1    -2     2    -1     1    -2    -2    -1     1    -2    -1     2    -1    -1     1    -2    -1     2     1    -1     1     2     1     2    -2     1    -2     1     2     1     1    -2    -2    -2    -2    -1    -1    -2    -1    -2    -1     1    -2 8 1     2    -1     1    -2     2     1     1     1    -1    -1    -1     2    -2    -1    -1    -2    -1    -2     2     1    -2     2    -2     1     2    -2    -2     2    -2     2     2     2    -1    -2     2    -2     1    -1     2     1     2     2    -2     2 9 2     1     1    -2    -1    -2     2     2     2     1    -2     2     2    -1     1     1     2    -2     2     2    -2     1    -2    -2    -1    -1    -1    -2     2    -2     1     2    -2     2    -2     1     2     1    -2     1    -1     1     2     1     1 10 -1    -2    -2     2     2     1    -2     2    -2     2    -1     2    -2    -1     2     2    -2    -1    -2     1    -1    -1     2    -2     1     2     1     1     1    -2     2     1    -1    -1     2     1     1     1    -2     1     2     1     2     2    -2

## 2. Fungsi Fitness
Planarisasi graf berkaitan dengan reposisi sisi-sisi graf sehingga menjadi tidak berpotongan. Oleh karena itu, fungsi obyektif dapat dirumuskan sebagai sebuah persamaan fungsi sebagai berikut:
) . ( . c e c c obj e v M c v f    (1)
di mana:
v c = bobot c c v e = bobot e c e c = jumlah perpotongan sisi e c = jumlah sisi dalam graf M = jumlah sisi graf lengkap 2-layer
Penentuan sisi berpotongan dilakukan sebagai berikut:
Misalkan  (i,j)  dan  (k,l)  adalah  dua  sisi  pada  graf,  maka  (i,j)  dan  (k,l)  berpotongan  jika i<k<j<l atau k<i<l<j dan nilai gennya sama.
Makin kecil nilai f oby , makin baik kromosom yang bersesuaian. Karena fungsi fitness adalah fungsi yang menyatakan ukuran sehat atau tidaknya suatu kromosom, maka suatu kromosom yang  memiliki  nilai  fitness  lebih  besar  pastilah  berkaitan  dengan  nilai f oby yang  lebih  kecil. Oleh karena itu, fungsi fitness dikonstruksi sebagai berikut:
obj fit f f 1  (2)
Dari  persamaan  (1),  dipilih  bobot v c =1,6  sedangkan  bobot  v e =1,  sehingga  fungsi  obyektif menjadi:
3 ) 45 (
. 6 . 1     c c obj v c f (3)
Penambahan  faktor  3  pada  persamaan  (1)  dimaksudkan  untuk  menghindari        penyebut menjadi nol pada konstruksi fungsi fitness.
Hasil  perhitungan  dengan  program  Matlab  berdasarkan  populasi  awal  pada  Tabel  1  dapat dilihat pada Tabel 2.
Tabel 2. Nilai objektif dan Fitness, Peluang fitness dan kumulatif.
Individu Nilai_obj Nilai_fit Peluang_fi t Peluang_kom  Bil. Acak r (1) (2) (3) (4) (5) (6) 1 2 3 4 5 6 7 8 9 10 79.2000 95.2000 108.0000 90.4000 82.4000 79.2000 72.8000 82.4000 92.0000 98.4000 0.0126 0.0105 0.0093 0.0111 0.0121 0.0126 0.0137 0.0121 0.0109 0.0102 0.0181 0.0151 0.0133 0.0159 0.0174 0.0181 0.0197 0.0174 0.0156 0.0146 0.0181 0.0332 0.0464 0.0623 0.0797 0.0978 0.1175 0.1349 0.1505 0.1650 0.2748 0.1255 0.7584 0.7654 0.4305 0.7559 0.7492 0.5676 0.1073 0.2094
3. Operator Genetika
- Reproduksi roulette-wheel
Model  reproduksi  yang  digunakan  disini  adalah  reproduksi  roulette-wheel  yang prosesnya  mengikuti  cara  kerja  meja  roulette,  dimana  kromosom  yang  memiliki  selisih peluang  kumulatif  lebih  besar  dengan  kromosom  sebelumnya  berpeluang  lebih  besar untuk  terseleksi  kembali  sebagai  kromosom  pada  generasi  selanjutnya.  Proses  seleksi dilakukan  dengan  membangkitkan  bilangan  acak  r  sebanyak  jumlah  kromosom  didalam populasi. Sepuluh bilangan acak r yang pertama ditampilkan pada kolom 6 Tabel 2. Hasil seleksi diperlihatkan pada Tabel 3.

## Tabel 3. Populasi Hasil Reproduksi
Individu Kromosom 1 1    -1     1     2    -1    -1     2    -1     2    -1    -1    -1    -1    -1     1    -1     1     2    -1    -2     1     2     2    -2    -1    -2     2     2     1     1     2    -2    -1     1     1     2    -2    -1     1    -1     1     1 -1    -1    -1 2 1     2    -1     1    -2     2     1     1     1    -1    -1    -1     2    -2    -1    -1    -2    -1    -2     2     1    -2     2    -2     1     2    -2    -2     2    -2     2     2     2    -1    -2     2    -2     1    -1     2     1     2 2    -2     2 3 1     2     1    -2     1     1    -2    -2    -1     2    -1     1     1     1     1    -2     2     2     1     2    -1    -2    -1     2     2     1     1     1    -1     2    -2    -2     2    -2     1    -1    -2     1    -1     2    -2     1 2    -2    -1 4 11     2     1    -2     2     1    -2    -2    -1     2    -1     1     1     1     1    -2     2     2     1     2    -1    -2    -1     2     2     1     1     1    -1     2    -2    -2     2    -2     1    -1    -2     1    -1     2    -2     1 2    -2    -1 5 -1    -1    -2    -2    -1    -2     1     2    -1    -2    -2     2     1    -2    -1    -2    -2    -2    -2    -2     2     2    -1     2     1    -2     1    -2    -2     2     1    -1    -2    -2    -1    -2    -2     2     1    -2     1 2     2     2     2 6 1     2     1    -2     1     1    -2    -2    -1     2    -1     1     1     1     1    -2     2     2     1     2    -1    -2    -1     2     2     1     1     1    -1     2    -2    -2     2    -2     1    -1    -2     1    -1     2    -2     1 2    -2    -1 7 1    -2     2    -2    -1     1    -1     1     1     1    -1     2    -2     2     2     2    -2     1     2    -1     1    -1     1     1     2    -1    -1     1     2     2    -2    -1     2     2     2     1     1     1     2    -2     1    -2 1     2    -1 8 -2     2    -2     2    -2    -1    -1     2     2     2     2     1    -2     2    -1    -1    -2     2    -1    -2     2    -2    -1    -2    -2    -2     1    -1     2     2    -1    -1     1     1     2    -2     1     1    -1    -1    -2 1    -1    -2    -2 9 1     2     1    -2     2    -1     1    -2    -2    -1     1    -2    -1     2    -1    -1     1    -2    -1     2     1    -1     1     2     1     2    -2     1    -2     1     2     1     1    -2    -2    -2    -2    -1    -1    -2    -1    - 2    -1     1    -2 10 1     2     2    -2     2    -1     1     2     1    -2    -2    -1     2    -2    -1    -1     1    -1    -2    -1    -1     1    -1    -1    -2     2    -1     2    -1     2    -1    -2     2    -1     1    -1     2     1    -2     1    -1    - 1    -1    -2    -1
- Penyilangan one-cut point
Penyilangan  dengan  metode one-cut  point dilakukan  dengan  memasangkan  kromosom secara  acak,  kemudian  memilih  1  titik  penyilangan  yang  akan  menentukan  posisi pemotongan  kromosom.  Misalkan  kromosom  ke-6  dan  ke-10  terpilih  sebagai  pasangan pertama yang mengalami penyilangan, dan r=20 adalah titik penyilangan.
6 1     2     1    -2     1     1    -2    -2    -1     2    -1     1     1     1     1    -2     2     2     1         |     -1    -2    -1     2     2     1     1     1    -1     2    -2    -2     2    -2     1    -1    -2     1    -1     2    -2     1    -  2    -2    -1 10 1     2     2    -2     2    -1     1     2     1    -2     -2    -1     2    -2    -1    -1     1    -1    -2     |      -1    -1     1    -1    -1    -2     2    -1     2    -1     2    -1    -2     2    -1     1    -1     2     1    -2     1    -1    -1    -1    -2    -1

## Jusmawati Massalesse, Muh. Ali Imran
Maka kromosom baru hasil penyilangan adalah:
1’
1     2     1    -2     1     1    -2    -2    -1     2    -1     1     1     1     1    -2     2     2     1         |       -1    -1     1    -1    -1    -2     2    -1     2    -1     2    -1    -2     2    -1     1    -1     2     1    -2     1    -1    -1    -1    -2    -1
2’
1     2     2    -2     2    -1     1     2     1    -2     -2    -1     2    -2    -1    -1     1    -1    -2     |      -1    -2    -1     2     2     1     1     1    -1     2    -2    -2     2    -2     1    -1    -2     1    -1     2    -2     1    -  2    -2    -1
- Mutasi
Didalam  penelitian  ini  dipilih  =0.001,  yang  berarti  sekitar  1%  gen  di  dalam  populasi akan mengalami mutasi. Proses dimulai dengan membangkitkan bilangan random r  (0,1) sebanyak jumlah gen di dalam populasi. Gen yang bersesuaian dengan bilangan random r  akan  mengalami  mutasi  dengan  cara  merubah  nilai  gen  tersebut  menjadi  nilai  gen lain di dalam himpunan nilai gen {-2,-1,0,1,2}. Proses evolusi secara lengkap mengikuti alur kerja berikut ini:
Gambar 4. Alur kerja  proses evolusi
Stop TIDAK Start Populasi awal fungsi Objektif i = 1, 2, 3, …, n Nilai Fitnes fungsi_fitnes(i) = i = 1, 2, 3, …, p Kriteria Konvergensi Reproduksi Populasi Baru YA Crossover Mutasi

## Jusmawati Massalesse, Muh. Ali Imran
Melalui  program  simulasi  dilakukan  iterasi  sebanyak  2000  kali  (2000  generasi).  Pada  setiap generasi  dipilih  kromosom  terbaik  kemudian  diplot  pada  bidang  dengan  sumbu  mendatar menyatakan generasi ke- sedangkan sumbu tegak menyatakan nilai fitness terbaik .
Gambar 5: Plot generasi versus nilai fitness tertinggi
Grafik yang diperoleh  menyatakan bahwa  nilai fitness terbaik  konvergen ke nilai fitness 0,0909. Nilai ini merupakan nilai fitness dari kromosom:
Representasi  graf    2-layer  maksimal  dari  kromosom  tersebut  sebagaimana  diperlihatkan  pada Gambar 4.
Gambar 6. Subgraf planar maksimal dari K 10

## 4.  Kesimpulan
Dari  proses  dan  hasil  yang  diperoleh  melalui  running  program  simulasi  yang  disusun menggunakan software Matlab, ternyata pengambilan nilai parameter dan kemampuan komputer sangat menentukan pencapaian solusi. Beberapa hal yang menjadi perhatian adalah:
1. Pengambilan populasi awal yang berukuran kurang dari 100 menyebabkan jangkauan ruang solusi  membutuhksan  iterasi  yang  jauh  lebih  banyak  dibandingkan  dengan  populasi  yang berukuran  100.  Sedangkan  untuk  ukuran  populasi  yang  lebih  besar  dari  100,  dibutuhkan waktu yang lama untuk menghasilkan output dalam satu kali running . Ukuran populasi yang ideal adalah 100, dan diperlukan minimal 1500 kali iterasi untuk mencapai solusi.
2. Proporsi jumlah gen yang mengalami mutasi yang terlalu kecil (mendekati nol) menyebabkan program  tidak  dapat  konvergen  ke  suatu  nilai  tertentu,  sedangkan  pengambilan  yang
1     -2    -2     2     0    -1    -1    -1    -2    -2     2     2     0    -1     0     0     1     1    -1    -1    -1     0     1     1     2    -2    -2     1     1    -2    -1     0     1     2     2    -1     1     2     0    -1     2    -2     2    -2     1
1 2 4 5 6 7 3
8 9 10

## Jusmawati Massalesse, Muh. Ali Imran
mendekati  nilai  1  mengakibatkan  kerusakan  kromosom,  ditandai  oleh  nilai  rata-rata  fungsi fitness yang tidak monoton naik.
3. Graf  planar  2-layer  maksimal  yang  dihasilkan  dengan  menggunakan  Algoritma  Genetika adalah  45-7=38  sisi.  Angka  45  adalah total jumlah  sisi  dari  graf  K 10, sedangkan  jumlah  sisi yang  dihilangkan  dari  graf  dinyatakan  oleh  banyaknya  gen  bernilai  0  pada  kromosom  yang mewakili solusi.

## Ucapan Terima Kasih
Penulis  mengucapkan  terima  kasih  kepada  Lembaga  Penelitian  Universitas  Hasanuddin  yang telah  memberikan  bantuan  dana  melalui  DIPA  Universitas  Hasanuddin  dengan  Surat  Perjanjian Pelaksanaan Penelitian Nomor: 3844/J04.2/PM.05/2006 tanggal 1 Mei 2006

## Daftar Pustaka
[1].  F.  Comellas,    1992,  “ Using  Genetic  Algorithms  for  Planarization  Problem” ,  in  C. Brezinski    and  U.  Kulish  (Editors):  Computational  and  Applied  Mathematics,I,  Elsevier Science Publishers, 93-97.
[2].  Nora  Hartsfield  dan  Gerhard  Ringel,  1997,  “ Pearl  in  Graph  Theory A  comprehensive Introduction”, Revised and Augmented, Academic Press, London.
[3].  Jusmawati Massalesse, 2005,  “ Pemakaian Algoritma Genetika Pada Masalah Planarisasi Graf ”, Penelitian RUTIN pada Lembaga Penelitian Univ. Hasanuddin.
[4].  Robin J. Wilson dan John J. Watkins, 1990, “ Graphs An Introductory Approach”, John Wiley &     Sons Inc. Canada.