Pemaksimalan Papan Sirkuit Di Pandang Sebagai Masalah Planarisasi Graf 2-Layer Menggunakan Algoritma Genetika

Abstract

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₁₀ 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₁₀. 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₁₀ dikurangi 7 (45-7=38).