Operator dan Teknik Lanjutan dalam Algoritma Genetika
Genotipe yang paling sederhana adalah kromosom haploid atau tunggal. Kromosom haploid hanya mengandung satu set gen yaitu, satu alel untuk menempati setiap lokus. Ketika alam membangun kehidupan yang lebih kompleks maka, diperlukan struktur kromosom dan ini dapat dicapai dengan diploid. Dalam bentuk diploid, suatu genotipe membawa satu atau lebih pasangan kromosom yang berisi informasi untuk fungsi yang sama. Misalkan sebuah struktur kromosom diploid dimana huruf yang berbeda mewakili alel yang berbeda :
P q r s t
P Q R S T
Alel mewakili sifat gen tertentu. Awalnya, di alam masing-masing alel dapat mewakili sifat fenotipik yang berbeda. Pada contoh di atas, kita asumsikan bahwa semua huruf besar dominan dan semua huruf kecil resesif maka, fenotip diekspresikan sebagai :
P q r S t
--> P Q R S t
p Q R S t
Dominasi adalah operator genetik yang digunakan untuk menghitung fenotip dari nilai alel yang dimungkinkan pada posisi gen. Dominasi dan diploidi dapat dengan mudah diimplementasikan dalam algoritma genetika, kita asumsikan ada 3 alel :
(0) - Disandikan untuk gen 0;
(1) - Disandikan secara resesif untuk gen 1;
(2) - Disandikan secara dominan untuk gen 1.
Rasio fenotip untuk dominasi adalah 3 : 1 yang dicapai untuk pasangan alel 0 dengan 1, dan 0 dengan 2. Dominasi dapat berkembang melalui substitusi alel 1 untuk 2 dan sebaliknya.
Dalam algoritma genetika, diploidi mungkin berguna dalam aplikasi on-line dimana sistem dapat beralih diantara kondisi.
Algoritma genetika multiploid menggabungkan beberapa kandidat untuk setiap gen di dalam genotip tunggal dan menggunakan beberapa bentuk mekanisme dominasi untuk memutuskan mana pilihan masing-masing gen aktif dalam fenotip. Genotip multiploid yang ditunjukkan pada gambar dibawah berisi kromosom p, panjang L, dan mask yang menentukan kromosom p mana yang dominan pada posisi tertentu dalam kromosom. Informasi ini diterjemahkan menjadi fenotip sebagai berikut :
Nilai alel a pada lokus i dalam mask menunjukkan bahwa gen ke-i dalam kromosom dengan indeks a menjadi gen ke-i dari fenotip. Dalam gambar di atas, panjang mask adalah m dan panjang kromosom L maka, gen di lokus "i" dalam mask dengan nilai 'a' menunjukkan bahwa set ke-i dari L/m secara bersamaan dalam kromosom ke-a yang dominan.
Pembalikan adalah operator genetika yang tidak teratur dan mengkode ulang. Operator pembalikan adalah mekanisme alami utama untuk mengkode ulang masalah. Di operator pembalik, dua titik dipilih di sepanjang kromosom, kromosom dipotong pada titik-titik tersebut dan titik-titik akhir dari potongan dibalikkan. Sebagai contoh, anggap ada sebuah kromosom dengan panjang 8 dimana dua titik pembalik dipilih secara acak :
1 1 ^ 0 1 1 1 ^ 0 1
Dengan menggunakan operator pembalik maka, hasilnya akan menjadi :
1 1 1 1 1 0 0 1
Tujuan adanya pembalikan adalah untuk mengurangi panjang string sehingga mereka dapat bertahan lebih lama. Algoritma dasar untuk pembalikan dapat diberikan sebagai berikut :
Terdapat beberapa operator pengkode ulang, yang merupakan variasi pada pembalikan, yaitu :
1. Pembalikan linear;
2. Pembalikan linear + end;
3. Pembalikan berkelanjutan;
4. Pembalikan massa.
Fitur pembalikan dan crossover dikombinasikan sehingga menghasilkan sebuah operator pengkode ulang adalah :
1. Partially Matched Crossover (PMX);
2. Order Crossover (OX);
3. Cycle Crossover (CX).
3.1 Partially Matched Crossover (PMX)
Di PMX, dua string diselaraskan dan dua titik crossover dipilih secara seragam secara acak. Anggap terdapat dua string :
Dua titik dipilih secara acak dan PMX dilanjutkan berdasarkan posisi pertukaran. Diantara titik crossover ditukarkan. Ini dilakukan dengan memetakan induk B ke induk A. Jadi setelah PMX, keturunan yang dihasilkan sebagai berikut :
3.2 Order Crossover (OX)
OX dimulai dengan cara yang mirip dengan PMX tetapi bukan menggunakan pertukaran antar titik seperti PMX akan tetapi, OX menggunakan gerakan penggeseran dengan mentransfer posisi yang sudah dipetakan. Anggap terdapat sebuah kromosom induk :
Pada pemetaan induk B dengan induk A, titik 3,6, dan 5 dibiarkan kosong
Tempat kosong tersebut diisi dengan penggeseran yang dimulai dengan kedua titik crossover
Tempat kosong tersebut kemudian diisi dengan bagian yang cocok yang diambil dari induk A, sehingga keturunan yang dihasilkan seperti yang ada di bawah :
3.3 Cycle Crossover (CX)
CX berbeda dengan PMX dan OX, CX bekerja dengan rekombinasi dibawah batasan bahwa setiap gen berasal dari induk atau yang lain.
Di algoritma genetika relung biasanya merujuk kepada hal yang membuat kelompok tertentu menjadi unik, seperti memiliki tingkat kebugaran yang sama, genotip, dll. Sementara spesiasi merujuk kepada individu yang berada dalam kelompok tersebut.
4.1 Relung dan Spesiasi dalam Masalah Multimodal
Kita anggap terdapat sebuah mesin slot dua tangan, jika satu orang bermain, dia akan akan mencoba tiap tangan untuk beberapa saat untuk mengetahui siapa yang memiliki hasil lebih besar dan akan seterusnya menggunakan tangan tersebut. Sekarang kita anggap bahwa sekelompok orang memainkan mesin slot yang sama dan grup yang bermain harus berbagi kemenangan mereka dan begitu sebaliknya. Pemain diperbolehkan mengganti grup untuk meningkatkan bagian mereka.
Jika kita anggap M adalah total orang yang bermain :
Kemudian, orang-orang yang membentuk kelompok di masing-masing lengan diberikan oleh persamaan berikut :
Algoritma genetika menggunakan kepanikan untuk diterapkan di fungsi multimodal untuk menghadapi 2 masalah utama, yang pertama adalah distribusi individu secara merata di semua puncak seperti gambar di bawah :
Setiap puncak dalam lanskap solusi dapat dilihat sebagai relung yang terpisah. Aplikasi algoritma genetika yang berhasil harus menghasilkan beberapa individu yang tersebar di masing-masing relung. Masalah kedua ialah induk dari berbagai spesies yaitu relung yang berbeda cenderung menghasilkan anak yang tidak terpakai sehingga, induk yang menempati relung yang berbeda harus dikucilkan dari perkawinan. Berikut gambar yang mengilustrasikan masalah tersebut :
4.1.1 Crowding
Penanganan yang dilakukan untuk mencegah genotip tunggal mendominasi populasi, adalah dengan memastikan bahwa individu yang baru lahir akan menggantikan induk yang memiliki genotip yang mirip. Crowding mencoba untuk mempertahankan populasi yang seimbang dengan cara memilih formasi sel individu secara acak dan melalui perhitungan jarak hamming, akan dipilih korban yang cocok.
Keuntungan dari crowding adalah beberapa individu harus diperiksa kapan memilih korban, karena formasi sel biasanya berjumlah 2 atau 3. Penggantian individu yang serupa ini bertindak untuk mencegah satu genotip dari mengambil alih populasi secara sepenuhnya, sehingga memungkinkan relung yang kurang bugar untuk terbentuk dalam populasi utama.
4.1.2 Sharing
Pada metode sharing, individu yang berada dalam suatu populasi memiliki sumber daya yang terbatas sehingga mereka harus berjuang. Akan tetapi, sharing merupakan metode yang sangat spesifik terhadap masalah yang harus diketahui.
Menentukan fungsi Sharing berdasarkan kesamaan :
Atau, berdasarkan kesamaan pada fenotip (nilai kode) dibanding genotip :
Semakin mirip kromosomnya maka, semakin banyak nilai kebugaran yang harus dibagi. Setiap kromosom memiliki faktor berbagi yang dikalkulasikan :
Kebugaran kromosom dihitung ulang dengan membagi kebugaran asli dengan faktor pembagi :
4.2 Relung dan Spesiasi dalam Masalah Unimodal
Penggunaan relung dalam masalah multimodal adalah pemetaan sederhana, dengan evolusi dari berbagai spesies yang berbeda untuk tiap puncak dari lanskap solusi. Akan tetapi, pemetaan ini tidaklah mudah di masalah unimodal yang biasanya hanya memiliki satu puncak, atau memiliki satu puncak yang lebih tinggi dibanding yang lain.
Terdapat beberapa metode yang tidak secara ketat menggunakan relung, metode ini memastikan individu yang baru lahir cukup berbeda dari populasi lainnya yaitu, Pencegahan Klon dan Algoritma Genetika Keadaan Tunak (Steady State Genetic Algorithms/SSGA). Dua metode ini beroperasi dengan cara yang mirip dengan crowding. Akan tetapi, kedua metode ini memiliki biaya yang tinggi.
4.2.1 Pencegahan Inses
Pencegahan Inses berusaha untuk menjodohkan induk dengan niat anak mereka mengambil gen terbaik dari induk mereka. Hal ini dilakukan dengan mengawinkan induk yang berbeda satu sama lain. Ketika populasi berevolusi, individual di dalamnya menjadi lebih mirip, sehingga lebih menyulitkan untuk mencari induk yang sesuai. Untuk menghindari hal tersebut, terdapat ambang batas yang diterapkan yang memudahkan dalam pemilihan induk.
Pencegahan Inses mendorong perkawinan antar spesies, karena lanskap kebugaran di fungsi unimodal cenderung seperti yang terlihat dibawah:
SET THRESHOLD
REPEAT
FOR EACH INDIVIDUAL DO
TEST INDIVIDUAL
ENTER PARENT POPULATION
IF NO-NEW-PARENTS THEN LOWER THRESHOLD
FOR EACH INDIVIDUAL DO
REPEAT
SELECT PARENTS
UNTIL DIFFERENT()
UNTIL END-CRITERION REACHED OR THRESHOLD=0
Cara ini hanya akan berhasil jika sebuah individu lebih bugar dibandingkan anggota yang memiliki kebugaran paling rendah di populasi induk.
4.2.2 Algoritma Pigmi
Algoritma Pigmi digunakan pada masalah yang memiliki dua atau lebih kebutuhan. Misal, evolusi dari suatu solusi yang harus efisien dan singkat. Relung digunakan dengan memiliki dua fungsi kebugaran yang terpisah sehingga menciptakan dua spesies individu dari tiap spesies kemudian dianggap sebagai jenis kelamin yang berbeda, dan ketika orang tua dipilih untuk menciptakan individu baru, suatu individu ditarik dari masing-masing spesies dengan maksud dari tiap induk mengerahkan tekanan dari fungsi kebugarannya.
Berikut ini ialah pseudocode untuk Algoritma Pigmi:
REPEAT
FOR EACH INDIVIDUAL DO
TEST INDIVIDUAL WITH MAIN FITNESS FUNCTION
ENTER PARENT POPULATION #1
IF UNSUCCESSFUL
TEST INDIVIDUAL WITH SECONDARY FITNESS FUNCTION
ENTER PARENT POPULATION #2
FOR EACH INDIVIDUAL DO
SELECT PARENT FROM POPULATION #1
SELECT PARENT FROM POPULATION #2
CREATE NEW INDIVIDUAL
UNTIL END-CRITERION REACHED
Tiap relung diimplementasikan sebagai kelompok elitis yang terpisah, karena untuk setiap relung, yang mempertahankan individu pada lanskap solusi yang serupa.
4.3 Perkawinan Terbatas
Tujan dari perkawinan terbatas ini ialah untuk mendorong spesiasi dan mengurangi produksi yang cacat yang terjadi saat terdapat keturunan dari induk yang berbeda relung. Alam mencegah hal ini dengan dengan mencegah terjadinya perkawinan dari spesies yang berbeda, menggunakan berbagai teknik.
5. Operator Mikro
5.1 Segregasi dan Translokasi
Segregasi merupakan proses pemilihan acak dalam penyusunan gamet. Segregasi mengekploitasi organisasi kromosom yang tepat. Maka dari itu, operator translokasi digunakan sebagai operator crossover antar kromosom. Operator ini dapat diimplementasikan dengan menghubungkan alel dengan nama gen mereka.
5.2 Duplikasi dan Penghapusan
Terdapat juga operator tingkat rendah untuk melakukan pencarian algoritma genetika, yaitu Duplikasi dan Penghapusan. Duplikasi antar kromosom dilakukan dengan menduplikasikan gen tertentu dan menempatkannya dalam keturunannya. Untuk operator penghapusan dilakukan dengan cara menghapus gen ganda dari kromosom. Tingkat mutasi dapat dikontrol secara efektif oleh kedua operator ini, dimana duplikasi dapat meningkatkan tingkat mutasi sedangkan penghapusan menurunkan tingkat mutasi.
5.3 Penentuan Seksual
Penentuan jenis kelamin ditangani secara berbeda pada spesies yang berbeda.Sebagai contoh, kelamin manusia ditentukan dari salah satu dari 23 pasang kromosom. Perempuan memiliki kromosom XX dan laki-laki memiliki kromosom XY. Pada saat pembuahan, kromosom X dari perempuan akan digabungkan dengan kromosom X atau kromosom Y dari laki-laki. Dengan menerapkan strategi yang sama maka, pembentukan perbedaan jenis kelamin secara efektif membagi spesies menjadi 2 atau lebih kelompok.
6. Representasi Non-Biner
Kromosom adalah urutan simbol yang berupa angka biner sehingga, setiap simbol memiliki kardinalitas 2. Huruf kardinalitas yang lebih tinggi telah digunakan di beberapa penelitian dan diyakini diantaranya memiliki keunggulan. Goldberg berpendapat bahwa secara teori, representasi biner memberikan jumlah terbesar terhadap skema dan menyediakan paralelisme implisit tingkat tinggi. Tetapi Antonisse mengartikan skema secara berbeda, dan menyimpulkan bahwa huruf kardinalitas yang lebih tinggi yang mengandung lebih banyak skema dibanding biner.
Goldberg kini telah mengembangkan teori yang menjelaskan mengapa representasi kardinalitas tinggi dapat bekerja dengan baik. Teorinya mengatakan bahwa setiap simbol bertemu dalam beberapa generasi pertama hanya menyisakan sejumlah kecil kemungkinan nilai-nilai. Dengan cara ini, setiap simbol secara efektif hanya memiliki kardinalitas rendah. Berbagai operator bilangan real dapat dengan mudah dipertimbangkan, misal:
1. Operator Kombinasi
* Rata-rata : Mengambil rata-rata aritmatika dari gen kedua induk.
* Rata-rata geometris : Mengambil nilai akar kuadrat dari produk kedua nilai.
* Extension : Mengambil perbedaan antara dua nilai dan menambahkan atau mengurangi nilai tersebut.
2. Operator Mutasi
* Penggantian acak : Mengganti nilai dengan nilai acak.
* Creep : Menambah atau mengurangi jumlah nilai secara acak dalam jumlah kecil.
* Creep geometris : Mengkalikan nilai acak mendekati satu.
7. Optimalisasi Multi-Objektif
Pada masalah optimasi multi-objektif, beberapa fungsi perlu dioptimalkan secara bersamaan. Pada kasus ini, tidak terdapat solusi yang tebaik dengan semua objektif karena adanya perbedaan antar objektif. Oleh karena itu, biasanya ada seperangkat solusi untuk masalah multi-objektif, solusi ini disebut Solusi Optimal Pareto atau solusi yang tidak mendominasi.
Dengan menggunakan konsep optimalisasi Pareto, kita dapat menemukan seperangkat solsui yang optimal bagi tiap objektif.
8. Optimalisasi Kombinasi
Optimalisasi kombinasi mengandung sejumlah besar masalah dengan fitur dan properti yang berbeda. Berikut adalah karakteristik dari masalah-masalah tersebut:
* Untuk menentukan permutasi beberapa item yang terkait dengan masalah.
* Untuk menentukan kombinasi dari beberapa item.
* Untuk menentukan permutasi dan kombinasi dari beberapa item.
Pendekatan umum untuk mengaplikasikan algoritma genetika dalam masalah ini ialah:
* Menggunakan algoritma genetika untuk mengevolusi permutasi dan/atau kombinasi dari item yang dipertimbangkan.
* Menggunakan pendekatan heuristik untuk membangun solusi sesuai dengan permutasi dan kombinasi.
9. Teknik Berbasis Pengetahuan
Sebagian besar peneliti sudah menggunakan algoritma genetika menggunakan crossover tradisional dan operator mutasi, tetapi sudah banyak yang menganjurkan untuk merancang sebuah operator baru untuk setiap tugas, dengan ber-domain kan pengetahuan. Sehingga, hal ini akan membuat algoritma genetika lebih spesifik terhadap tugas dan meningkatkan performa secara signifikan. Dimana algoritma genetika dirancang unntuk menangani masalah nyata dan harus bersaing dengan teknik optimasi lainnya. Berbagai metode untuk menggabungkan informasi spesifik dari masalah dengan algoritma genetika adalah sebagai berikut:
- Skema hibrida.
- Operator yang diarahkan dengan pengetahuan.
- Komputer paralel.
Dalam skema hibrida, algoritma genetika digunakan untuk mendekati nilai optimal, kemudian skema optimasi konvensional dapat digunakan untuk lebih mendekati nilai optimal. Skema hibrida dapat direpresentasikan menggunakan skema seperti yang terlihat pada gambar dibawah:
Pada operator yang diarahkan menggunakan pengetahuan dapat digunakan untuk:
- Menghasilkan sistem Steiner.
- Menghitung mutasi dan crossover yang dipertahankan.
- Mutasi yang diarahkan pada tujuan.
Pada komputer paralel pada algoritma genetika menggunakan operasi master/slave. Master melakukan seleksi dan perkawinan, sedangkan slave mengevaluasi kebugaran dari kromosom baru. Master menunggu hingga seluruh slave menyelesaikan tugas atau master dapat membagikan pekerjaan baru kepada tiap slave setelah slave tersebut menyelesaikan pekerjaannya. Hal ini dapat terlihat pada gambar dibawah:
