Prosiding

Seminar Nasional Teknik Elektro dan Informatika

SNTEI 2012

“Sinergi Teknik Elektro, Industri, dan Pemerintah untuk Pembangunan Nasional”

Seminar Nasional dalam Rangka 25th Anniversary Jurusan Teknik Elektro Politeknik Negeri Ujung Pandang

Makassar, 29 Maret 2012

Publikasi oleh : Jurusan Teknik Elektro Politeknik Negeri Ujung Pandang

ISBN 978-602-18168-0-6

Copyright © 2012 pada SNTEI 2012, Jurusan Teknik Elektro, Politeknik Negeri Ujung Pandang, Makassar

ISBN : 978-602-18168-0-6 Reproduksi atau penerjemahan sebagian atau keseluruhan dari makalah-makalah ini harus seizin dari Panitia SNTEI 2012 Politeknik Negeri Ujung Pandang. Segala tindakan/perbuatan tanpa seizin dari pemilik hak cipta adalah suatu pelanggaran hukum. Pengajuan ijin atau informasi lebih lanjut, harus dialamatkan ke Panita SNTEI 2012, Jurusan Teknik Elektro, Polteknik Negeri Ujung Pandang.

ii

KATA PENGANTAR

Pertama-tama kami ucapkan puji syukur kepada Tuhan Yang Maha Kuasa atas

selesainya penyusunan Publikasi Ilmiah atau Proceeding Jurnal Ilmiah, hasil persentasi

pada Seminar Teknik Elektro dan Informatika (SNTEI) 2012 yang diselenggarakan oleh

Jurusan Elektro Politeknik Negeri Ujung Pandang. Seminar Nasional ini dilaksanakan

pada hari Kamis Tanggal 29 Maret 2012 di Makassar Golden Hotel, Kota Makassar

dengan tema : Sinergi Teknik Elektro, Industri dan Pemerintah untuk Pembangunan

Nasional.

Jumlah jurnal yang ada pada proceeding sebanyak 32 judul dengan berbagai

kategori bidang Teknik Elektro dan Informatika, seperti teknik energi, telekomunikasi,

kontrol/elektronika dan informatika. Adapun penulisnya dari berbagai perguruan tinggi

di Indonesia.

Kami telah berupaya menyajikan publikasi ilmiah ini menjadi karya inovatif dari

para kaum intelektual bertujuan untuk menambah dan berbagi pengetahuan bagi kita

semua, terutama para akademisi di bidang teknik elektro dan informatika, namun kami

menyadari bahwa masih ada kekurangannya. Olehnya itu diharapkan saran atau

masukan dari para pembaca untuk lebih menyempurnakan terbitan berikutnya.

Demikian pengantar kami, dan kami ucapkan terima kasih kepada para pembaca

dan terima kasih pula kepada semua pihak yang telah membantu dalam penyusunan

prosiding ini. Akhir kata selamat berkarya untuk kemajauan bangsa dan negara.

Makassar, 5 April 2012

Wassalam,

Panitia Pelaksana

iii

SUSUNAN PANITIA SNTEI 2012

Pelindung :

o Dr. Syahrul Yasin Limpo, S.H, M.Si, M.H (Gubernur Sulawesi Selatan) o Ir. Ilham Arief Sirajuddin, MM (Walikota Makassar) o Ir. Bahder Johan (Direktur PT.Kima/Dewan Penyantun PNUP) o Dr.Pirman, M.Si. (Direktur Politeknik Neg. Ujung Pandang)

Komite Program :

o Dr. Ir. Adit Kurniawan, M.T. (ITB, Bandung) o Yudho Giri Sucahyo (UI, Jakarta) o Prof. Dr.Ir. Mochamad Ashari. M.Eng. (ITS, Surabaya) o Nisfu Asrul Sani (ITS, Surabaya) o Husni Tedja Sukmana (UIN Jakarta) o M.Rusdi Syamsuddin (Kist Korea) o Romi Satria Wahono (LIPI, Jakarta) o Prof. Dr. Ir. Salama Manjang, M.T. (Unhas, Makassar) o Dr.Ir. Rhiza S. Sadjad, MSEE. (Unha,s Makassar) o Dr.Ir.Zahir Zainuddin, M.Sc. (Unhas, Makassar) o Dr. Ir. Andani Ahmad, M.T. (Unhas, Makassar) o Dr.Ir. Elyas Palantei, ST.,M.Eng. (Unhas, Makassar) o Ridwan A.Kambau, ST, MKom (IUN, Makassar) o Dr. Armin Lawi, S.Si,M.Eng (STIMIK Kharisma) o Rahmat Syam (UNM, Makassar)

Pengarah :

o Ir. Muas, M.T (PD I PNUP) o Andi Gunawan, S.E.,M.Com.Ak (PD II PNUP) o Drs. Muslimin, M.Hum (PD III PNUP) o Dr. Jumadi Tanggo (PD IV PNUP)

Penanggung Jawab/Ketua Umum :

Ir. Hafsah Nirwana, M.T (Ketua Jurusan Teknik Elektro PNUP) Ketua Pelaksana : Ibrahim Abduh, S.ST.,MT. Wakil Ketua Pelaksana : Iin Karmila, S.ST.,M.T. Sekertaris : Rini Nur, S.T.,M.T. Bendahara : Dharma Aryani, S.T.,M.T Wakil Bendahara : Nuraeni Umar, ST.,MT.

iv

Seksi Perlengkapan & Akomodasi :

o Yedy George, S.ST.,M.T. o Andi Wawan Indrawan, SST, M.Eng o Sahbuddin, Abdul Kadir S.ST.,M.T. o Ahmad Subair, ST.

Seksi Pendanaan:

o Ir. Abdullah Bazergan,M.T ,. o Nurhayati , S.Si.,M.T. o Ir. Farchia Ulfiah, M.T. o Handoko, Amd. (Exelkomindo) o Amiruddin Assegaf, S.T. (PT. Semen Tonasa) o Dina Desriany, A.Md, ST

Humas,Publikasi & Dokumentasi:

o Ir. Stephy B. Walukow., MT. (Politeknik Negeri Menado) o Tri Hartono, S.ST., MT. (Politeknik Negeri Bandung) o Otniel A. Mone, S.ST.,M.T. (Politeknik Negeri Kupang) o Sarwo Pranoto, S.T., M.Eng. o Irawan S.ST., M.T. o Eddy Tungadi, S.T., M.T. o Syahrul Amin

Acara & Pendaftaran :

o Irawati Razak, S.T., M.T. o Muhammad Ilyas Syarif, S.ST., M.T. o Ruslan L, ST.,M.T. o Ir. Satriyani, M.T. o Airin Dewi Utami, S.T., M.T.

Seksi Komsumsi :

o Ir. Kifayah, M.T. o Sulhan Bone, S.ST.,M.T. o Arni Litha, S.T. M.T o Fitriaty Pangerang, ST .M.T. o Kurniawati Naim, S.T.,M.T. o Emmiati o Rahmi

Pembantu Umum :

o Lidemar Halide, S.T.,M.T o Muh. Syamsul Bahri, SE. o Ridwan Akib o Wahyullah o Rasdiana o Rosmala

v

o Hasnawati o Emmiyah o Tim Mahasiswa Elektro

Seksi Acara Pemakalah :

Sem Teknik Listrik : Hamdani, S.T. M.T. Muh. Ashar, S.T.

Sem. Tek. Telkom : Muh. Mimsyad, S.T., M.Eng Umar Katu, S.T., M.T Sem. Tek. Jaringan Komputer : Muh. Fajri Raharjo, S.T., M.T. Iin Karmila, S.ST., M.Eng Sem Teknik Kontrol/Elektronika : Sulaeman, S.T., M.T. Moh. Adnan, S.T., M.T Tim Penilai Karya Ilmiah

Bidang Teknik Tenaga Listrik dan Energi :

o Prof. Dr.Ir.Mochamad Ashari. M.Eng. o Prof. Dr. Ir. Salama Manjang, M.T. o Aksan, S.T.,M.T. o Hamdani, S.T.M.T. o Bahtiar, S.T.,M.T.

Bidang Teknik Telekomunikasi :

o Dr.Ir. Elyas Palantei, ST.,M.Eng. o Dr. Ir. Andani Ahmad, M.T. o Sulwan Dase, S.T., M.T. o Rusdi Wartapne, S.T.,MT

Bidang Teknik Kontrol/Elektronika/Robotika :

o Dr.Ir. Rhiza S. Sadjad, MSEE. o Ir. Daniel Kambuno.,M.T o Nur Aminah S.T.,M.T.

Bidang Komputer dan Jaringan/Informatika :

o Dr.Ir. Zahir Zainuddin, M.Sc. o Dr. Armin Lawi, S.Si,M.Eng o Dr. Irfan Syamsuddin, M.Com. o Drs. Kasim M.T.

vi

DAFTAR ISI

SESI I

TE01 Evaluasi Monitoring Sistem Tenaga Listrik dengan Menggunakan Scada Gateway dan Remote Terminal Unit (Studi Kasus Tragi Tello) , Nadjamuddin Harun {Jurusan Teknik Elektro, Fakultas Teknik, Universitas Hasanuddin}

1

TE02 Analisa Pengujian Penuaan yang Dipercepat dari Material Isolasi Tegangan Tinggi, Umar Hamid, Muhammad Ilyas Syarif {Teknik Elektro, Politeknik Negeri Ujung Pandang}

5

TE03 Optimisasi Biaya Pengoperasian Pembangkit Termal pada PT. PLN (Persero) Cabang Ternate, Umar, Subhan Petrana {Fakultas Teknik, Universitas Khairun}

10

TE04 Optimalisasi Pemakaian Beban Listrik untuk Instalasi Listrik Domestik, Aksan, Sulhan Bone {Program Studi Teknik Listrik, Politeknik Negeri Ujung Pandang}

15

TE05 Pembuatan Automatic Transfer Switch (ATS) Berbasis Programmable Logic Control (PLC) untuk Kapasitas Genset 75 kVA, Rusli, Richard Semuel Waremra {Laboratory of Electrical Engineering Faculty of Engineering, University of Musamus (UNMUS) Merauke }

21

TE06 Kajian Potensi Energi Listrik Mikrohidro dalam Menunjang Terwujudnya DME (Desa Mandiri Energi), Lanto Mohamad Kamil Amali {Teknik Elektro, Universitas Negeri Gorontalo}

28

TE07 Studi Aliran Beban Berbasis Jaringan Syaraf Buatan, Syafaruddin {Jurusan Teknik Elektro, Universitas Hasanuddin, Makassar}

34

TK01 Sistem Pemantau Gait Menggunakan Accelerometer dengan Metode Peak Detection, Sarwo Pranoto, Andi Wawan Indrawan {Program Studi Teknik Listrik, Politeknik Negeri Ujung Pandang}

38

SESI II

TT01 Pelacak Perahu Nelayan melalui Sinyal Handy Talkie, Irawati Razak, Farchia Ulfiah {Program Studi Teknik Telekomunikasi, Jurusan Teknik Elektro, Politeknik Negeri Ujung Pandang}

43

TT02 Sistem Komunikasi Broadband pada Pengguna Bergerak dengan Kecepatan Tinggi, Nurmayanti Zain, Syafruddin Syarif, {Fakultas Teknik, Universitas Hasanuddin}

51

TT03 Monitoring Suhu, Keasaman dan Salinitas Air pada Budidaya Udang Windu, Nuraeni Umar, Muh. Ahyar {Program Studi Teknik Telekomunikasi, Jurusan Teknik Elektro, Politeknik Negeri Ujung Pandang}

53

vii

TT04 Sistem Monitoring Posisi Kapal di Pesisir Pantai Berbasis Global Positioning System, Hafsah Nirwana, Ibrahim Abduh, {Teknik Elektro, Politeknik Negeri Ujung Pandang}

61

TT05 Restorasi Citra Menggunakan Tapis Wiener dengan Kontrol PSF dan NSR, Bulkis Kanata, {Laboratorium Telekomunikasi, Jurusan Elektro Fakultas Teknik, Universitas Mataram}

69

TT06 Pengukuran Redaman Serat Optik yang Dibengkokkan, Rusdi Wartapane, Nur Aminah, {Teknik Elektro, Poteknik Negeri Ujung Pandang}

74

TT07 Studi Skenario Frekuensi untuk Penerapan LTE di Indonesia, Syafruddin Syarif1), Airin Dewi Utami Thamrin2), Dina Desriany3) {Fakultas Teknik, Universitas Hasanuddin1); Teknik Elektro Politeknik Negeri Ujung Pandang2&3)}

82

TI01 Aplikasi Non Adjacent Form (NAF) pada Countermeasure Simple Power Analysis Attack Kriptografi Kurva Eliptik, Sahbuddin Abdul Kadir, {Teknik Elektro, Politeknik Negeri Ujung Pandang}

87

SESI III

TI02 Pemodelan Perilaku Hunter-Prey dengan Fuzzy Cognitive Maps Menggunakan Metode Crips dan Fuzzy Weight Analysis, Irawan, {Program Studi Teknik Komputer Jaringan, Jurusan Teknik Elektro Politeknik Negeri Ujung Pandang}

93

TI03 Model Infrastruktur Perangkat Lunak Sensor Cloud untuk Sistem Monitoring Lingkungan, Rahman1), Zahir Zainuddin2) {Lab Teknik Komputer dan Jaringan (TKJ) Jurusan Elektro Politeknik Negeri Ujung Pandang 1); Lab Sistem Berbasis Komputer Teknik Elektro Universitas Hasanuddin 2)}

101

TI04 Sistem Identifikasi Telapak Tangan Menggunakan Webcam dengan Algoritma Neuro Fuzzy, Hartanto {Kejuruan Listrik BLKI Makassar, Kementerian Tenaga Kerja dan Transmigrasi RI}

106

TI05 Sistem Rute Penerbangan Berbasis Internet Agent Service, Rini Nur1), Zahir Zainuddin2), Rhiza S. Sadjad3) {Teknik Komputer & Jaringan, Jurusan Elektro, Politeknik Negeri Ujung Pandang1); Jurusan Elektro, Fakultas Teknik Universitas Hasanuddin2&3)}

113

TI06 Implementasi Sistem Air Mancur CAD Berbasis GUI untuk Perancangan, Munawir 1), Zahir Zainudddin2) {Fakultas Teknik Komputer Universitas Cokroaminoto Palopo1); Laboratorium Sistem Berbasis Komputer Teknik Elektro; Fakultas Teknik, Universitas Hasanuddin2)}

122

TI07 Algoritma Genetika Hibrid pada Kasus Pencarian Jalur Terpendek, Eddy Tungadi1), Airin Dewi Utami2) {Program Studi Teknik Komputer dan Jaringan1); Program Studi Teknik Telekomunikasi 2), Jurusan Teknik Elektro Politeknik Negeri Ujung Pandang}

126

viii

TI08 Networked Autoreport System untuk Monitoring Packer Semen pada PT. Semen Tonasa, Asminar1, Zahir Zainudddin2 {Fakultas Teknik Elektro, Universitas Haluoleo (UNHALU)1, Lab Sistem Berbasis Komputer Teknik Elektro Universitas Hasanuddin2}

131

TI09 Sistem Monitoring dan Kontrol Lalu Lintas Perkotaan, Marson James Budiman1), Zahir Zainuddin2) {Laboratorium Teknik Informatika Jurusan Teknik Elektro, Program Studi Teknik Informatika, Politeknik Negeri Manado1); Jurusan Teknik Elektro Universitas Hasanuddin2)}

135

SESI IV

TK02 Rancang Bangun Kontroler Frekwensi Generator PLTMH, Daniel Kambuno {Politeknik Negeri Ujung Pandang}

139

TK03 Rancang Bangun Sistem Full Motor Protection dengan Bantuan PLC Siemens LOGO, Fatahula, Iksan Kamil {Jurusan Teknik Elektro, Politeknik Negeri Jakarta}

144

TK04 Pengukur Curah Hujan Berbasis Mikrokontroller, Zahir Zainuddin1), Satriady Siraj2), Hadijah Putra Djaya3 {Electronics and Devices Laboratory Laboratorium Electronika dan Divais1); Laboratory Assistant of Electronics and Devices Laboratory2); Asisten Laboratorium Elektronika dan Divais3)}

149

TT08 Metode Teknik Estimasi Lokasi Indoor Menggunakan Wireless Local Area Network, Arni Litha, Yappa Baru {Teknik Elektro, Politeknik Negeri Ujung Pandang}

152

TT09 Estimasi Kanal Indoor Powerline Communication Menggunakan Algoritma Iterative Matrix, Muh. Fajri Raharjo {Teknik Elektro, Politeknik Negeri Ujung Pandang}

157

TT10 Antena Base Station Near Vertical Incidence Skywave (NVIS) untuk Operasi Bazarnas Makassar, Abdullah Bazergan, Sulwan Dase {Teknik Telekomunikasi, Jurusan Teknik Elektro, Politeknik Negeri Ujung Pandang}

168

TI10 e-Xam, Instrumen Evaluasi Kegiatan Belajar-Mengajar Berbasis Komputer, Khaidir Mustafa {Teknik Komputer dan Jaringan Politeknik Negeri Ujung Pandang}

173

TK05 Pemodelan dan Simulasi Fuzzy Logic Direct Torque Control pada Pengaturan Kecepatan Motor Induksi, Andi Wawan Indrawan, Sarwo Pranoto {Teknik Listrik, Jurusan Teknik Elektro, Politeknik Negeri Ujung Pandang}

177

Prosiding Seminar Nasional Teknik Elektro & Informatika TI07 SNTEI 2012 PNUP, Makassar, 29 Maret 2012

ISBN: 978-602-18168-0-6 126

Algoritma Genetika Hibrid pada Kasus Pencarian Jalur Terpendek

Eddy Tungadi1) dan Airin Dewi Utami2)

Program Studi Teknik Komputer dan Jaringan1) Program Studi Teknik Telekomunikasi 2)

Jurusan Teknik Elektro Politeknik Negeri Ujung Pandang Email : e_tungadi@yahoo.com, airinthamrin@yahoo.com

Abstrak—Algoritma Genetika Hibrid pada kasus pencarian jalur terpendek. Penelitian ini bertujuan untuk memodifikasi (hibridisasi) algoritma genetika, membangun aplikasi dengan menggunakan sebuah kasus jalur terpendek. Adapun metode yang digunakan dalam penelitian ini, yaitu mengambil data jalur, merancang algoritma dan melakukan pengukuran jalur terpendek optimal beserta waktu komputasinya dengan menggunakan parameter jumlah anggota populasi, peluang persilangan, dan peluang mutasi. Hasil peneltian menunjukkan bahwa algoritma genetika hibrid dapat menghasilkan sebuah solusi jalur optimal dengan waktu komputasi yang kecil.

Kata kunci : Jalur Terpendek, Algoritma Genetika Hibrid

I. PENDAHULUAN

Sejak dibuat pertama kali oleh John Holland, Algoritma Genetika telah menyita perhatian dan menjadi objek penelitian di seluruh dunia. Karakter algoritma genetika yang tidak deterministik memungkinkan untuk melakukan modifikasi lebih lanjut pada algoritma genetika yang telah ada sebelumnya.

Sementara itu, kasus pencarian jalur terpendek menjadi salah satu persoalan yang juga menyita perhatian. Dalam dunia nyata, aplikasi-aplikasi yang mencari jalur terpendek telah diterapkan pada perencanaan pembangunan, perencanaan produksi, jalur pengisian uang pada ATM, jalur patroli polisi, jalur pesawat terbang dan sebagainya.

Persoalan pencarian jalur terpendek ini dideskripsikan sebagai persoalan untuk menentukan lintasan yang harus dilalui ketika mengunjungi beberapa titik hingga diperoleh jarak tempuh terpendek. Meskipun sepertinya mudah dipaparkan, akan tetapi sangat sulit untuk diselesaikan terutama untuk persoalan dengan jumlah titik yang besar. Hingga kini belum ada suatu metode eksak yang dapat menjamin

menghasilkan nilai optimal untuk masalah ini. Kalaupun ada maka metode itu akan memerlukan waktu komputasi yang cukup lama dalam mencari solusi jalur terpendek.

Algoritma genetika dapat memecahkan permasalahan waktu komputasi ini dengan menghasilkan solusi jalur terpendek yang optimal. Berdasarkan pemikiran tersebut, penulis mengangkat algoritma genetika dan kemudian melakukan modifikasi padanya agar dapat menyelesaikan masalah pencarian jalur terpendek ini.

Dengan diimplementasikannya algoritma ini kedalam sebuah simulasi, diharapkan dapat membantu pencarian jalur yang paling optimal. Penelitian ini akan memanfaatkan konsep-konsep matematika dan kaitannya dalam pengeksekusian suatu algoritma. Namun bukan hanya sebagai tulisan namun juga sebagai bukti konsep-konsep ini dapat dimanfaatkan dalam kehidupan sehari-hari.

II. LANDASAN TEORI

A. Graf dan Jaringan

Sebuah graf dapat disebut sebagai kumpulan titik yang disebut simpul (vertex) dan dihubungkan oleh garis yang disebut sisi (edge). Graf dapat digunakan sebagai cara yang sangat sederhana untuk memodelkan banyak jalur atau jaringan.

Dalam menggambarkan graf, simpul digambarkan dengan lingkaran kecil atau titik tebal dan sisi digambarkan dengan garis. Jika sisi (i,j) memiliki aliran dari simpul i menuju ke simpul j maka sisi tersebut merupakan sisi berarah dan dilambangkan dengan panah.

a.sisi tak berarah b.sisi berarah

c. sisi dua arah Gambar 2.1 Arah sisi pada graf

i j i j

i j

Prosiding Seminar Nasional Teknik Elektro & Informatika TI07 SNTEI 2012 PNUP, Makassar, 29 Maret 2012

ISBN: 978-602-18168-0-6 127

Beberapa definisi berhubungan dengan graf berarah:[7] - Dalam graf dengan garis hubung berarah,

derajat kedalam (in-degree) dari simpul v, dituliskan sebagai deg-(v), adalah banyaknya garis hubung dengan v sebagai simpul akhirnya. Derajat keluar (out-degree) dari v, dituliskan sebagai deg+ (v), adalah banyaknya garis hubung dengan v sebagai simpul awalnya.

- Sebuah graf berarah disebut terhubung kuat (strongly connected) jika ada sebuah a ke b dan dari b ke a untuk semua pasangan simpul a, b pada graf.

- Sebuah graf berarah disebut terhubung lemah (weakly connected) jika hanya ada jalur dari a ke b tetapi tidak dari b ke a, atau sebaliknya.

Graf dapat digunakan pada kasus pencarian jalur

terpendek, dimana suatu sisi menyatakan suatu ruas jalan, sedangkan simpul menyatakan simpul pertemuan beberapa ruas jalan seperti pertigaan atau perempatan. Selanjutnya didefinisikan suatu bobot pada masing-masing sisi yang memberikan panjang jalan yang dinyatakan oleh sisi tersebut.

Misalkan G = (V, E) adalah sebuah graf sederhana dengan |V| = n. Anggap simpul pada G disusun dengan urutan v1 , v2 …, vn Matriks kedekatan (Adjacency matrix) dari graf G, AG, yang berkaitan dengan simpul-simpul, adalah sebuah matriks boolean nxn dengan G elemen ke (i, j) berharga 1 jika vi dan vj bertetangga, dan selainnya itu berharga 0.

Dengan kata lain, untuk sebuah matriks kedekatan A = [aij], maka berlaku

1, jika {vi ,vj} adalah sebuah garis hubung G Aij = 0, jika bukan garis hubung G

Graf dapat digunakan pada kasus jalur

terpendek. Dimana suatu edge menyatakan suatu ruas jalan, sedangkan verteks menyatakan titik pertemuan beberapa ruas jalan seperti pertigaan atau perempatan. Jika suatu jalan diberlakukan dua arah, maka dinyatakan dalam dua edge dengan arah berlawanan. Selanjutnya didefinisikan suatu bobot pada masing-masing edge yang memberikan panjang jalan yang dinyatakan oleh edge tersebut. Selanjutnya kita ingin melakukan perjalanan, sedemikian sehingga setiap jalan dilalui sedikitnya sekali yang sekaligus meminimumkan jarak total yang dilalui. Dalam hal ini suatu jalan yang diberlakukan dua arah cukup dilalui sekali. (Deo, 1986)

B. Persoalan Jalur Terpendek

Persoalan jalur terpendek yaitu menemukan jalur terpendek antara dua atau beberapa simpul yang berhubungan. Persoalan mencari jalur terpendek di dalam graf merupakan salah satu persoalan optimasi. Persoalan ini biasanya direpresentasikan dalam bentuk graf. Graf yang digunakan dalam pencarian jalur terpendek adalah graf berbobot (weighted graph),

C. Algoritma Genetika

Algoritma genetika merupakan solusi yang baik, tapi tidak mungkin dibuktikan secara deterministik [Sivanandam, 2008]. Algoritma genetika mungkin tidak selalu mencapai hasil yang terbaik, tetapi bisa berharga dalam memecahkan masalah. Algoritma genetika yang baik secara dramatis bisa mengurangi waktu yang diharuskan dalam memecahkan masalah. Meski tidak menjamin selalu dapat memecahkan masalah, tetapi seringkali memecahkan masalah dengan cukup baik untuk kebanyakan masalah..

Proses yang akan dilakukan dalam Algoritma Genetika untuk menentukan jalur terpendek, yaitu: 1. Pembentukan populasi awal

Untuk merepresentasikan individu anggota populasi digunakan metode acak yang akan menggambarkan sebuah jalur dari titik awal hingga titik tujuan. 2. Proses reproduksi

Proses seleksi akan menentukan individu mana saja yang akan dipilih untuk dilakukan rekombinasi. Kemungkinan terpilihnya suatu individu bergantung dari peluang fit dari individu tersebut. Mula-mula nilai fit masing-masing individu dihitung. Masing-masing individu dalam suatu wadah seleksi akan menerima peluang fit yang tergantung pada nilai fit dirinya sendiri terhadap jumlah nilai fit dari semua individu dalam wadah seleksi tersebut. Metode ini disebut metode roda Roulet (Roulette Wheel).

Dari gambar 1 terlihat bahwa individu yang memiliki porsi yang besar akan memiliki peluang fit yang semakin besar pula, sehingga kemungkinan untuk terpilih sebagai parent pun semakin besar.

Prosiding Seminar Nasional Teknik Elektro & Informatika TI07 SNTEI 2012 PNUP, Makassar, 29 Maret 2012

ISBN: 978-602-18168-0-6 128

Gambar 1. Seleksi dengan roda Roulet

3. Proses Rekombinasi Setelah reproduksi dilakukan, maka proses

selanjutnya adalah melakukan rekombinasi individu melalui persilangan. Persilangan dilakukan dengan menyilangkan dua kromosom untuk membentuk kromosom baru yang harapannya lebih baik dari pada induknya. Tidak semua kromosom pada suatu populasi akan mengalami proses persilangan ini. Banyak kromosom yang mengalami proses persilangan didasarkan pada peluang crossover (pc) yang telah ditentukan terlebih dahulu. Kemudian penulis memanfaatkan metode PMX (Partial Mapped Crossover) untuk memunculkan variasi turunan yang lebih banyak.

A1 = 2 | 5 4 | 6 A2 = 1 2 | 7 5 4 | 3

Hasil dari persilangan menghasilkan dua string baru (‘) yang berarti string tersebut menjadi dua bagian dari generasi baru

A1’ = 2 7 5 4 3 A2’ = 2 7 5 4 6

Dan untuk memastikan bahwa individu hasil persilangan adalah jalur yang terpendek maka dilakukan perbaikan tur dengan melakukan pemangkasan

4. Proses Seleksi Setelah operasi genetika dilakukan, dilanjutkan

dengan proses seleksi. Individu yang akan diproses secara genetika pada generasi berikutnya berupa 80% individu terbaik dari generasi sebelumnya dan 20% individu baru. Dengan persentase ini akan diperoleh variasi individu yang memungkinkan terbentuknya individu terbaik.

5. Proses Mutasi Proses seleksi dan persilangan menghasilkan

string yang berbeda dari induknya. Tetapi kedua proses ini belum cukup menampilkan variasi string untuk dapat melihat ruang permasalahan secara keseluruhan. Masalah ini dapat diatasi melalui suatu operator lain yang dikenal sebagai operator mutasi. Frekuensi terjadinya mutasi ditentukan oleh sebuah nilai yang disebut peluang mutasi (pm). Peluang mutasi akan menentukan kromosom mana yang akan mengalami mutasi.

Proses mutasi dilakukan dengan mengambil sebuah titik mutasi secara acak sehingga terbentuk individu baru, seperti contoh berikut:

A = 1 2 4 5 | 6 A’ = 1 2 4 5 | 8 7

Proses pencarian akan berhenti jika tidak ada perubahan nilai fit dari individu terbaik atau berhenti pada generasi yang ditentukan sendiri.

III. METODOLOGI

Penelitian ini dilakukan melalui beberapa tahap, yang dapat dijabarkan sebagai berikut:

A. Studi Kepustakaan

Pada tahap ini dilakukan pengumpulan bahan pustaka dan hasil-hasil penelitian pada jurnal-jurnal terdahulu, khususnya pada algoritma genetika yang pernah dilakukan untuk masalah jalur terpendek. Informasi-informasi yang diperoleh kemudian dipelajari dan dirangkumkan sebagai referensi untuk membangun sistem ini.

B. Penyusunan Algoritma

Menentukan spesifikasi sistem yang akan digunakan dalam hal ini penyusunan algoritma genetika hibrid.

C. Pembuatan Program Aplikasi

Pada tahap ini akan dibuat dua buah program yaitu dengan menggunakan algoritma genetika hibrid. Program akan dibuat menggunakan perangkat lunak Delphi 7.0.

D. Eksperimen

Melakukan pengujian yang akan menguji efektifitas dan efisiensi dari metode yang diajukan masing-masing algoritma pada beberapa persoalan .Hasil yang diperoleh selanjutnya akan dibandingkan.

IV. PEMBAHASAN

A. Model Matematika Jalur Terpendek

Terdapat banyak aplikasi yang berkaitan dengan graf. Di dalam aplikasi tersebut, graf digunakan sebagai alat untuk merepresentasikan atau memodelkan persoalan. Berdasarkan graf yang

14.95% 6.33%

6.73%

11.70%

10.35%

12.82%8.55%

7.92%

11.96%

8.68% 1

2

3

4

5

6

7

8

Prosiding Seminar Nasional Teknik Elektro & Informatika TI07 SNTEI 2012 PNUP, Makassar, 29 Maret 2012

ISBN: 978-602-18168-0-6 129

dibentuk, barulah persoalan tersebut dapat diselesaikan.

Dengan menggunakan defenisi di atas, masalah lintasan terpendek dapat diformulasikan sebagai masalah yang meminimumkan fungsi objektif sbb: [1]

ij

DD

SSi

DD

ijSSj

ij IC

(4.1)

Diberikan sebuah graf terhubung dengan 10 titik

seperti pada gambar berikut.

Gambar 2. Graf Terhubung

Dilakukan prosedur algoritma genetika dengan

mengambil 10 sampel individu dari populasi. Dan digunakan peluang crossover 100% dan peluang mutasi 50%.

Setelah dilakukan 20 kali percobaan pencarian jalur terpendek dengan algoritma genetika hibrid diperoleh hasil seperti pada tabel 6.1.

Diperoleh sebuah individu terbaik dengan jalur paling optimal yaitu ”ss 04 05 09 dd” dengan jarak tempuh 31 m dan dengan persentase kesalahan sebesar 5%.

B. Analisa

Dari hasil percobaan dengan menggunakan tiga buah parameter yang sama, yaitu jumlah anggota populasi sebanyak 10 buah, peluang crossover (pc) sebesar 100% dan peluang mutasi (pm) 50%, maka dapat dilihat solusi jalur terpendek beserta waktu komputasinya.

Perhitungan jalur terpendek dengan Algoritma Genetika Hibrid dapat menghasilkan solusi konvergen dengan persentasi kesalahan yang cukup kecil.

Adanya modifikasi yaitu dengan memanfaatkan PMX pada proses kawin silang dan menggunakan seleksi 20-80 menyebabkan lebih beragamnya kromosom yang dihasilkan dari tiap generasi. Sementara konvergensi diperoleh dari keragaman individu yang dihasilkan.

Tabel 1. Tabel Hasil Percobaan

Perc Individu Terbaik

Nilai obj (meter)

Gen Akhir

Waktu Komputasi

(ms)

1 ss040509dd 31 18 2719

2 ss040509dd 31 23 3484

3 ss040509dd 31 13 1906

4 ss040509dd 31 10 1579

5 ss040509dd 31 16 2547

6 ss040509dd 31 18 2828

7 ss040509dd 31 12 1844

8 ss040509dd 31 11 1750

9 ss040509dd 31 10 1579

10 ss040509dd 31 12 1859

11 ss040509dd 31 10 1328

12 ss040509dd 31 12 2062

13 ss030608dd 32 10 1672

14 ss040509dd 31 16 2469

15 ss040509dd 31 10 1515

16 ss040509dd 31 13 2093

17 ss040509dd 31 10 1531

18 ss040509dd 31 12 1860

19 ss040509dd 31 19 2765

20 ss040509dd 31 15 2203

Rata-rata 13.5 154.05

V. KESIMPULAN DAN SARAN

A. Kesimpulan

1. Algoritma genetika dapat dimodifikasi untuk mendapatkan konvergensi solusi yang lebih baik dan waktu komputasi yang lebih kecil.

2. Algoritma genetika dapat menyelesaikan masalah jalur terpendek dengan waktu komputasi yang lebih kecil.

3. Parameter jumlah anggota populasi, peluang crossover, dan peluang mutasi yang dipilih harus disesuaikan dengan metode yang akan digunakan, misalnya ketika metode menitikberatkan pada proses persilangan, maka peluang crossover dibuat 100%.

B. Saran

1. Diperlukan pengembangan lebih lanjut dari Algoritma Genetika untuk perbaikan konvergensi solusi dan waktu komputasi karena masih banyak kemungkinan metode lain yang dapat diadopsi ke dalam algoritma ini.

0

0

0

0

0

0

d

Prosiding Seminar Nasional Teknik Elektro & Informatika TI07 SNTEI 2012 PNUP, Makassar, 29 Maret 2012

ISBN: 978-602-18168-0-6 130

2. Diharapkan adanya penelitian lebih lanjut yang dapat menghasilkan sebuah solusi optimal terbaik dengan waktu komputasi yang lebih kecil.

3. Diharapkan dapat dilakukan pembandingan secara komprehensif antara algoritma genetika standar dan algoritma genetika hibrid, agar arah perbaikan untuk algoritma ini lebih jelas terlihat.

DAFTAR PUSTAKA

[1] Ahn and Ramakrishna., GA For SP Routing Problem and The Sizing of populations, IEEE Transactions On Evolutionary Computation, vol.6,No 6, Desember 2002, 567-571

[2] Gen, Mitsuo, et. al., Network Models and Optimization: Multiobjective Genetic Algorithm Approach, Springer, London, 2008

[3] Goldberg, D.E., Genetic Algorithms in Search, Optimization & Machine Learning, New York: Addison-Wesley, 1989

[4] Kusumadewi, S., dan H., Purnomo, Penyelesaian Masalah Optimasi dengan Teknik-teknik Heuristik, Yogyakarta, Graha Ilmu, 2005

[5] Mutakhiroh, Iing, dkk., Pemanfaatan Metode Heuristik Dalam Pencarian Jalur Terpendek dengan Algoritma Semut dan Algoritma Genetika, Seminar Nasional Aplikasi Teknologi Informasi, hlm: 1 s/d 5, 2007

[6] Sivanandam, S.N., Deepa, S.N, Introduction to Genetic Algorithms, New York, Springer Berlin Heidelberg, 2008, 30-60

[7] Suksmono, Adrian B., Matematika Diskrit dan Aplikasinya - Diktat Kuliah EL-2009 Matematika Diskrit, Intitut Teknologi Bandung, 2006.

I

 

 

INDEKS PENULIS   

     

A N Abdullah Bazergan TT10 Nadjamuddin Harun TE01 Airin Dewi Utami TT07,TI07 Nuraeni Umar TT03 Aksan TE04 Nur Aminah TT06Andi Wawan Indrawan TK01,TK05 Nurmayanti Zain TT02 Arni Litha TT08 R Asminar TI08 Rahman TI03 B Rhiza S. Sadjad TI05 Bulkis Kanata TT05 Richard Semuel Waremra TE05 D Rini Nur TI05Daniel Kambuno TK02 Rusdi Wartapane TT06 Dina Desriany TT07 Rusli TE05 E S Eddy Tungadi TI07 Sahbuddin Abdul Kadir TI01 F Sarwo Pranoto TK01,TK05Farchia Ulfiah TT01 Satriady Siraj TK04 Fatahula TK03 Subhan Petrana TE03 H Sulhan Bone TE04 Hadijah Putra Djaya TK04 Sulwan Dase TT10 Hafsah Nirwana TT04 Syafaruddin TE07Hartanto TI04 Syafruddin Syarif TT02,TT07 I U Ibrahim Abduh TT04 Umar TE03 Iksan Kamil TK03 Umar Hamid TE02 Irawan TI02 Y Irawati Razak TT01 Yappa Baru TT08K Z Khaidir Mustafa TI10 Zahir Zainuddin TI03, TI05 L TI06, TI08 Lanto M. Kamil Amali TE05 TI09, TK04 M Marson James Budiman

TI09

Muh. Ahyar TT03 Muh. Fajri Raharjo TT09 Muhammad Ilyas Syarif

TE02

Munawir TI06

II

 

  

SUSUNAN ACARA SEMINAR NASIONAL TEKNIK ELEKTRO DAN INFORMATIKA (SNTEI) 2012

TEMA : Sinergi Teknik Elektro, Industri dan Pemerintahan untuk Pembangunan Nasional

Waktu/Jam Acara Keterangan 08.00 - 08.45 Registrasi Panitia 08.45 - 09.30 Pembukaan Oleh Protokol (MC) 1. Paduan Suara Mahasiswa Poltek Ujung Pandang 2. Kesenian Daerah (Tarian

Paddupa) Mahasiswa Teknik Elektro PNUP

3. Laporan Ketua Panitia Ibrahim Abduh, S.ST.,M.T. 4. Sambutan Ketua Jurusan Ir. Hafsah Nirwana, M.T. 5. Sambutan Direktur PNUP &

Pembukaan Acara SNTEI 2012 Dr. Pirman, M.Si.

6. Pembacaan Doa Drs. Muh. Tang. M.Ag. 09.30 - 09.45 Coffee Break I Panitia 09.45 - 12. 30 Seminar / Diskusi Panel Moderator : (A.Wawan

Indrawan, S.ST.,M.Eng.) 1. Akademisi (Ketua Forum Teknik

Elektro Se Indonesia) Prof. Dr.Ir. Mochamad Ashari, M.Eng

2. Industri / Pemerintahan (Sekertaris Utama BPPT)

Dr. Jumain Appe

3. Ka. Balitbangda Sul-Sel Ir. H. Idrus Hafid 4. Alumni / Pengusaha (Direktur

Utama Swatama Mega Teknik) Ir. Abdillah Natsir

12.30 - 14.00 Makan Siang dan Ishoma Panitia 14.00 - 16.00 Pemakalah Jurnal Panitia 1. Teknik Listrik (Kelompok 1) Moderator : Hamdani, S.T.M.T. 2. Teknik Telekomunikasi

(Kelompok 2) Moderator : Ir. Abdullah Bazergan, M.T.

3. Teknik Kontrol/Elektronika (Kelompok 3)

Moderator : Muh. Mimsyad, M.Eng.

4. Teknik Komputer Jaringan/IT (Kelompok 4)

Moderator : Iin Karmila Yusri, S.ST.,M.Eng

16.00 - 16.30 Penutupan Panitia

16.30 - 17.00 Coffe Break II dan Penyerahan Sertifikat

Panitia

 

Sponsored by

:

Supported by

ALUMNI D3 TKJ 2007