metode semut
PEMANFAATAN METODE HEURISTIK DALAM PENCARIAN JALUR
TERPENDEK DENGAN ALGORITMA SEMUT DAN ALGORITMA GENETIKA
ABSTRAKSI
Tanpa program komputer hanyalah menjadi sebuah kotak yang tak berguna. Secara umum, pencarian
jalur terpendek dapat dibagi menjadi dua metode yaitu metode konvensional dan heuristik. Pemanfaatan metode
heuristik yang diharapkan dapat menyelesaikan masalah pencarian jalur terpendek dengan hasil yang lebih
variatif dan dengan waktu perhitungan yang lebih singkat.
Pada metode konvensional logika yang dipakai hanya dengan membandingkan jarak masing-masing
node dan kemudian mencari jarak yang terpendek. Namun, kelemahan metode konvesional pada keakuratan
hasil yang didapatkan serta tingkat kesalahan yang dihasilkan pada perhitungan. Hal tersebut tidak akan
menjadi masalah jika data yang dibutuhkan hanya sedikit, sebaliknya maka akan menyebabkan peningkatan
tingkat kesalahan perhitungan dan penurunan keakuratan.
Pemanfaatan teknologi informasi pada pencarian jalur terpendek menghasilkan suatu hasil atau
keluaran yang akurat dan tepat, untuk pilihan perjalanan seseorang dengan mempertimbangkan beberapa
parameter yang lain. Untuk kasus yang berbeda algoritma akan memberikan hasil yang berbeda, tidak dapat
dipastikan bahwa algoritma semut atau genetik yang terbaik. Secara konsep algoritma, metode konvesional
lebih mudah untuk dipahami tetapi, hasil yang diperoleh dari metode heuristik lebih variatif. Dengan metode
heuristik, waktu perhitungan yang diperlukan lebih cepat 30% dibandingkan dengan menggunakan metode
konvensional.
Kata kunci: Pencarian jalur terpendek, Heuristik, Algoritma Semut, Algoritma Genetika
1. PENDAHULUAN
Untuk menggunakan atau memfungsikan
sebuah komputer maka harus terdapat program yang
terdistribusi di dalamnya, tanpa program komputer
hanyalah menjadi sebuah kotak yang tak berguna.
Program yang terdapat pada komputer sangat
bervariasi dan setiap program pasti menggunakan
algoritma. Algoritma merupakan kumpulan perintah
untuk menyelesaikan suatu masalah. Perintahperintahnya dapat diterjemahkan secara bertahap
dari awal hingga akhir. Masalah tersebut dapat
berupa apapun dengan catatan untuk setiap masalah
memiliki kriteria kondisi awal yang harus dipenuhi
sebelum menjalankan algoritma.
Dalam kehidupan, sering dilakukan
perjalanan dari satu tempat atau kota ke tempat yang
lain dengan mempertimbangkan efisiensi, waktu dan
biaya sehingga diperlukan ketepatan dalam
menentukan jalur terpendek antar suatu kota. Hasil
penentuan jalur terpendek akan menjadi
pertimbangan dalam pengambilan keputusan untuk
menununjukkan jalur yang akan ditempuh dan yang
didapatkan juga membutuhkan kecepatan dan
keakuratan dengan bantuan komputer.
Secara umum, pencarian jalur terpendek
dapat dibagi menjadi dua metode, yaitu metode
konvensional dan metode heuristik. Metode
konvensional cenderung lebih mudah dipahami
daripada metode heuristik, tetapi jika dibandingkan,
hasil yang diperoleh dari metode heuristik lebih
variatif dan waktu perhitungan yang diperlukan
lebih singkat.
a. Rumusan Masalah
Seringkali penyelesaian masalah jalur
terpendek masih menggunakan metode konvensional
bahkan menggunakan perhitungan manual.
Pemanfaatan metode heuristik masih sangat jarang
digunakan, Sehingga dapat dirumuskan sebuah
masalah yaitu dengan pemanfaatan metode heuristik
yang diharapkan nantinya dapat menyelesaikan
masalah pencarian jalur terpendek dengan hasil yang
lebih variatif dan dengan waktu perhitungan yang
lebih singkat.
b. Batasan Masalah
Dari latar belakang dan rumusan masalah
yang telah dijelaskan, penelitian dibatasi pada dua
jenis algoritma yang digunakan dalam metode
heuristik, yaitu algoritma genetika (Genetic
Algorithm, GA) dan algoritma semut (Ant Colony
Algorithm, Antco).
c. Tujuan Penelitian
Penelitian bertujuan menyelesaikan masalah
rute menggunakan metode heuristik, khususnya
algoritma genetika dan algoritma semut, mencoba
mengimplementasikan dengan sebuah kasus
sederhana, dan mempelajari lebih dalam tentang
cabang dari ilmu kecerdasan buatan.
d. Manfaat Penelitian
Manfaat yang dapat diambil dari penelitian
adalah:
1. Menawarkan penyelesaian yang lebih mudah
dalam perhitungan (sesuai dengan tujuan
algoritma heuristik) untuk pencarian jalur
terpendek
2. Dapat diaplikasikan menjadi sebuah perangkat
lunak
2. LANDASAN TEORI
a. Pencarian jalur terpendek
Secara umum penyelesaian masalah
pencarian jalur terpendek dapat dilakukan
menggunakan dengan dua buah metode, yaitu
metode algoritma konvensional dan metode
heuristik. Metode algoritma konvensional diterapkan
dengan cara perhitungan matematis seperti biasa,
sedangkan metode heuristik diterapkan dengan
perhitungan kecerdasan buatan, dengan menentukan
basis pengetahuan dan perhitungannya.
a. Metode konvensional
Metode konvensional berupa algoritma yang
menggunakan perhitungan matematis biasa. Ada
beberapa metode konvensional yang biasa
digunakan untuk melakukan pencarian jalur
terpendek, diantaranya algoritma Djikstraa,
algoritma Floyd-Warshall, dan algoritma
Bellman-Ford
b. Metode heuristik
Adalah sub bidang dari kecerdasan buatan yang
digunakan untuk melakukan pencarian dan
penentuan jalur terpendek. Ada beberapa
algoritma pada metode heuristik yang biasa
digunakan dalam pencarian jalur terpendek.
Namun dalam penelitian dibatasi hanya
membahas dua macam algoritma yaitu algoritma
semut dan algoritma genetika.
b. Algoritma semut
Algoritma Semut diadopsi dari perilaku
koloni semut yang dikenal sebagai sistem semut
(Dorigo, 1996). Secara alamiah koloni semut
mampu menemukan rute terpendek dalam perjalanan
dari sarang ke tempat-tempat sumber makanan.
L R L R
(a) (b)
L R L R
(c) (d)
Gambar 1. Perjalanan semut menemukan sumber
makanan.
Koloni semut dapat menemukan rute
terpendek antara sarang dan sumber makanan
berdasarkan jejak kaki pada lintasan yang telah
dilalui. Semakin banyak semut yang melalui suatu
lintasan, maka semakin jelas bekas jejak kakinya.
Hal ini menyebabkan lintasan yang dilalui semut
dalam jumlah sedikit, semakin lama semakin
berkurang kepadatan semut yang melewatinya, atau
bahkan akan tidak dilewati sama sekali. Sebaliknya
lintasan yang dilalui semut dalam jumlah banyak,
semakin lama akan semakin bertambah kepadatan
semut yang melewatinya, atau bahkan semua semut
melalui lintasan tersebut.
Gambar 1.a menujukkan perjalanan semut
dalam menemukan jalur terpendek dari sarang ke
sumber makanan, terdapat dua kelompok semut
yang melakukan perjalanan. Kelompok semut L
berangkat dari arah kiri ke kanan dan kelompok
semut R berangkat dari kanan ke kiri. Kedua
kelompok berangkat dari titik yang sama dan dalam
posisi pengambilan keputusan jalan sebelah mana
yang akan diambil. Kelompok L membagi dua
kelompok lagi. Sebagian melalui jalan atas dan
sebagian melalui jalan bawah. Hal ini juga berlaku
pada kelompok R. Gambar 1.b dan Gambar 1.c
menunjukkan bahwa kelompok semut berjalan pada
kecepatan yang sama dengan meninggalkan feromon
atau jejak kaki di jalan yang telah dilalui. Feromon
yang ditinggalkan oleh kumpulan semut yang
melalui jalan atas telah mengalami banyak
penguapan karena semut yang melalui jalan atas
berjumlah lebih sedikit dari pada jalan yang di
bawah. Hal ini disebabkan jarak yang ditempuh
lebih panjang daripada jalan bawah. Sedangkan
feromon yang berada di jalan bawah penguapannya
cenderung lebih lama. Karena semut yang melalui
jalan bawah lebih banyak daripada semut yang
melalui jalan atas. Gambar 1.d menunjukkan bahwa
semut-semut yang lain pada akhirnya memutuskan
untuk melewati jalan bawah karena feromon yang
ditinggalkan masih banyak. Sedangkan feromon
pada jalan atas sudah banyak menguap sehingga
semut-semut tidak memilih jalan atas tersebut.
Semakin banyak semut yang melalui jalan maka
semakin banyak semut yang mengikutinya, semakin
sedikit semut yang melalui jalan, maka feromon
yang ditinggalkan semakin berkurang bahkan hilang.
Dari sinilah kemudian terpilihlah jalur terpendek
antara sarang dan sumber makanan.
Dalam algoritma semut, diperlukan beberapa
variabel dan langkah-langkah untuk menentukan
jalur terpendek, yaitu:
Langkah 1:
a. Inisialisasi harga parameter-parameter
algoritma.
Parameter-parameter yang di inisialisasikan
adalah:
1. Intensitas jejak semut antar kota dan
perubahannya (τij
) Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-35
2. Banyak kota (n) termasuk x dan y
(koordinat) atau dij (jarak antar kota)
3. Tetapan siklus-semut (Q)
4. Tetapan pengendali intensitas jejak semut
(α)
5. Tetapan pengendali visibilitas (β)
6. Visibilitas antar kota = 1/dij (ηij)
7. Banyak semut (m)
8. Tetapan penguapan jejak semut (ρ)
9. Jumlah siklus maksimum (NCmax) bersifat
tetap selama algoritma dijalankan,
sedangkan τij akan selalu diperbaharui
harganya pada setiap siklus algoritma mulai
dari siklus pertama (NC=1) sampai tercapai
jumlah siklus maksimum (NC=NCmax)
atau sampai terjadi konvergensi.
b. Inisialisasi kota pertama setiap semut.
Setelah inisialisasi τij
dilakukan, kemudian m
semut ditempatkan pada kota pertama tertentu
secara acak.
Langkah 2:
Pengisian kota pertama ke dalam tabu list.
Hasil inisialisasi kota pertama setiap semut dalam
langkah 1 harus diisikan sebagai elemen pertama
tabu list. Hasil dari langkah ini adalah terisinya
elemen pertama tabu list setiap semut dengan indeks
kota tertentu, yang berarti bahwa setiap tabuk
(1) bisa
berisi indeks kota antara 1 sampai n sebagaimana
hasil inisialisasi pada langkah 1.
Langkah 3:
Penyusunan rute kunjungan setiap semut ke
setiap kota. Koloni semut yang sudah terdistribusi ke
sejumlah atau setiap kota, akan mulai melakukan
perjalanan dari kota pertama masing-masing sebagai
kota asal dan salah satu kota-kota lainnya sebagai
kota tujuan. Kemudian dari kota kedua masingmasing, koloni semut akan melanjutkan perjalanan
dengan memilih salah satu dari kota-kota yang tidak
terdapat pada tabuk
sebagai kota tujuan selanjutnya.
Perjalanan koloni semut berlangsung terus menerus
sampai semua kota satu persatu dikunjungi atau
telah menempati tabuk
. Jika s menyatakan indeks
urutan kunjungan, kota asal dinyatakan sebagai
tabuk
(s) dan kota-kota lainnya dinyatakan sebagai
{N-tabuk}, maka untuk menentukan kota tujuan
digunakan persamaan probabilitas kota untuk
dikunjungi sebagai berikut:
[ ] [ ]
∑[ ] [ ]
∈ −
α β
α β
τ ⋅ η
τ ⋅ η
=
k' {N tabu }
ik' ik'
k ij ij
ij
k
p untuk j∈{N-tabuk}
dan p 0
k
ij
= , untuk j lainnya
dengan i sebagai indeks kota asal dan j sebagai
indeks kota tujuan.
Langkah 4:
a. Perhitungan panjang rute setiap semut.
Perhitungan panjang rute tertutup (length closed
tour) atau Lk setiap semut dilakukan setelah satu
siklus diselesaikan oleh semua semut.
Perhitungan dilakukan berdasarkan tabuk
masing-masing dengan persamaan berikut:
∑
−
=
= + +
n 1
s 1
k tabu (n),tabu (1) tabu (s),tabu (s 1) k k k k
L d d
dengan dij
adalah jarak antara kota i ke kota j
yang dihitung berdasarkan persamaan:
2 2
( ) ( )
ij i j i j
d = x − x + y − y
b. Pencarian rute terpendek.
Setelah Lk setiap semut dihitung, akan didapat
harga minimal panjang rute tertutup setiap
siklus atau LminNC dan harga minimal panjang
rute tertutup secara keseluruhan adalah atau
Lmin.
c. Perhitungan perubahan harga intensitas jejak
kaki semut antar kota.
Koloni semut akan meninggalkan jejak-jejak
kaki pada lintasan antar kota yang dilaluinya.
Adanya penguapan dan perbedaan jumlah semut
yang lewat, menyebabkan kemungkinan
terjadinya perubahan harga intensitas jejak kaki
semut antar kota. Persamaan perubahan ini
adalah:
∑
=
∆τ = ∆τ
m
k 1
k
ij ij
dengan
k
ij
∆τ adalah perubahan harga intensitas
jejak kaki semut antar kota setiap semut yang
dihitung berdasarkan persamaan
k
k
ij
L
Q
∆τ = ,
untuk (i,j) ∈ kota asal dan kota tujuan dalam
tabuk
0
k
∆τ
ij
= , untuk (i,j) lainnya
Langkah 5:
a. Perhitungan harga intensitas jejak kaki semut
antar kota untuk siklus selanjutnya.
Harga intensitas jejak kaki semut antar kota pada
semua lintasan antar kota ada kemungkinan
berubah karena adanya penguapan dan
perbedaan jumlah semut yang melewati. Untuk
siklus selanjutnya, semut yang akan melewati
lintasan tersebut harga intensitasnya telah
berubah. Harga intensitas jejak kaki semut antar
kota untuk siklus selanjutnya dihitung dengan
persamaan:
ij ij ij
τ = ρ ⋅ τ + ∆τ
b. Atur ulang harga perubahan intensitas jejak kaki
semut antar kota. Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-36
Untuk siklus selanjutnya perubahan harga
intensitas jejak semut antar kota perlu diatur
kembali agar memiliki nilai sama dengan nol.
Langkah 6:
Pengosongan tabu list, dan ulangi langkah 2 jika
diperlukan. Tabu list perlu dikosongkan untuk
diisi lagi dengan urutan kota yang baru pada
siklus selanjutnya, jika jumlah siklus maksimum
belum tercapai atau belum terjadi konvergensi.
Algoritma diulang lagi dari langkah 2 dengan
harga parameter intensitas jejak kaki semut antar
kota yang sudah diperbaharui.
c. Algoritma genetika
Algoritma genetika adalah algoritma
pencarian yang didasarkan atas mekanisme seleksi
alami dan evolusi biologis. Algoritma genetika
mengkombinasikan antara deretan struktur dengan
pertukaran informasi acak ke bentuk algoritma
pencarian dengan beberapa perubahan bakat pada
manusia. Pada setiap generasi, himpunan baru dari
deretan individu dibuat berdasarkan kecocokan
pada generasi sebelumnya (Goldberg,1989).
Dalam algoritma genetika, diperlukan
beberapa proses untuk menentukan jalur terpendek,
yaitu:
a. Proses Pengkodean (Encoding)
Adalah salah suatu proses yang sulit dalam
algoritma genetika. Hal ini disebabkan Karena
proses pengkodean untuk setiap permasalahan
berbeda-beda karena tidak semua teknik pengkodean
cocok untuk setiap permasalahan. Proses
pengkodean ini menghasilkan suatu deretan yang
kemudian disebut kromosom. Kromosom terdiri dari
sekumpulan bit yang dikenal sebagai gen.
Ada beberapa macam teknik pengkodean
yang dapat dilakukan dalam algoritma genetika
(Lukas, 2005), diantaranya pengkodean biner
(binary encoding), pengkodean permutasi
(permutation encoding), pengkodean nilai (value
encoding) dan pengkodean pohon (tree encoding).
b. Proses Seleksi
Adalah proses untuk menentukan individu
mana saja yang akan dipilih untuk dilakukan
rekombinasi dan bagaimana keturunan terbentuk
dari individu-individu terpilih tersebut. Langkah
pertama yang dilakukan dalam seleksi adalah
pencarian nilai fitness. Masing-masing individu
dalam suatu wadah seleksi akan menerima
probabilitas reproduksi yang tergantung pada nilai
obyektif dirinya sendiri terhadap nilai obyektif dari
semua individu dalam wadah seleksi tersebut. Nilai
fitness kemudian akan digunakan pada tahap seleksi
berikutnya.
Ada beberapa macam proses seleksi yang ada
pada algoritma genetika, diantaranya (Kusumadewi,
2005):
1. Seleksi dengan Roda Roulette (Roulette Wheel
Selection), dengan memetakan individu-individu
dalam suatu segmen garis secara berurutan
sedemikian hingga tiap-tiap segmen individu
memiliki ukuran yang sama dengan ukuran
fitness-nya.
2. Seleksi berdasarkan Ranking Fitness (Rankbased Fitness), yaitu dengan cara mengurutkan
populasi menurut nilai obyektifnya.
3. Seleksi Pengambilan Sampling Stocastic
(Stocastic Universal Sampling), dengan
memetakan individu-individu seperti halnya roda
roulette, kemudian memberikan sejumlah pointer
sebanyak individu yang ingin diseleksi pada
garis tersebut.
4. Seleksi Lokal (Local Selection), seleksi yang
dilakukan hanya pada konstrain tertentu.
5. Seleksi dengan Pemotongan (Truncation
Selection), seleksi buatan yang biasanya
digunakan oleh polulasi yang jumlahnya sangat
besar.
6. Seleksi dengan Turnamen (Tournament
Selection), menetapkan suatu nilai turnamen
untuk individu-individu yang dipilih secara acak
dari suatu populasi.
c. Proses Rekombinasi
Adalah proses untuk menyilangkan dua
kromosom sehingga membentuk kromosom baru
yang harapannya lebih baik dari pada induknya.
Rekombinasi dikenal juga dengan nama crossover.
Tidak semua kromosom pada suatu populasi akan
mengalami proses rekombinasi. Kemungkinan suatu
kromosom mengalami proses rekombinasi
didasarkan pada probabilitas crossover yang telah
ditentukan terlebih dahulu. Probabilitas crossover
menyatakan peluang suatu kromosom akan
mengalami crossover.
Ada beberapa macam proses rekombinasi
yang ada pada algoritma genetika, diantaranya
(Kusumadewi, 2005):
1. Rekombinasi diskret, dengan menukar nilai
variabel antar kromosom induk
2. Rekombinasi menengah, merupakan metode
rekombinasi yang hanya digunakan untuk
variabel real dan variabel yang bukan biner.
3. Rekombinasi garis, memiliki prinsip yang sama
dengan rekombinasi menengah, dengan nilai
alpha sama untuk semua variabel.
4. Penyilangan satu titik, dengan menukar variabelvariabel antar kromosom pada satu titik untuk
menghasilkan anak.
5. Penyilangan banyak titik, dengan menukar
variabel-variabel antar kromosom pada banyak
titik untuk menghasilkan anak.
6. Penyilangan seragam, dengan membuat sebuah
mask penyilangan sepanjang panjang kromosom
secara acak.
7. Penyilangan dengan permutasi, dengan cara
memilih sub-barisan suatu turnamen dari satu Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-37
induk dengan tetap menjaga urutan dan posisi
sejumlah kota yang mungkin terhadap induk
lainnya.
d. Proses Mutasi
Adalah proses penambahan nilai acak yang
sangat kecil dengan probabilitas rendah pada
variabel keturunan. Peluang mutasi didefinisikan
sebagai persentasi dari jumlah total gen pada
populasi yang mengalami mutasi. Peluang mutasi
mengendalikan banyaknya gen baru yang akan
dimunculkan untuk dievaluasi. Jika peluang mutasi
terlalu kecil, banyak gen yang mungkin berguna
tidak dievaluasi, tetapi bila peluang mutasi ini terlalu
besar maka akan terlalu banyak gangguan acak,
sehingga anak akan kehilangan kemiripan dari
induknya dan algoritma juga akan kehilangan
kemampuan untuk belajar dari history pencarian
(Kusumadewi, 2005). Ada beberapa macam proses
mutasi yang ada pada algritma genetika,
diantaranya:
1. Mutasi bilangan real, dengan mendefinisikan
ukuran langkah mutasi, kecil atau besar.
2. Mutasi biner, dengan mengganti satu atau
beberapa nilai gen dari kromosom.
Berikut adalah langkah algoritma genetika
sederhana untuk pencarian jalur terpendek:
Langkah 1
Inisialisasi generasi awal. Generasi awal harus
diinisialisasi kosong, sehingga belum ada generasi.
Generasi = 0.
Langkah 2
Inisialisasi populasi awal, P (generasi) secara acak.
Populasi yang ditentukan di inisialisasi secara acak.
Langkah 3
Evaluasi nilai fitness pada setiap individu dalam P
(generasi). Nilai fitness adalah nilai yang
menunjukkan kualitas suatu kromosom dalam
populasi.
Langkah 4
a. Menambahkan generasi baru dengan persamaan:
generasi = generasi+1
b. Seleksi populasi tersebut untuk mendapatkan
kandidat induk P’ (generasi)
c. Lakukan crossover pada P’ (generasi).
d. Lakukan mutasi pada P’ (generasi).
e. Lakukan evaluasi fitness setiap individu pada P’
(generasi).
f. Bentuk populasi baru, P (generasi) =
{P(generasi1) yang bertahan, P’ (generasi)}.
3. METODE PENELITIAN
Pada penelitian ini, terdapat beberapa metode
pengumpulan data yang digunakan, yaitu:
1. Metode kepustakaan
Metode pengumpulan data kepustakaan
dilakukan dengan mengumpulkan data-data dari
sumber atau buku yang relevan terhadap
penelitian.
2. Metode wawancara
Metode wawancara dilakukan dengan cara tatap
muka dan menanyakan langsung kepada objek
yang pernah melakukan penelitian sebelumnya.
4. PEMBAHASAN
4.1 Pencarian jalur terpendek
Gambar 2. Ilustrasi Jalur Terpendek dengan Jarak
Pada dasarnya permasalahan pencarian jalur
terpendek antar kota merupakan pencarian jalur
terpendek antar titik yang telah diketahui
koordinatnya. Dengan mengetahui konsep pencarian
jalur terpendek antar titik, untuk selanjutnya dapat
diterapkan pada pencarian jalur terpendek pada
berbagai kota yang ingin diketahui. Contoh kasus
yang akan diambil adalah pencarian jalur terpendek
antara titik A dan titik E.
Terdapat dua jenis kasus yang bisa
diturunkan dari gambar di atas. Kasus pertama
adalah mengetahui jarak antar node yang
ditunjukkan dengan garis penghubung antar titik..
Kasus yang kedua adalah dengan dengan
mengetahui koordinat titik saja. Gambar 2
merupakan jenis kasus yang pertama yaitu dengan
mengetahui jarak antar titik. Sedangkan gambar 3
merupakan jenis kasus yang kedua, yaitu dengan
mengetahui titik koordinatnya saja. Untuk kasus
pertama, penyelesaian cenderung lebih mudah
karena jarak antar titik telah diketahui sebagai
berikut:
Tabel 1. Tabel Jarak antar Titik
A B C D E
A 0 5 7 3 -
B 5 0 4 - -
C 7 4 0 - 5
D 3 - - 0 4
E - - 5 4 0
Sedangkan untuk kasus kedua yang telah
ditunjukkan pada Gambar 3.
Dari gambar 3 di atas, misalnya titik–titik
yang telah ditentukan mempunyai koordinat
sebagaimana tabel 2. Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-38
Gambar 3. Ilustrasi Jalur Terpendek tanpa Jarak
Tabel 2. Koordinat titik antar kota
Karena belum diketahui jarak antar titiknya
dan hanya diketahui titik koordinat saja, Maka
perhitungan dimulai dari penentuan jarak antar
simpul titik dengan dengan menggunakan titik yang
diketahui. Titik yang diketahui menggunakan
koordinat sumbu X dan Y. Langkah di atas
merupakan langkah yang harus dilakukan untuk
semua metode.
Penyelesaian kasus diatas dapat dilakukan
dengan dua metode seperti yang telah dijelaskan
pada bab II, yaitu metode konvensional dan metode
heuristik. Pada metode konvensional, logika yang
dipakai sangat sederhana. Yaitu hanya dengan
membandingkan jarak masing-masing node dan
kemudian mencari jarak yang terpendek. Namun,
kelemahan metode konvesional ini adalah pada
keakuratan hasil yang didapatkan serta tingkat
kesalahan yang dihasilkan pada perhitungan. Hal
tersebut tidak akan menjadi masalah jika data yang
dibutuhkan hanya sedikit, sebaliknya maka akan
menyebabkan peningkatan tingkat kesalahan
perhitungan dan penurunan keakuratan. Penelitian
ini akan membahas mengenai penyelesaian jalur
terpendek menggunakan metode heuristik dengan
algortima semut dan algoritma genetika.
4.2 Penyelesaian pencarian jalur terpendek
a. Algoritma semut
Berdasarkan contoh kasus yang ada, maka
langkah yang harus dilakukan adalah:
1. Menginisialisasi parameter-parameter yang
diperlukan, yaitu:
a. τij
(intensitas jejak semut antar kota) dan
perubahannya, parameter ini berfungsi
menentukan jumlah intensitas jejak semut
antar kota sehingga diketahui jalur terpendek
yang dihasilkan.
b. n (banyak kota) termasuk x dan y (koordinat)
atau dij
(jarak antar kota), pada contoh kasus
di atas, jumlah n = 5 dan mempunyai
koordinat atau jarak yang telah ditentukan.
c. Q (tetapan siklus-semut), α (tetapan
pengendali intensitas jejak semut), β (tetapan
pengendali visibilitas), ηij
(visibilitas antar
kota=1/dij
), dan ρ (tetapan penguapan jejak
semut), nilai dari parameter harus
didefinisikan dahulu karena bersifat sebagai
konstanta.
d. m (banyak semut), jumlah semut yang akan
digunakan untuk menyelusuri jalur bisa
bernilai sembarang tergantung oleh
pengguna. Contoh kasus diatas menggunakan
100 semut.
e. NCmax(jumlah siklus maksimum), adalah
jumlah maksimum siklus yang ingin di
jalankan, hingga menemukan hasil yang
terbaik. Misal maksimum siklus 10 kali,
maka perhitungan akan dilakukan maksimal
10 kali hingga menemukan hasil yang
terpendek.
2. Menempatkan kelompok semut tersebut pada
kota pertama. Pemilihan kota pertama dilakukan
secara acak.
3. Setelah menempatkan kota pertama dalam tabu
list, dimulailah perjalanan semut-semut tersebut
dari kota pertama menuju kota tujuan yang telah
ditentukan berdasarkan persamaan probabilitas
pada bagian dua. Jarak yang dicari adalah jarak
dari kota A ke kota E, dengan mencari jalur
terpendek dan hasil jalur yang didapatkan tidak
harus melewati semua kota.
4. Menghitung panjang perjalanan dari masingmasing semut dan kemudian ditentukan jalur
terpendek berdasarkan Tij (harga intensitas jejak
kaki semut ).
5. Langkah 1 sampai langkah 4 akan diulang
sebanyak Ncmax atau jika telah mengalami
konvergen. Setiap dimulainya siklus baru ,maka
harga Tij di-reset ulang bernilai sama dengan
nol.
b. Algoritma genetika
Berdasarkan contoh kasus di atas, maka
langkah yang harus dilakukan adalah:
1. Menginisialisasi parameter-parameter yang
diperlukan, yaitu:
a. Popsize (ukuran populasi): ukuran populasi
yang akan digunakan untuk perhitungan.
Contoh pada kasus diatas ditentukan ukuran
populasi sebanyak 10.
b. pc (peluang crossover): peluang terjadinya
rekombinasi atau persilangan pada suatu
kromosom. Contoh pada kasus diatas
ditentukan peluang crossover sebesar 0.500
c. pm (peluang mutasi): persentasi dari jumlah
total gen pada populasi yang mengalami
mutasi. Contoh pada kasus diatas ditentukan
peluang mutasi sebesar 0.100
X Y
A 20 50
B 10 25
C 18 10
D 50 40
E 55 15 Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-39
d. kb (peluang pelestarian): peluang pelestarian
dari populasi yang ada. Contoh pada kasus
diatas ditentukan peluang pelestarian sebesar
0.100
e. MaxGen (maksimum generasi): maksimum
generasi yang akan ada pada perhitungan.
Contoh pada kasus diatas ditentukan
maksimum jumlah generasi sebanyak 50
f. (panjang kromosom): panjang kromosom
yang diinginkan. Contoh pada kasus diatas
ditentukan panjang kromosom adalah 5
2. Melakukan seleksi sesuai dengan metode yang
dibutuhkan.
Misalkan pada kasus, dilakukan seleksi
menggunakan metode Roda Roulette, maka
langkah-langkah yang harus dikerjakan:
a. Mencari nilai fitness relatif dan fitness
kumulatif. Misalkan Total Fitness = 12,5720.
Maka dapat dicari fitness relatif (pk) dari
tiap-tiap kromosom:
1. p1=F1/Total
Fitness=0,902/12,5720=0,071.
2. p2=F1/Total
Fitness=0,823/12,5720=0,065.
3. p3=F1/Total
Fitness=0,627/12,5720=0,049.
dan seterusnya sampai sebanyak ukuran
populasi. Fitness kumulatif (qk) dapat dicari
sebagai berikut:
1.q1 = p1 = 0,071.
2.q2 = q1 + p2 = 0,071 + 0,065 = 0.136.
3.q3 = q2 + p3 = 0,136 + 0,049
dan seterusnya sampai sebanyak ukuran
populasi.
b. Membangkitkan bilangan acak sebanyak
ukuran populasi = 10. Bilangan acak
berukuran 0-1.
3. Melakukan persilangan sesuai dengan metode
yang dibutuhkan.
a. Membangkitkan bilangan acak antara 0-1
sebanyak ukuran populasi, yaitu 10 buah
untuk memilih kromosom mana saja yang
akan dilakukan persilangan.
b. Memilih bilangan acak yang kurang dari
peluang crossover, sehingga kromosomnya
dapat disilangkan.
.
4. Melakukan mutasi sesuai dengan metode yang
dibutuhkan.
a. Menghitung jumlah bit yang ada pada
populasi, dengan rumus Popsize*L =
10*6=60.
b. Membangkitkan bilangan acak antara 0-1
sebanyak jumlah bit (360 buah).
c. Kromosom yang terkecil daripada peluang
mutasi, akan terkena mutasi.
d. Populasi akhir setelah dilakukan mutasi akan
dijadikan sebagai populasi awal untuk
generasi berikutnya.
e. Ulangi langkah a sampai d sebanyak ukuran
maksimum gen = 50.
f. Temukan nilai fitness terbaik
5. KESIMPULAN
a. Pemanfaatan teknologi informasi pada
pencarian jalur terpendek menghasilkan suatu
hasil atau keluaran yang akurat dan tepat, untuk
pilihan perjalanan seseorang dengan
mempertimbangkan beberapa parameter yang
lain.
b. Untuk kasus yang berbeda algoritma akan
memberikan hasil yang berbeda, tidak dapat
dipastikan bahwa algoritma semut atau genetik
yang terbaik.
c. Secara konsep algoritma, metode konvesional
lebih mudah untuk dipahami. Namun, hasil
yang diperoleh dari metode heuristik lebih
variatif.
d. Dengan metode heuristik, waktu perhitungan
yang diperlukan lebih cepat 30% dibandingkan
dengan menggunakan metode konvensional.
6. SARAN
a. Diharapkan ada penelitian lebih lanjut untuk
mengetahui efisiensi dari pencarian jalur
terpendek menggunakan Metode heuristik.
b. Diharapkan adanya penelitian yang dapat
membandingkan antar metode heuristik yang
lain.
PUSTAKA
Goldberg, D.E., Genetic Algorithms in Search,
Optimization & Machine Learning, New
York: Addison-Wesley, 1989
Kusumadewi, S., Artificial Intelligence (Teknik dan
Aplikasinya), Yogyakarta: Graha Ilmu, 2003
Kusumadewi, S., dan H., Purnomo, Penyelesaian
Masalah Optimasi dengan Teknik-teknik
Heuristi, Yogyakarta: Graha Ilmu, 2005
Lukas, dkk., “Penerapan Algoritma Genetika untuk
Travelling Salesman Problem dengan
Menggunakan Metode Order Crossover dan
Insertion Mutation”, Seminar Nasional
Aplikasi Teknologi Informasi, hlm: 1 s/d 5,
2005
Efendi, R., “Penerapan algoritma semut untuk
pemecahan masalah spanning tree pada kasus
pemasangan jaringan kabel telepon”. Tugas
Akhir, Jurusan Teknik Informatika,
Universitas Islam Indonesia, 2003.
TERPENDEK DENGAN ALGORITMA SEMUT DAN ALGORITMA GENETIKA
ABSTRAKSI
Tanpa program komputer hanyalah menjadi sebuah kotak yang tak berguna. Secara umum, pencarian
jalur terpendek dapat dibagi menjadi dua metode yaitu metode konvensional dan heuristik. Pemanfaatan metode
heuristik yang diharapkan dapat menyelesaikan masalah pencarian jalur terpendek dengan hasil yang lebih
variatif dan dengan waktu perhitungan yang lebih singkat.
Pada metode konvensional logika yang dipakai hanya dengan membandingkan jarak masing-masing
node dan kemudian mencari jarak yang terpendek. Namun, kelemahan metode konvesional pada keakuratan
hasil yang didapatkan serta tingkat kesalahan yang dihasilkan pada perhitungan. Hal tersebut tidak akan
menjadi masalah jika data yang dibutuhkan hanya sedikit, sebaliknya maka akan menyebabkan peningkatan
tingkat kesalahan perhitungan dan penurunan keakuratan.
Pemanfaatan teknologi informasi pada pencarian jalur terpendek menghasilkan suatu hasil atau
keluaran yang akurat dan tepat, untuk pilihan perjalanan seseorang dengan mempertimbangkan beberapa
parameter yang lain. Untuk kasus yang berbeda algoritma akan memberikan hasil yang berbeda, tidak dapat
dipastikan bahwa algoritma semut atau genetik yang terbaik. Secara konsep algoritma, metode konvesional
lebih mudah untuk dipahami tetapi, hasil yang diperoleh dari metode heuristik lebih variatif. Dengan metode
heuristik, waktu perhitungan yang diperlukan lebih cepat 30% dibandingkan dengan menggunakan metode
konvensional.
Kata kunci: Pencarian jalur terpendek, Heuristik, Algoritma Semut, Algoritma Genetika
1. PENDAHULUAN
Untuk menggunakan atau memfungsikan
sebuah komputer maka harus terdapat program yang
terdistribusi di dalamnya, tanpa program komputer
hanyalah menjadi sebuah kotak yang tak berguna.
Program yang terdapat pada komputer sangat
bervariasi dan setiap program pasti menggunakan
algoritma. Algoritma merupakan kumpulan perintah
untuk menyelesaikan suatu masalah. Perintahperintahnya dapat diterjemahkan secara bertahap
dari awal hingga akhir. Masalah tersebut dapat
berupa apapun dengan catatan untuk setiap masalah
memiliki kriteria kondisi awal yang harus dipenuhi
sebelum menjalankan algoritma.
Dalam kehidupan, sering dilakukan
perjalanan dari satu tempat atau kota ke tempat yang
lain dengan mempertimbangkan efisiensi, waktu dan
biaya sehingga diperlukan ketepatan dalam
menentukan jalur terpendek antar suatu kota. Hasil
penentuan jalur terpendek akan menjadi
pertimbangan dalam pengambilan keputusan untuk
menununjukkan jalur yang akan ditempuh dan yang
didapatkan juga membutuhkan kecepatan dan
keakuratan dengan bantuan komputer.
Secara umum, pencarian jalur terpendek
dapat dibagi menjadi dua metode, yaitu metode
konvensional dan metode heuristik. Metode
konvensional cenderung lebih mudah dipahami
daripada metode heuristik, tetapi jika dibandingkan,
hasil yang diperoleh dari metode heuristik lebih
variatif dan waktu perhitungan yang diperlukan
lebih singkat.
a. Rumusan Masalah
Seringkali penyelesaian masalah jalur
terpendek masih menggunakan metode konvensional
bahkan menggunakan perhitungan manual.
Pemanfaatan metode heuristik masih sangat jarang
digunakan, Sehingga dapat dirumuskan sebuah
masalah yaitu dengan pemanfaatan metode heuristik
yang diharapkan nantinya dapat menyelesaikan
masalah pencarian jalur terpendek dengan hasil yang
lebih variatif dan dengan waktu perhitungan yang
lebih singkat.
b. Batasan Masalah
Dari latar belakang dan rumusan masalah
yang telah dijelaskan, penelitian dibatasi pada dua
jenis algoritma yang digunakan dalam metode
heuristik, yaitu algoritma genetika (Genetic
Algorithm, GA) dan algoritma semut (Ant Colony
Algorithm, Antco).
c. Tujuan Penelitian
Penelitian bertujuan menyelesaikan masalah
rute menggunakan metode heuristik, khususnya
algoritma genetika dan algoritma semut, mencoba
mengimplementasikan dengan sebuah kasus
sederhana, dan mempelajari lebih dalam tentang
cabang dari ilmu kecerdasan buatan.
d. Manfaat Penelitian
Manfaat yang dapat diambil dari penelitian
adalah:
1. Menawarkan penyelesaian yang lebih mudah
dalam perhitungan (sesuai dengan tujuan
algoritma heuristik) untuk pencarian jalur
terpendek
2. Dapat diaplikasikan menjadi sebuah perangkat
lunak
2. LANDASAN TEORI
a. Pencarian jalur terpendek
Secara umum penyelesaian masalah
pencarian jalur terpendek dapat dilakukan
menggunakan dengan dua buah metode, yaitu
metode algoritma konvensional dan metode
heuristik. Metode algoritma konvensional diterapkan
dengan cara perhitungan matematis seperti biasa,
sedangkan metode heuristik diterapkan dengan
perhitungan kecerdasan buatan, dengan menentukan
basis pengetahuan dan perhitungannya.
a. Metode konvensional
Metode konvensional berupa algoritma yang
menggunakan perhitungan matematis biasa. Ada
beberapa metode konvensional yang biasa
digunakan untuk melakukan pencarian jalur
terpendek, diantaranya algoritma Djikstraa,
algoritma Floyd-Warshall, dan algoritma
Bellman-Ford
b. Metode heuristik
Adalah sub bidang dari kecerdasan buatan yang
digunakan untuk melakukan pencarian dan
penentuan jalur terpendek. Ada beberapa
algoritma pada metode heuristik yang biasa
digunakan dalam pencarian jalur terpendek.
Namun dalam penelitian dibatasi hanya
membahas dua macam algoritma yaitu algoritma
semut dan algoritma genetika.
b. Algoritma semut
Algoritma Semut diadopsi dari perilaku
koloni semut yang dikenal sebagai sistem semut
(Dorigo, 1996). Secara alamiah koloni semut
mampu menemukan rute terpendek dalam perjalanan
dari sarang ke tempat-tempat sumber makanan.
L R L R
(a) (b)
L R L R
(c) (d)
Gambar 1. Perjalanan semut menemukan sumber
makanan.
Koloni semut dapat menemukan rute
terpendek antara sarang dan sumber makanan
berdasarkan jejak kaki pada lintasan yang telah
dilalui. Semakin banyak semut yang melalui suatu
lintasan, maka semakin jelas bekas jejak kakinya.
Hal ini menyebabkan lintasan yang dilalui semut
dalam jumlah sedikit, semakin lama semakin
berkurang kepadatan semut yang melewatinya, atau
bahkan akan tidak dilewati sama sekali. Sebaliknya
lintasan yang dilalui semut dalam jumlah banyak,
semakin lama akan semakin bertambah kepadatan
semut yang melewatinya, atau bahkan semua semut
melalui lintasan tersebut.
Gambar 1.a menujukkan perjalanan semut
dalam menemukan jalur terpendek dari sarang ke
sumber makanan, terdapat dua kelompok semut
yang melakukan perjalanan. Kelompok semut L
berangkat dari arah kiri ke kanan dan kelompok
semut R berangkat dari kanan ke kiri. Kedua
kelompok berangkat dari titik yang sama dan dalam
posisi pengambilan keputusan jalan sebelah mana
yang akan diambil. Kelompok L membagi dua
kelompok lagi. Sebagian melalui jalan atas dan
sebagian melalui jalan bawah. Hal ini juga berlaku
pada kelompok R. Gambar 1.b dan Gambar 1.c
menunjukkan bahwa kelompok semut berjalan pada
kecepatan yang sama dengan meninggalkan feromon
atau jejak kaki di jalan yang telah dilalui. Feromon
yang ditinggalkan oleh kumpulan semut yang
melalui jalan atas telah mengalami banyak
penguapan karena semut yang melalui jalan atas
berjumlah lebih sedikit dari pada jalan yang di
bawah. Hal ini disebabkan jarak yang ditempuh
lebih panjang daripada jalan bawah. Sedangkan
feromon yang berada di jalan bawah penguapannya
cenderung lebih lama. Karena semut yang melalui
jalan bawah lebih banyak daripada semut yang
melalui jalan atas. Gambar 1.d menunjukkan bahwa
semut-semut yang lain pada akhirnya memutuskan
untuk melewati jalan bawah karena feromon yang
ditinggalkan masih banyak. Sedangkan feromon
pada jalan atas sudah banyak menguap sehingga
semut-semut tidak memilih jalan atas tersebut.
Semakin banyak semut yang melalui jalan maka
semakin banyak semut yang mengikutinya, semakin
sedikit semut yang melalui jalan, maka feromon
yang ditinggalkan semakin berkurang bahkan hilang.
Dari sinilah kemudian terpilihlah jalur terpendek
antara sarang dan sumber makanan.
Dalam algoritma semut, diperlukan beberapa
variabel dan langkah-langkah untuk menentukan
jalur terpendek, yaitu:
Langkah 1:
a. Inisialisasi harga parameter-parameter
algoritma.
Parameter-parameter yang di inisialisasikan
adalah:
1. Intensitas jejak semut antar kota dan
perubahannya (τij
) Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-35
2. Banyak kota (n) termasuk x dan y
(koordinat) atau dij (jarak antar kota)
3. Tetapan siklus-semut (Q)
4. Tetapan pengendali intensitas jejak semut
(α)
5. Tetapan pengendali visibilitas (β)
6. Visibilitas antar kota = 1/dij (ηij)
7. Banyak semut (m)
8. Tetapan penguapan jejak semut (ρ)
9. Jumlah siklus maksimum (NCmax) bersifat
tetap selama algoritma dijalankan,
sedangkan τij akan selalu diperbaharui
harganya pada setiap siklus algoritma mulai
dari siklus pertama (NC=1) sampai tercapai
jumlah siklus maksimum (NC=NCmax)
atau sampai terjadi konvergensi.
b. Inisialisasi kota pertama setiap semut.
Setelah inisialisasi τij
dilakukan, kemudian m
semut ditempatkan pada kota pertama tertentu
secara acak.
Langkah 2:
Pengisian kota pertama ke dalam tabu list.
Hasil inisialisasi kota pertama setiap semut dalam
langkah 1 harus diisikan sebagai elemen pertama
tabu list. Hasil dari langkah ini adalah terisinya
elemen pertama tabu list setiap semut dengan indeks
kota tertentu, yang berarti bahwa setiap tabuk
(1) bisa
berisi indeks kota antara 1 sampai n sebagaimana
hasil inisialisasi pada langkah 1.
Langkah 3:
Penyusunan rute kunjungan setiap semut ke
setiap kota. Koloni semut yang sudah terdistribusi ke
sejumlah atau setiap kota, akan mulai melakukan
perjalanan dari kota pertama masing-masing sebagai
kota asal dan salah satu kota-kota lainnya sebagai
kota tujuan. Kemudian dari kota kedua masingmasing, koloni semut akan melanjutkan perjalanan
dengan memilih salah satu dari kota-kota yang tidak
terdapat pada tabuk
sebagai kota tujuan selanjutnya.
Perjalanan koloni semut berlangsung terus menerus
sampai semua kota satu persatu dikunjungi atau
telah menempati tabuk
. Jika s menyatakan indeks
urutan kunjungan, kota asal dinyatakan sebagai
tabuk
(s) dan kota-kota lainnya dinyatakan sebagai
{N-tabuk}, maka untuk menentukan kota tujuan
digunakan persamaan probabilitas kota untuk
dikunjungi sebagai berikut:
[ ] [ ]
∑[ ] [ ]
∈ −
α β
α β
τ ⋅ η
τ ⋅ η
=
k' {N tabu }
ik' ik'
k ij ij
ij
k
p untuk j∈{N-tabuk}
dan p 0
k
ij
= , untuk j lainnya
dengan i sebagai indeks kota asal dan j sebagai
indeks kota tujuan.
Langkah 4:
a. Perhitungan panjang rute setiap semut.
Perhitungan panjang rute tertutup (length closed
tour) atau Lk setiap semut dilakukan setelah satu
siklus diselesaikan oleh semua semut.
Perhitungan dilakukan berdasarkan tabuk
masing-masing dengan persamaan berikut:
∑
−
=
= + +
n 1
s 1
k tabu (n),tabu (1) tabu (s),tabu (s 1) k k k k
L d d
dengan dij
adalah jarak antara kota i ke kota j
yang dihitung berdasarkan persamaan:
2 2
( ) ( )
ij i j i j
d = x − x + y − y
b. Pencarian rute terpendek.
Setelah Lk setiap semut dihitung, akan didapat
harga minimal panjang rute tertutup setiap
siklus atau LminNC dan harga minimal panjang
rute tertutup secara keseluruhan adalah atau
Lmin.
c. Perhitungan perubahan harga intensitas jejak
kaki semut antar kota.
Koloni semut akan meninggalkan jejak-jejak
kaki pada lintasan antar kota yang dilaluinya.
Adanya penguapan dan perbedaan jumlah semut
yang lewat, menyebabkan kemungkinan
terjadinya perubahan harga intensitas jejak kaki
semut antar kota. Persamaan perubahan ini
adalah:
∑
=
∆τ = ∆τ
m
k 1
k
ij ij
dengan
k
ij
∆τ adalah perubahan harga intensitas
jejak kaki semut antar kota setiap semut yang
dihitung berdasarkan persamaan
k
k
ij
L
Q
∆τ = ,
untuk (i,j) ∈ kota asal dan kota tujuan dalam
tabuk
0
k
∆τ
ij
= , untuk (i,j) lainnya
Langkah 5:
a. Perhitungan harga intensitas jejak kaki semut
antar kota untuk siklus selanjutnya.
Harga intensitas jejak kaki semut antar kota pada
semua lintasan antar kota ada kemungkinan
berubah karena adanya penguapan dan
perbedaan jumlah semut yang melewati. Untuk
siklus selanjutnya, semut yang akan melewati
lintasan tersebut harga intensitasnya telah
berubah. Harga intensitas jejak kaki semut antar
kota untuk siklus selanjutnya dihitung dengan
persamaan:
ij ij ij
τ = ρ ⋅ τ + ∆τ
b. Atur ulang harga perubahan intensitas jejak kaki
semut antar kota. Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-36
Untuk siklus selanjutnya perubahan harga
intensitas jejak semut antar kota perlu diatur
kembali agar memiliki nilai sama dengan nol.
Langkah 6:
Pengosongan tabu list, dan ulangi langkah 2 jika
diperlukan. Tabu list perlu dikosongkan untuk
diisi lagi dengan urutan kota yang baru pada
siklus selanjutnya, jika jumlah siklus maksimum
belum tercapai atau belum terjadi konvergensi.
Algoritma diulang lagi dari langkah 2 dengan
harga parameter intensitas jejak kaki semut antar
kota yang sudah diperbaharui.
c. Algoritma genetika
Algoritma genetika adalah algoritma
pencarian yang didasarkan atas mekanisme seleksi
alami dan evolusi biologis. Algoritma genetika
mengkombinasikan antara deretan struktur dengan
pertukaran informasi acak ke bentuk algoritma
pencarian dengan beberapa perubahan bakat pada
manusia. Pada setiap generasi, himpunan baru dari
deretan individu dibuat berdasarkan kecocokan
pada generasi sebelumnya (Goldberg,1989).
Dalam algoritma genetika, diperlukan
beberapa proses untuk menentukan jalur terpendek,
yaitu:
a. Proses Pengkodean (Encoding)
Adalah salah suatu proses yang sulit dalam
algoritma genetika. Hal ini disebabkan Karena
proses pengkodean untuk setiap permasalahan
berbeda-beda karena tidak semua teknik pengkodean
cocok untuk setiap permasalahan. Proses
pengkodean ini menghasilkan suatu deretan yang
kemudian disebut kromosom. Kromosom terdiri dari
sekumpulan bit yang dikenal sebagai gen.
Ada beberapa macam teknik pengkodean
yang dapat dilakukan dalam algoritma genetika
(Lukas, 2005), diantaranya pengkodean biner
(binary encoding), pengkodean permutasi
(permutation encoding), pengkodean nilai (value
encoding) dan pengkodean pohon (tree encoding).
b. Proses Seleksi
Adalah proses untuk menentukan individu
mana saja yang akan dipilih untuk dilakukan
rekombinasi dan bagaimana keturunan terbentuk
dari individu-individu terpilih tersebut. Langkah
pertama yang dilakukan dalam seleksi adalah
pencarian nilai fitness. Masing-masing individu
dalam suatu wadah seleksi akan menerima
probabilitas reproduksi yang tergantung pada nilai
obyektif dirinya sendiri terhadap nilai obyektif dari
semua individu dalam wadah seleksi tersebut. Nilai
fitness kemudian akan digunakan pada tahap seleksi
berikutnya.
Ada beberapa macam proses seleksi yang ada
pada algoritma genetika, diantaranya (Kusumadewi,
2005):
1. Seleksi dengan Roda Roulette (Roulette Wheel
Selection), dengan memetakan individu-individu
dalam suatu segmen garis secara berurutan
sedemikian hingga tiap-tiap segmen individu
memiliki ukuran yang sama dengan ukuran
fitness-nya.
2. Seleksi berdasarkan Ranking Fitness (Rankbased Fitness), yaitu dengan cara mengurutkan
populasi menurut nilai obyektifnya.
3. Seleksi Pengambilan Sampling Stocastic
(Stocastic Universal Sampling), dengan
memetakan individu-individu seperti halnya roda
roulette, kemudian memberikan sejumlah pointer
sebanyak individu yang ingin diseleksi pada
garis tersebut.
4. Seleksi Lokal (Local Selection), seleksi yang
dilakukan hanya pada konstrain tertentu.
5. Seleksi dengan Pemotongan (Truncation
Selection), seleksi buatan yang biasanya
digunakan oleh polulasi yang jumlahnya sangat
besar.
6. Seleksi dengan Turnamen (Tournament
Selection), menetapkan suatu nilai turnamen
untuk individu-individu yang dipilih secara acak
dari suatu populasi.
c. Proses Rekombinasi
Adalah proses untuk menyilangkan dua
kromosom sehingga membentuk kromosom baru
yang harapannya lebih baik dari pada induknya.
Rekombinasi dikenal juga dengan nama crossover.
Tidak semua kromosom pada suatu populasi akan
mengalami proses rekombinasi. Kemungkinan suatu
kromosom mengalami proses rekombinasi
didasarkan pada probabilitas crossover yang telah
ditentukan terlebih dahulu. Probabilitas crossover
menyatakan peluang suatu kromosom akan
mengalami crossover.
Ada beberapa macam proses rekombinasi
yang ada pada algoritma genetika, diantaranya
(Kusumadewi, 2005):
1. Rekombinasi diskret, dengan menukar nilai
variabel antar kromosom induk
2. Rekombinasi menengah, merupakan metode
rekombinasi yang hanya digunakan untuk
variabel real dan variabel yang bukan biner.
3. Rekombinasi garis, memiliki prinsip yang sama
dengan rekombinasi menengah, dengan nilai
alpha sama untuk semua variabel.
4. Penyilangan satu titik, dengan menukar variabelvariabel antar kromosom pada satu titik untuk
menghasilkan anak.
5. Penyilangan banyak titik, dengan menukar
variabel-variabel antar kromosom pada banyak
titik untuk menghasilkan anak.
6. Penyilangan seragam, dengan membuat sebuah
mask penyilangan sepanjang panjang kromosom
secara acak.
7. Penyilangan dengan permutasi, dengan cara
memilih sub-barisan suatu turnamen dari satu Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-37
induk dengan tetap menjaga urutan dan posisi
sejumlah kota yang mungkin terhadap induk
lainnya.
d. Proses Mutasi
Adalah proses penambahan nilai acak yang
sangat kecil dengan probabilitas rendah pada
variabel keturunan. Peluang mutasi didefinisikan
sebagai persentasi dari jumlah total gen pada
populasi yang mengalami mutasi. Peluang mutasi
mengendalikan banyaknya gen baru yang akan
dimunculkan untuk dievaluasi. Jika peluang mutasi
terlalu kecil, banyak gen yang mungkin berguna
tidak dievaluasi, tetapi bila peluang mutasi ini terlalu
besar maka akan terlalu banyak gangguan acak,
sehingga anak akan kehilangan kemiripan dari
induknya dan algoritma juga akan kehilangan
kemampuan untuk belajar dari history pencarian
(Kusumadewi, 2005). Ada beberapa macam proses
mutasi yang ada pada algritma genetika,
diantaranya:
1. Mutasi bilangan real, dengan mendefinisikan
ukuran langkah mutasi, kecil atau besar.
2. Mutasi biner, dengan mengganti satu atau
beberapa nilai gen dari kromosom.
Berikut adalah langkah algoritma genetika
sederhana untuk pencarian jalur terpendek:
Langkah 1
Inisialisasi generasi awal. Generasi awal harus
diinisialisasi kosong, sehingga belum ada generasi.
Generasi = 0.
Langkah 2
Inisialisasi populasi awal, P (generasi) secara acak.
Populasi yang ditentukan di inisialisasi secara acak.
Langkah 3
Evaluasi nilai fitness pada setiap individu dalam P
(generasi). Nilai fitness adalah nilai yang
menunjukkan kualitas suatu kromosom dalam
populasi.
Langkah 4
a. Menambahkan generasi baru dengan persamaan:
generasi = generasi+1
b. Seleksi populasi tersebut untuk mendapatkan
kandidat induk P’ (generasi)
c. Lakukan crossover pada P’ (generasi).
d. Lakukan mutasi pada P’ (generasi).
e. Lakukan evaluasi fitness setiap individu pada P’
(generasi).
f. Bentuk populasi baru, P (generasi) =
{P(generasi1) yang bertahan, P’ (generasi)}.
3. METODE PENELITIAN
Pada penelitian ini, terdapat beberapa metode
pengumpulan data yang digunakan, yaitu:
1. Metode kepustakaan
Metode pengumpulan data kepustakaan
dilakukan dengan mengumpulkan data-data dari
sumber atau buku yang relevan terhadap
penelitian.
2. Metode wawancara
Metode wawancara dilakukan dengan cara tatap
muka dan menanyakan langsung kepada objek
yang pernah melakukan penelitian sebelumnya.
4. PEMBAHASAN
4.1 Pencarian jalur terpendek
Gambar 2. Ilustrasi Jalur Terpendek dengan Jarak
Pada dasarnya permasalahan pencarian jalur
terpendek antar kota merupakan pencarian jalur
terpendek antar titik yang telah diketahui
koordinatnya. Dengan mengetahui konsep pencarian
jalur terpendek antar titik, untuk selanjutnya dapat
diterapkan pada pencarian jalur terpendek pada
berbagai kota yang ingin diketahui. Contoh kasus
yang akan diambil adalah pencarian jalur terpendek
antara titik A dan titik E.
Terdapat dua jenis kasus yang bisa
diturunkan dari gambar di atas. Kasus pertama
adalah mengetahui jarak antar node yang
ditunjukkan dengan garis penghubung antar titik..
Kasus yang kedua adalah dengan dengan
mengetahui koordinat titik saja. Gambar 2
merupakan jenis kasus yang pertama yaitu dengan
mengetahui jarak antar titik. Sedangkan gambar 3
merupakan jenis kasus yang kedua, yaitu dengan
mengetahui titik koordinatnya saja. Untuk kasus
pertama, penyelesaian cenderung lebih mudah
karena jarak antar titik telah diketahui sebagai
berikut:
Tabel 1. Tabel Jarak antar Titik
A B C D E
A 0 5 7 3 -
B 5 0 4 - -
C 7 4 0 - 5
D 3 - - 0 4
E - - 5 4 0
Sedangkan untuk kasus kedua yang telah
ditunjukkan pada Gambar 3.
Dari gambar 3 di atas, misalnya titik–titik
yang telah ditentukan mempunyai koordinat
sebagaimana tabel 2. Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-38
Gambar 3. Ilustrasi Jalur Terpendek tanpa Jarak
Tabel 2. Koordinat titik antar kota
Karena belum diketahui jarak antar titiknya
dan hanya diketahui titik koordinat saja, Maka
perhitungan dimulai dari penentuan jarak antar
simpul titik dengan dengan menggunakan titik yang
diketahui. Titik yang diketahui menggunakan
koordinat sumbu X dan Y. Langkah di atas
merupakan langkah yang harus dilakukan untuk
semua metode.
Penyelesaian kasus diatas dapat dilakukan
dengan dua metode seperti yang telah dijelaskan
pada bab II, yaitu metode konvensional dan metode
heuristik. Pada metode konvensional, logika yang
dipakai sangat sederhana. Yaitu hanya dengan
membandingkan jarak masing-masing node dan
kemudian mencari jarak yang terpendek. Namun,
kelemahan metode konvesional ini adalah pada
keakuratan hasil yang didapatkan serta tingkat
kesalahan yang dihasilkan pada perhitungan. Hal
tersebut tidak akan menjadi masalah jika data yang
dibutuhkan hanya sedikit, sebaliknya maka akan
menyebabkan peningkatan tingkat kesalahan
perhitungan dan penurunan keakuratan. Penelitian
ini akan membahas mengenai penyelesaian jalur
terpendek menggunakan metode heuristik dengan
algortima semut dan algoritma genetika.
4.2 Penyelesaian pencarian jalur terpendek
a. Algoritma semut
Berdasarkan contoh kasus yang ada, maka
langkah yang harus dilakukan adalah:
1. Menginisialisasi parameter-parameter yang
diperlukan, yaitu:
a. τij
(intensitas jejak semut antar kota) dan
perubahannya, parameter ini berfungsi
menentukan jumlah intensitas jejak semut
antar kota sehingga diketahui jalur terpendek
yang dihasilkan.
b. n (banyak kota) termasuk x dan y (koordinat)
atau dij
(jarak antar kota), pada contoh kasus
di atas, jumlah n = 5 dan mempunyai
koordinat atau jarak yang telah ditentukan.
c. Q (tetapan siklus-semut), α (tetapan
pengendali intensitas jejak semut), β (tetapan
pengendali visibilitas), ηij
(visibilitas antar
kota=1/dij
), dan ρ (tetapan penguapan jejak
semut), nilai dari parameter harus
didefinisikan dahulu karena bersifat sebagai
konstanta.
d. m (banyak semut), jumlah semut yang akan
digunakan untuk menyelusuri jalur bisa
bernilai sembarang tergantung oleh
pengguna. Contoh kasus diatas menggunakan
100 semut.
e. NCmax(jumlah siklus maksimum), adalah
jumlah maksimum siklus yang ingin di
jalankan, hingga menemukan hasil yang
terbaik. Misal maksimum siklus 10 kali,
maka perhitungan akan dilakukan maksimal
10 kali hingga menemukan hasil yang
terpendek.
2. Menempatkan kelompok semut tersebut pada
kota pertama. Pemilihan kota pertama dilakukan
secara acak.
3. Setelah menempatkan kota pertama dalam tabu
list, dimulailah perjalanan semut-semut tersebut
dari kota pertama menuju kota tujuan yang telah
ditentukan berdasarkan persamaan probabilitas
pada bagian dua. Jarak yang dicari adalah jarak
dari kota A ke kota E, dengan mencari jalur
terpendek dan hasil jalur yang didapatkan tidak
harus melewati semua kota.
4. Menghitung panjang perjalanan dari masingmasing semut dan kemudian ditentukan jalur
terpendek berdasarkan Tij (harga intensitas jejak
kaki semut ).
5. Langkah 1 sampai langkah 4 akan diulang
sebanyak Ncmax atau jika telah mengalami
konvergen. Setiap dimulainya siklus baru ,maka
harga Tij di-reset ulang bernilai sama dengan
nol.
b. Algoritma genetika
Berdasarkan contoh kasus di atas, maka
langkah yang harus dilakukan adalah:
1. Menginisialisasi parameter-parameter yang
diperlukan, yaitu:
a. Popsize (ukuran populasi): ukuran populasi
yang akan digunakan untuk perhitungan.
Contoh pada kasus diatas ditentukan ukuran
populasi sebanyak 10.
b. pc (peluang crossover): peluang terjadinya
rekombinasi atau persilangan pada suatu
kromosom. Contoh pada kasus diatas
ditentukan peluang crossover sebesar 0.500
c. pm (peluang mutasi): persentasi dari jumlah
total gen pada populasi yang mengalami
mutasi. Contoh pada kasus diatas ditentukan
peluang mutasi sebesar 0.100
X Y
A 20 50
B 10 25
C 18 10
D 50 40
E 55 15 Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-39
d. kb (peluang pelestarian): peluang pelestarian
dari populasi yang ada. Contoh pada kasus
diatas ditentukan peluang pelestarian sebesar
0.100
e. MaxGen (maksimum generasi): maksimum
generasi yang akan ada pada perhitungan.
Contoh pada kasus diatas ditentukan
maksimum jumlah generasi sebanyak 50
f. (panjang kromosom): panjang kromosom
yang diinginkan. Contoh pada kasus diatas
ditentukan panjang kromosom adalah 5
2. Melakukan seleksi sesuai dengan metode yang
dibutuhkan.
Misalkan pada kasus, dilakukan seleksi
menggunakan metode Roda Roulette, maka
langkah-langkah yang harus dikerjakan:
a. Mencari nilai fitness relatif dan fitness
kumulatif. Misalkan Total Fitness = 12,5720.
Maka dapat dicari fitness relatif (pk) dari
tiap-tiap kromosom:
1. p1=F1/Total
Fitness=0,902/12,5720=0,071.
2. p2=F1/Total
Fitness=0,823/12,5720=0,065.
3. p3=F1/Total
Fitness=0,627/12,5720=0,049.
dan seterusnya sampai sebanyak ukuran
populasi. Fitness kumulatif (qk) dapat dicari
sebagai berikut:
1.q1 = p1 = 0,071.
2.q2 = q1 + p2 = 0,071 + 0,065 = 0.136.
3.q3 = q2 + p3 = 0,136 + 0,049
dan seterusnya sampai sebanyak ukuran
populasi.
b. Membangkitkan bilangan acak sebanyak
ukuran populasi = 10. Bilangan acak
berukuran 0-1.
3. Melakukan persilangan sesuai dengan metode
yang dibutuhkan.
a. Membangkitkan bilangan acak antara 0-1
sebanyak ukuran populasi, yaitu 10 buah
untuk memilih kromosom mana saja yang
akan dilakukan persilangan.
b. Memilih bilangan acak yang kurang dari
peluang crossover, sehingga kromosomnya
dapat disilangkan.
.
4. Melakukan mutasi sesuai dengan metode yang
dibutuhkan.
a. Menghitung jumlah bit yang ada pada
populasi, dengan rumus Popsize*L =
10*6=60.
b. Membangkitkan bilangan acak antara 0-1
sebanyak jumlah bit (360 buah).
c. Kromosom yang terkecil daripada peluang
mutasi, akan terkena mutasi.
d. Populasi akhir setelah dilakukan mutasi akan
dijadikan sebagai populasi awal untuk
generasi berikutnya.
e. Ulangi langkah a sampai d sebanyak ukuran
maksimum gen = 50.
f. Temukan nilai fitness terbaik
5. KESIMPULAN
a. Pemanfaatan teknologi informasi pada
pencarian jalur terpendek menghasilkan suatu
hasil atau keluaran yang akurat dan tepat, untuk
pilihan perjalanan seseorang dengan
mempertimbangkan beberapa parameter yang
lain.
b. Untuk kasus yang berbeda algoritma akan
memberikan hasil yang berbeda, tidak dapat
dipastikan bahwa algoritma semut atau genetik
yang terbaik.
c. Secara konsep algoritma, metode konvesional
lebih mudah untuk dipahami. Namun, hasil
yang diperoleh dari metode heuristik lebih
variatif.
d. Dengan metode heuristik, waktu perhitungan
yang diperlukan lebih cepat 30% dibandingkan
dengan menggunakan metode konvensional.
6. SARAN
a. Diharapkan ada penelitian lebih lanjut untuk
mengetahui efisiensi dari pencarian jalur
terpendek menggunakan Metode heuristik.
b. Diharapkan adanya penelitian yang dapat
membandingkan antar metode heuristik yang
lain.
PUSTAKA
Goldberg, D.E., Genetic Algorithms in Search,
Optimization & Machine Learning, New
York: Addison-Wesley, 1989
Kusumadewi, S., Artificial Intelligence (Teknik dan
Aplikasinya), Yogyakarta: Graha Ilmu, 2003
Kusumadewi, S., dan H., Purnomo, Penyelesaian
Masalah Optimasi dengan Teknik-teknik
Heuristi, Yogyakarta: Graha Ilmu, 2005
Lukas, dkk., “Penerapan Algoritma Genetika untuk
Travelling Salesman Problem dengan
Menggunakan Metode Order Crossover dan
Insertion Mutation”, Seminar Nasional
Aplikasi Teknologi Informasi, hlm: 1 s/d 5,
2005
Efendi, R., “Penerapan algoritma semut untuk
pemecahan masalah spanning tree pada kasus
pemasangan jaringan kabel telepon”. Tugas
Akhir, Jurusan Teknik Informatika,
Universitas Islam Indonesia, 2003.
oop
OOP adalah paradigma pemrograman yang cukup dominan saat ini, karena mampu memberikan solusi kaidah pemrograman modern. Meskipun demikian, bukan berarti bahwa pemrograman prosedural sudah tidak layak lagi .
OOP diciptakan karena dirasakan masih adanya keterbatasan pada bahasa pemrograman tradisional. Konsep dari OOP sendiri adalah, semua pemecahan masalah dibagi ke dalam objek. Dalam OOP data dan fungsi-fungsi yang akan mengoperasikannya digabungkan menjadi satu kesatuan yang dapat disebut sebagai objek. Proses perancangan atau desain dalam suatu pemrograman merupakan proses yang tidak terpisah dari proses yang mendahului, yaitu analisis dan proses yang mengikutinya. Pembahasan mengenai orientasi objek tidak akan terlepas dari konsep objek seperti inheritance atau penurunan, encapsulation atau pembungkusan,
dan polymorphism atau kebanyakrupaan. Konsep-konsep ini merupakan fundamental dalam orientasi objek yang perlu sekali dipahami serta digunakan dengan baik, dan menghindari penggunaannya yang tidak tepat.
Class dan Objek
Dalam lingkungan program berorientasi objek, pemrogram mendefinisikan class secara statik. Pada saat run-time, class akan diinstantiasi menjadi objek. Ada pun objek yang merupakan instantiasi dari suatu class selalu dapat diacu melalui current objek, apa pun nama instant-nya.
Dalam lingkungan program berorientasi objek, pemrogram mendefinisikan class secara statik. Pada saat run-time, class akan diinstantiasi menjadi objek. Ada pun objek yang merupakan instantiasi dari suatu class selalu dapat diacu melalui current objek, apa pun nama instant-nya.
Dapat didefinisikan bahwa class merupakan struktur data dari suatu objek, lebih jelasnya adalah sebuah bentuk dasar atau blueprint yang mendefinisikan variabel method umum pada semua objek dari beberapa macam. Objek sendiri adalah kumpulan variabel dan fungsi yang dihasilkan dari template khusus atau disebut class. objek adalah elemen pada saat run-time yang akan diciptakan, dimanipulasi, dan dihancurkan ketika eksekusi. Ada pun class merupakan definisi statik dari himpunan objek yang mungkin diciptakan sebagai instantiasi dari class. Sederhananya adalah kumpulan objek yang mempunyai atribut sama. Dengan demikian, pada saat run-time maka yang kita miliki adalah objek.
Class biasany dibuat seperti ini
Class nama_classnya{
//berisi sekumpulan fungsi,variabel dan
//statement-statement lainnya
}
Class biasany dibuat seperti ini
Class nama_classnya{
//berisi sekumpulan fungsi,variabel dan
//statement-statement lainnya
}
Agar class tersebut dpt digunakan maka perlu memiliki atribut-atribut contonya dalam php/c++
//di php
class NamaClass {
var $atribut1;
var $atribut2;
function operasi(){}
class NamaClass {
var $atribut1;
var $atribut2;
function operasi(){}
}
//di c++
class NamaClass {
public:
int atribut1;
int atribut2;
int operasi(){retun nilai_int}
};
class NamaClass {
public:
int atribut1;
int atribut2;
int operasi(){retun nilai_int}
};
Pada bahasa pemerograman web lain ex. Java file harus disimpan dengan nama class berbeda dengan PHP kita dapat memberikan nama yang tidak mesti sama dengan nama classnya
Inheritance
Inheritance atau pewarisan adalah kalimat yang pasti ada di dalam pemerograman berorientasi objek disebut juga dengan istilah reusable.
Inheritance atau pewarisan adalah kalimat yang pasti ada di dalam pemerograman berorientasi objek disebut juga dengan istilah reusable.
Ketika kita menggunakan kembali atau mengganti method dari class yang sudah ada, serta ketika menambahkan field instant dan method baru, maka pada saat itulah Anda bekerja dengan inheritance. Konsep ini merupakan konsep yang fundamental dalam orientasi objek dan harus digunakan dengan baik, ada beberapa macam Inheritance atau pewarisan yang ada di dalam OOP Single Inheritance dan Multple Inheritance
- Single Inheritance
- Multiple Inheritance
dalam penggunaan inheritance class Induk akan mewariskan semua atribut yang ia miliki sehingga class bawahnya akan memilki atribut yang sama dengan class induk, bahkan dapat memilki kebabasan untuk memilki atribut berbeda dengan class induknya berikut ilustrasi dalam php
catatan :
sampai sekarang PHP belum mendukung multiple inheritance seperti C++ walapun PHP dan c/c++ begitu banyak kemiripannya, dan perubahan PHP versi 5 ditekankan pada OOP salah satunya adalah beberapa tambahan untuk kemampuan inheritance
sampai sekarang PHP belum mendukung multiple inheritance seperti C++ walapun PHP dan c/c++ begitu banyak kemiripannya, dan perubahan PHP versi 5 ditekankan pada OOP salah satunya adalah beberapa tambahan untuk kemampuan inheritance
/* inheritance.php */
class Bapak {
var $nama =”Bapak”;
function Bapak($n) {
$this->nama = $n;
}
var $nama =”Bapak”;
function Bapak($n) {
$this->nama = $n;
}
function Hallo() {echo “Halo, saya $this->nama
”;}
}
”;}
}
class Anak extends Bapak {}
$test = new Anak(”Anak dari Bapak”);
$test->Hallo();
?>
$test = new Anak(”Anak dari Bapak”);
$test->Hallo();
?>
Hasil tampilan dari listing program di atas adalah “Halo, saya Anak dari Bapak” dan bukannya “Halo, saya Bapak”. Mengapa demikian? Memang di dalam class Bapak didefinisikan variabel nama dengan nilai Bapak, selanjutnya kita membuat objek dari class Anak yang merupakan turunan dari class Bapak. Lihat bahwa instantiasi sekaligus mengisikan parameter baru “Anak dari Bapak”, sehingga ketika dipanggil maka mengisikan $this->nama dengan parameter tersebut. Ada pun di dalam implementasi pemrograman, kebanyakan pemrogram merasakan beberapa manfaat dari inheritance atau pewarisan, diantaranya:
Subclass mampu menyediakan perilaku khusus dari elemen dasar yang disediakan oleh superclass.
Subclass mampu menyediakan perilaku khusus dari elemen dasar yang disediakan oleh superclass.
Pemrogram dapat mengimplementasikan superclass untuk memanggil class abstrak yang menyatakan perilaku umum.
D.I.S.C
Kita barangkali akan dapat merajut jalinan interaksi yang lebih harmonis dan produktif, jika kita mampu mengenali kepribadian rekan kerja kita dengan lebih baik. Sebab, kita tahu, setiap orang memiliki tipe karakter yang unik. Dalam konteks ini, terdapat empat model kepribadian yang lazim dikenal sebagai DISC – atau singkatan dari : dominance, influence, steadiness, and conscientiousness. Mengenal lebih dalam keempat model ini barangkali akan membantu kita lebih efektif ketika membangun relasi dengan orang lain.
Dominance Style
Orang-orang yang masuk dalam model ini adalah mereka yang
suka mengendalikan lingkungan mereka, serta senang menggerakkan orang-orang di sekitar mereka. Mereka adalah jenis pribadi yang suka to-the-point, tidak bertele-tele. Mereka juga senang mengambil peran penting, pembuat keputusan, problem solver, dan melaksanakan berbagai hal. Mereka cenderung menyukai posisi sebagai leader. Meskipun demikian, ketika menjadi leader, mereka cenderung akan menjadi pemimpin yang otoriter, demanding, dan kurang memiliki kesabaran serta empati pada bawahan.
Orang-orang yang masuk dalam model ini adalah mereka yang
suka mengendalikan lingkungan mereka, serta senang menggerakkan orang-orang di sekitar mereka. Mereka adalah jenis pribadi yang suka to-the-point, tidak bertele-tele. Mereka juga senang mengambil peran penting, pembuat keputusan, problem solver, dan melaksanakan berbagai hal. Mereka cenderung menyukai posisi sebagai leader. Meskipun demikian, ketika menjadi leader, mereka cenderung akan menjadi pemimpin yang otoriter, demanding, dan kurang memiliki kesabaran serta empati pada bawahan.
Ketika orang-orang dari model ini termotivasi secara negative, mereka dapat menjadi seorang pembangkang (rebels). Mereka juga tipe orang yang cepat menjadi bosan dengan suatu rutinitas. Mereka juga kurang suka dengan detil, karena pada dasarnya mereka cenderung tipe yang suka dengam big-view picture dan visioner. Orang dengan tipe D ini juga adalah orang yang menyukai tantangan dan berani mengambil resiko.
Untuk menciptakan lingkungan motivasi yang benar pada model kepribadian seperti ini, kita perlu memperhatikan hal berikut:
• Pesan harus jelas, dan langsung pada pokok pembahasan ketika kita berinteraksi dengan model kepribadian seperti ini.
• Hindari hal-hal yg terlalu pribadi atau berbicara terlalu banyak yang tidak ada hubungannya dengan pekerjaan.
• Biarkan mereka tahu apa yang anda harapkan dari mereka. Jika anda harus mengarahkan mereka, berikan mereka kesempatan untuk mengambil keputusan dan berada dalam kendali.
• Terimalah kebutuhan mereka untuk variasi dan perubahan. Jika mungkin, berikan tantangan-tantangan baru, juga kesempatan untuk mengarahkan yang lain.
• Pesan harus jelas, dan langsung pada pokok pembahasan ketika kita berinteraksi dengan model kepribadian seperti ini.
• Hindari hal-hal yg terlalu pribadi atau berbicara terlalu banyak yang tidak ada hubungannya dengan pekerjaan.
• Biarkan mereka tahu apa yang anda harapkan dari mereka. Jika anda harus mengarahkan mereka, berikan mereka kesempatan untuk mengambil keputusan dan berada dalam kendali.
• Terimalah kebutuhan mereka untuk variasi dan perubahan. Jika mungkin, berikan tantangan-tantangan baru, juga kesempatan untuk mengarahkan yang lain.
Influence Style
Orang-orang dengan model ini adalah mereka yang suka bergaul dengan orang lain, ekstrovert, dan senang berada pada lingkaran pertemanan yang luas. Mereka benar-benar menikmati berada bersama teman-temannya. Mereka tidak suka menyelesaikan sesuatu atau bekerja sendirian (single fighter). Sebaliknya, mereka lebih suka berhubungan dan bekerja dengan orang-orang daripada sendirian.
Orang-orang dengan model ini adalah mereka yang suka bergaul dengan orang lain, ekstrovert, dan senang berada pada lingkaran pertemanan yang luas. Mereka benar-benar menikmati berada bersama teman-temannya. Mereka tidak suka menyelesaikan sesuatu atau bekerja sendirian (single fighter). Sebaliknya, mereka lebih suka berhubungan dan bekerja dengan orang-orang daripada sendirian.
Orang-orang dengan model ini juga memiliki empati yang tinggi terhadap orang lain, dan mudah melibatkan perasaan ketika menjalankan aktivitasnya. Mereka pada dasarnya orang yang penuh optimisme, antusias, dan cenderung memiliki sifat dasar yang riang. Meskipun demikian, mereka bukan orang tepat ketika harus mengerjakan tugas-tugas yang menuntut ketelitian tinggi seperti akuntansi dan keuangan. Pada sisi lain, mereka dapat menjadi best promotor untuk gagasan-gagasan baru.
Untuk memberikan motivasi bagi mereka, kita bisa melakukan hal-hal berikut:
• Berikan waktu anda untuk berinteraksi dan mendengarkan aspirasi mereka.
• Sediakan tugas dimana mereka memiliki kesempatan untuk membangun relasi dan berhubungan dengan orang lain dari beragam latar belakang
• Berikan bimbingan dan arahan yang jelas – termasuk deadline, sebab tanpa panduan ini mereka sering akan “ngelantur” dan tidak mampu menyelesaikan perkerjaan dengan tepat waktu.
• Berikan waktu anda untuk berinteraksi dan mendengarkan aspirasi mereka.
• Sediakan tugas dimana mereka memiliki kesempatan untuk membangun relasi dan berhubungan dengan orang lain dari beragam latar belakang
• Berikan bimbingan dan arahan yang jelas – termasuk deadline, sebab tanpa panduan ini mereka sering akan “ngelantur” dan tidak mampu menyelesaikan perkerjaan dengan tepat waktu.
Steadiness Style
Orang-orang dalam model ini cenderung introvert, reserve, dan quiet. Mereka adalah orang-orang yang lebih suka melakukan sesuatu secara sistematis, teratur dan bertahap. Mereka juga cendrung menyukai sesuatu yang berjalan dengan konsisten, dapat diprediksi dan lingkungan kerja yang stabil dan harmonis. Orang-orang dalam model ini juga tergolong pribadi yang sabar, dapat diandalkan dan cenderung memiliki loyalitas yang tinggi.
Orang-orang dalam model ini cenderung introvert, reserve, dan quiet. Mereka adalah orang-orang yang lebih suka melakukan sesuatu secara sistematis, teratur dan bertahap. Mereka juga cendrung menyukai sesuatu yang berjalan dengan konsisten, dapat diprediksi dan lingkungan kerja yang stabil dan harmonis. Orang-orang dalam model ini juga tergolong pribadi yang sabar, dapat diandalkan dan cenderung memiliki loyalitas yang tinggi.
Pada sisi lain, mereka termasuk golongan yang kurang menyukai perubahan yang radikal dan bersifat mendadak. Juga cenderung terpaku pada sistem yang sudah berjalan; dan karena itu kurang terdorong untuk melakukan inovasi yang bersifat radikal. Ketika mereka mengalami demotivasi, mereka cenderung akan menjadi orang yang kaku, resisten dan kemudian melakukan perlawanan secara pasif.
Untuk menciptakan iklim yang positif kepada orang-orang dengan model steadiness, kita bisa melakukan hal berikut:
• Berikan mereka kesempatan untuk bekerja sama dalam tim untuk mencapai hasil yang diinginkan.
• Berikan arahan-arahan yang spesifik dan sistematis
• Ketika melakukan perubahan, pastikan dengan prosedur yang sistematis, langkah-demi-langkah dan yakinkan bahwa kekhawatiran dan kecemasan mereka tidak akan terjadi. Mereka butuh rasa aman.
• Yakinkan mereka bahwa anda telah telah berpikir matang sebelum memutusakan perubahan. Berikan mereka kesempatan atau ruang untuk menyelesaikan masalah jika terjadi secara bertahap.
• Berikan mereka kesempatan untuk bekerja sama dalam tim untuk mencapai hasil yang diinginkan.
• Berikan arahan-arahan yang spesifik dan sistematis
• Ketika melakukan perubahan, pastikan dengan prosedur yang sistematis, langkah-demi-langkah dan yakinkan bahwa kekhawatiran dan kecemasan mereka tidak akan terjadi. Mereka butuh rasa aman.
• Yakinkan mereka bahwa anda telah telah berpikir matang sebelum memutusakan perubahan. Berikan mereka kesempatan atau ruang untuk menyelesaikan masalah jika terjadi secara bertahap.
Conscientiousness Style
Orang-orang dalam kategori ini termasuk pribadi yang menekankan akurasi dan ketelitian. Mereka cenderung menyukai sesuatu yang direncanakan dengan matang dan bersifat menyeluruh. Mereka juga cenderung suka dengan pekerjaan yang mengacu pada prosedur dan standar operasi yang baku. Orang-orang dalam kategori ini adalah pemikir yang kritis dan suka melakukan analisa untuk memastikan akurasi.
Orang-orang dalam kategori ini termasuk pribadi yang menekankan akurasi dan ketelitian. Mereka cenderung menyukai sesuatu yang direncanakan dengan matang dan bersifat menyeluruh. Mereka juga cenderung suka dengan pekerjaan yang mengacu pada prosedur dan standar operasi yang baku. Orang-orang dalam kategori ini adalah pemikir yang kritis dan suka melakukan analisa untuk memastikan akurasi.
Pada sisi lain, karena cenderung terfokus pada keteraturan, pribadi dalam model ini cenderung skeptis terhadap gagasan-gagasan baru yang radikal. Mereka juga agak enggan menerima proses perubahan yang mendadak. Ketika mereka termotivasi secara negative, mereka akan menjadi sinis atau sangat kritis.
Perlakuan yang optimal untuk orang-orang dalam model ini adalah sebagai berikut:
• Memberikan tugas dimana terdapat kesempatan bagi mereka untuk mendemonstrasikan keahlian mereka
• Memberikan tugas yang menuntut akurasi dan ketelitian
• Memberikan tugas yang membutuhkan perencanaan yang matang dan bersifat komprehensif
• Ketika memberikan instruksi, harus disertai dengan data dan argumen yang rasional dan disajikan secara sistematis.
• Memberikan tugas dimana terdapat kesempatan bagi mereka untuk mendemonstrasikan keahlian mereka
• Memberikan tugas yang menuntut akurasi dan ketelitian
• Memberikan tugas yang membutuhkan perencanaan yang matang dan bersifat komprehensif
• Ketika memberikan instruksi, harus disertai dengan data dan argumen yang rasional dan disajikan secara sistematis.
Demikianlah peta empat model kepribadian yang dapat kita eksplorasi. Dengan mengenali tipe kepribadian mitra/rekan kerja Anda, diharapkan Anda bisa membangun hubungan interpersonal yang lebih produktif nan lestari.
Cara ngebersihin Ramnit
1. Ini antivirus andalan saya. Hanya anda yang tau. Soalnya yang lain sih bayar. Hehe http://www.freerav.com/
2. Sebaiknya memang diinstal ulang saya computer anda sekalian tetapi setelah itu jangan diinstal driver dulu. Cara yang harus dilakukan adalah cara ke 3
3. Matikan autorun lewat start-run atau bisa dengan Win+R dan ketikan gpedit.msc . pada computer configuration-system klik 2x pada “Turn off autoplay” klik enable dan bawahnya klik pada All drive dan lakukan hal sama pada user configuration
4. Sementara matikan akses untuk System Volume Information dan Recycle setiap Harddrive. Caranya adalah klik tools Folder option pada tab view hilangi centang pada use simple file sharing dan klik ok, lalu klik kanan pada System Volume Information di drive C:\ kliksharing and security pada tab security klik advanced dan hilangkan centangan pada option dibawahnya. Klik ok. Jika ada peringatan klik ok saja. Dan ok dan selesai. Lakukan pada recycle dan pada drive anda yang lain
5. Buat folder Microsoft pada dua buah tempat yaitu di security c:\program files\ dan c:\program files\common files\ dan lakukan cara ke 4
6. Scan virus dengan antivirus andalan anda. Dan akan dtemui berbagai macam virus berjuta-juta. Jika tempat saya ada 6000 virus . . yang 3000 hanya file htm sih . . tp tetep aja ^&^*&
7. hapus file mecurigakan yang ada di drive kalian misal tryel.exe
8. Seharusnya sampai sini computer sudah aman. Jika tempat saya sih . .hehe
9. Sementara jangan mengkopi file yang sama dengan file yang sudah terinfeksi dfolder yang sama namanya. Seperti saya “D:\program files sudah terinfeksi semua” sekarang saya ganti install di “D:\programs files\” hehe
10. Semoga membantu
11. Jangan lupa kasih
jika suka tapi jangan di
saya cuman sharing aja. habis kesel sama virus ini.
virus
W32/Ramnit aka Win32.Siggen.8
Perhatian para pengguna komputer dalam beberapa bulan terakhir ini banyak tersita pada Stuxnet, Sality, Virut dan Shortcut. Termasuk perkembangan virus lokal yang secara tidak langsung menantang kreativitas programmer-programmer untuk memunculkan program antivirus lokal seperti Artav yang digawangi oleh anak SMP :). Perhatian user yang cukup besar terhadap virus lokal jangan sampaimengakibatkan lengah dengan keberadaan virus mancanegara, seperti salah satu virus yang sedang menyebar saat ini. Virus ini termasuk golongan trojan/backdoor, ia akan aktif jika komputer target terkoneksi internet dan salah satu senjata pamungkasnya yang berbahaya dan membuat pusing pengguna komputer adalah melakukan download virus lain. Hebatnya, nama dan jenis virus yang didownload akan berbeda-beda untuk setiap komputer target baik dari nama maupun ukurannya, hal inilah yang menyebabkan banyak program antivirus sekalipun kesulitan untuk melakukan deteksi dan pembersihan. Jika file tersebut berhasil di download, maka secara otomatis akan di aktifkan di komputer dan melakukan serangkaian kode jahat yang sudah ditanam didalam tubuhnya.
Secara umum virus ini cukup merepotkan, ia akan selalu melakukan koneksi ke internet untuk memanggil alamat website yang sudah ditentukan yang akan ditampilkan secara terus menerus sehingga mengakibatkan komputer menjadi lambat pada saat di akses, terlebih virus ini akan menginjeksi file yang mempunyai ekstensi EXE, DLL dan HTM/HTML baik berupa file program maupun file system Windows sehingga diperlukan langkah pembersihan khusus.
Ciri dan gejala
Berikut beberapa ciri dan gejala jika komputer terinfeksi virus W32/Ramnit (Win32.Siggen.8)
- Akan menampilkan aplikasi Internet Explorer yang berisi penawaran atau iklan investasi, game dan program-program promosi (terkadang menampilkan iklan porno) dalam jumlah yang banyak secara terus menerus selama komputer terkoneksi internet sehinggamenghabiskan banyak bandwidth untuk iklan yang ditampilkan dan mengakibatkan akses internet menjadi lambat (lihat gambar 1).
Gambar 1, Alamat website yang akan ditampilkan oleh W32/Ramnit (Win32.Siggen.8)
- Icon Removable media (USB Flash) berubah menjadi icon Folder (lihat gambar 2)
Gambar 2, Icon USB Flash yang diubah W32/Ramnit (Win32.Siggen.8 )
- User tidak dapat mengakses USB Flash dengan menampilkan pesan ”Access is denied” (lihat gambar 3)
Gambar 3, Blok akses USB Flash
- Muncul pesan “Compressed (zipped) Folders” pada saat mengakses Flash disk (lihat Gambar 4)
Gambar 4, Pesan error saat akses USB Flash
- Muncul banyak file dengan nama file “Copy of Shortcut to (1).lnk” s/d “Copy of Shortcut to (4).lnk” di USB Flash. (lihat gambar 5)
Gambar 5, File virus yang di drop oleh virus di USB Flash
- Salah satu hal yang unik dan membuat virus ini sangat mudah aktif dan sulit dibasmi adalah setiap kali user melakukan klik kanan, selain menampilkan menu klik kanan, secara tidak langsung pengguna komputer juga menjalankan virus ini.
Langganan:
Postingan (Atom)