DAFTAR
ISI
HALAMAN
JUDUL...................................................................................... i
KATA
PENGANTAR................................................................................... ii
DAFTAR
ISI.................................................................................................. iii
BAB I............................................................................................................... 1
PENDAHULUAN.......................................................................................... 1
A.
Latar Belakang..................................................................................... 1
B.
Rumusan Masalah................................................................................. 1
BAB II............................................................................................................. 2
PEMBAHASAN............................................................................................. 2
A.
Algoritma Paralel.................................................................................. 2
B.
Menyelesaikan
Sistem Persamaan Linear dengan Matriks................... 6
C.
Algoritma Genetika.............................................................................. 10
D.
Searching dan Optimasi Paralel dalam
Algoritma Genetika................. 11
E.
Kelebihan Algoritma
Genetika ( GA ) sebagai Metode Optimasi........ 12
BAB III............................................................................................................ 14
PENUTUP...................................................................................................... 14
A. Kesimpulan........................................................................................... 14
DAFTAR PUSTAKA.................................................................................... 15
BAB
I
PENDAHULUAN
A.
Latar
Belakang
Masalah
numerik merupakan salah satu masalah yang memerlukan kecepatan komputasi yang
sangat tinggi untuk dapat mengadaptasi suatu algoritma sekuensial ke dalam
algoritma paralel, maka terlebih dahulu harus dipelajari mengenai konsep
pemrosesan paralel dan bagaimana proses-proses dapat berlangsung secara
paralel.
Algoritma genetika merupakan suatu
metode yang menggunakan seleksi alam yang merupakan bagian utama dari prinsip
evolusi sebagai dasar pemikiran untuk menyelesaikan suatu permasalahan. Prinsip
ini dikemukakan oleh Charles Darwin, dimana tanpa menghiraukan prinsip dasar
penurunan sifat, Darwin mengemukakan penggabungan kualitas induk pada generasi
berikutnya, disamping itu bahwa individu yang mampu beradaptasi dengan
lingkungannya akan mempunyai kesempatan hidup yang lebih besar.
B.
Rumusan
Masalah
Berdasarkan Penjelasan Latar belakang di atas
di dalam Penulisan Makalah, akan kami angkat permasalahan, yang terdapat
mengenai isi di dalam makalah yang
tercantum di bawah ini :
1) Penjelasan
tentang Algoritma Paralel
2) Menyelesaikan
Sistem Persamaan Linear menggunakan metode Matriks
3) Penjelasan
tentang Algoritma Genetika
BAB II
PEMBAHASAN
A.
Algoritma
Paralel
Algoritma
paralel adalah algoritma untuk menyelesaikan masalah numerik, karena
masalah numerik merupakan salah satu masalah yang memerlukan kecepatan
komputasi yang sangat tinggi. Untuk dapat mengadaptasi suatu algoritma
sekuensial ke dalam algoritma paralel, terlebih dahulu harus dipelajari
mengenai konsep pemrosesan paralel dan bagaimana proses-proses dapat
berlangsung secara paralel.
Dalam
beberapa kasus, algoritma sekuensial dengan mudah dapat diadaptasi ke dalam
lingkungan paralel. Namun dalam kebanyakan kasus, problem komputasi harus
dianalisa ulang dan menghasilkan algoritma paralel yang baru. Terdapat beberapa
penelitian mengenai perancangan algoritma paralel untuk problem-problem praktis
seperti pengurutan, pemrosesan geraf, solusi untuk persamaan lanjar, solusi
untuk persamaan diferensial, dan untuk simulasi. Teknik pembangunan algoritma
paralel dapat dibedakan sebagai berikut :
1. Paralisme Data
Teknik
paralelisme data merupakan teknik yang paling banyak digunakan dalam program
paralel. Teknik ini lahir dari penelitian bahwa aplikasi utama komputasi
paralel adalah dalam bidang sain dan engineer, yang umumnya melibatkan array
multi-dimensi yang sangat besar. Dalam program sekuensial biasa, array ini
dimanipulasi dengan mempergunakan perulangan bersarang untuk mendapatkan hasil.
Kebanyakan program paralel dibentuk dengan mengatur ulang algoritma sekuensial
agar perulangan bersarang tersebut dapat dilaksanakan secara paralel.
Paralelisme data menunjukkan bahwa basis data dipergunakan sebagai dasar untuk
membentuk aktifitas paralel, dimana bagian yang berbeda dari basis data akan
diproses secara paralel. Dengan kata lain paralelisme dalam program ini dibentuk
dari penerapan operasi-operasi yang sama ke bagian array data yang berbeda.
Prinsip paralelisme data ini berlaku untuk pemrograman multiprosesor dan
multikomputer.
2. Partisi Data
Merupakan
teknik khusus dari Paralelisme Data, dimana data disebar ke dalam memori-memori
lokal multikomputer. Sebuah proses paralel kemudian ditugaskan untuk
mengoperasikan masingmasing bagian data. Proses tersebut harus terdapat dalam
lokal memori yang sama dengan bagian data, karena itu proses dapat mengakses
data tersebut secara lokal. Untuk memperoleh kinerja yang baik, setiap proses
harus memperhatikan variabel-variabel dan data-data lokalnya masing-masing.
Jika
suatu proses membutuhkan akses data yang terdapat dalam remote memori, maka hal
ini dapat dilakukan melalui jaringan message passing yang menghubungkan
prosesor-prosesor. Karena komunikasi antar prosesor ini menyebabkan terjadinya
waktu tunda, maka messsage passing ini sebaiknya dilakukan dalam frekuensi yang
relatif kecil. Dapat disimpulkan bahwa tujuan dari partisi data adalah untuk
mereduksi waktu tunda yang diakibatkan komunikasi messsage passing antar
prosesor. Algoritma paralel mengatur agar setiap proses dapat melakukan
komputasi dengan local data masing-masing.
3. Algoritma Relaksasi
Pada
algoritma ini, setiap proses tidak membutuhkan sinkronisasi dan komunikasi
antar proses. Meskipun prosesor mengakses data yang sama, setiap prosesor dapat
melakukan komputasi sendiri tanpa tergantung pada data antara yang dihasilkan
oleh proses lain. Contoh algoritma relaksasi adalah algoritma perkalian matrik,
pengurutan dengan mengunakan metode ranksort dan lain sebagainya.
4. Paralelisme Sinkron
Aplikasi
praktis dari komputasi paralel adalah untuk problem yang melibatkan array
multi-dimensi yang sangat besar. Problem tersebut mempunyai peluang yang baik
untuk paralelisme data karena elemen yang berbeda dalam array dapat diproses
secara paralel. Teknik komputasi numerik pada array ini biasanya iteratif, dan
setiap iterasi akan mempengaruhi iterasi berikutnya untuk menuju solusi akhir.
Misalnya saja untuk solusi persamaan numerik pada sistem yang besar. Umumnya,
setiap iterasi mempergunakan data yang dihasilkan oleh iterasi sebelumnya dan
program akhirnya menuju suatu solusi dengan akurasi yang dibutuhkan. Algoritma
iterasi ini mempunyai peluang paralelisme pada setiap iterasinya. Beberapa
proses parallel dapat dibentuk untuk bekerja pada array bagian yang berbeda.
Namun setelah setiap iterasi, prosesproses harus disinkronkan, karena hasil
yang diproduksi oleh satu proses dipergunakan oleh prosesproses lain pada
iterasi berikutnya. Teknik pemrograman paralel seperti ini disebut paralelisme
sinkron. Contohnya adalah perhitungan numerik pada Metode Eliminasi Gauss. Pada
paralelisme sinkron ini, struktur umum programnya biasanya terdiri dari
perulangan FORALL yang akan membentuk sejumlah besar proses paralel untuk
dioperasikan pada bagian array data yang berbeda. Setiap proses diulang dan
disinkronkan pada akhir iterasi. Tujuan dari sinkronisasi ini adalah untuk
meyakinkan bahwa seluruh proses telah menyelesaikan iterasi yang sedang
berlangsung, sebelum terdapat suatu proses yang memulai iterasi berikutnya.
5. Komputasi Pipeline
Pada
komputasi pipeline, data dialirkan melalui seluruh struktur proses, dimana
masing-masing proses membentuk tahap-tahap tertentu dari keseluruhan komputasi
. Algoritma ini dapat berjalan dengan baik pada multikomputer, karena adanya
aliran data dan tidak banyak memerlukan akses ke data bersama. Contoh komputasi
pipeline adalah teknik penyulihan mundur yang merupakan bagian dari metode
Eliminasi.
Dalam
merancang suatu algoritma paralel kita harus mempertimbangkan pula hal-hal yang
dapat mengurangi kinerja program paralel. Hal-hal tersebut adalah :
1.
Memory
Contention
Eksekusi prosesor tertunda ketika prosesor
menunggu hak ases ke sel memori yang sedang dipergunakan oleh prosesor lain.
Problem ini muncul pada arsitektur multiprosesor dengan memori bersama.
2. Excessive Seqential Code
Pada
beberapa algoritma paralel, akan terdapat kode sekuensial murni dimana tipe
tertentu dari operasi pusat dibentuk, seperti misalnya pada proses
inisialisasi. Dalam beberapa algoritma, kode sekuensial ini dapat mengurangi
keseluruhan speedup yang dapat dicapai. Process Creation Time Pembentukan
proses paralel akan membutuhkan waktu eksekusi. Jika proses yang dibentuk
relative berjalan dalam waktu yang relatif lebih singkat dibandingkan dengan
waktu pembentukan proses itu sendiri, maka overhead pembuatan akan lebih besar
dibandingkan dengan waktu eksekusi paralel algoritma. Communication Delay
Overhead ini muncul hanya pada multikomputer. Hal ini disebabkan karena
interaksi antar prosesor melalui jaringan komunikasi. Dalam beberapa kasus,
komunikasi antar dua prosesor mungkin melibatkan beberapa prosesor antara dalam
jaringan komunikasi. Jumlah waktu tunda komunikasi dapat menurunkan kinerja
beberapa algoritma paralel.
6. Synchronization Delay
Ketika
proses paralel disinkronkan, berarti bahwa suatu proses akan harus menunggu
proses lainnya. Dalam beberapa program paralel, jumlah waktu tunda ini dapat
menyebabkan bottleneck dan mengurangi speedup keseluruhan. Load Imbalance Dalam
beberapa program paralel, tugas komputasi dibangun secara dinamis dan tidak
dapat diperkirakan sebelumnya. Karena itu harus selalu ditugaskan ke
prosesor-prosesor sejalan dengan pembangunan tugas tersebut. Hal ini dapat
menyebabkan suatu prosesor tidak bekerja (idle), sementara prosesor lainnya
tidak dapat mengerjakan task yang ditugaskannya.
B. Menyelesaikan
Sistem Persamaan Linear dengan Matriks
1. Sistem Persamaan Linier dua Variabel
Salah satu diantara penggunaan invers matriks adalah untuk menyelesaikan
sistim persamaan linier. Tentu saja teknik penyelesaiannya dengan aturan persamaan matriks, yaitu :
Selain
dengan persamaan matriks, teknik menyelesaikan sistem persamaan linier juga
dapat dilakukan dengan determinan matriks. Aturan dengan cara ini adalah :
Untuk lebih jelasnya, ikutilah contoh soal berikut ini:
Tentukan himpunan penyelesaian sistem persamaan 2x –
3y = 8 dan x + 2y = –3 dengan metoda:
a)
Invers matriks
b)
Determinan
Jawab :
Jawab :
a)
Dengan metoda invers
matriks diperoleh :
b)
Dengan metode determinan matriks
diperoleh :
2) Sistem Persamaan Linier Tiga
Variabel.
Seperti halnya pada sistem persamaan
linier dua variabel, menyelesaikan sistem persamaan linier tiga variabel dengan
matriks juga terdiri dari dua cara, yakni dengan menggunakan determinan matriks
dan dengan menggunakan aturan invers perkalian matriks. Berikut ini akan
diuraikan masing masing cara tersebut.
Aturan menyelesaikan sistem persamaan
linier menggunakan determinan matriks adalah dengan menentukan terlebih dahulu
matriks koefisien dari sistem persamaan itu. Selanjutnya ditentukan empat nilai
determinan sebagai berikut:
a. D
yakni determinan matriks koefisien
b. Dx
yakni determinan matriks koefisien dengan koefisien x diganti konstanta
c. Dy
yakni determinan matriks koefisien dengan koefisien y diganti konstanta
d. Dz
yakni determinan matriks koefisien dengan koefisien z diganti konstanta
Rumus
masing-masingnya adalah sebagai berikut:
Untuk
lebih jelasnya, ikutilah contoh soal berikut ini:
Tentukanlah
himpunan penyelesaian sistem persamaan linier dibawah ini dengan menggunakan
metoda determinan
2x
– 3y + 2z = –3
x
+ 2y + z = 2
2x
– y + 3z = 1
Jawab
:
D
= (2)(2)(3) + (–3)(1)(2) + (2)(1)(–1) – (2)(2)(2) – (2)(1)(–1) – (–3)(1)(3)
D
= 12 – 6 – 2 – 8 + 2 + 9
D
= 7
Dx
= (–3)(2)(3) + (–3)(1)(1) + (2)(2)(–1) – (2)(2)(1) – (–3)(1)(–1) –
(–3)(2)(3)
Dx
= –18 – 3 – 4 – 4 – 3 + 18
Dx
= –14
Dy
= (2)(2)(3) + (–3)(1)(2) + (2)(1)(1) – (2)(2)(2) – (2)(1)(1) – (–3)(1)(3)
Dy
= 12 – 6 + 2 – 8 – 2 + 9
Dy
= 7
Dz
= (2)(2)(1) + (–3)(2)(2) + (–3)(1)(–1) – (–3)(2)(2) – (2)(2)(–1) –
(–3)(1)(1)
Dz
= 4 – 12 + 3 + 12 + 4 + 3
Dz
= 14
C.
Algoritma
Genetika
Algoritma genetika adalah suatu
algoritma pencarian yang berbasis pada mekanisme seleksi alam dan genetika.
Algoritma genetika merupakan salah satu algoritma yang sangat tepat digunakan
dalam menyelesaikan masalah optimasi kompleks, yang sulit dilakukan oleh metode
konvernsional.
Algoritma genetika bekerja dengan
suatu populasi string dan melakukan proses pencarian nilai optimal secara
parallel, dengan mengunakan operator genetika. Algoritma genetika akan
melakukan rekombinasi antar individu. Algoritma genetika memiliki elemen dasar
berupa string yang tersusun dari rangkaian substring (gen), yang masing-masing
merupakan kode dari parameter dalam ruang solusi dimana suatu string (kromosom)
menyatakan kandidat solusi. Kumpulan string dalam populasi berkembang dari
generasi ke generasi melalui operator genetika. Pada setiap iterasi,
individu-individu (kromosom) dalam populasi itu akan dievolusi dan diseleksi
untuk menentukan populasi pada generasi berikutnya. Populasi ini akan terus berulang
sampai menemukan suatu parameter dengan
nilai yang paling optimal sesuai dengan yang diinginkan.
Algoritma genetika (Genetic
Algorithms, GA) merupakan tipe EA yang paling popular. Algoritma genetika
berkembang seiring dengan perkembangan teknologi informasi yang sangat pesat.
Karena kemampuannya untuk menyelesaikan berbagai masalah kompleks, algoritma
ini banyak digunakan dalam bidang fisika, biologi, ekonomi, sosiologi dan
lain-lain yang sering menghadapi masalah optimasi yang model matematikanya kompleks
atau bahkan sulit dibangun.
Generasi ini akan merepresentasikan
perbaikan-perbaikan pada populasi awalnya. Dengan melakukan proses ini secara
berulang, algoritma ini diharapkan dapat mensimulasikan proses evolusioner.
Pada akhirnya, akan didapatkan solusi-solusi yang paling tepat bagi
permasalahan yang dihadapi. Untuk menggunakan algoritma genetika, solusi
permasalahan direpresentasikan sebagai khromosom.
Tiga aspek yang penting untuk
penggunaan algoritma genetika:
1. Defenisi fungsi fitness
2. Defenisi dan implementasi representasi
genetika
3. Defenisi dan implementasi operasi genetika
Jika ketiga aspek di
atas telah didefinisikan, algoritma genetika akan bekerja dengan baik. Tentu
saja, algoritma genetika bukanlah solusi terbaik untuk memecahkan segala
masalah. Sebagai contoh, metode tradisional telah diatur untuk untuk mencari
penyelesaian dari fungsi analitis convex yang “berperilaku baik” yang
variabelnya sedikit. Pada kasus-kasus ini, metode berbasis kalkulus lebih
unggul dari algoritma genetika karena metode ini dengan cepat menemukan solusi
minimum ketika algoritma genetika masih menganalisa bobot dari populasi awal.
Untuk problem-problem ini pengguna
harus mengakui fakta dari pengalaman ini dan memakai metode tradisional yang
lebih cepat tersebut. Akan tetapi, banyak persoalan realistis yang berada di
luar golongan ini. Selain itu, untuk persoalan yang tidak terlalu rumit, banyak
cara yang lebih cepat dari algoritma genetika. Jumlah besar dari populasi
solusi, yang merupakan keunggulan dari algoritma genetika, juga harus mengakui
kekurangannya dalam dalam kecepatan pada sekumpulan komputer yang dipasang
secara seri-fitness function dari tiap solusi harus dievaluasi. Namun, bila
tersedia komputerkomputer yang paralel, tiap prosesor dapat mengevaluasi fungsi
yang terpisah pada saat yang bersamaan. Karena itulah, algoritma genetika
sangat cocok untuk perhitungan yang paralel.
D. Searching dan Optimasi Paralel
dalam Algoritma Genetika
Dalam bidang
industri manufaktur, GA digunakan untuk perencanaan dan penjadwalan produksi.
GA juga bisa diterapkan untuk kompresi citra, optimasi penugasan mengajar bagi
dosen, penjadwalan dan alokasi ruang ujian, optimasi penjadwalan kuliah,
optimasi multi travelling salesman problem (M-TSP), dan penyusunan rute dan
jadwal kunjungan wisata yang efisien. Algoritma genetika diilhami oleh ilmu
genetika, karena itu istilah yang digunakan dalam algoritma genetika banyak
diadopsi dari ilmu tersebut.
Apabila
dibandingkan dengan prosedur pencarian dan optimasi biasa, algoritma genetika
berbeda dalam beberapa hal sebagai berikut :
·
Manipulasi dilakukan
terhadap kode dari himpunan parameter (biasa disebut chromosome), tidak secara
langsung terhadap parameternya sendiri.
·
Proses pencarian
dilakukan dari beberapa titik dalam satu populasi, tidak dari satu titik saja.
·
Proses pencarian
menggunakan informasi dari fungsi tujuan.
·
Pencariannya
menggunakan stochastic operators yang bersifat probabilistik, tidak menggunakan
aturan deterministik.
E. Kelebihan Algoritma
Genetika ( GA ) sebagai Metode Optimasi
·
GA merupakan algoritma
yang berbasis populasi yang memungkinkan digunakan pada optimasi masalah dengan
ruang pencarian (search space) yang sangat luas dan kompleks. Properti ini juga
memungkinkan GAs untuk melompat keluar dari daerah optimum lokal.
·
Individu yang ada pada
populasi bisa diletakkan pada beberapa sub-populasi yang diproses pada sejumlah
komputer secara paralel. Hal ini bisa mengurangi waktu komputasi pada masalah
yang sangat kompleks. Penggunaan sub-populasi juga bisa dilakukan pada hanya
satu komputer untuk menjaga keragaman populasi & meningkatkan kualitas
hasil pencarian.
·
GA menghasilkan
himpunan solusi optimal yang sangat berguna pada peyelesaian masalah dengan
banyak obyektif.
·
GA dapat menyelesaikan
masalah kompleks dengan banyak variabel (kontinyu, diskrit atau campuran
keduanya).
·
GA menggunakan
chromosome untuk mengkodekan solusi sehingga bisa melakukan pencarian tanpa
memperhatikan informasi derivatif yang spesifik dari masalah yang diselesaikan.
·
GA bisa
diimplementasikan pada bermacam data seperti data yang dibangkitkan secara
numerik atau dengan fungsi analitis.
·
GA cukup fleksibel
untuk dihibridisasikan dengan algoritma lainnya. Beberapa penelitian
membuktikan, hybrid GA (HGA) sangat efektif untuk menghasilkan solusi yang
lebih baik.
·
GA bersifat ergodic,
sembarang solusi bisa diperoleh dari solusi yang lain dengan hanya beberapa
langkah. Hal ini memungkinkan eksplorasi pada daerah pencarian yang sangat
luas, yang dapat dilakukan dengan lebih cepat dan mudah.
BAB
III
PENUTUP
A.
Kesimpulan
Jadi Algoritma paralel
itu merupakan suatu uruta-urutan logis dari suatu pernyataan yang ditekankan
pada manipulasi elemen data yang dimiliki oleh satu atau lebih dari satu proses
secara bersamaan dalam rangka menyelesaikan sebuah masalah yang biasanya
dieksekusi dengan asumsi satu instruksi pada suatu waktu yamg dimana
menggunakan komputer parallel yang memiliki banyak prosesor (multi prosesor)
dan memiliki kemampuan pengolahan/pemrosesan parallel serta melakukan proses
running time untuk suatu penilaian algoritma dalam analisa algoritma pengolahan
parallel dimana waktu yang digunakan oleh sebuah algoritma untuk menyelesaikan
masalah pada sebuah komputer parallel dihitung dari saat algoritma mulai hingga
saat algoritma berhenti.
Sedangkan algoritma
genetika bekerja dengan suatu populasi string dan melakukan proses pencarian
nilai optimal secara parallel, dengan mengunakan operator genetika. Algoritma
genetika akan melakukan rekombinasi antar individu. Algoritma genetika memiliki
elemen dasar berupa string yang tersusun dari rangkaian substring (gen), yang
masing-masing merupakan kode dari parameter dalam ruang solusi dimana suatu
string (kromosom) menyatakan kandidat solusi. Kumpulan string dalam populasi
berkembang dari generasi ke generasi melalui operator genetika. Pada setiap
iterasi, individu-individu (kromosom) dalam populasi itu akan dievolusi dan
diseleksi untuk menentukan populasi pada generasi berikutnya. Populasi ini akan
terus berulang sampai menemukan suatu
parameter dengan nilai yang paling optimal sesuai dengan yang
diinginkan.
DAFTAR
PUSTAKA
Tidak ada komentar:
Posting Komentar