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.
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
ii
SUSUNAN PANITIA SNTEI 2012 Pelindung : Dr. Syahrul Yasin Limpo, S.H, M.Si, M.H (Gubernur Sulawesi Selatan) Ir. Ilham Arief Sirajuddin, MM (Walikota Makassar) Ir. Bahder Johan (Direktur PT.Kima/Dewan Penyantun PNUP) Dr.Pirman, M.Si. (Direktur Politeknik Neg. Ujung Pandang)
o o o o
Komite Program : o o o o o o o o o o o o o o o
Dr. Ir. Adit Kurniawan, M.T. (ITB, Bandung) Yudho Giri Sucahyo (UI, Jakarta) Prof. Dr.Ir. Mochamad Ashari. M.Eng. (ITS, Surabaya) Nisfu Asrul Sani (ITS, Surabaya) Husni Tedja Sukmana (UIN Jakarta) M.Rusdi Syamsuddin (Kist Korea) Romi Satria Wahono (LIPI, Jakarta) Prof. Dr. Ir. Salama Manjang, M.T. (Unhas, Makassar) Dr.Ir. Rhiza S. Sadjad, MSEE. (Unha,s Makassar) Dr.Ir.Zahir Zainuddin, M.Sc. (Unhas, Makassar) Dr. Ir. Andani Ahmad, M.T. (Unhas, Makassar) Dr.Ir. Elyas Palantei, ST.,M.Eng. (Unhas, Makassar) Ridwan A.Kambau, ST, MKom (IUN, Makassar) Dr. Armin Lawi, S.Si,M.Eng (STIMIK Kharisma) Rahmat Syam (UNM, Makassar)
Pengarah : o o o o
Ir. Muas, M.T (PD I PNUP) Andi Gunawan, S.E.,M.Com.Ak (PD II PNUP) Drs. Muslimin, M.Hum (PD III PNUP) 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.
iii
Seksi Perlengkapan & Akomodasi : o o o o
Yedy George, S.ST.,M.T. Andi Wawan Indrawan, SST, M.Eng Sahbuddin, Abdul Kadir S.ST.,M.T. Ahmad Subair, ST.
Seksi Pendanaan: o o o o o o
Ir. Abdullah Bazergan,M.T ,. Nurhayati , S.Si.,M.T. Ir. Farchia Ulfiah, M.T. Handoko, Amd. (Exelkomindo) Amiruddin Assegaf, S.T. (PT. Semen Tonasa) Dina Desriany, A.Md, ST
Humas,Publikasi & Dokumentasi: o o o o o o o
Ir. Stephy B. Walukow., MT. (Politeknik Negeri Menado) Tri Hartono, S.ST., MT. (Politeknik Negeri Bandung) Otniel A. Mone, S.ST.,M.T. (Politeknik Negeri Kupang) Sarwo Pranoto, S.T., M.Eng. Irawan S.ST., M.T. Eddy Tungadi, S.T., M.T. Syahrul Amin
Acara & Pendaftaran : o o o o o
Irawati Razak, S.T., M.T. Muhammad Ilyas Syarif, S.ST., M.T. Ruslan L, ST.,M.T. Ir. Satriyani, M.T. Airin Dewi Utami, S.T., M.T.
Seksi Komsumsi : o o o o o o o
Ir. Kifayah, M.T. Sulhan Bone, S.ST.,M.T. Arni Litha, S.T. M.T Fitriaty Pangerang, ST .M.T. Kurniawati Naim, S.T.,M.T. Emmiati Rahmi
Pembantu Umum : o Lidemar Halide, S.T.,M.T o Muh. Syamsul Bahri, SE. o Ridwan Akib o Wahyullah o Rasdiana o Rosmala
iv
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 o o o o
Prof. Dr.Ir.Mochamad Ashari. M.Eng. Prof. Dr. Ir. Salama Manjang, M.T. Aksan, S.T.,M.T. Hamdani, S.T.M.T. Bahtiar, S.T.,M.T.
Bidang Teknik Telekomunikasi : o o o o
Dr.Ir. Elyas Palantei, ST.,M.Eng. Dr. Ir. Andani Ahmad, M.T. Sulwan Dase, S.T., M.T. 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 o o o
Dr.Ir. Zahir Zainuddin, M.Sc. Dr. Armin Lawi, S.Si,M.Eng Dr. Irfan Syamsuddin, M.Com. Drs. Kasim M.T.
v
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
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
SESI II
vi
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
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
SESI III
vii
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
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
SESI IV
viii
Prosiding Seminar Nasional Teknik Elektro & Informatika SNTEI 2012 PNUP, Makassar, 29 Maret 2012
TI07
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 :
[email protected],
[email protected] 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
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 seharihari.
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 ISBN: 978-602-18168-0-6
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. i
i
j
a.sisi tak berarah
j
b.sisi berarah i
j
c. sisi dua arah Gambar 2.1 Arah sisi pada graf
126
Prosiding Seminar Nasional Teknik Elektro & Informatika SNTEI 2012 PNUP, Makassar, 29 Maret 2012
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)
ISBN: 978-602-18168-0-6
TI07
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.
127
Prosiding Seminar Nasional Teknik Elektro & Informatika SNTEI 2012 PNUP, Makassar, 29 Maret 2012
TI07
5.
1
8.68%
2 14.95%
6.33%
11.96% 7.92%
6.73% 11.70%
8.55%
3 4 5 6
12.82%
7 10.35%
8
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 A 1’ = 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.
ISBN: 978-602-18168-0-6
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=1245|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 jurnaljurnal 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
128
Prosiding Seminar Nasional Teknik Elektro & Informatika SNTEI 2012 PNUP, Makassar, 29 Maret 2012
TI07
Tabel 1. Tabel Hasil Percobaan
dibentuk, barulah persoalan tersebut dapat diselesaikan. Dengan menggunakan defenisi di atas, masalah lintasan terpendek dapat diformulasikan sebagai masalah yang meminimumkan fungsi objektif sbb: [1] DD DD
C
i SS j SS j i
ij
I ij
(4.1)
Diberikan sebuah graf terhubung dengan 10 titik seperti pada gambar berikut. 0
0
0
0
d
0 0 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.
ISBN: 978-602-18168-0-6
Waktu Nilai obj Gen Komputasi (meter) Akhir (ms)
Perc
Individu Terbaik
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
13.5
154.05
Rata-rata
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%. 1.
B. Saran 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.
129
Prosiding Seminar Nasional Teknik Elektro & Informatika SNTEI 2012 PNUP, Makassar, 29 Maret 2012
2.
3.
TI07
Diharapkan adanya penelitian lebih lanjut yang dapat menghasilkan sebuah solusi optimal terbaik dengan waktu komputasi yang lebih kecil. 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]
[2]
[3]
[4]
[5]
[6]
[7]
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 Gen, Mitsuo, et. al., Network Models and Optimization: Multiobjective Genetic Algorithm Approach, Springer, London, 2008 Goldberg, D.E., Genetic Algorithms in Search, Optimization & Machine Learning, New York: AddisonWesley, 1989 Kusumadewi, S., dan H., Purnomo, Penyelesaian Masalah Optimasi dengan Teknik-teknik Heuristik, Yogyakarta, Graha Ilmu, 2005 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 Sivanandam, S.N., Deepa, S.N, Introduction to Genetic Algorithms, New York, Springer Berlin Heidelberg, 2008, 30-60 Suksmono, Adrian B., Matematika Diskrit dan Aplikasinya - Diktat Kuliah EL-2009 Matematika Diskrit, Intitut Teknologi Bandung, 2006.
ISBN: 978-602-18168-0-6
130
INDEKS PENULIS A Abdullah Bazergan Airin Dewi Utami Aksan Andi Wawan Indrawan Arni Litha Asminar B Bulkis Kanata D Daniel Kambuno Dina Desriany E Eddy Tungadi F Farchia Ulfiah Fatahula H Hadijah Putra Djaya Hafsah Nirwana Hartanto I Ibrahim Abduh Iksan Kamil Irawan Irawati Razak K Khaidir Mustafa L Lanto M. Kamil Amali M Marson James Budiman Muh. Ahyar Muh. Fajri Raharjo Muhammad Ilyas Syarif Munawir
TT10 TT07,TI07 TE04 TK01,TK05 TT08 TI08 TT05 TK02 TT07 TI07 TT01 TK03 TK04 TT04 TI04 TT04 TK03 TI02 TT01 TI10 TE05
N Nadjamuddin Harun Nuraeni Umar Nur Aminah Nurmayanti Zain R Rahman Rhiza S. Sadjad Richard Semuel Waremra Rini Nur Rusdi Wartapane Rusli S Sahbuddin Abdul Kadir Sarwo Pranoto Satriady Siraj Subhan Petrana Sulhan Bone Sulwan Dase Syafaruddin Syafruddin Syarif U Umar Umar Hamid Y Yappa Baru Z Zahir Zainuddin
TE01 TT03 TT06 TT02 TI03 TI05 TE05 TI05 TT06 TE05 TI01 TK01,TK05 TK04 TE03 TE04 TT10 TE07 TT02,TT07 TE03 TE02 TT08 TI03, TI05 TI06, TI08 TI09, TK04
TI09 TT03 TT09 TE02 TI06
I
SUSUNAN ACARA SEMINAR NASIONAL TEKNIK ELEKTRO DAN INFORMATIKA (SNTEI) 2012 TEMA : Sinergi Teknik Elektro, Industri dan Pemerintahan
untuk Pembangunan Nasional
Waktu/Jam 08.00 - 08.45 08.45 - 09.30
09.30 - 09.45 09.45 - 12. 30
12.30 - 14.00 14.00 - 16.00
16.00 - 16.30 16.30 - 17.00
Acara Registrasi Pembukaan 1. Paduan Suara 2. Kesenian Daerah (Tarian Paddupa) 3. Laporan Ketua Panitia 4. Sambutan Ketua Jurusan 5. Sambutan Direktur PNUP & Pembukaan Acara SNTEI 2012 6. Pembacaan Doa Coffee Break I Seminar / Diskusi Panel 1. Akademisi (Ketua Forum Teknik Elektro Se Indonesia) 2. Industri / Pemerintahan (Sekertaris Utama BPPT) 3. Ka. Balitbangda Sul-Sel 4. Alumni / Pengusaha (Direktur Utama Swatama Mega Teknik) Makan Siang dan Ishoma Pemakalah Jurnal 1. Teknik Listrik (Kelompok 1) 2. Teknik Telekomunikasi (Kelompok 2) 3. Teknik Kontrol/Elektronika (Kelompok 3) 4. Teknik Komputer Jaringan/IT (Kelompok 4) Penutupan Coffe Break II dan Penyerahan Sertifikat
Keterangan Panitia Oleh Protokol (MC) Mahasiswa Poltek Ujung Pandang Mahasiswa Teknik Elektro PNUP Ibrahim Abduh, S.ST.,M.T. Ir. Hafsah Nirwana, M.T. Dr. Pirman, M.Si. Drs. Muh. Tang. M.Ag. Panitia Moderator : (A.Wawan Indrawan, S.ST.,M.Eng.) Prof. Dr.Ir. Mochamad Ashari, M.Eng Dr. Jumain Appe Ir. H. Idrus Hafid Ir. Abdillah Natsir Panitia Panitia Moderator : Hamdani, S.T.M.T. Moderator : Ir. Abdullah Bazergan, M.T. Moderator : Muh. Mimsyad, M.Eng. Moderator : Iin Karmila Yusri, S.ST.,M.Eng Panitia Panitia
II
Sponsored by :
Supported by ALUMNI D3 TKJ 2007
