diklatkerja

Operation Research and Analysis

Optimasi Stokastik

Dipublikasikan oleh Siti Nur Rahmawati pada 22 Agustus 2022

Metode optimasi stokastik (SO) adalah metode optimasi yang menghasilkan dan menggunakan variabel acak. Untuk masalah stokastik, variabel acak muncul dalam rumusan masalah optimasi itu sendiri, yang melibatkan fungsi tujuan acak atau kendala acak. Metode optimasi stokastik juga mencakup metode dengan iterasi acak. Beberapa metode optimasi stokastik menggunakan iterasi acak untuk memecahkan masalah stokastik, menggabungkan kedua arti dari optimasi stokastik. Metode optimasi stokastik menggeneralisasi metode deterministik untuk masalah deterministik.

Metode untuk fungsi stokastik

Data masukan sebagian acak muncul di bidang-bidang seperti estimasi dan kontrol waktu nyata, optimasi berbasis simulasi di mana simulasi Monte Carlo dijalankan sebagai perkiraan sistem aktual, dan masalah di mana ada kesalahan eksperimental (acak) dalam pengukuran kriteria. Dalam kasus seperti itu, pengetahuan bahwa nilai fungsi terkontaminasi oleh "noise" acak mengarah secara alami ke algoritme yang menggunakan alat inferensi statistik untuk memperkirakan nilai "sebenarnya" fungsi dan/atau membuat keputusan optimal secara statistik tentang langkah selanjutnya. Metode kelas ini meliputi:

pendekatan stokastik (SA), oleh Robbins dan Monro (1951)
penurunan gradien stokastik
perbedaan hingga SA oleh Kiefer dan Wolfowitz (1952)
gangguan simultan SA oleh Spall (1992)
optimasi skenario

Metode pencarian acak

Di sisi lain, bahkan ketika kumpulan data terdiri dari pengukuran yang tepat, beberapa metode memasukkan keacakan ke dalam proses pencarian untuk mempercepat kemajuan. Keacakan tersebut juga dapat membuat metode kurang sensitif terhadap kesalahan pemodelan. Selanjutnya, keacakan yang disuntikkan dapat memungkinkan metode untuk lolos dari optimum lokal dan akhirnya mendekati optimum global. Memang, prinsip pengacakan ini dikenal sebagai cara yang sederhana dan efektif untuk mendapatkan algoritme dengan kinerja bagus yang hampir pasti secara seragam di banyak kumpulan data, untuk berbagai macam masalah. Metode optimasi stokastik semacam ini meliputi:

simulasi anil oleh S. Kirkpatrick, C. D. Gelatt dan M. P. Vecchi (1983)
anil kuantum
Kolektif Probabilitas oleh D.H. Wolpert, S.R. Bieniawski dan D.G. Rajnarayan (2011)
optimasi pencarian reaktif (RSO) oleh Roberto Battiti, G. Tecchiolli (1994), baru-baru ini diulas dalam buku referensi
metode cross-entropy oleh Rubinstein dan Kroese (2004)
pencarian acak oleh Anatoly Zhigljavsky (1991)
Pencarian informasi
terowongan stokastik
tempering paralel alias pertukaran replika
pendakian bukit stokastik
algoritma kawanan
algoritma evolusioner

algoritma genetika oleh Holland (1975)
strategi evolusi

algoritma optimasi & modifikasi objek kaskade (2016)

Sebaliknya, beberapa penulis berpendapat bahwa pengacakan hanya dapat meningkatkan algoritma deterministik jika algoritma deterministik dirancang dengan buruk sejak awal. Fred W. Glover[20] berpendapat bahwa ketergantungan pada elemen acak dapat mencegah pengembangan komponen deterministik yang lebih cerdas dan lebih baik. Cara di mana hasil algoritma optimasi stokastik biasanya disajikan (misalnya, hanya menyajikan rata-rata, atau bahkan yang terbaik, dari N berjalan tanpa menyebutkan spread), juga dapat menghasilkan bias positif terhadap keacakan.

Sumber Artikel: en.wikipedia.org

Selengkapnya

Operation Research and Analysis

Matematika Komputasi

Dipublikasikan oleh Siti Nur Rahmawati pada 22 Agustus 2022

Matematika komputasional melibatkan penelitian matematika dalam matematika serta di bidang sains di mana komputasi memainkan peran sentral dan esensial, dan menekankan algoritma, metode numerik, dan komputasi simbolis.

Matematika terapan komputasional terdiri dari penggunaan matematika untuk memungkinkan dan meningkatkan komputasi komputer dalam matematika terapan. Matematika komputasi juga dapat merujuk pada penggunaan komputer untuk matematika itu sendiri. Ini termasuk penggunaan komputer untuk perhitungan matematis (aljabar komputer), studi tentang apa yang dapat (dan tidak dapat) dikomputerisasi dalam matematika (metode efektif), perhitungan mana yang dapat dilakukan dengan teknologi saat ini (teori kompleksitas), dan bukti mana yang dapat diperoleh. dilakukan pada komputer (asisten bukti).

Bidang matematika komputasi

Matematika komputasi muncul sebagai bagian yang berbeda dari matematika terapan pada awal 1950-an. Saat ini, matematika komputasi dapat merujuk atau mencakup:

Ilmu komputasi, juga dikenal sebagai komputasi ilmiah atau rekayasa komputasi
Memecahkan masalah matematika dengan simulasi komputer sebagai lawan dari metode analitik matematika terapan
Metode numerik yang digunakan dalam komputasi ilmiah, misalnya aljabar linier numerik dan solusi numerik dari persamaan diferensial parsial
Metode stokastik, seperti metode Monte Carlo dan representasi ketidakpastian lainnya dalam komputasi ilmiah
Matematika komputasi ilmiah, khususnya analisis numerik, teori metode numerik
Kompleksitas komputasi
Aljabar komputer dan sistem aljabar komputer
Penelitian berbantuan komputer di berbagai bidang matematika, seperti logika (pembuktian teorema otomatis), matematika diskrit, kombinatorik, teori bilangan, dan topologi aljabar komputasi
Kriptografi dan keamanan komputer, yang melibatkan, khususnya, penelitian tentang pengujian primalitas, faktorisasi, kurva eliptik, dan matematika blockchain
Linguistik komputasi, penggunaan teknik matematika dan komputer dalam bahasa alami
Geometri aljabar komputasi
Teori grup komputasi
Geometri komputasi
Teori bilangan komputasi
Topologi komputasi
Statistik komputasi
Teori informasi algoritma
Teori permainan algoritma
Ekonomi matematika, penggunaan matematika dalam ekonomi, keuangan dan, sampai batas tertentu, akuntansi.
matematika eksperimental

Sumber Artikel: en.wikipedia.org

Selengkapnya

Operation Research and Analysis

Metode Iteratif

Dipublikasikan oleh Siti Nur Rahmawati pada 22 Agustus 2022

Dalam matematika komputasi, metode iteratif adalah prosedur matematika yang menggunakan nilai awal untuk menghasilkan urutan peningkatan solusi perkiraan untuk kelas masalah, di mana pendekatan ke-n diturunkan dari yang sebelumnya. Implementasi spesifik dari metode iteratif, termasuk kriteria terminasi, adalah algoritma dari metode iteratif. Metode iteratif disebut konvergen jika barisan yang bersesuaian konvergen untuk aproksimasi awal yang diberikan. Sebuah analisis konvergensi matematis ketat dari metode iteratif biasanya dilakukan; namun, metode iteratif berbasis heuristik juga umum.

Sebaliknya, metode langsung berusaha memecahkan masalah dengan urutan operasi yang terbatas. Dengan tidak adanya kesalahan pembulatan, metode langsung akan memberikan solusi eksak (misalnya, menyelesaikan sistem persamaan linear $A\mathbf {x} =\mathbf {b}$ dengan eliminasi Gauss). Metode iteratif seringkali merupakan satu-satunya pilihan untuk persamaan nonlinier. Namun, metode iteratif seringkali berguna bahkan untuk masalah linier yang melibatkan banyak variabel (kadang-kadang dalam urutan jutaan), di mana metode langsung akan sangat mahal (dan dalam beberapa kasus tidak mungkin) bahkan dengan daya komputasi terbaik yang tersedia.

Titik tetap yang menarik

Jika suatu persamaan dapat dimasukkan ke dalam bentuk f(x) = x, dan solusi x adalah titik tetap tarik-menarik dari fungsi f, maka dapat dimulai dengan titik x1 pada cekungan tarik-menarik x, dan misalkan xn+ 1 = f(xn) untuk n 1, dan barisan {xn}n 1 akan konvergen ke solusi x. Di sini xn adalah aproksimasi atau iterasi ke-n dari x dan xn+1 adalah iterasi berikutnya atau n+1 dari x. Sebagai alternatif, superskrip dalam tanda kurung sering digunakan dalam metode numerik, agar tidak mengganggu subskrip dengan arti lain. (Misalnya, x(n+1) = f(x(n)).) Jika fungsi f terdiferensialkan secara kontinu, syarat yang cukup untuk konvergensi adalah bahwa jari-jari spektral turunan dibatasi secara ketat oleh satu di sekitar titik tetap. Jika kondisi ini berlaku pada titik tetap, maka lingkungan yang cukup kecil (cekungan tarik-menarik) harus ada.

Sistem linier

Dalam kasus sistem persamaan linear, 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 yang asli; dan berdasarkan pengukuran kesalahan dalam hasil (sisa), bentuk "persamaan koreksi" yang proses ini diulang. Meskipun metode ini sederhana untuk diturunkan, diimplementasikan, dan dianalisis, konvergensi hanya dijamin untuk kelas matriks yang terbatas.

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 bekerja dengan membentuk basis dari barisan pangkat matriks yang berurutan dikalikan dengan residual awal (urutan Krylov). Pendekatan ke solusi kemudian dibentuk dengan meminimalkan residu atas subruang yang terbentuk. Metode prototipikal dalam kelas ini adalah metode gradien konjugasi (CG) yang mengasumsikan bahwa matriks sistem {\displaystyle A}A adalah pasti-positif simetris. Untuk simetris (dan mungkin tidak terbatas) {\displaystyle A}Satu bekerja dengan metode residual minimal (MINRES). Dalam kasus matriks non-simetris, metode seperti metode residual minimal umum (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 The Treatise of Chord and Sine dengan presisi tinggi. Metode iteratif awal untuk memecahkan sistem linier muncul dalam surat Gauss kepada seorang siswanya. Dia mengusulkan pemecahan sistem persamaan 4-kali-4 dengan berulang kali memecahkan komponen di mana sisa adalah yang terbesar [rujukan?].

Teori metode iteratif stasioner didirikan dengan kokoh dengan karya D.M. Muda mulai tahun 1950-an. Metode gradien konjugasi juga ditemukan pada 1950-an, dengan pengembangan independen oleh Cornelius Lanczos, Magnus Hestenes dan Eduard Stiefel, tetapi sifat dan penerapannya disalahpahami pada saat itu. Baru pada tahun 1970-an disadari bahwa metode berbasis konjugasi bekerja sangat baik untuk persamaan diferensial parsial, terutama tipe eliptik.

Sumber Artikel: en.wikipedia.org

Selengkapnya

Operation Research and Analysis

Heuristik (ilmu komputer)

Dipublikasikan oleh Siti Nur Rahmawati pada 22 Agustus 2022

Dalam optimasi matematika dan ilmu komputer, heuristik (dari bahasa Yunani "Saya menemukan, menemukan") 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, juga disebut heuristik, adalah 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$ .

Etimologi

Kata "heuristik" mulai digunakan pada awal abad ke-19. Ini dibentuk secara tidak teratur dari kata Yunani heuriskein, yang berarti "menemukan".

Sumber Artikel: en.wikipedia.org

Selengkapnya

Operation Research and Analysis

Metaheuristik

Dipublikasikan oleh Siti Nur Rahmawati pada 22 Agustus 2022

Dalam ilmu komputer dan optimasi matematika, metaheuristik adalah prosedur tingkat tinggi atau heuristik yang dirancang untuk menemukan, menghasilkan, atau memilih heuristik (algoritma pencarian parsial) yang dapat memberikan solusi yang cukup baik untuk masalah optimasi, terutama dengan informasi yang tidak lengkap atau tidak sempurna. atau kapasitas komputasi yang terbatas. Metaheuristik sampel subset dari solusi yang dinyatakan terlalu besar untuk benar-benar dihitung atau dieksplorasi. Metaheuristik dapat membuat asumsi yang relatif sedikit tentang masalah optimasi yang sedang dipecahkan dan mungkin dapat digunakan untuk berbagai masalah.

Dibandingkan dengan algoritma optimasi dan metode iteratif, metaheuristik tidak menjamin bahwa solusi optimal global dapat ditemukan pada beberapa kelas masalah. Banyak metaheuristik menerapkan beberapa bentuk optimasi stokastik, sehingga solusi yang ditemukan bergantung pada himpunan variabel acak yang dihasilkan. Dalam optimasi kombinatorial, dengan mencari lebih dari satu set besar solusi yang layak, metaheuristik sering dapat menemukan solusi yang baik dengan upaya komputasi yang lebih sedikit daripada algoritma optimasi, metode iteratif, atau heuristik sederhana. Dengan demikian, mereka adalah pendekatan yang berguna untuk masalah optimasi. Beberapa buku dan makalah survei telah diterbitkan tentang masalah ini.

Kebanyakan literatur tentang metaheuristik adalah eksperimental di alam, menggambarkan hasil empiris berdasarkan eksperimen komputer dengan algoritma. Tetapi beberapa hasil teoretis formal juga tersedia, seringkali pada konvergensi dan kemungkinan menemukan optimum global. Banyak metode metaheuristik telah diterbitkan dengan klaim kebaruan dan kemanjuran praktis. Sementara bidang ini juga menampilkan penelitian berkualitas tinggi, banyak dari publikasinya memiliki kualitas yang buruk; kekurangan termasuk ketidakjelasan, kurangnya elaborasi konseptual, eksperimen yang buruk, dan ketidaktahuan literatur sebelumnya.

Properti

Ini adalah properti yang menjadi ciri sebagian besar metaheuristik:

Metaheuristik adalah strategi yang memandu proses pencarian.
Tujuannya adalah untuk mengeksplorasi ruang pencarian secara efisien untuk menemukan solusi yang mendekati optimal.
Teknik yang membentuk algoritma metaheuristik berkisar dari prosedur pencarian lokal sederhana hingga proses pembelajaran yang kompleks.
Algoritma metaheuristik adalah perkiraan dan biasanya non-deterministik.
Metaheuristik tidak spesifik masalah.

Klasifikasi

Diagram Euler dari klasifikasi yang berbeda dari metaheuristik.

Ada berbagai macam metaheuristik dan sejumlah properti untuk mengklasifikasikannya.

Pencarian lokal vs. pencarian global

Salah satu pendekatannya adalah dengan mengkarakterisasi jenis strategi pencarian. Salah satu jenis strategi pencarian adalah perbaikan pada algoritma pencarian lokal sederhana. Algoritma pencarian lokal yang terkenal adalah metode hill climbing yang digunakan untuk menemukan lokal optimum. Namun, mendaki bukit tidak menjamin menemukan solusi optimal global.

Banyak ide metaheuristik diusulkan untuk meningkatkan heuristik pencarian lokal untuk menemukan solusi yang lebih baik. Metaheuristik tersebut termasuk simulasi anil, pencarian tabu, pencarian lokal berulang, pencarian lingkungan variabel, dan GRASP. Metaheuristik ini dapat diklasifikasikan sebagai metaheuristik pencarian berbasis lokal atau pencarian global.

Metaheuristik pencarian global lainnya yang tidak berbasis pencarian lokal biasanya adalah metaheuristik berbasis populasi. Metaheuristik tersebut meliputi optimasi koloni semut, komputasi evolusioner, optimasi gerombolan partikel, algoritma genetika, dan algoritma optimasi pengendara

Solusi tunggal vs berbasis populasi

Dimensi klasifikasi lainnya adalah solusi tunggal vs pencarian berbasis populasi. Pendekatan solusi tunggal berfokus pada modifikasi dan peningkatan solusi kandidat tunggal; metaheuristik solusi tunggal termasuk simulasi anil, pencarian lokal berulang, pencarian lingkungan variabel, dan pencarian lokal terpandu. Pendekatan berbasis populasi memelihara dan meningkatkan beberapa solusi kandidat, seringkali menggunakan karakteristik populasi untuk memandu pencarian; metaheuristik berbasis populasi meliputi komputasi evolusioner, algoritme genetika, dan optimasi gerombolan partikel. Kategori lain dari metaheuristik adalah Swarm intelligence yang merupakan perilaku kolektif dari agen yang terdesentralisasi dan terorganisir sendiri dalam suatu populasi atau swarm. Pengoptimalan koloni semut, pengoptimalan kawanan partikel, pengoptimalan kognitif sosial adalah contoh dari kategori ini.

Hibridisasi dan algoritma memetika

Sebuah metaheuristik hibrida adalah salah satu yang menggabungkan metaheuristik dengan pendekatan optimasi lainnya, seperti algoritma dari pemrograman matematika, pemrograman kendala, dan pembelajaran mesin. Kedua komponen metaheuristik hibrida dapat berjalan secara bersamaan dan bertukar informasi untuk memandu pencarian.

Di sisi lain, algoritma Memetic mewakili sinergi pendekatan evolusioner atau berbasis populasi dengan pembelajaran individu yang terpisah atau prosedur perbaikan lokal untuk pencarian masalah.

Contoh algoritme memetika adalah penggunaan algoritme pencarian lokal alih-alih operator mutasi dasar dalam algoritme evolusi.

Metaheuristik paralel

Metaheuristik paralel adalah salah satu yang menggunakan teknik pemrograman paralel untuk menjalankan beberapa pencarian metaheuristik secara paralel; ini dapat berkisar dari skema terdistribusi sederhana hingga pencarian bersamaan yang berinteraksi untuk meningkatkan solusi keseluruhan.

Metaheuristik yang terinspirasi alam dan berbasis metafora

Artikel utama: Kecerdasan kawanan dan Daftar metaheuristik yang terinspirasi metafora

Bidang penelitian yang sangat aktif adalah desain metaheuristik yang diilhami alam. Banyak metaheuristik baru-baru ini, terutama algoritma berbasis komputasi evolusioner, terinspirasi oleh sistem alami. Alam bertindak sebagai sumber konsep, mekanisme dan prinsip untuk merancang sistem komputasi buatan untuk menangani masalah komputasi yang kompleks. Metaheuristik tersebut termasuk simulasi anil, algoritma evolusioner, optimasi koloni semut dan optimasi gerombolan partikel. Sejumlah besar metaheuristik yang terinspirasi metafora baru-baru ini mulai menarik kritik di komunitas riset karena menyembunyikan kurangnya kebaruan mereka di balik metafora yang rumit.

Aplikasi

Metaheuristik digunakan untuk optimasi kombinatorial di mana solusi optimal dicari melalui ruang pencarian diskrit. Contoh masalah adalah masalah salesman keliling di mana ruang pencarian solusi kandidat tumbuh lebih cepat daripada eksponensial saat ukuran masalah meningkat, yang membuat pencarian menyeluruh untuk solusi optimal menjadi tidak layak. Selain itu, masalah kombinatorial multidimensi, termasuk sebagian besar masalah desain di bidang teknik seperti pencarian bentuk dan pencarian perilaku, menderita kutukan dimensi, yang juga membuatnya tidak layak untuk pencarian lengkap atau metode analisis. Metaheuristik juga banyak digunakan untuk penjadwalan jobshop dan masalah pemilihan pekerjaan. Metaheuristik populer untuk masalah kombinatorial termasuk simulasi anil oleh Kirkpatrick et al., algoritma genetika oleh Holland et al., pencarian pencar dan tabu search oleh Glover. Tinjauan literatur tentang optimasi metaheuristik, menyarankan bahwa Fred Glover yang menciptakan kata metaheuristik.

Kerangka Pengoptimalan Metaheuristik (MOFs)

MOF dapat didefinisikan sebagai '' seperangkat alat perangkat lunak yang menyediakan implementasi yang benar dan dapat digunakan kembali dari satu set metaheuristik, dan mekanisme dasar untuk mempercepat implementasi heuristik bawahan mitranya (mungkin termasuk pengkodean solusi dan operator khusus teknik) , yang diperlukan untuk memecahkan contoh masalah tertentu menggunakan teknik yang disediakan''.

Ada banyak alat pengoptimalan kandidat yang dapat dianggap sebagai MOF dari berbagai fitur: Comet, EvA2, evolvica, Evolutionary::Algorithm, GAPlayground, jaga, JCLEC, JGAP, jMetal, n-genes, Open Beagle, Opt4j, ParadisEO/EO , Pisa, Pembuat Jam, FOM, Hypercube, HotFrame, Templar, EasyLocal, iOpt, OptQuest, JDEAL, Toolkit Algoritma Pengoptimalan, HeuristicLab, MAFRA, Localizer, GALIB, DREAM, Discropt, MALLBA, MAGMA, Metaheuristics.jl, UOF dan Perencana Opta.

Kontribusi

Banyak metaheuristik yang berbeda ada dan varian baru terus diusulkan. Beberapa kontribusi paling signifikan di bidang ini adalah:

1952: Robbins dan Monro bekerja pada metode optimasi stokastik.
1954: Barricelli melakukan simulasi pertama dari proses evolusi dan menggunakannya pada masalah optimasi umum.
1963: Rastrigin mengusulkan pencarian acak.
1965: Matyas mengusulkan optimasi acak.
1965: Nelder dan Mead mengusulkan heuristik simpleks, yang ditunjukkan oleh Powell untuk konvergen ke titik non-stasioner pada beberapa masalah.
1965: Ingo Rechenberg menemukan algoritma Strategi Evolusi pertama.
1966: Fogel dkk. mengusulkan pemrograman evolusioner.
1970: Hastings mengusulkan algoritma Metropolis–Hastings.
1970: Cavicchio mengusulkan adaptasi parameter kontrol untuk pengoptimal.
1970: Kernighan dan Lin mengusulkan metode partisi grafik, terkait dengan pencarian mendalam variabel dan pencarian berbasis larangan (tabu).
1975: Holland mengusulkan algoritma genetika.
1977: Glover mengusulkan pencarian pencar.
1978: Mercer dan Sampson mengusulkan metaplan untuk menyetel parameter pengoptimal dengan menggunakan pengoptimal lain.
1980: Smith menjelaskan pemrograman genetik.
1983: Kirkpatrick dkk. mengusulkan simulasi anil.
1986: Glover mengusulkan pencarian tabu, penyebutan pertama istilah metaheuristik.
1989: Moscato mengusulkan algoritma memetika.
1990: Moscato dan Fontanari, dan Dueck dan Scheuer, secara independen mengusulkan aturan pembaruan deterministik untuk simulasi anil yang mempercepat pencarian. Hal ini menyebabkan ambang menerima metaheuristik.
1992: Dorigo memperkenalkan optimasi koloni semut dalam tesis PhD-nya.
1995: Wolpert dan Macready membuktikan teorema tidak ada makan siang gratis.

Sumber Artikel: en.wikipedia.org

Selengkapnya

Operation Engineering and Management

Efisiensi

Dipublikasikan oleh Siti Nur Rahmawati pada 22 Agustus 2022

Efisiensi adalah kemampuan yang sering terukur untuk menghindari pemborosan bahan, energi, tenaga, uang, dan waktu dalam melakukan sesuatu atau dalam menghasilkan hasil yang diinginkan. Dalam arti yang lebih umum, itu adalah kemampuan untuk melakukan sesuatu dengan baik, berhasil, dan tanpa pemborosan. Seperti yang didefinisikan oleh Deborah Stone, efisiensi adalah "dengan demikian bukan tujuan itu sendiri. Ini bukan sesuatu yang kita inginkan untuk kepentingannya sendiri, melainkan karena efisiensi membantu kita mencapai lebih banyak hal yang kita hargai."

Dalam istilah yang lebih matematis atau ilmiah, ini menandakan tingkat kinerja yang menggunakan input paling sedikit untuk mencapai jumlah output tertinggi. Ini sering secara khusus terdiri dari kemampuan aplikasi spesifik upaya untuk menghasilkan hasil tertentu dengan jumlah atau kuantitas minimum pemborosan, biaya, atau upaya yang tidak perlu. Efisiensi mengacu pada input dan output yang sangat berbeda di berbagai bidang dan industri. Pada tahun 2019, Komisi Eropa mengatakan: "Efisiensi sumber daya berarti menggunakan sumber daya bumi yang terbatas secara berkelanjutan sambil meminimalkan dampak terhadap lingkungan. Ini memungkinkan kita untuk menciptakan lebih banyak dengan lebih sedikit dan memberikan nilai lebih besar dengan lebih sedikit input.

Efisiensi dan efektivitas

Efisiensi sangat sering dikacaukan dengan efektivitas. Secara umum, efisiensi adalah konsep yang dapat diukur, secara kuantitatif ditentukan oleh rasio output yang berguna terhadap total input yang berguna. Efektivitas adalah konsep sederhana untuk dapat mencapai hasil yang diinginkan, yang dapat dinyatakan secara kuantitatif tetapi biasanya tidak memerlukan matematika yang lebih rumit daripada penjumlahan. Efisiensi seringkali dapat dinyatakan sebagai persentase dari hasil yang idealnya dapat diharapkan, misalnya jika tidak ada energi yang hilang karena gesekan atau penyebab lain, dalam hal ini 100% bahan bakar atau input lain akan digunakan untuk menghasilkan hasil yang diinginkan. Dalam beberapa kasus, efisiensi dapat diukur secara tidak langsung dengan nilai non-persentase, mis. impuls tertentu.

Cara yang umum tetapi membingungkan untuk membedakan antara efisiensi dan efektivitas adalah pepatah "Efisiensi adalah melakukan sesuatu dengan benar, sedangkan efektivitas adalah melakukan hal yang benar." Pepatah ini secara tidak langsung menekankan bahwa pemilihan tujuan dari suatu proses produksi sama pentingnya dengan kualitas proses itu. Pepatah ini populer dalam bisnis namun mengaburkan pengertian yang lebih umum dari "efektivitas", yang akan/seharusnya menghasilkan mnemonik berikut: "Efisiensi adalah melakukan sesuatu dengan benar; efektivitas adalah menyelesaikan sesuatu." Hal ini memperjelas bahwa efektivitas, misalnya jumlah produksi yang besar, juga dapat dicapai melalui proses yang tidak efisien jika, misalnya, pekerja bersedia atau terbiasa bekerja lebih lama atau dengan upaya fisik yang lebih besar daripada di perusahaan atau negara lain atau jika mereka dapat bekerja lebih lama. terpaksa melakukannya. Demikian pula, sebuah perusahaan dapat mencapai efektivitas, misalnya jumlah produksi yang besar, melalui proses yang tidak efisien jika mampu menggunakan lebih banyak energi per produk, misalnya jika harga energi atau biaya tenaga kerja atau keduanya lebih rendah daripada pesaingnya.

Ketidakefisienan

Inefisiensi adalah tidak adanya efisiensi. Macam-macam inefisiensi antara lain:

Inefisiensi alokasi mengacu pada situasi di mana distribusi sumber daya antara alternatif tidak sesuai dengan selera konsumen (persepsi biaya dan manfaat). Misalnya, sebuah perusahaan mungkin memiliki biaya terendah dalam hal "produktif", tetapi hasilnya mungkin tidak efisien dalam hal alokasi karena biaya "benar" atau sosial melebihi harga yang bersedia dibayar konsumen untuk unit ekstra produk. Ini benar, misalnya, jika perusahaan menghasilkan polusi (lihat juga biaya eksternal). Konsumen akan lebih suka bahwa perusahaan dan pesaingnya menghasilkan lebih sedikit produk dan membebankan harga yang lebih tinggi, untuk menginternalisasi biaya eksternal.
Inefisiensi distributif mengacu pada distribusi pendapatan dan kekayaan yang tidak efisien dalam suatu masyarakat. Penurunan utilitas marjinal kekayaan, secara teori, menunjukkan bahwa distribusi kekayaan yang lebih egaliter lebih efisien daripada distribusi inegalitarian. Inefisiensi distributif sering dikaitkan dengan ketimpangan ekonomi.
Inefisiensi ekonomi mengacu pada situasi di mana "kita bisa melakukan pekerjaan yang lebih baik," yaitu, mencapai tujuan kita dengan biaya lebih rendah. Ini adalah kebalikan dari efisiensi ekonomi. Dalam kasus terakhir, tidak ada cara untuk melakukan pekerjaan yang lebih baik, mengingat sumber daya dan teknologi yang tersedia. Kadang-kadang, jenis efisiensi ekonomi ini disebut sebagai efisiensi Koopman.
Inefisiensi Keynesian dapat didefinisikan sebagai penggunaan sumber daya yang tidak lengkap (tenaga kerja, barang modal, sumber daya alam, dll.) karena permintaan agregat yang tidak memadai. Kami tidak mencapai output potensial, sementara menderita pengangguran siklis. Kita bisa melakukan pekerjaan yang lebih baik jika kita menerapkan pengeluaran defisit atau kebijakan moneter ekspansif.
Inefisiensi pareto adalah situasi di mana satu orang tidak dapat dibuat lebih baik tanpa membuat orang lain menjadi lebih buruk. Dalam praktiknya, kriteria ini sulit diterapkan di dunia yang terus berubah, begitu banyak penekanan ukuran Kaldor-Hicks efisiensi dan inefisiensi: situasi tidak efisien jika seseorang dapat dibuat lebih baik bahkan setelah kompensasi yang dibuat lebih buruk, terlepas dari apakah kompensasi benar-benar terjadi.
Inefisiensi produktif mengatakan bahwa kita dapat menghasilkan output tertentu dengan biaya lebih rendah—atau dapat menghasilkan lebih banyak output dengan biaya tertentu. Misalnya, perusahaan yang tidak efisien akan memiliki biaya operasi yang lebih tinggi dan akan berada pada kerugian kompetitif (atau memiliki keuntungan yang lebih rendah daripada perusahaan lain di pasar). Lihat Sickles and Zelenyuk (2019, Bab 3) untuk diskusi yang lebih luas.
Inefisiensi pasar sumber daya mengacu pada hambatan yang mencegah penyesuaian penuh pasar sumber daya, sehingga sumber daya tidak digunakan atau disalahgunakan. Misalnya, pengangguran struktural dihasilkan dari hambatan mobilitas di pasar tenaga kerja yang mencegah pekerja pindah ke tempat dan pekerjaan di mana ada lowongan pekerjaan. Dengan demikian, pekerja yang menganggur dapat hidup berdampingan dengan lowongan pekerjaan yang tidak terisi.
X-inefisiensi mengacu pada inefisiensi dalam "kotak hitam" produksi, yang menghubungkan input ke output. Jenis inefisiensi ini mengatakan bahwa kita dapat mengatur orang atau proses produksi dengan lebih efektif. Seringkali masalah "moral" atau "kelembaman birokrasi" menyebabkan inefisiensi X.

Inefisiensi produktif, inefisiensi pasar sumber daya, dan inefisiensi X dapat dianalisis menggunakan analisis data envelopment dan metode serupa.

Ekspresi matematika

Efisiensi sering diukur sebagai rasio keluaran yang berguna terhadap masukan total, yang dapat dinyatakan dengan rumus matematika r=P/C, di mana P adalah jumlah keluaran yang berguna ("produk") yang dihasilkan per jumlah C ("biaya" ) dari sumber daya yang dikonsumsi. Ini mungkin sesuai dengan persentase jika produk dan bahan habis pakai dikuantifikasi dalam unit yang kompatibel, dan jika bahan habis pakai diubah menjadi produk melalui proses konservatif. Misalnya, dalam analisis efisiensi konversi energi mesin kalor dalam termodinamika, produk P mungkin merupakan jumlah keluaran kerja yang berguna, sedangkan C yang dapat dikonsumsi adalah jumlah masukan panas suhu tinggi. Karena kekekalan energi, P tidak pernah bisa lebih besar dari C, sehingga efisiensi r tidak pernah lebih besar dari 100% (dan bahkan harus lebih kecil pada suhu yang terbatas).

Dalam ilmu pengetahuan dan teknologi

Dalam fisika

Kerja yang berguna per kuantitas energi, keuntungan mekanik atas keuntungan mekanik ideal, sering dilambangkan dengan huruf kecil Yunani (Eta):

Efisiensi listrik
Efisiensi konversi energi
Efisiensi mekanis
Efisiensi termal, rasio kerja yang dilakukan terhadap energi panas yang dikonsumsi

Penggunaan energi yang efisien, tujuan memaksimalkan efisiensi

- Dalam termodinamika: Efisiensi konversi energi, ukuran kerugian termodinamika hukum kedua

- Efisiensi radiasi, rasio daya terpancar terhadap daya yang diserap pada terminal antena

- Efisiensi volumetrik, dalam desain mesin pembakaran internal untuk RAF

Rasio angkat-ke-tarik
Efisiensi Faraday, elektrolisis
Efisiensi kuantum, ukuran sensitivitas perangkat fotosensitif
Efisiensi kisi, generalisasi pemantulan cermin, diperluas ke kisi difraksi

Dalam ilmu ekonomi

Teknologi peningkatan produktivitas
Efisiensi ekonomi, sejauh mana pemborosan atau fitur lain yang tidak diinginkan dapat dihindari
Efisiensi pasar, sejauh mana pasar tertentu menyerupai pasar ideal yang efisien

Efisiensi Pareto, keadaan tidak mungkin membuat satu individu menjadi lebih baik, tanpa membuat individu lain menjadi lebih buruk
Efisiensi Kaldor-Hicks, versi efisiensi Pareto yang tidak terlalu ketat
Efisiensi alokatif, distribusi barang yang optimal
Upah efisiensi, membayar pekerja lebih dari tarif pasar untuk meningkatkan produktivitas

Efisiensi bisnis, pendapatan relatif terhadap pengeluaran, dll.
Gerakan Efisiensi, Era Progresif (1890–1932), menganjurkan efisiensi dalam ekonomi, masyarakat, dan pemerintah

Dalam ilmu lain

Dalam komputasi:

Efisiensi algoritmik, mengoptimalkan kecepatan dan kebutuhan memori program komputer.
Efisiensi penyimpanan, efektivitas penyimpanan data komputer
Faktor efisiensi, dalam komunikasi data

Efisiensi (statistik), ukuran keinginan estimator
Efisiensi material, membandingkan kebutuhan material antara proyek konstruksi atau proses fisik
Efisiensi administratif, mengukur transparansi dalam otoritas publik dan kesederhanaan aturan dan prosedur untuk warga negara dan bisnis
Dalam biologi:

Efisiensi fotosintesis
Efisiensi ekologis

Sumber Artikel: en.wikipedia.org

Selengkapnya