diklatkerja

Operation Research and Analysis

Model Matematika: Klasifikasi, Pengertian, dan Penerapan dalam Bisnis dan Teknik

Dipublikasikan oleh Dias Perdana Putra pada 16 April 2024

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

Selengkapnya

Model Matematika: Klasifikasi, Pengertian, dan Penerapan dalam Bisnis dan Teknik

Operation Research and Analysis

Metode Iteratif: Pengertian, Definisi, dan Metode

Dipublikasikan oleh Dias Perdana Putra pada 16 April 2024

Metode Interatif

Dalam matematika komputasi, metode iteratif adalah prosedur matematika yang menggunakan nilai awal untuk menghasilkan rangkaian perkiraan solusi yang meningkat terhadap suatu kelas masalah, dengan perkiraan ke-n diturunkan dari perkiraan sebelumnya. Implementasi khusus dari metode iteratif, termasuk kriteria terminasi, adalah algoritma metode iteratif. Suatu metode iteratif dikatakan konvergen jika barisan-barisan yang bersesuaian konvergen pada pendekatan pertama tertentu. Biasanya, analisis konvergensi yang ketat secara matematis dilakukan secara berulang; Namun, prosedur berulang berdasarkan heuristik juga umum dilakukan.

Metode langsung, sebaliknya, berupaya memecahkan masalah dengan menggunakan serangkaian operasi terbatas.Jika tidak ada kesalahan pembulatan, metode langsung memberikan solusi yang akurat (misalnya menyelesaikan sistem persamaan linear dengan eliminasi Gaussian). Untuk persamaan nonlinier, metode iteratif seringkali merupakan satu-satunya pilihan. Namun, metode iteratif juga sering berguna untuk permasalahan linier dengan banyak variabel (terkadang hingga jutaan), dimana metode langsung akan terlalu mahal (dan dalam beberapa kasus tidak mungkin) bahkan dengan daya komputasi terbaik yang tersedia.

Titik tetap yang menarik

Jika persamaan dapat ditulis sebagai f(x) = x dan penyelesaian x adalah titik tarik-menarik tetap dari f, maka kita dapat memulai dari titik x1 pada daerah tarik-menarik x dan himpunan xn+ 1 = f(xn) untuk n 1, dan barisan {xn} n 1 akan konvergen untuk menyelesaikan x. Di sini xn adalah pendekatan atau iterasi ke-n dari x dan xn+1 adalah iterasi berikutnya atau n+1 x. Alternatifnya, metode numerik sering kali menggunakan eksponen dalam tanda kurung. agar tidak mengalihkan perhatian dari petunjuk yang mempunyai arti lain. (Contoh: x(n+1) = f(x(n)).) Jika fungsi f dapat terdiferensiasi kontinu, syarat yang cukup untuk konvergensi adalah bahwa jari-jari spektral turunan dibatasi secara ketat oleh kesatuan di sekitar titik tetap.Jika kondisi ini terpenuhi pada suatu titik tertentu, maka harus ada lingkungan yang cukup kecil (cekungan daya tarik).

Sistem linier

Untuk sistem persamaan linier, dua kelas utama metode iteratif adalah metode iteratif stasioner dan metode subruang Krylov yang lebih umum.

Metode iteratif stasioner

pengantar

Metode iteratif stasioner menyelesaikan sistem linier dengan operator yang mendekati operator aslinya; dan berdasarkan kesalahan pengukuran pada hasil (sisa), buatlah “persamaan koreksi” yang proses ini diulangi. Meskipun metode ini mudah untuk diturunkan, diterapkan, dan dianalisis, konvergensi hanya dijamin untuk kelas matriks tertentu.

Definisi

Sebuah metode iteratif didefinisikan oleh

$\mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0$

dan untuk sistem linier tertentu $A\mathbf {x} =\mathbf {b}$ dengan solusi eksak $\mathbf {x} ^{*}$ kesalahan oleh

$\mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.$

Metode iteratif disebut linier jika terdapat matriks $C\in \mathbb {R} ^{n\times n}$ sedemikian itu

$\mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0$

dan matriks ini disebut matriks iterasi. Metode iteratif dengan matriks iterasi tertentu $C$ disebut konvergen jika berikut ini berlaku

$\lim _{k\rightarrow \infty }C^{k}=0\,.$

Sebuah teorema penting menyatakan bahwa untuk suatu metode iteratif dan matriks iterasinya $C$ konvergen jika dan hanya jika jari-jari spektralnya $\rho (C)$ lebih kecil daripada kesatuan, yaitu

$\rho (C)<1\,.$

Metode iteratif dasar bekerja dengan membagi matriks $A$ menjadi

$A=M-N$

dan di sini matriks $M$ harus mudah dibalik. Metode iteratif sekarang didefinisikan sebagai

$M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b\,,\quad k\geq 0\,.$

Dari sini berikut bahwa matriks iterasi diberikan oleh

$C=I-M^{-1}A=M^{-1}N\,.$

Contoh

Contoh dasar metode iteratif stasioner menggunakan pemisahan matriks $A$ seperti

$A=D+L+U\,,\quad D:={\text{diag}}((a_{ii})_{i})$

di mana $D$ hanyalah bagian diagonal dari $A$ , dan $L$ adalah bagian segitiga bawah dari $A$ . Masing-masing, $U$ adalah bagian segitiga atas dari $A$ .

Metode Richardson: $M:={\frac {1}{\omega }}I\quad (\omega \neq 0)$

Metode Jacobi: $M:=D$

Metode Jacobi teredam: $M:={\frac {1}{\omega }}D\quad (\omega \neq 0)$

Metode Gauss–Seidel: $M:=D+L$

Metode over-relaksasi (SOR): $M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)$

Relaksasi berlebihan berurutan (SSOR): $M:={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \not \in \{0,2\})$

Metode iteratif stasioner linier juga disebut metode relaksasi.

Metode subruang Krylov

Metode subruang Krylov terdiri dari pembuatan basis dari barisan pangkat matriks yang berurutan dikalikan dengan sisa awal (urutan Krylov). Perkiraan solusi kemudian dibuat dengan meminimalkan residu di subruang yang dibuat. Metode prototipe kelas ini adalah metode gradien konjugasi (CG), yang mengasumsikan bahwa matriks sistem A terdefinisi positif secara simetris. Untuk nilai simetris (dan mungkin tak terhingga), metode residu minimum(MINRES) dapat digunakan. Untuk matriks non-simetris, metode seperti metode residu terkecil yang digeneralisasi (GMRES) dan metode gradien bikonjugasi (BiCG) telah diturunkan.

Konvergensi metode subruang Krylov

Karena metode ini membentuk basis, terbukti bahwa metode tersebut konvergen dalam N iterasi, di mana N adalah ukuran sistem. Namun, dengan adanya kesalahan pembulatan, pernyataan ini tidak berlaku; apalagi, dalam praktiknya N bisa sangat besar, dan proses iteratif mencapai akurasi yang cukup jauh lebih awal. Analisis metode ini sulit, tergantung pada fungsi spektrum operator yang rumit.

Prakondisi

Operator aproksimasi yang muncul dalam metode iteratif stasioner juga dapat digabungkan dalam metode subruang Krylov seperti GMRES (sebagai alternatif, metode Krylov yang telah diprakondisikan dapat dianggap sebagai percepatan metode iteratif stasioner), di mana mereka menjadi transformasi dari operator asli ke kondisi yang mungkin lebih baik. satu. Konstruksi preconditioners adalah area penelitian yang besar.

Sejarah

Jamshīd al-Kāsh menggunakan metode iteratif untuk menghitung sinus 1° dan dalam Risalah tentang Akord dan Sinus dengan sangat presisi. Salah satu metode berulang pertama untuk menyelesaikan sistem linier muncul dalam surat dari Gauss kepada seorang siswa. Dia mengusulkan penyelesaian sistem persamaan 4 x 4 dengan berulang kali mencari suku dengan sisa terbesar.

Teori metode iteratif stasioner tertanam kuat dalam karya D.M. Muda sejak tahun 1950-an. Metode gradien konjugasi juga ditemukan pada tahun 1950-an, terlepas dari pengembangannya oleh Cornelius Lanczos, Magnus Hestenes dan Eduard Stiefel, namun sifat dan penerapannya masih sedikit dipahami pada saat itu. Baru pada tahun 1970-an diketahui bahwa metode adjoint bekerja sangat baik untuk persamaan diferensial parsial, khususnya persamaan elips.

Disadur dari: en.wikipedia.org

Selengkapnya

Metode Iteratif: Pengertian, Definisi, dan Metode

Operation Research and Analysis

Pencarian Lokal Teriterasi: Pengertian, dan Algoritma

Dipublikasikan oleh Dias Perdana Putra pada 16 April 2024

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

Selengkapnya

Pencarian Lokal Teriterasi: Pengertian, dan Algoritma

Operation Research and Analysis

Hill Climbing: Pengertian, Varian dan Masalah Dataran Tinggi

Dipublikasikan oleh Dias Perdana Putra pada 16 April 2024

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

Selengkapnya

Hill Climbing: Pengertian, Varian dan Masalah Dataran Tinggi

Operation Research and Analysis

Mengenal Pengertian, Fungsi dari Heuristik dalam Ilmu Komputer

Dipublikasikan oleh Dias Perdana Putra pada 16 April 2024

Heuristik

Dalam optimasi matematika dan ilmu komputer, adalah teknik yang dirancang untuk memecahkan masalah lebih cepat ketika metode klasik terlalu lambat atau untuk menemukan solusi perkiraan ketika metode klasik gagal untuk menemukan solusi yang tepat. . Hal ini dicapai dengan perdagangan optimalitas, kelengkapan, akurasi, atau presisi untuk kecepatan. Di satu sisi, itu bisa dianggap sebagai jalan pintas.

Fungsi heuristik,

fungsi yang memberi peringkat alternatif dalam algoritma pencarian pada setiap langkah percabangan berdasarkan informasi yang tersedia untuk memutuskan cabang mana yang akan diikuti. Misalnya, mungkin mendekati solusi yang tepat.

Definisi dan motivasi

Tujuan dari heuristik adalah untuk menghasilkan solusi dalam kerangka waktu yang wajar yang cukup baik untuk memecahkan masalah yang dihadapi. Solusi ini mungkin bukan yang terbaik dari semua solusi untuk masalah ini, atau mungkin hanya mendekati solusi yang tepat. Tapi tetap berharga karena menemukannya tidak membutuhkan waktu yang lama.

Heuristik dapat menghasilkan hasil sendiri, atau mereka dapat digunakan bersama dengan algoritma optimasi untuk meningkatkan efisiensinya (misalnya, mereka dapat digunakan untuk menghasilkan nilai benih yang baik). Hasil tentang NP-hardness dalam ilmu komputer teoretis menjadikan heuristik satu-satunya pilihan yang layak untuk berbagai masalah optimasi kompleks yang perlu diselesaikan secara rutin dalam aplikasi dunia nyata. Heuristik mendasari seluruh bidang Kecerdasan Buatan dan simulasi komputer berpikir, karena mereka dapat digunakan dalam situasi di mana tidak ada algoritma yang diketahui.

Trade-off

Kriteria trade-off untuk memutuskan apakah akan menggunakan heuristik untuk memecahkan masalah yang diberikan meliputi:

Optimalitas: Ketika ada beberapa solusi untuk masalah yang diberikan, apakah heuristik menjamin bahwa solusi terbaik akan ditemukan? Apakah benar-benar perlu untuk menemukan solusi terbaik?
Kelengkapan: Ketika ada beberapa solusi untuk masalah yang diberikan, dapatkah heuristik menemukan semuanya? Apakah kita benar-benar membutuhkan semua solusi? Banyak heuristik hanya dimaksudkan untuk menemukan satu solusi.
Akurasi dan presisi: Dapatkah heuristik memberikan interval kepercayaan untuk solusi yang diklaim? Apakah bilah kesalahan pada solusi terlalu besar?
Waktu eksekusi: Apakah ini heuristik paling terkenal untuk memecahkan masalah jenis ini? Beberapa heuristik berkumpul lebih cepat daripada yang lain. Beberapa heuristik hanya sedikit lebih cepat daripada metode klasik, dalam hal ini 'overhead' dalam menghitung heuristik mungkin berdampak negatif.

Dalam beberapa kasus, mungkin sulit untuk memutuskan apakah solusi yang ditemukan oleh heuristik cukup baik, karena teori yang mendasari heuristik tidak terlalu rumit.

Contoh

Masalah yang lebih sederhana

Salah satu cara untuk mencapai perolehan kinerja komputasi yang diharapkan dari heuristik terdiri dari pemecahan masalah yang lebih sederhana yang solusinya juga merupakan solusi untuk masalah awal.

Masalah penjual keliling

Contoh pendekatan dijelaskan oleh Jon Bentley untuk memecahkan masalah penjual keliling (TSP):

Diberikan daftar kota dan jarak antara setiap pasangan kota, apa rute terpendek yang mungkin mengunjungi setiap kota tepat satu kali dan kembali ke kota asal?

sehingga dapat memilih urutan menggambar menggunakan pen plotter. TSP dikenal sebagai NP-hard sehingga solusi optimal untuk masalah ukuran sedang pun sulit untuk dipecahkan. Sebaliknya, algoritma serakah dapat digunakan untuk memberikan solusi yang baik tetapi tidak optimal (ini adalah perkiraan untuk jawaban yang optimal) dalam waktu yang cukup singkat. Heuristik algoritma serakah mengatakan untuk memilih apa pun yang saat ini merupakan langkah terbaik berikutnya terlepas dari apakah itu mencegah (atau bahkan membuat tidak mungkin) langkah baik nanti. Ini adalah heuristik dalam praktik yang mengatakan itu adalah solusi yang cukup baik, teori mengatakan ada solusi yang lebih baik (dan bahkan dapat mengatakan seberapa jauh lebih baik dalam beberapa kasus).

Mencari

Contoh lain dari heuristik membuat algoritma lebih cepat terjadi pada masalah pencarian tertentu. Awalnya, heuristik mencoba setiap kemungkinan pada setiap langkah, seperti algoritma pencarian ruang penuh. Tapi itu bisa menghentikan pencarian kapan saja jika kemungkinan saat ini sudah lebih buruk daripada solusi terbaik yang sudah ditemukan. Dalam masalah pencarian seperti itu, heuristik dapat digunakan untuk mencoba pilihan yang baik terlebih dahulu sehingga jalur yang buruk dapat dihilangkan lebih awal (lihat pemangkasan alfa-beta). Dalam kasus algoritma pencarian terbaik-pertama, seperti pencarian A*, heuristik meningkatkan konvergensi algoritma sambil mempertahankan kebenarannya selama heuristik dapat diterima.

Newell dan Simon: hipotesis pencarian heuristik

Dalam pidato penerimaan Penghargaan Turing mereka, Allen Newell dan Herbert A. Simon membahas hipotesis pencarian heuristik: sistem simbol fisik akan berulang kali menghasilkan dan memodifikasi struktur simbol yang diketahui sampai struktur yang dibuat cocok dengan struktur solusi. Setiap langkah berikutnya tergantung pada langkah sebelumnya, sehingga pencarian heuristik mempelajari jalan apa yang harus dikejar dan mana

perlu diabaikan dengan mengukur seberapa dekat langkah saat ini dengan solusi. Oleh karena itu, beberapa kemungkinan tidak akan pernah dihasilkan karena kemungkinannya kecil untuk menyelesaikan solusi.

Metode heuristik dapat menyelesaikan tugasnya dengan menggunakan pohon pencarian. Namun, alih-alih menghasilkan semua cabang solusi yang mungkin, heuristik memilih cabang yang lebih mungkin menghasilkan hasil daripada cabang lainnya. Ini selektif pada setiap titik keputusan, memilih cabang yang lebih mungkin menghasilkan solusi.

Perangkat lunak antivirus

Perangkat lunak antivirus sering menggunakan aturan heuristik untuk mendeteksi virus dan bentuk malware lainnya. Pemindaian heuristik mencari kode dan/atau pola perilaku yang umum pada kelas atau keluarga virus, dengan seperangkat aturan yang berbeda untuk virus yang berbeda. Jika file atau proses eksekusi ditemukan berisi pola kode yang cocok dan/atau melakukan rangkaian aktivitas tersebut, pemindai menyimpulkan bahwa file tersebut terinfeksi. Bagian paling canggih dari pemindaian heuristik berbasis perilaku adalah bahwa ia dapat bekerja melawan virus yang sangat acak yang memodifikasi/bermutasi (polimorfik) yang tidak dapat dengan mudah dideteksi dengan metode pemindaian string yang lebih sederhana. Pemindaian heuristik memiliki potensi untuk mendeteksi virus di masa depan tanpa mengharuskan virus untuk pertama kali terdeteksi di tempat lain, diserahkan ke pengembang pemindai virus, dianalisis, dan pembaruan deteksi untuk pemindai yang diberikan kepada pengguna pemindai.

Jebakan

Beberapa heuristik memiliki teori dasar yang kuat; mereka diturunkan secara top-down dari teori atau diperoleh berdasarkan data eksperimental atau dunia nyata. Yang lain hanyalah aturan praktis berdasarkan pengamatan atau pengalaman dunia nyata bahkan tanpa melihat teori. Yang terakhir terkena lebih banyak jebakan.

Ketika heuristik digunakan kembali dalam berbagai konteks karena telah terlihat "berfungsi" dalam satu konteks, tanpa terbukti secara matematis untuk memenuhi serangkaian persyaratan tertentu, ada kemungkinan bahwa kumpulan data saat ini tidak selalu mewakili kumpulan data masa depan ( lihat: overfitting) dan "solusi" yang diklaim itu ternyata mirip dengan kebisingan.

Analisis statistik dapat dilakukan ketika menggunakan heuristik untuk memperkirakan kemungkinan hasil yang salah. Untuk menggunakan heuristik untuk memecahkan masalah pencarian atau masalah knapsack, perlu untuk memeriksa apakah heuristik tersebut dapat diterima. Diberikan fungsi heuristik $h(v_{i},v_{g})$ dimaksudkan untuk mendekati jarak optimal sebenarnya $d^{\star }(v_{i},v_{g})$ ke simpul tujuan $v_{g}$ dalam grafik berarah $G$ berisi $n$ total simpul atau simpul berlabel $v_{0},v_{1},\cdots ,v_{n}$ "diterima" berarti secara kasar bahwa heuristik meremehkan biaya untuk tujuan atau secara formal bahwa $h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})$ untuk semua $(v_{i},v_{g})$ di mana ${i,g}\in [0,1,...,n]$

Jika heuristik tidak dapat diterima, heuristik mungkin tidak akan pernah menemukan tujuannya, baik dengan berakhir di jalan buntu grafik $G$ atau dengan melompat-lompat di antara dua node $v_{i}$ dan $v_{j}$ dengan ${i,j}\neq g$ .

Disadur dari : en.wikipedia.org

Selengkapnya

Mengenal Pengertian, Fungsi dari Heuristik dalam Ilmu Komputer

Operation Research and Analysis

Mengenal Heuristic dari Sudut Pandang Psikologi, Hukum dan Ekonomi

Dipublikasikan oleh Dias Perdana Putra pada 16 April 2024

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

Selengkapnya