Algoritma Genetika

Dalam ilmu komputer dan riset operasi, algoritma genetika (GA) adalah metaheuristik yang terinspirasi oleh proses seleksi alam yang termasuk dalam kelas yang lebih besar yaitu algoritma evolusioner (EA). Algoritma genetika biasanya digunakan untuk menghasilkan solusi berkualitas tinggi untuk masalah optimasi dan pencarian dengan mengandalkan operator yang terinspirasi secara biologis seperti mutasi, crossover, dan seleksi. Beberapa contoh aplikasi GA termasuk mengoptimalkan pohon keputusan untuk kinerja yang lebih baik, memecahkan teka-teki sudoku, optimasi hiperparameter, inferensi sebab akibat, dan lain-lain.

Metodologi

Masalah optimasi

Dalam algoritma genetika, sebuah populasi kandidat solusi (disebut individu, makhluk, organisme, atau fenotipe) untuk sebuah masalah optimasi berevolusi menuju solusi yang lebih baik. Setiap kandidat solusi memiliki sekumpulan properti (kromosom atau genotipe) yang dapat dimutasi dan diubah; secara tradisional, solusi direpresentasikan dalam bentuk biner sebagai string 0 dan 1, tetapi pengkodean lain juga dimungkinkan.

Evolusi biasanya dimulai dari populasi individu yang dibangkitkan secara acak, dan merupakan proses yang berulang, dengan populasi di setiap iterasi disebut generasi. Pada setiap generasi, kebugaran setiap individu dalam populasi dievaluasi; kebugaran biasanya merupakan nilai dari fungsi objektif dalam masalah optimasi yang sedang dipecahkan. Individu yang lebih fit dipilih secara stokastik dari populasi saat ini, dan genom setiap individu dimodifikasi (direkombinasi dan mungkin dimutasi secara acak) untuk membentuk generasi baru. Generasi baru dari kandidat solusi kemudian digunakan dalam iterasi algoritma berikutnya. Umumnya, algoritme akan berhenti ketika jumlah generasi maksimum telah dihasilkan, atau tingkat kebugaran yang memuaskan telah dicapai untuk populasi.

Algoritma genetika pada umumnya membutuhkan
Representasi standar dari setiap kandidat solusi adalah sebagai sebuah larik bit (disebut juga bit set atau bit string).Larik dengan tipe dan struktur lain dapat digunakan dengan cara yang sama. Sifat utama yang membuat representasi genetika ini nyaman adalah bagian-bagiannya mudah disejajarkan karena ukurannya yang tetap, yang memfasilitasi operasi crossover sederhana. Representasi panjang variabel juga dapat digunakan, tetapi implementasi persilangan lebih kompleks dalam kasus ini.

Representasi seperti pohon dieksplorasi dalam pemrograman genetik dan representasi bentuk grafik dieksplorasi dalam pemrograman evolusioner; campuran kromosom linier dan pohon dieksplorasi dalam pemrograman ekspresi gen.Setelah representasi genetik dan fungsi fitness didefinisikan, GA akan menginisialisasi populasi solusi dan kemudian memperbaikinya melalui aplikasi berulang dari operator mutasi, crossover, inversi, dan seleksi.

Inisialisasi
Ukuran populasi bergantung pada sifat masalah, tetapi biasanya berisi beberapa ratus atau ribuan solusi yang mungkin. Seringkali, populasi awal dibuat secara acak, sehingga memungkinkan seluruh kemungkinan solusi (ruang pencarian). Kadang-kadang, solusi dapat "diunggulkan" di area di mana solusi optimal kemungkinan besar akan ditemukan atau distribusi probabilitas pengambilan sampel disetel untuk fokus pada area-area yang lebih diminati.

Seleksi
Selama setiap generasi yang berurutan, sebagian dari populasi yang ada dipilih untuk direproduksi untuk generasi baru. Solusi individu dipilih melalui proses berbasis kebugaran, di mana solusi yang lebih bugar (yang diukur dengan fungsi kebugaran) biasanya lebih mungkin untuk dipilih. Metode seleksi tertentu menilai kecocokan setiap solusi dan secara khusus memilih solusi terbaik. Metode lain hanya menilai sampel acak dari populasi, karena proses sebelumnya mungkin sangat memakan waktu.

Fungsi kebugaran didefinisikan melalui representasi genetik dan mengukur kualitas solusi yang direpresentasikan. Fungsi kebugaran selalu bergantung pada masalah. Sebagai contoh, dalam masalah knapsack, seseorang ingin memaksimalkan nilai total objek yang dapat dimasukkan ke dalam knapsack dengan kapasitas tertentu. Representasi dari solusi dapat berupa sebuah larik bit, di mana setiap bit merepresentasikan objek yang berbeda, dan nilai dari bit tersebut (0 atau 1) merepresentasikan apakah objek tersebut ada di dalam ransel atau tidak. Tidak semua representasi seperti itu valid, karena ukuran objek bisa saja melebihi kapasitas ransel. Kecocokan solusi adalah jumlah nilai dari semua objek di dalam knapsack jika representasi tersebut valid, atau 0 jika tidak.

Dalam beberapa masalah, sulit atau bahkan tidak mungkin untuk mendefinisikan ekspresi fitness; dalam kasus ini, simulasi dapat digunakan untuk menentukan nilai fungsi fitness dari sebuah fenotipe (misalnya dinamika fluida komputasi digunakan untuk menentukan hambatan udara dari kendaraan yang bentuknya dikodekan sebagai fenotipe), atau bahkan algoritma genetika interaktif digunakan.

Operator genetika
Langkah selanjutnya adalah menghasilkan populasi generasi kedua dari solusi-solusi yang terpilih, melalui kombinasi operator genetik: crossover (juga disebut rekombinasi), dan mutasi.

Untuk setiap solusi baru yang akan dihasilkan, sepasang solusi "induk" dipilih untuk dikawinkan dari kumpulan solusi yang telah dipilih sebelumnya. Dengan menghasilkan solusi "anak" menggunakan metode persilangan dan mutasi di atas, solusi baru dibuat yang biasanya memiliki banyak karakteristik yang sama dengan "induknya". Orang tua baru dipilih untuk setiap anak baru, dan prosesnya berlanjut hingga populasi solusi baru dengan ukuran yang sesuai dihasilkan. Meskipun metode reproduksi yang didasarkan pada penggunaan dua orang tua lebih "terinspirasi oleh biologi", beberapa penelitian menunjukkan bahwa lebih dari dua "orang tua" menghasilkan kromosom yang lebih berkualitas.

Proses-proses ini pada akhirnya menghasilkan populasi kromosom generasi berikutnya yang berbeda dari generasi awal. Secara umum, rata-rata kebugaran akan meningkat dengan prosedur ini untuk populasi, karena hanya organisme terbaik dari generasi pertama yang dipilih untuk berkembang biak, bersama dengan sebagian kecil solusi yang kurang cocok. Solusi yang kurang cocok ini memastikan keanekaragaman genetik dalam kumpulan genetik orang tua dan oleh karena itu memastikan keanekaragaman genetik generasi anak-anak berikutnya.

Terdapat perbedaan pendapat mengenai pentingnya persilangan versus mutasi. Ada banyak referensi dalam Fogel (2006) yang mendukung pentingnya pencarian berbasis mutasi.Meskipun crossover dan mutasi dikenal sebagai operator genetik utama, ada kemungkinan untuk menggunakan operator lain seperti pengelompokan ulang, kolonisasi-kepunahan, atau migrasi dalam algoritme genetik.

Perlu dilakukan tuning parameter seperti probabilitas mutasi, probabilitas crossover, dan ukuran populasi untuk menemukan pengaturan yang masuk akal untuk kelas masalah yang sedang dikerjakan. Tingkat mutasi yang sangat kecil dapat menyebabkan penyimpangan genetik (yang bersifat non-ergodik). Laju rekombinasi yang terlalu tinggi dapat menyebabkan konvergensi prematur pada algoritma genetika. Laju mutasi yang terlalu tinggi dapat menyebabkan hilangnya solusi yang baik, kecuali jika seleksi elitis digunakan. Ukuran populasi yang memadai memastikan keanekaragaman genetik yang cukup untuk masalah yang dihadapi, tetapi dapat menyebabkan pemborosan sumber daya komputasi jika diatur ke nilai yang lebih besar dari yang dibutuhkan.

Heuristik
Selain operator utama di atas, heuristik lain dapat digunakan untuk membuat perhitungan lebih cepat atau lebih kuat. Heuristik spesiasi menghukum crossover antara kandidat solusi yang terlalu mirip; hal ini mendorong keanekaragaman populasi dan membantu mencegah konvergensi dini ke solusi yang kurang optimal.

Disadur dari: en.wikipedia.org

Psikologi

Heuristik, berasal dari bahasa Yunani εὑρίσκω (heurískō), yang berarti "menemukan", adalah proses dimana orang menggunakan jalan pintas mental untuk mengambil keputusan. Ini adalah strategi sederhana yang digunakan oleh manusia, hewan, organisasi, dan bahkan mesin untuk membuat penilaian cepat, mengambil keputusan, dan menemukan solusi terhadap masalah yang kompleks. Heuristik sering kali melibatkan pemfokusan pada aspek paling relevan dari suatu masalah atau situasi untuk merumuskan solusi. Meskipun heuristik dapat memberikan jawaban dan solusi yang tepat, heuristik tidak selalu benar atau lebih akurat.

Herbert A.Simon memperkenalkan konsep heuristik pada tahun 1950an, menunjukkan batasan pengambilan keputusan yang rasional. Pada tahun 1970-an, Amos Tversky dan Daniel Kahneman melanjutkan penelitian mereka tentang bias kognitif dan memperkenalkan model heuristik tertentu. Sementara beberapa orang mengklaim bahwa heuristik muncul semata-mata karena kemalasan, yang lain mengklaim bahwa proses ini bisa lebih tepat daripada keputusan berdasarkan faktor dan konsekuensi yang diketahui, terutama dalam situasi ketidakpastian.

Filsafat

Perangkat heuristik digunakan dalam entitas. Cerita, metafora, dan sejenisnya juga dapat disebut sebagai heuristik dalam konteks ini. Sebagai contoh klasik, gagasan utopia dalam karya Plato The Republic bukanlah sesuatu yang dikejar, melainkan panduan untuk memahami hubungan antar konsep dan implikasinya.

Selain itu, istilah heuristik sering digunakan untuk menggambarkan aturan, prosedur, atau metode praktis.Para filsuf sains menekankan pentingnya heuristik untuk pemikiran kreatif dan pembangunan teori ilmiah, termasuk karya seperti The Logic of Scientific Discovery karya Karl Popper dan tulisan lain oleh Imre Lakatos, Lindley Darden, dan William C. Wimsatt.

Hukum

Dalam teori hukum, khususnya teori hukum dan ekonomi, heuristik digunakan ketika analisis kasus per kasus dianggap tidak praktis tergantung kepentingan regulator. Misalnya saja dalam sistem regulasi sekuritas, asumsi bahwa semua investor bertindak dengan rasionalitas yang tinggi tidak selalu sesuai dengan kenyataan karena investor menghadapi keterbatasan kognitif akibat bias, heuristik, dan framing effect. Misalnya, batasan usia untuk meminum minuman beralkohol yaitu 21 tahun di Amerika Serikat dianggap sebagai batas heuristik dan sewenang-wenang karena sulit untuk menentukan kapan seseorang sudah cukup umur.

Berdasarkan undang-undang paten, pemberian monopoli sementara atas suatu ide penemuan dibenarkan untuk menciptakan insentif bagi para penemu. Namun, seperti dalam kasus usia minimum untuk meminum minuman beralkohol, batas 20 tahun untuk monopoli paten dianggap heuristik dan dapat dikatakan bahwa batas tersebut diatur secara berbeda tergantung pada jenis industrinya, misalnya dalam kasus paten perangkat lunak.

Ekonomi Perilaku

Heuristik dalam ekonomi perilaku mengacu pada strategi kognitif yang digunakan individu untuk menyederhanakan proses pengambilan keputusan dalam konteks ekonomi. Heuristik yang banyak diteliti adalah penahan dan penyesuaian, dimana penahan atau informasi awal dapat mempengaruhi penilaian di masa depan meskipun tidak ada kaitannya dengan keputusan yang diambil. Penyesuaian ini melibatkan perubahan bertahap terhadap peringkat awal. Fenomena ini diamati dalam berbagai konteks, termasukkeputusan keuangan, perilaku konsumen, dan negosiasi.

Para peneliti mencari strategi untuk mengurangi dampak penahan dan adaptasi, seperti menyediakan banyak jangkar, mendorong pembentukan jangkar alternatif, dan memberikan isyarat kognitif untuk meningkatkan kehati-hatian dalam pengambilan keputusan. Heuristik lain yang diperiksa mencakup keterwakilan, di mana orang-orang dikategorikan berdasarkan kesamaan dengan contoh-contoh yang umum, dan ketersediaan, di mana kemungkinan suatu peristiwa dinilai berdasarkan kemudahan kejadian tersebut terjadi pada mereka.

Disadur dari : en.wikipedia.org

Hill Climbing

Dalam analisis numerik, pendakian bukit merupakan teknik optimasi matematis yang termasuk dalam keluarga pencarian lokal. Ini adalah algoritma berulang yang dimulai dengan solusi sewenang-wenang terhadap suatu masalah dan kemudian mencoba menemukan solusi yang lebih baik dengan membuat perubahan bertahap pada solusi tersebut. Jika suatu perubahan mengarah pada solusi yang lebih baik, perubahan bertahap lainnya akan dilakukan terhadap solusi baru tersebut, dan seterusnya, hingga tidak ada perbaikan lebih lanjut yang dapat ditemukan.

Misalnya mendaki bukit bisa diterapkan pada masalah penjual. Sangat mudah untuk menemukan solusi awal yang mencakup semua kota, namun mungkin akan sangat buruk jika dibandingkan dengan solusi optimal.Algoritme dimulai dengan solusi ini dan melakukan perbaikan kecil pada solusi tersebut, seperti mengubah urutan dua kota yang dikunjungi. Anda mungkin akan menempuh jarak yang jauh lebih pendek.

Hill Climbing menemukan solusi optimal untuk masalah cembung; Untuk permasalahan lainnya, hanya ditemukan local optima (solusi yang tidak dapat diperbaiki oleh konfigurasi tetangga), yang belum tentu merupakan solusi terbaik (global optimum) dari semua kemungkinan solusi (ruang pencarian). Contoh algoritma yang menyelesaikan masalah cembung dengan mendaki bukit antara lain algoritma pemrograman linier simpleks dan algoritma pencarian biner. Untuk menghindari terjebak dengan optimasi lokal, Anda dapat menggunakan restart (yaitu pencarian lokal berulang) atau berbasis iterasi yang lebih kompleks (misalnya pencarian lokal berulang) atau skema berbasis memori (misalnya optimasi pencarian reaktif, dll gunakan pencarian tabu) atau dalam modifikasi stokastik tanpa memori (misalnya simulasi anil).Kesederhanaan relatif dari algoritma ini menjadikannya pilihan pertama yang populer di antara algoritma optimasi. Ini banyak digunakan dalam kecerdasan buatan untuk mencapai suatu keadaan tujuan dari titik awal. Dalam algoritma yang sesuai, opsi berbeda digunakan untuk node berikutnya dan node awal. Meskipun algoritme yang lebih canggih seperti Simulated Annealing atau Tabu Search mungkin memberikan hasil yang lebih baik, penskalaan juga dapat berfungsi dalam beberapa situasi.

Hill Climbing seringkali dapat memberikan hasil yang lebih baik dibandingkan algoritma lain ketika waktu yang tersedia untuk pencarian terbatas, seperti dalam sistem real-time, selama sejumlah kecil perbaikan umumnya mengarah pada solusi yang baik (solusi optimal). .atau pendekatan dekat). Di sisi lain, pengurutan gelembung dapat dilihat sebagai algoritma pendakian (setiap pertukaran elemen yang bertetangga mengurangi jumlah pasangan elemen yang tidak berurutan), namun pendekatan ini jauh dari efisien bahkan untuk N sederhana, karena jumlah pertukaran yang diperlukan meningkat tepat.

Varian

Dalam pendakian yang mudah, node pertama yang terdekat dipilih, sedangkan pada pendakian yang lebih curam, semua penerusnya dibandingkan dan node yang paling dekat dengan solusi dipilih. Kedua bentuk tersebut gagal jika tidak ada simpul terdekat. Hal ini dapat terjadi bila terdapat maksimum lokal dalam ruang pencarian yang bukan merupakan solusi. Mendaki bukit paling curam mirip dengan pencarian terbaik pertama, mencoba semua kemungkinan perluasan jalur saat ini, bukan hanya satu.

Pendakian stokastik tidak memeriksa semua tetangga sebelum memutuskan bagaimana bergerak. Sebaliknya, Anda memilih tetangga secara acak dan memutuskan (berdasarkan jumlah perbaikan yang dilakukan pada tetangga tersebut) apakah akan pindah ke tetangga tersebut atau memeriksa tetangga lainnya.Penurunan koordinat melakukan pencarian garis sepanjang arah koordinat pada titik saat ini di setiap iterasi. Beberapa versi penurunan koordinat secara acak memilih arah koordinat yang berbeda di setiap iterasi.

Masalah Dataran Tinggi

Masalah lain yang terkadang muncul saat mendaki bukit adalah dataran tinggi. Dataran tinggi terjadi ketika ruang pencarian datar, atau cukup datar sehingga nilai yang dikembalikan oleh fungsi tujuan tidak dapat dibedakan dari nilai yang dikembalikan untuk wilayah tetangga karena presisi yang digunakan oleh mesin untuk merepresentasikan nilai tersebut. Dalam kasus seperti itu, pendaki mungkin tidak dapat menentukan arah yang harus dituju dan mungkin menyimpang ke arah yang tidak pernah membawa kemajuan.

Disadur dari: en.wikipedia.org

Pencarian Lokal Teriterasi

Pencarian lokal berulang (ILS) adalah istilah dalam matematika terapan dan ilmu komputer yang mendefinisikan modifikasi metode pencarian atau penskalaan lokal untuk memecahkan masalah optimasi diskrit.Metode pencarian lokal bisa terjebak dalam kondisi minimum lokal di mana tidak ada tetangga terbaik yang tersedia.

Perubahan sederhana adalah mengulangi panggilan ke rutinitas pencarian lokal, setiap kali dimulai dengan konfigurasi awal yang berbeda. Ini disebut pencarian lokal berulang dan berarti bahwa pengetahuan yang diperoleh pada tahap pencarian lokal sebelumnya tidak digunakan. Pembelajaran berarti mengevaluasi sejarah sebelumnya, seperti ingatan tentang nilai minimum lokal yang ditemukan sebelumnya, untuk menciptakan titik awal yang lebih baik untuk penelusuran lokal.

ketika meminimalkan suatu fungsi, menentukan minimum lokal yang baik akan lebih mudah jika Anda memulai dari minimum lokal dengan nilai yang rendah dibandingkan jika Anda memulai dari titik acak. Satu-satunya batasan adalah menghindari pembatasan pada wadah penarik tertentu. Oleh karena itu, tendangan untuk menjadikan minimer lokal sebagai titik awal untuk putaran berikutnya harus cukup kuat, tetapi tidak terlalu kuat, sehinggaterhindar dari serangan balik. untuk reboot secara acak dari memori.

Algoritma Perturbasi

Menemukan algoritma perturbasi untuk pencarian lokal teriterasi (ILS) bukanlah tantangan yang mudah. Tujuan utamanya adalah untuk menghindari ketergantungan pada nilai minimum lokal yang sama dan untuk memastikan pencapaian properti ini, operasi penghapusan dilarang. Namun banyak hal yang perlu diperhatikan dalam merancang permutasi yang efektif karena ada dua jenis permutasi yang dianggap buruk. Pertama, permutasinya terlalu lemah, yang mungkin mengakibatkan penggunaan minimum lokal yang sama,. Kedua, permutasinya terlalu kuat, sehingga menyebabkan restart secara acak dan menyulitkan pencarian solusi optimal.Oleh karena itu, menciptakan algoritma perturbasi yang seimbang dan efisien sangat penting untuk mengoptimalkan kinerja pencarian lokal berulang.

Gangguan tolok ukur

Prosedurnya adalah menetapkan sekumpulan nilai gangguan sedemikian rupa sehingga nilai-nilai ini signifikan untuk suatu peristiwa: probabilitas sedang dan tidak jarang. Kemudian dimungkinkan untuk memeriksa grafik referensi pada waktu proses untuk mendapatkan gambaran rata-rata dari kejadian sebelumnya.

Gangguan adaptif
Karena tidak ada fungsi apriori yang menentukan nilai mana yang paling sesuai untuk suatu kelainan tertentu, pendekatan terbaik adalah menjadikannya adaptif. Misalnya, Battiti dan Protasi dalam mengusulkan algoritma pencarian reaktif untuk MAX-SAT, yang cocok dengan kerangka ILS. Mereka melakukan skema gangguan “terarah” yang diimplementasikan menggunakan algoritma pencarian Tabu dan menerapkan algoritma penurunan lokal standar setelah setiap gangguan. Cara lain untuk beradaptasi terhadap gangguan adalah dengan mengubah kekuatannya secara deterministik selama pencarian.

Optimalkan gangguan

Pendekatan lainnya adalah mengoptimalkan subbagian masalah dengan menjaga properti No Undo tetap aktif. Jika metode ini memungkinkan, solusi apa pun yang dihasilkan setelah gangguan mungkin akan sangat baik. Selain itu, suku cadang baru juga dioptimalkan.

Disadur dari: en.wikipedia.org

Pengertian Model Matematika

Model matematika adalah deskripsi abstrak dari sistem konkret dengan menggunakan konsep dan bahasa matematika. Proses pengembangan model matematika disebut pemodelan matematika. Model matematika digunakan dalam matematika terapan dan ilmu alam (misalnya fisika, biologi, ilmu bumi, kimia) dan disiplin ilmu teknik (misalnya ilmu komputer, teknik elektro), serta dalam sistem non-fisik seperti ilmu sosial. (seperti ekonomi, psikologi, sosiologi, ilmu politik). Matematika juga dapat diajarkan sebagai mata pelajaran mandiri .Penggunaan model matematika untuk memecahkan masalah dalam operasi komersial atau militer merupakan bagian besar dari bidang riset operasi.Model matematika juga digunakan dalam musik, linguistik dan filsafat (misalnya secara intensif dalam filsafat analitis). Sebuah model dapat membantu menjelaskan suatu sistem, menguji pengaruh berbagai komponen, dan membuat prediksi tentang perilaku.

Klasifikasi

Pemodelan matematika dapat dibagi menjadi beberapa kategori seperti: B. linier vs. nonlinier, statis vs. dinamis, eksplisit vs. implisit, diskrit vs. kontinu, deterministik vs.probabilistik (stokastik), deduktif, induktif atau geser dan strategis vs. non-strategis.Pertama, perbedaan antara model linier dan nonlinier bergantung pada jenis operator dalam model matematika. Model linier memiliki operator linier sedangkan model nonlinier memiliki operator nonlinier. Misalnya, dalam model statistik linier, hubungan parameter dianggap linier meskipun mungkin nonlinier dalam variabel prediktor.Hal yang sama berlaku untuk persamaan diferensial linier, yang masih dapat memiliki ekspresi nonlinier.Perbedaan model statis dan dinamis terletak pada perhitungan waktu.

Model dinamis merepresentasikan perubahan keadaan sistem dari waktu ke waktu, sedangkan model statis mengasumsikan bahwa sistem berada dalam keadaan setimbang dan tidak berubah seiring waktu.Lebih jauh lagi, perbedaan antara eksplisit dan implisit bergantung pada pengetahuan tentang parameter masukan. Suatu model dikatakan eksplisit jika seluruh parameter masukan diketahui dan keluarannya dapat dihitung dengan jumlah perhitungan yang terbatas.Sebaliknya, suatu model dikatakan implisit ketika parameter keluaran diketahui dan masukan yang bersangkutan harus diselesaikan melalui prosedur berulang.Pemodelan dapat bersifat diskrit atau kontinu, bergantung pada apakah objek direpresentasikan secara diskrit sebagai partikel dalam model molekul atau secara kontinu sebagai medan kecepatan fluida dalam pipa.Dalam model deterministik, setiap kombinasi nilai variabel ditentukan secara unik oleh parameter dan keadaan sebelumnya, sedangkan model stokastik menyertakan unsur keacakan dan variabel dijelaskan bukan oleh nilai unik tetapi oleh distribusi probabilitas.

Pemodelan deduktif didasarkan pada struktur logis dan berbasis teori, sedangkan pemodelan induktif didasarkan pada temuan empiris dan generalisasinya. Pemodelan mengambang tidak bergantung pada teori atau observasi dan hanya merupakan penerapan struktur yang diharapkan.Terakhir, model strategis dalam teori permainan berbeda karena model tersebut memodelkan agen dengan insentif yang tidak sesuai, seperti spesies yang bersaing atau penawar dalam lelang. Model strategis mengasumsikan bahwa para pemain adalah pengambil keputusan otonom yang secara rasional memilih tindakan yang memaksimalkan fungsi tujuan mereka. Tantangan utama ketika menggunakan model strategis adalah definisi dan kuantifikasi konsep solusi seperti ekuilibrium Nash. Model strategis mempunyai sifat menarik dalam memisahkan pemikiran tentang aturan main dari pemikiran tentang perilaku para pemain.

Konstruksi

Dalam bisnis dan teknik, model matematika dapat digunakan untuk memaksimalkan hasil tertentu. Sistem yang sedang dipertimbangkan memerlukan masukan tertentu. Hubungan antara input dan output sistem juga bergantung pada variabel lain: variabel keputusan, variabel keadaan, variabel eksogen dan variabel acak.Variabel keputusan terkadang disebut variabel independen. Variabel eksogen terkadang disebut parameter atau konstanta.Variabel-variabel tersebut tidak independen satu sama lain karena variabel keadaan bergantung pada keputusan, input, variabel acak dan eksogen.

Selain itu, variabel keluaran bergantung pada keadaan sistem (diwakili oleh variabel keadaan).Tujuan dan batasan suatu sistem dan penggunanya dapat direpresentasikan sebagai fungsi variabel keluaran atau variabel keadaan. Fungsi tujuan bergantung pada perspektif pengguna model. Tergantung pada konteksnya, fungsi tujuan juga disebut sebagai indeks kinerja karena merupakan salah satu ukuran yang menarik bagi pengguna.Meskipun tidak ada batasan jumlah fungsi tujuan dan batasan yang dapat dimiliki suatu model, penggunaan atau pengoptimalan model menjadi lebih kompleks (secara komputasi) seiring dengan bertambahnya jumlah fungsi tujuan.Misalnya, para ekonom sering menggunakan aljabar linier ketika menggunakan model input-output. Model matematika kompleks dengan banyak variabel dapat dikonsolidasikan menggunakan vektor, dimana satu simbol mewakili beberapa variabel.

Informasi apriori

Masalah pemodelan matematika sering diklasifikasikan ke dalam model kotak hitam atau model kotak putih, bergantung pada seberapa banyak informasi apriori tentang sistem yang tersedia. Model kotak hitam adalah sistem yang tidak tersedia informasi apriori. Model kotak putih (juga disebut kotak kaca atau kotak transparan) adalah sistem yang berisi semua informasi yang diperlukan. Dalam praktiknya, semua sistem berada di antara model kotak hitam dan kotak putih, sehingga konsep ini hanya berguna sebagai panduan intuitif saat memutuskan pendekatan mana yang akan diambil.Secara umum, yang terbaik adalah menggunakan informasi apriori sebanyak mungkin untuk membuat model lebih akurat.Oleh karena itu, model kotak putih umumnya dianggap lebih sederhana karena model berperilaku benar bila informasi digunakan dengan benar.

Informasi apriori sering kali datang dalam bentuk pengetahuan tentang jenis fungsi yang menghubungkan variabel berbeda. Misalnya, ketika kita memodelkan cara kerja suatu obat dalam sistem tubuh manusia, kita mengetahui bahwa jumlah obat dalam darah biasanya mengalami penurunan fungsi secara eksponensial. Namun masih adaparameter yang belum diketahui; Seberapa cepat jumlah obat berkurang dan berapa jumlah awal obat di dalam darah? Oleh karena itu, contoh ini bukanlah model kotak putih murni.

Parameter-parameter ini harus diestimasi dengan cara tertentu sebelum model dapat digunakan.Dalam model kotak hitam kami mencoba memperkirakan bentuk fungsional dari hubungan antara variabel dan parameter numerik dalam fungsi-fungsi ini. Misalnya, dengan menggunakan informasi apriori, kita dapat memperoleh serangkaian fungsi yang dapat mendeskripsikan sistem secara memadai. Jika tidak ada informasi apriori, kami mencoba menggunakan fungsi seumum mungkin untuk mencakup semua model yang berbeda.

Pendekatan yang umum digunakan untuk model kotak hitam adalahjaringan saraf tiruan, yang biasanya tidak membuat asumsi tentang data masukan.Alternatifnya, algoritma NARMAX (model rata-rata bergerak autoregresif nonlinier dengan masukan eksogen), dikembangkan sebagai bagian dari identifikasi sistem nonlinier, dapat digunakan untuk memilih istilah model, menentukan struktur model, dan memperkirakan parameter yang tidak diketahui dengan adanya gangguan nonlinier. linier dan berkorelasi. Keuntungan model NARMAX dibandingkan jaringan saraf adalah NARMAX menghasilkan model yang dapat ditulis dan dihubungkan ke prosesyang mendasarinya, sedangkan jaringan saraf menghasilkan perkiraan buram.

Disadur dari : en.wikipedia.org

Optimisasi Matematika

Optimasi matematika (atau disebut juga optimasi) atau pemrograman matematika adalah pemilihan elemen terbaik, dengan memperhatikan beberapa kriteria, dari beberapa alternatif yang tersedia. Secara umum, optimasi matematika dibagi menjadi dua subbidang: optimasi diskrit dan optimasi kontinu. Masalah optimasi muncul di semua disiplin ilmu kuantitatif mulai dari ilmu komputer dan teknik hingga riset operasi dan ekonomi, dan pengembangan metode solusi telah menjadi perhatian matematika selama berabad-abad.

Dalam pendekatan yang lebih umum, masalah optimasi terdiri dari memaksimalkan atau meminimalkan fungsi nyata dengan secara sistematis memilih nilai input dari dalam himpunan yang diizinkan dan menghitung nilai fungsi tersebut. Generalisasi teori dan teknik optimasi ke formulasi lain merupakan area yang luas dalam matematika terapan.

Sejarah

Fermat dan Lagrange menemukan formula berbasis kalkulus untuk mengidentifikasi titik optimum, sementara Newton dan Gauss mengusulkan metode iteratif untuk menuju titik optimum.

Istilah "pemrograman linier" untuk kasus optimasi tertentu adalah berkat George B. Dantzig, meskipun sebagian besar teorinya telah diperkenalkan oleh Leonid Kantorovich pada tahun 1939. (Pemrograman dalam konteks ini tidak mengacu pada pemrograman komputer, tetapi berasal dari penggunaan program oleh militer Amerika Serikat untuk merujuk pada jadwal pelatihan dan logistik yang diusulkan, yang merupakan masalah yang dipelajari Dantzig pada saat itu). Dantzig mempublikasikan algoritma Simplex pada tahun 1947, dan juga John von Neumann dan peneliti lainnya bekerja pada aspek teoritis pemrograman linier (seperti teori dualitas) pada waktu yang sama.

Peneliti penting lainnya dalam optimasi matematika termasuk yang berikut ini:

• Richard Bellman
• Dimitri Bertsekas
• Michel Bierlaire
• Stephen P. Boyd
• Roger Fletcher
• Martin Grötschel
• Ronald A. Howard
• Fritz John
• Narendra Karmarkar
• William Karush
• Leonid Khachiyan
• Bernard Koopman
• Harold Kuhn
• László Lovász
• David Luenberger
• Arkady Nemirovsky
• Yurii Nesterov
• Lev Pontryagin
• R. Tyrrell Rockafellar
• Naum Z. Shor
• Albert Tucker

Subbidang utama

• Pemrograman cembung mempelajari kasus ketika fungsi objektifnya cembung (minimisasi) atau cekung (maksimisasi) dan set batasannya cembung. Hal ini dapat dilihat sebagai kasus khusus pemrograman nonlinier atau sebagai generalisasi pemrograman kuadratik linier atau cembung.
• Pemrograman linier (LP), sebuah jenis pemrograman cembung, mempelajari kasus di mana fungsi objektif f adalah linier dan batasannya ditentukan hanya dengan menggunakan persamaan dan pertidaksamaan linier. Himpunan kendala seperti itu disebut polihedron atau polytope jika dibatasi.
• Pemrograman kerucut orde dua (SOCP) adalah sebuah program cembung, dan mencakup beberapa jenis program kuadratik.
• Pemrograman semidefinit (SDP) adalah subbidang optimasi cembung di mana variabel-variabel yang mendasarinya adalah matriks semidefinit. Ini adalah generalisasi dari pemrograman kuadratik linier dan cembung.
• Pemrograman kerucut adalah bentuk umum dari pemrograman cembung. LP, SOCP, dan SDP semuanya dapat dilihat sebagai program kerucut dengan jenis kerucut yang sesuai.
• Pemrograman geometris adalah teknik di mana kendala objektif dan ketidaksetaraan yang dinyatakan sebagai posynomial dan kendala kesetaraan sebagai monomial dapat ditransformasikan ke dalam program cembung.
• Pemrograman bilangan bulat mempelajari program linier di mana beberapa atau semua variabel dibatasi untuk mengambil nilai bilangan bulat. Ini tidak cembung, dan secara umum jauh lebih sulit daripada pemrograman linier biasa.
• Pemrograman kuadratik memungkinkan fungsi objektif memiliki suku kuadratik, sementara himpunan layak harus ditentukan dengan persamaan dan ketidaksetaraan linier. Untuk bentuk tertentu dari suku kuadrat, ini adalah jenis pemrograman cembung.
• Pemrograman pecahan mempelajari optimasi rasio dari dua fungsi nonlinier. Kelas khusus program pecahan cekung dapat ditransformasikan menjadi masalah optimasi cembung.
• Pemrograman nonlinier mempelajari kasus umum di mana fungsi tujuan atau kendala atau keduanya mengandung bagian nonlinier. Ini mungkin atau mungkin bukan program cembung. Secara umum, apakah program tersebut cembung atau tidak, akan mempengaruhi tingkat kesulitan dalam menyelesaikannya.
• Pemrograman stokastik mempelajari kasus di mana beberapa kendala atau parameter bergantung pada variabel acak.
• Optimasi robust, seperti halnya pemrograman stokastik, merupakan upaya untuk menangkap ketidakpastian dalam data yang mendasari masalah optimasi. Optimasi kuat bertujuan untuk menemukan solusi yang valid di bawah semua kemungkinan realisasi ketidakpastian yang didefinisikan oleh himpunan ketidakpastian.
• Optimasi kombinatorial berkaitan dengan masalah-masalah di mana himpunan solusi yang layak adalah diskrit atau dapat direduksi menjadi diskrit.
• Optimasi stokastik digunakan dengan pengukuran fungsi acak (noisy) atau input acak dalam proses pencarian.
• Optimasi dimensi tak terbatas mempelajari kasus ketika himpunan solusi yang layak adalah subset dari ruang dimensi tak terbatas, seperti ruang fungsi.
• Heuristik dan metaheuristik membuat sedikit atau tidak ada asumsi tentang masalah yang dioptimalkan. Biasanya, heuristik tidak menjamin bahwa solusi optimal akan ditemukan. Di sisi lain, heuristik digunakan untuk menemukan solusi perkiraan untuk banyak masalah optimasi yang rumit.
• Pemenuhan batasan mempelajari kasus di mana fungsi objektif f adalah konstan (ini digunakan dalam kecerdasan buatan, terutama dalam penalaran otomatis).
• Pemrograman kendala adalah paradigma pemrograman di mana hubungan antar variabel dinyatakan dalam bentuk kendala.
• Pemrograman disjungtif digunakan di mana setidaknya satu kendala harus dipenuhi, tetapi tidak semua. Hal ini sangat berguna dalam penjadwalan.
• Pemetaan ruang adalah sebuah konsep untuk pemodelan dan optimasi sistem rekayasa untuk akurasi model dengan ketelitian tinggi (halus) yang mengeksploitasi model kasar atau model pengganti yang bermakna secara fisik yang sesuai.

Dalam sejumlah subbidang, teknik-teknik ini dirancang terutama untuk optimasi dalam konteks dinamis (yaitu, pengambilan keputusan dari waktu ke waktu):

• Kalkulus variasi Merupakan cabang dari optimasi dimensi tak terbatas yang berkaitan dengan menemukan cara terbaik untuk mencapai suatu tujuan, seperti menemukan permukaan yang batasnya adalah kurva tertentu, tetapi dengan luas area yang paling kecil.
• Teori kontrol optimal adalah generalisasi dari kalkulus variasi yang memperkenalkan kebijakan kontrol.
• Pemrograman dinamis adalah pendekatan untuk menyelesaikan masalah optimasi stokastik dengan parameter model yang bersifat stokastik, acak, dan tidak diketahui. Pendekatan ini mempelajari kasus di mana strategi optimasi didasarkan pada pemecahan masalah menjadi submasalah yang lebih kecil. Persamaan yang menggambarkan hubungan antara submasalah ini disebut persamaan Bellman.
• Pemrograman matematika dengan kendala keseimbangan adalah di mana kendala mencakup ketidaksetaraan variasi atau komplementaritas.

Optimalisasi multi-objektif

Menambahkan lebih dari satu tujuan pada masalah optimasi akan menambah kompleksitas. Sebagai contoh, untuk mengoptimalkan desain struktural, kita menginginkan desain yang ringan dan kaku. Ketika dua tujuan bertentangan, sebuah trade-off harus dibuat. Mungkin ada satu desain yang paling ringan, satu desain yang paling kaku, dan sejumlah desain yang tak terbatas yang merupakan kompromi antara berat dan kekakuan. Himpunan desain trade-off yang meningkatkan satu kriteria dengan mengorbankan kriteria lainnya dikenal sebagai himpunan Pareto. Kurva yang dibuat dengan memplotkan berat terhadap kekakuan dari desain terbaik dikenal sebagai batas Pareto.

Sebuah desain dinilai sebagai "Pareto optimal" (setara dengan "Pareto efisien" atau dalam himpunan Pareto) jika tidak didominasi oleh desain lainnya: Jika desain tersebut lebih buruk daripada desain lain dalam beberapa hal dan tidak lebih baik dalam hal apa pun, maka desain tersebut didominasi dan tidak optimal secara Pareto.

Pilihan di antara solusi "optimal Pareto" untuk menentukan "solusi favorit" didelegasikan kepada pengambil keputusan. Dengan kata lain, mendefinisikan masalah sebagai optimasi multi-objektif menandakan bahwa ada beberapa informasi yang hilang: tujuan yang diinginkan diberikan tetapi kombinasinya tidak dinilai secara relatif satu sama lain. Dalam beberapa kasus, informasi yang hilang dapat diperoleh melalui sesi interaktif dengan pengambil keputusan.

Masalah optimasi multi-objektif telah digeneralisasi lebih lanjut menjadi masalah optimasi vektor di mana urutan (parsial) tidak lagi diberikan oleh urutan Pareto.

Pengoptimalan multi-moda atau global

Masalah optimasi sering kali bersifat multi-modal; artinya, masalah tersebut memiliki beberapa solusi yang baik. Solusi-solusi tersebut dapat berupa solusi yang baik secara global (nilai fungsi biaya yang sama) atau bisa juga berupa solusi yang baik secara global dan solusi yang baik secara lokal. Mendapatkan semua (atau setidaknya beberapa) dari beberapa solusi adalah tujuan dari pengoptimal multi-modal.

Teknik optimasi klasik karena pendekatannya yang berulang-ulang tidak memberikan hasil yang memuaskan ketika digunakan untuk mendapatkan banyak solusi, karena tidak ada jaminan bahwa solusi yang berbeda akan diperoleh bahkan dengan titik awal yang berbeda dalam beberapa kali menjalankan algoritma.Pendekatan umum untuk masalah optimasi global, di mana beberapa ekstrema lokal mungkin ada termasuk algoritme evolusioner, optimasi Bayesian, dan simulated annealing.

Disadur dari : en.wikipedia.org