KECERDASAN BUATAN RANGKUMAN 12,13,14

 

Genetic Algorithm

Genetic algorithm adalahsuatumetode meta-heuristik yang dapatmenyelesaikanpermasalahanproduksipakaian. Formalasirumus fitness yang tepatdapatmemberikansuatunilaidarikromosomdalam genetic algorithm, sehingga genetic algorithm dapatbekerjamaksimaluntukmenyelesaikanpermasalahanperencanaanproduksi.

 

Outline

Genetic Algorithm  :

Chromosome( Kromosom)

Fitness( Kebugaran )

Parent Selection( Seleksiinduk )                                                                                                            Crossover and Mutation ( Crossover dan Mutase )

Survivor Selection( Seleksi korban )

Solusidalam Genetic Algorithm :

1.      Genetic Algorithm memodelkansolusinyasebagai string / array

2.       Bentuk default adalah Array 1 dimensi Tapi tidak terbatas padanya, Tetapitidakterbatas pada itu

3.       Juga disebutKromosom

4.       Juga disebutsebagai Solusi IndividuKeterampilan

5.       teknikdiperlukanuntukDesain  a Solution

6.        Occam's Razor: Semakinsederhanasemakinbaik

Contoh Desain Solusi

MasalahTravelling Salesman 

1.  Jika kitamemilikikota N untukdikunjungi

-          ID Kota: 1, 2,…, N

-          AsumsikanSemuakotaterhubungsepenuhnya

2. Makasolusinyaadalah:

-          Array [1 × N] dari Integer

-          Nilai: urutankunjungan

 

 

 

Pengoptimalan matematika

 

 

1.      Jika kita memiliki fungsi untuk mengoptimalkan

a. F (x_1,x_2,…,x_n )

2.      Maka solusinya adalah:

a. Larik [1 × N] Float

b. Nilai: urutan kunjungan

 

Masalah Knapsack

Masalah Kendi Air

 

Pencarianmetaheuristik

1.      Prosedur tingkat tinggi atau heuristik yang dirancang untuk menemukan, menghasilkan, atau memilih heuristik (algoritme penelusuran parsial) yang dapat memberikan solusi yang cukup baik untuk masalah pengoptimalan,terutamadenganinformasi yang tidaklengkapatautidaksempurnaataukapasitaskomputasi yang terbatas

2.      Ambil contohsekumpulansolusi yang terlalubesaruntukdijadikansampelsepenuhnya

Pengoptimalanmatematika

1.      Meminimalkanfungsi y = 3x ^ 4−4x ^ 3

2.      Pendekatanpencarian: Temukan x yang meminimalkan y

3.      Pendekatanmatematika: 

a. Turunanpertama

b. dy / dx = 12x ^ 3−12x ^ 2, menghasilkan x = 1

Contoh :

1. PencarianAcak

2. Simulasi Annealing

3.Algoritma genetikagenerasi 1

4.Algoritma Genetikagenerasi 2

5.Algoritma Genetikagenerasi 5

6.Algoritma Genetikagenerasi 10

AlgoritmaOptimasi

Komputasi Evolusioner

1.      abstraksi dari teori evolusi biologis yang digunakan untuk membuat prosedur atau metodologi optimasi,biasanyadiimplementasikan di komputer, yang digunakanuntukmemecahkanmasalah

Algoritmaevolusioner

1. umum, algoritmaoptimasi meta-heuristikberbasispopulasi yang menggunakanmekanisme yang terinspirasi oleh biologisepertimutasi, persilangan, seleksialam dan survival of the fittest.

2. EA adalahalgoritma yang menerapkanabstraksi EC

Genetic Algorithms (GA): binary strings

Evolution Strategies (ES): real-valued vectors 

Evolutionary Programming (EP): finite state machines

Genetic Programming (GP): LISP trees 

Differential Evolution (DE) 

Grammatical Evolution (GE) 

Skema Umum EA

Aplikasi EC: Optimasi

1.      Penjadwalan

-          Penjadwalan kursus, tabel waktu perusahaan / proyek, penjadwalan rumah sakit, dll.

2.      Masalah Knapsack, Pengemasan,

3.      Masalah Stok Pemotongan

4.      Simulasi Desain

5.      Dll

AlgoritmaGenetika

1. kelastertentudarialgoritmaevolusi yang menggunakanteknik yang terinspirasi oleh biologievolusisepertipewarisan, mutasi, seleksi, dan persilangan

2.      Awalnyadikembangkan oleh John Holland (1975)

Sifat AlgoritmaGenetika

1.      Individual - Solusi apa pun yang memungkinkan

2.      Populasi - Kelompoksemuaindividu

3.      Search Space - Semuakemungkinansolusiuntukmasalahini

4.      Kromosom - Cetakbiruuntukindividu

5.      Kebugaran - kualitassolusi

6.      Rekombinasi - menguraikanduasolusiberbeda dan kemudiansecaraacakmencampurbagian-bagiannyauntukmembentuksolusibaru

7.      Mutasi - secaraacakmengganggusolusikandidat

Kromosom

Representing Solution :

1.      Rancang apa solusinya, dan bagaimana mengukur kualitasnya

a.       Contoh: Masalah TSP

o   Solusi: Daftar kota yang dikunjungi

o   Kualitas: Biaya untuk mengunjungi semua kota menggunakan daftar yang tersedia

b.      Contoh: Masalah Knapsack

o   Solusi: daftar barang yang dipilih

o   Kualitas: nilai barang yang dipilih, kelebihan berat atau tidak

2. Rancangapasolusinya, dan bagaimanamengukurkualitasnya

a. Contoh: Meminimalkan / MemaksimalkanFungsi

- Solusi: x_1, x_2,…x_n

- Kualitas: evaluasifungsi

 3. Cetak biru (seperangkat parameter) yang menentukan solusi yang diusulkan untuk masalah tersebut

4. Diwakili dalam string :

- Secara tradisional sebagai biner, tetapi pengkodean lain seperti integer atau real juga dimungkinkan

5. Evolusi biasanya dimulai dari populasi individu yang dibuat secara acak

Contohkromosom

1 .Masalah: 

Temukan x_1 dan x_2 yang meminimalkanfungsi f (x_1, x_2) = x_1 ^ 3 + 1 / 3x_2 ^ 2 dalamrentang [-2, 3]

2.      RepresentasiIndividu

Nilai Integer, Nilai RiilPengkodean Biner (untukmewakili Integer) Pengkodean Integer (untukmewakili Real) Encoding Nyata (untukmewakili Real) Dll

Untuk mengoptimalkan nilai (nyata), praktik terbaik adalah menyandikan fenotipe ke dalam genotipe (kromosom) yang jauh lebih panjang.

v

FungsiKebugaran

1. Fungsiobjektif :

Evaluasikromosom Nilai / sifatsuatularutandiwakili oleh sebuahkromosomSebuahsolusimungkinmemilikibeberapafungsitujuan yang dirancang Harus mempertimbangkansemuakendala yang ada

2. Kualitaskromosom Nilai untukmenunjukkankualitassolusi

3. Survival of the fittest Semakintinggi fitness berartisemakinbaiksolusinyaKebugaran yang lebihtinggiharusbertahanIndividukebugaranrendahakanbinasa

4. CiriDidefinisikan dengan jelas (dari fungsi tujuan), Harus cukup cepat untuk dihitung, Harus menghasilkan hasil yang intuitif., Kandidat terbaik / terburuk harus memiliki nilai skor terbaik / terburuk

5. Memaksimalkanfungsitujuan

6.MeminimalkanfungsitujuanAtaukombinasinya

Masalah Penjual Bepergian

1.Baca setiap pasangan gen

2.Jika ada sisi (koneksi) untuk setiap pasang node dalam gen, hitung biayanya, f = 1 / h

3.Jika ada pasangan node yang tidak terhubung, f = 0

1.Masalah Knapsack 

Hitungbobot total, jika total <max, f = nilai total 

Jika total> max, f = 0

2.OptimasiFungsiDekodekromosom, 

jikanilainyaberadadalambatas,

hitungtujuannya Jika nilainya di luarbatas, f = 0

parent selection

1.Proses pemilihanindividusebagai orang tuauntukmenghasilkanketurunanbaruuntukgenerasiselanjutnya

-          Solusi individudipilihmelalui proses berbasiskebugaranMetode yang 

2.populer dan dipelajaridenganbaik: 

- PemilihanRoda Roulette 

- SeleksiTurnamen

- [Baru] Roda Roulette melaluiPenerimaan Stochastic

PemilihanRoda Roulette 

1.      Individu diberi kemungkinan terpilih yang berbanding lurus dengan kebugaran merekap_i = f_i / Σ_j = 1 ^ Nf_j

2.      Dua individu kemudian dipilih secara acak berdasarkan probabilitas tersebut dan menghasilkan keturunan.Stochastic, Kompleksitas waktu O (n) atau O (logn)

PemilihanRodaRolet Stochastic

Pilihsecaraacaksatuindividuidenganprobabilitasseragam (1 / N), Terimaseleksidenganprobabilitas fi / fmax, di mana fmax = max {f_i} _i = 1 ^ N adalah fitness maksimaldalampopulasi Jika tidak, prosedurdiulangidarilangkah 1

Seleksi Turnamen

kebisinganstokastikberkurang, cepat, mudahditerapkanmemilikitekananseleksikonstan

Crossover atauRekombinasi

1.Memungkinkan proses evolusiuntukbergerakmenuju wilayah ruangpencarian yang menjanjikan

2.Cocok dengan sub-solusi orang tua yang baikuntukmembangunketurunan yang lebihbaik

3,.Crossover tidak selaluterjadiberdasarkanprobabilitas yang ditetapkanProbabilitaspersilanganbiasanya ~ 60% hingga 70%.

4. Skema Umum: Titik Tunggal, DuaTitik, salingsilangtitik-n Persilanganseragam, Persilanganaritmatikadll.

5.Untukkromosom yang teratur Crossover yang cocoksebagian Cycle crossover Pesan crossover dll.

 

Mutase

1. untuk mensimulasikan pengaruh kesalahan yang terjadi dengan probabilitas rendah selama duplikasi

2. kemungkinan kecil mutasi

- loop melalui semua alel

- Dengan probabilitas kecil (~ 1%), ubah dengan jumlah kecil atau ganti dengan nilai baru

3. Skema Umum: Mutasitingkat bit Mutasitingkat gen / alel

4. MutasitingkatkromosomUntukkromosom yang teraturTukarmutasiPerebutanmutasidll.

Seleksi Korban

1.Penggantian Generasimenghasilkan n lepasmata air, di mana n adalahukuranpopulasi, dan seluruhpopulasidigantidengan yang baru di akhiriterasi Harus menambahkanmekanismeuntukmemastikanindividuterbaikbertahan: Elitisme

2.Stabil menghasilkansatuatauduamata air di setiapiterasi dan merekamenggantikansatuatauduaindividudaripopulasiJauhlebihsederhana, tetapimembutuhkanlebihbanyakgenerasiuntukberkumpul

Elitism :

Usually used in Generational Replacement type

Copied the best chromosomes into the next generation once or twice

Ensure the solution quality obtained will not decrease from one generation to the next

Stopping Criteria

Iterasi maks (generasi maks)

Batas waktu

Ketinggian kebugaran

Ambang batas kebugaran

Keragaman populasi dan generasi

 

EAs are suitable for problems:

MasalahKompleksSulitdimengertiTidakbisamenggunakancarakonvensionalSistemwaktunyataSolusinyatidakharus yang paling optimal TidakadapengetahuansebelumnyaTidakadaanalisismatematis yang tersedia

 

Problems Solved using EAs
MasalahPenjualBepergian Jalur TerpendekRanselMasalah Stok PemotonganPenjadwalanMasalahPengoptimalanLainnya

 

Choosing Searching Method

Seberapabesarruangmasalahnya? Berapafaktorpercabangan (b) dan kedalamansolusi (d)? Berapaprosesor dan ruangmemori yang tersedia? Apakahsolusinyaharus optimal? Dapatkahfungsiheuristikditemukan / dirumuskan? Ada satutujuanataulebih?

 

Conclusion 

Metode yang termasuk dalam pencarian buta membutuhkan memori yang sangat besar untuk memecahkan masalah sederhana.

Dengan kecepatan saat ini dan memori komputer yang terbatas, saat ini blind search masih belum memungkinkan untuk diimplementasikan ke dunia nyata.

Satu-satunya metode yang dapat digunakan adalah Iterative Deepening Search (IDS) karena memerlukan sedikit memori meskipun waktu pengerjaannya sangat lama.

Di antarametodepencarian yang termasukdalampencarianheuristik, A * adalahpilihanterbaikketikakitadapatmenemukanfungsiheuristikuntukmasalah yang akandiselesaikan. Kita dapatmemilihvariasi A * yang paling sesuaidenganmasalah yang akandipecahkan dan sumberdaya (waktu dan memori) yang kitamiliki. Jika lebihdarisatujenisfungsiheuristikditemukan, pilih yang paling mendekatibiayasebenarnya.