BAB II TINJAUAN PUSTAKA

BAB II TINJAUAN PUSTAKA 2.1

Pemotongan Logam Proses pemotongan logam merupakan suatu proses yang digunakan untuk mengubah bentuk suatu produk dari logam (komponen mesin) dengan cara memotong. Proses pemesinan dengan menggunakan prinsip pemotongan logam dibagi dalam tiga kelompok dasar, yaitu : proses pemotongan dengan mesin pres, proses pemotongan konvensional dengan mesin perkakas, dan proses pemotongan non konvensional. Proses pemotongan dengan menggunakan

mesin pres meliputi

pengguntingan (shearing), pengepresan (pressing) dan penarikan (drawing, elongating). Proses pemotongan konvensional dengan mesin perkakas meliputi proses bubut (turning), proses frais (milling), dan sekrap (shaping). Proses pemotongan non konvensional contohnya dengan mesin EDM (Electrical Discharge Machining) dan wire cutting. Proses pemotongan logam ini biasanya disebut proses pemesinan, yang dilakukan dengan cara membuang bagian benda kerja yang tidak digunakan menjadi beram (chips), sehingga terbentuk benda kerja. Dari semua prinsip pemotongan di atas pada buku ini akan dibahas tentang proses pemesinan dengan menggunakan mesin perkakas [11]. Proses permesinan (Machining process) merupakan proses pembentukan suatu produk dengan pemotongan dan menggunakan mesin perkakas. Umumnya, benda kerja yang di gunakan berasal dari proses sebelumnya,

seperti

proses

penuangan

(Casting)

dan

proses

pembentukan (Metal Forging). Proses permesinan ini berdasarkan bentuk alat potong dapat di bagi menjadi 2 tipe, yaitu : 1. Bermata potong tunggal (single point cutting tools) 2. Bermata potong jamak (multiple points cuttings tools) Secara umum, gerakan pahat pada proses permesinan terdapat 2 tipe yaitu : gerak makan (feeding movement) dan gerak potong (cutting movements). Sehingga berdasarkan proses gerak potong dan gerak 4 Universitas Sumatera Utara

makannya, proses pemesinan pemesinan dapat di bagi menjadi beberapa tipe, antara

lain : •

Proses Bubut (Turning)

•

Proses Sekrap (Shaping)

•

Proses Freis (Milling)

•

Proses Gurdi (Drilling)

•

Proses Bor (Boring)

•

Proses Kikir (Filling)

•

Proses Gergaji atau parut (Sawing, Broaching)

Tabel 2.1 klasifikasi proses pemesinan pemesinan menurut jenis gerakan relatif pahat/perkakas potong terhadap benda kerja,

Proses pemesinan adalah proses yang paling banyak dilakukan untuk menghasilkan suatu produk jadi yang berbahan baku logam. Diperkirakan sekitar 60% sampai 80% dari seluruh proses pembuatan komponen mesin yang komplit dilakukan dengan proses pemesinan [11] 5 Universitas Sumatera Utara

2.2

Pengertian Optimasi Optimasi adalah suatu proses untuk mencapai hasil ideal atau optimal (nilai efektif yang dapat dicapai), optimasi merujuk pada studi permasalahan yang mencoba untuk mencari nilai minimum dan maksimum yang akan memberikan solusi optimal. (Wikipedia : Optimasi 2007)

2.2.1

Metode Optimasi Metode

mencari

nilai

optimum

dikenal

sebagai

teknik

mathematical programming dan bisa di pelajari sebagai riset operasi. Riset operasi adalah cabang matematika yang berkaitan dengan penerapan metode ilmiah pengambilan keputusan dan penerapan metode ilmiah dan teknik pengambilan keputusan dan penetapan penyelesaian terbaik

atau

optimal.

Perkembangan

metode optimasi

semakin

mengalami kemajuan hingga masa modern sekarang, hal ini dilihat dengan semakin banyak metode optimasi yang popular dan banyak dipakai antara lain seperti dynamic programming, integer programming, game theory, dan metode optimasi modern. [2]

2.2.2

Metode Optimasi Modern Metode optimasi modern juga disebut metode optimasi yang

ampuh dan populer untuk menyelesaikan masalah teknik optimasi yang komplek. Metode yang tergolong dalam metode optimasi modern adalah:

2.3

•

Algoritma genetika (Genetic Algorithm)

•

Optimasi partikel swarm (Particle Swarm Optimization)

•

Optimasi koloni semut (Ant Colony Optimization)

•

Optimasi berbasis jaringan syaraf tiruan

•

Optimasi fuzzy (Fuzzy Optimization), dan

•

Simulasi Penguatan (Simulated annealing)

Mesin sekrap (shaping) Mesin sekrap (Shaping) adalah mesin perkakas yang mempunyai gerak utama bolak-balik horizontal dan berfungsi untuk merubah bentuk dan ukuran benda kerja sesuai dengan yang dikehendaki. Pahat bekerja 6 Universitas Sumatera Utara

pada saat gerakan maju, dengan gerakan ini dihasilkan pekerjaan meratakan bidang, membuat alur, membuat bidang bersudut atau bertingkat dan membentuk bidang-bidang yang tidak beraturan.Prinsip kerja mesin sekrap adalah gerakan berputar dari motor diubah menjadi gerak lurus/gerak bolak-balik melalui blok geser dan lengan penggerak. Possisi langkah dapat diatur dengan spindle posisi dan untuk mengatur panjang langkah dengan bantuan blok geser. [13]

2.3.1

Jenis – Jenis Pemesinan Mesin Sekrap Mesin Sekrap adalah mesin yang relatif sederhana. Biasanya

digunakan dalam ruang alat atau untuk mengerjakan benda kerja yang jumlahnya satu atau dua buah untuk prototype (benda contoh). Pahat yang digunakan sama dengan pahat bubut. Proses sekrap tidak terlalu memerlukan perhatian/konsentrasi bagi operatornya ketika melakukan penyayatan. Mesin Sekrap yang sering digunakan adalah Mesin Sekrap horizontal. Selain itu, ada Mesin Sekrap vertical yang biasanya dinamakan mesin slotting/slotter. Proses sekrap ada dua macam yaitu proses sekrap (shaper) dan planner. Proses sekrap dilakukan untuk benda kerja yang relatif kecil, sedang proses planner untuk benda kerja yang besar. [11]

Jenis mesin sekrap

yang umum digunakan adalah sebagai

berikut: 1. Mesin Sekrap Datar atau Horizontal (Shaper) Mesin jenis ini umum dipakai untuk produksi dan pekerjaan serbaguna terdiri atas rangka dasar dan rangka yang mendukung lengan horizontal. Benda kerja didukung pada rel silang sehingga memungkinkan benda kerja untuk digerakkan ke arah menyilang atau vertikal dengan tangan atau penggerak daya.Pada mesin ini pahat melakukan gerakan bolak-balik, sedangkan benda kerja melakukan gerakan ingsutan. Panjang langkah maksimum sampai 1.000 mm, cocok untuk benda pendek dan tidak terlalu berat.

7 Universitas Sumatera Utara

Gambar 2.1 Mesin Sekrap Datar atau Horizontal (Shaper) (Sumber: Laboratorium Teknologi Mekanik dan Laboratorium Ilmu Logam Fisik Universitas Sumatera Utara, 2013)

2. Mesin Sekrap Vertikal (Slotter) Mesin sekrap jenis ini digunakan untuk pemotongan dalam, menyerut dan bersudut serta untuk pengerjaan permukaan-permukaan yang sukar dijangkau. Selain itu mesin ini juga bisa digunakan untuk operasi yang memerlukan pemotongan vertikal. Gerakan pahat dari mesin

ini naik turun secara vertikal, sedangkan benda kerja bisa

bergeser kearah memanjang dan melintang. Mesin jenis ini juga dilengkapi dengan meja putar, sehingga dengan mesin ini bisa dilakukan pengerjaan pembagian bidang yang sama besar.

Gambar 2.2 Mesin Sekrap Vertikal (Slotter) (Sumber: http://google/indoteknik.com, 2013)

3. Mesin Sekrap Planner Digunakan untuk mengerjakan benda kerja yang panjang dan besar (berat). Benda kerja dipasang pada eretan yang melakukan gerak bolak-balik, sedangkan pahat membuat gerakan ingsutan dan gerak 8 Universitas Sumatera Utara

penyetelan. Lebar benda ditentukan oleh jarak antartiang mesin. Panjang langkah mesin jenis ini ada yang mencapai 200 sampai 1.000 mm.

Gambar 2.3 Mesin Sekrap Planner (Sumber: http://google/indoteknik.com, 2013)

2.3.2

Mekanisme Kerja Mesin Sekrap Mekanisme yang mengendalikan Mesin Sekrap ada dua macam

yaitu mekanik dan hidrolik. Pada mekanisme mekanik digunakan crank mechanism (Gambar 2.25). Pada mekanisme ini roda gigi utama (bull gear) digerakkan oleh sebuah pinion yang disambung pada poros motor listrik melalui gear box dengan empat, delapan, atau lebih variasi kecepatan. RPM dari roda gigi utama tersebut menjadi langkah per menit (strokes per minute, SPM). Gambar s kematik mekanisme dengan sistem hidrolik dapat dilihat pada Gambar 2.25. Mesin dengan mekanisme system hidrolik kecepatan sayatnya dapat diukur tanpa bertingkat, tetap sama sepanjang langkahnya. Pada tiap saat dari langkah kerja, langkahnya dapat dibalikkan sehingga jika mesin macet lengannya dapat ditarik kembali. Kerugiannya yaitu penyetelen panjang langkah tidak teliti.

Gambar 2.4 Mekanisme Mesin Sekrap 9 Universitas Sumatera Utara

2.3.3

Bagian Utama Mesin Sekrap

Mesin sekrap terdiri atas beberapa bagian seperti di bawah ini

Gambar 2.5 Bagian Utama Mesin Sekrap [11]

Keterangan: 1.Badan mesin Merupakan keseluruhan mesin tempat mekanik penggerak dan tuas pengatur. 2) Meja mesin Fungsinya merupakan tempat kedudukan benda kerja atau penjepit benda kerja. Meja mesin didukung dan digerakkan oleh eretan lintang dan eretan tegak. Eretan lintang dapat diatur otomatis.

3) Lengan Fungsinya untuk menggerakan pahat maju mundur. Lengan diikat dengan engkol menggunakan pengikat lengan. Kedudukan lengan di atas badan dan dijepit pelindung lengan agar gerakannya lurus. 4) Eretan pahat Fungsinya untuk mengatur ketebalan ketebalan pemakanan pahat.Dengan memutar roda pemutar maka pahat akan turun atau naik. Ketebalan pamakanan dapat dibaca pada dial. Eretan pahat terpasang di bagian ujung lengan dengan ditumpu oleh dua buah mur baut pengikat. Eretan

dapat dimiringkan untuk penyekrapan penyekrapan bidang bersudut atau miring. Kemiringan eretan dapat dibaca pada pengukur sudut eretan. 5) Pengatur kecepatan Fungsinya untuk mengatur atau memilih jumlah langkah lengan mesin per menit. Untuk pemakanan tipis dapat dipercepat. Pengaturan harus pada saat mesin berhenti. 10 Universitas Sumatera Utara

6) Tuas panjang langkah Berfungsi mengatur panjang pendeknya langkah pahat atau lengan sesuai panjang benda yang disekrap.Pengaturan dengan memutar tap ke arah kanan atau kiri. 7) Tuas posisi pahat Tuas ini terletak pada lengan mesin dan berfungsi untuk mengatur kedudukan pahat terhadap benda kerja. Pengaturan dapat dilakukan setelah mengendorkan pengikat lengan. 8) Tuas pengatur gerakan otomatis meja melintang Untuk menyekrap secara otomatis diperlukan pengaturanpengaturan panjang engkol yang mengubah gerakan putar mesin pada roda gigi menjadi gerakanlurus meja. Dengan demikian meja melakukan gerak ingsutan (feeding).

2.3.4

Bentuk Pahat Sekrap Pahat sekrap terdiri dari beberapa macam sesuai dengan

kegunaannya, seperti terlihat pada gambar di bawah ini:


(h)

(i)

(j)

Gambar 2.6 Bentuk Pahat Sekrap [11]

Keterangan: a) pahat sekrap kasar lurus b) pahat sekrap kasar lengkung c) pahat sekrap d) pahat sekrap runcing e) pahat sekrap sisi f) pahat sekrap sisi kasar g) pahat sekrap sisi datar h) pahat sekrap profil i) pahat sekrap masuk ke dalam atau pahat sekrap masuk ke luar lurus. j) pahat sekrap masuk dalam atau pahat sekrap masuk ke luar diteruskan.

2.3.5

Sudut asah Pahat

Gambar 2.7 Sudut asah Sekrap


Keterangan: α = sudut bebas β = sudut mata potong (baji) γ = sudut buang ᵟ = sudut potong (α + β) 2.3.6

Jenis bahan Pahat

Terdapat dua jenis bahan pahat seperti terlihat di bawah

Gambar 2.8 jenis bahan pahat

a) H.S.S (High Speed Steel) digunakan untuk memotong material yang mempunyai tegangan tarik tinggi. b) Carbide digunakan untuk benda – benda tuangan.

2.3.7

Elemen Dasar dan Perencanaan Proses Sekrap Elemen pemesinan dapat dihitung dengan rumus-rumus yang

identik dengan elemen pemesinan proses pemesinan yang lain. 2.3.7.1 Kecepatan potong (Cutting Speed): Kecepatan potong biasanya dinyatakan dalam isitilah m/menit, yaitu kecepatan dimana pahat melintasi benda kerja untuk mendapatkan hasil yang paling baik pada kecepatan yang sesuai. Kecepatan potong dipengaruhi oleh dua faktor, yaitu: kekerasan dari bahan yang akan dipotong dan jenis alat potong yang digunakan. Untuk keperluan ini digunakan persamaan sebagai berikut:

=

(m/menit) atau np =

Dimana:

………...(2.1)

= Kecepatan Potong (m/menit) np

= Jumlah langkah per menit (langkah/menit)

L

= Panjang langkah pemesinan (mm) 13 Universitas Sumatera Utara

Berikut ini adalah tabel mengenai kecepatan potong beberapa bahan logam.

Tabel 2.2 Kecepatan potong beberapa logam

No.

Nama Bahan

Kecepatan Potong (m/menit)

1.

Baja Lunak

24-30

2.

Baja perkakas

12-18

3.

Besi Tuang abu-abu

18-24

4.

Kuningan keras

20-45

5.

Kuningan lunak

60

6.

Tembaga

60

7.

Alumunium

300

(Sumber: George Love dan Harus A.R. 1986:190)

2.3.7.2 Kecepatan Pemakanan

Kecepatan pemakanan adalah pergerakan titik sayat alat potong per satu putaran benda kerja. Dalam proses sekrap, kecepatan pemakanan dinyatakan dalam mm/min dan dapat di hitung dengan menggunakan persamaan berikut: f= f x np …………………… (2.2) f

Dimana :

= kecepatan makan (m/menit)

f

= gerak makan (mm/langkah)

np

= Jumlah langkah per menit (langkah/menit)

2.3.7.3 Waktu Pemotongan (Cutting Time):

Cutting time adalah waktu pemotongan dalam pemesinan mesin sekrap, yang dapat diukur dengan persamaan : tc = w / ν f

……………………………………………………. (2.3)


Dimana :

2.3.8

tc

= Kecepatan makan (menit)

w

= lebar pemotongan benda kerja (mm)

Proses Sekrap

1) Menjalankan mesin -

Lengan digerakkan dengan cara memutar roda pemeriksa untuk melihat kemungkinan tertabraknya lengan

-

-

-

-

Menentukan banyak langkah per menit Motor mesin dihidupkan Dengan cara memasukkan tuas kopling mesin mulai bekerja Mencoba langkah pemakanan (feeding) dari meja, mulai dari langkah halus sampai langkah kasar Perhatikan seluruh gerak mesin Menghentikan kerja mesin dilakukan dengan cara melepas tuas kopling kemudian matikan motor.

2. Proses penyekrapan -

Penyekrapan datar Penyekrapan bidang rata adalah penyekrapan benda kerja agar menghasilkan permukaan yang rata. Penyekrapan bidang rata dapat dilakukan dengan cara mendatar (horizontal) dan cara tegak (Vertical). Pada penyekrapan arah mendatar yang bergerak adalah benda kerja atau meja ke arah kiri kanan. Pahat melakukan langkah penyayatan dan ketebalan diatur dengan menggeser eretan pahat.

-

Penyekrapan tegak Pada penyekrapan tegak, yang bergerak adalah eretan pahat naik turun. Pengaturan ketebalan dilakukan dengan menggeser meja. Pahat harus diatur sedemikian rupa (menyudut) sehingga hanya bagian ujung saja yang menyayat dan bagian sisi dalam keadaan bebas. Tebal pemakanan di atur tipis ± 50 mm.


Langkah kerja penyekrapan tegak sesuai dengan penyekrapan yang datar. (1) Kedalaman pemotongan dilakukan oleh gerakan meja (2) Feeding dilakukan oleh gerakan eretan alat potong. -

Penyekrapan menyudut Penyekrapan bidang menyudut adalah penyekrapan benda kerja agar menghasilkan permukaan yang miring/sudut. Pada penyekrapan ini yang bergerak adalah eretan pahat maju mundur.

Pengaturan

ketebalan

dilakukan

dengan

memutar

eretenpahat sesuai dengan kebutuhan sudut pemakanan : (1) Kedalaman pemotongan dilakukan oleh gerakan meja (2) Feeding dilakukan oleh eretan alat pemotong. -

Penyekrapan alur Menurut alur penyekrapan, Mesin Sekrap dapat digunakan untuk membuat alur : (1) Alur terus luar (2) Alur terus dalam (3) Alur buntu (4) Alur tembus. Alur terus luar di antaranya adalah alur “U”, alur “V”, dan alur ekor burung.

Gambar 2.9 Penyekrapan Alur Terus Luar


2.4

Algoritma Genetika 2.4.1

Pengenalan Algoritma Genetika Algoritma genetik pertama kali diperkenalkan oleh John Holland

dari Universitas Michigan pada tahun 1975. John Holland bersama murid-murid serta rekan kerjanya lalu mempublikasikan tulisannya berjudul “Adapted in Natural and Artificial System”. Dalam tulisan tersebut dijelaskan bahwa algoritma genetik sangat cocok digunakan untuk memecahkan masalah optimasi kompleks dan juga untuk aplikasi yang membutuhkan pemecahan masalah adaptif. Sehingga dengan beberapa keunggulan tersebut, algoritma genetik diterima pada berbagai kalangan dan telah diaplikasikan pada berbagai bidang

Algoritma genetik merupakan metode pencarian stokastik yang diilhami oleh proses biologi yang dapat diterapkan pada sebagian besar permasalahan. Algoritma genetik memodelkan mekanisme seleksi alam dan proses genetik untuk menuntun suatu pencarian seperti cara-cara alam dalam menyelesaikan permasalahan adaptasi organisme untuk mempertahankan kelangsungan hidupnya.

Algoritma genetika banyak diaplikasikan untuk berbagai macam permasalahan, seperti: permasalah

optimasi, pemrograman otomatis,

machine learning, model ekonomi, model sistem imunisasi, dan model ekologis. Algoritma genetika juga sangat berguna dan efisien untuk mengatasi

masalah dengan karakteristik sebagai berikut : Ruang

masalah sangat besar, kompleks, dan sulit dipahami, tidak tersedianya analisis matematika yang memadai, ketika metode-metode konvensional sudah tidak mampu menyelesaikan masalah yang dihadapi, solusi yang diharapkan tidak harus paling optimal, tetapi cukup “bagus” atau bisa diterima, terdapat batasan waktu, misalnya dalam real time system atau sistem waktu nyata.

Algoritma genetik memiliki perbedaan yang mendasar dengan metode pencarian solusi optimal berbasis model matematika kalkulus, perbedaan tersebut adalah sebagai berikut : 17 Universitas Sumatera Utara

1. Mekanisme optimasi algoritma genetik bekerja berdasarkan kromosom, dimana setiap kromosom menyimpan informasi parameter-parameter tersebut. 2. Proses pencarian solusi optimal pada mekanisme algoritma genetik tidak dilakukan pada satu titik pencarian, tetapi pada sekumpulan titik pencarian. 3. Algoritma genetik tidak membutuhkan prosedurprosedur matematis dalam mencari solusi optimal tetapi algoritma genetik menggunakan informasi langsung dari hasil transfer tiap-tiap parameternya ke suatu fungsi yang dapat mewakili tujuan dari proses optimasi yang sedang dilakukan. 4. Mekanisme genetik digunakan dalam pemrosesan kode parameter suatu permasalahan, melalui proses seleksi, rekombinasi dan mutasi untuk memperoleh solusi optimal. 5. Proses pencarian solusi optimal menggunakan metode algoritma genetik menggunakan titik acuan sembarang, untuk menghindari solusi optimal lokal. 6. pencarian terbimbing diberikan melalui penilaian terhadap kualitas kode atau kromosom yang dimiliki oleh setiap individu dalam suatu generasi.

2.4.2

Aplikasi Algoritma Genetika Algoritma genetika telah digunakan untuk memecahkan masalah

dibidang teknik, bisnis, dan hiburan, termasuk: 1. Optimasi: algoritma genetika banyak digunakan dalam berbagai tugas optimasi, termasuk optimasi numerik dan masalah-masalah optimasi kombinatorial seperti TPS (traveling salesman problem), job shop scheduling, dan desain sirkuit. 2. Pemrograman otomatis: algoritma genetika telah digunakan untuk berevolusi terhadap program komputer untuk melakukan tugas-tugas yang spesifik dan merancang struktur komputasi lain. 3. Machine Learning: algoritma genetika banyak digunakan untuk aplikasi mesin-learning, termasuk klasifikasi dan prediksi struktur protein. Algoritma genetika juga telah digunakan untuk merancang jaringan syaraf tiruan dan untuk mengendalikan robot. 18 Universitas Sumatera Utara

4. Model Ekonomi: algoritma genetikatelah digunakan untuk memodelkan proses inovasi, pengembangan strategi penawaran, dan munculnya pasar ekonomi. 5. Model sistem imunisasi: algoritma genetika telah digunakan untuk memodelkan beberapa aspeksistem kekebalan tubuh alami, termasuk mutasi somatik selama masa hidup individu dan menemukan keluarga dengan gen ganda selama evolusi. 6. Model ekologi: algoritma genetikatelah digunakan untuk memodelkan fenomena ekologi seperti hosp-parasite co-evolution, dan arus sumber daya dalam ekologi. 7. Interaksi antara evolusi dan pembelajaran: algoritma genetika telah banyak digunakan untuk mempelajari bagaimana individu belajar dan memengaruhi proses evolusi suatu spesies satu sama lain.

2.4.3

Struktur Umum Algoritma Genetika Pada algortima genetika ini, teknik pencarian dilakukan sekaligus

atas sejumlah solusi yang mungkin dikenal dengan istilah populasi. Individu yang terdapat dalam suatu populasi disebut dengan istilah kromosom. Kromosom ini merupakan suatu solusi yang masih berbentuk simbol. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil evolusi kromosom-kromosom melalui iterasi yang disebut istilah generasi. Pada setiap generasi, kromosom akan melalui proses evaluasi denganmenggunakan alat ukur yg di sebut dengan fungsi fitness.

Nilai fitness dari suatu kromosom akan menunjukkan kualitas kromosom dalam populasi tersebut. Generasi berikutnya dikenal dengan istilah anak (off-spring) terbentuk dari gabungan 2 kromosom generasi sekarang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover). Selain operator penyilangan, suatu kromosom dapat juga dimodifikasi dengan menggunakan operator mutasi. Populasi generasi yang baru dibentuk dengan cara menyeleksi nilai fitness dari kromosom induk (parent) dan nilai fitness dari kromosom anak (off-spring), serta menolak kromosom-kromosom yang 19 Universitas Sumatera Utara

lainnya sehingga ukuran populasi (jumlah kromosom dalam suatu populasi) konstan. Setelah melalui beberapa generasi, maka algoritma genetika ini akan konvergen ke kromosom terbaik.

2.5

Komponen-Komponen Utama Algoritma Genetika Ada 6 komponen utama dalam algoritma genetika, yaitu teknik penyandian, prosedur inisialisasi, fungsi evaluasi, seleksi, operator genetika dan penentuan parameter.

2.5.1

Teknik penyandian Teknik penyandian atau biasa disebut juga teknik pengkodean

disini meliputi penyandian gen dan kromosom. Gen merupakan bagian dari kromosom, satu gen biasanya akan mewakili satu variable

Gen dapat di presentasikan dalam bentu: sting bit, pohon, array bilangan real, daftar aturan, elemen permutasi, elemen program, atau representasi lainnya dapat diimplementasikan untuk operator genetika.

Gambar 2.9 menunjukkan representasi string bit dan pohon.

0 1 0 1 0 0 1

0 1 1 1

gen – 1

gen – 2

gen – 3

gen – 1

gen – 2

gen – 3

Gambar 2.10 Representasi string bit dan pohon

Demikian juga, kromosom dapat direpresentasikan dengan menggunakan:

1. String bit : 10011, 11101, dst 2. Bilangan Real : 56.56, -67.98, 562.88, dst 20 Universitas Sumatera Utara

3. Elemen Permutasi : E2, E10, E5, dst 4. Daftar Aturan : R1, R2, R3, dst 5. Elemen Program : pemrograman genetika, dst 6. Struktur lainnya

2.5.2

Proses inisialisasi (Membangkitkan populasi awal) Ukuran populasi tergantung pada masalah yang akan dipecahkan

dan jenis operator gen etika yang akan diimplementasikan. Setelah ukuran populasi ditentukan, kemudian harus dilakukan inisialisasi terhadap kromosom yang terdapat pada populasi tersebut. Inisialisasi kromosom dilakukan secara acak, namun demikian harus tetap memperhatikan domain solusi dan kendala permasalahanyang ada.

2.5.3

Fungsi evaluasi Ada 2 hal yang harus diperhatikan dalam melakukan evaluasi

kromosom, yaitu: evaluasi fungsi objektif (fungsi tujuan) dan konveksi fungsi objektif ke dalam fungsi fitness. Secara umum, fungsi fitness diturunkan dari fungsi objektif dengan nilai yang tidak negatif. Apabila ternyata fungsi objektif memiliki nilai negatif, maka perlu ditambahkan suatu konstanta C agar nilai fitness yang terbentuk menjadi tidak negatif.

2.5.4

Seleksi Seleksi ini bertujuan untuk memberikan kesempatan reproduksi

yang lebih besar bagi anggota populasi yang paling fit. Ada beberapa metode seleksi dari induk, antara lain: •

Rank-based fitness assignment.

•

Roulette wheel selection.

•

Stochastic universal sampling.

•

Local selesction.

•

Truncation selsction.

•

Tournamen selection. Dari beberapa metode seleksi tersebut, metode seleksi roda

roulette (Roulette wheel selection) adalah metode yang paling sederhana dan yang sering digunakan. 21 Universitas Sumatera Utara

2.5.5

Operator genetika Ada 2 operator genetika, yakni sebagai berikut:

1. Operator untuk melakukan rekombinasi, yang terdiri dari: •

•

•

Rekombinasi bernilai real -

Rekombinasi diskret

-

Rekombinasi intermediate (menengah)

-

Rekombinasi garis

-

Rekombinasi garis yang diperluas

Rekombinasi bernilai biner (crossover) -

Crossover satu titik

-

Crossover banyak titik

-

Crossover seregam

Crossover dengan permutasi

2. Mutasi

2.5.6

•

Mutasi bernilai real

•

Mutasi bernilai biner

•

Mutasi kromosom permutasi

Penentuan parameter Yang disebut dengan perameter disini adalah parameter control

algoritma genetika, yaitu: ukuran populasi (popsize), peluang crossover (Pc), dan peluang mutasi (pm). Nilai parameter ini ditentukan berdasarkan permasalahan yang akan dipecahkan. Ada beberapa rekomendasi yang bisa digunakan, antara lain: •

Untuk permasalahan yang memiliki kawasan solusi cukup besar, De Jong merekomendasikan untuk nilai parameter kontrol: (popsize; Pc; pm) = (50; 0,6; 0,001).

•

Bila rata-rata fitness setiap generasi digunakan sebagai indicator, maka Grefenstette merekomendasikan: (popsize; Pc; pm) = (30; 0,95; 0,01).

•

Bila fitness dari individu terbaik dipantau pada satiap generasi, maka usulannya adalah: (popsize; Pc; pm) = (80; 0,45; 0,01).

•

Ukuran populasi sebaiknya tidak lebih kecil dari 30, untuk sembarangan jenis permasalahan. 22 Universitas Sumatera Utara

2.6

Seleksi Seleksi digunakan untuk memilih individu-individu mana saja yang akan dipilih untuk proses pindah silang dan mutasi. Seleksi digunakan untuk mendapatkan calon induk yang baik. Semakin tinggi nilai fitness suatu individu, semakin besar kemungkinannnya untuk terpilih. Langkah pertama yang dilakukan dalam seleksi ini adalah pencarian nilai fitness. Nilai fitness ini yang nantinya akan digunakan pada tahap-tahap seleksi berikutnya.

Masing-masing individu dalam wadah seleksi akan menerima probabilitas reproduksi yang tergantung pada nilai objektif dirinya sendiri terhadap nilai objektif dari semua individu dalam wadah seleksi tersebut. Proses seleksi akan menentukan individu-individu mana saja yang akan dipilih untuk dilakukan rekombinasi dan bagaimana offspring terbentuk dari individu - individu terpilih tersebut.

2.6.1

Rank-Based Fitness Assignment Pada rank-based fitness assignment, populasi diurutkan menurut

nilai objektifnya. Nilai fitness dari tiap-tiap individu hanya tergantung pada posisi individu tersebut dalam urutan, dan tidak dipengaruhi oleh nilai objektifnya.

Misalkan N adalah jumlah individu dalam suatu populasi. Pos adalah posisi individu dalam populasi tersebut (posisi terendah suatu individu adalah pos = 1, dan posisi tertingginya adalah pos = N). sedangkan SP adalah selective pressure. Nilai fitness dari suatu individu dapat di hitung sebagai: •

Linear rangking: Fitness(Pos) = 2 – SP + 2(SP – 1)(Pos – 1) / (N – 1) Nilai SPϵ [1,2].

•

Non-linear rangking: Fitness(Pos) = Nind * X ^ (Pos – 1) / Sum(X^(i-1); I = 1... N Nilai SPϵ [1,2]. Sedangkan X dihitung sebagai akar polynomial: 23 Universitas Sumatera Utara

(SP – 1) * X ^(N – 1) + SP* X ^(N – 2) + … + SP* X + SP = 0 Nilai SPϵ [1, N – 2].

2.6.2

Seleksi Roda Roulette (Roulette wheel selection) Metode seleksi dengan mesin roulette ini merupakan metode

yang paling sederhana dan sering dikenal dengan nama Stochastic Sampling With Replacement. Cara kerja metode ini adalah sebagai berikut: 1. Dihitung nilai fitness dari masing-masing individu (fi, dimana i adalah individu ke-1 sampai ke-n). 2. Dihitung total fitness se 3. mua individu. 4. Dihitung pobabilitas masing-masing individu. 5. Dari probabilitas tersebut, dihitung jatah masing-masing individu pada angka 1 sampai 200. 6. Dibangkitkan bilangan random antara 1 sampai 200. Dari bilangan random yang dihasilkan, ditentukan individu mana yang terpilih dalam proses seleksi.

Gambar 2.11 Ilustrasi seleksi dengan mesin roulette 24 Universitas Sumatera Utara

2.6.3

Stochastic universal sampling Stochastic universal sampling memiliki nilai bias nol dan dan

penyebaran yang minimum. Pada metode ini, individu - individu dipetakan dalam suatu segmen garis secara berutan sedemikian hingga tiap-tiap segmen individu memiliki ukuran yang sama denganukuran fitnessnya seperti halnya pada seleksi

2.6.4

Seleksi Lokal (Local selesction) Pada seleksi lokal, Setiap individu yang berada didalam

konstrain tertentu disebut dengan nama lingkungan lokal. Interaksi antar individu hanya dilakukan didalam wilayah tersebut. Lingkungan tersebut ditetapkan sebagai struktur dimana populasi tersebut terdistribusi. Lingkungan tersebut juga dapat dipandang sebagai kelompok pasanganpasangan yang potensial.

Gambar 2.12 menunjukkan seleksi lokal, dalam lingkungan linear (full and half ring)

Gambar 2.12 Lingkungan Linear (full and half ring); jarak = 2

Langkah pertama adalah menyeleksi separuh pertama dari populasi yang berpasangan secara random. Kemudian lingkungan baru tersebut diberikan pada setiap individu yang terseleksi. Pada lingkungan yang baru tersebut, kita bisa menyeleksi pasangan-pasangan yang cocok atau

pasangan

yang

terbaik,

pasangan

yang

memiliki

fitness

proporsional, atau pasangan yang seragam. Struktur lingkungan pada seleksi local dapat berbentuk: 25 Universitas Sumatera Utara

•

Linear : full ring dan half ring

•

Dimensi-2: -full cross dan half cross -full star dan half star

•

Dimensi-3 dan struktur yang lebih kompleks yang merupakan kombinasi dari kedua struktur diatas.

Gambar 2.13 Lingkungan Dimensi – 2 (full and half cross); jarak = 1 Full star

Half star

Gambar 2.14 Lingkungan Dimensi – 2 (full and half star); jarak = 1

2.6.5

Seleksi dengan Pemotongan (Truncation selesction) Pada metode – metode seleksi yang telah di jelaskan terdahulu, ,

seleksi dilakukan secara alami. Pada seleksi dengan pemotongan ini, lebih berkesan sebagai seleksi buatan. Seleksi ini biasanya digunakan oleh populasi yang jumlahnya sangat besar. Pada metode ini, seleksi Individu-individu diurutkan berdasarkan nilai fitnessnya. Hanya individu yang terbaik saja yang akan diseleksi sebagai induk Parameter yang digunakan adalah suatu nilai ambang trunk yang mengindikasikan 26 Universitas Sumatera Utara

ukuran populasi yang akan diseleksi sebagai indukyang berkis arantara 50% -10%.Individu-individu yang ada di bawah nilai ambang ini tidak akan menghasilkan keturunan.

2.6.6

Seleksi dengan Turnamen ( Tournamen Selection) Pada metode seleksi dengan turnamen, ditetapkan suatu nilai tour

untuk individu-individu yang dipilih secara random dari suatu populasi. Individu-individu yang terbaik dalam kelompok ini akan diseleksi sebagai induk. Parameter yang digunakan pada metode ini adalah ukuran tour yang bernilai antara 2 sampai N (jumlah individu dalam suatu populasi).

2.7

Rekombinasi 2.7.1

Rekombinasi bernilai real

-

Rekombinasi diskret

-

Rekombinasi menengah (intermediate)

-

Rekombinasi garis

-

Rekombinasi garis yang diperluas

2.7.2

Rekombinasi bernilai biner (crossover) Pindah silang (Crossover) adalah operator dari Algoritma

genetika yang melibatkan dua induk untuk membentuk kromosom baru. Pindah silang menghasilkan titik baru dalam ruang pencarian yang siap untuk diuji. Operasi ini tidak selalu dilakukan pada semua individu yang ada. Individu dipilih secara acak untuk dilakuakn crossing dengan Pc antara 0.6 sampai 0.95. Jika pindah silang tidak dilakukan,maka nilai dari induk akan diturunkan kepada keturunan. Prinsip dari pindah silang ini adalah melakukan operasi (pertukaran, aritmatika) pada gen-gen yang bersesuaian dari dua induk untuk menghasilkan individu baru. Proses crossover dilakukan pada setiap individu dengan probabilitas crossover yang ditentukan. Pada gambar 2.4 diilustrasikan diagram alir penggunaan probabilitas crossover pada proses crossover. Operator crossover ini bergantung pada representasi kromosom yang dilakukan. 27 Universitas Sumatera Utara

Gambar 2.15 Diagram alir proses crossover

2.7.2.1 Crossover satu titik (Single-point Crossover) Crossover satu titik dan banyak titik biasanya digunakan untuk representasi kromosom dalam biner. Pada crossover satu titik, posisi crossover k (k=1,2,…,N-1) dengan N sebagai panjang kromosom diseleksi secara random. Variabel-variabel ditukar antara kromosom pada titik tersebut untuk menghasilkan anak. Pada gambar 2.16 diilustrasikan crossover satu titik.

Gambar 2.16 Ilustrasi crossover satu titik 28 Universitas Sumatera Utara

2.7.2.2 Crossover banyak titik (Multi-point Crossover) Pada crossover banyak titik, m posisi penyilangan ki (k=1,2,…., N-1; i=1,2,…,m) dengan N = panjang kromosom diseleksi secara randomdan tidak diperbolehkan ada posisi yang sama, serta diurutkan naik. Variabel-variabel ditukar antara kromosom pada titik tersebut untuk menghasilkan anak. Pada gambar 2.17 diilustrasikan crossover dua titik dan pada gambar 2.18 diilustrasikan crossover lebih dari dua titik.

Gambar 2.17 Ilustrasi Crossover dua titik

Gambar 2.18 Ilustrasi crossover lebih banyak titik

2.7.2.3 Crossover Seragam (uniform Crossover) Pada penyilangan seragam, Setiap lokasi memiliki potensi sebagai tempat penyilangan.Sebuah mask penyilangan dibuat sepanjang panjang kromosom secara random yang menunjukan bit-bit dalam mask yang mana induk akan mensupply anak dengan bit-bit yang ada. Induk yang mana yang akan menyumbangkan bit ke anak yang dipilih secara random dengan probabilitas yang sama.


2.7.2.4 Crossover dengan permutasi (Permutation Crossover) Dengan permutasi, kromosom-kromosom anak diperoleh dengan cara memilih sub-barisan suatu tour dari satu induk dengan tetap menjaga urutan dan posisis ejumlah kota yang mungkin terhadap induk yang lainnya.

2.8

Mutasi Operator berikutnya pada algoritma genetika adalah mutasi gen. Operator ini berperan untuk menggantikan gen yang hilang dari populasi akibat proses seleksi yang memungkinkan munculnya kembali gen yang tidak muncul pada inisialisasi populasi.

Kromosom anak dimutasi dengan menambahkan nilai random yang sangat kecil (ukuran langkah mutasi), dengan probabilitas yang rendah. Peluang mutasi (Pm) 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 pernah dievalusi. Tetapi bila peluang mutasi ini terlalu besar, maka akan terlalu banyak gangguan acak, sehingga anak akan kehilangan kemiripan dari induknya, dan juga algoritma kehilangan kemampuan untuk belajar dari history pencarian.

Ada beberapa pendapat mengenai laju mutasi ini. Ada yang berpendapat bahwa laju mutasi sebesar 1/n akan memberikan hasil yang cukup baik. Ada juga yang beranggapan bahwa laju mutasi tidak tergantung pada ukuran populasinya. Kromosom hasil mutasi harus diperiksa apakah masih berada pada domain solusi, dan bila perlu bias dilakukan perbaikan.


Gambar 2.19 Diagram alir proses mutasi

Proses diatas menggambarkan cara mudah untuk melakukan mutasi. Proses mutasi yang dilakukan tidak harus seperti pada proses tersebut. Proses yang lain bias dengan melakukan mutasi pada gen sebanyak probabilitas mutasi dikalikan jumlah gen, dimana posisi gen yang akan dilakukan mutasi dipilih secara acak.

2.8.1

Mutasi Bilangan Real Pada mutasi bilangan real, ukuran langkah mutasi biasanya

sangat sulit ditentukan. Ukuran yang paling kecil biasanya sering mengalami kesuksesan, namun adakalanya ukuran yang lebih besar akan berjalan lebih cepat. Operator mutasi untuk bilangan real dapat ditetapkan sebagai: -

variabel yang dimutasi = variable ± range * delta; ( + atau – memiliki probabilitas yang sama).

-

range = 0,5 * domain variable (interval pencarian)

-

delta = Σ(ai* 2-i); ai= 1 dengan probabilitas1/m, selain itu ai= 0, dengan m = 20 31 Universitas Sumatera Utara

2.8.2

Mutasi Bilangan biner Cara sederhana untuk mendapatkan mutasi biner adalah dengan

mengganti satu atau beberapa nilai gen dari kromosom. Langkahlangkah mutasi adalah: 1.

Hitung jumlah gen pada populasi (panjang kromosom dikalikan dengan ukuran populasi).

2.

Pilih secara acak gen yang akan dimutasi.

3.

Tentukan kromosom dari gen yang terpilih untuk dimutasi.

4.

Ganti nilai gen (0 ke 1, atau 1 ke 0) dari kromosom yang akan dimutasi tersebut.

2.8.3

Mutasi kromosom permutasi

Gambar 2.20 Proses dan hasil mutasi

2.9

Siklus Algoritma Genetika Siklus dari Algoritma genetika pertama kali diperkenalkan oleh David Goldberg, dimana gambaran siklus tersebut dapat dilihat pada gambar 2.21.

Gambar 2.21 Siklus Algoritma genetika oleh David Goldberg 32 Universitas Sumatera Utara

Siklus ini kemudian diperbaiki oleh beberapa ilmuwan yang mengembangkan Algoritma genetika, yaitu Zbigniew Michalewicz dengan menambahkan operator elitism dan membalik proses seleksi setelah proses reproduksi.

Gambar 2.22 Siklus Algoritma genetika Zbigniew Michalewicz hasil perbaikan dari siklus algoritma genetika yang dikenalkan oleh David Goldberg

2.10

Algoritma Genetika Sederhana Misalkan P(generasi) adalah populasi dari satu generasi, maka secara sederhana algoritma genetika terdiri dari beberapa langkahlangkah berikut:

1. Generasi=0 (generasi awal). 2. Inisialisasi populasi awal, P(generasi), secara acak. 3. Evaluasi nilai fitness pada setiapindividu dalam P(generasi). 4. Selanjutnya dilakukan langkah-langkah berikut hinggan mencapai maksimum generasi: a. generasi = generasi + 1 (tambah generasi). b. seleksi populasi tersebut untuk mendapatkan kandidat induk. 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)


2.10.1 Metode Seleksi Dengan Roda Roulette Seperti telah dijelaskan sebelumnya bahwa seleksi induk pada algoritma genetika sederhana ini menggunakan metode seleksi roda roulette karena metode seleksi inilah yang paling banyak digunakan. Seleksi ini bertujuan untuk memberikan kesempatan reproduksi yang lebih besar bagi anggota populasi yang memiliki fitness tinggi untuk melakukan reproduksi.

Algoritma genetika roda roulette: -

Hitng total fitness (F): Total fitness = Ʃ Fk ; k = 1,2,… popsize

-

Hitung fitness relatif tiap individu: Pk = Fk /total fitnees

-

Hitung fitness komulatif: q1 = p 1 qk = qk-1 + pk; k=2,3,….. (popsize)

-

pilih induk yang akan menjadi kandidat untuk di crossover dengan cara:

-

Bangkitkan nilai random r. Jika qk = r dan qk+1

> r,

maka pilih kromosom ke (k+1) sebagai

kandidat induk.

2.10.2 Crossover (penyilangan) Crossover (penyilangan) dilakukan atas 2 kromosom untuk menghasilkan kromosom anak. Kromosom anak yang terbentuk akan mearisi sebagian besar sifat krimosom induknya.metode yg sering digunakan pada algoritma genetika sederhana ini adalah crossover satu titik dan crossover dua titik. Pada metode ini,kita pilih sembarang bilangan secara acak untuk menentukan posisi persilangan, kemudian kita tukarkan bagian kanan titik potong dari kedua induk kromosom tersebut untuk menghasilkan kromosom anak. Misalkan:


Apabila posisi titik potong yang terpilih secara acak adalah 3, maka kromosom anak yang terbentuk adalah:

Pada crossover ada satu parameter yang sangat penting yaitu peluang crossover (Pc). Peluang crossover menunjukkan rasio anak yang dihasilkan dalam setiap generasi dengan ukuran populasi. Misalkam ukuran populasi (popsize=100), sedangkan peluang crossover (Pc = 0,25),berarti bahwa diharapkan ada 25 kromosom dari 100 kromosom yang semula pada populasi tersebut akan mengalami crossover.

2.10.3 Mutasi Mutasi yang digunakan pada algoritma genetika sederhana dengan kromosom biner seperti dijelaskan sebelumnya, pada dasarnya akan mengubah secara acak nilai suatu bit pada posisi tertentu. Kemudian kita mengganti bit 1 dengan bit 0, atau sebaliknya mengganti bit 0 dengan bit 1. Pada mutasi ini sangat dimungkinkan munculnya kromosom baru yang semula belum muncul dalam populasi awal. Misalkan :

terkena mutasi pada gen ke 5, di peroleh:

Pada mutasi ada satu parameter yang sangat penting yaitu peluang crossover (pm). peluang mutasi menunjukkan presentasi jumlah total gen pada populasi yang akan mengalami mutasi. Untuk melakukan mutasi, terlebih dahulu kita harus menghitung jumlah total gen pada populasi tersebut. Kemudian bangkitkan bilangan random

yang

menentukan posisi mana yang akan di mutasi. 35 Universitas Sumatera Utara

Secara umum, diagram alir algoritma genetika sederhana seperti terlihat pada gambar 2.23.

Gambar 2.23 Diagram alir algoritma genetika sederhana

2.10

Prosedur Algoritma Genetika Untuk menggunakan Algoritma genetika, perlu dilakukan prosedur sebagai berikut: 1. Menetapkan parameter optimasi, jumlah parameter optimasi, dan batas dari parameter optimasi 2. Menetapkan fungsi optimasi atau fungsi objektif 3. Menetapkan parameter algoritma genetika. 4. Membangkitkan populasi awal, mengkodekan, nilai real. 5. Mendefinisikan nilai fitness, yang merupakan ukuran baik tidaknya sebuah individu atau baik tidaknya solusi yang didapatkan. 6. Menentukan proses pembangkitan populasi awal. Hal ini biasanya dilakukandengan menggunakan pembangkitan acak seperti randomwalk. 7. Menentukan proses seleksi yang akan digunakan. 8. Menentukan proses pindah silang (crossover) dan mutasi gen yang akan digunakan.

2.10.1 Menetapkan parameter optimasi Menetapkan parameter optimasi, jumlah parameter optimasi, dan batas dari parameter optimasi. 36 Universitas Sumatera Utara

Contoh: •

Parameter optimasi : a. Panjang → X1 → X2

b. Lebar •

Jumlah parameter

:2

•

Batas parameter

: rb ≤ X1 ≤ ra rb ≤ X2 ≤ ra

Dimana

: ra = Batas atas rb = Batas bawah

2.10.2 Menetapkan fungsi optimasi atau fungsi objektif Fungsi objektif boleh menggunakan fungsi yang sudah ada, boleh juga dibuat sendiri. Sebaiknya pahami terlebih dahulu permasalahan kita, barulah pilih fungsi objektif yang cocok. Ada dua bentuk fungsi objektif, yaitu fungsi linear, dan fungsi nonlinear. Fungsi linear biasanya digunakan pada masalah yang tidak terkendala atau unconstraint. Karena tidak terkendala, solusi yang dihasilkan ada banyak titik sehingga kurang akurat. Sedangkan fungsi nonlinear, biasanya digunakan pada masalah yang terkendala atau constraint. Karena memiliki kendala, solusi yang dihasilkan lebih sedikit sehingga lebih akurat. Beberapa fungsi objektif linear yang sudah ada dan sering digunakan untuk optimasi adalah: •

Sphere Function f x =

•

x ……………………………………………………………………….. 2.5

Rastrigin Function f x =10n+

•

n i=1

xi2 -10cos 2πxi $ ……………………….…….. 2.6

Michalewics Function f x = -

n i=1

ixi2 sin⁡(xi ) 'sin ( )* π

2m

……………………….…………….(2.7)


2.10.3 Menetapkan Parameter Algoritma Genetika Parameter yang dimaksud adalah Jumlah generasi atau keturunan, Jumlah populasi pada setiap generasi, pengkodean panjang kromosom, probabilitas pindah silang (pc), dan probabilitas mutasi (pm). Banyaknya populasi dalam satu generasi, dan banyak generasi adalah tergantung dari yang kita inginkan. Akan tetapi, penentuan parameter ini juga dapat mengikuti aturan dibawah ini:

Tabel 2.3 Tabel perbandingan populasi, pc, dan pm

Masalah Untuk permasalahan yang memiliki kawasan solusi cukup besar. Bila rata-rata fitness setiap generasi digunakan sebagai indikator. Bila fitness dari individu terbaik dipantau pada setiap generasi.

Populasi

pc

pm

50

0,6

0,001

30

0,95

0,01

80

0,45

0,01

Maksimum generasi dan ukuran populasi sebaiknya tidak lebih kecil dari 30 untuk sembarang jenis permasalahan. (Sumber: eprints.undip.ac.id/25536/1/ML2F300570.pdf)

Pengkodean panjang kromosom berlaku untuk setiap parameter dengan menggunakan batasnya masing-masing. Jumlahkan untuk mendapatkan panjang kromosom pada satu individu. Pengkodean dilakukan mengikuti aturan: 2-./ < r2 − r4 × 106 ≤ 2-. ……………………………………….. 2.8 2.10.4 Menetapkan populasi awal Pembangkitan biasanya dilakukan secara acak, dan tersusun atas sederetan bilangan biner (dalam GA disebut bit-bit. Bit merupakan nilai dari sebuah gen) yang disebut kromosom. Kromosom mewakili parameter optimasi, satu kromosom berarti mewakili satu parameter optimasi. Dua parameter optimasi berarti ada dua kromosom. Kromosom yang lebih dari satu akan membentuk individu. 38 Universitas Sumatera Utara

Individu merupakan salah satu solusi yang mungkin. Individu bias dikatakan sama dengan kromosom, yang merupakan kumpulan gen. Gen ini bisa biner, pecahan (float), dan kombinatorial. Beberapa definisi penting yang perlu diperhatikan dalam mendefinisikan individu untuk membangun penyelesaian permasalahan dengan Algoritma genetika adalah sebagai berikut: 1. Genotype (Gen), adalah variable dasar yang membentuk suatu kromosom. Dalam algoritma genetika, gen ini bisa berupa biner, float, integer maupun karakter. 2. Allele, adalah nilai dari suatu gen, bisa berupa biner, float, integer maupun karakter. 3. Kromosom, adalah gabungan dari gen-gen yang membentuk arti tertentu. Ada beberapa macam bentuk kromosom, yaitu: • Kromosom biner adalah kromosom yang disusun dari gen-gen yang bernilai biner. • Kromosom float adalah kromosom yang disusun dari gen-gen yang bernilai pecahan, termasuk gen yang bernilai genap. • Kromosom string adalah kromosom yang disusun dari gen-gen yang bernilai string. • Kromosom kombinatorial adalah kromosom yang disusun dari gengen yang dinilai berdasarkan urutannya. 4. Individu, adalah kumpulan gen, bisa dikatakan sama dengan kromosom. Individu menyatakan salah satu kemungkinan solusi dari suatu permasalahan. 5. Populasi, adalah sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi. 6. Generasi, adalah satu satuan siklus proses evolusi atau satu literasi didalam Algoritma genetika. 7. Nilai fitness menyatakan seberapa baik nilai dari suatu individu atau solusi yang didapatkan. Nilai inilah yang dijadikan acuan untuk mencapai nilai optimal.


Gambar 2.24 Visualisasi gen, allele, kromosom, individu, dan populasi pada algoritma genetika

Satu gen biasanya akan mewakili satu variabel. Gen dapat dipresentasikan dalam bentuk bit, bilangan real, daftar aturan, elemen permutasi, elemen program, atau representasi lainnya yang dapat diimplementasikan untuk operator genetika.

1. Mendekodekan Bilangan biner setiap kromosom didekodekan ke bilangan desimal. Proses ini dapat dilakukan dengan menggunakan perhitungan matematis atau dengan program komputer. Contoh dengan perhitungan matematis: 1010 = (0 x 20) + (1 x 21) + (0 x 22) + (1 x 23) =0+2+0+ 8 = 10 10011 = (1 x 20) + (1 x 21) + (0 x 22) + (0 x 23) + (1 x 24) = 1 + 2 + 0 + 0 + 16 = 19 40 Universitas Sumatera Utara

2. Nilai riil Bilangan desimal setiap kromosom kemudian dicari nilai riil-nya menggunakan rumus: x9 = r4 + Bil. Desimal × ?

r2 − r4 A ………………………….…………… 2.9 2-@ − 1

Dimana : xk = Nilai riil untuk kromosom k ra = Batas atas parameter pemilik kromosom k rb = Batas bawah parameter pemilik kromosom k mk = Panjang kromosom k

2.10.5 Menetapkan Nilai fitness Nilai riil setiap kromosom pada satu individu dimasukkan ke fungsi objektif untuk mendapatkan nilai fitnesss individu. Contoh: Fungsi objektif : C DE = DF + DG

I

I

Kromosom (Nilai riil) x1

x2

HI

I1

0,22

0,33

0,55

I2

0,44

0,55

0,99

Generasi Populasi Individu

2.10.6 Menetapkan Seleksi Proses ini bertujuan untuk membangkitkan populasi baru. Setiap kromosom/individu pada populasi awal akan diseleksi berdasarkan nilai fitness. Kromosom/individu yang tidak lolos seleksi akan dibuang. Jadi sebenarnya, populasi baru ini adalah kumpulan anggota populasi lama yang lolos seleksi. Ada beberapa jenis metode seleksi yaitu: metode Roulette Wheel, metode Stochastic, metode Ranking, dan metode turnamen. Metode yang paling sering digunakan adalah metode Roulette Wheel. Metode ini dikenal juga dengan metode Monte Carlo. Ada beberapa langkah dalam proses seleksi menggunakan metode Roulette Wheel yaitu:


•

Hitung nilai fitness setiap kromosom/individu, f9 ataufL .

•

Hitung total fitness untuk populasi:

F=

NL L

fL …………………………………………………………………………… 2.10

Dimana: F JI •

= Total fitness = Jumlah individu pada satu populasi

Hitung probabilitas seleksi pI untuk masing-masing individu.

fL PI = ………………………………………………………(2.11) F

Dimana : pI = Probabilitas seleksi individu I I •

= 1,2,…,JI

Hitung probabilitas kumulatif qI untuk masing-masing individu. qI=

JI I=1

pI …………………………………………………(2.12)

Dimana : qI = Probabilitas kumulatif individu I I

= 1,2,…,JI

•

Hasilkan sejumlah nilai acak r (0< r <1) untuk setiap individu.

•

Jika r ≤ q1, pilih individu I1. Jika tidak, ikuti aturan:

TU/ < V ≤ TU dan pilih individu I.

2.10.7 Menentukan Proses Pindah Silang (Crossover) Pindah

silang

(crossover)

melibatkan

dua

induk

untuk

membentuk suatu individu dengan kromosom baru. Pindah silang menghasilkan titik baru dalam ruang pencarian yang siap untuk diuji. Prinsip dari pindah silang ini adalah melakukan pertukaran pada gen-gen yang bersesuaian dari dua induk untuk menghasilkan individu baru yang unggul karena menerima gen-gen baik dari kedua induknya. Langkah pertama proses pindah silang adalah membangkitkan sejumlah angka acak, rk (0

Caranya dengan

mengambil sebagian dari induk yang satu, dan

menukarnya dengan sebagian dari induk yang lainnya.

Dari sekian banyak metode pindah silang yang ada, metode yang paling sering digunakan adalah: •

Pindah silang satu titik (one point crossover) Mengambil setengah bagian induk yang satu dan menukarnya dengan setengah bagian induk lainnya. Contohnya:

Gambar 2.25 Pindah silang satu titik

(Sumber: lecturer.eepis-its.edu/~entin/Kecerdasan%20Buatan) •

Pindah silang dua titik (two point crossover) Mengambil sepertiga bagian induk yang satu dan menukarnya dengan sepertiga bagian induk lainnya. Contohnya:

Gambar 2.26 Pindah silang dua titik

(Sumber: lecturer.eepis-its.edu/~entin/Kecerdasan%20Buatan)

2.10.8

Menentukan Proses Mutasi Proses ini berperan untuk menggantikan gen yang hilang dari

populasi akibat proses seleksi yang memungkinkan munculnya gen yang tidak muncul pada pembangkitan populasi. Kromosom anak dimutasi dengan menambahkan nilai acak yang sangat kecil dengan probabilitas yang rendah.


Probabilitas mutasi (pm) didefinisikan sebagai persentasi dari jumlah total gen pada populasi yang mengalami mutasi. Peluang mutasi mengendalikan banyaknya gen baru yang akan dimunculkan untuk dievaluasi. Jika pm terlalu kecil, banyak gen yang mungkin berguna tidak pernah terevaluasi. Jika terlalu besar, akan terlalu banyak gangguan acak, sehingga anak akan kehilangan kemiripan dari induknya.

Untuk melakukan mutasi, pertama kita bangkitkan angka acak rk (0
2.10.9 Elitism Proses seleksi dilakukan secara random sehingga tidak ada jaminan bahwa suatu indvidu yang bernilai fitness tertinggi akan selalu terpilih. Walaupun individu bernilai fitness tertinggi terpilih, mungkin saja individu tersebut akan rusak (nilai fitnessnya menurun) karena proses pindah silang. Oleh karena itu, untuk menjaga agar individu bernilai fitness tertinggi tersebut tidak hilang selama evolusi, maka perlu dibuat satu atau beberapa kopinya. Prosedur ini dikenal sebagai elitisme.tetapi didalam optimasi ini elitisme tidak dipakai karena menggunakan algortima genetika standar

2.10.10 Evaluasi Ulang Sekarang, susun lagi data-data terakhir, yang terdiri dari individu/kromosom yang sudah termutasi dan juga yang tidak ikut termutasi. Kemudian, lakukan lagi prosedur mengubah bilangan biner yang di dapat setelah mutasi sampai mendapatkan nilai fitnessnya. Jika 44 Universitas Sumatera Utara

kita mendapatkan nilai fitness yang lebih tinggi dari nilai fitness milik populasi awal, berarti telah kita dapatkan sebuah solusi optimal. Jika tidak, ulangi kembali prosedur algoritma genetikanya sampai diperoleh solusi yang diinginkan.

2.11

Algoritma Genetika Dalam MATLAB MATLAB menyediakan toolbox untuk mengelolah suatu optimasi dengan menggunakan Algoritma Genetika. Penggunaan software dimaksudkan agar data dapat diperluas, sehingga proses

optimasi dapat dilakukan lebih kompleks, Perhitungan

pada

setiap

langkah

cepat, dan lebih mudah.

algoritma

genetika

seperti

membangkitkan populasi, mencari nilai fitness dan seterusnya akan dikerjakan otomatis oleh MATLAB. Jadi, kita hanya perlu memasukkan

variabel-variabel sesuai dengan masalah yang ingin kita optimasi.

Optimasi dengan algoritma genetika disimpan pada toolbox optimasi. Untuk mengaktifkan toolbox optimasi dapat dilakukan dengan dua cara. Yang pertama dengan memasukkan shortcut toolbox optimasi

pada jendela utama MATLAB dengan cara mengetikkan: optimtool ‘ga’ kemudian tekan: enter ,

Gambar 2.27 Command window MATLAB

maka akan muncul jendela toolbox optimasi seperti gambar 2.28

dibawah ini.


Gambar 2.28 Toolbox Optimasi pada MATLAB

Cara kedua yaitu dengan mencari toolbox optimasi secara manual. Pada jendela utama MATLAB klik tombol:

Start > Toolboxes > More… > Global Optimization > Optimization Tool seperti terlihat pada gambar 2.29 dibawah ini.

Gambar 2.29 Cara membuka Toolbox Optimasi secara manual

Tool optimasi ini berisi bermacam-macam metode optimasi. Klik pada kolom Solver, dan cari “ga – Genetic Algorithm”. Pada kolom


sebelah kanan akan muncul opsi-opsi yang dapat kita sesuaikan dengan permasalahan optimasi yang kita hadapi.

Gambar 2.30 Tampilan Toolbox Optimasi

Untuk mengetahui apa-apa saja yang perlu kita isi, klik tombol: >> , maka akan muncul panduan yang menjelaskan istilah-istilah pada toolbox GA.

Gambar 2.31 Penjelasan Toolbox Optimasi


Setelah selesai mengisi semua Problem Setup and Results dan Options, klik pada tombol Start maka optimasi akan dimulai dan kita tinggal menunggu hasilnya.

1. Problem Setup and Results •

Solver. Berisi bermacam-macam metode optimasi. Setiap metode memiliki opsi-opsi yang berbeda dengan metode lainya.

•

Problem. Terdapat Fitness Function untuk memanggil persamaan/fungsi optimasi

yang

ingin

digunakan.

Untuk

memanggil,

ketik

@fungsi_optimasi. Misalnya ingin menggukan fungsi Rastrigin, maka kita ketikkan: @rastriginfcn. Fungsi Rastrigin ini adalah salah satu fungsi optimasi yang disediakan oleh MATLAB. JIka kita ingin menggunakan fungsi buatan sendiri, kita harus membuat script-nya terlebih dulu. Caranya, pada jendela utama MATLAB klik: File > New > Script atau Function. Kemudian ketikkan fungsi optimasi yang diinginkan. Kemudian Number of Variables adalah jumlah variabel yang terdapat pada fungsi optimasi. •

Constraint. Jika fungsi optimasi kita bebrbentuk persamaan linear, maka isi semua baris kecuali Nonlinear constraints function. Jika berbentuk persamaan nonlinear, isikan baris Bounds dan Nonlinear constraints function saja.

2. Options Adalah tempat kita mengatur parameter GA seperti banyak populasi, jumlah generasi, jenis pindah silang, probabilitas pindah silang, jenis mutasi, probabilitas mutasi dan lain-lain. Dengan menggunakan opsi yang berbeda-beda, kita akan mendapatkan banyak hasil optimasi yang dapat saling kita bandingkan, kemudian kita putuskan mana yang paling sesuai dengan permasalahan yang kita punya.

Jika kita ingin melihat hasil grafik proses pengerjaannya tinggal mencentang pilihan yang ada pada plot function. Misalnya kita ingin


melihat fitness terbaik dan individu terbaik, maka ceklis atau centang kolom best fitness dan best individu.seperti terlihat pada gambar 2.31.

Gambar 2.32 Window hasil fitness

Hasil nilai akhir pada MATLAB dapat dilihat pada kolom result yang berada pada kiri bawah sedangkan pada command window terlihat jumlah generasi yang dibangkitkan.


BAB II TINJAUAN PUSTAKA

Recommend Documents