Matematika komputasional 

Matematika komputasi mencakup studi matematika dalam matematika serta bidang ilmiah di mana ilmu komputer memainkan peran sentral dan penting, menekankan algoritma, metode numerik, dan perhitungan simbolik.

Matematika komputasi terapan adalah penggunaan matematika untuk mengaktifkan dan meningkatkan perhitungan komputasi dalam matematika terapan. Matematika Komputasi juga dapat merujuk pada penggunaan komputer dalam matematika itu sendiri. Hal ini termasuk penggunaan komputer untuk perhitungan matematis (aljabar komputer), studi tentang apa yang dapat (dan tidak dapat) dikomputerisasi dalam matematika (metode efektif), perhitungan apa yang dapat dilakukan dengan teknologi saat ini (Teori Kompleksitas), dan demonstrasi apa yang diperlukan. mungkin dilakukan. diterima. dilakukan di komputer (tes asisten).

Bidang matematika komputasi

Matematika komputasi, sebagai cabang yang berkembang dari matematika terapan pada awal 1950-an, melibatkan beragam aspek yang mencakup ilmu komputasi atau komputasi ilmiah, yang mencakup pemecahan masalah matematika melalui simulasi komputer daripada metode analitik matematika terapan.

Disiplin ini mencakup penerapan metode numerik seperti aljabar linier numerik dan solusi numerik persamaan diferensial parsial, serta metode stokastik seperti metode Monte Carlo untuk mengatasi representasi ketidakpastian dalam konteks komputasi ilmiah.

Matematika komputasi juga mencakup analisis numerik dan teori metode numerik, kompleksitas komputasi, aljabar komputer, dan sistem aljabar komputer. Selain itu, penelitian berbantuan komputer diterapkan dalam berbagai bidang matematika, seperti logika, matematika diskrit, kombinatorik, teori bilangan, dan topologi aljabar komputasi.

Aspek kriptografi dan keamanan komputer, termasuk pengujian primalitas, faktorisasi, kurva eliptik, dan matematika blockchain, juga menjadi bagian dari matematika komputasi. Disiplin ini juga merambah ke linguistik komputasi, geometri aljabar komputasi, teori grup komputasi, geometri komputasi, teori bilangan komputasi, topologi komputasi, statistik komputasi, teori informasi algoritma, teori permainan algoritma, dan ekonomi matematika yang melibatkan penerapan matematika dalam ekonomi, keuangan, dan sebagian akuntansi. Ini juga mencakup eksplorasi matematika eksperimental.

Disadur dari : en.wikipedia.org

Feasible Region

Dalam optimasi matematis, wilayah, himpunan, ruang pencarian, atau ruang solusi yang layak adalah himpunan semua titik yang mungkin (kumpulan nilai dari variabel yang dipilih) dari suatu masalah optimasi yang memenuhi batasan masalah tersebut. , yang mungkin mengandung kesenjangan, persamaan dan ketidaksetaraan. pembatasan bilangan bulat. Ini adalah rangkaian solusi pertama yang mungkin untuk mengatasi masalah tersebut sebelum mempersempit kelompok kandidat.

Misalnya, pertimbangkan masalah meminimalkan fungsi sehubungan dengan variabel dan , tunduk pada dan 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

Dalam banyak permasalahan, himpunan layak mencerminkan batasan bahwa satu atau lebih variabel tidak boleh negatif. Untuk permasalahan pemrograman yang hanya menggunakan bilangan bulat, himpunan bilangan bulat (atau bagiannya) adalah himpunan yang diperbolehkan. Dalam permasalahan program linier, himpunan layak adalah politop cembung: wilayah ruang multidimensi yang batasnya dibentuk oleh bidang hiper dan simpulnya 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 yang ruas garis yang menghubungkan dua titik layak hanya melalui titik layak lainnya dan tidak melalui suatu titik di luar himpunan layak tersebut. Himpunan layak cembung muncul dalam banyak jenis masalah, termasuk masalah program linier, dan sangat menarik karena masalah dengan fungsi tujuan konveks yang dimaksimalkan umumnya lebih mudah diselesaikan jika ada solusi cembung. set yang diizinkan, dan setiap maksimum lokal juga merupakan maksimum 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 dapat diwujudkan bisa terbatas atau tidak terbatas. Misalnya, himpunan nilai realisasi yang ditentukan oleh himpunan batasan {x ≥ 0, y ≥ 0} tidak terhingga karena tidak ada batasan jarak yang dapat ditempuh dalam arah tertentu selama berada dalam rentang nilai realisasi tetap. Sebaliknya, himpunan kemungkinan yang dibentuk oleh himpunan batasan {x ≥ 0, y ≥ 0, x + 2y ≤ 4} adalah terbatas karena amplitudo pergerakan ke segala arah dibatasi oleh batasan tersebut.

Untuk masalah program linier dengan n variabel, kondisi yang diperlukan tetapi tidak cukup untuk membatasi himpunan kemungkinan adalah jumlah batasan paling sedikit n + 1 (seperti yang ditunjukkan pada contoh di atas).

Ketika himpunan kemungkinan tidak terbatas, optimalitas mungkin terjadi atau tidak tergantung pada spesifikasi fungsi tujuan.Misalnya, jika wilayah layak ditentukan oleh himpunan batasan {x ≥ 0, y ≥ 0}, maka permasalahan pemaksimalan x + y adalah suboptimal karena setiap solusi yang mungkin dapat diperbaiki dengan meningkatkan x atau y; Namun jika permasalahannya meminimalkan x + y, maka terdapat permasalahan optimal (terutama pada (x, y) = (0, 0)).

Solusi kandidat

Dalam optimasi dan cabang matematika lainnya, serta dalam algoritma pencarian (cabang ilmu komputer), solusi kandidat adalah anggota dari himpunan solusi yang mungkin dalam domain yang mungkin dari suatu masalah tertentu. Solusi kandidat tidak harus berupa solusi yang mungkin atau masuk akal terhadap suatu masalah, namun hanya solusi yang memenuhi semua batasan; yaitu, dalam serangkaian solusi yang mungkin. Algoritma untuk menyelesaikan berbagai jenis masalah optimasi sering kali mereduksi himpunankemungkinan solusi menjadi subkumpulan solusi layak yang poin-poinnya tetap menjadi solusi layak, sementara solusi lain yang mungkin kemudian dikeluarkan sebagai kandidat.

Ruang semua kandidat solusi sebelum mengecualikan titik layak disebut wilayah layak, himpunan layak, ruang pencarian, atau ruang solusi. Ini adalah himpunan semua solusi yang mungkin yang memenuhi kondisi batas masalah. Kepuasan Kendala adalah proses menemukan titik-titik dalam suatu himpunan yang mungkin.

Algoritma genetika

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

Kalkulus

Dalam kalkulus, pencarian solusi optimal dilakukan dengan menggunakan uji turunan pertama: turunan pertama dari fungsi yang dioptimalkan ditetapkan sama dengan nol, dan nilai apa pun dari variabel terpilih yang memenuhi persamaan ini diperlakukan sebagai kandidat solusi (sementara mereka yang tidak dikecualikan dari daftar peringkat). Solusi potensial mungkin bukan solusi aktual dalam beberapa hal. Pertama, ini mungkin merupakan titik terendah ketika bertujuan untuk mencapai titik tertinggi (atau sebaliknya), dan kedua, mungkin tidak memberikan titik terendah atau tertinggi pada, melainkan sebuah pelana atau titik balik ketika ada jeda sementara dalam pertumbuhan lokal. . Jika tidak, fungsinya akan hilang. Solusi kandidat tersebut dapat dikecualikan dengan uji turunan kedua, yang pemenuhannya cukup untuk membuat solusi kandidat setidaknya optimal secara lokal.Ketiga, solusi potensial mungkin optimal secara lokal namun tidak optimal secara global.

Dalam mengambil antiturunan dari monomial bentuk  solusi kandidat menggunakan rumus kuadratur Cavalieri adalah Kandidat solusi ini sebenarnya benar kecuali jika

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 penyelesaian masalah program linier, sebuah simpul dari politop yang layak dipilih sebagai kandidat solusi awal dan diuji optimalitasnya; Jika ditolak sebagai titik optimal, simpul-simpul tetangga dianggap sebagai kandidat solusi berikutnya. Proses ini berlanjut hingga solusi yang diusulkan dianggap optimal.

Disadur dari: en.wikipedia.org

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 dimaksudkan untuk mendekati jarak optimal sebenarnya  ke simpul tujuan dalam grafik berarah  berisi  total simpul atau simpul berlabel  "diterima" berarti secara kasar bahwa heuristik meremehkan biaya untuk tujuan atau secara formal bahwa untuk semua di mana 

Jika heuristik tidak dapat diterima, heuristik mungkin tidak akan pernah menemukan tujuannya, baik dengan berakhir di jalan buntu grafik  atau dengan melompat-lompat di antara dua node dan dengan .

Disadur dari : en.wikipedia.org

Metaheuristik

Metaheuristik adalah prosedur tingkat tinggi atau heuristik dalam ilmu komputer dan optimasi matematika yang digunakan untuk menemukan, menghasilkan, atau memilih heuristik yang dapat memberikan solusi yang cukup baik terhadap masalah optimasi. Hal ini sangat berguna ketika informasi tersedia sebagian atau tidak lengkap atau daya komputasi terbatas.

Metaheuristik bekerja dengan sampel dari subkumpulan solusi yang terlalu besar untuk dihitung atau diperiksa sepenuhnya. Meskipun tidak menjamin solusi optimal secara global, metaheuristik seringkali dapat menemukan solusi yang baik dengan upaya komputasi yang lebih sedikit dibandingkan algoritma optimasi, metode iteratif, atau heuristik sederhana. Sebagian besar literatur dan penelitian di bidang ini bersifat eksperimental dan menggunakan eksperimen komputer untuk mengevaluasi kinerja algoritma.Meskipun banyak metode metaheuristik yang mengklaim kebaruan dan efektivitas praktis, banyak literatur juga memiliki kekurangan, seperti: B. Ketidakjelasan, kurangnya pengembangan konseptual, eksperimen yang buruk, dan kurangnya pemahaman terhadap literatur sebelumnya.

Properti

Metaheuristik mencirikan sejumlah properti khas yang membentuk identitasnya. Pertama, metaheuristik adalah strategi yang mengarahkan proses pencarian, bertujuan untuk menjelajahi ruang pencarian dengan efisien guna menemukan solusi yang mendekati optimal. Kedua, teknik yang membentuk algoritma metaheuristik dapat bervariasi dari prosedur pencarian lokal yang sederhana hingga proses pembelajaran yang kompleks. Ketiga, algoritma metaheuristik bersifat perkiraan dan biasanya non-deterministik, menunjukkan bahwa solusi yang dihasilkan tidak selalu sama dalam setiap percobaan. Terakhir, metaheuristik tidak spesifik terhadap suatu masalah tertentu, menjadikannya dapat diadaptasi untuk berbagai jenis masalah optimasi. Dengan kombinasi properti ini, metaheuristik menjadi pendekatan yang fleksibel dan kuat untuk menangani masalah optimasi yang kompleks.

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 dengan meningkatkan algoritma pencarian lokal sederhana. Algoritma pencarian lokal yang terkenal adalah metode pendakian bukit, yang digunakan untuk mencari nilai maksimum lokal. Namun, mendaki gunung bukanlah jaminan menemukan solusi optimal secara global.

Banyak ide metaheuristik telah diajukan untuk meningkatkan heuristik pencarian lokal dan menemukan solusi yang lebih baik.Metaheuristik ini mencakup simulasi anil, pencarian tabu, pencarian lokal berulang, pencarian lingkungan variabel, dan GRASP. Metaheuristik ini dapat diklasifikasikan sebagai metaheuristik pencarian lokal atau metaheuristik pencarian global.Metaheuristik lain untuk penelusuran global yang tidak didasarkan pada penelusuran lokal biasanya adalah metaheuristik berbasis populasi. Metaheuristik tersebut meliputi optimasi koloni semut, perhitungan evolusi, optimasi kawanan partikel, algoritma genetika, dan algoritma optimasi pengendara.

Solusi tunggal vs berbasis populasi

Dimensi klasifikasi lainnya adalah solusi tunggal versus pencarian populasi. Pendekatan solusi tunggal berfokus pada perubahan dan peningkatan solusi tunggal. Metaheuristik solusi tunggal mencakup simulasi anil, pencarian lokal berulang, pencarian lingkungan variabel, dan pencarian lokal terpandu. Pendekatan berbasis populasi memupuk dan menyempurnakan banyak solusi potensial, sering kali menggunakan karakteristik populasi untuk memandu pencarian. Metaheuristik populasimencakup perhitungan evolusi, algoritma genetika, dan optimasi kawanan partikel. Kategori metaheuristik lainnya adalah kecerdasan gerombolan, yang merupakan perilaku kolektif dari agen-agen yang terdesentralisasi dan terorganisir sendiri dalam suatu populasi atau kawanan. Contoh kategori ini mencakup optimasi koloni semut, optimasi kawanan partikel, dan optimasi kognitif sosial.

Hibridisasi dan algoritma matematika

Metaheuristik hibrid menggabungkan metaheuristik dengan pendekatan pengoptimalan lainnya, seperti algoritma pemrograman matematika, pemrograman kendala, dan pembelajaran mesin. Kedua elemen metaheuristik hybrid dapat bekerja secara bersamaan dan bertukar informasi untuk memandu pencarian.

Di sisi lain, algoritma memetika mewakili sinergi pendekatan evolusioner atau demografis dengan pembelajaran individu yang terpisah atau metode perbaikan lokal untuk menemukan masalah.Contoh algoritma memetika adalah penggunaan algoritma pencarian lokal sebagai pengganti operator mutasi dasar dalam algoritma evolusi.

Metaheuristik paralel

Metaheuristik paralel adalah metaheuristik yang menggunakan teknik pemrograman paralel untuk melakukan beberapa pencarian metaheuristik secara paralel; Hal ini dapat mencakup pola pencarian terdistribusi atau bersamaan yang bekerja sama untuk meningkatkan solusi keseluruhan.

Metaheuristik yang terinspirasi alam dan berbasis metafora

Bidang penelitian yang sangat aktif adalah desain metaheuristik yang terinspirasi dari alam. Banyak metaheuristik modern, terutama algoritma yang didasarkan pada komputasi evolusioner, terinspirasi oleh sistem alam. Alam adalah sumber konsep, mekanisme, dan prinsip desain sistem komputasi buatan untuk memecahkan masalah komputasi yang kompleks. Metaheuristik ini mencakup simulasi anil, algoritma evolusi, optimasi koloni semut, dan optimasi kawanan partikel. Banyak metaheuristik yang terinspirasi olehMetafora baru-baru ini dikritik oleh komunitas riset karena menyembunyikan kurangnya kebaruan di balik metafora yang kompleks.

Aplikasi

Metaheuristik digunakan untuk optimasi kombinatorial, yang mencari solusi optimal dalam ruang pencarian diskrit. Contoh masalahnya adalah masalah travelling salesman, dimana ruang pencarian untuk solusi potensial tumbuh lebih cepat daripada eksponensial seiring dengan bertambahnya ukuran masalah, sehingga pencarian komprehensif untuk solusi optimal menjadi tidak mungkin. Selain itu, masalah kombinatorial berdimensi tinggi, termasuk sebagian besar masalah desain teknis seperti pencarian bentuk dan pencarian perilaku, mengalami kutukan dimensi, yang juga membuatnya tidak dapat digunakan untuk metode pencarian atau analisis yang komprehensif. Metaheuristik juga banyak digunakan dalam masalah penjadwalan tugas dan seleksi. Salah satu metaheuristik yang populer untuk masalah kombinatorial adalah Simulated Annealing oleh Kirkpatrick et al., algoritma genetika Holland et al., pencarian terdistribusi dan pencarian tabu dari Glover. Tinjauan literatur tentang optimasi metaheuristik menunjukkan bahwa Fred Glover menciptakan kata metaheuristik.

Kerangka Pengoptimalan Metaheuristik (MOFs)

MOF dapat didefinisikan sebagai “seperangkat perangkat lunak yang menyediakan implementasi yang benar dan dapat digunakan kembali dari serangkaian metaheuristik dan mekanisme yang mendasarinya untuk mempercepat implementasi subheuristik yang setara (mungkin termasuk pengkodean solusi dan teknik operator khusus) yang digunakan untuk memecahkan suatu masalah. diperlukan.”, misalnya penerapan konkrit dari teknik yang dimaksudkan.

Ada banyak alat pengoptimalan potensial yang dapat dianggap MOF dengan fungsi berbeda: Comet, EvA2, evolvica, Evolutionary::Algorithm, GAPlayground,guard, JCLEC, JGAP, jMetal, n-genes, Open Beagle, Opt4j, ParadisEO/EO , Pisa, Pembuat Jam, FOM, Hypercube, HotFrame, Templar, EasyLocal, iOpt, OptQuest, JDEAL, Toolkit Algoritma Optimasi, HeuristicLab, MAFRA, Localizer, GALIB, DREAM, Discropt, MALLBA, MAGMA, Metaheuristics.jl, UOF dan Opta Planner.

Kontribusi

Seiring berjalannya waktu, dunia metaheuristik telah menyaksikan sejumlah kontribusi signifikan yang membentuk fondasi pendekatan pencarian dan optimasi ini. Sejak tahun 1950-an hingga 1990-an, berbagai tokoh dan peneliti telah mengenalkan metode-metode yang inovatif dan beragam. Robbins dan Monro membuka jalannya dengan metode optimasi stokastik pada tahun 1952, disusul dengan simulasi evolusi oleh Barricelli pada tahun 1954. Rastrigin memperkenalkan konsep pencarian acak pada tahun 1963, sementara Nelder dan Mead menciptakan heuristik simpleks pada tahun 1965. Era ini juga menyaksikan munculnya algoritma genetika oleh Holland pada tahun 1975 dan konsep pencarian tabu oleh Glover pada tahun 1986. Inovasi terus berlanjut dengan penemuan algoritma memetika oleh Moscato pada tahun 1989, serta kontribusi penting lainnya, termasuk optimasi koloni semut oleh Dorigo pada tahun 1992. Selanjutnya, teorema "tidak ada makan siang gratis" yang dibuktikan oleh Wolpert dan Macready pada tahun 1995 memberikan wawasan mendalam tentang batasan metaheuristik. Inilah perjalanan penuh inovasi dan penemuan yang membangun dasar bagi fleksibilitas dan efektivitas pendekatan metaheuristik dalam menangani berbagai masalah optimasi.

Disadur dari: en.wikipedia.org

Alokasi Sumberdaya

Dalam ilmu ekonomi, alokasi sumber daya adalah penentuan alokasi sumber daya yang ada untuk berbagai tujuan. Pada tingkat makroekonomi, alokasi sumber daya dapat dilakukan melalui pasar atau perencanaan. Dalam konteks manajemen proyek, alokasi sumber daya adalah perencanaan kegiatan dan sumber daya yang diperlukan untuk suatu proyek, dengan mempertimbangkan ketersediaan sumber daya dan waktu proyek.

Ekonomi

Di bidang ekonomi, bidang keuangan publik berkaitan dengan tiga bidang utama: stabilisasi makroekonomi, distribusi pendapatan dan kekayaan, dan alokasi sumber daya. Sebagian besar studi alokasi sumber daya dikhususkan untuk menemukan kondisi di mana mekanisme alokasi sumber daya tertentu menghasilkan hasil yang efisien Pareto, di mana tidak ada pihak yang dapat memperbaiki situasi tanpa merugikan pihak lain.

Perencanaan strategis

Dalam perencanaan strategis, alokasi sumber daya adalah rencana penggunaan sumber daya yang tersedia, seperti sumber daya manusia, terutama dalam waktu dekat, untuk mencapai tujuan di masa depan. Ini adalah proses mengalokasikan sumber daya yang langka ke berbagai proyek atau unit bisnis.Ada berbagai pendekatan untuk menyelesaikan masalah alokasi sumber daya, misalnya alokasi sumber daya dapat dilakukan dengan pendekatan manual, pendekatan algoritmik (lihat di bawah), atau kombinasi keduanya.

Mungkin terdapat mekanisme kontinjensi, seperti pemeringkatan prioritas elemen-elemen yang tidak termasuk dalam rencana, yang menunjukkan elemen mana yang harus didanai jika diperlukan lebih banyak sumber daya, dan peringkat prioritas beberapa elemen yang termasuk dalam rencana, yang menunjukkan elemen mana, jika ada, harus dikorbankan Pembiayaan penuh diperlukan. harus dikurangi.

Algoritma

Alokasi sumber daya dapat diputuskan menggunakan program komputer yang diterapkan pada domain tertentu untuk mendistribusikan sumber daya secara otomatis dan dinamis kepada peminta.Hal ini sangat umum terjadi pada perangkat elektronik yang digunakan untuk penerusan dan komunikasi. Misalnya, alokasi saluran dalam komunikasi nirkabel dapat ditentukan oleh stasiun pemancar dasar dengan menggunakan algoritma yang tepat.

Kelas sumber daya di mana pelamar menawar sumber daya terbaik berdasarkan saldo "uang" mereka, seperti dalam model bisnis lelang online. Sebuah artikel tentang alokasi slot CPUmembandingkan algoritma lelang dengan penjadwalan pembagian proporsional.

Disadur dari : en.wikipedia.org

Metode optimasi stokastik

Pengendalian proses statistik (SPC) atau pengendalian kualitas statistik (SQC) adalah penerapan metode statistik untuk memantau dan mengendalikan kualitas suatu proses produksi. Hal ini untuk memastikan proses berjalan efisien dan menghasilkan produk yang memenuhi spesifikasi dan memiliki lebih sedikit limbah atau cacat. SPC dapat diterapkan pada berbagai proses dimana hasil dari “produk yang sesuai” (produk yang memenuhi spesifikasi) dapat diukur. Alat utama yang digunakan diSPC meliputi diagram proses, diagram kendali, fokus pada perbaikan berkelanjutan, dan desain eksperimen.

Contoh proses yang menerapkan SPC adalah lini produksi di bidang manufaktur.SPC harus diimplementasikan dalam dua tahap: tahap pertama adalah pembentukan awal proses dan tahap kedua adalah penggunaan proses produksi secara teratur. Pada fase kedua, keputusan harus dibuat mengenai periode pengujian, tergantung pada perubahan kondisi 5M&E (manusia, mesin, material, metode, pergerakan, lingkungan) dan tingkat keausan suku cadang yang digunakan dalam proses.

Manufaktur (suku cadang mesin, templat dan aksesori).Keuntungan SPC dibandingkan dengan metode pengendalian mutu lainnya seperti “inspeksi” adalah bahwa metode ini berfokus pada deteksi dini dan pencegahan masalah dibandingkan memperbaikinya setelah masalah terjadi. Selain mengurangi pemborosan, SPC juga dapat menghasilkan pengurangan waktu yang dibutuhkan untuk menghasilkan suatu produk. SPC mengurangi kemungkinan produk akhir perlu dikerjakan ulang atau dibuang.

Metode untuk fungsi stokastik

Data masukan acak sebagian muncul di berbagai bidang seperti estimasi dan kontrol waktu nyata, optimasi berbasis simulasi di mana simulasi Monte Carlo dilakukan sebagai perkiraan sistem nyata, dan masalah di mana kesalahan eksperimental (acak) terjadi dalam pengukuran kriteria. Dalam kasus seperti itu, mengetahui bahwa nilai fungsi terkontaminasi oleh "kebisingan" acak secara alami mengarah pada algoritma yang menggunakan alat inferensi statistik untuk memperkirakan nilai "sebenarnya" dari fungsi dan/atau keputusan optimal secara statistik tentang langkah selanjutnya yang harus dipenuhi. Metode di 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, meskipun kumpulan data terdiri dari pengukuran yang tepat, beberapa metode memperkenalkan keacakan ke dalam proses pencarian untuk mempercepat kemajuan. Keacakan ini juga dapat membuat metode ini kurang rentan terhadap kesalahan pemodelan. Selain itu, keacakan yang disuntikkan dapat menyebabkan metode keluar dari optimal lokal dan akhirnya mendekati optimal global. Faktanya, prinsip pengacakan ini dikenal sebagai cara sederhana dan efektif untuk mendapatkan algoritmayang bekerja hampir secara seragam pada banyak kumpulan data dan untuk berbagai masalah. Jenis metode optimasi stokastik 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),
• 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. Fred W. Glover berpendapat bahwa ketergantungan pada elemen acak dapat menghambat pengembangan komponen deterministik yang lebih baik dan lebih cerdas. Cara penyajian hasil algoritma optimasi stokastik (misalnya rata-rata atau bahkan N run terbaik tanpa menyebutkan variasi juga dapat menghasilkan bias positif terhadap keacakan.

Disadur dari: en.wikipedia.org