BAB II

KAJIAN TEORI

Kajian teori pada bab ini membahas tentang pengertian dan penjelasan yang

berkaitan dengan optimasi, pemrograman linear, pemrograman nonlinear, quadratic

programming dan algoritma genetika. Kajian teori tersebut akan digunakan untuk

bab pembahasan selanjutnya.

A. Optimasi

Optimasi berasal dari bahasa inggris optimization yang memiliki arti

memaksimalkan atau meminimumkan sebuah fungsi yang diberikan untuk beberapa

macam kendala (Licker, 2003 : 170). Definisi lain yaitu menurut Rao (2009 : 1)

optimasi dapat didefinisikan sebagai proses untuk menemukan kondisi yang

memberikan nilai maksimum dan minimum dari suatu fungsi.

Optimasi berkaitan dengan pencarian solusi dari suatu permasalahan dengan

kendala tertentu. Permasalahan tersebut dapat berupa pemrograman linear dan

pemrograman nonlinear. Pada permasalahan sehari-hari seringkali diselesaikan

dengan pemrograman non linear. Terdapat beberapa metode untuk menyelesaikan

permasalahan pemrograman nonlinear, diantaranya adalah Lagrange Multiplier,

pendekatan kondisi Karush-Kuhn-Tucker, Quadratic Programming, dan Separable

Programming.

B. Fungsi Konveks dan Konkaf

Pada subbab ini akan didefinisikan mengenai beberapa fungsi sebagai berikut:

7
Definisi 2.1 (Varberg & Purcell, 2001 : 155)

Misalkan f terdefinisi pada interval I (terbuka, tertutup, atau tidak satupun)

maka,

i. naik pada I jika untuk setiap pasang bilangan dan dalam I,

ii. turun pada I jika untuk setiap pasang bilangan dan dalam I,

iii. monoton murni pada I jika f naik atau turun pada I.

Definisi 2.2 (Varberg & Purcell, 2001 : 156)

Misalkan f terdiferensial untuk setiap , maka f dikatakan cekung

keatas atau konveks jika naik untuk setiap dan f dikatakan cekung

kebawah atau konkaf jika turun untuk setiap .

Teorema 2.1 (Varberg & Purcell, 2001 : 157)

Misalkan f terdiferensial dua kali untuk setiap

i. Jika , maka f cekung keatas atau konveks untuk setiap ,

ii. Jika , maka f cekung kebawah atau konkaf untuk setiap .

Turunan kedua dari fungsi f adalah turunan pertama dari , sehingga dapat

disimpulkan bahwa jika positif maka naik dan jika negatif maka turun.

Turunan parsial kedua dapat digunakan untuk menguji konveks atau

konkafnya suatu fungsi f dengan banyak variabel. Uji konveksitas untuk fungsi satu

variabel yang memiliki turunan kedua untuk setiap x yang mungkin. Dengan

8
demikian, menurut Hiller dan Lieberman (2008 : 473), fungsi bersifat sebagai

berikut:

1. Konveks jika dan hanya jika untuk setiap nilai x yang mungkin,

2. Konveks ketat jika dan hanya jika untuk setiap nilai x yang

mungkin,

3. Konkaf jika dan hanya jika untuk setiap nilai x yang mungkin,

4. Konkaf ketat jika dan hanya jika untuk setiap nilai x yang

mungkin.

Jika terdapat dua variabel ( maka uji konveksitas dapat dilihat pada

tabel 2.1 berikut:

Tabel 2.1. Fungsi Konveks dan Konkaf dengan Dua Variabel

Konveks Konkaf
Kuantitas Konveks Konkaf
Ketat Ketat

* +

C. Pemrograman Linear

Pemrograman Linear adalah metode optimasi untuk menemukan nilai

optimum dan fungsi tujuan linear pada kondisi pembatasan-pembatasan tertentu

(Ruminta, 2009 : 327). Pemrograman linear adalah salah satu teknik Operations

9
Research yang paling banyak digunakan. Teknik ini menjadi dasar pengembangan

teknik Operations Rersearch yang lain seperti Goal Programming, Binary Integer

Programming atau Zero-One Programming. Teknik ini bisa digunakan untuk

menyelesaikan teknik Operations Research lain, seperti Transportation, Assignment,

Crash Time and Crash Cost program pada Critical Path Method, Equilibrium

condition pada Markov Analysis, Dual Programming pada Game Theory, dan

Network Analysis seperti Transhipment, Shortest Route, Minimum Spanning Tree,

dan Maximal Flow.

Model pemrograman linear mempunyai tiga unsur utama yaitu (Siswanto,

2006 : 25-26):

1. Variabel Keputusan

Variabel Keputusan adalah variabel yang akan mempengaruhi nilai tujuan yang

hendak dicapai. Pada proses pembentukan suatu model, menentukan variabel

keputusan harus dilakukan terlebih dahulu sebelum menentukan fungsi tujuan

dan kendala-kendalanya.

2. Fungsi Tujuan

Fungsi Tujuan adalah tujuan yang hendak dicapai diwujudkan ke dalam sebuah

fungsi matematika linear. Selanjutnya fungsi-fungsi tersebut dimaksimumkan

atau diminimumkan terhadap kendala-kendala yang ada. Terdapat dua

kemungkinan fungsi tujuan yaitu,

1) Maksimumkan

2) Minimumkan

10
3. Fungsi Kendala

Fungsi Kendala adalah suatu pembatas terhadap variabel-variabel keputusan

yang dibuat. Kendala tersebut harus dituangkan ke dalam fungsi matematika

linear. Dapat disimpulkan bahwa program linear adalah sebuah metode

matematis yang berkarakteristik linear untuk menemukan suatu penyelesaian

optimal dengan cara memaksimumkan atau meminimumkan fungsi tujuan

terhadap satu susunan kendala.

Beberapa asumsi penggunaan pemrograman linear pada kehidupan nyata

yaitu (Ruminta, 2009 : 329):

1. Proporsionalitas

Kontribusi masing-masing variabel keputusan terhadap fungsi tujuan dan

pembatasan-pembatasan adalah proporsional langsung terhadap nilai variabel

keputusan.

2. Aditivitas

Kontribusi terhadap fungsi tujuan dan pembatasan-pembatasan untuk beberapa

variabel keputusan yang lain sehingga kontribusi masing-masing variabel

keputusan dapat digabungkan / ditambahkan menjadi kontribusi total.

3. Divisibilitas

Variabel keputusan adalah kontinu sehingga dapat diambil nilai fraksionalnya.

11
4. Deterministik

Semua parameter (fungsi tujuan, pembatasan-pembatasan, seluruh koefisien)

diketahui dengan pasti dan tetap tidak berubah selama dilakukan kajian dan

analisis.

Menurut Ruminta (2009 : 330), persoalan program linear adalah persoalan

optimasi yang memenuhi ketentuan berikut:

1. Fungsi tujuan merupakan fungsi linear dari variabel keputusan.

2. Nilai variabel keputusan harus memenuhi pembatasan-pembatasan. Setiap

pembatasan harus berbentuk persamaan atau ketidaksamaan linear.

3. Setiap variabel keputusan harus dibatasi yaitu non negatif.

Definisi 2.3 Fungsi Linear (Winston, 2004 : 52)

Fungsi merupakan fungsi linear jika dan hanya jika fungsi

dapat dituliskan , dengan

merupakan konstanta.

Contoh 2.1

Fungsi berikut merupakan fungsi linear:

Definisi 2.4 Fungsi Pertidaksamaan Linear (Winston, 2004 : 52)

Untuk sebarang fungsi linear dan sebarang bilangan ,

pertidaksamaan dan merupakan fungsi

pertidaksamaan linear.

12
Contoh 2.2

Fungsi berikut merupakan fungsi pertidaksamaan linear:

Ada beberapa persyaratan penting dalam merumuskan persoalan

pemrograman linear yaitu (Ruminta, 2009 : 331):

1. Ada beberapa kuantitas yang memungkinkan dioptimasi untuk digunakan

sebagai tujuan.

2. Ada variabel-variabel yang dapat dibuat variabel keputusan.

3. Ada pembatasan kemampuan dalam mencapai tujuan.

4. Ada langkah-langkah alternatif pemecahan yang dapat dipilih.

5. Tujuan dan pembatasan-pembatasan harus dapat diekspresikan dalam persamaan

atau ketidaksamaan linear.

Definisi 2.5 Pemrograman Linear (Susanta, 1994 : 6)

Diberikan fungsi merupakan fungsi linear, merupakan

variabel keputusan ke-j, dan merupakan konstanta-konstanta yang diketahui,

merupakan nilai ruas kanan dari persamaan kendala ke-m yang menunjukkan

nilai syarat kendala tersebut, umtuk setiap (indeks untuk jumlah

variabel kendala dan (indeks untuk jumlah variabel keputusan.

Secara umum, model pemrograman linear dirumuskan sebagai berikut:

Memaksimumkan / Meminimumkan : (2.1)

dengan kendala : dan (2.2)

13
 dalam hal ini, [ ], (2.3)

[ ] (2.4)

[ ], (2.5)

dan [ ] (2.6)

Matriks merupakan matriks satu kolom dari variabel-variabel yang dicari,

dan adalah matriks satu baris untuk setiap koefisien ongkos ( ). Matriks

merupakan matriks koefisien persamaan kendala, dan adalah matriks satu kolom

dari ruas kanan persamaan kendala. (Bronson & Naadimuthu, 1997 : 20)

Jika (2.1) dan (2.2) dituliskan dalam bentuk matriks menjadi:

Memaksimumkan / Meminimumkan : [ ][ ]

dengan kendala :

[ ][ ] [ ] , dan [ ]

Jika bentuk perkalian matriks tersebut diuraikan menjadi penjumlahan aljabar

akan menjadi:

14
 Memaksimumkan / Meminimumkan

∑ (2.7)

dengan kendala:

(2.8a)

(2.8b)

(2.8c)

(2.8d)

atau jika ditulis ulang, maka bentuk fungsi kendala (2.8a) - (2.8d) menjadi:

∑ dengan (2.9a)

dengan (2.9b)

D. Pemrograman Nonlinear

Pemrograman nonlinear adalah suatu teknik dalam masalah optimasi yang

mempunyai fungsi tujuan nonlinear dan fungsi kendala berbentuk nonlinear atau

linear. (Bazaraa et al, 2006 : 1).

Bentuk umum dari pemrograman nonlinear adalah menemukan nilai

, (Hiller & Lieberman, 2001 : 654) sehingga

Max / Min ,

dimana berupa fungsi non linear, (2.10a)

kendala , untuk setiap (2.10b)

dan (2.10c)

15
 Fungsi kendala dapat berupa fungsi nonlinear maupun fungsi linear.

Selain itu, dan fungsi adalah fungsi-fungsi dengan n variabel.

E. Quadratic Programming

Quadratic Programming adalah pendekatan penyelesaian permasalahan

optimasi nonlinear dimana kendalanya berupa fungsi linear dan fungsi tujuannya

merupakan kuadrat dari variabel keputusan ataupun perkalian dari dua variabel

keputusan (Hiller & Lieberman, 2001 : 665). Bentuk umum dari masalah quadratic

programming menurut Peressini et al (1988 : 258) yaitu:

Meminimumkan (2.11a)

Dengan kendala (2.11b)

Konsep matriks , , , dan sama seperti penjelasan pada (2.3) – (2.6).

adapun merupakan suatu konnstanta, sedangkan merupakan matriks simetris

yang tersusun dari nilai , dimana merupakan hasil dari turunan parsial kedua

terhadap dan dari fungsi tujuan. Matriks merupakan matriks simetris,

sehingga nilai . Bentuk (2.11a) dapat ditransformasikan menjadi berikut:

∑ ∑ ∑ (2.12)

Jika adalah matriks definit positif, merupakan fungsi konveks ketat,

dan fungsi kendala merupakan fungsi konveks, maka setiap nilai minimum dari

masalah tersebut merupakan minimum global (Rao, 1984 : 231).

16
F. Kondisi Karush Khun-Tucker

Model Karush Khun – Tucker dapat digunakan untuk menyelesaikan suatu

fungsi linear maupun non linear. Pada metode ini, program yang diselesaikan

merupakan program yang memiliki kendala pertidaksamaan. Metode Karush Khun –

Tucker merupakan pengembangan dari penyelesaian model nonlinear berkendala

persamaan yang dikerjakan dengan mencari titik-titik stasionernya, yaitu titik yang

berpotensi menjadi titik optimal.

Terdapat beberapa syarat Karush Khun – Tucker untuk masalah optimasi

berkendala. Syarat tersebut dirumuskan oleh Karush dan Khun – Tucker. Berikut

adalah teorema yang menjelasakan tentang syarat Karush Khun – Tucker untuk

masalah maksimum dan minimum.

Teorema 2.2. Syarat Karush Khun-Tucker masalah maksimum

(Winston, 2003 : 676)

Misalkan dan merupakan suatu masalah berpola

memaksimumkan. Jika merupakan suatu solusi optimal untuk

dan , maka merupakan fungsi nonlinear dan

terdapat pengali serta variabel slack sehingga memenuhi

1. ∑

2. [ ]

3. ∑

4.

17
5.

Teorema 2.3. Syarat Karush Khun-Tucker masalah minimum (Winston,

2003 : 676)

Misalkan dan merupakan suatu masalah berpola

meminimumkan. Jika merupakan suatu solusi optimal untuk

dan , maka merupakan fungsi nonlinear dan

terdapat pengali serta variabel surplus sehingga

memenuhi

1. ∑

2. [ ]

3. ( ∑ )

4.

5.

Pada syarat kedua dari Teorema 2.2 dan Teorema 2.3 berakibat

. Hal ini dapat dilihat pada saat , sehingga [ ] . Berdasarkan

bentuk umum fungsi kendala, maka [ ] yaitu .

Permasalahan pada quadratic programming dapat diselesaikan dengan

menggunakan persyaratan Khun-Tucker seperti yang tertera pada Teorema 2.2 dan

Teorema 2.3. Selain itu, dalam quadratic programming juga terdapat kondisi

complementary slackness khusus.

18
 Secara umum, kondisi complementary slackness pada quadratic

programming dapat dinyatakan dalam Sifat 2.1 sebagai berikut:

Sifat 2.1. Complementary slackness pada quadratic programming

(Winston, 2003 : 687)

1. dan pada kondisi Khun-Tucker dan tidak dapat kedua-duanya

bernilai positif.

2. Variabel surplus (excess) ataupun slack untuk kendala ke-i dan tidak

dapat kedua-duanya bernilai positif.

Bukti Sifat 2.1:

1. Diperhatikan Syarat 1) dan 3) pada Teorema 2.2, yaitu:

Syarat 1) yaitu : ∑ sehingga

∑ disubtitusikan ke Syarat 3)

( ∑ )

Jika maka , yaitu .

Jika maka , yaitu atau . Berdasarkan Syarat

5) maka .

Hal ini berlaku juga untuk Teorema 2.3, sehingga terbukti bahwa dan

pada kondisi Khun-Tucker dan tidak dapat kedua-duanya bernilai

positif.

19
 2. Diperhatikan Syarat 2) yaitu [ ]

Pada fungsi kendala maka bentuk kanonik kendala tersebut

yaitu , sehingga syarat 2) menjadi:

Jika maka , yaitu .

Jika maka , yaitu atau . Berdasarkan Syarat 5)

maka .

Pada fungsi kendala dapat diubah menjadi .

Melalui cara yang sama maka didapat pula , sehingga terbukti bahwa

variabel surplus (excess) ataupun slack untuk kendala ke-i dan tidak dapat kedua-

duanya bernilai positif.

G. Algoritma Genetika

Algoritma Genetika merupakan suatu metode algoritma pencarian

berdasarkan pada mekanisme seleksi alam dan genetik alam (Kusumadewi, 2003 :

87). Algoritma Genetika terinspirasi oleh proses biologi dari teori evolusi Darwin,

sehingga banyak istilah dan konsep biologi yang digunakan dalam Algoritma

Genetika (Chambers, 2000 : 13).

Algoritma Genetika muncul dari teori-teori dalam buku biologi, sehingga

banyak istilah dan konsep biologi yang digunakan. Proses-proses yang terjadi dalam

Algoritma Genetika juga tidak jauh berbeda dengan apa yang terjadi pada evolusi

biologi. Sekumpulan individu yang sama, yang disebut spesies, hidup, berproduksi

20
dan mati dalam satu area yang disebut populasi. Jika anggota-anggota populasi

(individu) terpisah, misalnya karena terjadi banjir atau gempa, maka individu-

individu tersebut akan membentuk beberapa populasi yang terpisah. Setelah

beberapa waktu akan terjadi proses pembentukan spesies baru atau dikenal dengan

istilah speciation dan juga terjadi perubahan hereditas (heredity) secara bertahap

yang membentuk ciri-ciri baru pada spesies tersebut. Sebagai contoh, spesies

pemangsa mengalami perubahan bertahap sehingga memiliki gigi taring yang lebih

panjang dan tajam (Suyanto, 2005 : 1).

Algoritma Genetika merupakan teknik pencarian yang didasarkan atas

mekanisme seleksi genetik natural. Algoritma genetika berbeda dengan teknik

pencarian konvensional. Algoritma genetika dimulai dari himpunan solusi yang pada

umumnya dihasilkan secara acak. Himpunan ini disebut populasi, sedangkan setiap

individu dalam populasi disebut kromosom (merupakan representasi dari solusi) dan

yang menempati kromosom disebut gen dan nilainya dapat berupa bilangan numerik,

bilangan biner, simbol ataupun sebuah karakter dari permasalahan yang ingin

diselesaikan (Gen & Cheng, 2000 : 1).

Pada setiap generasi, kromosom akan melalui proses evaluasi dengan

menggunakan alat ukur yang disebut dengan fungsi fitness (kebugaran). Nilai fitness

dari suatu kromosom akan menunjukkan kualitas dari kromosom dalam populasi

tersebut (Zukhri, 2014 : 23). Generasi berikutnya dikenal dengan istilah anak

(offspring) terbentuk dari gabungan dua kromosom generasi sekarang yang bertindak

sebagai induk (parent) dengan menggunakan operator penyilangan (crossover).

21
Selain operator penyilangan, suatu kromosom dapat pula dimodifikasi dengan

menggunakan operator mutasi (mutation) dengan harapan akan menghasilkan

kromosom baru dengan tingkat fitness lebih tinggi sebagai generasi baru atau

keturunan (offspring) berikutnya. Setelah beberapa generasi maka algoritma genetika

akan konvergen pada kromosom terbaik, yang diharapkan merupakan solusi optimal

(Goldberg, 1989 : 71).

Menurut Gen dan Cheng ada tiga kelebihan dari Algorima Genetika dalam

proses pencarian nilai optimal (Zukhri, 2014 : 11), yaitu:

1. Algoritma Genetika hanya memerlukan sedikit perhitungan matematis yang

berhubungan dengan masalah yang ingin diselesaikan.

2. Operasi evolusi dari Algoritma Genetika sangat efektif untuk mengobservasi

posisi global secara acak.

3. Algoritma genetika memiliki fleksibilitas untuk diimplementasikan secara

efisien pada problematika tertentu.

Hal-hal yang terdapat dalam Algoritma Genetika adalah sebagai berikut

(Weise, 2009):

a. Gen (Genotype) adalah sebuah nilai yang menyatakan satuan dasar yang

membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan

kromosom.

b. Allele yaitu nilai dari sebuah gen, dapat berupa bilangan biner, float, integer,

karakter, dan kombinatorial.

c. Kromosom adalah gabungan gen-gen yang membentuk nilai tertentu.

22
d. Individu merupakan suatu nilai atau keadaan yang menyatakan salah satu solusi

yang mungkin dari permasalahan yang diangkat.

e. Populasi merupakan sekumpulan individu yang akan diproses bersama dalam

satu siklus proses evolusi. Populasi terdiri dari sekumpulan kromosom.

f. Induk adalah kromosom yang akan dikenai operasi genetik pindah silang.

g. Pindah silang merupakan operasi genetik yang mewakili proses

perkembangbiakan antar individu.

h. Offspring adalah kromosom yang merupakan hasil dari operasi genetik pindah

silang yang dikenal keturunan atau sebagai anak.

i. Mutasi merupakan operasi genetik yang mewakili proses mutasi dalam

perjalanan hidup individu. Mutasi berperan menghasilkan perubahan acak dalam

populasi, yang berguna untuk menambah variasi dari kromosom-kromosom

dalam sebuah populasi.

j. Proses seleksi merupakan proses yang mewakili proses seleksi alam (natural

selection) dari teori Darwin. Proses ini dilakukan untuk menentukan induk dari

operasi genetik pindah silang yang akan dilakukan untuk menghasilkan

keturunan (offspring).

k. Nilai fitness merupakan penilaian yang menentukan bagus tidaknya sebuah

kromosom.

l. Fungsi Evaluasi adalah fungsi yang digunakan untuk menentukan nilai fitness.

Fungsi evaluasi ini merupakan sekumpulan kriteria-kriteria tertentu dari

permasalahan yang ingin diselesaikan.

23
m. Generasi merupakan satuan dari populasi setelah mengalami operasi-operasi

genetika, berkembang biak, dan menghasilkan keturunan. Pada akhir dari setiap

generasi, untuk menjaga jumlah kromosom dalam populasi tetap konstan,

kromosom-kromosom yang mempunyai nilai fitness yang rendah dan memiliki

peringkat dibawah nilai minimal akan dihapus dari populasi.

Algoritma Genetika sangat tepat jika digunakan untuk menyelesaikan

masalah optimasi yang kompleks dan sukar diselesaikan dengan menggunakan

metode konvensional (Supriyanto, 2010 : 4). Sebagaimana halnya dengan proses

evolusi di alam, suatu algoritma genetikayang sederhana umumnya terdiri dari tiga

operasi, yaitu: operasi seleksi, operasi crossover (persilangan), dan operasi mutasi.

Struktur umum dari suatu Algoritma Genetika terdiri dari langkah-langkah:

a. Membangkitkan Populasi Awal

Diawali dengan membangkitkan sejumlah individu secara acak atau melalui

prosedur tertentu. Ukuran populasi tergantung pada masalah yang akan dipecahkan

dan jenis operator genetika yang akan diimplementasikan. Setelah ukuran populasi

ditentukan, kemudian dilakukan inisialisasi terhadap kromosom yang terdapat pada

populasi tersebut. Inisialisasi kromosom dilakukan secara acak, namun demikian

harus tetap memperhatikan domain solusi dan kendala permasalahan yang ada

(Kusumadewi, 2003 : 282).

Proses pembangkitan populasi awal diawali dari pengkodean gen dari

kromosom. Satu gen biasanya merepresentasikan satu variabel. Gen dapat diwakili

dalam bentuk bilangan real, bit, daftar aturan, elemen permutasi, elemen program,

24
atau representasi lainnya yang dapat diimplementasikan untuk operator genetika.

Teknik pengkodean ini tergantung pada pemecahan masalah yang dihadapi seperti

bilangan acak, pendekatan tertentu, dan permutasi gen.

b. Seleksi

Seleksi merupakan pemilihan dua buah kromosom untuk dijadikan sebagai

induk yang dilakukan secara proporsional sesuai dengan nilai fitness-nya

(Michalewics, 1996 : 75). Seleksi digunakan untuk memilih individu-individu mana

saja yang akan dipilih untuk proses crossover dan mutasi. Masing-masing individu

yang diseleksi akan diberikan probabilitas reproduksi tergantung dari nilai objektif

dirinya sendiri terhadap nilai objektif dari semua individu dalam seleksi tersebut.

Nilai fitness inilah yang nantinya akan digunakan pada tahap seleksi berikutnya.

Untuk itu dapat digunakan rumus sebagai berikut :

(2.13)

Fungsi objektif perlu ditambah 1 untuk menghindari kesalahan yang diakibatkan

pembagian oleh 0. Semakin tinggi nilai fitness suatu individu semakin besar

kemungkinannya untuk dipilih.

Masing-masing individu dalam wadah seleksi akan menerima probabilitas yang

tergantung pada nilai fitness-nya. Selanjutnya akan dicari nilai probabilitasnya

dengan rumus sebagai berikut:

(2.14)

Cara untuk mencari nilai kumulatif probabilitas adalah sebagai berikut:

25
 ∑ (2.15)

Setelah didapat nilai probabilitasnya selanjutnya dihitung komulatif

probabilitasnya. Proses seleksi menggunakan roulete-wheel dilakukan setelah

didapatkan nilai komulatif probabilitas. Prosesnya adalah dengan membangkitkan

bilangan acak dalam range 0 – 1.

Jika maka pilih kromosom ke-k sebagai induk. (2.16)

c. Crossover

Pindah silang (Crossover) adalah operator dari algoritma genetika yang

melibatkan dua induk untuk membentuk kromosom baru. Crossover menghasilkan

keturunan baru dalam ruang pencarian yang siap diuji. Operasi ini tidak selalu

dilakukan pada setiap individu yang ada. Individu dipilih secara acak untuk

dilakukan crossover dengan parameter crossover probability antara 0,6 – 0,95.

Jika crossover tidak dilakukan maka nilai dari induk akan diturunkan kepada

keturunan (Michalewicz, 1996 : 78).

Prinsip dari crossover adalah melakukan operasi genetika (pertukaran,

aritmatika) pada gen-gen yang bersesuaian dari dua induk untuk menghasilkan

indivadu baru. Crossover dilakukan pada setiap individu dengan probabilitas

crossover yang telah ditentukan.

d. Mutasi

Mutasi merupakan proses untuk mengubah nilai dari satu atau beberapa gen

dalam suatu kromosom. Operasi mutasi yang dilakukan pada kromosom dengan

26
tujuan untuk memperoleh kromosom-kromosom baru sebagai kandidat solusi pada

generasi mendatangdengan fitness yang lebih baik, dan lama kelamaan menuju solusi

optimum yang diinginkan. Akan tetapi, untuk mencapai hal ini penekanan selektif

juga memegang peranan yang penting. Jika dalam proses pemilihan kromosom-

kromosom cenderung terus pada kromosom yang memiliki fitness yang tinggi saja,

konvergensi prematur akan sangat mudah terjadi (Murniati, 2009 : 24).

Jumlah kromosom yang mengalami mutasi dalam satu populasi ditentukan oleh

parameter mutation probability . Pada umumnya nilainya adalah (Supriyanto,

2010 : 10). Proses mutasi dilakukan dengan cara mengganti satu gen yang terpilih

secara acak dengan suatu nilai baru yang didapat secara acak. Langkah pertama

adalah menghitung panjang total gen yang ada dalam satu populasi.

(2.17)

Jika peluang mutasi terlalu kecil, banyak gen yang mungkin berguna tidak

pernah dievaluasi. Tetapi jika peluang mutasi terlalu besar, maka akan terlalu banyak

gangguan acak, sehingga anak akan kehilangan kemiripan dari induknya dan

algoritme kehilangan kemampuan untuk belajar dan melakukan pencarian.

e. Evaluasi Solusi

Langkah ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness

dari setiap kromosom hingga kriteria menjadi terpenuhi. Namun karena seleksi

dilakukan secara acak maka diperlukan langkah untuk menjaga agar individu bernilai

fitness terbaik tidak hilang selama proses evolusi. Proses ini dikenal dengan nama

27
etilism (Kusumadewi, 2003 : 112). Bila kriteria berhenti belum terpenuhi maka akan

dibentuk lagi generasi baru dengan mengulangi langkah sebelumnya tetapi tetap

menyertakan individu yang disimpan dalam proses etilism sehingga hasil perhitungan

dapat konvergen. Beberapa kriteria berhenti menurut Sukmawan (2003 : 25) adalah

sebagai berikut:

1. Berhenti pada generasi tertentu.

2. Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai

fitness tertinggi / terendah yang tidak berubah.

3. Berhenti bila dalam n generasi berikutnya tidak diperoleh nilai fitness yang

lebih tinggi / rendah.

Pada umumnya proses Algoritma Genetika untuk mendapatkan hasil optimal

membutuhkan proses pengulangan yang cukup panjang.

Selanjutnya, diberikan contoh pennyelesaian pemrograman nonlinier

menggunakan metode quadratic programming dengan algoritma genetika. Berikut

gambaran umum penyelesaian pemrograman nonlinear menggunakan metode

quadratic programming dengan algoritma genetika.

Contoh 2.1

Meminimumkan fungsi :

(2.16)

dengan kendala :

(2.17a)

(2.17b)

28
 (2.17c)

(2.17d)

Penyelesaian:

a. Pembentukan model nonlinear menggunakan quadratic programming

Persamaan (2.16) dan (2.17) perlu diidentifikasi menjadi bentuk umum

quadratic programming yang tertera pada persamaan (2.10) dan (2.11) sebagai

berikut:

Persamaan (2.16) dapat ditentukan :

Matriks merupakan matriks baris koefisien-koefisien dari sehingga:

[ ],

Matriks adalah matriks kolom untuk variabel-variabel keputusan, sehingga

[ ].

Matriks merupakan matriks simetris dengan merupakan turunan kedua dari ,

merupakan turunan kedua dari , dan merupakan turunan kedua dari ,

sehingga matriks :

[ ] [ ]

29
 [ ][ ] [ ][ ][ ]

Bentuk Kendala (2.17) kemudian disesuaikan dengan persamaan (2.11) menjadi:

Tampak bahwa Persamaan (2.16) dan (2.17) memenuhi bentuk persamaan

(2.10) dan (2.11). Selanjutnya, akan dilihat apakah persamaan (2.16) dan (2.17)

menghasilkan minimum global jika diselesaikan menggunakan metode quadratic

programming dengan algoritma genetika, yaitu dengan melihat turunan parsialnya.

Diperoleh turunan parsial kedua dari persamaan (2.16) adalah sebagai berikut :

dan turunan pertama dari Persamaan (2.17) adalah sebagai berikut:

30
 Terlihat bahwa , maka berdasarkan Tabel 2.1 fungsi

merupakan fungsi koveks ketat, sedangkan , maka menurut Definisi

2.2 merupakan fungsi konveks. Karena merupakan fungsi konveks dan

meriupakan fungsi konveks maka minimum lokal yang dihasilkan dari permasalahan

tersebut merupakan minimum global (Rao, 1984 : 231). Sehingga, persamaan (2.16)

cukup diselesaikan dengan quadratic programming menggunakan metode Khun-

Tucker untuk mencari nilai minimum global (Rao, 1984 : 98).

Langkah-langkah penyelesaian dengan quadratic programming adalah

sebagai berikut:

1. Menentukan kondisi Khun Tucker

Berdasarkan Teorema 2.3 maka persamaan (2.16) dapat ditentukan syarat Khun

Tucker-nya yaitu:

1) (2.18a)

(2.18b)

(2.18c)

2) [ ] (2.19a)

[ ] (2.19b)

[ ] (2.19c)

31
3) (2.20a)

(2.20b)

(2.20c)

4) (2.21)

5) (2.22)

Sebagai akibat dari (2.19) maka:

(2.23a)

(2.23b)

(2.23c)

Bentuk (2.23) dapat dijadikan bentuk kanonik sehingga menjadi:

(2.24a)

(2.24b)

(2.24c)

Setelah mengidentifikasi syarat Khun Tucker, maka kondisi Khun Tucker untuk

persamaan (2.16) dan (2.17) yaitu:

(2.18a)

(2.18b)

(2.18c)

(2.24a)

(2.24b)

32
 (2.24c)

2. Mengidentifikasi complementary slackness

Berdasarkan (2.19) dan (2.24), (2.18) dan (2.22), dan Sifat 2.1, maka kondisi

complementary slackness untuk persamaan (2.16) adalah:

3. Menambahkan variabel buatan untuk setiap kondisi Khun Tucker yang tidak

memiliki variabel basis

Persamaan (2.18) dan (2.24) tidak ada yang memiliki basis sehingga semuanya

ditambahkan variabel buatan sehingga bentuknya menjadi:

(2.25a)

(2.25b)

(2.25c)

(2.25d)

(2.25e)

(2.25f)

Semua variabel non negatif.

4. Menentukan fungsi tujuan baru yang linear

Bentuk fungsi linear baru yang linear untuk Contoh diatas adalah

33
 Meminimumkan

(2.26)

Dengan kendala:

(2.25a)

(2.25b)

(2.25c)

(2.25d)

(2.25e)

(2.25f)

Semua variabel non negatif.

b. Penyelesaian model linear menggunakan Algoritma Genetika

Setelah mendapat fungsi (2.26) dan kendala (2.25) linear menggunakan

metode quadratic programming, selanjutnya dilakukan penyelesaian model linear

dengan algoritma genetika adalah sebagai berikut:

1. Generasi pertama

a. Membangkitkan populasi awal

Karena yang dicari adalah nilai maka variabel tersebut

dijadikan sebagai gen-gen pembentuk kromosom , sehingga ditentukan gen yang

digunakan sebanyak nilai yang akan dicari yaitu 18. Selanjutnya proses inisialisasi

dilakukan dengan cara memberikan nilai awal gen-gen dengan nilai acak sesuai

34
batasan yang telah ditentukan. Pada permasalahan ini jumlah populasi di tentukan

sebanyak 18 sebagai berikut:

Kromosom (1) [ ]

Kromosom (2) [ ]

Kromosom (3) [ ]

Kromosom (4) [ ]

Kromosom (5) [ ]

Kromosom (6) [ ]

10]

35
Kromosom (7) [ ]

Kromosom (8) [ ]

Kromosom (9) [ ]

Kromosom (10) [

Kromosom (11) [

Kromosom (12) [

36
Kromosom (13) [

Kromosom (14) [

Kromosom (15) [

Kromosom (16) [

Kromosom (17) [

Kromosom (18) [

37
 ]

b. Seleksi

Permasalahan yang ingin diselesaikan adalah nilai variabel

yang meminimumkan , maka fungsi objektif yang

dapat digunakan untuk mendapatkan solusi adalah fungsi objektif (kromosom) =

Perhitungan nilai fungsi objektif dari kromosom yang telah dibangkitkan

adalah sebagai berikut:

(kromosom 1) = 33

(kromosom 2) = 49

(kromosom 3) = 61

(kromosom 4) = 57

(kromosom 5) = 45

(kromosom 6) = 33

(kromosom 7) = 52

(kromosom 8) = 57

(kromosom 9) = 72

(kromosom 10) = 47

(kromosom 11) = 76

38
 (kromosom 12) = 68

(kromosom 13) = 48

(kromosom 14) = 28

(kromosom 15) = 65

(kromosom 16) = 41

(kromosom 17) = 76

(kromosom 18) = 43

Rata-rata dari fungsi objektif adalah : 52,83

Proses seleksi dilakukan dengan cara membuat kromosom yang mempunyai

nilai fungsi objektif kecil mempunyai kemungkinan terpilih yang besar. Untuk itu

dapat digunakan fungsi fitness sesuai dengan persamaan (2.13). Sehingga didapat

nilai fitness sebagai berikut:

Fitness 1 = 0,0294

Fitness 2 = 0,0200

Fitness 3 = 0,0161

Fitness 4 = 0,0172

Fitness 5 = 0,0217

Fitness 6 = 0,0294

Fitness 7 = 0,0189

Fitness 8 = 0,0172

Fitness 9 = 0,0137

39
 Fitness 10 = 0,0208

Fitness 11 = 0,0130

Fitness 12 = 0,0145

Fitness 13 = 0,0204

Fitness 14 = 0,0345

Fitness 15 = 0,0152

Fitness 16 = 0,0238

Fitness 17 = 0,0130

Fitness 18 = 0,0227

Total fitness = 0,3615

Tahap selanjutnya adalah mencari probabilitas terpilih. Dilakukan

perhitungan menggunakan persamaan (2.14), dan didapat hasil sebagai berikut:

40
 Berdasarkan hasil perhitungan diatas, didapatkan kromosom ke-14 yang

mempunyai fitness paling besar maka kromosom tersebut mempunyai probabilitas

untuk terpilih pada generasi selanjutnya lebih besar dari kromosom lainnya. Untuk

41
proses seleksi digunakan roulette wheel, untuk itu dicari nilai kumulatif

probabilitasnya menggunakan persamaan (2.15) sebagai berikut:

42
 Setelah dihitung komulatif probabilitasnya maka proses seleksi

menggunakan roulette wheel dapat dilakukan. Putar roulette wheel sebanyak jumlah

populasi yaitu 18 kali (bangkitkan bilangan acak R antara 0 sampai 1 sebanyak 18)

dan pada tiap putaran pilih satu kromosom untuk populasi baru. Misal didapatkan

bilangan acak sebagai berikut:

43
 Berdasarkan persamaan (2.16), kromosom baru yang menjadi induk adalah

bilangan acak pertama R(1) lebih besar dari C(13) dan lebih kecil daripada C(14),

maka pilih kromosom (14) sebagai kromosom pada populasi baru dari bilangan acak

yang telah dibangkitkan diatas, maka populasi kromosom baru hasil proses seleksi

adalah sebagai berikut:

Kromosom (1) = Kromosom (14)

Kromosom (2) = Kromosom (4)

Kromosom (3) = Kromosom (13)

Kromosom (4) = Kromosom (1)

Kromosom (5) = Kromosom (10)

Kromosom (6) = Kromosom (4)

Kromosom (7) = Kromosom (17)

Kromosom (8) = Kromosom (12)

Kromosom (9) = Kromosom (18)

Kromosom (10) = Kromosom (18)

Kromosom (11) = Kromosom (7)

Kromosom (12) = Kromosom (11)

Kromosom (13) = Kromosom (18)

Kromosom (14) = Kromosom (9)

Kromosom (15) = Kromosom (2)

44
Kromosom (16) = Kromosom (6)

Kromosom (17) = Kromosom (13)

Kromosom (18) = Kromosom (2)

Kromosom baru hasil proses seleksi adalah:

Kromosom (1) [

Kromosom (2) [

Kromosom (3) [

Kromosom (4) [

Kromosom (5) [

Kromosom (6) [

Kromosom (7) [

Kromosom (8) [

Kromosom (9) [

45
 ]

Kromosom (10) [

Kromosom (11) [

Kromosom (12) [

Kromosom (13) [

Kromosom (14) [

Kromosom (15) [

Kromosom (16) [

10]

Kromosom (17) [

Kromosom (18) [

c. Crossover

46
 Setelah proses seleksi maka proses selanjutnya adalah proses crossover.

Metode yang digunakan salah satunya adalah one-cut point, yaitu memilih secara

acak satu posisi dalam kromosom induk kemudian saling menukar gen. Kromosom

yang dijadikan induk dipilih secara acak dan jumlah kromosom yang mengalami

crossover dipengaruhi oleh crossover probability . Pada umumnya

ditentukan mendekati 1, misalnya 0,8 (Suyanto, 2005).

Misal ditentukan crossover probability adalah sebesar 0,8. Proses

selanjutnya adalah dengan membangkitkan bilangan acak R antara 0 dan 1 sebanyak

populasi yaitu 18 dan didapat bilangan acak sebagai berikut:

47
 Kromosom ke-k akan dipilih sebagai induk jika , dari bilangan

acak yang telah dibangkitkan. Sehingga kromosom yang menjadi induk adalah

kromosom (2), kromosom (3), kromosom (4), kromosom (5), kromosom (7),

kromosom (8), kromosom (9), kromosom (10), kromosom (12), kromosom (13),

kromosom (14), dan kromosom (16).

Setelah melakukan pemilihan induk, proses selanjutnya adalah menentukan

posisi Posisi cut-point crossover. Posisi cut-point crossover dipilih menggunakan

bilangan acak 1 – (panjang kromosom – 1), dalam persoalan ini berarti dipilih

bilangan acak 1-17 sebanyak jumlah crossover yang terjadi yaitu 12. Sehingga

didapat posisi cut-point crossover sebagai berikut:

48
 Setelah menentukan posisi cut-point crossover, selanjutnya akan dibentuk

populasi kromosom setelah mengalami crossover. Dengan demikian populasi

kromosom yang mengalami crossover adalah:

Offspring (1) diisi dengan cara melihat nilai C(1). Karena C(1) = 3, maka

diambil 3 gen pertama dari kromosom (2), sedangkan gen selanjutnya diambil dari

kromosom (3). Hal yang sama juga berlaku untuk offspring selanjutnya. Sehingga

offspring yang terbentuk adalah

Offspring (1) = Kromosom (2) >< Kromosom (3)

Offspring (2) = Kromosom (3) >< Kromosom (4)

Offspring (3) = Kromosom (4) >< Kromosom (5)

49
 [

Offspring (4) = Kromosom (5) >< Kromosom (7)

Offspring (5) = Kromosom (7) >< Kromosom (8)

Offspring (6) = Kromosom (8) >< Kromosom (9)

Offspring (7) = Kromosom (9) >< Kromosom (10)

Offspring (8) = Kromosom (10) >< Kromosom (12)

Offspring (9) = Kromosom (12) >< Kromosom (13)

Offspring (10) = Kromosom (13) >< Kromosom (14)

50
 [

Offspring (11) = Kromosom (14) >< Kromosom (16)

10]

Offspring (12) = Kromosom (16) >< Kromosom (2)

Hasil crossover menjadi kromosom baru, sedangkan kromosom yang tidak

menggalami crossover tetap digunakan untuk membentuk populasi. Dengan

demikian populasi kromosom setelah mengalami proses crossover adalah:

Kromosom (1) [

Kromosom (2) [

Kromosom (3) [

Kromosom (4) [

Kromosom (5) [

51
Kromosom (6) [

Kromosom (7) [

Kromosom (8) [

Kromosom (9) [

Kromosom (10) [

Kromosom (11) [

Kromosom (12) [

Kromosom (13) [

Kromosom (14) [

10]

Kromosom (15) [

Kromosom (16) [

52
 ]

Kromosom (17) [

Kromosom (18) [

d. Mutasi

Langkah pertama untuk menentukan kromosom yang mengalami mutasi

adalah dengan menghitung panjang total gen yang ada dalam satu populasi. Dalam

kasus ini panjang total gen sesuai dengan persamaan (2.15) adalah .

Untuk memilih posisi gen yang mengalami mutasi dilakukan dengan

membangkitkan bilangan integer acak antara 1 sampai total gen, yaitu 1 sampai 324.

Jika bilangan acak yang dibangkitkan lebih kecil daripada parameter mutation

probability maka pilih posisi tersebut sebagai sub-kromosom yang mengalami

mutasi. Misal kita tentukan 0,05 maka kemungkinan ada 5 % dari total gen yang

mengalami mutasi. Sehingga didapat jumlah mutasi =

(dibulatkan menjadi 16).

Setelah membangkitkan bilangan acak antara 1 sampai 324 sebanyak 16

untuk memilih posisi gen yang mengalami mutasi dan membangkitkan bilangan acak

1 sampai 18 sebanyak 16 untuk menggantikan gen yang mengalami mutasi maka

didapat bilangan acak sebagai berikut:

53
 Tabel 2.2. Bilangan Acak untuk Mutasi Generasi Pertama

Posisi Bilangan Acak

Gen Pengganti
16 17
24 5
25 11
61 10
69 9
76 9
102 15
109 5
119 16
172 15
178 13
206 13
215 6
234 8
249 8
297 9
Dari tabel 2.2, diketahui bilangan acak pertama yang dibangkitkan terpilih

posisi gen 16 yang mengalami mutasi. Dengan demikian yang akan mengalami

mutasi adalah kromosom ke-1 gen nomor 16. Maka nilai gen pada posisi tersebut

diganti dengan bilangan acak antara 1-18 yang sudah tercantum pada tabel 2.2 yaitu

17. Begitu seterusnya hingga bilangan acak terakhir yang telah dibangkitkan.

Sehingga kromosom yang telah mengalami mutasi sebagai berikut:

Kromosom (1) [

Kromosom (2) [

Kromosom (3) [

54
 ]

Kromosom (4) [

Kromosom (5) [

Kromosom (6) [

Kromosom (7) [

Kromosom (8) [

Kromosom (9) [

Kromosom (10) [

Kromosom (11) [

Kromosom (12) [

Kromosom (13) [

55
 Kromosom (14) [

10]

Kromosom (15) [

Kromosom (16) [

Kromosom (17) [

Kromosom (18) [

Setelah proses mutasi, maka telah diselesaikan satu iterasi dalam algoritma

genetika atau disebut satu generasi dan didapatkan:

Kromosom (1) [

Kromosom (2) [

Kromosom (3) [

Kromosom (4) [

Kromosom (5) [

56
 ]

Kromosom (6) [

Kromosom (7) [

Kromosom (8) [

Kromosom (9) [

Kromosom (10) [

Kromosom (11) [

Kromosom (12) [

Kromosom (13) [

Kromosom (14) [

10]

Kromosom (15) [

57
 Kromosom (16) [

Kromosom (17) [

Kromosom (18) [

e. Evaluasi

Selanjutnya akan diperiksa fungsi objektif setelah 1 generasi. Dan

didapatkan hasil sebagai berikut:

(kromosom 1) = 28

(kromosom 2) = 39

(kromosom 3) = 55

(kromosom 4) = 33

(kromosom 5) = 39

(kromosom 6) = 57

(kromosom 7) = 77

(kromosom 8) = 68

(kromosom 9) = 43

(kromosom 10) = 43

(kromosom 11) = 52

(kromosom 12) = 66

58
 (kromosom 13) = 43

(kromosom 14) = 79

(kromosom 15) = 49

(kromosom 16) = 33

(kromosom 17) = 48

(kromosom 18) = 49

Rata-rata dari fungsi objektif adalah : 50,06

Dapat dilihat dari hasil perhitungan fungsi objektif diatas bahwa setelah satu

generasi, nilai hasil rata-rata fungsi objektif mengalami penurunan dibandingkan

hasil rata-rata fungsi objektif pada saat sebelum mengalami seleksi crossover dan

mutasi. Hal ini menunjukkan bahwa kromosom atau solusi yang dihasilkan setelah

satu generasi lebih baik dibandingkan generasi sebelumya.

Selanjutnya generasi baru yang telah terbentuk akan mengalami proses yang

sama seperti generasi sebelumya yaitu proses evaluasi, seleksi, crossover, dan mutasi

yang kemudian akan menghasilkan kromosom-kromosom baru untuk generasi yang

selanjutnya. Proses ini akan berulang sampai mendapatkan generasi terbaik atau akan

berhenti setelah sejumlah generasi yang telah ditetapkan sebelumya.

Penyelesaian model linear dengan algoritma genetika selanjutnya dilakukan

menggunakan software Matlab. Optimisasi Algoritma default dari Matlab merupakan

optimisasi meminimumkan. Beberapa komponen Algoritma Genetika yang telah di

59
set oleh Matlab yaitu jumlah populasi sebanyak 20, seleksi menggunakan metode

roulette, crossover probability ( ) = 0,8 dan mutation probability ( ).

Hasil yang diperoleh dari perhitungan menggunakan software matlab

(Lampiran 2) yaitu , , dan . Sehingga nilai minimum untuk

fungsi nonlinear yaitu:

60