Ag-maxfunctionina

Genetic Algorithms Melacak maksimum dari suatu fungsi. Genetic Algorithms (GA) dikelompokkan ke dalam metoda adaptive random search. Dalam optimisasi fungsi, max/min dari suatu (y=f(x)) didapatkan berdasarkan variasi dari x yang dimulai dari titik awalnya. GA mencakup sekumpulan titik. Elemen dasar dari GA adalah individu tiruan. Seperti halnya individu alamiah, individu tiruan juga terdiri dari suatu chromosome dan fitness value. Kebugaran (fitness) dari suatu individu digambarkan oleh seberapa baik individu tersebut dapat beradaptasi terhadap alam. Haltersebut menentukan individu sejenis untuk bertahan hidup dan berkembang biak. (It determines the individual's likelihood for survival and mating.). Setiap perubahan dari chromosome akan membawa perubahan pada kebugaran dari indifidu (individual fitness). Dalam permasalahan dibawah ini, (Searching a maximum of a function) suatu individu tiruan hanya terdiri dari nilai x and y=f(x)). x memegang peran penting dalam mementukan suatu chromosome sedang y menentukan fitness. Namun demikian, implementasi GA bekerja menggunakan binary coded x(xc), dan bukan dengan x itu sendiri. artifical individual ::= I = {xc,f(x)} Kumpulan dari individu yang sama dinamakan population. Population ::= P = {I1,I2,..,In} n: jumlah dari individual-individu

Coding Implementasi GA bekerja berdasarkan pada nilai x yang dikodekan (coded x value). Tujuan dari coding adalah untuk menciptakan representasi dari x yang setiap posisinya dapat di-modified, dipotong dan dipertukarka menjadi new x. Kode-x seperti chromosome dalam genetika, atau dengan kata lain informasi yang dibawa dapat dimodifikasi (modifiable carrier of information). Implementasi metoda pengkodean didasarkan pada representasi binary string dari suatu angka (string 0 atau 1). Dalam contoh dibawah ini dapat terlihat contoh dari nilai-nilai binary-coded x sbb. Untuk penyederhanaannya digunakan bilangan integer positip sepanjang 8 bit. examples of coding x xc (binary coded x)

114 01001110 132 00100001 Cara membaca binary code (dibalik): 0 1 0 0 1 1 1 0 LSB MSB

1

Algoritma keseluruhan. Suatu populasi awal (parental generation) dibangkitkan secra random (nilai x dipilih secara acak, dan kemudian nilai y dihitung). Atas dasar generasi ini GA diciptakan offspring generation menggunakan operator genetika Selection, Crossover dan Mutation. Individu tiruan generasi baru akan menjadi parental generation untuk offspring generation berikutnya. Dengan tiap generasi baru ini nilai kebugaran keseluruhan dari populasi akan meningkat. Proses pembentukan offspring generations berdasarkan pembentukan generasi baru, diulangi-ulang sampai dicapai hasil yang optimum. Sketsa berikut menggambarkan satu iterasi dalam implementasi GA untuk menciptakan 2 individu baru. Langkah-langkah tersebut diulang lagi sampai jumlah individu dalam offspring generation sama dengan parental generation.

Proses penciptaan generasi baru dihentukan bila generasi yang diharapkan sudah tercapai atau bila seluruh nilai kebugaran dari populasi generasi terakhir tidak bertambah lagi. Berikut diskripsi ringkas dari operator genetika

Seleksi Seleksi merupakan suatu proses pemilihan individu dari populasi untuk menciptakan individu baru. Individu yang tepat adalah individu dengan dengan kebugaran yang baik. Operator ini mengimplementasikan prinsip ” yang paling bugar akan bertahan” (survival of the fittest). Implementasi dari seleksi turnamen memilih sepasang individu (ayah, ibu) untuk menciptakan dua individu baru dalam bentuk offspring generation. Pasangan individu yang tepat adalah individu dengan nilai y tinggi, karena yang ingin dicapai adalah nilai maksimum fungsi. Examples: Selection (based on the test function F0 ; 0.0 < x < 10) parents x xc (binary-coded y x) P1 4 00100000 0.108 P2 8 00010000 1.22 E-08 P3 7 11100000 2.68 E-04

2

Contoh diatas menunjukkan tiga nilai-x,y. P1 dan P3 terpilih sebagai individu ayah dan ibu, karena kebugarannya lebih tinggi dari P2.

Pindah-silang (Crossover) Setelah pemilihan dua pasangan individu, langkah selanjutnya adalah prose pindah-silang. Crossover adalah proses menciptakan coded xc baru dengan kombinasi dari dua coded xc. Disini digunakan algoritma crossover satu-titik. Tergantung pada nilai probabilitas yang telah ditentukan (pc: probabilitas crossover; 0 < pc < 1) nilai-nilai xc dari pasangan individu dikompbinasikan atau tidak. Jika nilai xc dikombinasikan (crossover = true) maka nilai binary-coded x dari pasangan individu (suatu bit-string) akan dipotong dua bagian dengan pemilihan titik crossover secara random. Dua coded xc baru dihasilkan melalui alternatif kombinasi dari bagian-bagian tersebut. Example: Crossover (based on function F0; 0.0 < x < 10; crossover point= 1) Pare nts PF PM

x xc (binarycoded x) 1 001000 00 7 111000 00

Y-Wert

0.108

xc (cutted )

0 010000 0 2.68 E- 1 04 110000 0

xc (twiste d) 1 010000 0 0 110000 0

xc (binarycoded x) 101000 00

x Y

childr en

5 0.7 98

C1

011000 00

6 0.1 08

C2

Mutasi (Mutation) Langkah terakhir dari GA adalah mutasi. Mutasi merupakan proses merubah nilai coded xc secara acak, dengan mengimplementasikan satu-titik algoritma mutasi. Pelaksanaan mutasi didasarkan pada probabilitas mutasi (pm; 0 < pm < 1.0). jika nilai xc dimutasikan maka nilai dari posisi yang dipilih secara acak dari binary-coded xc berubah. Bila nilai pada posisi tersebut 0, akan berubah menjadi 1 dan sebaliknya. Contoh berikut C1 tidak dimutasi; C2 dimutasi. Posisi 3 dari binary-string xc dirubah. Example: Mutation (based on function F0 ; 0.0 < x < 10; mutation position = 3) before mutation C1 C2

xc (binarycoded x)

x

Y

xc (binarycoded x)

x

Y

1010000 0 0110000 0

5

0.798

10100000

5

0.798

after mutation No mutated

6

0.108

01000000

2

1.22 E-08

C2 (mutated)

3

Example: Crossover (based on function F0; 0.0 < x < 10; crossover point= 1) Parents x xc (binary-coded x) Y-Wert PF 1 00100000 0.108 PM 7 11100000 2.68 E-04 xc (cutted) 0 0100000 1 1100000

xc (twisted) xc (binary-coded x) x 1 0100000 10100000 5 0 1100000 01100000 6

Y children 0.798 C1 0.108 C2

Example: Mutation (based on function F0 ; 0.0 < x < 10; mutation position = 3) before mutation xc (binary-coded x) x Y C1 10100000 5 0.798 C2 01100000 6 0.108 xc (binary-coded x) x 10100000 5 01000000 2

Y 0.798 1.22 E-08

after mutation C1 (no mutated) C2 (mutated)

4

5