Jaringan Saraf Tiruan (Artificial Neural Network)

Berawal dari sistem mesin Von Neumann, sistem komputer pada saat ini telah berkembang pesat. Jaringan syaraf tiruan (JST) terjemahan dari Artificial Neural Network, merupakan suatu model dari sistem syaraf biologis yang disederhanakan sebagai suatu alternatif sistem komputasi. (Penelitian Jaringan Syaraf Tiruan,1993). Meskipun kecepatan proses yang telah dicapai komputer dewasa ini lebih cepat jika dibandingkan dengan proses yang dilakukan otak manusia, komputer masih belum bisa menandingi universilitas kemampuan pada otak manusia.

Struktur sel syaraf biologis

Sel syaraf biologis atau disebut juga Neuron memiliki tiga komponen penyusun yang saling bekerja sama untuk mengolah sinyal-sinyal informasi. Tiga komponen tersebut adalah dendirt, soma atau badan sel dan axon seperti tampak pada gambar 1.

Dendrit merupakan serabut saraf yang bercabang-cabang pendek dan berjumlah lebih dari satu ini bertugas menerima sinyal dari neuron lain. Sinyal listrik ini dilewatkan melalui celah sinapsis (sianapsis gap) yang pada perjalanan biologisnya terjadi proses kimiawi dengan penskalaan frekuensi sinyal, pada jaringan syaraf tiruan proses ini disebut pembentukan bobot. Sinyal yang diterima diolah oleh soma dan kemudian dijumlahkan.

Gambar 1. Struktur Sel Syaraf Biologis

Untuk mengirimkan informasi ke sel lain, sinyal dilewatkan melalui axon yang merupakan serabut syaraf tunggal dan pada ujungnya bercabang-cabang. Selanjutnya sinyal akan melalui celah sinapsis dan disampaikan ke soma lain oleh dendrit neuron tersebut. Sehingga dengan terintegrasi dan terkoneksinya neuron satu dengan yang lain akan dapat melaksanakan aktifitas secara teratur sesuai kebutuhan.

Struktur jaringan saraf tiruan

JST disusun oleh elemen – elemen pemroses yang berada pada lapisan-lapisan yang berhubungan dan diberi bobot. Dengan serangkaian inputan diluar sistem yang diberikan kepadanya jaringan ini dapat memodifikasi bobot yang akan dihasilkannya, sehingga akan menghasilkan output yang konsisten sesuai dengan input yang diberian kepadanya. Setiap elemen pemroses melaksanakan operasi matematika yang sudah ditentukan dan menghasilkan (hanya) sebuah harga keluaran dari satu ataupun banyak masukan. Struktur jaringan akan ditunjukkan seperti pada gambar berikut ini :

Gambar 2. Model tiruan neuron

Sebuah pemodelan neuron memiliki masukan Xp sebanyak p, yang berasal dari sel lain atau dari inputan luar (bukan dari neuron). Selanjutnya setiap inputan diberi pembobot Wkp. Masing – masing inputan Xp akan dikalikan dengan pembobot Wk yang berkesesuaian. Untuk semua hasil perkalian akan dijumlahkan sebagaimana pada persamaan dibawah ini :

(1)

dan hasil persamaan tersebut akan menjadi masukan bagi fungsi aktivasi untuk mendapatkan tingkat derajat sinyal keluaran pada neuron, dimana terdapat bermacam-macam jenis fungsi aktivasi. Untuk jenis fungsi sigmoid dapat dideskripsikan dengan persamaan :

(2)

dengan grafik yang ditunjukkan sebagai berikut :

Gambar 3. Grafik fungsi sigmoid

Pada umumnya sinyal fungsi aktivasi yang dikeluarkan tiap neuron berbeda, hal ini dikarenakan berbedanya nilai bobot yang diterima tiap neuron berbeda.

Pemodelan jaringan pada syaraf tiruan sering dikategorikan menjadi tiga yaitu : Single layer, multi layer dan competitve layer. Namun pada pembahasan kali ini hanya akan dibahas single layer dan multi layer, karena mengingat kaidah pelatihannya menggunakan algoritma backpropagation. Secara umum , tiap unit pada lapisan (Layer) yang sama atau dapat kita sebut neuron mempunyai tingkah laku yang sama untuk pemrosesan sinyal data. Hanya hal terpenting yang perlu diperhatikan adalah penentuan penggunaan jenis fungsi aktifasi pada masing-masing unit pada lapisan tersebut dan pola koneksi pembobot antar lapisan. Namun biasanya unit pada lapisan yang sama mempunyai jenis fungsi aktifasi yang sama dan pola koneksi pembobot yang sama pula.

Untuk pemilihan jumlah layer bukan berarti pemilihan layer untuk neuron, namun pemilihan layer untuk penghubung jalur pembobot antar neuron. Jadi variabel terpenting untuk pengenalan pola adalah pembobotnya.

Single layer

Jaringan ini terdiri atas lapisan input dengan beberapa unit input, satu lapis pembobot dan lapisan output yang terdiri atas beberapa unit output dimana masing – masing unit input terkoneksi secara penuh dengan masing-masing unit output, tetapi setiap unit output tidak terkoneksi dengan unit input maupun unit output yang lain. Pada jaringan ini masing-masing input unit menerima sinyal informasi dari luar dan melalui koneksi yang ada, dilakukan proses pembobotan untuk masing-masing sinyal yang akhirnya akan direspon oleh masing-masing output unit. Pembobot untuk satu unit output tidak akan berpengaruh pada unit output yang lain.

Multi layer

Cara kerja dari model ini sama seperti pada jaringan lapis tunggal. Hanya saja pada arsitekturnya terdapa tambahan beberapa layer untuk pembobot. Jadi pada pemodelan ini terdapat tambahan beberapa atau satu layer lagi diantara input layer dan output layer yang sering disebut dengan lapisan tersembunyi (Hidden Layer). Sehingga dengan demikian terdapat lapisan pembobot antara input layer, hidden layer dan output layer. Kelebihan dari arsitektur jenis ini jika dibandingkan dengan single layer ialah dapat menyelesaikan masalah kompleks yang mungkin tidak dapat diselesaikan oleh jaringan single layer secara sempurna. Hanya saja proses pelatihannya membutuhkan waktu yang agak lama karena tentu saja lebih sulit untuk dilakukan.

Gambar 4. Jaringan syaraf umpan maju dengan dua lapisan sel hidden

Jaringan Syaraf Tiruan Back-Propagation

Jaringan Syaraf Tiruan Back-Propagation merupakan salah satu model jaringan yang populer pada jaringan syaraf tiruan. Model jaringan ini banyak digunakan untuk diaplikasikan pada penyelesaian suatu masalah berkaitan dengan identifikasi, prediksi, pengenalan pola dan sebagainya. Pada latihan yang berulang–ulang, algoritma ini akan menghasilkan unjuk kerja yang lebih baik. Hal ini berarti bahwa “bobot interkoneksi” JST semakin mendekati bobot yang seharusnya.(Penelitian Jaringan Syaraf Tiruan,1993). Kelebihan lain yang dimiliki JST ini adalah kemampuannya untuk belajar (bersifat adaptif) dan kebal terhadap adanya kesalahan (Fault Tolerance) dengan kelebihan tersebut JST dapat mewujudkan sistem yang tahan akan kerusakan (robust) dan konsisten bekerja dengan baik.

Metode Backpropagation ini pertama kali diperkenalkan oleh Paul Werbos pada tahun 1974, kemudian dikemukakan kembali oleh David Parker di tahun 1982 dan kemudian dipopulerkan oleh Rumelhart dan McCelland pada tahun 1986. Pada Algoritma BackPropagation ini, arsitektur jaringan menggunakan jaringan banyak lapis. Secara garis besar proses pelatihan pada jaringan saraf tiruan dikenal beberapa tipe pelatihan, yaitu Supervised Training, Unsupervised Training, Fixed-Weight Nets.

Metode pelatihan BackPropagation atau dikenal dengan Generalize Delta Rule (GDR) ini merupakan supervised training dimana untuk tiap pola input terdapat pasangan target output untuk masing-masing pola input. Sebenarnya adalah metode gradient descent untuk meminimasi total square error pada keluaran hasil perhitungan jaringan. Ide dasarnya dapat dideskripsikan dengan pola hubungan yang sederhana yaitu : jika output memberikan hasil yang tidak sesuai dengan target yang tidak diinginkan, maka pembobot akan dikoreksi agar errornya dapat diperkecil dan selanjutnya respon jaringan diharapkan akan lebih mendekati harga yang sesuai. Pada umumnya tujuan jaringan syaraf tiruan melakukan proses pelatihan adalah untuk mendapatkan balancing antara kemampuan jaringan untuk menanggapi secara benar pola-pola input pada saat pelatihan (dapat dikatakan kemampuan mengingat) dan kemampuan untuk memberikan penilaian yang layak dari suatu pola masukkan lain yang serupa. Sehingga dari proses pelatihan tersebut akan dibentuk suatu harga pembobot yang akan digunakan sebagai faktor penggali dari pola masukkan yang lain.

Pada metode ini, terdapat tiga tahapan dalam proses pelatihan, yaitu: proses umpan maju dari pola input pelatihan, perhitungan dan propagasi balik dari error yang terjadi dan penyesuaian nilai bobot.

Pada tahap pelatihan ini merupakan langkah bagaimana suatu jaringan syaraf itu berlatih, yaitu: proses umpan maju dari pola input pelatihan, perhitungan, dan propagasi balik dari error yang terjadi dari penyesuaian nilai pembobot.

Pada tahap pelatihan ini merupakan langkah bagaimana suatu jaringan syaraf itu berlatih, yaitu dengan cara melakukan perubahan bobot sambungan, baik bobot sambungan antar input layer dan hidden layer maupun antara hidden layer dan output layer, bila terdapat lebih dari satu hidden layer maka juga terdapat pembobot antar hidden layer itu sendiri. Sedangkan penyelesaian masalah baru akan dilakukan jika proses pelatihan tersebut selesai, fase tersebut adalah proses pemakaian/testing tentunya dengan menggunakan pembobot yang telah dihasilkan dari proses pelatihan yang telah dilakukan.

A. Fase pelatihan umpan mundur (backpropagation)

Jaringan BackPropagation terdiri atas beberapa layer yang masing-masing unit pada satu layer terhubung penuh dengan masing-masing unit pada lapisan diatasnya atau dibawahnya, kecuali pada bias hanya terkoneksi penuh dengan unit layer diatasnya yang ditunjukkan pada gambar 7.

Pada gambar 7 tersebut menunjukkan jaringan yang memiliki satu hidden layer dengan input layer X, hidden layer Z dan output layer Y, serta pemberian nilai bias, yaitu suatu masukkan dengan nilai tetap sama yaitu 1.

Gambar 5. Jaringan Syaraf Tiruan dengan satu hidden layer

Algoritma belajar BackPropagation terdiri dari dua proses, feed foward dan back propagation dari errornya. Selama feed foward masing-masing unit masukkan menerima (X) atau sinyal masukkan dari luar, kemudian sinyal tersebut disebarkan masing-masing unit pada hidden layer (Z), masing-masing hidden unit menghitung sesuai dengan fungsi aktifasinya. Dan kemudian mengirim sinyal itu kemasing-masing unit pada output layer akan menghitung sesuai dengan fungsi aktifasinya juga, yang akan menghasilkan sinyal keluaran sebagai respon jaringan dengan adanya pemberian pola input tersebut.

Pada propagasi baliknya, masing-masing output unit dibandingkan dengan hasil perhitungan aktivasi Y dengan nilai target t untuk mendapatkan error, berdasarkan error inilah akan dihitung nilai δk, selanjutnya harga error pada output unit akan disebarkan mundur ke masing-masing uni pada hidden layer. Selanjutnya error tersebut digunakan untuk memperbaiki faktor pembobot antara unit output dengan unit hidden demikian selanjutnya dicari error dari keluaran hidden untuk memperbaiki faktor pembobot antara unit input. Untuk jelasnya dapat dijelaskan sebagai berikut :

Langkah 1 : Pemberian inisialisasi faktor penimbang (diberi nilai kecil secara random)

Langkah 2 : Ulangi step 2 hingga 9 hingga kondisi stop terpenuhi

Langkah 3 : Untuk masing-masing pasangan pelatihan lakukan langkah 3 hingga 8

Feedforward

Langkah 3 : Masing-masing unit input (Xi, i =1,…n) menerima sinal input X_i dan sinyal tersebut disebarkan ke unit bagian atas lapisan tersembunyi (hidden units)

Langkah 4 : Masing – masing hidden menjumlahkan fakor penimbang :

(3)

Dan menghitung sesuai dengan fungsi aktivasi :

(4)

karena yang digunakan fungsi sigmoid maka :

(5)

Kemudian mengirim sinyal tersebut ke semua unit di atasnya (output unit).

Langkah 5 : Masing-masing unit output (Y_k, k=1,2,3…..m) dijumlahkan faktor penimbang

(6)

Menghitung sesuai dengan fungsi aktivasi

(7)

Back Propagation dari errornya

Langkah 6 : Masing-masing unit output (Y_k, k=1,…….,m) menerima pola target sesuai dengan pola masukan saat pelatihan dan menghitung errornya

(8)

karena f’(y _in_k) = y_k dengan menggunakan fungsi sigmoid, maka :

(9)

Menghitung pembetulan faktor penimbang (kemudian memperbaiki W_jk ).

(10)

Menghitung pembetulan koreksi :

(11)

Dan mengirim nilai δ_k ke unit layer dibawahnya.

Langkah 7 : masing-masing unit hidden (Z_j , j=1……,p) menjumlah delta inputnya (dari unit layer di atasnya).

(12)

Selanjutnya dikalikan dengan turunan dari fungsi akifasinya untuk menghitung error.

(13)

Menghitung pembetulan penimbang (digunakan untuk memeperbaiki V_ij .

(14)

Kemudian menghitung pembetulan bias (untuk memperbaiki V_oj)

(15)

Memperbaiki penimbang dan bias

Langkah 8 : Masing –masing output unit (Y_k , k=1,…,m) diperbaiki bias dan penimbangnya (j = 0,…,n)

(16)

Langkah 9 : Uji kondisi pemberhentian.

B. Fase Pemakaian Neural Network

Pada fase pelatihan akan didapatkan harga pembobot pada masing-asing layer. Pada fase pemakaian ini, pembobot yang dipakai adalah pembobot yang dibentuk pada saat pelatihan saat mencapai harga terbaik tentunya dengan pola jaringan yang sama seperti pada fase pelatihan, jika pola jaringan tidak sama, maka dapat dipastikan jaringan akan memberikan output yang tidak diinginkan. Algoritma yang dipakai pada fase ini hanya menggunakan bagian feedfoward dari pelatihan. Secara lengkap dapat dijelaskan sebagai berikut :

Langkah 0 : Pemberian inisialisasi faktor penimbang (diambilkan dari pembobot yang dibentuk pada saat pelatihan)

Langkah 1 : untuk masing-masing pola input, dilakukan langkah 2- 4.

Langkah 2 : masing – masing unit input (X_i, i =1 ,….n) menerima sinyal input X_i dan sinyal tersebut disebarkan ke unit bagian atas lapisan tersembunyi (unit hidden)

Langkah 3 : Masing-masing hidden unit menjumlahkan faktor penimbang :

(17)

Dan menghitung sesuai dengan fungsi aktivasi :

(18)

karena yang digunakan fungsi sigmoid maka :

(19)

Kemudian mengirim sinyal tersebut ke semua unit di atasnya (output unit) .

Langkah 4 : Masing-masing unit output(Yk, k=1,2,3…..,m) dijumlahkan faktor penimbang :

(20)

Menghitung sesuai dengan fungsi aktivasi :

(21)

karena yang digunakan fungsi sigmoid maka :

(22)

Algoritma Genetika / Genetic Algorithm

Algoritma Genetika / Genetic Algorithm

Algoritma genetik 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 lingkunganya akan mempunyai kesempatan hidup yang lebih besar.

Penggunaan prinsip genetika pada komputer dimulai pada tahun 1950 ketika beberapa ahli Biologi mengunakan komputer untuk simulasi sistem biologi. Akhir tahun 1975 John Holland dari Universitas Michigan melalui paper yang berjudul “Adaption in Natural and Artificial System” mengunakan konsep dasar algoritma genetika. 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 (Kromosam) 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. Adapun struktur umum algoritma genetika dapat diilustrasikan pada gambar berikut:

Gambar 1. Struktur umum Algoritma Genetika

Binary encoding dapat memberikan banyak kemungkinan pada kromosom meskipun pada jumlah allele yang sedikit. Dilain pihak jenis encoding ini tidak cukup natural untuk beberapa kasus tertentu dan kadang-kadang harus dilakukan koreksi setelah melakukan crossover atau mutasi, contoh penggunaan Binary encoding adalah pada permasalahan knapsack atau pengepakan, dimana ada beberapa barang dengan jumlah dan ukuran masing-masing dan knapsack harus memberikan kapasitasnya untuk barang-barang tersebut, permasalahanya adalah bagaimana memilih barang untuk memaksimalkan jumlah barang sehingga dapat ditampung olehk napsack tanpa harus menambah kapasitasnya.

Istilah-istilah yang digunakan dalam Algoritma genetika ini hampir sama dengan istilah-istilah yang dipakai dalam bidang biologi genetika, antara lain Gen, Kromosom, Populasi, Fungsi Fitness, dan operator genetika yang meliputi mutasi dan crossover.

Gen

Gen adalah suatu sel dari suatu kromosom atau nilai yang terdapat dalam Algoritma genetika ini dapat dibentuk oleh sebuah byte bahkan tidak menutup kemungkinan suatu string. Gen ini mewakili sebagian kecil dari solusi permasalahan.

Kromosom

Individu dalam populasi disebut string, genotype atau kromosom-kromosom terdiri dari unit-unit yang dinamakan Gen, Karakter, Decoder. Kromosom ini dapat mewakili suatu solusi, dimana dapat diilustrasikan dalam gambar dibawah ini:

Gambar 2. Kromosom dalam algoritma genetika

Untuk mempresentasikan kromosom dilakukan dengan proses encoding, dibawah ini akan dijelaskan beberapa proses encoding yang biasa digunakan dalam beberapa kasus tertentu.

Permutation Encoding

Untuk jenis Permutation Encoding ini digunakan untuk permasalahan proses pengurutan, misalnya terdapat kasus optimasi jadwal atau pada kasus traveling salesman. Pada Permutation Encoding, setiap Gen pada kromosom berupa angka dimana dapat ditampilkan seperti gambar di bawah ini:

Gambar 3. Permutation Encoding

Permutation Encoding hanya berlaku untuk permasalahan pengurutan, untuk itu dalam kasus-kasus yang ada pada Permutation Encoding terdapat beberapa jenis crossover dan mutasi yang harus dibuat untuk mempertahankan kromosom agar tetap konsisten. Contoh penggunaan Permutation Encoding ini adalah pada kasus trvelling salesman, dimana terdapat beberapa kota dengan jarak masing-masing. Pada kasus traveling salesman ini seorang salesman harus mengunjungi semua kota yang ada, tetapi tidak harus berjalan jauh untuk mencapai seluruh kota. Permasalahanya adalah menentukan urutan kota yang akan dikunjungi untuk meminimalisasi jarak yang harus ditempuh.

Binary encoding

Binary encoding adalah jenis encoding yang paling sering digunakan karena kasus pertama yang ada pada Algiritma Genetik menggunakan algoritma jenis ini. Setiap kromosom pada Binary encoding merupakan bit 0 dan 1 dimana dapat ditampilkan pada gambar bawah:

Gambar 4. Binary encoding

Binary encoding dapat memberikan banyak kemungkinan pada kromosom meskipun pada jumlah Gen yang sedikit. Dilain pihak jenis encoding ini tidak cukup natural untuk beberapa kasus tertentu dan kadang-kadang harus dilakukan koreksi setelah melakukan crossover atau mutasi, contoh penggunaan Binary encoding adalah pada permasalahan knapsack atau pengepakan, dimana ada beberapa barang dengna jumlah dan ukuran masing-masing dan knapsack harus memberikan kapasitasnya untuk barang-barang tersebut, permasalahanya adalah bagaimana memilih barang untuk memaksimalkan jumlah barang sehingga dapat ditampung oleh knapsack tanpa harus menambah kapasitasnya.

Crossover

Crossover adalah operator algoritma genetika yang membutuhkan parameter dua kromosom. Dua buah kromosom tersebut disebut kromosom induk. Operator ini akan menghasilkan dua buah kromosom baru. Ada beberapa jenis crossover yang sering digunakan dalam algoritma genetika antara lain:

Ordered Based Crossover

Ordered based Crossover diawali dengan menentukan posisi-posisi gen secara random pada induk pertama misalnya didapatkan posisi 3,4,6 dan 9 pada induk.

P1= ( 1 2 3 4 5 6 7 8 9 )

P1= ( 4 5 2 1 8 7 6 9 3 )

Kemudian Gen-gen pada induk yang berada tepat dibawah posisi-posisi tersebut dicatat yaitu 2,1,7 dan 3 untuk Q1 disalin dari P1 dengan menghilangkan angka-angka 2,1,7 dan3 tersebut sehingga menjadi

Q1= ( x x x 4 5 6 x 8 9 )

Subset 2,1,7, dan 3 ini di masukan dalam Q1 dimulai dari kiri dengan mempertahankan urutan sehingga menjadi

Q1 = (2 1 7 4 5 6 3 8 9)

Untuk Q2 diperlukan sama hanya perlu meukar induk pertama menjadi induk kedua dan induk kedua menjadi induk pertama yang menjadi:

Q2 = (3 5 2 1 8 7 4 6 9)

One-Point Crossover

Contoh kerja operator ini adalah dengan menentukan crossover point (gen tertentu). Kromosom baru pertama berisi gen pertama sampai gen crossover point dari kromosom induk pertama ditambah dengan gen dari crossover point sampai gen terakhir dari kromosom induk kedua. Kromosom baru kedua berisi gen pertama sampai gen crossover point dari induk kedua ditambahkan dengan gen dari crossover point sampai gen dari kromosom induk pertama. Adapun metode crossover ini dapat diilustrasikan pada gambar berikut:

Gambar 5. Proses crossover dengan satu crossover point

Dari ilustrasi di atas maka contoh penerapan metode One-Point Crossover adalah sebagai berikut:

Parent 1: 1 2 3 4 5 | 6 7 8 9

Parent 2: 4 5 3 6 8 | 9 7 2 1

Setelah proses crossover turunan yang dapat dihasilkan adalah dari kedua parent diatas adalah:

Parent 1: 1 2 3 4 5 | 9 7 2 1

Parent 2: 4 5 3 6 8 | 6 7 8 9

Two-Point Crossover

Proses Two-Point Crossover hampir sama dengan prosedur One-Point Crossover, kecuali pada Two-Point Crossover harus dipilih dua crossover point dan hanya gen yang ada di antara kedua crossover point itu yang akan ditukarkan.

Metode ini dapat menjadi bagian awal dan akhir dari kromosom dan hanya menukar bagian tengahnya saja.

N-Point Crossover

Prosedur N-Point Crossover hampir sama baik dengan prosedur one-point crossover maupun two-point crossover, hanya saja dalam n-point crossover ini harus dipilih n crossover point dan hanya gen di antara crossover point ganjil dan genap yang dapat ditukarkan sedangkan gen diantara genap dan ganjil operator crossover tidak berubah. Atau dengan kata lain harus dipilih posisi n dan hanya bit antara ganjil dan genap posisi crossover yang akan dihilangkan.

Contoh: P1= 9 7 6 3 2 8

P2= 2 1 9 7 4 5

Jika didapatkan angka random untuk n=3 dan diacak 1,2 dan 4 sebagai posisi dari gen yang akan di crossover, didapatkan kromosom turunan:

T1= 9 1 6 3 4 5

T2= 2 7 9 7 2 8

Mutasi

Mutasi adalah operator yang membutuhkan satu perameter. Kromosom operator ini merupakan nilai suatu gen dari sebuah kromosom sehingga kromosom yang baru ini berbeda dengan kromosom yang lama. Sekumpulan kejadian dengan suatu nilai pelanggaran maksimal dapat dengan mudah dihilangkan selama evaluasi fitness “tujuan dari proses mutasi ini, untuk mempertahankan kehilangan permanent dari suatu bit atau gen” (Whitley,1993:16). Seluruh proses mutasi ini menjanjikan keuntungan melalui pengarahan mutasi kemana mutasi ini tersebut sangat dibutuhkan. Oprator mutasi digunakan untuk melakukan modifikasi satu atau lebih dari nilai gen dalam individu yang sama. Mutasi memastikan bahwa probabilitas untuk pencarian pada daerah tertentu dalam persoalan tidak akan pernah nol dan mencegah kehilangan total materi genetika setelah pemilihan dan penghapusan. Mutasi ini bukanlah operator genetika yang utama, yang dilakukan secara acak pada gen dengan kemungkinan yang lebih kecil. Metode ini disebut metasi gen (gene mutation) terdapat metode lain yaitu: “order mutation” dimana dimungkinkan untuk menghilangkan seluruh gen dari dua gen yang dipilih secara acak. Terdapat empat operator yang biasa digunakan untuk permasalahan penjadwalan antara lain:

Violation Directed Mutation (VDM)

Memilih sutatu kejadian dengan suatu nilai pelanggaran maksimal, dan secara acak mengubah waktu penugasan.

Event Freeing Mutation (EFM)

Memilih suatu kejadian dengan sauatu pelanggaran maksimal, kemudian memberi waktu baru yang mana akan mengurangi secara maksimal angka ini.

Secara stokastik memilih suatu kejadian ,bias melalui kejadian itu dengan nilai pelanggaran yang tinggi, kemudian secara stokastik memilh waktu baru untuk kejadian ini, bisa melalui waktu yang mana akan mengurangi secara maksimal angka pelanggaran kejadian.

Fungsi Objektif

Fungsi objektif adalah tujuan dari optimasi permasalahan. Biasanya fungsi objektif ini hanya dua macam yaitu memaksimalkan dan meminimalkan

Model Pengembangan Algoritma Genetika

Algoritma genetika menyelesaikan permasalahan dengan cara menghasilkan, mengubah dan mengevaluasi kandidat solusi dari permasalahan tersebut. Awalnya sebuah populasi acak yang terdiri dari kromosom-kromosom di hasilkan kemudian kromosom-kromosom itu diubah oleh operator genetika yaitu crossover dan mutasi, kemudian kromosom-kromosom tersebut dievaluasi oleh fungsi fitness.

Terdapat beberapa cara dalam menentukan inisialisasi diantaranya biner dan non biner. Untuk inisialisasi masalah penjadwalan yang paling sederhana dapat dilihat sebagai masalah penetapan V even atau kejadian dalam S selang waktu dengan kata lain definisi dari masalah penjadwalan adalah:

E adalah definisi dari sejumlah V even (e1.e2,….en)

T adalah definisi dari sejumlah S selang waktu (t1,t2,…tn)

Berdasarkan definisi tersebut maka permasalahan penjadwalan tersebut ditetapkan sebagai pasangan terurut (a,b) yang berarti a Є E dan b Є T, dengan intepretasi bahwa even a terjadi pada selang waktu b.

Terdapat berbagai versi pengkodean masalah penjadwalan diantaranya adalah representasi klasik dan representasi Tuples. Dalam representasi kalsik digunakan matrik dua dimensi. Bagian kolom merupakan bagian produksi dan bagian baris merupakan interval waktu. Isi dari matrik M(i,j) adalah staf atau karyawan yang mengerjakan WOdan jumlah shiftnya. Jadi matrik M(i,j) dibaca sebagai karyawan dengan shift m mengerjakan WOpada bagian produksi.

Metode penentuan lokasi awal sangat berpengaruh terhadap kinerja algoritma genetika. Ada dua cara yang bisa digunakan untuk menghasilkan dua populasi awal. Cara yang pertama dengan menghasilkan seluruh kromosom secara acak. Sedangkan cara yang kedua sebagain kromosom dihasilkan dengan metode tertentu, yang dikenal dengan populasi awal terarah. Salah satu metode untuk membangkitkan populasi awal adalah metode Joshepus permutation.

Berikut adalah algoritma joshepus permutation:

Step 1 = [ Nilai awal ]

For i=1 to N Step1

Plist[i] 0

End for

N Loop random (N) + 1

F gen random (N) + 1

K=1

Step 2 = [ Isi nilai gen ]

Kromosom [k] F gen

Plist [F gen] 1

Step 3 = [ Cek kondisi ]

If ( K= n ) then go to Step 7

End if

Step 4 = [ Cari nilai gen selanjutnya ]

For i=1 to N Loop Step1

Repeat

F gen F gen + 1

If (F gen > N) then

F gen 1

Until Plist [F gen] <> 1

End if

End for

Step 5 = [ Naikan ounter k ]

K =K+1

Step 6 = [ Ulangi Step2 sampai Step 5 ]

Go to Step 2

Step 7 = [ Ulangi untuk kromosom selanjutnya ]

If Belum_semua_krm_telah_diinisialisasi then

Kromosom parameter_ke_krm_berikutnya_dalam_populasi

Go to Step 2

End if

Step 8 = [ Selesai ]

Return

N adalah jumlah allele dalam seluruh kromosom, Plist adalah sebuah array dengan jumlah element sebanyak N, random (x) adalah fungsi generator bilangan random antara 0 sampai x-1. element array dimulai dari 1. kromosom adalah element dari array populasi yang menampung urutan allele.

Fungsi Evaluasi atau Fungsi Fitness

Fungsi adalah salah satu aspek terpenting dalam algoritma genetika. Fungsi evaluasi yang baik harus mampu menghasilkan suatu kurva silo. Siklus yang cukup baik dan dapat mewakili permasalahan yang dihadapi.

Pengumpulan dini dalam algoritma genetika terjadi ketika beberapa kromosom dengan nilai fitness yang tinggi (tapi bukan optimal) memdominasi populasi dengan mengakibatkan algoritma genetika konvergen pada local optima. Ketika populasi konvergen kemampuan algoritma genetika untuk mencari solusi manjadi lebih baik. Crossover antara kromosom yang hampir identik menghasilkan kromosom baru yang identik dalam operasi ini hanya operasi mutasi yang mampu menghasilkan kromosom yang relatif baru dan merupakan cara untuk menghidarkan kromosom yang super mendominasi populasi.