OPTIMASI FUNGSI TANPA KENDALA DENGAN ALGORITMA GENETIKA

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

OPTIMASI FUNGSI TANPA KENDALA DENGAN ALGORITMA GENETIKA SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Disusun Oleh: Yolenta Asri Astuti Prany NIM : 023114002

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SANATA DHARMA YOGYAKARTA 2007






ABSTRAK

Secara umum, permasalahan optimasi dalam kehidupan sehari – hari lebih sering menggunakan pemrograman linear, karena lebih mudah untuk diselesaikan dari pada dengan menggunakan pemrograman tak linear. Karena pemrograman tak linear selalu menimbulkan kesulitan dalam penanganan analitik dan numerik (teknik konvensional), bahkan untuk fungsi dua variabel pun terkadang sulit untuk diselesaikan. Algoritma Genetika merupakan salah satu teknik yang dapat dipilih untuk menyelesaikan permasalahan pemrograman tak linear tersebut, karena Algoritma Genetika merupakan teknik pencarian stokastik dengan sistem pencarian berdasarkan mekanisme genetika dalam biologi. Pada skripsi ini, generasi baru (anak) terbentuk dari rekombinasi dan mutasi dengan menggunakan metode pemotongan satu titik. Pemilihan anak pada proses rekombinasi atau mutasi dilakukan secara acak. Dari percobaan, solusi optimal akan lebih mendekati dengan nilai konvensionalnya pada probabilitas rekombinasi 0.5 dengan probabilitas mutasi 0.08. Namun, probabilitas tersebut tidak mutlak, karena Algoritma Genetika menggunakan teknik pencarian secara acak.

vi


ABSTRACT

Generally, the optimization problems in daily life is more regular using the linear programming, because it is easier to solved than nonlinear programming. Because nonlinear programming are difficultly in analytic handling and numeric (conventional technique), even for two variables function it is difficult to be solved, sometimes. Genetic Algorithm are one of technique that could be chosen to solved it, because Genetic Algorithm are stochastic search techniques based on the mechanism of genetic on biology. On this mini thesis, a new generation (offspring) formed of crossover or mutation with one cut point method. Selection of new generation by crossover and mutation conducted at random. According to the experiments, it is visible to get the optimal solution close to a value by conventional with crossover probabilities 0.5 and mutation probabilities 0.08. But, that is not absolute, because the searching technique of Genetic Algorithm are randomly.

vii


KATA PENGANTAR

Puji syukur kepada Bapa di Surga dan Bunda Maria yang memberikan kasih-Nya dan melimpahkan karunia-Nya sehingga penulisan skripsi ini dapat diselesaikan. Skripsi ini disusun dalam rangka menyelesaikan pendidikan tingkat Sarjana Strata Satu Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sanata Dharma Yogyakarta. Penulis dalam menyusun skripsi ini dari awal sampai akhir mendapatkan dukungan dan bantuan dari berbagai pihak. Oleh karena itu, pada kesempatan ini penulis menyampaikan ucapan terima kasih yang sebesar-besarnya kepada: 1. Bapak Ig. Aris Dwiatmoko, M.Si selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sanata Dharma Yogyakarta. 2. Bapak Drs. HJ Haris Sriwindono, M.Kom selaku Dosen Pembimbing I dan Bapak Y.G Hartono, S.Si selaku Dosen Pembimbing II yang dengan sabar telah banyak membimbing dan memberikan petunjuk dalam penyusunan skripsi ini. 3. Bapak dan Ibu dosen yang telah memberikan ilmu dan pengetahuan selama masa perkuliahan. 4. Staff fakultas MIPA terima kasih atas dorongan dan pelayanan yang telah diberikan. 5. Bapak dan Mama yang telah memberikan kasih, dorongan semangat, serta doa yang melimpah selama kehidupanku di dunia ini.

viii


6. Abang dan adikku (Yacobus dan Ade (Nenek Lampir)) terima kasih untuk “kata-kata” yang membuatku semakin termotivasi . 7. Keluarga besarku yang tersebar di berbagai kota. Terima kasih atas doa dan bantuan yang telah kalian berikan. 8. T Agusta Dwi Handaru yang telah menambah warna dalam kehidupanku. Terima kasih atas kesabaran dan cinta mu. 9. Sahabat-sahabatku nan jauh di sana: Yulia, Maria, dan Uthe terima kasih buat persahabatan, perhatian dan dukungannya. 10. Teman-teman angkatan 2002: Ngq, Debby, Lia, Ika, Sari, Aan, Tato, Bani, Lili, Taim, Ijup, Markus, Felix, Vida (Ipid), Retno, Priska, Galih, Aning, Desy, Rita, Wuri, Deon, Cheea, Nunung, Dani , Palma, dan Asih. Esp. Debby, Lia, dan Ijup yang selalu menemaniku ketika masa-masa ngantukku dengan chating bersama. 11. Teman-teman kostku (Wisma Lestari) esp. Lia, Kawat (thanks atas printernya), M`Nchis, dan M`Mitha yang menjadi setan serta malaikat ketika skripsi ini dibuat. Thanks untuk hari-hari ceria yang telah kita lewati bersama. 12. Teman seperjuanganku dalam menyusun skripsi (Ipid Manyiiit), terima kasih atas bantuan dan perhatiannya. 13. Teman-teman kost (tumpangan) ku, Ipid (namamu paling banyak terucap…), Endra, Primtul, M`Lina, Ine, Maria, Lili. Terima kasih atas tumpangannya, tanpa kalian entah bagaimana nasibku.

ix


14. Teman-teman KKN ku, yang berlomba-lomba untuk menyelesaikan skripsi. Serta warga Caben. Terima kasih untuk dorongan dan semangat yang telah kalian berikan. 15. Teman-teman P3W Terima kasih untuk dorongan dan semangat yang telah kalian berikan. 16. Teman-Teman Pondok Baca Kota Baru, tempatku menghilangkan kepenatan belajar. Teruslah berusaha mengembangkan Pondok Baca, upah kalian besar di Surga. 17. Semua pihak yang telah turut membantu hingga skripsi ini selesai yang tidak dapat disebutkan satu persatu.

Penulis menyadari masih ada kekurangan, kekeliruan, dan masih jauh dari sempurna. Oleh karena itu, penulis mengharapkan saran dan kritik yang bersifat membangun demi kemajuan yang akan datang. Semoga penulisan skripsi ini dapat memberikan manfaat bagi pembaca.

Yogyakarta, Juli 2007

Penulis

x


DAFTAR ISI

HALAMAN JUDUL.....................................................................................

i

HALAMAN PERSETUJUAN PEMBIMBING ...........................................

ii

HALAMAN PENGESAHAN.......................................................................

iii

HALAMAN PERSEMBAHAN ...................................................................

iv

PERNYATAAN KEASLIAN KARYA .......................................................

v

ABSTRAK ....................................................................................................

vi

ABSTRACT..................................................................................................

vii

KATA PENGANTAR ..................................................................................

viii

DAFTAR ISI.................................................................................................

xi

DAFTAR TABEL.........................................................................................

xiv

DAFTAR GAMBAR………………………………………………………

xxi

BAB I

PENDAHULUAN...................................................................

1

A. Latar Belakang. .....................................................................

1

B. Perumusan Masalah ..............................................................

4

C. Pembatasan Masalah .............................................................

4

D. Tujuan Penulisan...................................................................

4

E. Metode Penulisan ..................................................................

5

F. Manfaat Penulisan.................................................................

5

G. Sistematika Penulisan ...........................................................

5

xi


BAB II

OPTIMASI FUNGSI TANPA KENDALA..........................

7

A. Optimasi Fungsi Satu Variabel Tanpa Kendala Dengan Kalkulus ................................................................................

7

B. Optimasi Fungsi Beberapa Variabel Tanpa Kendala

BAB III

Dengan Kalkulus...................................................................

21

ALGORITMA GENETIKA..................................................

50

A. Latar Belakang Biologi .........................................................

50

B. Struktur Umum Algoritma Genetika.....................................

51

C. Komponen-komponen Utama Algoritma Genetika. .............

56

1. Teknik Penyandian..........................................................

56

2. Prosedur Inisialisasi ........................................................

57

3. Fungsi Evaluasi (fitness function) ...................................

58

4. Seleksi .............................................................................

59

4.1. Seleksi Roda Rolet .................................................

59

4.2. Seleksi Rangking....................................................

60

4.3. Seleksi Turnamen...................................................

61

5. Operator Genetika ...........................................................

62

5.1. Rekombinasi (crossover) .......................................

62

5.2. Mutasi.....................................................................

63

6. Penentuan Parameter.......................................................

64

xii


BAB IV

ALGORITMA

GENETIKA

UNTUK

OPTIMASI

FUNGSI TANPA KENDALA...............................................

66

PENUTUP...............................................................................

112

A. Kesimpulan ...........................................................................

112

B. Saran......................................................................................

113

DAFTAR PUSTAKA ..................................................................................

114

LAMPIRAN ...............................................................................................

116

BAB V

xiii


DAFTAR TABEL

Tabel 3.2.1

Tabel Istilah dalam Algoritma Genetika ............................

53

Tabel 3.3.1.1

Pemetaan nilai biner ke nilai real .......................................

57

Tabel 3.4.2.1

Contoh populasi dengan 5 kromosom yang diberi fitness baru.....................................................................................

Tabel 4.1

Tabel nilai maksimum fungsi f (x1 , x2 ) = x12 + 2 x1 x2 + x22 dengan probabilitas rekombinasi 0.2 dan

probabilitas

mutasi 0.01 hingga 0.1 ....................................................... Tabel 4.2

61

70

Tabel nilai maksimum fungsi f (x1 , x2 ) = x12 + 2 x1 x2 + x22 dengan probabilitas rekombinasi 0.25 dan probabilitas mutasi 0.01 hingga 0.1 .......................................................

Tabel 4.3


probabilitas


71

72


Tabel 4.5

73

Tabel nilai maksimum fungsi f (x1 , x2 ) = x12 + 2 x1 x2 + x22

dengan probabilitas rekombinasi 0.4 dan

probabilitas

mutasi 0.01 hingga 0.1 .......................................................

xiv

74


Tabel 4.6


Tabel 4.7


probabilitas


75

76

Tabel nilai maksimum fungsi f (x1 , x2 ) = x12 + 2 x1 x2 + x22 dengan probabilitas rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08 .........................................................................

Tabel 4.9

Tabel

nilai

maksimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

fungsi probabilitas

rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1. Tabel 4.10

Tabel

nilai

maksimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

Tabel

nilai

maksimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

probabilitas

Tabel

nilai

maksimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

probabilitas 85

fungsi probabilitas

rekombinasi 0.35 dan probabilitas mutasi 0.01 hingga 0.1

xv

84

fungsi


83

fungsi

rekombinasi 0.25 dan probabilitas mutasi 0.01 hingga 0.1 Tabel 4.11

77

86


Tabel 4.13

Tabel

nilai

maksimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

fungsi probabilitas


Tabel

nilai

maksimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

fungsi probabilitas


Tabel

nilai

maksimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

Tabel

nilai

minimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

probabilitas

Tabel

nilai

minimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

probabilitas

Tabel

nilai

minimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

probabilitas

Tabel

nilai

minimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

probabilitas 92

fungsi probabilitas


xvi

91

fungsi


90

fungsi


89

fungsi


88

fungsi


87

93


Tabel 4.20

Tabel

nilai

minimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

fungsi

dengan probabilitas


Tabel

nilai

minimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

fungsi probabilitas


Tabel

nilai

minimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

Tabel

nilai

maksimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

probabilitas

Tabel

nilai

minimum

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

probabilitas 97

fungsi probabilitas

rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08 ............ Tabel 4.25

96

fungsi

rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08 ............ Tabel 4.24

95

fungsi


94

98

2 2 Tabel nilai maksimum fungsi f (x ) = x1 e − ( x1 + x 2 ) dengan

probabilitas rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1........................................................................... Tabel 4.26

101


probabilitas rekombinasi 0.25 dan probabilitas mutasi 0.01 hingga 0.1...................................................................

xvii

102


Tabel 4.27



102


probabilitas rekombinasi 0.35 dan probabilitas mutasi 0.01 hingga 0.1................................................................... Tabel 4.29

103



103


probabilitas rekombinasi 0.45 dan probabilitas mutasi 0.01 hingga 0.1................................................................... Tabel 4.31

104



104


probabilitas mutasi 0.01 dan probabilitas rekombinasi 0.2 hingga 0.5........................................................................... Tabel 4.33

105


probabilitas mutasi 0.02 dan probabilitas rekombinasi 0.2 hingga 0.5...........................................................................

xviii

105


Tabel 4.34



106



106



107



107



108



108



xix

109


Tabel 4.41



xx

109


DAFTAR GAMBAR

Gambar 2.1.1

Grafik f ( x) = x 3 − x 2 − x + 2 .............................................

8

Gambar 2.1.2

x* titik batas dari I atau f ′(x* ) = 0 ....................................

9

Gambar 2.1.3

Grafik fungsi f ( x) = 7 x 2 − 3 x + 5 .....................................

11

Gambar 2.1.4

Grafik fungsi pada selang tertutup [a, b]. ..........................

12

Gambar 2.1.5

Fungsi kontinu pada selang tertutup [a, b].........................

14

Gambar 2.1.6

Grafik fungsi f ( x) = x 2 − 4 x + 5 .......................................

20

Gambar 2.2.1

Grafik fungsi f ( x, y ) = x 2 + y 2 − x − y + 1 .......................

33

Gambar 2.2.2

Grafik fungsi f ( x1 , x2 ) = x13 + x23 − 3 x1 − 12 x2 + 20 ..........

47

Gambar 3.2.1.

Ilustrasi Algoritma Genetika ..............................................

54

Gambar 3.3.1.1 Representasi string bit .......................................................

56

Gambar 3.3.1.2 Representasi panjang kromosom .......................................

57

Gambar 3.4.1.1 Contoh penggunaan metode seleksi roda roulette..............

59

Gambar 3.5.1.1 Rekombinasi satu titik........................................................

62

Gambar 4.1

Grafik fungsi f (x1 , x2 ) = x12 + 2 x1 x2 + x22 ..........................

67

Gambar 4.2

Grafik

terjadinya

f (x1 , x2 ) = x12 + 2 x1 x2 + x22

nilai dengan

maksimum probabilitas

rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1..

xxi

70


Gambar 4.3

Grafik

terjadinya

f (x1 , x2 ) = x12 + 2 x1 x2 + x22

nilai

maksimum

dengan

probabilitas

rekombinasi 0.25 dan probabilitas mutasi 0.01 hingga 0.1…................................................................................... Gambar 4.4

Grafik

terjadinya

f (x1 , x2 ) = x12 + 2 x1 x2 + x22

nilai

maksimum

dengan

probabilitas

rekombinasi 0.3 dan probabilitas mutasi 0.01 hingga 0.1.. Gambar 4.5

Grafik

terjadinya

f (x1 , x2 ) = x12 + 2 x1 x2 + x22

nilai

maksimum

dengan

probabilitas

rekombinasi 0.35 dan probabilitas mutasi 0.01 hingga 0.1. Gambar 4.6

Grafik

terjadinya

f (x1 , x2 ) = x12 + 2 x1 x2 + x22

nilai

maksimum

dengan

probabilitas


Grafik

terjadinya

f (x1 , x2 ) = x12 + 2 x1 x2 + x22

nilai

maksimum

dengan

probabilitas


Grafik

terjadinya

f (x1 , x2 ) = x12 + 2 x1 x2 + x22

nilai

maksimum

dengan

probabilitas

rekombinasi 0.5 dan probabilitas mutasi 0.01 hingga 0.1... Gambar 4.9

Grafik

terjadinya

f (x1 , x2 ) = x12 + 2 x1 x2 + x22

nilai

maksimum

dengan

probabilitas

rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08. ...........

xxii

71

72

73

74

75

76

77


Gambar 4.10

Grafik fungsi f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1 ...................

Gambar 4.11

Grafik

terjadinya

nilai

maksimum

fungsi f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

78

probabilitas rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1........................................................................... Gambar 4.12

Grafik

terjadinya

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

nilai dengan



Grafik

terjadinya

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

nilai dengan

Grafik

terjadinya

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

nilai dengan

probabilitas

Grafik

terjadinya

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

nilai dengan

probabilitas

Grafik

terjadinya

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

nilai dengan

probabilitas 87



xxiii

86

maksimum


85

maksimum

rekombinasi 0.35 dan probabilitas mutasi 0.01 hingga 0.1 Gambar 4.15

84

maksimum


83

88


Gambar 4.17

Grafik

terjadinya

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

nilai dengan



Grafik

terjadinya

nilai

fungsi f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

89

minimum dengan


Grafik

terjadinya

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

nilai dengan

minimum probabilitas


Grafik

terjadinya

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

nilai dengan

Grafik

terjadinya

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

nilai dengan

probabilitas

Grafik

terjadinya

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

nilai dengan

probabilitas

Grafik

terjadinya

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

nilai dengan

probabilitas 94



xxiv

93

minimum


92

minimum


91

minimum


90

95


Gambar 4.24

Grafik

terjadinya

nilai

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan



Grafik

terjadinya

nilai

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan


rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08 ............. Gambar 4.26

Grafik

terjadinya

nilai

f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1

dengan

96

97


rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08 .............

98

Gambar 4.27

grafik fungsi f (x1 , x2 ) = x1 e − ( x1 + x2 ) ..............................

99

Gambar 4.28

2 2 Grafik nilai maksimum fungsi f (x ) = x1 e − ( x1 + x 2 ) dengan

2

2


103


probabilitas rekombinasi 0.25 dan probabilitas mutasi 0.01 hingga 0.1................................................................... Gambar 4.30

103


probabilitas rekombinasi 0.3 dan probabilitas mutasi 0.01 hingga 0.1...........................................................................

xxv

104


Gambar 4.31



104



105



Grafik

nilai

maksimum

105

2 2 fungsi f (x ) = x1 e − ( x1 + x 2 )

dengan probabilitas rekombinasi 0.5 dan probabilitas mutasi 0.01 hingga 0.1 ....................................................... Gambar 4.35

106


probabilitas mutasi 0.01 dan probabilitas rekombinasi 0.2 hingga 0.5........................................................................... Gambar 4.36

Grafik

nilai

maksimum

dengan

probabilitas

mutasi

2 2 fungsi f (x ) = x1 e − ( x1 + x 2 )

0.02

dan

probabilitas

rekombinasi 0.2 hingga 0.5 ................................................ Gambar 4.37

Grafik

nilai

maksimum

dengan

probabilitas

mutasi

107

2 2 fungsi f (x ) = x1 e − ( x1 + x 2 )

0.03

dan

probabilitas

rekombinasi 0.2 hingga 0.5 ................................................

xxvi

106

107


Gambar 4.38

Grafik

nilai

maksimum

dengan

probabilitas

mutasi

2 2 fungsi f (x ) = x1 e − ( x1 + x 2 )

0.04

dan

probabilitas


Grafik

nilai

maksimum

dengan

probabilitas

mutasi

2 2 fungsi f (x ) = x1 e − ( x1 + x 2 )

0.05

dan

probabilitas


108

108


probabilitas mutasi 0.06 dan probabilitas rekombinasi 0.2 hingga 0.5........................................................................... Gambar 4.41

Grafik

nilai

maksimum

dengan

probabilitas

mutasi

2 2 fungsi f (x ) = x1 e − ( x1 + x 2 )

0.07

dan

probabilitas


Grafik

nilai

maksimum

dengan

probabilitas

mutasi

Grafik

nilai

maksimum

dengan

probabilitas

mutasi

0.08

dan

probabilitas

Grafik

nilai

maksimum

dengan

probabilitas

mutasi

0.09

dan

probabilitas 110

2 2 fungsi f (x ) = x1 e − ( x1 + x 2 )

0.1

dan

probabilitas

rekombinasi 0.2 hingga 0.5 ................................................

xxvii

110

2 2 fungsi f (x ) = x1 e − ( x1 + x 2 )


109

2 2 fungsi f (x ) = x1 e − ( x1 + x 2 )


109

111


BAB I PENDAHULUAN

A. Latar Belakang Teori optimasi secara klasik dibangun dengan menggunakan kalkulus diferensial untuk menentukan nilai minimum atau maksimum (optimum) dari fungsi dengan kendala atau tanpa kendala. Untuk fungsi tanpa kendala, f(x) harus memenuhi setiap x yang memenuhi pembataspembatas: x ≥ 0 dimana f(x) adalah fungsi yang bernilai real dari Rn. Jika ada beberapa atau semua fungsi dari f(x) adalah tidak linear maka masalah tersebut dikatakan pemrograman tak linear. Secara matematis, suatu titik dikatakan pembuat maksimum apabila

(

)

terdapat suatu titik x * = x1* , x2* , x3* ,..., xn* yang memenuhi f (x* ) ≥ f (x) ,

atau pembuat minimum apabila f (x* ) ≤ f (x) . Secara umum, optimasi pemrograman tak linear selalu menimbulkan kesulitan dalam penangan analitis dan numerik, dan lebih sulit dari pemrograman linear. Walaupun dalam kasus dimana semua kendala adalah linear dan hanya fungsi tujuannya yang tak linear, tetap saja sulit untuk diselesaikan. Oleh sebab itu diperlukan teknik lain yang dapat menyelesaikan masalah optimasi dalam pemrograman tak linear. Algoritma Genetika tergolong dalam algoritma yang bersifat heuristik, sehingga dapat memberikan banyak kemungkinan penyelesaian dan memberikan pertimbangan untuk mengambil suatu keputusan. 1


2

Sejak tahun 1960, mulai berkembang perhatian dalam menirukan kehidupan makhluk hidup untuk menyelesaikan masalah optimasi yang sulit. Saat ini, terdapat tiga topik utama dalam penelitian yang menirukan kehidupan makhluk hidup, yaitu Algoritma Genetika, Pemrograman Evolusi, dan Strategi Evolusi. Diantara ketiga topik tersebut, yang paling sering digunakan adalah Algoritma Genetika. Algoritma Genetika banyak dipakai pada aplikasi bisnis, teknik, maupun bidang keilmuan lainnya. Algoritma Genetika dapat dipakai untuk mendapatkan solusi yang tepat untuk masalah optimasi yang kompleks dan sulit diselesaikan. Menurut Goldberg (1989) Algoritma Genetika adalah teknik pencarian stokastik berdasarkan mekanisme seleksi alam dan sifat genetika. Pada dasarnya, Algoritma Genetika merupakan implementasi dari teori evolusi dan teori genetika yang dikemukakan oleh Darwin dalam konsep biologi. Seperti proses evolusi di alam, Algoritma Genetika umumnya terdiri dari tiga operator, yaitu operator reproduksi, operator persilangan (crossover), dan operator mutasi. Suatu individu mempunyai sifat tertentu ditentukan dengan susunan gen dalam kromosom individu tersebut. Dalam Algoritma Genetika, teori genetika tersebut digunakan untuk merepresentasikan setiap solusi dari masalah yang ada. Karena tiap kromosom merupakan solusi dari masalah yang akan diselesaikan, kromosom yang terbaik merupakan pendekatan dari solusi optimal dari masalah yang akan diselesaikan. Berdasarkan pada konsep biologi dari


3

Darwin, dalam menyelesaikan suatu masalah, Algoritma Genetika memulai pekerjaannya dengan sekumpulan solusi yang disebut populasi. Setiap individu pada populasi disebut kromosom yang menggambarkan suatu solusi dari masalah yang akan diselesaikan. Kromosom-kromosom terus berkembang terus menerus yang disebut generasi. Pada setiap generasi, kromosom dievaluasi dengan menggunakan alat ukur yang disebut fitness (tingkat kesesuaian). Nilai fitness dari suatu kromosom akan

menunjukkan

kualitas

kromosom

dalam

populasi

tersebut.

Kromosom yang terpilih membentuk kromosom baru, yaitu anak atau keturunan (offspring) yang terbentuk dari gabungan dua kromosom generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover) atau dengan mengubah suatu kromosom dengan menggunakan operator mutasi. Generasi baru dibentuk dengan cara menyeleksi nilai fitness dari kromosom induk dan nilai fitness dari kromosom anak serta menghilangkan kromosom lainnya sehingga ukuran populasi konstan. Setelah melalui beberapa generasi, algoritma ini akan konvergen ke arah kromosom yang terbaik dengan harapan kromosom tersebut merupakan solusi optimal dari masalah yang diselesaikan. Sistem pencarian untuk mendapatkan nilai yang paling optimum pada Algoritma Genetika diharapkan dapat memberikan penyelesaian yang terbaik, dan semakin memudahkan menyelesaikan masalah Optimasi pemrograman tak linear dibandingkan dengan teknik konvensional.


4

B. Perumusan Masalah Masalah yang akan dibahas pada skripsi ini adalah : 1. Bagaimana cara Algoritma Genetika dalam mencari nilai optimum dari masalah optimasi fungsi tanpa kendala? 2. Bagaimana mendapatkan nilai optimum fungsi tanpa kendala dengan menggunakan Algoritma Genetika?

C. Pembatasan Masalah Pembatasan mengenai optimasi fungsi tanpa kendala pada skripsi ini hanya untuk program tak linear dengan dua variabel. Penulis akan menggunakan software aplikasi MATLAB untuk menyelesaikan masalah optimasi tanpa kendala tersebut.

D. Tujuan Penulisan Skripsi ini bertujuan untuk memenuhi salah satu persyaratan untuk memperoleh gelar Sarjana Sains dalam bidang matematika. Selain itu skripsi ini bertujuan untuk: 1. Lebih

memahami

penerapan

Algoritma

Genetika

dalam

menyelesaikan masalah optimasi fungsi tanpa kendala. 2. Mendapatkan nilai yang paling optimum dari masalah optimasi fungsi tanpa kendala dengan menggunakan Algoritma Genetika.


5

E. Metode Penulisan Penulisan skripsi ini menggunakan metode studi pustaka, yaitu dengan menggunakan buku-buku, jurnal-jurnal, dan makalah-makalah yang telah dipublikasikan, sehingga tidak ditemukan hal baru.

F. Manfaat Penulisan Manfaat yang diharapkan dari penulisan skripsi ini adalah semakin memperdalam pemahaman akan Algoritma Genetika dalam menyelesaikan masalah optimasi, terutama dalam menyelesaikan masalah optimasi fungsi tanpa kendala, dan dapat mencari nilai optimum dengan menggunakan Algoritma Genetika.

G. Sistematika Penulisan BAB I

PENDAHULUAN

Pada Bab I dipaparkan mengenai latar belakang skripsi ini, perumusan masalah, pembatasan masalah, tujuan penulisan, metode penulisan, dan manfaat penulisan.

BAB II OPTIMASI FUNGSI TANPA KENDALA Bab II dengan judul Optimasi Fungsi Tanpa Kendala terdiri atas dua subbab. Dalam bab ini dibahas mengenai optimasi fungsi satu variabel tanpa kendala dengan kalkulus dan optimasi fungsi beberapa variabel tanpa kendala dengan kalkulus.


6

BAB III ALGORITMA GENETIKA Bab III dengan judul Algoritma Genetika terdiri atas empat subbab. Dalam bab ini dibahas mengenai latar belakang biologi, struktur umum Algoritma

Genetika,

dan

komponen–komponen

utama

Algoritma

Genetika.

BAB IV OPTIMASI

FUNGSI

TANPA

KENDALA

DENGAN

ALGORITMA GENETIKA Bab IV dengan judul Algoritma Genetika Untuk Optimasi Fungsi tanpa kendala Tanpa Kendala merupakan inti permasalahan yang diangkat dalam skripsi ini. Dalam bab ini akan diperlihatkan contoh – contoh permasalahan optimasi tanpa kendala disertai dengan penyelesainnya menggunakan teknik konvensional (kalkulus) dan dengan menggunakan Algoritma Genetika.

BAB V PENUTUP Bab V merupakan bab terakhir dalam skripsi ini. Bab ini berisi kesimpulan dari skripsi ini dan saran yang diharapkan berguna untuk perkembangan penelitian mengenai optimasi dengan Algoritma Genetika selanjutnya.


BAB II OPTIMISASI FUNGSI TANPA KENDALA

A. Optimisasi Fungsi Satu Variabel Tanpa Kendala Dengan Kalkulus Definisi 2.1.1 Misalkan f(x) adalah fungsi bernilai real yang didefinisikan pada selang I. (Selang I dapat terbatas atau tidak terbatas, tertutup atau terbuka, atau setengah terbuka). Suatu titik x* di I adalah : a. Pembuat minimum mutlak (global) untuk f(x) pada I jika f ( x * ) ≤ f ( x)

untuk setiap x di I; b. Pembuat minimum mutlak tegas untuk f(x) pada I jika f ( x * ) < f ( x) untuk setiap x di I dan x ≠ x* ; c. Pembuat minimum relatif (lokal) untuk f(x) jika ada bilangan positif δ sedemikian

hingga

f ( x * ) ≤ f ( x)

untuk

setiap

x

di

I

dimana

x* − δ < x < x* + δ ; d. Pembuat minimum relatif tegas untuk f(x) jika ada bilangan positif δ sedemikian

hingga f ( x * ) < f ( x)

untuk

setiap

x

di

I

dimana

x * − δ < x < x * + δ dan x ≠ x * ; e. Pembuat maksimum mutlak untuk f(x) pada I jika f ( x * ) ≥ f ( x) untuk setiap x di I; f. Pembuat maksimum mutlak tegas untuk f(x) pada I jika f ( x * ) > f ( x) untuk setiap x di I dan x ≠ x* ;

7

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI 8

g. Pembuat maksimum relatif untuk f(x) jika ada bilangan positif δ sedemikian

hingga

f ( x * ) ≥ f ( x)

untuk

setiap

x

di

I

dimana

x* − δ < x < x* + δ ; h. Pembuat maksimum relatif tegas untuk f(x) jika ada bilangan positif δ sedemikian

hingga f ( x * ) > f ( x)

untuk

setiap

x

di

I

dimana

x * − δ < x < x * + δ dan x ≠ x * ; i. Titik kritis dari f(x) jika f ′( x * ) ada dan sama dengan nol.

Contoh 2.1.1

Gambar 2.1.1 Grafik f ( x) = x 3 − x 2 − x + 2

Pada gambar grafik di atas terlihat bahwa setiap x di [-3, 4]. Titik x* = -2 adalah Pembuat minimum mutlak tegas. Titik x* = 3 adalah pembuat


maksimum mutlak. Titik x* = −

1 adalah pembuat maksimum relatif tegas, 3

dan titik x* = 1 adalah pembuat minimum relatif tegas.▲

Teorema 2.1.1

Misalkan f(x) adalah fungsi yang terdiferensialkan pada selang I. Jika x* adalah pembuat minimum relatif atau pembuat maksimum relatif pada f(x), maka salah satu dari yang berikut berlaku: i. ii.

x* adalah titik batas/akhir dari I f ′( x * ) = 0 .

y=f(x)

I

pembuat minimum f ′( x * ) = 0

x*

x*

Titik batas dan maksimum * ( f ′( x ) ≠ 0 )

Gambar 2.1.2 x* titik batas dari I atau f ′(x* ) = 0

Bukti :

Misalkan x* adalah pembuat minimum relatif dari f(x) dan x* bukan titik dalam dari I. Berdasarkan hipotesa f ′( x ∗ ) ada. Akan dibuktikan f ′( x ∗ ) = 0. f ′( x * ) = lim* x→ x

f ( x) − f ( x * ) x − x*

…(1)


Karena f(x*) ≤ f(x) untuk x mendekati x*, f(x) - f(x*) adalah tak negatif untuk setiap x mendekati x*. Oleh karena itu, karena x – x* > 0 untuk x*< x, dan x – x* < 0 untuk x*> x, dapat terlihat f ( x) − f ( x * ) ≥ 0 untuk x*< x, * x−x

dan f ( x) − f ( x * ) ≤ 0 untuk x*> x, x − x* selama x mendekati x*. Berdasarkan persamaan (1) dan persamaan di atas diperoleh

f ′( x * ) ≥ 0

f ′( x * ) ≤ 0 . Hal ini membuktikan bahwa

dan

f ′( x * ) = 0 . Untuk x* pembuat maksimum relatif, bukti analog.■

Definisi 2.1.2

Bila x* suatu titik dalam daerah asal f dan bila f ′( x* ) = 0 atau f ′( x * ) tidak ada, maka x* dikatakan titik kritis dari f.

Contoh 2.1.2

Misalkan f ( x) = 7 x 2 − 3 x + 5 . Maka f ′( x) = 14 x − 3 . Ditentukan f ′( x) = 0 14 x − 3 = 0

x = 143 . Titik kritis dari f(x) adalah

3 14

.▲


Gambar 2.1.3 grafik fungsi f ( x) = 7 x 2 − 3x + 5

Maka f ′( x) = 14 x − 3 . Ditentukan

f ′( x) = 0 14 x − 3 = 0

x = 143 . Titik kritis dari f(x) adalah

3 14

.▲

Teorema 2.1.2 (Teorema Nilai Ekstrim)

Jika fungsi f kontinu pada selang tertutup [a, b], maka f mencapai nilai minimum mutlak dan maksimum mutlak pada selang [a, b].

Bukti diluar jangkauan penulis. Lihat buku Analisis Real.


Teorema nilai ekstrim dapat tercapai apabila terjadi pada: i. Selang tertutup; dan ii. Fungsi bersifat kontinu pada selang tersebut. Jika kondisi (i) dan (ii) tidak terpenuhi, maka titik ekstrim belum tentu ada. Jika domain suatu fungsi adalah selang tertutup, untuk menentukan ekstrim mutlak, fungsi tersebut harus diuji tidak hanya pada titik kritis tapi juga pada titik batas selang. Teorema titik kritis menjamin bahwa ekstrim mutlak terjadi di dalam selang.

f(c) • f(a)

• a

c

d

b

Gambar 2.1.4 Grafik fungsi pada selang tertutup [a, b].

Gambar 2.1.4 dapat dilihat bahwa titik batas selang terjadi pada x = a dan b, sedangkan titik kritis terjadi pada x = c dan d. Nilai maksimum mutlak terjadi pada titik kritis c, dan nilai minimum mutlak terjadi pada titik batas selang a. Maka baik nilai maksimum mutlak atau minimum mutlak terletak dalam selang tertutup [a, b].


Teorema 2.1.3 (Teorema Rolle)

Misalkan f adalah fungsi yang memenuhi syarat: 1. f kontinu pada selang tertutup [a, b]. 2. f mempunyai turunan pada selang terbuka (a, b). 3. f(a) = f(b) = 0. Maka ada suatu c ∈ (a, b) sehingga f ′(c) = 0.

Bukti :

Jika f(x) = 0 untuk semua x pada selang [a, b], maka f ′( x) = 0 untuk semua x pada (a, b), sehingga setiap bilangan di antara a dan b dapat diambil sebagai c. Jika f(x) tidak nol untuk suatu x pada selang terbuka (a, b) dan karena f kontinu pada selang tertutup [a, b], maka menurut teorema 2.1.2, f mempunyai nilai maksimum mutlak dan minimum mutlak pada [a, b]. Dari (3) diketahui

f(a) = 0 dan f(b) = 0. Selanjutnya f(x) tidak nol untuk suatu x pada (a, b). Maka f akan mempunyai nilai maksimum mutlak yang positif untuk suatu c1 pada (a, b) atau mempunyai nilai minimum mutlak yang negatif di suatu c2 pada (a, b), atau dua-duanya terjadi. Jadi untuk c = c1 atau c = c2 atau keduaduanya, terdapat ekstrim mutlak di titik dalam selang [a, b]. Oleh karena itu ekstrim mutlak f(c) juga ekstrim relatif. Karena f ′(c) ada berdasarkan hipotesis, maka menurut teorema 2.1.1, f ′(c) = 0.■


Teorema 2.1.4 (Teorema Nilai Rata-Rata)

Misalkan f adalah fungsi yang memenuhi syarat: 1. f kontinu pada selang tertutup [a, b]. 2. f mempunyai turunan pada selang terbuka (a, b). Maka ada suatu c ∈ (a, b) sehingga f ′(c) =

f (b) − f (a ) . b−a

Bukti :

f(x) y

•B

y=g(x)

A•

x x a b Gambar 2.1.5 fungsi kontinu pada selang tertutup [a,b].

Misalkan fungsi f(x) untuk x ∈ [a, b] seperti ditunjukkan pada gambar 2.1.5 Fungsi g(x) adalah persamaan garis yang melalui titik A dan B. Dibentuk fungsi s(x) yaitu s ( x) = f ( x) − g ( x) untuk setiap x ∈ [a, b] . Karena garis ini mempunyai kemiringan

f (b) − f (a ) dan melalui (a, f(a)), maka bentuk titik b−a

kemiringan untuk persamaannya adalah

g ( x) − f (a ) =

f (b) − f (a) ( x − a ) atau b−a

g ( x) = f (a ) +

f (b) − f (a ) ( x − a) b−a


s ( x) = f ( x) − g ( x) ⇔

s ( x) = f ( x) − f (a ) −

f (b) − f (a ) ( x − a) b−a

Perhatikan bahwa s(b) = s(a) = 0 dan bahwa untuk x dalam (a, b) s ′( x) = f ′( x) −

f (b) − f (a ) . b−a

Menurut teorema 2.1.2 fungsi s harus mencapai nilai maksimum atau nilai minimum pada [a, b]. Jika kedua nilai tersebut adalah 0, maka s(x) secara identik adalah 0 pada [a, b], akibatnya s ′( x) = 0 untuk semua x dalam (a, b). Jika salah satu nilai maksimum atau minimum tidak sama dengan 0, maka nilai tersebut tercapai pada suatu titik dalam c. Karena s(a) = s(b) = 0. Dan s mempunyai turunan di setiap titik dari (a, b), sehingga menurut teorema 2.1.3 s ′(c) = 0 . Karena diketahui terdapat suatu bilangan c dalam (a, b) yang memenuhi

s′(c) = 0 , maka 0 = f ′(c) − f ′(c) =

f (b) − f (a ) atau b−a f (b) − f (a) ■ b−a


Teorema 2.1.5 Misalkan f ( x), f ′( x), f ′′( x) ada pada selang tertutup [a, b]. Jika x*, x adalah dua titik yang berbeda pada [a, b], maka terdapat titik z tepat berada di antara x* dan x sehingga f ( x) = f ( x * ) + f ′( x * )( x − x * ) +

f ′′( z ) ( x − x* ) 2 . 2

Bukti : Misalkan suatu fungsi f ( x) = f ( x * ) + f ′( x * )( x − x * ) + R( x − x * ) 2

…(2)

Pandang F(x), F ( x) = f ( x) − f ( x * ) − f ′( x * )( x − x * ) − R( x − x * ) 2

…(3)

Maka dari (2) diperoleh F(x) = 0. Karena F(x) = 0, maka F(a) = F(b) = 0. f ( x), f ′( x), f ′′( x) kontinu pada selang tertutup [a, b], maka penjumlahan dan pengurangan fungsi – fungsi (F(x)) tersebut juga kontinu pada selang tertutup [a, b], dan F ′( x) = f ′( x) − f ′( x * ) − 2 R( x − x * )

…(4)

terlihat bahwa F(x) mempunyai turunan. Karena ketiga syarat dari teorema Rolle dipenuhi, maka menurut teorema Rolle, terdapat bilangan z1 antara x dan

x * ( x < z1 < x * ) sedemikian sehingga F ′( z1 ) = 0

…(5a)

Dari (4) diperoleh F ′( x) = 0

…(5b)


(5a) dan (5b) menunjukkan bahwa F ′(x) memenuhi teorema Rolle dalam (x, z1). Jadi terdapat bilangan z antara x dan z1 sedemikian sehingga F ′′( z ) = 0 , dan dari (4) diperoleh R=

1 2

F ′′( x) = f ′( x) − 2 R . Karena

F ′′( z ) = 0 , maka

f ′′( z ) .

Substitusi R dalam (2), maka

f ( x) = f ( x * ) + f ′( x * )( x − x * ) +

1 2

f ′′( z )( x − x * ) 2 .■

Definisi 2.1.1 merupakan cara untuk mengetahui apakah suatu titik x* di I adalah minimum atau maksimum mutlak atau relatif di I. Namun pada definisi 2.1.1 tidak diketahui apakah memang benar titik x* tersebut adalah pembuat minimum / maksimum mutlak tegas atau pembuat minimum / maksimum relatif tegas. Oleh sebab itu diperlukan cara lain yang lebih baik, yaitu teorema 2.1.6, yang dapat menentukan apakah pembuat maksimum / minimum (baik mutlak ataupun relatif) tersebut tegas atau tidak.

Teorema 2.1.6

Misalkan f ( x), f ′( x), f ′′( x ) kontinu pada selang I dan x* ∈I adalah titik kritis dari f(x). a. Jika f ′′( x) ≥ 0 untuk setiap x ∈ I, maka x* adalah pembuat minimum mutlak dari f(x) di I. b. Jika f ′′( x) > 0 untuk setiap x∈I sedemikian hingga x ≠ x * , maka x* adalah Pembuat minimum mutlak tegas dari f(x) di I. c. Jika f ′′( x * ) > 0 , maka x* adalah pembuat minimum relatif tegas dari f(x).


d. Jika f ′′( x) ≤ 0 untuk setiap x∈I, maka x* adalah pembuat maksimum mutlak dari f(x) di I. e. Jika f ′′( x) < 0 untuk setiap x∈I sedemikian hingga x ≠ x * , maka x* adalah Pembuat maksimum mutlak tegas dari f(x) di I. f. Jika f ′′( x * ) < 0 , maka x* adalah pembuat maksimum relatif tegas dari f(x).

Bukti :

Bukti (a): Jika x ∈ I dan x ≠ x*, maka berdasarkan teorema 2.1.5 dan hipotesa f ′( x * ) =0 menghasilkan f ( x) − f ( x * ) =

f ′′( z ) ( x − x* ) 2 , 2

…(6)

dimana z adalah titik yang berada tepat di antara x* dan x. Karena itu, jika f ′′( x) ≥ 0 untuk setiap x∈I, maka f ( x) ≥ f ( x * ) untuk setiap x∈I karena (x - x * ) 2 ≥ 0 untuk setiap x ∈ I. 2

Bukti (b): Jika x∈I dan x ≠ x*, maka berdasarkan teorema 2.1.5 dan hipotesa f ′( x * ) =0 menghasilkan f ( x) − f ( x * ) =

f ′′( z ) ( x − x* ) 2 , 2

…(7)

dimana z adalah titik yang berada tepat di antara x* dan x. Karena itu, jika

f ′′( x) > 0

untuk setiap x ∈ I, maka f ( x) > f ( x * ) untuk setiap x ∈ I karena

(x - x * ) 2 > 0 untuk setiap x∈I. 2


Bukti (c): Jika f ′′( x * ) > 0 , kekontinuitas dari f ′′(x) mengimplikasikan bahwa ada δ > 0 sehingga f ′′(x) > 0 untuk setiap x ∈ I sedemikian hingga x* - δ < x < x* + δ . Namun persamaan (7) menunjukkan bahwa f(x) > f(x*) untuk setiap x∈I sedemikian hingga x ≠ x * , x * − δ < x < x * + δ , dimana x* adalah satu satunya pembuat minimum relatif dari f(x). Bukti (d): Jika x∈I dan x ≠ x*, maka berdasarkan teorema 2.1.5 dan hipotesa f ′( x * ) =0 menghasilkan f ( x) − f ( x * ) =

f ′′( z ) ( x − x* ) 2 , 2

…(8)

dimana z adalah titik yang berada tepat di antara x* dan x. Karena itu, jika f ′′( x) ≤ 0 untuk setiap x∈I, maka f ( x) ≤ f ( x * ) untuk setiap x∈I karena f ( x) − f ( x * ) ≤ 0 untuk setiap x ∈ I.

Bukti (e): Jika x ∈ I dan x ≠ x*, maka berdasarkan teorema 2.1.5 dan hipotesa f ′( x * ) =0 menghasilkan f ( x) − f ( x * ) =

f ′′( z ) ( x − x* ) 2 , 2

…(9)

dimana z adalah titik yang berada tepat di antara x* dan x. Karena itu, jika f ′′( x) < 0 untuk setiap x∈I, maka f ( x) < f ( x * ) untuk setiap x∈I karena f ( x) − f ( x * ) ≤ 0 untuk setiap x ∈ I.


Bukti (f): Jika f ′′( x * ) < 0 , kekontinuitasan dari f ′′( x) mengimplikasikan bahwa ada δ > 0 sehingga f ′′(x) < 0 untuk setiap x∈I sedemikian hingga x* -

δ < x < x* + δ . Namun persamaan (9) menunjukkan bahwa f(x) < f(x*) untuk setiap x∈I sedemikian hingga x ≠ x * , x * − δ < x < x * + δ , dimana x* adalah satu - satunya pembuat maksimum relatif dari f(x). ■

Contoh 2.1.3

Tentukan ekstrim mutlak dari fungsi f ( x) = x 2 − 4 x + 5 pada selang [1,4].

Gambar 2.1.6 grafik fungsi f ( x) = x 2 − 4 x + 5 .

i. Mencari titik kritis

f ′( x) = 0 2x − 4 = 0

x=2

ii. Mengevaluasi f(x) pada titik akhir dan titik kritis f (1) = 12 − 4 × 1 + 5 = 2 f (2) = 2 2 − 4 × 2 + 5 = 1


f (4) = 4 2 − 4 × 4 + 5 = 5 Dari langkah 9, dapat disimpulkan bahwa nilai maksimum mutlak terjadi pada titik (4, 5), dan nilai minimum mutlak terjadi pada titik (2,1).▲

B. Optimisasi Fungsi Beberapa Variabel Tanpa Kendala Dengan Kalkulus

Perluasan dari fungsi satu variabel adalah fungsi lebih dari satu variabel dengan mengkombinasikan beberapa teori kalkulus dengan aljabar linear. Oleh sebab itu, untuk permulaan akan dibahas beberapa terminologi dan notasi. Vektor pada Rn adalah pasangan terurut n-tupel x = (x1, x2, …, xn) dari bilangan real xi yang disebut dengan komponen dari x. Vektor x = (x1, x2, …, xn) ⎛ x1 ⎞ ⎜ ⎟ ⎜x ⎟ disebut vektor baris, dan vektor x = ⎜ 2 ⎟ disebut vektor kolom. M ⎜ ⎟ ⎜x ⎟ ⎝ n⎠

Maka dapat dilihat bahwa fungsi f(x1, x2, …, xn) dari n variabel sebagai fungsi f(x) dari vektor tunggal variabel x = (x1, x2, …, xn).

Definisi 2.2.1

Didefinisikan penjumlahan dari dua vektor x = (x1, x2, …, xn) dan y = (y1, y2, …, yn) pada Rn dengan x + y = (x1 + y1, x2 + y2, …, xn + yn),

dan perkalian dari x dan bilangan real λ dengan

λ x = ( λ x1, λ x2, …, λ xn).


Definisi 2.2.2

Jika x = (x1, x2, …, xn) dan y = (y1, y2, …, yn) adalah vektor-vektor di Rn, maka perkalian titik atau perkalian dalam x • y didefinisikan sebagai n

x • y = x1 y1 + x2 y 2 + ... + xn y n = ∑ xk y k . k =1

Akibat 2.2.1 Perkalian titik adalah linear pada kedua variabel; yaitu,

(αx + βy ) • z = α (x • z ) + β (y • z ), x • (αy + βz ) = α (x • y ) + β (x • z ) , untuk semua vektor x, y, z pada Rn dan bilangan real α , β .

Bukti : (αx + β y ) • z = (αx1 + βy1 , αx2 + βy 2 , K , αxn + βy n ) • ( z1 , z 2 , K , z n ) = ((αx1 + βy1 ).z1 + (αx2 + βy 2 ).z 2 + K + (αxn + βy n ).z n ) = (αx1 .z1 + βy1 .z1 + αx2 .z 2 + βy 2 .z 2 + K + αxn .z n + βy n .z n ) = ((αx1 .z1 + αx2 .z 2 + K + αxn .z n ) + (βy1 .z1 + βy2 .z 2 + K + βy n .z n )) = (α ( x1 .z1 + x2 .z 2 + K + xn .z n ) + β ( y1 .z1 + y 2 .z 2 + K + y n .z n )) = α (x • z ) + β (y • z )

x • (αy + βz ) = ( x1 , x2 , K , xn ) • (αy1 + βz1 , αy 2 + βz 2 , K , αy n + βz n ) = ( x1 .(αy1 + βz1 ) + x2 .(αy 2 + βz 2 ) + K + xn .(αy n + βz n ))


= ( x1 .αy1 + x1 .βz1 + x2 .αy2 + + x2 .βz 2 + K + xn .αy n + xn .βz n ) = ( x1 .αy1 + x2 .αy 2 + K + xn .αy n + x1 .βz1 + x2 .βz 2 + K + xn .βz n ) = (α ( x1 . y1 + x2 . y 2 + K + xn . y n ) + β ( x1 .x1 + x2 .βx2 + K + xn .βxn )) = α (x • y ) + β (x • z ) .■

Definisi 2.2.3 Dua vektor x dan y adalah ortogonal jika x • y = 0.

Definisi 2.2.4 Norm atau panjang x pada vektor x = (x1, x2, …, xn) adalah fungsi real pada Rn dengan syarat: 1.

x ≥ 0 untuk setiap vektor di Rn.

2.

x = 0 jika dan hanya jika x adalah vektor nol 0.

3.

αx = α x untuk setiap vektor di Rn dan semua bilangan real α .

4.

x + y ≤ x + y untuk semua vektor x, y di Rn (ketidaksamaan segitiga).

Contoh 2.2.1 x pada vektor x = (x1, x2, …, xn) adalah x = ( x12 + x22 + ... + xn2 )1 / 2 = (x • x)1 / 2 .


Definisi 2.2.5 Untuk vektor tak nol x dan y di R2 atau R3, perkalian titik x • y secara umum didefinisikan x • y = x y cos θ

…(1)

dimana θ ∈ [0, π ] adalah sudut antara x dan y.

x

θ y Untuk vektor x dan y di Rn dengan n > 3, formula (1) untuk perkalian titik tetap dapat digunakan jika cos θ didefinisikan. Untuk x, y ∈ Rn didefinisikan cos θ =

x•y x y

Teorema 2.2.1 Pertidaksamaan Cauchy – Schwarz untuk setiap vektor x dan y, x•y ≤ x y

Bukti : Apabila x dan y adalah vektor nol, maka 0 ≤ 0, dimana hal tersebut adalah benar untuk setiap x dan y. Jika x atau y (salah satunya) vektor tak nol, maka dari persamaan (1) didapatkan x • y = x y cos θ ≤ x y ,


karena cos θ ≤ 1 untuk setiap nilai pada θ .■

Pada pertidaksamaan Cauchy – Schwarz, − 1 ≤ cos θ ≤ 1 dan cos θ = 1 jika

hanya jika terdapat satu vektor yang merupakan kelipatan vektor lainnya.

Definisi 2.2.6

Jika x dan y adalah vektor di Rn, panjang atau jarak d (x, y ) di antara x dan y didefinisikan sebagai: 1

⎞2 ⎛ n d (x, y ) = x − y = ⎜ ∑ ( xi − yi ) 2 ⎟ ⎠ ⎝ i=1

Definisi 2.2.7

Bola B (x, r ) yang berpusat pada x dengan radius r adalah himpunan semua vektor y di Rn, dimana jarak dari x kurang dari r, maka

{

}

B(x, r ) = y ∈ R n y − x < r .

Definisi 2.2.8 Titik x pada sub himpunan D di Rn adalah titik dalam dari D jika terdapat r > 0, dimana bola B (x, r ) dalam D. Bagian dalam D o pada D adalah himpunan dari semua titik dalam dari D. Himpunan G di Rn terbuka jika G o = G , artinya, jika semua titik dalam himpunan adalah titik – titik dalam. Himpunan F di Rn


tertutup jika F mencangkup setiap titik x sehingga terdapat barisan {x(k)} di F dengan lim x ( k ) − x = 0 . k →∞

Definisi 2.2.9 Himpunan D di Rn adalah terbatas jika terdapat suatu konstanta M > 0 sehingga x < M untuk setiap x∈D, artinya, D adalah terbatas jika dan hanya jika D termasuk dalam bola besar B(0, M) dengan pusat 0.

Contoh 2.2.1 Pada R2, himpunan F dengan komponennya adalah titik – titik tak negatif, yaitu F = {x = ( x1 , x2 ) ∈ R 2 x1 ≥ 0, x2 ≥ 0}, adalah tertutup tapi tidak terbatas. Titik x = (x1, x2) pada F adalah titik dalam dari F jika dan hanya jika x1 > 0, x2 > 0 karena bola B(x, r) termasuk di dalam F walaupun r adalah bilangan positif terkecil dari x1, x2.▲

Definisi 2.2.10 Misalkan f (x) adalah fungsi yang bernilai real didefinisikan pada sub himpunan D di Rn. Titik x* di D adalah: a

Pembuat minimum mutlak untuk f (x) pada D jika f (x* ) ≤ f (x) untuk setiap x ∈ D;

b Pembuat minimum mutlak tegas untuk f (x) pada D jika f (x* ) < f (x) untuk setiap x ∈ D, dimana x ≠ x* ;


c

Pembuat minimum relatif untuk f (x) jika terdapat bilangan positif δ sehingga f (x* ) ≤ f (x) untuk setiap x∈ D dimana x ∈ B (x* , δ ) ;

d Pembuat minimum relatif tegas untuk f (x) jika terdapat bilangan positif

δ sehingga f (x* ) < f (x) untuk setiap x∈ D dimana x ∈ B(x* , δ ) dan x ≠ x* ; e

Pembuat maksimum mutlak untuk f (x) pada D jika f (x* ) ≥ f (x) untuk setiap x ∈ D;

f

Pembuat maksimum mutlak tegas untuk f (x) pada D jika f (x* ) > f (x) untuk setiap x ∈ D, dimana x ≠ x* ;

g Pembuat maksimum relatif untuk f (x) jika terdapat bilangan positif δ sehingga f (x* ) ≥ f (x) untuk setiap x∈ D dimana x ∈ B (x* , δ ) ; h Pembuat maksimum relatif tegas untuk f (x) jika terdapat bilangan positif

δ sehingga f (x* ) > f (x) untuk setiap x∈ D dimana x ∈ B(x* , δ ) dan x ≠ x* ; i

Titik kritis untuk f (x) jika turunan parsial pertama dari f (x) ada pada x* dan

∂f * (x ) = 0 , i = 1, 2, …, n. ∂xi

Teorema 2.2.2 Misalkan f (x) adalah fungsi yang bernilai real dimana semua turunan parsial pertama dari f (x) ada pada sub himpunan D di Rn. Jika x* adalah titik dalam


dari D yang adalah pembuat minimum relatif dari f (x) , maka x* adalah titik kritis dari f (x) , yaitu,

∂f * (x ) = 0 , i = 1, 2, …, n. ∂xi

Bukti : Karena x* = ( x1* , x2* ,..., xn* ) adalah pembuat minimum relatif untuk f (x) dan

titik dalam dari D, terdapat bilangan positif r sehingga bola B(x*, r) termasuk di dalam D dan f (x* ) ≤ f (x) untuk setiap x ∈ B(x*, r). Akan ditunjukkan ∂f * (x ) = 0 ; ∂xi Akan ditunjukkan

∂f * (x ) = 0 dengan menggunakan fungsi satu variabel, ∂xi

yaitu f ( x, x2* , x3* ,..., xn* ) . Dimana x2* , x3* ,..., xn* adalah variabel tetap fungsi tersebut. Misalkan fungsi satu variabel g (x) didefinisikan sebagai

g ( x) = f ( x, x2* , x3* ,..., xn* ) adalah terdiferensialkan dan memenuhi

g ( x1* ) ≤ g ( x) untuk setiap x

sedemikian sehingga x1* − r < x < x1* + r . Oleh sebab itu, x1* adalah pembuat minimum relatif untuk g (x) pada I = ( x1* − r , x1* + r ). Karena itu, jika x1* bukan titik akhir dari I, berdasarkan teorema 2.1.1 maka

g ′( x1* ) = 0 . Tetapi jika g ′( x1* ) =

∂f * * ∂f * (x ) x1 , x2 ,..., xn* = ∂x1 ∂x1

(

)


maka

∂f * ∂f * (x ) = 0 . Dengan cara yang sama dapat dibuktikan (x ) = 0 un∂xi ∂xi

tuk i = 1, 2, …, n .■

Teorema 2.2.3 Misalkan x* , x adalah titik pada Rn dan f(x) adalah fungsi n variabel dengan turunan pertama dan turunan parsial kedua pada suatu himpunan terbuka termasuk segmen garis [x* , x] = {w ∈ R n | w = x* + t (x − x* );0 ≤ t ≤ 1} . Maka terdapat z∈[ x* , x] sedemikian hingga

f (x) = f (x* ) + ∇f (x* ) • (x − x* ) + 12 (x − x* ) • Hf (z )(x − x* ) .

Bukti : Jika dari formula Taylor

f ( x) = f ( x * ) + f ′( x * )( x − x * ) +

f ′′( z ) ( x − x* ) 2 2

…(2)

dapat ditunjukkan korespodensi formula Taylor untuk fungsi beberapa variabel, maka formula tersebut berlaku untuk fungsi beberapa variabel. Akan dimulai dengan kasus fungsi dua variabel. Misalkan f(x) = f(x1,x2) adalah fungsi yang didefinisikan pada R2 dan bahwa x* = ( x1* , x2* ) dan x = (x1,x2) adalah titik tetap. Didefinisikan ϕ (t ) untuk t ∈ R dengan

ϕ (t ) = f (x* + t (x − x* )) = f ( x1* + t ( x1 − x1* ), x2* + t ( x2 − x2* ))

…(3)


Maka ϕ (t ) adalah fungsi dari satu variabel t untuk t = 0 dan t = 1 sedemikian hingga

ϕ (0) = f (x* ) = f ( x1* , x2* ) ; ϕ (1) = f (x) = f ( x1 , x 2 ) . Jika ϕ ′(t ) and ϕ ′′(t ) adalah kontinu, maka dapat diimplikasikan formula Taylor (2) untuk ϕ (t ) pada titik t* = 0, t = 1. Dengan menggantikan

f ′(x* ) dengan ϕ ′(t * ) dan f ′′(x* ) dengan ϕ ′′( s ) sehingga dihasilkan f (x) = f (x* ) + ϕ ′(0)(1 − 0) +

ϕ ′′( s ) 2

(1 − 0) 2 ,

…(4)

dimana s adalah titik di antara 0 dan 1. Jika f(x) mempunyai turunan pertama dan turunan parsial kedua, maka ϕ (t ) mempunyai turunan pertama dan turunan parsial kedua dimana dapat dihitung dengan menggunakan aturan rantai sebagai berikut: Jika t ∈ R dan w = x* + t (x − x* ) , maka

ϕ (t ) = f (w ) = f (x* + t (x − x* )) = f ( x1* + t ( x1 − x1* ), x2 + t ( x2 − x2* )) . berdasarkan aturan rantai,

ϕ (t ) = f (x* + t (x − x* ))

ϕ ′(t ) =

∂f ∂f (x)( x1 − x1* ) + (x)( x2 − x2* ) ∂x2 ∂x1

= ∇f ( w ) • ( x − x * ) ,

…(5)


⎛ ∂f ⎞ ∂f dimana ∇f (w ) = ⎜⎜ (w ), (w ) ⎟⎟ adalah gradien dari f(x) yang dievaluasi ∂x2 ⎝ ∂x1 ⎠ pada w. Dengan menggunakan aturan rantai, didapatkan

ϕ ′(t ) =

=

∂ ∂x1

⎡ ∂f ⎤ ∂f (w )( x1 − x1* ) + (w )( x2 − x2* )⎥ ( x1 − x1* ) + ⎢ ∂x2 ⎣ ∂x1 ⎦

∂ ∂x2

⎡ ∂f ⎤ ∂f (w )( x1 − x1* ) + (w )( x2 − x2* )⎥ ( x2 − x2* ) ⎢ ∂x2 ⎣ ∂x1 ⎦

∂2 f ∂2 f * 2 w − + ( )( x x ) 2 (w )( x1 − x1* )( x2 − x2* ) + 1 1 ∂x12 ∂x1∂x2 ∂2 f (w )( x2 − x2* ) 2 . ∂x22

Untuk ϕ ′′(t ) dapat ditunjukkan dengan formula matriks:

⎛ ∂2 f ⎞ ∂2 f ⎜ (w) (w) ⎟ 2 ∂x ∂x1∂x2 ⎟ ϕ ′′(t ) = ( x − x* , x − x* ) • ⎜⎜ 2 1 ⎟ 1 1 2 2 ∂ f ∂2 f (w) (w) ⎟ ⎜ 2 ∂x2 ⎝ ∂x2 ∂x1 ⎠

⎛ x1 − x1* ⎞ ⎟ ⎜ ⎟ ⎜ ⎜ *⎟ ⎝ x2 − x 2 ⎠

= (x − x* ) • ( Hf (w )(x − x* )) ,

…(6)

dimana Hf(w) adalah matriks simetris 2 x 2 dari semua pasangan turunan parsial kedua terurut yang dievaluasi pada w. Gunakan (5) dan (6) untuk memperlihatkan (4) sebagai berikut:

f (x) = f (x* ) + ∇f (x* ) • (x − x* ) + 12 (x − x* ) • Hf (z )(x − x* ) ,

…(7)

dimana z = x* + s (x − x* ) dan 0 ≤ s ≤ 1 . Formula Taylor ini berlaku untuk fungsi dua variabel. Hal ini benar untuk sembarang x dan x* di R2 jika f(x) mempunyai turunan pertama dan turunan parsial kedua pada R2. Seperti yang terlihat, gradien ∇f (x* ) memainkan peranan seperti turunan pertama dan


Hessian Hf(z) berperan seperti turunan kedua dalam teorema Taylor satu variabel. Jika f(x) = f(x1, x2,…, xn) adalah fungsi n variabel dengan turunan pertama dan turunan parsial kedua pada Rn dan jika gradien ∇f dari f(x) adalah n vektor ⎛ ∂f ∂f ∂f ⎞ ⎟ , sementara Hessian Hf dari f(x) adalah matriks n x n , ,..., ∇f = ⎜⎜ ∂xn ⎟⎠ ⎝ ∂x1 ∂x2

⎛ ∂2 f ⎜ 2 ⎜ ∂x1 ⎜ ∂2 f Hf = ⎜ ∂x ∂x ⎜ 2 1 ⎜ M ⎜ ∂2 f ⎜ ∂x ∂x ⎝ n 1

∂2 f ∂x1∂x2 ∂2 f ∂x22 M ∂2 f ∂xn ∂xn1

∂2 f ⎞ ⎟ ∂x1∂xn ⎟ ∂2 f ⎟ ⎟ ∂x2 ∂xn ⎟ , O M ⎟ ∂2 f ⎟ L ∂xn2 ⎟⎠ L

maka formula Taylor benar untuk semua pilihan x dan x* pada Rn. Jika fungsi f(x) tidak terdefinisi pada semua titik di Rn, maka formula Taylor tetap bernilai benar untuk x dan x* pada domain dari f(x), asalkan f(x) mempunyai turunan pertama dan turunan parsial kedua pada suatu himpunan terbuka termasuk segmen garis [x*, x], yaitu [x* , x] = {w | w = x* + t (x − x* );0 ≤ t ≤ 1} .■

Contoh 2.2.2

Tentukan maksimum dan minimum dari fungsi f ( x, y ) = x 2 + y 2 − x − y + 1

pada cakram D yaitu x 2 + y 2 ≤ 1 .


Gambar 2.2.1 grafik fungsi f ( x, y ) = x 2 + y 2 − x − y + 1

i.

⎛ ∂f ∂f ⎞ = = 0 ⎟⎟ . Menentukan titik kritis ⎜⎜ ⎝ ∂x ∂y ⎠ ∂f = 2x − 1 ∂x 0 = 2x − 1

x = 12 . ∂f = 2y −1 ∂y

0 = 2y −1 y = 12 .

Sehingga (x, y) = ( 12 , 12 ) adalah titik kritis dari cakram terbuka U = {( x, y ) x 2 + y 2 ≤ 1} .

ii. Batas ∂U diparameterkan dengan c(t ) = (sin t , cos t ), 0 ≤ t ≤ 2π .


Sehingga f (c(t )) = sin 2 t + cos 2 t − sin t − cos t + 1 = 2 − sin t − cos t

= g (t ) . Untuk menentukan maksimum dan minimum dari f pada ∂U , g ′(t ) = 0 hanya jika

g ′(t ) = − cos t + sin t 0 = − cos t + sin t cos t = sin t ,

yaitu pada saat t =

π 5π ,

4

4

. Jadi nilai ekstrim dari f pada ∂U adalah pada

titik – titik c( π4 ), c( 54π ) , dan titik akhir c(0) = c(2π ) . iii. Menentukan nilai f.

f ( 12 , 12 ) = ( 12 ) 2 + ( 12 ) 2 − 12 − 12 + 1 = f (c( π4 )) = f ( f (c( 54π )) = f (−

2 2

2 2

) = ( 22 ) 2 + ( 22 ) 2 −

,

2 2

,−

2 2

) = (−

) + (−

2 2 2

2 2

−

) +

2 2 2

1 2

2 2

2 2

+1 = 2 − 2

+

2 2

+1 = 2 + 2

dan

f (c(0)) = f (c(2π )) = f (0,1) = (0) 2 + (1) 2 − 0 − 1 + 1 = 1 iv. Bandingkan semua nilai, maka didapatkan minimum mutlak yang terletak pada titik ( 12 , 12 ) dan maksimum mutlak yang terletak pada titik (−

2 2

,−

2 2

) .▲


Teorema 2.2.2 merupakan cara untuk mengetahui apakah suatu titik x* di Rn adalah titik kritis. Namun pada teorema 2.2.2 tidak diketahui apakah titik x* tersebut adalah pembuat minimum / maksimum mutlak (tegas) atau pembuat minimum / maksimum relatif (tegas). Oleh sebab itu diperlukan cara lain yang lebih baik, yaitu teorema 2.2.4 yang dapat menentukan apakah pembuat maksimum / minimum (baik mutlak ataupun relatif) tersebut tegas atau tidak.

Teorema 2.2.4

Andaikan x* adalah titik kritis pada fungsi f(x) dengan turunan pertama dan turunan parsial kedua pada Rn, maka: a

x* adalah pembuat minimum mutlak untuk f(x) jika

(x − x* ) • Hf (z )(x − x* ) ≥ 0 untuk setiap x ∈ Rn dan setiap z ∈ [x*, x]; b

x* adalah pembuat minimum mutlak tegas untuk f(x) jika

(x − x* ) • Hf (z )(x − x* ) > 0 untuk setiap x ∈ Rn sedemikian hingga x ≠ x * dan setiap z ∈ [x*, x]; c

x* adalah pembuat maksimum mutlak untuk f(x) jika

(x − x* ) • Hf (z )(x − x* ) ≤ 0 untuk setiap x ∈ Rn dan setiap z ∈ [x*, x]; d

x* adalah pembuat maksimum mutlak tegas untuk f(x) jika

(x − x* ) • Hf (z )(x − x* ) < 0 untuk setiap x ∈ Rn sedemikian hingga x ≠ x * dan setiap z ∈ [x*, x].


Bukti :

Karena x* adalah titik kritis pada f(x), turunan parsial pertama pada f(x) adalah nol pada x* , maka ∇f (x * ) = 0. Oleh karena itu, jika x adalah sembarang titik pada Rn selain x* (berdasarkan teorema 2.2.3) maka

f (x) = f (x* ) + 12 (x − x* ) • Hf (z )(x − x* ) ≥ 0 , dimana z ∈ [x*, x]. Persamaan ini menghasilkan setiap pernyataan yang ada pada teorema 2.2.4. Pada pernyataan (a) teorema di atas didapatkan

f (x) − f (x* ) = 12 (x − x* ) • Hf (z )(x − x* ) ≥ 0 , dan juga, f(x) ≥ f( x* ) untuk setiap x ∈ Rn .

Pada pernyataan (b) teorema di atas didapatkan

f (x) − f (x* ) = 12 (x − x* ) • Hf (z )(x − x* ) > 0 , dan juga, f(x) > f( x* ) untuk setiap x ∈ Rn sedemikian hingga x ≠ x * .

Pada pernyataan (c) teorema di atas didapatkan

f (x) − f (x* ) = 12 (x − x* ) • Hf (z )(x − x* ) ≤ 0 , dan juga, f(x) ≤ f( x* ) untuk setiap x ∈ Rn.

Pada pernyataan (d) teorema di atas didapatkan

f (x) − f (x* ) = 12 (x − x* ) • Hf (z )(x − x* ) < 0 , dan juga, f(x) < f( x* ) untuk setiap x ∈ Rn sedemikian hingga x ≠ x * .■


Pada pembuktian teorema 2.2.3 telah diketahui bahwa Hessian Hf(x) dari fungsi f(x) pada n variabel dengan turunan pertama dan turunan parsial kedua adalah matriks simetris n x n. Sehingga sembarang matriks (A) simetris n x n menentukan fungsi QA(y) pada Rn disebut bentuk kuadrat yang berhubungan dengan A

Q A = y • Ay , y ∈ R n . Jika f(x) adalah fungsi n variabel dengan turunan pertama dan turunan parsial kedua, dan jika H = Hf(z) adalah Hessian dari f(x) yang dievaluasi pada titik z, maka H adalah matriks simetris n x n. Untuk x, x* ∈ Rn, bentuk kuadrat QH yang berhubungan dengan H dievaluasi pada x − x * adalah

QH (x − x * ) = (x − x * ) • Hf (z )(x − x * ) . Hal ini tepat sama dengan pernyataan yang terdapat dalam teorema 2.2.4.

Definisi 2.2.11

Andaikan A adalah matriks simetris n x n dan Q A = y • Ay adalah bentuk kuadrat yang berhubungan dengan A. Maka A dan QA disebut: a. Semidefinit positif jika Q A = y • Ay ≥ 0 , untuk setiap y ∈ R n ; b. Definit positif jika Q A = y • Ay > 0 , untuk setiap y ∈ R n , y ≠ 0 ; c. Semidefinit negatif jika Q A = y • Ay ≤ 0 , untuk setiap y ∈ R n ; d. Definit negatif jika Q A = y • Ay < 0 , untuk setiap y ∈ R n , y ≠ 0 ; e. Tidak definit jika Q A = y • Ay > 0 , untuk suatu y ∈ R n dan Q A ( y ) < 0 untuk y ∈ R n lainnya.


Teorema 2.2.5

Andaikan x* adalah titik kritis dari fungsi f(x) dengan turunan pertama dan turunan parsial kedua pada Rn dan bahwa Hf(x) adalah Hessian dari f(x). Maka x* adalah:

a. Pembuat minimum mutlak untuk f(x) jika Hf(x) adalah semidefinit positif pada Rn; b. Pembuat minimum mutlak tegas untuk f(x) jika Hf(x) adalah definit positif pada Rn; c. Pembuat maksimum mutlak untuk f(x) jika Hf(x) adalah semidefinit negatif pada Rn; d. Pembuat maksimum mutlak tegas untuk f(x) jika Hf(x) adalah definit negatif pada Rn.

Bukti :

Hf (x) adalah Hessian dari f(x), maka: (a) berdasarkan definisi 2.2.11 Hf (x) adalah semidefinit positif jika

Q A = y • Ay ≥ 0 , karena QH (x − x * ) = (x − x * ) • Hf (z )(x − x * ) , maka berdasarkan teorema 2.2.4 x* adalah pembuat minimum mutlak. (b) berdasarkan

definisi

2.2.11

Hf (x)

adalah

definit

positif

jika

Q A = y • Ay > 0 , maka berdasarkan teorema 2.2.4 x* adalah pembuat minimum mutlak tegas.


(c) berdasarkan definisi 2.2.11 Hf (x) adalah semidefinit negatif jika QA = y • Ay ≤ 0 , maka berdasarkan teorema 2.2.4 x* adalah pembuat

maksimum mutlak. (d) berdasarkan

definisi

2.2.11

Hf (x)

adalah

definit

negatif

jika

Q A = y • Ay < 0 , maka berdasarkan teorema 2.2.4 x* adalah pembuat maksimum mutlak tegas.■

Teorema 2.2.6

⎛a Matriks simetris 2 x 2 A = ⎜⎜ 11 ⎝ a12

a12 ⎞ ⎟ adalah: a22 ⎟⎠

a. Definit positif jika dan hanya jika a12 ⎞ ⎟ > 0; a22 ⎟⎠

⎛a a11 > 0, det ⎜⎜ 11 ⎝ a12

b. Definit negatif jika dan hanya jika ⎛a a11 < 0, det ⎜⎜ 11 ⎝ a12

a12 ⎞ ⎟ > 0. a22 ⎟⎠

Bukti :

A adalah matriks simetris 2 x 2 ⎛a A = ⎜⎜ 11 ⎝ a12

a12 ⎞ ⎟ a22 ⎟⎠

maka bentuk asosiasi kuadrat dari A adalah

Q A (x) = x • Ax = a11 x 12 + 2a12 x 1 x 2 + a22 x 22 .


Untuk setiap x ≠ 0 di R2, baik x = ( x1 ,0) dengan x1 ≠ 0 atau x = ( x1 , x2 ) dengan x2 ≠ 0 . Akan dianalisa untuk 2 kasus berikut: Kasus I. x = ( x1 ,0) dengan x1 ≠ 0 . Pada kasus ini, Q A (x) = a11 x12 maka Q A ( x) > 0 jika dan hanya jika a11 > 0 , sedangkan Q A (x) < 0 jika dan hanya jika a11 < 0 .

Kasus II. x = ( x1 , x2 ) dengan x2 ≠ 0 . Pada kasus ini, x1 = tx2 untuk suatu bilangan real t dan

[

]

Q A (x) = a11t 2 + 2a12t + a22 x22 = ϕ (t ) x22 , dimana ϕ (t ) = a11t 2 + 2a12t + a22 . Karena

x2 ≠ 0 , dapat dilihat bahwa

Q A ( x) > 0 untuk setiap x jika dan hanya jika ϕ (t ) > 0 untuk setiap t ∈ R.

ϕ ′(t ) = 2a11t + 2a12 ,

ϕ ′′(t ) = 2a11 , sehingga t * = −

a12 adalah titik kritis dari ϕ (t ) dan titik kritis tersebut adalah a11

pembuat minimum tegas jika a11 > 0 dan pembuat maksimum tegas jika a11 < 0 . Jika a11 > 0 dan jika t ∈ R , maka ⎛ a12 ⎞ ⎛a a2 1 ⎟⎟ = − 12 + a22 = det ⎜⎜ 11 a11 a11 ⎝ a12 ⎝ a11 ⎠

ϕ (t ) ≥ ϕ (t * ) = ϕ ⎜⎜ −

⎛a Jadi, jika a11 > 0 dan det⎜⎜ 11 ⎝ a12

a12 ⎞ ⎟. a22 ⎟⎠

…(8)

a12 ⎞ ⎟ > 0 , maka ϕ (t ) > 0 untuk setiap t ∈ R a22 ⎟⎠

dan membuat Q A ( x) > 0 untuk setiap x = ( x1 , x2 ) dengan x2 ≠ 0 . Dengan


kata lain, jika Q A ( x) > 0 untuk setiap x, maka ϕ (t ) > 0 untuk setiap t ∈ R dan sehingga a11 > 0 dan diskriminan dari ϕ (t ) ⎛a 4a122 − 4a11a22 = −4 det⎜⎜ 11 ⎝ a12 ⎛a adalah negatif, yaitu a11 > 0 dan det⎜⎜ 11 ⎝ a12 ⎛a Jika a11 < 0 pada (8) dan det ⎜⎜ 11 ⎝ a12

a12 ⎞ ⎟ a22 ⎟⎠

a12 ⎞ ⎟ >0. a22 ⎟⎠

a12 ⎞ ⎟ > 0 , maka ϕ (t ) < 0 untuk setiap a22 ⎟⎠

t ∈ R dan membuat Q A (x) < 0 untuk setiap x = ( x1 , x2 ) dengan x2 ≠ 0 . den-

gan kata lain jika Q A ( x) < 0 untuk setiap x, maka ϕ (t ) < 0 untuk setiap t ∈ R dan sehingga a11 < 0 dan diskriminan dari ϕ (t ) ⎛a 4a122 + 4a11a22 = 4 det ⎜⎜ 11 ⎝ a12 ⎛a adalah positif, yaitu a11 < 0 dan det⎜⎜ 11 ⎝ a12

a12 ⎞ ⎟ a22 ⎟⎠

a12 ⎞ ⎟ > 0 .■ a22 ⎟⎠

Definisi 2.2.12

Misalkan A adalah matriks simetris n x n. Didefinisikan Δ k adalah determinan dari sudut atas-tangan kiri submatriks k x k dari A untuk 1 ≤ k ≤ n . Determinan Δ k disebut principal minor ke-k dari A.


⎛ a11 ⎜ ⎜ a12 A = ⎜ a13 ⎜ ⎜ M ⎜a ⎝ 1n

a12 a22 a23 a2 n

Δ1 = a11 , a13 L a1n ⎞ ⎟ a23 L a2 n ⎟ ⎛ a11 a12 ⎞ ⎜⎜ ⎟, Δ = det 2 a12 a22 ⎟⎠ a33 L a3n ⎟ , dengan ⎝ ⎟ M ⎟ M a3n L amn ⎟⎠ Δ n = det A.

Teorema 2.2.7

Jika A adalah matriks simetris n x n dan jika Δ k adalah principal minor ke-k dari A untuk 1 ≤ k ≤ n , maka: a

A adalah definit positif jika hanya jika Δ k > 0 untuk k = 1,2,..., n ;

b

A adalah definit negatif jika hanya jika (−1) k Δ k > 0 untuk k = 1,2,..., n .

Bukti :

Untuk membuktikan teorema ini digunakan metode induksi matematis, yaitu dengan dibuktikannya untuk n = k hingga n = k + 1 adalah benar. Pada pembuktian ini cukup dibuktikan untuk n = 2 dan n = 3 , maka n = k adalah benar. Untuk n = 2 adalah benar berdasarkan teorema 2.2.6, maka akan dibuktikan untuk n = 3 .

Misalkan

⎛ a11 ⎜ A = ⎜ a12 ⎜a ⎝ 13

a12 a22 a23

a13 ⎞ ⎟ a23 ⎟ a33 ⎟⎠

adalah matriks simetris 3 x 3 dan

x = ( x1 , x2 , x3 ) adalah vektor tak nol pada R3. Maka salah satu dari kedua ka-

sus ini harus dipenuhi:


Kasus I. ⎛a Jika x3 = 0 , maka x • Ax = ( x1 , x2 ) • ⎜⎜ 11 ⎝ a12

a12 ⎞⎛ x1 ⎞ ⎟⎜ ⎟ dan ( x1 , x2 ) ≠ (0,0) , sea22 ⎟⎠⎜⎝ x2 ⎟⎠

hingga berdasarkan teorema 2.2.6 menunjukkan a. x • Ax > 0 jika untuk setiap x ≠ 0 sedemikian sehingga x3 = 0 jika dan hanya jika Δ1 > 0, Δ 2 > 0 ; b. x • Ax < 0 jika untuk setiap x ≠ 0 sedemikian sehingga x3 = 0 jika dan hanya jika Δ1 < 0, Δ 2 > 0 .

Kasus II. Jika x3 ≠ 0 dan x2 = tx3 , x1 = sx3 untuk setiap bilangan real s, t, maka

(

)

x • Ax = x32 a11 s 2 + a22t 2 + a33 + 2a12 st + 2a13 s + 2a23t .

Sebagai akibatnya, karena x3 ≠ 0 diikuti dengan x • Ax > 0 untuk setiap x ≠ 0 sedemikian sehingga x3 ≠ 0 jika dan hanya jika

ϕ ( s, t ) = a11s 2 + a22t 2 + a33 + 2a12 st + 2a13 s + 2a23t > 0 untuk setiap bilangan real s, t. Pada penambahan, x • Ax < 0 untuk setiap x ≠ 0 sedemikian sehingga x3 = 0 jika daan hanya jika ϕ ( s, t ) < 0 untuk

setiap bilangan real s, t. Titik kritis dari ϕ ( s, t ) adalah solusi dari persamaan 0=

∂ϕ = 2a11s + 2a12t + 2a13 , ∂s

0=

∂ϕ = 2a12 s + 2a22t + 2a23 , ∂t


yaitu, a11s + a12t = −a13 , a12 s + a22t = − a23 .

Persamaan tersebut mempunyai solusi yang unik ( s * , t * ) jika dan hanya jika ⎛a Δ 2 = det ⎜⎜ 11 ⎝ a12

a12 ⎞ ⎟≠ 0, a22 ⎟⎠

dan solusi unik ini didapatkan dari Aturan Cramer`s yaitu s* =

⎛− a 1 det ⎜⎜ 13 Δ2 ⎝ − a23

a12 ⎞ ⎟, a22 ⎟⎠

− a13 ⎞ ⎟. − a23 ⎟⎠

⎛a 1 det ⎜⎜ 11 Δ2 ⎝ a12

t* =

…(9)

Jika persamaan a11s * + a12t * + a13 = 0 dikalikan dengan s*dan persamaan a12 s * + a22t * + a23 = 0 dikalikan dengan t*:

( )

a11 s *

2

+ a12 s *t * + a13 s * = 0

( )

a12 s *t * + a22 t *

2

+ a23t * = 0

dan menambahkan kedua persamaan tersebut hingga menghasilkan

( )

a11 s *

2

( )

+ a12 s *t * + a13 s * + a12 s *t * + a22 t *

( )

a11 s *

2

( )

+ a22 t *

2

2

+ a23t * = 0

+ 2a12 s *t * + a13 s * + a23t * = 0 .

Akibatnya,

ϕ ( s * , t * ) = a13 s * + a23t * + a33 , dan sehingga (9) diimplikasikan bahwa jika Δ 2 ≠ 0 , maka ⎛ a11 ⎜ ϕ ( s , t ) = det⎜ a12 ⎜a ⎝ 13 *

*

a12 a22 a23

a13 ⎞ ⎟ det A Δ 3 . = a23 ⎟ = Δ Δ 2 2 a33 ⎟⎠

…(10)


⎛ 2a Karena Hϕ ( s, t ) = det⎜⎜ 11 ⎝ 2a12

2a12 ⎞ ⎟ = 4Δ 2 , berdasarkan teorema 2.2.6 dan teo2a22 ⎟⎠

rema 2.2.5 yaitu ( s * , t * ) adalah pembuat minimum mutlak tegas untuk

ϕ ( s * , t * ) jika dan hanya jika Δ1 > 0, Δ 2 > 0 . Dengan cara yang sama, ( s * , t * ) adalah pembuat maksimum mutlak tegas untuk ϕ ( s * , t * ) jika dan hanya jika Δ1 < 0, Δ 2 > 0 .

Jika Δ1 > 0, Δ 2 > 0, Δ 3 > 0 , maka kesimpulan (a) pada kasus I menunjukkan bahwa jika x ≠ 0 dan x3 = 0 , maka x • Ax > 0 ; dengan kata lain, pada kasus II menunjukkan bahwa jika x ≠ 0 dan x3 ≠ 0 , x2 = tx3 , x1 = sx3 , maka x • Ax = x32ϕ ( s, t ) ≥ x32ϕ ( s * , t * ) = x32

Δ3 > 0. Δ2

Oleh karena itu, x • Ax > 0 untuk setiap x ≠ 0 jika Δ1 > 0, Δ 2 > 0, Δ 3 > 0 . Dengan kata lain, jika x • Ax > 0 untuk setiap x ≠ 0 , maka kesimpulan (a) dari kasus I menunjukkan bahwa Δ1 > 0, Δ 2 > 0 . Juga, jika x* = ( s * , t * ,1) , maka (10) menghasilkan

Δ3 = ϕ ( s * , t * ) = x • Ax > 0 , Δ2 maka Δ 3 > 0 . Hal ini membuktikan bagian (a) pada teorema 2.2.7. pembuktian bagian (b) pada teorema 2.2.7, bukti analog.■


Teorema 2.2.8 Misalkan fungsi f(x) dengan turunan pertama dan turunan parsial kedua pada suatu himpunan D di Rn. Misalkan x* adalah titik dalam dari D dan x* adalah titik kritis dari f(x). Maka x* adalah: a

Pembuat minimum relatif tegas dari f(x) jika Hf( x* ) adalah definit positif.

b

Pembuat maksimum relatif tegas dari f(x) jika Hf( x* ) adalah definit negatif.

Bukti : Didefinisikan Δ k (x) adalah principal minor ke-k dari Hf (x) . Dari hipotesa diketahui Δ k (x * ) > 0 untuk k = 0, 1, 2, …,n. Karena turunan kedua dari f(x) adalah kontinu, maka setiap Δ k (x) adalah fungsi dari x yang kontinu. Karena

Δ k (x* ) > 0 , dari kekontinuitasan ditunjukkan bahwa terdapat suatu bilangan rk > 0 pada setiap k sedemikian sehingga Δ k (x) > 0 jika x − x* < rk . Himpunan r = min{r1 , r2 ,..., rn } dan perhatikan bahwa untuk setiap k = 0, 1, 2, …,n didapatkan Δ k (x) > 0 jika x − x* < r . Oleh karena itu, berdasarkan teorema 2.2.6, matriks Hf(x) adalah definit positif jika x − x* < r . Jika 0 < x − x* < r , maka berdasarkan teorema 2.2.3 didapatkan

f (x) = f (x* ) + ∇f (x* ) • (x − x* ) + 12 (x − x* ) • Hf (z )(x − x* )


dimana z berada pada segmen garis x dan x*. Karena x − x * < r , maka didapatkan z − x* < r . Oleh sebab itu Hf(z) adalah definit positif. Akibatnya, jika 0 < x − x* < r , maka f (x) = f (x* ) + 0 + bilangan positif . Sehingga x − x* < r dan x ≠ x* menyatakan bahwa f (x) > f (x* ) , dimana x* adalah pembuat minimum relatif tegas dari f(x). Untuk x* pembuat maksimum relatif tegas, bukti analog.■

Contoh 2.2.4 f ( x1 , x2 ) = x13 + x23 − 3 x1 − 12 x2 + 20

Gambar 2.2.2 grafik fungsi f ( x1 , x2 ) = x13 + x23 − 3 x1 − 12 x2 + 20 ⎛ 3 x12 − 3 ⎞ ⎟ ∇f ( x ) = ⎜ 2 ⎜ 3 x − 12 ⎟ ⎝ 2 ⎠


⎛ 6x 0 ⎞ ⎟ Hf (x) = ⎜⎜ 1 6 x2 ⎟⎠ ⎝0 Menentukan titik kritis,

∂f (x) = 0 , i = 1, 2, maka ∂xi

∂f ( x) = 0 ∂x1

∂f ( x) = 0 ∂x2

3 x12 − 3 = 0

3 x22 − 12 = 0

x1 = ±1 Berdasarkan definisi 2.2.11

ϕ A (x) = x • Ax ⎛ 6 x 0 ⎞ ⎛ x1 ⎞ ⎟⎟ ⎜⎜ ⎟⎟ = ( x1 , x2 ) • ⎜⎜ 1 ⎝ 0 6 x2 ⎠ ⎝ x 2 ⎠

= ( x1 , x2 ) • (6 x12 ,6 x22 ) = 6 x13 + 6 x23

Untuk:

ϕ (1,2) = 6.13 + 6.2 3 = 54 ≥ 0, semidefinit positif.

ϕ (1,−2) = 6.13 + 12.(−2) 3 = −42 ≤ 0, semidefinit negatif.

ϕ (−1,2) = 6.(−1) 3 + 12.23 = 42 ≥ 0, semidefinit positif.

ϕ (−1,−2) = 6.(−1) 3 + 12.(−2) 3

x2 = ±2


= −54 ≤ 0, semidefinit negatif.

Mencari nilai optimum:

f (1,2) = 13 + 2 3 − 3.1 − 12.2 + 20 = 2 f (1,−2) = 13 + (−2) 3 − 3.1 − 12.( −2) + 20 = 34 f (−1,2) = (−1) 3 + 2 3 − 3.( −1) − 12.2 + 20 = 6

f (−1,−2) = (−1) 3 + (−2) 3 − 3.(−1) − 12.(−2) + 20 = 38 Pembuat minimum relatif terjadi pada titik (1,2) dan (-1,2). Pembuat maksimum relatif terjadi pada titik (1,-2) dan (-1,-2).▲


BAB III ALGORITMA GENETIKA

Algoritma Genetika adalah algoritma pencarian heuristik yang didasarkan atas mekanisme evolusi biologis. Algoritma genetika pertama kali dikembangkan oleh John Holland (1975), dan mempunyai ciri-ciri istimewa, yaitu : (1) representasi string bit, (2) seleksi yang seimbang (proporsional), dan (3) rekombinasi (crossover) sebagai metode utama untuk menghasilkan individu baru.

A. Latar Belakang Biologi Semua makhluk hidup terdiri dari sel-sel, dimana setiap selnya terdapat kumpulan kromosom yang sama. Kromosom adalah untaian dari DNA dan membentuk model yang akan membedakan makhluk hidup yang satu dengan makhluk hidup yang lain. Sebuah kromosom terdiri dari gen-gen yang merupakan blok-blok dari DNA. Setiap gen terbentuk dari protein tertentu, yang mengkodekan sebuah trait (ciri bawaan), misalnya : warna mata, warna kulit, dan lain-lain. Kemungkinan untuk mengatur sebuah trait disebut allele, misalnya mengatur warna untuk mata. Setiap gen mempunyai posisi tersendiri pada kromosom, disebut dengan locus. Kumpulan dari materi-materi gen (pada semua kromosom) disebut genome. Kumpulan yang terdiri dari gen-gen pada genome, disebut genotipe (genotype). Sebelum melakukan reproduksi, pertama kali yang akan muncul adalah rekombinasi (crossover atau rekombinasi). Gen-gen pada induk (parents) akan

50


membentuk kromosom baru, yang merupakan kombinasi dari kromosomkromosom kedua induk, yang akan membentuk anak (offspring) yang dapat bermutasi. Mutasi merupakan penggantian suatu gen pada suatu elemen di dalam

DNA.

Perubahan

tersebut

mungkin

dikarenakan

kesalahan

penggandaan gen-gen dari induknya. Untuk menyelesaikan masalah yang ada, maka dicari solusi terbaik dari semua kemungkinan solusi yang ada. Kumpulan semua solusi yang memungkinkan tersebut berada dalam ruang pencarian (search space). Setiap titik di dalam ruang pencarian merupakan satu solusi yang memungkinkan (feasible solution). Setiap solusi yang memungkinkan dapat diberi pengenal dalam bentuk nilai atau fitness dari permasalahan yang ada. Proses pencarian solusi menjadi rumit karena tidak diketahui dimana harus mencari. Banyak metode yang dikenal untuk menemukan solusi yang layak, diantaranya adalah Algoritma Genetika (Genetic Algorithm) yang dibuat berdasarkan analogi mekanisme yang terjadi terhadap proses evolusi.

B. Struktur Umum Algoritma Genetika Algoritma Genetika merupakan metode optimasi yang berdasarkan pada fenomena alam yang dalam penelusurannya mencari titik optimal berdasarkan ide yang ada pada genetika dan teori Darwin (1809-1882) yaitu “survival of the fittest” yang menyatakan bahwa evolusi jenis-jenis spesies makhluk hidup dan ekosistemnya terjadi karena seleksi alam. Individu yang lebih kuat (fit)


akan memiliki tingkat survival dan tingkat reproduksi yang lebih tinggi jika dibandingkan dengan individu yang kurang fit. Berbeda dengan teknik konvensional, algoritma genetika dimulai dengan memberikan himpunan awal (inisialisasi) dari solusi-solusi secara acak yang disebut populasi. Setiap individu pada populasi disebut kromosom (solusi yang masih berbentuk simbol), yang memodelkan sebuah solusi dari permasalahan yang ada. Kromosom yang berkembang setelah melalui beberapa iterasi disebut generasi. Setiap generasi kromosom dievaluasi dengan menggunakan alat ukur yang disebut dengan fitness. Generasi yang terbentuk dari gabungan dua kromosom dari generasi sekarang dengan menggunakan operator rekombinasi atau dengan memodifikasikan kromosom dengan menggunakan operator mutasi disebut anak (offspring). Populasi generasi yang baru dibentuk dengan cara menyeleksi nilai fitness dari kromosom induk dan nilai fitness dari kromosom anak, serta menolak kromosom-kromosom yang lainnya sehingga ukuran (jumlah kromosom) populasi konstan. Kromosom yang paling fit atau kromosom yang mempunyai nilai fitness yang paling besar (untuk permasalahan maksimum) atau nilai fitness yang paling kecil (untuk permasalahan minimum), yang mempunyai probabilitas paling tinggi yang akan dipilih. Istilah-istilah yang digunakan dalam algoritma genetika, dijelaskan dalam tabel dibawah ini:


Istilah dalam algoritma

Keterangan.

genetika Populasi

Himpunan beberapa solusi.

Kromosom

Solusi.

Gen

Bagian dari kromosom.

Induk (parent)

Solusi yang akan dikenakan proses rekombinasi atau mutasi.

Anak (Offspring)

Solusi baru yang dihasilkan melalui proses rekombinasi atau mutasi.

Rekombinasi

Proses yang melibatkan dua solusi untuk mendapatkan solusi baru.

Mutasi

Proses yang melibatkan satu solusi untuk mendapatkan solusi baru.

Seleksi

Pemilihan kromosom yang baik Tabel 3.2.1 Tabel istilah dalam Algoritma Genetika.

Struktur umum algoritma genetika (Mitsuo Gen dan Runwei Cheng, 1997) dapat pula dideskripsikan seperti pada gambar 3.2.1 berikut:


crossover chromosomes encoding solutions

1100101010 1011101110 0011011001 1100110001

1100101010 1011101110

1100101110 1011101010 mutation 0011011001

0011001001

selection new population

evaluation offspring 1100101110 1011101010 0011001001 decoding solutions fitness computation

Gambar 3.2.1. Ilustrasi Algoritma Genetika


Keterangan gambar 3.2.1. Dalam menyelesaikan masalah, algoritma genetika diawali dengan menginisialisasikan himpunan solusi yang dibangkitkan secara acak. Himpunan solusi ini disebut populasi. Setiap individu pada populasi disebut kromosom yang menggambarkan sebuah solusi dari masalah yang akan diselesaikan. Sebuah kromosom dapat dinyatakan dalam simbol string misalnya kumpulan string bit. Kromosom-kromosom dapat berubah terus menerus disebut dengan regenerasi. Pada setiap generasi, kromosom dievaluasi dengan mengunakan alat ukur yang disebut fungsi fittnes (tingkat kesesuaian). Untuk membuat generasi berikutnya, kromosom-kromosom baru yang disebut offspring (keturunan) terbentuk dengan cara menggabung dua kromosom dari generasi sekarang dengan menggunakan operator crossover (rekombinasi) atau mengubah sebuah kromosom dengan menggunakan operator mutasi. Generasi baru dibentuk dengan cara seleksi yang dilakukan terhadap induk dan anak berdasarkan nilai fitness-nya dan menghilangkan yang lainnya. Kromosom-kromosom yang lebih sesuai memiliki probabilitas untuk dipilih. Setelah beberapa generasi, algoritma ini akan konvergen ke arah bentuk kromosom yang terbaik, dengan harapan dapat menyatakan solusi optimal dari permasalahan yang diselesaikan.


C. Komponen-komponen Utama Algoritma Genetika 1. Teknik Penyandian Teknik penyandian meliputi penyandian gen dari kromosom. Satu gen biasanya akan mewakili satu variabel, dan dapat direpresentasikan dalam bentuk: string bit, pohon, array, bilangan real, daftar aturan, elemen permutasi, elemen program, atau representasi lainnya yang dapat diimplementasikan untuk operator genetika. Gambar 3.3.1.1 menunjukan representasi string bit. Biasanya penyandian kromosom

menggunakan

string biner. Setiap bit dalam string dapat merepresentasikan beberapa karateristik dari solusi.

0 1 0

1 0 0 1 10100111

Pengkodean nilai untuk variabel x1

Pengkodean nilai untuk variabel x2

Gambar 3.3.1.1 Representasi string bit

Pertama, variabel keputusan dikodekan ke dalam bentuk string biner. Panjang dari string tergantung pada ketepatan angkanya. Contohnya, domain dari xj adalah [aj, bj] dan ketepatan angkanya adalah 4 angka setelah desimal. Ketepatan tersebut diperlukan karena pada selang domain dari setiap variabel harus terbagi sedikitnya (bj-aj) × 10n (n=ketepatan angka) ukuran selang. Keharusan berapa bit (dinotasikan dengan mj) yang diperlukan untuk sebuah variabel dihitung dengan cara sebagai berikut : m j = 2 log[(b j − a j )10 n + 1]


2 mj −1 < (b j − a j ) × 10 n ≤ 2 mj − 1 .

Pemetaan dari string biner ke bilangan real untuk variabel xj secara sederhana dan lengkap ditunjukkan sebagai berikut: x j = a j + desimal( substring j ) ×

bj − a j 2 mj − 1

dimana desimal (substringj ) menunjukkan nilai desimal dari substringj untuk variabel keputusan xj. Panjang kromosom keseluruhan adalah

n

∑m j =1

j

bit (dimana j adalah

banyaknya variabel yang digunakan) dan direpresentasikan sebagai berikut: 33 bit vj 000001010100101001 101111011111110 18 bit 15bit

Gambar 3.3.1.2 representasi panjang kromosom

Nilai biner

Nilai desimal

x1 000001010100101001

5417

x2 101111011111110

24318

Tabel 3.3.1.1 pemetaan nilai biner ke nilai real

2. Prosedur Inisialisasi Ukuran populasi tergantung dari permasalahan yang akan diselesaikan dan jenis operator genetika yang akan diimplementasikan. Setelah ukuran populasi ditentukan, kemudian dilakukan inisialisasi terhadap kromosom


yang terdapat dalam populasi tersebut. Inisialisasi kromosom dilakukan secara acak, namun harus tetap memperhatikan domain solusi dan kendala permasalahan yang ada.

3. Fungsi Evaluasi (fitness function) Secara umum, fungsi evaluasi diturunkan dari fungsi objektif (fungsi tujuan) dengan nilai yang tidak negatif. Apabila ternyata fungsi tujuan memiliki nilai negatif, maka perlu ditambahkan suatu konstanta C agar nilai fitness yang terbentuk menjadi tidak negatif. Proses dari penentuan fitness dari sebuah kromosom terdiri dari tiga langkah, yaitu: 1. Tukar kromosom genotip ke kromosom penotip. Artinya, tukar string biner ke nilai real relatif xk = (x1, x2), k = 0, 1, 2, …, ukuran populasi. 2. Hitung fungsi tujuan f(xk). 3. Tukar nilai dari fungsi tujuan ke fitness. Untuk permasalahan maksimum, nilai fitness sebanding dengan nilai fungsi tujuannya, eval (vk ) = f ( xk ), k = 0, 1, 2, ..., ukuran populasi . Dari penghitungan tersebut, akan dapat dilihat kromosom yang terkuat, mempunyai nilai fitness paling besar dan kromosom yang paling lemah, mempunyai nilai fitness yang paling kecil.


4. Seleksi Tujuan dari seleksi adalah untuk menentukan individu-individu mana saja yang akan dipilih untuk dilakukan rekombinasi dan mutasi. Metode seleksi yang paling sering digunakan adalah Rank-based assignment, Roulette wheel selection (seleksi roda roulette), dan tournament selection (seleksi dengan turnamen). Seleksi akan menentukan individu-individu mana saja yang akan dipilih untuk dilakukan rekombinasi dan bagaimana anak terbentuk dari individu-individu terpilih tersebut. 4.1. Seleksi Roda Rolet (roulette-wheel) Metode seleksi roda rolet merupakan metode yang paling sederhana, dan sering juga dikenal dengan nama stochastic sampling with replacement. Metode ini menirukan permainan roulette-wheel di mana masing-masing kromosom menempati potongan lingkaran pada roda rolet secara proporsional sesuai dengan nilai fitnessnya. Kromosom yang mempunyai nilai fitness lebih besar menempati potongan lingkaran yang lebih besar dibandingkan dengan kromosom bernilai fitness rendah. Gambar 3.4.1.1 ilustrasi sebuah contoh penggunaan metode roda roulette. K4

Kromosom K1 K2 K3 K4 Jumlah

Nilai Fitness 1 2 0.5 0.5 4

Probabilitas 0.25 0.5 0.125 0.125

K1

K3

K2

Gambar 3.4.1.1 Contoh penggunaan metode seleksi roda roulette.


Kromosom K1 mempunyai probabilitas 25% untuk dipilih setiap kali suatu kromosom dipilih (setiap roda diputar). Probabilitas masingmasing individu dapat dicari dari pembagian fitness masing-masing individu dengan total fitness dalam populasi. Seleksi dengan roda rolet berdasarkan skala fitness. Karena terpilihnya suatu kromosom dalam populasi untuk dapat berkembang biak

adalah

sebanding

dengan

fitnesnya,

maka

akan

terjadi

kecenderungan kromosom yang baik akan terpelihara terus sehingga dapat membawa ke hasil optimum lokal (konvergensi dini) ke suatu hasil yang bukan optimum global. Sebaliknya, jika semua kromosom dalam populasi mempunyai fitness yang hampir sama, maka seleksi ini akan menjadi seleksi yang bersifat acak.

4.2. Seleksi Ranking Seleksi dengan roda rolet sebelumnya memiliki kelemahan ketika fitness yang tersebar dalam populasi berbeda jauh misalnya jika fitness dari kromosom terbaik dalah 90% dari keseluruhan roda rolet, maka kromosom lain akan mempunyai kesempatan yang kecil untuk terpilih. Pada

seleksi

ranking,

pertama

dilakukan

merangkingkan

kromosom dalam populasi kemudian setiap kromosom menerima nilai fitness dari ranking tersebut. Kromosom yang terjelek akan mendapatkan nilai fitness 1, terjelek kedua mendapat nilai fitness 2 dan seterusnya


sampai yang terbaik mendapatkan nilai fitness N (jumlah kromosom dalam populasi). Sebagai ilustrasi dapat dilihat pada tabel. Kromosom

Fitnes

Fitnes Baru

B 5 1 D 5 2 E 5 3 C 10 4 A 15 5 Tabel 3.4.2.1 Contoh populasi dengan 5 kromosom yang diberi fitness baru

4.3. Seleksi Turnamen Seleksi turnamen

merupakan

jenis seleksi yang

divariasi

berdasarkan seleksi roda rolet dan seleksi ranking. Sejumlah k kromosom tertentu dari populasi dengan n kromosom (k ≤ n) dipilih secara acak dengan probabilitas yang sama. Dari k kromosom yang terpilih tersebut kemudian dipilih suatu kromosom dengan fitness terbaik, yang diperoleh dari hasil pengurutan rangking fitness kromosom-kromosom yang dipilih tersebut. Perbedaan dengan seleksi roda Roulette adalah bahwa pemilihan kromosom yang akan digunakan untuk berkembang biak tidak berdasarkan skala fitness dari populasi. Untuk k = 1, seleksi turnamen ini akan sama dengan seleksi secara acak karena hanya melibatkan satu kromosom. Untuk k = 2, maka dua kromosom dalam populasi akan dipilih secara acak, kemudian dari dua kromosom tersebut dipilih satu kromosom dengan fitness tersebut. Biasanya yang sering digunakan adalah untuk k = 2 tergantung dari ukuran populasi.


5. Operator Genetika Ada 2 operator genetika, yaitu: 5.2

Rekombinasi (crossover) Pada skripsi ini operator rekombinasi yang akan digunakan adalah rekombinasi bernilai biner. Rekombinasi bernilai biner terdiri dari : rekombinasi satu titik, rekombinasi banyak titik, dan rekombinasi seragam. Rekombinasi yang akan digunakan dalam skripsi ini adalah rekombinasi satu titik. Pada rekombinasi satu titik, posisi rekombinasi k,(k = 1, 2, …, N-1) dengan N = panjang kromosom, diseleksi secara random. Variabel-variabel ditukar antar kromosom pada titik tersebut untuk menghasilkan anak (Gambar 3.5.1.1). induk 011 000111101

anak 011 001010100

111 001010100

111 000111101

Gambar 3.5.1.1 Rekombinasi satu titik.

Pertama, ditentukan terlebih dahulu probabilitas rekombinasi, pada skripsi ini probabilitas rekombinasi adalah 0.25 dengan harapan 25% dari kromosom akan mengalami rekombinasi. Dibangkitkan bilangan dari selang [0, 1] secara acak sebanyak jumlah populasi, jika bilangan tersebut kurang dari 0.25, maka bilangan tersebut terpilih untuk menjadi induk. Setidaknya dua kromosom yang harus


terpilih untuk menjadi induk. Bilangan tersebut akan menentukan populasi ke-berapa yang akan menjadi induk. Setelah induk terpilih, bangkitkan posisi rekombinasi atau pos secara acak dari selang [1, panjang kromosom-1]. Tukar kromosom dari induk1 ke induk2 pada pos yang telah ditentukan. Hasil yang didapat dinamakan anak.

5.2

Mutasi Setelah mengalami proses rekombinasi, pada anak dapat dilakukan mutasi. Variabel anak dimutasi dengan menambahkan nilai random yang sangat kecil, dengan probabilitas rendah. Peluang mutasi (pm) didefinisikan sebagai presentasi dari jumlah total gen pada populasi yang mengalami mutasi. Kromosom hasil mutasi harus diperiksa, apakah masih berada dalam domain solusi, dan bila perlu bisa dilakukan perbaikan. Mutasi berperan untuk menggantikan gen yang hilang dari populasi akibat proses seleksi yang memungkinkan munculnya kembali gen yang tidak muncul pada inisialisasi populasi. Mutasi terdiri dari mutasi bernilai real dan mutasi bernilai biner. Mutasi yang akan digunakan pada skripsi ini adalah mutasi biner. Langkah-langkah dari mutasi biner adalah ; i. Hitung jumlah gen pada populasi (panjang kromosom dikalikan dengan ukuran populasi).


ii. Tentukan probabilitas mutasi. Pada skripsi ini probabilitas yang digunakan adalah 0.01, sehingga diharapkan 1% dari jumlah gen mengalami mutasi. iii. Secara acak tentukan posisi mutasi, nomor kromosom, nomor bit, dan bilangan dari selang [0, 1]. iv. Ganti nilai gen (0 ke 1, atau 1 ke 0) dari kromosom yang akan dimutasi tersebut.

Hasil dari mutasi disebut anak. Hasil dari mutasi dan rekombinasi dimasukkan ke dalam populasi baru yang kemudian akan dihitung nilai fitness-nya. Nilai fitness yang terbaik akan masuk ke dalam populasi sebelumnya Agar populasi tetap konstan, maka kromosom yang mempunyai nilai fitness yang terburuk akan digantikan dengan kromosom anak yang mempunyai nilai fitness terbaik.

6. Penentuan Parameter Yang dimaksud dengan parameter disini adalah parameter kontrol Algoritma Genetika, yaitu ukuran populasi (popsize), peluang rekombinasi (Pc), dan peluang mutasi (Pm). Nilai parameter ditentukan dengan berdasarkan permasalahan yang akan diselesaikan. Ada beberapa rekomendasi yang bisa digunakan, antara lain:


i.

Untuk permasalahan yang memiliki kawasan solusi cukup besar, De Jong merekomendasikan untuk nilai parameter kontrol: (uk_populasi; pc; pm) = (50; 0.6; 0.001).

ii.

Bila rata-rata fitness setiap generasi digunakan sebagai indikator, maka Grefenstette merekomendasikan: (uk_populasi; pc; pm) = (30; 0.95; 0.01).

iii.

Bila fitness dari individu terbaik dipantau pada setiap generasi, maka diusulkan: (uk_populasi; pc; pm) = (80; 0.45; 0.01).

iv.

Ukuran populasi sebaiknya tidak lebih kecil dari 30, untuk sembarang jenis permasalahan.


BAB IV OPTIMASI FUNGSI TANPA KENDALA DENGAN ALGORITMA GENETIKA

Pada bab ini akan diberikan contoh-contoh dari permasalahan optimasi pemrograman tak linear fungsi dua variabel tanpa kendala. Permasalahan-permasalahan tersebut akan diselesaikan dengan teknik konvensional menggunakan kalkulus, serta dengan Algoritma Genetika.

Contoh 4.1 Permasalahan optimasi tanpa kendala diberikan sebagai berikut: Maksimumkan f (x1 , x2 ) = x12 + 2 x1 x2 + x22

0.1 ≤ x1 ≤ 10 4 .5 ≤ x 2 ≤ 9

Temukan nilai optimum dengan menggunakan Algoritma Genetika dan dengan teknik konvensional.

a) Dengan Teknik Konvensional (Kalkulus).

f (x1 , x2 ) = x12 + 2 x1 x2 + x22 , dengan 0.1 ≤ x1 ≤ 10 , 4.5 ≤ x2 ≤ 9

66


Gambar 4.1 grafik fungsi f (x1 , x2 ) = x12 + 2 x1 x2 + x22

Menentukan titik kritis: ⎛ 2 x + 2 x2 ⎞ ⎟⎟ ∇f = ⎜⎜ 1 ⎝ 2 x1 + 2 x2 ⎠

⎛ 2 2⎞ ⎟⎟ Hf = ⎜⎜ ⎝ 2 2⎠ ∂f ( x) = 0 ∂ ∂f ( x1 ) = 2 x1 + 2 x2 ∂

∂f ( x2 ) = 2 x1 + 2 x2 ∂

0 = 2 x1 + 2 x2

0 = 2 x1 + 2 x2

x1 = − x2

x1 = − x2

Titik kritis tidak diketahui. Berdasarkan teorema 2.1.2, maka


Untuk f(0.1, 4.5)

f (x ) = (0.1) 2 + 2(0.1) 2 (4.5) + (4.5) 2 = 0.01 + 0.9 + 20.25

= 21.16

Untuk f(10, 9) f (x ) = (10) 2 + 2(10) 2 (9) + (9) 2 = 100 + 180 + 81

= 361

Nilai maksimum 361, dan nilai minimum 21.16.

b) Dengan Algoritma Genetika.

Representasi Masalah Misalkan ketepatan angka untuk menyelesaikan permasalahan optimasi di atas adalah empat tempat setelah desimal. Dan iterasi yang akan dicapai adalah 100 iterasi. Jumlah populasi yang akan terjadi adalah 10, akan ditentukan berapa bit yang harus digunakan untuk variabel x1 dan x2 : m1 = 2 log[(batas bawah − batas atas)10 4 + 1]= 2 log[(10 − 0.1)10 4 + 1] = 16.59 ≈ 17 (10-0.1) × 104 = 99,000 216 < 99,000 ≤ 217 m1 = 2 log[(batas bawah − batas atas)10 4 + 1]= 2 log[(9 − 4.5)10 4 + 1] = 15.45 ≈ 16 (9-4.5) × 104 = 45,000


215 < 45,000 ≤ 216 Total bit dalam tiap kromosom (panjang kromosom) adalah (17 + 16)bit = 33 bit. Untuk rekombinasi dan mutasi akan diuji pada probabilitas rekombinasi antara 0.2 hingga 0.5, dan mutasi pada probabilitas 0.01 hingga 0.1. Sehingga, rekombinasi kromosom akan terjadi apabila bilangan acak rekombinasi [0, 1] lebih kecil atau sama dengan probabilitas rekombinasinya. Begitu pula dengan mutasi, apabila bilangan acak mutasi [0, 1] lebih kecil atau sama dengan probabilitas mutasi, maka mutasi kromosom akan terjadi. Dari 10 percobaan akan dicari nilai maksimum yang mempunyai selisih 5% dari teknik konvensional. Setiap percobaan diuji pada 100 generasi.

Untuk permasalahan maksimum:


Pc = 0.2 Nilai Terbesar Pada Titik 10 kali Percobaan

Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Banyak Percobaan

tidak ada yang memenuhi

348.1101 347.9697 348.1439

(9.9578, 8.6999) (9.9578, 8.6999) (9.9587, 8.6953)

1 2 1

tidak terjadi

Tabel 4.1 Tabel nilai maksimum fungsi f (x1 , x2 ) = x12 + 2 x1 x2 + x22 dengan

probabilitas rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1.

10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 Probabilitas Mutasi

Gambar 4.2 Grafik terjadinya nilai maksimum f (x1 , x2 ) = x12 + 2 x1 x2 + x22

dengan probabilitas rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1.

Dari tabel 4.1 dan gambar 4.2 terlihat bahwa percobaan terbanyak untuk mendapatkan solusi terbaik terjadi pada probabilitas mutasi 0.07.


Pm


0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Banyak Percobaan


343.7628

(9.9587, 8.6999) tidak terjadi

2



10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0.08

0.09

0.1

Probabilitas Mutas i





Pm


0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Banyak Percobaan


348.1439 348.1439 348.1491 335.6864 347.5269

(9.9587, 8.6999) (9.9587, 8.6999) (9.9587, 8.7001) (9.3393, 8.9824) (9.9421, 86999)

1 1 2 1 1

Tabel 4.3 Tabel nilai maksimum fungsi dengan probabilitas rekombinasi

0.3 dan probabilitas mutasi 0.01 hingga 0.1.

10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0






Pm


0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Banyak Percobaan


358.67 348.1439 348.2313 348.1439

(9.9574, 8.9812) (9.9587, 8.6999) tidak terjadi (9.9610, 8.6999) (9.9568, 8.6999)

1 1 3 2



10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0






Pm


0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Banyak Percobaan

tidak ada yang memenuhi 343.6813 (9.8762, 8.6624) tidak ada yang memenuhi 348.1439 (9.9587, 8.6999) tidak ada yang memenuhi 346.3638 (9.9484, 8.6624) 358.6958 (9.9581, 8.9812) 348.096 (9.9574, 8.6999) 348.1468 (9.9588, 8.6999)

1 2 1 2 1 1



10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0






Pm


0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Banyak Percobaan

tidak ada yang memenuhi 348.1439 348.2249 348.1496 359.0371 349.5406 348.1439

(9.9587, 8.6999) (9.9433, 8.7175) (9.9588, 8.6999) (9.9484, 8.9999) (9.9961, 8.6999) (9.9587, 8.6999)

1 1 1 1 2 1



10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0






Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Pc = 0.5 Nilai Terbesar Pada Titik 10 kali Percobaan 348.14398 (9.9587, 8.6999)

Banyak Percobaan 1


343.3662 350.2321

(9.8325, 8.6976) (9.9970, 8.7175)

1 3



10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0






Dari grafik-grafik di atas, terlihat bahwa nilai maksimum yang mendekati dengan pencarian teknik konvensional serta mengalami percobaan terbanyak adalah dengan menggunakan probabilitas mutasi 0.08. Akan dilihat berdasarkan probabilitas mutasi (pada probabilitas mutasi 0.08).

Pc 0.2 0.25 0.3 0.35 0.4 0.45 0.5

Pm = 0.08 Nilai Terbesar Pada Titik 10 kali Percobaan 348.1439 (9.9587, 8.6953) tidak ada yang memenuhi 348.1491 (9.9587, 8.7001) tidak ada yang memenuhi 358.6958 (9.9581, 8.9812) 359.0371 (9.9484, 8.9999) tidak ada yang memenuhi

Banyak Percobaan 1 2 2 2


probabilitas rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08.

10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5

Probabilitas Rekom binas i


dengan probabilitas rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08.


Dari tabel 4.8 terlihat bahwa percobaan terbanyak untuk mendapatkan solusi terbaik terjadi pada probabilitas rekombinasi 0.4 dan 0.45 dengan probabilitas mutasi 0.08.

Contoh 4.2

Permasalahan optimasi tanpa kendala diberikan sebagai berikut: f (x1 , x2 ) = 3x12 x2 − 9 x23 − x12 + 1 Temukan nilai optimum dengan menggunakan Algoritma Genetika dan dengan teknik konvensional.

Gambar 4.10 grafik fungsi f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1

a) Dengan Teknik Konvensional (Kalkulus)

Menentukan titik kritis:


⎛ 6 x x − 2 x1 ⎞ ⎟ ∇f = ⎜⎜ 12 2 2⎟ ⎝ 3 x1 − 27 x2 ⎠

∂f ( x) = 0 ∂ ∂f ( x2 ) = 3 x12 − 27 x22 ∂

∂f ( x1 ) = 6 x1 x2 − 2 x1 ∂

0 = x12 − 9 x22

0 = x1 (3 x2 − 1)

x1 = 0 atau x2 =

1 3

untuk x1 = 0 , x2 = 0 untuk x2 = 1 , x1 = ±1 . 3

f(x) mempunyai tiga titik kritis, yaitu: p1 = (0,0), p2 = (1, 1 ), p3 = (−1, 1 ) 3 3

Dengan berdasarkan teorema 2.2.6, maka

∂f ( x1 x1 ) = 6 x1 − 2 ∂ ∂f ( x1 x2 ) = 6 x1 ∂ ∂f ( x2 x2 ) = −54 x2 ∂ ⎛ ∂f ⎜ ∂x x Δf (x) = ⎜ 1 1 ⎜ ∂f ⎜ ∂x x ⎝ 1 2

∂f ⎞ ⎟ ∂x1 x2 ⎟ ∂f ⎟ ∂x2 x2 ⎟⎠

⎛ ∂f ⎞ ∂f ∂f ⎟ − ⎜⎜ = ∂x1 x1 ∂x2 x2 ⎝ ∂x1 x2 ⎟⎠

2


= (6 x1 − 2)(−54 x2 ) − (6 x1 ) 2

= −36 x1 + 324 x1 x2 + 108 x2 2

Untuk p1 = (0,0), Δf (x) = 0 ; p1 tidak memberikan penyelesaian.

p2 = (1, 1 ), Δf (x) = 108 > 0 ; berdasarkan teorema 2.2.7 Δf (x) 3

definit

positif. p3 = (−1, 1 ), Δf (x) = −108 < 0 ; berdasarkan teorema 2.2.7 Δf (x) definit 3 negatif.

Pada titik (1, 1 ), (−1, 1 ) akan diuji dengan menggunakan definisi 2.2.11. 3 3 Q A = x • Ax , dengan A = Δf (x) 6 x1 ⎞ ⎛ 6x − 2 ⎟ = ( x1 , x2 ) • ⎜⎜ 2 − 54 x2 ⎟⎠ ⎝ 6 x1

⎛ x1 ⎞ ⎜⎜ ⎟⎟ ⎝ x2 ⎠

= ( x1 , x2 ) • (6 x1 x2 − 2 x1 + 6 x1 x2 , 6 x12 − 54 x22 ) = 12 x12 x2 + 4 x12 − 54 x23

Berdasarkan definisi 2.2.11, maka

( )

( )

3

Untuk titik (1, 1 ) : Q A (x) = 12 1 + 4 − 54 1 = 6 > 0 adalah pembuat 3 3 3 minimum relatif.


( )

( )

3

Untuk titik (−1, 1 ) : QA (x) = 12 1 + 4 − 54 1 = 6 > 0 adalah pembuat 3 3 3 minimum relatif.

Mencari nilai optimum Untuk f (1, 1 ) 3 f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 = 3.12. 13 − 9.( 1 3 ) 3 − 12 + 1 = 0.66

Untuk f (−1, 1 ) 3 f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 = 3.(−1) 2 . 1 3 − 9.( 1 3 ) 3 − (−1) 2 + 1 = 0.66

Minimum relatif terjadi pada titik (1, 1 ), (−1, 1 ) . 3 3

b) Dengan Algoritma Genetika Representasi Masalah Misalkan ketepatan angka untuk menyelesaikan permasalahan optimasi di atas adalah empat tempat setelah desimal. Dan iterasi yang akan dicapai adalah 100 iterasi. Jumlah populasi yang akan terjadi adalah 10, akan ditentukan berapa bit yang harus digunakan untuk variabel x1 dan x2 :


m1 = 2 log[(batas bawah − batas atas)10 4 + 1]= 2 log[(1 + 1)10 4 + 1] = 14.2878 ≈ 15 (1+1) × 104 = 20,000 214 < 20,000 ≤ 215 m2 = 2 log[(batas bawah − batas atas)10 4 + 1]= 2 log[(1 + 1)10 4 + 1] = 14.2878 ≈ 15 (1+1) × 104 = 20,000 214 < 20,000 ≤ 215 Total bit dalam tiap kromosom (panjang kromosom) adalah (15 + 15)bit = 30 bit. Untuk rekombinasi dan mutasi akan diuji pada probabilitas rekombinasi antara 0.2 hingga 0.5, dan mutasi pada probabilitas 0.01 hingga 0.1. Sehingga, rekombinasi kromosom akan terjadi apabila bilangan acak rekombinasi [0, 1] lebih kecil atau sama dengan probabilitas rekombinasinya. Begitu pula dengan mutasi, apabila bilangan acak mutasi [0, 1] lebih kecil atau sama dengan probabilitas mutasi, maka mutasi kromosom akan terjadi. Dari 10 percobaan akan dicari nilai maksimum yang mempunyai selisih 0.5% dari teknik konvensional. Dan nilai minimum yang mempunyai selisih 5% dari teknik konvensional. Setiap percobaan diuji pada 100 generasi.

Untuk permasalahan maksimum:


Pc = 0.2 Nilai Terbesar Pada Titik 10 kali Percobaan 0.9958 (0.0645, 0.0001) 0.9971 (0.0500, 0.0444) 0.9955 (0.0666, 0.0418) 1 (0.0002, 0.0001) 0.9958 (0.0666, 0.0209) 0.9992 (0.0041, 0.0444) 1 (0.0001, 0.0001) 1 (0.0041, 0.0001) 0.9961 (0.0626, 0.0055) 1 (0.0000, 0.0055)

Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Banyak Percobaan 6 5 4 4 6 8 8 5 5 6

Tabel 4.9 Tabel nilai maksimum fungsi f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 dengan probabilitas rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1.

9

Banyak Percobaan

8 7 6 5 4 3 2 1 0 0

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 Probabilitas Mutas i

Gambar 4.11 Grafik terjadinya nilai maksimum fungsi f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 dengan probabilitas rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1.

Dari tabel 4.9 dan gambar 4.11 terlihat bahwa percobaan terbanyak untuk mendapatkan solusi terbaik terjadi pada probabilitas mutasi 0.06 dan 0.07.


Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Pc = 0.25 Nilai Terbesar Pada Titik 10 kali Percobaan 0.9957 (0.0666, 0.0165) 0.9957 (0.0666, 0.0110) 0.9983 (-0.0417, 0.0001) 1 (0.0041, 0.0007) 1 (0.0041, 0.0006) 1 (0.0041, 0.0006) 1 (0.0041, 0.0105) 1 (0.0041, 0.0002) 1 (0.0041, 0.0082) 1 (0.0001, 0.0001)



9

Banyak Percobaan

8 7 6 5 4 3 2 1 0 0

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09

0.1

Probabilitas Mutasi

Gambar 4.12 Grafik terjadinya nilai maksimum f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 dengan probabilitas rekombinasi 0.25 dan probabilitas mutasi 0.01 hingga 0.1.



Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Pc = 0.3 Nilai Terbesar Pada Titik 10 kali Percobaan 0.9989 (0.0334, 0.0110) 0.9992 (0.0013, 0.0444) 1 (0.0041, 0.0001) 0.9983 (0.0333, 0.0444) 0.9992 (0.0041, 0.0444) 1 (0.0041, 0.0001) 1 (0.0041, 0.0001) 1 (0.0000, 0.0001) 1 (0.0041, 0.0001) 0.9992 (0.0041, 0.0444)


Tabel 4.11 Tabel nilai maksimum f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 dengan probabilitas rekombinasi 0.3 dan probabilitas mutasi 0.01 hingga 0.1.

9

Banyak Percobaan

8 7 6 5 4 3 2 1 0 0





Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Tabel 4.12

Pc = 0.35 Nilai Terbesar Pada Titik 10 kali Percobaan 0.9971 (0.0500, 0.0444) 0.9958 (0.0666, 0.0193) 0.9996 (0.0208, 0.0082) 1 (0.0042, 0.0001) 0.9975 (0.0500, 0.0001) 1 (0.0041, 0.0006) 0.9997 (0.0187, 0.0014) 1 (0.0041, 0.0001) 1 (0.0000, 0.0001) 1 (0.0002, 0.0001)


Tabel nilai maksimum fungsi f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1


9

Banyak Percobaan

8 7 6 5 4 3 2 1 0 0

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09

0.1

Probabilitas Mutasi




Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Tabel 4.13

Pc = 0.4 Nilai Terbesar Pada Titik 10 kali Percobaan 0.9975 (0.0500, 0.0001) 1 (0.0041, 0.0009) 0.9992 (0.0041, 0.0444) 1 (0.0041, 0.0001) 1 (0.0041, 0.0110) 0.9992 (0.0041, 0.0444) 0.9992 (0.0041, 0.0444) 1 (0.0041, 0.0110) 0.9992 (0.0041, 0.0444) 0.9993 (0.0041, 0.0418)


Tabel nilai maksimum fungsi f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1


10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0





Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Pc = 0.45 Nilai Terbesar Pada Titik 10 kali Percobaan 0.9983 (0.0333, 0.0444) 1 (0.0020, 0.0006) 1 (0.0041, 0.0002) 1 (0.0041, 0.0014) 1 (0.0002, 0.0001) 0.9989 (0.0333, 0.0110) 1 (0.0002, 0.0004) 0.9999 (0.0040, 0.0165) 0.9989 (0.0332, 0.0105) 1 (0.0041, 0.0110)



10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0





Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Pc = 0.5 Nilai Terbesar Pada Titik 10 kali Percobaan 0.9976 (0.0500, 0.0082) 1 (0.0041, 0.0055) 1 (0.0041, 0.0136) 0.9971 (0.0498, 0.0444) 1 (0.0001, 0.0001) 1 (0.0020, 0.0001) 0.9992 (0.0052, 0.0444) 1 (0.0001, 0.0055) 0.9957 (0.0666, 0.0139) 0.9997 (0.0177, 0.0027)



10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0



Dari tabel 4.15 dan gambar 4.17 terlihat bahwa percobaan terbanyak untuk mendapatkan solusi terbaik terjadi pada probabilitas mutasi 0.03. Dari gambar di atas, terlihat bahwa pada probabilitas mutasi 0.08 percobaan lebih banyak terjadi untuk mendapatkan solusi optimal.


Untuk permasalahan minimum: Pc = 0.2 Nilai Terkecil Pada Titik 10 kali Percobaan 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0.0002 (-1.0000, 0.0001) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000)

Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1


Tabel 4.16 Tabel nilai minimum fungsi f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 dengan probabilitas rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1.

10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0


Gambar 4.18 Grafik terjadinya nilai minimum fungsi f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 dengan probabilitas rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1.



Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Pc = 0.25 Nilai Terkecil Pada Titik 10 kali Percobaan 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0.0002 (-1.0000, 0.0001) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0.0004 (-0.9999, 0.0001) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000)



10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0


Gambar 4.19 Grafik terjadinya nilai minimum f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 dengan probabilitas rekombinasi 0.25 dan probabilitas mutasi 0.01 hingga 0.1.



Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Pc = 0.3 Nilai Terkecil Pada Titik 10 kali Percobaan 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0.0413 (-0.9792, 0.0001) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000)


Tabel 4.18 Tabel nilai minimum f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 dengan probabilitas rekombinasi 0.3 dan probabilitas mutasi 0.01 hingga 0.1.

10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0





Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Pc = 0.35 Nilai Terkecil Pada Titik 10 kali Percobaan 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0.0084 (-0.9959, 0.0001) 0 (-1.0000, 0.0000) 0.0006 (-0.9998, 0.0001) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000)



10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0





Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Tabel 4.20

Pc = 0.4 Nilai Terkecil Pada Titik 10 kali Percobaan 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0.0002 (-1.0000, 0.0001) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0.0063 (-0.9969, 0.0001)


Tabel nilai minimum fungsi f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1


10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0





Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Pc = 0.45 Nilai Terkecil Pada Titik 10 kali Percobaan 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0.001 (-0.9334, 0.0001) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000)



10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0





Pm 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

Pc = 0.5 Nilai Terkecil Pada Titik 10 kali Percobaan 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0.0043 (-0.9980, 0.0001) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000) 0 (-1.0000, 0.0000)



10

Banyak Percobaan

9 8 7 6 5 4 3 2 1 0 0





Dari grafik-grafik di atas, terlihat bahwa nilai maksimum dan minimum yang mendekati dengan pencarian teknik konvensional adalah dengan menggunakan probabilitas mutasi 0.08. Akan dilihat berdasarkan probabilitas mutasi (pada probabilitas mutasi 0.08).

Pc 0.2 0.25 0.3 0.35 0.4 0.45 0.5

Pm = 0.08 Nilai Terbesar Pada Titik 10 kali Percobaan 1 (0.0041, 0.0001) 1 (0.0041, 0.0002) 1 (0.0000, 0.0001) 1 (0.0041, 0.0001) 0.9999 (0.0040, 0.0165) 1 (0.0001, 0.0055) 1 (0.0041, 0.0110)

Banyak Percobaan 5 8 8 7 9 6 9

Tabel 4.23 Tabel nilai maksimum fungsi f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 dengan probabilitas rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08.

10 9 8 7 6 5 4 3 2 1 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5

Pr o b ab i l i t as R eko mb i nasi

Gambar 4.25 Grafik terjadinya nilai maksimum f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 dengan probabilitas rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08.


Pm = 0.08 Nilai Terbesar Pada Pc Titik 10 kali Percobaan 0.2 0 (-1.0000, 0.0000) 0.25 0.0004 (-0.9999, 0.0001) 0.3 0.0413 (-0.9792, 0.0001) 0.35 0 (-1.0000, 0.0000) 0.4 0 (-1.0000, 0.0000) 0.45 0 (-1.0000, 0.0000) 0.5 0 (-1.0000, 0.0000)

Banyak Percobaan 6 2 1 6 6 2 6

Tabel 4.24 Tabel nilai minimum fungsi f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1

Banyak Percobaan

dengan probabilitas rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08.

10 9 8 7 6 5 4 3 2 1 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5

Probabilitas Rekom binasi

Gambar 4.26 Grafik terjadinya nilai minimum f (x1 , x2 ) = 3 x12 x2 − 9 x23 − x12 + 1 dengan probabilitas rekombinasi 0.2-0.5 dan probabilitas mutasi 0.08.

Dari tabel 4.23 dan gambar 4.24 terlihat bahwa percobaan terbanyak untuk mendapatkan solusi terbaik terjadi pada probabilitas rekombinasi 0.45 dengan probabilitas mutasi 0.08.


Contoh 4.3 Permasalahan optimasi tanpa kendala diberikan sebagai berikut: Maksimumkan f (x1, x2 ) = x1 e − ( x1 + x2 ) 2

2

− 3 ≤ x1 ≤ 2 0 ≤ x2 ≤ 2

Gambar 4.27 grafik fungsi f (x1, x2 ) = x1 e − ( x1 + x2 ) 2

2

Temukan nilai maksimum dengan menggunakan teknik konvensional dan

a) Dengan Teknik Konvensional (Kalkulus)

Menentukan titik kritis : ⎛ (2 x + x 2 )e − ( x1 + x2 ) ⎞ ∇f = ⎜ 1 2 1 − ( x 2 + x 2 ) ⎟ ⎜ − 2x x e 1 2 ⎟ ⎝ ⎠ 1 2 2

⎛ 2(− x 3 − x 2 + x + 1)e − ( x12 + x22 ) 1 1 1 Hf = ⎜⎜ 2 2 2 ⎜ 2 x (−1 + 2 x 2 )e − ( x1 + x2 ) 1 2 ⎝ ∂f ( x) = 0 ∂

2

− 2 x1 x2 (2 + x1 )e − ( x1 + x2 ) ⎞⎟ 2 2 ⎟ 4 x1 x2 (1 + x12 )e − ( x1 + x 2 ) ⎟⎠ 2

2


2 2 ∂f ( x2 ) = −2 x12 x2 e −( x1 + x2 ) ∂

2 2 ∂f ( x1 ) = (2 x1 + x12 )e −( x1 + x2 ) ∂

0 = −2 x12 x2 e − ( x1 + x 2 ) 2 2

0 = (2 x1 + x12 )e − ( x1 + x2 ) 2

2

2

Titik kritis sulit untuk dicari. Q A = x • Hf (x).(x)

⎛ 2(− x 3 − x 2 + x + 1)e − ( x12 + x 22 ) ⎜ 1 1 1 = ( x1 , x2 ) • ⎜ 2 2 2 ⎜ 2 x (−1 + 2 x 2 )e − ( x1 + x 2 ) 1 2 ⎝

− 2 x1 x2 (2 + x1 )e − ( x1 + x2 ) ⎞⎟ ⎛ x1 ⎞ 2 2 ⎟ ⎜⎜ ⎟⎟ 4 x1 x2 (1 + x12 )e − ( x1 + x2 ) ⎟⎠ ⎝ x2 ⎠ 2

2

= (−2 x14 − 2 x13 + 2 x12 + x1 − 4 x12 x22 − 2 x13 x22 , − 2 x13 x2 + 8 x13 x23 + 4 x1 x23 )e − ( x1 + x 2 ) 2

Berdasarkan definisi 2.2.11, maka Untuk titik (-3, 0) Q A = (−2.(−3)5 − 2(−3) 4 + 2(−3)3 + (−3) 2 )e −9

= (486 − 162 − 54 − 9)e −9 = 0.03 > 0 adalah pembuat minimum relatif.

Untuk titik (2, 2)

QA = (−(2) 6 − (2)5 + (2) 4 + (2) 2 − (2) 6 − (2) 6 − (2)5 + (2)9 + (2) 6 )e − = (−64 − 32 + 16 + 4 − 64 − 64 − 32 + 512 + 64)e −8 = 0.11 > 0 adalah pembuat minimum relatif.

Pada titik (-3, 0) dan (2, 2) atau pada titik batas selang tidak terjadi nilai maksimum, sehingga pada permasalahan ini pembuat maksimum tidak dapat diketahui.

2


Berdasarkan teorema 2.1.2, maka akan dilihat titik minimum pada titik batas selang. Untuk f(-3, 0) f (x ) = (−3) e

− (( −3) 2 + 0 )

= -0.00037

Untuk f(2, 2) f (x ) = (2) e − ( 4+ 4) = 0.00067

b) Dengan Algoritma Genetika

Pada permasalahan contoh 4.3 dengan menggunakan teknik konvensional tidak diketahui pembuat nilai maksimumnya, maka dengan Algoritma Genetika diharapkan pembuat maksimum dapat diketahui sehingga nilai maksimum (relatife) dari permasalahan ini dapat dicari. Misalkan ketepatan angka untuk menyelesaikan permasalahan optimasi di atas adalah empat tempat setelah desimal. Dan iterasi yang akan dicapai adalah 100 iterasi. Jumlah populasi yang akan terjadi adalah 10, akan ditentukan berapa bit yang harus digunakan untuk variabel x1 dan x2 : m1 = 2 log[(batas bawah − batas atas)10 4 + 1]= 2 log[(2 + 3)10 4 + 1] = 15.6 ≈ 17 (2+3) × 104 = 50,001 216 < 50,001 ≤ 217


m1 = 2 log[(batas bawah − batas atas)10 4 + 1]= 2 log[(2 − 0)10 4 + 1] = 14.28 ≈ 15 (2-0) × 104 = 20,001 214 < 20,001 ≤ 215 Total bit dalam tiap kromosom (panjang kromosom) adalah (17 + 15)bit = 32 bit. Untuk rekombinasi dan mutasi akan diuji pada probabilitas rekombinasi antara 0.2 hingga 0.5, dan mutasi pada probabilitas 0.01 hingga 0.1. Sehingga, rekombinasi kromosom akan terjadi apabila bilangan acak rekombinasi [0, 1] lebih kecil atau sama dengan probabilitas rekombinasinya. Begitu pula dengan mutasi, apabila bilangan acak mutasi [0, 1] lebih kecil atau sama dengan probabilitas mutasi, maka mutasi kromosom akan terjadi. Setiap percobaan dilakukan untuk 100 generasi. Dari 10 percobaan didapatkan nilai maksimum 0.3679 pada titik (-1, 0) atau (1,0).


0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

10 Banyak Percobaan

Pm

Pc = 0.2 Banyak Percobaan 5 5 4 4 2 2 4 5 3 3

6 4 2 0 0


Tabel 4.25 Tabel nilai maksimum fungsi f (x ) = x1 e − ( x + x ) dengan probabilitas rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1. 2 1

8

2 2

Gambar 4.28 Grafik nilai maksimum fungsi f (x ) = x1 e − ( x + x ) dengan probabilitas rekombinasi 0.2 dan probabilitas mutasi 0.01 hingga 0.1. 2 1

2 2

Dari tabel 4.25 dan gambar 4.28 terlihat bahwa percobaan terbanyak untuk mendapatkan solusi terbaik terjadi pada probabilitas mutasi 0.01, 0.02, dan 0.08. Pc = 0.25 Banyak Pm Percobaan 0.01 4 0.02 5 0.03 3 0.04 4 0.05 4 0.06 4 0.07 3 0.08 3 0.09 4 0.1 4

Banyak Percobaan

10

6 4 2 0 0



8

2 2


2 2



Pc = 0.3 Banyak Pm Percobaan 0.01 6 0.02 4 0.03 3 0.04 5 0.05 5 0.06 3 0.07 4 0.08 5 0.09 5 0.1 4

Banyak Percobaan

10 8 6 4 2 0 0



2 2


2 2



2 2

10 Banyak Percobaan


8 6 4 2 0 0



2 2




2 2

10 Banyak Percobaan


8 6 4 2 0 0



2 2



2 2

10 Banyak Percobaan


8 6 4 2 0 0



2 2




2 2

10 Banyak Percobaan


8 6 4 2 0 0



2 2


Akan dilihat berdasarkan probabilitas mutasi:

Tabel 4.32 Tabel nilai maksimum fungsi f (x ) = x1 e − ( x + x ) dengan probabilitas mutasi 0.01 dan probabilitas rekombinasi 0.2 hingga 0.5. 2 1

2 2

10 Banyak Percobaan

Pm = 0.01 Banyak Pc Percobaan 0.2 5 0.25 4 0.3 6 0.35 4 0.4 6 0.45 4 0.5 4

8 6 4 2 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5


Gambar 4.35 Grafik nilai maksimum fungsi f (x ) = x1 e − ( x + x ) dengan probabilitas mutasi 0.01 dan probabilitas rekombinasi 0.2 hingga 0.5. 2 1

2 2

Dari tabel 4.32 dan gambar 4.35 terlihat bahwa percobaan terbanyak untuk mendapatkan solusi terbaik terjadi pada probabilitas rekombinasi 0.3 atau 0.4.



2 2

10 Banyak Percobaan


8 6 4 2 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5

Probabilitas Rek om binas i


2 2

Dari tabel 4.33 dan gambar 4.36 terlihat bahwa percobaan terbanyak untuk mendapatkan solusi terbaik terjadi pada probabilitas rekombinasi 0.5.


2 2

10 Banyak Percobaan


8 6 4 2 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5

Probabilitas Re kom binas i


2 2




2 2

10 Banyak Percobaan


8 6 4 2 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5



2 2



2 2

10 Banyak Percobaan


8 6 4 2 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5



2 2




2 2

10 Banyak Percobaan


8 6 4 2 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5



2 2

Dari tabel 4.37 dan gambar 4.40 terlihat bahwa percobaan terbanyak untuk mendapatkan solusi terbaik terjadi pada probabilitas rekombinasi 0.25, 0.4, dan 0.45.


2 2

10 Banyak Percobaan


8 6 4 2 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5

Probabilitas Rek om binas i


2 2




2 2

10 Banyak Percobaan


8 6 4 2 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5



2 2



2 2

10 Banyak Percobaan


8 6 4 2 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5



2 2



Pm = 0.1 Banyak Pc Percobaan 0.2 3 0.25 4 0.3 4 0.35 5 0.4 2 0.45 6 0.5 5 Tabel 4.41 Tabel nilai maksimum fungsi f (x ) = x1 e − ( x + x ) dengan probabilitas mutasi 0.1 dan probabilitas rekombinasi 0.2 hingga 0.5. 2 1

2 2

Banyak Percobaan

10 8 6 4 2 0 0.2

0.25

0.3

0.35

0.4

0.45

0.5

Probabilitas Re k om binas i


2 2

Dari tabel 4.41 dan gambar 4.44 terlihat bahwa percobaan terbanyak untuk mendapatkan solusi terbaik terjadi pada probabilitas rekombinasi 0.45. Dari grafik-grafik di atas, terlihat bahwa nilai optimum akan lebih banyak tercipai jika menggunakan probabilitas rekombinasi 0.5 dengan probabilitas mutasi 0.08.


BAB V PENUTUP

A. Kesimpulan Berdasarkan penelitian pada skripsi ini, hasil yang optimum terjadi karena ada beberapa kromosom yang terkena mutasi atau rekombinasi serta Algoritma Genetika merupakan salah satu teknik pencarian optimasi yang baik. Karena hasil yang didapat dengan menggunakan Algoritma Genetika mendekati nilai yang didapat dengan menggunakan teknik konvensional (berkisar antara 0.5% hingga 5%) dan juga ketika dengan teknik konvensional sulit untuk dicari titik kritisnya sehingga nilai optimumnya tidak didapatkan, dengan Algoritma Genetika nilai optimum tetap tercapai namum nilai optimum tersebut belum tentu nilai optimum mutlak. Berdasarkan hasil Algoritma Genetika dalam penyelesaian contoh-contoh pada bab IV, nilai optimum mungkin akan lebih cepat tercapai apabila probabilitas rekombinasi untuk memilih apakah terjadi rekombinasi atau tidak sebesar 0.5, dan probabilitas mutasi untuk memilih apakah terjadi mutasi atau tidak sebesar 0.08. Namun probabilitas tersebut belum tentu merupakan yang paling baik, karena Algoritma Genetika merupakan sistem yang dalam prosesnya selalu acak, sehingga hasil yang didapat belum tentu sama untuk setiap percobaan. Karena Algoritma Genetika dapat diprogramkan dengan komputer, maka dalam penyelesaiannya tentu saja lebih cepat dari pada teknik konvensional.

112


Dan bila permasalahan optimasi yang terjadi melibatkan banyak variabel (lebih dari dua variabel), jelas terlihat bahwa dengan teknik konvensional permasalahan tersebut sulit diselesaikan. Oleh sebab itu, Algoritma Genetika merupakan salah satu teknik yang baik untuk menyelesaikannya.

B. Saran Penyelesaian optimasi yang dikaji pada skripsi ini lebih kepada permasalahan optimasi untuk R2, sehingga penulis menganjurkan untuk mengkaji lebih dalam untuk permalasalahan optimasi di Rn. Algoritma genetika yang digunakan dalam skripsi ini untuk rekombinasi dan mutasi menggunakan metode satu titik, sehingga penulis menganjurkan untuk mencoba metode rekombinasi atau mutasi lain yang mungkin akan menghasilkan nilai optimum yang lebih baik.


DAFTAR PUSTAKA

Gen,Mitsuo & Cheng,Runwei. (1997). Genetic Algorithms And Engingering Design. New York: John Wiley & Sons.Inc.

Griffiths, David F. (1996). An Introduction to MATLAB (version 2.2). Sweden: Department of Mathematics, The University Dundee DD1 4HN.

Haeussler, Ernest F. & Paul, Richard S. (1996). Introduction Mathematical Analysis For Business, Economics, and the life and social sciences. New Jersey: Prentice Hall International Inc.

Kusumadewi,Sri. (2003). Artificial Intelligence (Teknik dan Aplikasinya). Yogyakarta: Graha Ilmu. Nissen, Volker & Biethan, J&o&rg . (1995). Evolutionary Algorithms in Management Applications. Berlin: Springer – Verlag.

Peressini, Anthony L., Sulivan, Francis E., Uhl, J. J.(1998). The Mathematics of Nonlinear Programming. New York: Springer – Verlag.

Purcel, Edwin J. & Varberg, Dale. (…). Kalkulus dan Geometri Analitis (Edisi Kelima). Jakarta: Erlangga.

Setya Budi, Wono. (2001). Kalkulus Peubah Banyak dan Penggunaannya. Bandung: ITB.

Sriwindono, Haris. (2006). Pengantar Algoritma Genetika. Yogyakarta: FMIPA – Ilmu Komputer, USD.

114


Suyanto. (2005). Algoritma Genetika dalam MATLAB. Yogyakarta: Andi Offset.

Taha, Hamdy A. (1976). Operation Research an Introduction (second edition). New York: Macmillan Publishing Co., Inc.


LAMPIRAN Flowchart Algoritma Genetika Untuk Menyelesaikan Optimasi Fungsi Dua Variabel

mulai

Input data

inspop

Populasi Anak

i=1

Hitung fitnes anak

Hitung fitness fitnes anak > max fitnes awal atau fitnes anak < max fitnes awal ? a c ≤ Pc ?

Ya

crossover Ya

Tidak

a m ≤ Pm ?

Ya

Jika max, populasi awal yang bernilai min diganti dengan kromosom anak. Dan sebaliknya untuk min.

mutasi

Tidak Tidak Populasi baru = populasi awal

Tidak

i=i+1

i = generasi ?

Ya

Selesai

116


Listing Program MenuAG2var.m

function MenuAG2var

clear; pil4=0; clc;

fprintf('===============================================\n') fptintf('Program

Untuk

Mencari

Nilai

Optimum

Fungsi

Dua

Variabel Dengan Algoritma Genetika\n') fprintf('1. Crossover menggunakan metode penyilangan satu titik, dengan probabilitas crossover untuk mencari orang tua adalah 0.25\n') fprintf('2.

Mutasi

titik,

menggunakan

dengan

metode

probabilitas

penyilangan

mutasi

untuk

satu

mencari

orang tua adalah 0.01\n') fprintf('3. Seleksi yang digunakan untuk memilih kromosom anak untuk dimasukkan ke populasi baru menggunakan mencari fitness yang terbaik\n') fprintf('===============================================\n')

while pil4~=3 fprintf('\nPilih Jenis Permasalahan\n') fprintf('1. Permasalahan Maksimum\n') fprintf('2. Permasalahan Minimum\n') fprintf('3. Keluar\n')

pil4=input('Masukkan menu yang anda inginkan : '); fprintf('\n')

switch pil4 case 1


fprintf('Input Data\n') jml_pop=input('Masukkan jumlah populasi = '); tel=input('Masukkan ketelitian Pc=input('Masukkan crossover

probabilitas

terjadinya

probabilitas

terjadinya

= ');

Pm=input('Masukkan mutasi

= ');

= ');

fprintf('Range pertama :\n') ba1=input('Masukkan bilangan awal

= ');

bb1=input('Masukkan bilangan akhir

= ');

fprintf('Range kedua

:\n')

ba2=input('Masukkan bilangan awal

= ');


= ');

Algoritma_genetika_maks(jml_pop,tel,Pc,Pm,ba1,b b1,ba2,bb2);

case 2 fprintf('Input Data\n') jml_pop=input('Masukkan jumlah populasi = '); tel=input('Masukkan ketelitian Pc=input('Masukkan crossover

probabilitas

terjadinya

probabilitas

terjadinya

= ');

Pm=input('Masukkan mutasi

= ');

= ');

fprintf('Range pertama :\n') ba1=input('Masukkan bilangan awal

= ');


= ');

fprintf('Range kedua

:\n')

ba2=input('Masukkan bilangan awal

= ');


= ');

Algoritma_genetika_min(jml_pop,tel,Pc,Pm,ba1,bb 1,ba2,bb2);


case 3

end end

Listing Program Untuk Inisialisasi Populasi

InisialisasiPopulasi.m %=========================================================== %Membangkitkan

sejumlah

UkPop

kromosom,

masing-masing

%kromosom berisi bilangan biner (0 dan 1) sejumlah JumGen % %Output : %

UkPop : ukuran populasi atau jumlah kromosom dalam

%populasi %

JumGen

:

jumlah gen dalam kromosom

% %Input : %

Populasi : kumpulan kromosom, matriks berukuran UkPop x

%JumGen % % %===========================================================

function Populasi = InisialisasiPopulasi(UkPop,JumGen);

Populasi = fix(2*rand(UkPop,JumGen));


Inis1.m %=========================================================== %Inisialisasi

populasi

pada

variabel

pertama

berupa

yang

akan

%kromosom, kromosom tersebut berisi bilangan %biner 0 atau 1 dan berisi bilangan desimal. % %Masukan: % jml_pop

=

Banyaknya

populasi

%diinisialisasikan %

ba

= Batas bawah

%

bb

= Batas atas

%

tel

= Ketelitian

% %Keluaran: %

x1des

= Kromosom variabel1 yang bernilai desimal

%

x1bin

= Kromosom variabel1 yang bernilai biner

%

m1

= Panjang kromosom

% %===========================================================

function [x1des,x1bin,m1]=Inis1(jml_pop,ba,bb,tel)

m=log2(((bb-ba)*10^tel)+1); m1=ceil(m);

banyak=1;

while banyak<=jml_pop Populasi=InisialisasiPopulasi(1,m1); a=1; hasil=0; for y=m1:-1:1 if(Populasi(1,a)==1) hasil=hasil+2^y;


end a=a+1; end akhir=ba+(hasil*(bb-ba)/((2^tel)-1)); if akhir>=ba & akhir<=bb generate(banyak,1)=akhir; banyak=banyak+1; end end

x1des=[generate]; [x1bin_baru]=dec2bin_pop(ba,bb,x1des,m1); x1bin=[x1bin_baru];

Inis2.m %========================================================== %Inisialisasi populasi pada variabel kedua berupa kromosom, %kromosom tersebut berisi bilangan %biner 0 atau 1 dan berisi bilangan desimal. % %Masukan: % jml_pop

=

Banyaknya

populasi

yang

akan

%diinisialisasikan %

ba

= Batas bawah

%

bb

= Batas atas

%

tel

= Ketelitian

% %Keluaran: %

x2des

= Kromosom variabel1 yang bernilai desimal

%

x2bin

= Kromosom variabel1 yang bernilai biner

%

m2

= Panjang kromosom

% %===========================================================


function [x2des,x2bin,m2]=Inis2(jml_pop,ba,bb,tel)

m=log2(((bb-ba)*10^tel)+1); m2=ceil(m);

banyak=1;

while banyak<=jml_pop Populasi=InisialisasiPopulasi(1,m2); a=1; hasil=0; for y=m2:-1:1 if(Populasi(1,a)==1) hasil=hasil+2^y; end a=a+1; end akhir=ba+(hasil*(bb-ba)/((2^tel)-1)); if akhir>=ba & akhir<=bb generate(banyak,1)=akhir; banyak=banyak+1; end end

x2des=[generate]; [x2bin_baru]=dec2bin_pop2(ba,bb,x2des,m2); x2bin=x2bin_baru;

Listing Program Mengitung Fitness

Hitungfitness.m ============================================================ %Menghitung nilai fitness kromsom variabel 1 dan variabel 2 %


%Masukan: %

hasil

: Nilai desimal dari kromosom variabel1 dan

%variabel2 % %Keluaran: %

hit

: Nilai fungsi dari tiap-tiap kromosom

%=========================================================

function hit=hitungfitness(hasil)

%hit=hasil(:,1).^2+2*hasil(:,1).*hasil(:,2)+hasil(:,2).^2; %hit=hasil(:,1).^3+hasil(:,2).^3-3.*hasil(:,1)12.*hasil(:,2)+20; %hit=hasil(:,1).^4+hasil(:,2).^4-hasil(:,1).^2hasil(:,2).^2+1; %hit=3.*(hasil(:,1).^2).*hasil(:,2)-9.*(hasil(:,2).^3)(hasil(:,1).^2)+1; hit=3.*((hasil(:,1)).^2).*hasil(:,2)-(9.*(hasil(:,2)).^3)((hasil(:,1)).^2)+1;

Listing Program Mengurutkan Kromosom Dari Fitness Maksimum ke Fitness Minimum

Urut_krom.m %=========================================================== %Urutkan kromosom berdasarkan nilai fungsi fitnesnya % %Masukan: %

uk_pop

= banyaknya populasi

%

kromosom_populasi_awal

= populasi kromosom sebelumnya

%

fungsi_fitnes

kromosom %

= nilai fitnes masing-masing


%Keluaran: %

urut_kromosom

=

kromosom

yang

telah

diurutkan

%berdasarkan nilai fitnesnya dari yang terbesar hingga yang %terkecil %===========================================================

function [urut_kromosom]=urut_krom(uk_pop,fungsi_fitnes, kromosom_ populasi_awal)

for i=1:uk_pop-1 for j=i+1:uk_pop if fungsi_fitnes(i,:) < fungsi_fitnes(j,:) temp_fitnes1=fungsi_fitnes(i,:); temp_krom=kromosom_populasi_awal(i,:); fungsi_fitnes(i,:)=fungsi_fitnes(j,:);

kromosom_populasi_awal(i,:)=kromosom_populasi_awal( j,:); fungsi_fitnes(j,:)=temp_fitnes1; kromosom_populasi_awal(j,:)=temp_krom; end end end urut_kromosom=[kromosom_populasi_awal];

Listing Program Mengubah Kromosom Dari Bentuk Biner ke Bentuk Desimal

populasi_baru_desimal.m %========================================================== %Mengubah variabel biner (0 dan 1) ke dalam bentuk desimal. % %Input: %

a1

= Batas bawah variabel1


%

b1

= Batas atas variabel1

%

n1

= Panjang kromosom variabel1

%

p1

= Populasi kromosom variabel1

%

a2


%

b2


%

n2


%

p2

= Populasi kromosom variabel2

% %Output: %

x1des_baru

: Kromosom variabel1 dalam bentuk desimal

%sebanyak jumlah % %

populasi x2des_baru

: Kromosom variabel2 dalam bentuk desimal

%sebanyak jumlah %

populasi

%===========================================================

Function[x1des_baru,x2des_baru]=populasi_baru_desimal(a1,b1, n1,p1,a2,b2,n2,p2)

[x1des_baru]=bin2dec_pop(a1,b1,n1,p1); [x2des_baru]=bin2dec_pop2(a2,b2,n2,p2);

bin2dec_pop.m %========================================================== %Mengubah variabel biner (0 dan 1) ke dalam bentuk desimal. % %Input: %

a

= Batas bawah

%

b

= Batas atas

%

n


%

p

= Populasi

% %Output:


%

x1des_baru

= Kromosom variabel1 dalam bentuk desimal

%sebanyak jumlah populasi % %Contoh: %

bin2dec_pop(2,8,10,'0010111010')

% %

x1des_baru=3.0909

%===========================================================

function [x1des_baru]=bin2dec_pop(a,b,n,p)

x=bin2dec(p); k=b-a; l=(2^n)-1; decx1=a+x*(k/l);

x1des_baru=[decx1];

bin2dec_pop2.m %========================================================== %Mengubah variabel biner (0 dan 1) ke dalam bentuk desimal. % %Input: %

a

= Batas bawah

%

b

= Batas atas

%

n


%

p

= Populasi

% %Output: %

x1des_baru

= Kromosom variabel1 dalam bentuk desimal

%sebanyak jumlah populasi % %Contoh: %

bin2dec_pop(2,8,10,'0010111010')


% %

x1des_baru=3.0909

%===========================================================

function [x1des_baru]=bin2dec_pop2(a,b,n,p)

x=bin2dec(p); k=b-a; l=(2^n)-1; decx1=a+x*(k/l);

x1des_baru=[decx1];

Listing Program Crossover

Seleksi_crossover.m %=========================================================== %Meng-crossover kromosom parent yang telah dipilih secara %acak untuk menghasilkan kromosom baru, yaitu kromsom anak. % %Input: %

L

= Panjang kromosom

%

jml

= Jumlah populasi

%

populasi

= Populasi kromosom sebelumnya

% %Output: %

populasi_baru_Cbiner

= Populasi baru kromosom setelah

%di crossover/kromosom anak. %===========================================================

Function [offspring]=seleksi_crossover(L,jml,populasi)

brs=[]; k=0;


pos2=randint(1,1,[1,L]);

if pos2==0 pos2=1; end

acak=rand(jml,1); t=acak<0.25; ind=find(t==1); brs=ind;

if length(brs)<2 acak=rand(jml,1); t=acak<0.25;

while t==0 acak=rand(jml,1); t=acak<0.25; end

ind=find(t==1); brs=ind;

if length(brs)==1 brs2=brs; brs(2)=brs2; end

end

parent=[populasi(brs(1),:); populasi(brs(2),:)] partisi1=parent(:,1:pos2); partisi2=parent(:,pos2+1:L);


offspring1=[partisi1(1,:),partisi2(2,:)]; offspring2=[partisi1(2,:),partisi2(1,:)];

offspring=[offspring1;offspring2]

Listing Program Mutasi

mutasi.m %=========================================================== %Mengantikan gen dengan cara mengubah nilai '0' menjadi '1' %dan sebaliknya. % %Masukan: %

ba1


%

bb1


%

ba2


%

bb2


%

pop_des= Populasi kromosom dalam bentuk desimal

%

w

= Banyaknya populasi

%

y

= Panjang kromosom

%

q1


%

pop

= Populasi berupa kromosom yang bernilai biner 0

%atau 1 % %Keluaran: %

x1bin_mut

= Kromosom variabel1 berbentuk biner

%

x2bin_mut

= Kromosom variabel2 berbentuk biner

% %===========================================================

function [x1binn, x2binn,x1dess,x2dess]=mutasi(ba1,bb1,ba2, bb2,w,y,q1,q2,pop,popdes)

tot_bit=w*y;


bnyk_mut=tot_bit*0.01; h=ceil(bnyk_mut);

for i=1:h acak(i)=rand; pos_bit(i)=acak(i)*tot_bit; pos_bit1(i)=ceil(pos_bit(i)); no_krom(i)=ceil(pos_bit1(i)/y); %t=find(no_krom(i+1)==no_krom(i)) no_krom1(i)=floor(pos_bit1(i)/y); no_bit(i)=pos_bit1(i)-(no_krom1(i)*y);

if no_bit(i)==0 no_bit(i)=1; end

end

pos_bitt=pos_bit1'; pos_bit1=pos_bitt; no_kromm=no_krom'; no_krom=no_kromm; no_bitt=no_bit'; no_bit=no_bitt; acakk=acak'; acak=acakk; pop_mutasi=[pos_bit1 no_krom no_bit acak]; parent_mutasi=pop(no_krom,:) off_mut=pop(no_krom,:);

for i=1:h

if parent_mutasi(i,no_bit(i))=='1' off_mut(i,no_bit(i))='0';


end

if parent_mutasi(i,no_bit(i))=='0' off_mut(i,no_bit(i))='1'; end

end

offspring_mut=off_mut x1binn=[offspring_mut(:,1:q1)]; x2binn=[offspring_mut(:,q1+1:y)]; [x1des_baru,x2des_baru]=populasi_baru_desimal(ba1,bb1,q1,x1b inn,ba2,bb2,q2,x2binn); x1dess=[x1des_baru]; x2dess=[x2des_baru];

Listing Program Mencari Nilai Optimum (Maksimum dan Minimum)

Algoritma_genetika_maks.m %=========================================================== %Mencari nilai maksimum untuk setiap generasi % %Input : %

jml_pop = Banyaknya populasi

%

tel

%

Pc

= Ketelitian = Probabilitas crossover untuk menentukan

%terjadi atau tidak crossover %

Pm

= Probabilitas mutasi untuk menentukan terjadi

%atau tidak mutasi %

ba1

= batas bawah variabel1

%

bb1

= batas atas variabel1

%

ba2


%

bb2


%=========================================================


function Algoritma_genetika_maks(jml_pop,tel,Pc,Pm,ba1,bb1, ba2,bb2)

clc; fprintf('MEMAKSIMUMKAN\n\n') gener=input('Masukkan generasi yang akan terjadi

= ');

z=0;

[x1des,x1bin,m1]=Inis1(jml_pop,ba1,bb1,tel); [x2des,x2bin,m2]=Inis2(jml_pop,ba2,bb2,tel); L=m1+m2;

populasi_desimal=[x1des x2des]; populasi_biner=[x1bin x2bin]; fitness_populasi=hitungfitness(populasi_desimal);

while z~=gener fprintf('\n\nGENERASI KE-%d\n',z+1) Populasi_Desimal=populasi_desimal; Populasi_Biner=populasi_biner; [urut_kromosom]=urut_krom(jml_pop,fitness_populasi,Popu lasi_Desimal); PopulasiAwal_desimal=urut_kromosom; [urut_kromosom]=urut_krom(jml_pop,fitness_populasi,Popu lasi_Biner);

PopulasiAwal_biner=urut_kromosom; acakC=rand; acakM=rand;

if acakC<=Pc fprintf('\nTERJADI CROSSOVER\n') [offspring]=seleksi_crossovermaks(L,jml_pop,Populas iAwal_biner)


x1bin_anak=[offspring(:,1:m1)]; x2bin_anak=[offspring(:,m1+1:L)]; [x1des_baru, x2des_baru]=populasi_baru_desimal (ba1,bb1,m1,x1bin_anak,ba2,bb2,m2,x2bin_anak); populasiAnak_desimalC=[x1des_baru x2des_baru]; populasiAnak_binerC=[x1bin_anak x2bin_anak]; end if acakC>Pc populasiAnak_desimalC=[]; populasiAnak_binerC=[]; end

if acakM<=Pm fprintf('\nTERJADI MUTASI\n') [x1binn, x2binn,x1dess,x2dess]=mutasi(ba1,bb1,ba2, bb2,jml_pop,L,m1,m2,PopulasiAwal_biner,PopulasiAwal _desimal); populasiAnak_binerM=[x1binn x2binn]; populasiAnak_desimalM=[x1dess x2dess]; end

if acakM>Pm populasiAnak_desimalM=[]; populasiAnak_binerM=[]; end

populasiAnak_desimal=[populasiAnak_desimalC; populasiAnak_desimalM];

populasiAnak_biner=[populasiAnak_binerC;populasiAnak_bi nerM]; [f,k]=size(populasiAnak_desimal); if f~=0 fitness_anak=hitungfitness(populasiAnak_desimal);


maksimum_fitness_awal=max(fitness_populasi); t=find(fitness_anak>maksimum_fitness_awal); indek=t; [c,d]=size(t);

if t==find(fitness_anak>maksimum_fitness_awal) PopulasiAwal_desimal(jml_pop+1-c: jml_pop,:)=[populasiAnak_desimal(indek,:)]; PopulasiAwal_biner(jml_pop+1c:jml_pop,:)=[populasiAnak_biner(indek,:)]; end end

if f==0 fprintf('\nTIDAK TERJADI CROSSOVER DAN MUTASI\n') end

populasi_desimal=PopulasiAwal_desimal; x1des_populasi=populasi_desimal(:,1); x2des_populasi=populasi_desimal(:,2); populasi_biner=PopulasiAwal_biner; fitness_populasi=hitungfitness(populasi_desimal);

maks=max(fitness_populasi); k=find(fitness_populasi==maks); fprintf('Nilai Maksimum %5.4f, Terjadi Pada:\n',maks) Kromosom_biner=populasi_biner(k,:) fprintf('Di titik : (%5.4f, %5.4f) \n',x1des_popula si(k),x2des_populasi(k)) z=z+1;

end fprintf('\n=============================================\n') fprintf('HASIL AKHIR\n')


Populasi_Desimal_Akhir=populasi_desimal; Populasi_Biner_Akhir=populasi_biner; fprintf('\n') fprintf('Nilai Maksimum %5.4f, Terjadi Pada:\n',maks) Kromosom_biner=populasi_biner(k,:) fprintf('Di titik : (%5.4f, %5.4f) \n',x1des_populasi(k), x2des_populasi(k))

pil3=0; while pil3~=3 fprintf('\nMenu\n') fprintf('1.

Lanjutkan

Mencari

Generasi

Baru

(Kembali

Looping)\n') fprintf('2. Lanjutkan Untuk Mencari Nilai Minimum\n') fprintf('3. Kembali Ke Permasalahan\n') pil3=input('Masukkan menu yang anda inginkan : '); fprintf('\n')

switch pil3 case 1 [Populasi_Desimal_Akhir, Populasi_Biner_Akhir]= Looping_maks(Populasi_Desimal_Akhir,Populasi_Bi ner_Akhir,L,ba1,bb1,m1,ba2,bb2,m2,jml_pop,Pc,Pm );

case 2 [Populasi_Desimal_Akhir, Populasi_Biner_Akhir]= Looping_minim(Populasi_Desimal_Akhir,Populasi_B iner_Akhir,L,ba1,bb1,m1,ba2,bb2,m2,jml_pop,Pc,P m);

case 3 MenuAG2var;


end end

Algoritma_genetika_min.m %=========================================================== %Mencari nilai minimum untuk setiap generasi % %Input : %

jml_pop = Banyaknya populasi

%

tel

%

Pc

= Ketelitian = Probabilitas crossover untuk menentukan


Pm

= Probabilitas mutasi untuk menentukan terjadi

%atau tidak mutasi %

ba1


%

bb1


%

ba2


%

bb2


%=========================================================

function Algoritma_genetika_min(jml_pop,tel,Pc,Pm,ba1,bb1, ba2,bb2) clc; fprintf('MEMINIMUMKAN\n\n') gener=input('Masukkan generasi yang akan terjadi

z=0;

[x1des,x1bin,m1]=Inis1(jml_pop,ba1,bb1,tel); [x2des,x2bin,m2]=Inis2(jml_pop,ba2,bb2,tel); L=m1+m2;

populasi_desimal=[x1des x2des]; populasi_biner=[x1bin x2bin];

= ');


fitness_populasi=hitungfitness(populasi_desimal);

while z~=gener fprintf('\n\nGENERASI KE-%d\n',z+1) Populasi_Desimal=populasi_desimal; Populasi_Biner=populasi_biner;

[urut_kromosom]=urut_krom(jml_pop,fitness_populasi,Popu lasi_Desimal); PopulasiAwal_desimal=urut_kromosom;

[urut_kromosom]=urut_krom(jml_pop,fitness_populasi,Popu lasi_Biner); PopulasiAwal_biner=urut_kromosom; acakC=rand; acakM=rand;

if acakC>=Pc fprintf('\nTERJADI CROSSOVER\n') [offspring]=seleksi_crossover(L,jml_pop,Populasi Awal_biner) x1bin_anak=[offspring(:,1:m1)]; x2bin_anak=[offspring(:,m1+1:L)]; [x1des_baru, x2des_baru]=populasi_baru_desimal( ba1,bb1,m1,x1bin_anak,ba2,bb2,m2,x2bin_anak); populasiAnak_desimalC=[x1des_baru x2des_baru]; populasiAnak_binerC=[x1bin_anak x2bin_anak]; end

if acakC

if acakM==Pm fprintf('\nTERJADI MUTASI\n') [x1binn, x2binn,x1dess,x2dess]=mutasi(ba1,bb1,ba2, bb2,jml_pop,L,m1,m2,PopulasiAwal_biner,PopulasiAwal _desimal); populasiAnak_binerM=[x1binn x2binn]; populasiAnak_desimalM=[x1dess x2dess]; end

if acakM~=Pm populasiAnak_desimalM=[]; populasiAnak_binerM=[]; end

populasiAnak_desimal=[populasiAnak_desimalC; populasi Anak_desimalM]; populasiAnak_biner=[populasiAnak_binerC;populasiAnak_ binerM];

[f,k]=size(populasiAnak_desimal);

if f~=0 fitness_anak=hitungfitness(populasiAnak_desimal); minimum_fitness_awal=min(fitness_populasi); t=find(fitness_anak<=minimum_fitness_awal); indek=t; [c,d]=size(t);

if t==find(fitness_anak<=minimum_fitness_awal) PopulasiAwal_desimal(jml_pop+1-c:jml_pop,:)= [populasiAnak_desimal(indek,:)]; PopulasiAwal_biner(jml_pop+1-c:jml_pop,:)= [populasiAnak_biner(indek,:)]; End


end


populasi_desimal=PopulasiAwal_desimal; x1des_populasi=populasi_desimal(:,1); x2des_populasi=populasi_desimal(:,2); populasi_biner=PopulasiAwal_biner; fitness_populasi=hitungfitness(populasi_desimal); minim=min(fitness_populasi); k=find(fitness_populasi==minim); fprintf('Nilai Minimum %5.4f, Terjadi Pada:\n',minim) Kromosom_biner=populasi_biner(k,:) fprintf('Di titik : (%5.4f, %5.4f) \n',x1des_populasi (k),x2des_populasi(k)) z=z+1; end fprintf('\n=============================================\n') fprintf('HASIL AKHIR\n') Populasi_Desimal_Akhir=populasi_desimal; Populasi_Biner_Akhir=populasi_biner; fprintf('\n') fprintf('Nilai Minimum %5.4f, Terjadi Pada:\n',minim) Kromosom_biner=populasi_biner(k,:) fprintf('Di titik : (%5.4f, %5.4f) \n',x1des_populasi(k), x2des_populasi(k))

pil2=0; while pil2~=3 fprintf('\nMenu\n')


fprintf('1.

Lanjutkan

Mencari

Generasi

Baru

(Kembali

Looping)\n') fprintf('2. Lanjutkan Untuk Mencari Nilai Maksimum\n') fprintf('3. Kembali Ke Menu Permasalahan\n')

pil2=input('Masukkan menu yang anda inginkan : '); fprintf('\n')

switch pil2 case 1 [Populasi_Desimal_Akhir, Populasi_Biner_Akhir]= Looping_minim(Populasi_Desimal_Akhir,Populasi_B iner_Akhir,L,ba1,bb1,m1,ba2,bb2,m2,jml_pop,Pc,P m);

case 2 [Populasi_Desimal_Akhir, Populasi_Biner_Akhir]= Looping_maks(Populasi_Desimal_Akhir,Populasi_Bi ner_Akhir,L,ba1,bb1,m1,ba2,bb2,m2,jml_pop,Pc,Pm );

case 3 MenuAG2var; end end

Listing Program Looping

Looping_maks.m %=========================================================== %Kembali mencari nilai minimum untuk setiap generasi % %Input :


%

Populasi_DA = populasi akhir tiap generasi dalam bentuk

%desimal %

Populasi_BA = populasi akhir tiap generasi dalam bentuk

%biner %

L

= panjang kromosom

%

ba1


%

bb1


%

m1

= panjang kromosom variabel1

%

ba2


%

bb2


%

m2

= panjang kromosom variabel

%

jml_pop


%

Pc

=

probabilitas

crossover

untuk

menentukan


Pm

=

probabilitas

mutasi

untuk

menentukan

%terjadi atau tidak mutasi % %Output: %

Populasi_Desimal_Akhir = populasi akhir setelah looping

%dalam bentuk desimal %

Populasi_Biner_Akhir

= populasi akhir setelah looping

%dalam bentuk biner %=========================================================

function [Populasi_Desimal_Akhir, Populasi_Biner_Akhir]= Looping_maks(Populasi_DA,Populasi_BA,L,ba1,bb1,m1,ba2,bb2,m2 ,jml_pop,Pc,Pm)

fprintf('MEMAKSIMUMKAN\n\n') z=0; x1des=[Populasi_DA(:,1)]; x2des=[Populasi_DA(:,2)]; x1bin=[Populasi_BA(:,1:m1)]; x2bin=[Populasi_BA(:,m1+1:L)];


populasi_desimal=[x1des x2des] populasi_biner=[x1bin x2bin] fitness_populasi=hitungfitness(populasi_desimal) gener=input('Masukkan generasi yang akan terjadi

= ');

while z~=gener fprintf('\n\nGENERASI KE-%d\n',z+1) Populasi_Desimal=populasi_desimal; Populasi_Biner=populasi_biner; lih=size(Populasi_Biner,2); popul2=Populasi_Biner(:,1:lih); selis=L-lih;

if L
if L>lih [x1bin,x2bin]=cek_panjang(L,Populasi_Biner,m1,m2,lih) Populasi_Biner=[x1bin x2bin]; end

[urut_kromosom]=urut_krom(jml_pop,fitness_populasi,Popu lasi_Desimal); PopulasiAwal_desimal=urut_kromosom [urut_kromosom]=urut_krom(jml_pop,fitness_populasi,Popu lasi_Biner); PopulasiAwal_biner=urut_kromosom acakC=rand; acakM=rand

if acakC>=Pc fprintf('\nTERJADI CROSSOVER\n')


[offspring]=seleksi_crossover(L,jml_pop,PopulasiAwa l_biner) x1bin_anak=[offspring(:,1:m1)]; x2bin_anak=[offspring(:,m1+1:L)]; [x1des_baru, x2des_baru]=populasi_baru_desimal (ba1,bb1,m1,x1bin_anak,ba2,bb2,m2,x2bin_anak); populasiAnak_desimalC=[x1des_baru x2des_baru] populasiAnak_binerC=[x1bin_anak x2bin_anak] end

if acakC
if acakM==Pm fprintf('\nTERJADI MUTASI\n') [x1binn, x2binn,x1dess,x2dess]=mutasi(ba1,bb1,ba2, bb2,jml_pop,L,m1,m2,PopulasiAwal_biner,PopulasiAwal _desimal); populasiAnak_binerM=[x1binn x2binn] populasiAnak_desimalM=[x1dess x2dess] end


populasiAnak_desimal=[populasiAnak_desimalC; populasi Anak_desimalM] populasiAnak_biner=[populasiAnak_binerC;populasiAnak_bi nerM]


[f,k]=size(populasiAnak_desimal);

if f~=0 fitness_anak=hitungfitness(populasiAnak_desimal) maksimum_fitness_awal=max(fitness_populasi); t=find(fitness_anak>maksimum_fitness_awal); indek=t; [c,d]=size(t);

if t==find(fitness_anak>maksimum_fitness_awal) PopulasiAwal_desimal(jml_pop+1-c:jml_pop,:)= [populasiAnak_desimal(indek,:)]; PopulasiAwal_biner(jml_pop+1-c:jml_pop,:)= [populasiAnak_biner(indek,:)]; end end


populasi_desimal=PopulasiAwal_desimal x1des_populasi=populasi_desimal(:,1); x2des_populasi=populasi_desimal(:,2); populasi_biner=PopulasiAwal_biner fitness_populasi=hitungfitness(populasi_desimal) maks=max(fitness_populasi); k=find(fitness_populasi==maks); z=z+1; end fprintf('\n=============================================\n') fprintf('HASIL AKHIR\n') Populasi_Desimal_Akhir=populasi_desimal Populasi_Biner_Akhir=populasi_biner


fprintf('\n') fprintf('Nilai Maksimum %5.4f, Terjadi Pada:\n',maks) Kromosom=k Kromosom_biner=populasi_biner(k,:) fprintf('Di titik : (%5.4f, %5.4f) \n',x1des_populasi(k), x2des_populasi(k)) fprintf('\n=============================================\n')

Looping_minim.m %=========================================================== %Kembali mencari nilai minimum untuk setiap generasi % %Input : %

Populasi_DA = populasi akhir tiap generasi dalam bentuk

%desimal %

Populasi_BA = populasi akhir tiap generasi dalam bentuk

%biner %

L

= panjang kromosom

%

ba1


%

bb1


%

m1

= panjang kromosom variabel1

%

ba2


%

bb2


%

m2

= panjang kromosom variabel

%

jml_pop


%

Pc

=

probabilitas

crossover

untuk

menentukan


Pm

=

probabilitas

mutasi

untuk

menentukan

%terjadi atau tidak mutasi % %Output: %

Populasi_Desimal_Akhir = populasi akhir setelah looping

%dalam bentuk desimal


%

Populasi_Biner_Akhir

= populasi akhir setelah looping

%dalam bentuk biner %=========================================================

function [Populasi_Desimal_Akhir, Populasi_Biner_Akhir]= Looping_minim(Populasi_DA,Populasi_BA,L,ba1,bb1,m1,ba2,bb2,m 2,jml_pop,Pc,Pm)

fprintf('MEMINIMUMKAN\n\n') z=0; x1des=[Populasi_DA(:,1)]; x2des=[Populasi_DA(:,2)]; x1bin=[Populasi_BA(:,1:m1)]; x2bin=[Populasi_BA(:,m1+1:L)]; populasi_desimal=[x1des x2des] populasi_biner=[x1bin x2bin] fitness_populasi=hitungfitness(populasi_desimal) gener=input('Masukkan generasi yang akan terjadi

= ');

while z~=gener fprintf('\n\nGENERASI KE-%d\n',z+1) Populasi_Desimal=populasi_desimal; Populasi_Biner=populasi_biner;

[urut_kromosom]=urut_krom(jml_pop,fitness_populasi,Popu lasi_Desimal); PopulasiAwal_desimal=urut_kromosom

[urut_kromosom]=urut_krom(jml_pop,fitness_populasi,Popu lasi_Biner); PopulasiAwal_biner=urut_kromosom acakC=rand; acakM=rand;


if acakC>=Pc fprintf('\nTERJADI CROSSOVER\n') [offspring]=seleksi_crossover(L,jml_pop,PopulasiAwa l_biner) x1bin_anak=[offspring(:,1:m1)]; x2bin_anak=[offspring(:,m1+1:L)]; [x1des_baru, x2des_baru]=populasi_baru_desimal(ba1, bb1,m1,x1bin_anak,ba2,bb2,m2,x2bin_anak); populasiAnak_desimalC=[x1des_baru x2des_baru]; populasiAnak_binerC=[x1bin_anak x2bin_anak]; end

if acakC
if acakM==Pm fprintf('\nTERJADI MUTASI\n') [x1binn, x2binn,x1dess,x2dess]=mutasi(ba1,bb1,ba2, bb2,jml_pop,L,m1,m2,PopulasiAwal_biner,PopulasiAwal _desimal); populasiAnak_binerM=[x1binn x2binn]; populasiAnak_desimalM=[x1dess x2dess]; end


populasiAnak_desimal=[populasiAnak_desimalC; populasi Anak_desimalM]


populasiAnak_biner=[populasiAnak_binerC;populasiAnak_bi nerM] [f,k]=size(populasiAnak_desimal);

if f~=0 fitness_anak=hitungfitness(populasiAnak_desimal) minimum_fitness_awal=min(fitness_populasi); t=find(fitness_anak<=minimum_fitness_awal); indek=t; [c,d]=size(t);

if t==find(fitness_anak<=minimum_fitness_awal) PopulasiAwal_desimal(jml_pop+1-c:jml_pop,:)= [populasiAnak_desimal(indek,:)]; PopulasiAwal_biner(jml_pop+1-c:jml_pop,:)= [populasiAnak_biner(indek,:)]; End

end


populasi_desimal=PopulasiAwal_desimal x1des_populasi=populasi_desimal(:,1); x2des_populasi=populasi_desimal(:,2); populasi_biner=PopulasiAwal_biner fitness_populasi=hitungfitness(populasi_desimal) minim=min(fitness_populasi); k=find(fitness_populasi==minim); z=z+1; end


fprintf('\n============================================\n') fprintf('HASIL AKHIR\n') Populasi_Desimal_Akhir=populasi_desimal Populasi_Biner_Akhir=populasi_biner fprintf('\n') fprintf('Nilai Minimum %5.4f, Terjadi Pada:\n',minim) Kromosom_biner=populasi_biner(k,:) fprintf('Di titik : (%5.4f, %5.4f) \n',x1des_populasi(k), x2des_populasi(k)) fprintf('\n=============================================\n')

OPTIMASI FUNGSI TANPA KENDALA DENGAN ALGORITMA GENETIKA

Recommend Documents