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 Research and Analysis

Wilayah yang Layak

Dipublikasikan oleh Siti Nur Rahmawati pada 22 Agustus 2022

Dalam optimasi matematis, daerah fisibel, himpunan fisibel, ruang pencarian, atau ruang solusi adalah himpunan semua titik yang mungkin (kumpulan nilai dari variabel pilihan) dari masalah optimasi yang memenuhi kendala masalah, yang berpotensi termasuk pertidaksamaan, persamaan, dan pertidaksamaan. batasan bilangan bulat. Ini adalah kumpulan kandidat solusi awal untuk masalah, sebelum kumpulan kandidat dipersempit.

Misalnya, pertimbangkan masalah meminimalkan fungsi $x^{2}+y^{4}$ sehubungan dengan variabel $x$ dan $y,$ , tunduk pada $1\leq x\leq 10$ dan $5\leq y\leq 12.\,$ Di sini himpunan layak adalah himpunan pasangan (x,y) yang nilai x paling sedikit 1 dan paling banyak 10 dan nilai y paling sedikit 5 dan paling banyak 12. Himpunan masalah yang layak terpisah dari fungsi tujuan, yang menyatakan kriteria yang akan dioptimalkan dan yang dalam contoh di atas adalah $x^{2}+y^{4}.$

Dalam banyak masalah, himpunan layak mencerminkan kendala bahwa satu atau lebih variabel harus non-negatif. Dalam masalah pemrograman bilangan bulat murni, himpunan layak adalah himpunan bilangan bulat (atau beberapa subset daripadanya). Dalam masalah pemrograman linier, himpunan layak adalah politop cembung: wilayah dalam ruang multidimensi yang batas-batasnya dibentuk oleh hyperplanes dan sudut-sudutnya adalah simpul.

Kepuasan kendala adalah proses menemukan titik di wilayah yang layak.

Daerah fisibel tertutup dari masalah program linier dengan tiga variabel adalah polihedron cembung.

Himpunan layak cembung

Dalam masalah pemrograman linier, serangkaian kendala linier menghasilkan wilayah layak cembung dari nilai-nilai yang mungkin untuk variabel-variabel tersebut. Dalam kasus dua variabel daerah ini berbentuk poligon sederhana cembung.

Himpunan layak cembung adalah himpunan di mana ruas garis yang menghubungkan dua titik layak hanya melalui titik layak lainnya, dan tidak melalui sembarang titik di luar himpunan layak. Himpunan layak cembung muncul dalam banyak jenis masalah, termasuk masalah pemrograman linier, dan mereka sangat menarik karena, jika masalah memiliki fungsi tujuan cembung yang dimaksimalkan, umumnya akan lebih mudah diselesaikan dengan adanya konveks. himpunan layak dan setiap optimum lokal juga akan menjadi optimum global.

Tidak ada set yang layak

Jika kendala dari masalah optimasi saling bertentangan, tidak ada titik yang memenuhi semua kendala dan dengan demikian wilayah yang layak adalah himpunan nol. Dalam hal ini masalah tidak memiliki solusi dan dikatakan tidak layak.

Himpunan layak terbatas (atas) dan himpunan layak tak terbatas (bawah). Set di bagian bawah berlanjut selamanya ke arah kanan.

Himpunan layak terbatas dan tidak terbatas

Himpunan layak terbatas (atas) dan himpunan layak tak terbatas (bawah). Set di bagian bawah berlanjut selamanya ke arah kanan.

Himpunan yang layak dapat dibatasi atau tidak dibatasi. Sebagai contoh, himpunan fisibel yang didefinisikan oleh himpunan kendala {x ≥ 0, y ≥ 0} tidak terbatas karena di beberapa arah tidak ada batasan seberapa jauh seseorang dapat pergi dan masih berada di daerah fisibel. Sebaliknya, himpunan layak yang dibentuk oleh himpunan kendala {x ≥ 0, y ≥ 0, x + 2y ≤ 4} dibatasi karena luasnya pergerakan ke segala arah dibatasi oleh kendala.

Dalam masalah pemrograman linier dengan n variabel, kondisi yang diperlukan tetapi tidak mencukupi untuk himpunan layak untuk dibatasi adalah bahwa jumlah kendala paling sedikit n + 1 (seperti yang diilustrasikan oleh contoh di atas).

Jika himpunan layak tidak terbatas, mungkin ada atau mungkin tidak optimal, tergantung pada spesifikasi fungsi tujuan. Sebagai contoh, jika daerah fisibel didefinisikan oleh himpunan kendala {x ≥ 0, y ≥ 0}, maka masalah memaksimalkan x + y tidak optimal karena setiap kandidat solusi dapat ditingkatkan dengan meningkatkan x atau y; namun jika masalahnya adalah untuk meminimalkan x + y, maka ada optimum (khususnya pada (x, y) = (0, 0)).

Solusi kandidat

Dalam optimasi dan cabang matematika lainnya, dan dalam algoritma pencarian (topik dalam ilmu komputer), solusi kandidat adalah anggota dari himpunan solusi yang mungkin di wilayah yang layak dari masalah yang diberikan. Solusi kandidat tidak harus menjadi solusi yang mungkin atau masuk akal untuk masalah—hanya dalam himpunan yang memenuhi semua kendala; yaitu, dalam himpunan solusi yang layak. Algoritma untuk menyelesaikan berbagai jenis masalah optimasi sering mempersempit himpunan solusi kandidat ke subset dari solusi layak, yang poinnya tetap sebagai solusi kandidat sementara solusi layak lainnya selanjutnya dikeluarkan sebagai kandidat.

Ruang dari semua solusi kandidat, sebelum titik fisibel dikeluarkan, disebut daerah fisibel, himpunan fisibel, ruang pencarian, atau ruang solusi. Ini adalah himpunan semua solusi yang mungkin yang memenuhi kendala masalah. Kepuasan kendala adalah proses menemukan titik dalam himpunan yang layak.

Algoritma genetika

Dalam kasus algoritma genetik thm, solusi kandidat adalah individu dalam populasi yang dikembangkan oleh algoritma.

Kalkulus

Dalam kalkulus, solusi optimal dicari dengan menggunakan uji turunan pertama: turunan pertama dari fungsi yang dioptimalkan disamakan dengan nol, dan setiap nilai dari variabel pilihan yang memenuhi persamaan ini dipandang sebagai solusi kandidat (sementara yang tidak dikesampingkan sebagai calon). Ada beberapa cara di mana solusi kandidat mungkin bukan solusi yang sebenarnya. Pertama, mungkin memberikan minimum ketika maksimum sedang dicari (atau sebaliknya), dan kedua, mungkin tidak memberikan minimum atau maksimum melainkan titik pelana atau titik belok, di mana jeda sementara dalam kenaikan lokal. atau jatuhnya fungsi terjadi. Solusi kandidat tersebut mungkin dapat dikesampingkan dengan menggunakan uji turunan kedua, yang kepuasannya cukup untuk solusi kandidat setidaknya optimal secara lokal. Ketiga, solusi kandidat mungkin optimum lokal tetapi bukan optimum global.

Dalam mengambil antiturunan dari monomial bentuk $x^{n},$ solusi kandidat menggunakan rumus kuadratur Cavalieri adalah ${\tfrac {1}{n+1}}x^{n+1}+C.$ Kandidat solusi ini sebenarnya benar kecuali jika $n=-1.$

Pemrograman linier

Serangkaian kendala pemrograman linier pada dua variabel menghasilkan wilayah nilai yang mungkin untuk variabel tersebut. Masalah dua variabel yang dapat diselesaikan akan memiliki wilayah layak dalam bentuk poligon sederhana cembung jika dibatasi. Dalam algoritma yang menguji titik-titik yang layak secara berurutan, setiap titik yang diuji pada gilirannya merupakan solusi kandidat.

Dalam metode simpleks untuk menyelesaikan masalah program linier, sebuah simpul dari politop yang layak dipilih sebagai kandidat solusi awal dan diuji optimalitasnya; jika ditolak sebagai optimal, simpul yang berdekatan dianggap sebagai kandidat solusi berikutnya. Proses ini dilanjutkan sampai solusi kandidat ditemukan menjadi yang optimal.

Sumber Artikel: en.wikipedia.org

Selengkapnya