Maximum dan Minimum

Dalam analisis matematis, maksimum dan minimum suatu fungsi mengacu pada nilai terbesar dan terkecil yang dapat diambil oleh fungsi tersebut. Nilai-nilai ini, yang biasa disebut sebagai nilai ekstrem, dapat didefinisikan dalam dua konteks: pertama, dalam rentang tertentu, yang dikenal sebagai nilai ekstrem lokal atau relatif, dan kedua, dalam seluruh rentang fungsi, yang dikenal sebagai nilai ekstrem global atau absolut. Konsep ini diperkenalkan dan dikembangkan oleh ahli matematika awal, dengan Pierre deFermat menjadi salah satu orang pertama yang mengusulkan teknik umum dan cukup untuk mencari nilai maksimum dan minimum dalam konteks fungsi matematika.

Dalam teori himpunan, maksimum dan minimum suatu himpunan mengacu pada elemen terbesar dan terkecil dari himpunan tersebut. Perlu diperhatikan bahwa himpunan tak hingga, seperti himpunan bilangan real, tidak memiliki nilai minimum dan maksimum karena tidak ada elemen yang membatasi nilai terbesar atau terkecil.Dalam statistika, terdapat konsep terkait yang disebut maksimum dan minimum sampling, yang mengacu pada nilai terbesar dan terkecil dalam suatu sampel data. Sebagai bagian integral dari analisis statistik, pemahaman maksimum dan minimum sangat penting untuk menilai distribusi data dan tren umum dalam suatu populasi.

Mencari Nilai Minimum dan Maximum

Menemukan maxima dan minima global adalah tujuan optimasi matematis. Jika suatu fungsi kontinu dalam interval tertutup, maka menurut teorema nilai ekstrim terdapat maksimum global dan minimum global. Selain itu, maksimum (atau minimum) global harus merupakan maksimum (atau minimum) lokal dalam domain atau pada batas domain. Jadi metode mencari maksimum (atau minimum) global adalah dengan mengamati semua maksimum (atau minimum) lokal di dalamnya sertamaksimum (atau minimum) dari titik-titik pada batas dan menemukan yang terbesar (atau lebih kecil).

Untuk fungsi terdiferensiasi, teorema Fermat menyatakan bahwa ekstrem lokal dalam suatu wilayah harus terjadi pada titik kritis (atau titik yang turunannya sama dengan nol). Namun, tidak semua titik balik bersifat ekstrem. Kita sering kali dapat membedakan apakah suatu titik kritis merupakan maksimum lokal, minimum lokal, atau bukan keduanya dengan menggunakan uji turunan pertama, uji turunan kedua, atau uji turunan orde tinggi, dengan memperhatikan diferensiasi yang cukup.

Untuk setiap fungsi yang ditentukan oleh bagian-bagian, nilai maksimum (atau minimum) dapat ditemukan dengan mencari nilai maksimum (atau minimum) dari masing-masing bagian secara terpisah dan kemudian menentukan mana yang terbesar (atau terkecil).

Fungsi Lebih dari satu Variabel

Kondisi serupa berlaku untuk fungsi dengan lebih dari satu variabel. Misalnya, pada gambar (yang dapat diperbesar) di sebelah kanan, kondisi yang diperlukan untuk maksimum lokal serupa dengan kondisi untuk fungsi variabel tunggal. Turunan parsial pertama dari z (variabel yang akan dimaksimalkan) adalah nol pada maksimumnya (titik terang di bagian atas gambar). Turunan parsial kedua bernilai negatif. Ini hanyalah kondisi yang diperlukan, namun tidak cukup untuk mencapai maksimum lokal sebesarkarena mungkin terdapat titik pelana.Agar kondisi ini dapat diselesaikan secara optimal, fungsi z juga harus terdiferensiasi sempurna. Uji turunan parsial kedua dapat membantu mengklasifikasikan titik tersebut sebagai maksimum relatif atau minimum relatif. Sebaliknya, terdapat perbedaan yang signifikan antara peran satu variabel dan peran beberapa variabel dalam mengidentifikasi kondisi ekstrem global. Misalnya, jika fungsi terdiferensiasi hingga f yang didefinisikan pada interval tertutup pada garis nyata mempunyai titik kritisyang merupakan minimum lokal, maka fungsi tersebut juga merupakan minimum global (gunakan teorema nilai antara dan teorema Rolle untuk membuktikannya) . dengan kontradiksi). Dalam dua dimensi atau lebih argumen ini gagal.Hal ini tercermin dari fungsinya.

yang titik kritisnya hanya di (0,0), yang merupakan minimum lokal dengan f (0,0) = 0. Namun, tidak bisa menjadi minimum global, karena f (2,3) = −5.

Maxima atau minima dari suatu fungsi

Jika jangkauan suatu fungsi yang ekstremnya dicari terdiri dari fungsi itu sendiri (yaitu jika ekstrem suatu fungsi dapat ditemukan), maka ekstremnya ditemukan dengan kalkulus variasi.

Sehubungan dengan himpunan

Paragraf tersebut menjelaskan konsep maxima dan minima dalam konteks himpunan terurut. Jika suatu himpunan terurut S mempunyai m anggota terbesar, maka m disebut anggota maksimum himpunan tersebut, ditulis maks(S). Jika S adalah himpunan bagian dari himpunan terurut T dan m adalah elemen terbesar dari S dengan keteraturan karena T, maka m adalah batas atas terkecil dari S dalam T. Konsep serupa berlaku untuk elemen terkecil, elemen minimal, dan elemen terkecil. elemen bawah terbesar. melompat.

Fungsi maksimum dan minimum untuk himpunan digunakan dalam database dan dapat dihitung dengan cepat menggunakan partisi.Dalam pengurutan parsial umum, elemen terkecil dan elemen minimal tidak boleh tertukar. Dalam himpunan terurut sebagian (poset), elemen terbesar adalah batas atas himpunan, sedangkan elemen maksimum m dari sebuah poset A memenuhi m ≤ b untuk setiap b di A, dan jika m ≤ b maka m = b. Elemen terkecil atau terbesar dari sebuah poset adalah unik, tetapi sebuah poset dapat memiliki beberapa elemen minimum atau maksimum.

Dalam himpunan terurut lengkap, himpunan tersebut dapat mempunyai paling banyak satu elemen minimum dan satu elemen maksimum. Pada himpunan terurut sempurna, elemen minimum adalah elemen terkecil dan elemen maksimum adalah elemen terbesar.Jika rantainya berhingga, maka selalu mempunyai maksimum dan minimum. Jika rantainya tidak terbatas, maka tidak harus memiliki maksimum atau minimum. Misalnya himpunan bilangan asli tidak mempunyai nilai maksimum, namun mempunyai nilai minimum. Jika suatu rantai tak terhingga S dibatasi, penutupan Cl(S) dari himpunan tersebut dapat mempunyai minimum dan maksimum, yang disebut batas bawah terbesar dan batas atas terkecil dari S.

Disadur dari: en.wikipedia.org

Optimisasi Matematika

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

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

Sejarah

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

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

Peneliti penting lainnya dalam optimasi matematika termasuk yang berikut ini:

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

Subbidang utama

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

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

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

Optimalisasi multi-objektif

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

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

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

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

Pengoptimalan multi-moda atau global

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

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

Disadur dari : en.wikipedia.org

Pengertian Model Matematika

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

Klasifikasi

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

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

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

Konstruksi

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

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

Informasi apriori

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

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

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

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

Disadur dari : en.wikipedia.org

Pencarian Lokal Teriterasi

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

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

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

Algoritma Perturbasi

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

Gangguan tolok ukur

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

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

Optimalkan gangguan

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

Disadur dari: en.wikipedia.org

Hill Climbing

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

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

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

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

Varian

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

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

Masalah Dataran Tinggi

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

Disadur dari: en.wikipedia.org

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