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 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 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  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 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: id.wikipedia.org

Pencarian Lokal Berulang (ILS) adalah istilah dalam matematika terapan dan ilmu komputer yang mendefinisikan modifikasi pencarian lokal atau metode mendaki bukit untuk memecahkan masalah optimasi diskrit.

Metode pencarian lokal bisa macet di minimum lokal, di mana tidak ada tetangga yang lebih baik yang tersedia.

Modifikasi sederhana terdiri dari panggilan iterasi ke rutin pencarian lokal, setiap kali dimulai dari konfigurasi awal yang berbeda. Ini disebut pencarian lokal berulang, dan menyiratkan bahwa pengetahuan yang diperoleh selama fase pencarian lokal sebelumnya tidak digunakan. Pembelajaran menyiratkan bahwa sejarah sebelumnya, misalnya memori tentang minima lokal yang ditemukan sebelumnya, ditambang untuk menghasilkan titik awal yang lebih baik dan lebih baik untuk pencarian lokal.

Asumsi implisitnya adalah distribusi berkerumun dari minima lokal: ketika meminimumkan suatu fungsi, menentukan minima lokal yang baik lebih mudah ketika memulai dari minimum lokal dengan nilai rendah daripada saat memulai dari titik acak. Satu-satunya peringatan adalah untuk menghindari kurungan di baskom atraksi tertentu, sehingga tendangan untuk mengubah peminim lokal menjadi titik awal untuk lari berikutnya harus cukup kuat, tetapi tidak terlalu kuat untuk menghindari kembali ke restart acak tanpa memori.

Pencarian Lokal Berulang didasarkan pada pembuatan urutan solusi optimal lokal dengan:

1. mengganggu minimum lokal saat ini;
2. menerapkan pencarian lokal setelah memulai dari solusi yang dimodifikasi.

Kekuatan gangguan harus cukup untuk mengarahkan lintasan ke cekungan tarikan yang berbeda yang mengarah ke optimum lokal yang berbeda.

Algoritma Gangguan

Algoritma gangguan untuk ILS bukanlah tugas yang mudah. Tujuan utamanya adalah untuk tidak terjebak dalam minimum lokal yang sama dan untuk mendapatkan properti ini benar, operasi undo dilarang. Meskipun demikian, permutasi yang baik harus mempertimbangkan banyak nilai, karena ada dua jenis permutasi buruk:

1. terlalu lemah: kembali ke minimum lokal yang sama
2. terlalu kuat: restart acak

Gangguan Tolok Ukur

Prosedurnya terdiri dari memperbaiki sejumlah nilai untuk gangguan sedemikian rupa sehingga nilai-nilai ini signifikan misalnya: pada probabilitas rata-rata dan tidak jarang. Setelah itu, pada saat runtime akan memungkinkan untuk memeriksa plot benchmark untuk mendapatkan ide rata-rata pada instance yang dilewati.

Gangguan Adaptif

Karena tidak ada fungsi apriori yang memberi tahu mana yang merupakan nilai yang paling cocok untuk gangguan tertentu, kriteria terbaik adalah membuatnya adaptif. Misalnya Battiti dan Protasi mengusulkan algoritma pencarian reaktif untuk MAX-SAT yang sangat cocok dengan kerangka kerja ILS. Mereka melakukan skema gangguan "terarah" yang diimplementasikan oleh algoritma pencarian tabu dan setelah setiap gangguan mereka menerapkan algoritma keturunan lokal standar. Cara lain untuk mengadaptasi gangguan adalah dengan mengubah secara deterministik kekuatannya selama pencarian.

Mengoptimalkan Gangguan

Prosedur lain adalah mengoptimalkan sub-bagian dari masalah, dengan mengaktifkan properti not-undo. Jika prosedur ini memungkinkan, semua solusi yang dihasilkan setelah gangguan cenderung sangat baik. Selanjutnya bagian-bagian baru juga dioptimalkan.

Kesimpulan

Metode ini telah diterapkan pada beberapa masalah optimasi kombinatorial termasuk masalah Penjadwalan Job Shop, Masalah Flow-Shop, Masalah Perutean Kendaraan serta banyak lainnya.

Sumber Artikel: id.wikipedia.org

Dalam analisis numerik, mendaki bukit adalah teknik optimasi matematis yang termasuk dalam keluarga pencarian lokal. Ini adalah algoritma iteratif yang dimulai dengan solusi arbitrer untuk suatu masalah, kemudian mencoba menemukan solusi yang lebih baik dengan membuat perubahan bertahap pada solusi. Jika perubahan menghasilkan solusi yang lebih baik, perubahan tambahan lainnya dilakukan pada solusi baru, dan seterusnya sampai tidak ada perbaikan lebih lanjut yang dapat ditemukan.

Misalnya, mendaki bukit dapat diterapkan pada masalah salesman keliling. Sangat mudah untuk menemukan solusi awal yang mengunjungi semua kota tetapi kemungkinan akan sangat buruk dibandingkan dengan solusi optimal. Algoritme dimulai dengan solusi semacam itu dan membuat perbaikan kecil untuknya, seperti mengubah urutan kunjungan dua kota. Akhirnya, rute yang jauh lebih pendek kemungkinan akan diperoleh.

Pendakian bukit menemukan solusi optimal untuk masalah cembung – untuk masalah lain hanya akan menemukan optima lokal (solusi yang tidak dapat diperbaiki oleh konfigurasi tetangga), yang belum tentu solusi terbaik (optimal global) dari semua solusi yang mungkin ( ruang pencarian). Contoh algoritma yang memecahkan masalah cembung dengan mendaki bukit termasuk algoritma simpleks untuk pemrograman linier dan pencarian biner.: 253  Untuk mencoba menghindari terjebak dalam optima lokal, seseorang dapat menggunakan restart (yaitu pencarian lokal berulang), atau lebih skema kompleks berdasarkan iterasi (seperti pencarian lokal berulang), atau pada memori (seperti optimasi pencarian reaktif dan pencarian tabu), atau pada modifikasi stokastik tanpa memori (seperti simulasi anil).

Kesederhanaan relatif dari algoritme menjadikannya pilihan pertama yang populer di antara algoritme pengoptimalan. Ini digunakan secara luas dalam kecerdasan buatan, untuk mencapai keadaan tujuan dari simpul awal. Pilihan yang berbeda untuk node berikutnya dan node awal digunakan dalam algoritma terkait. Meskipun algoritme yang lebih canggih seperti simulasi anil atau pencarian tabu dapat memberikan hasil yang lebih baik, dalam beberapa situasi mendaki bukit juga berfungsi dengan baik. Pendakian bukit seringkali dapat menghasilkan hasil yang lebih baik daripada algoritma lain ketika jumlah waktu yang tersedia untuk melakukan pencarian terbatas, seperti dengan sistem waktu nyata, selama sejumlah kecil peningkatan biasanya menyatu pada solusi yang baik (solusi optimal atau pendekatan dekat). Di sisi lain, bubble sort dapat dilihat sebagai algoritme pendakian bukit (setiap pertukaran elemen yang berdekatan mengurangi jumlah pasangan elemen yang tidak teratur), namun pendekatan ini jauh dari efisien bahkan untuk N yang sederhana, karena jumlah pertukaran yang diperlukan bertambah secara kuadrat.

Mendaki bukit adalah algoritme kapan saja: ia dapat mengembalikan solusi yang valid bahkan jika terputus kapan saja sebelum berakhir.

Deskripsi matematika

Mendaki bukit mencoba untuk memaksimalkan (atau meminimalkan) fungsi target , di mana adalah vektor nilai kontinu dan/atau diskrit. Pada setiap iterasi, mendaki bukit akan menyesuaikan satu elemen di dan menentukan apakah perubahan meningkatkan nilai . (Perhatikan bahwa ini berbeda dari metode penurunan gradien, yang menyesuaikan semua nilai dalam pada setiap iterasi sesuai dengan gradien bukit.) Dengan mendaki bukit, perubahan apa pun yang meningkatkan diterima, dan proses berlanjut sampai tidak ada perubahan yang dapat ditemukan untuk meningkatkan nilai. Maka dikatakan "optimal secara lokal".

Dalam ruang vektor diskrit, setiap nilai yang mungkin untuk  dapat divisualisasikan sebagai simpul dalam graf. Pendakian bukit akan mengikuti grafik dari titik ke titik, selalu meningkat (atau menurun) secara lokal nilai , hingga maksimum lokal (atau minimum lokal ) tercapai.

Varian

Dalam pendakian bukit sederhana, simpul terdekat pertama dipilih, sedangkan pada pendakian bukit tercuram semua penerus dibandingkan dan yang paling dekat dengan solusi dipilih. Kedua bentuk gagal jika tidak ada node yang lebih dekat, yang mungkin terjadi jika ada maxima lokal di ruang pencarian yang bukan solusi. Pendakian bukit pendakian terjal mirip dengan pencarian terbaik-pertama, yang mencoba semua kemungkinan ekstensi jalur saat ini, bukan hanya satu.

Pendakian bukit stokastik tidak memeriksa semua tetangga sebelum memutuskan bagaimana cara bergerak. Sebaliknya, ia memilih tetangga secara acak, dan memutuskan (berdasarkan jumlah peningkatan pada tetangga itu) apakah akan pindah ke tetangga itu atau memeriksa yang lain.

Penurunan koordinat melakukan pencarian garis sepanjang satu arah koordinat pada titik saat ini di setiap iterasi. Beberapa versi penurunan koordinat secara acak memilih arah koordinat yang berbeda masing-masing erasi.

Pendakian bukit yang dimulai ulang secara acak adalah meta-algoritma yang dibangun di atas algoritma pendakian bukit. Ini juga dikenal sebagai pendakian bukit Shotgun. Ini secara iteratif melakukan pendakian bukit, setiap kali dengan kondisi awal acak . terbaik dipertahankan: jika rangkaian baru mendaki bukit menghasilkan yang lebih baik daripada status tersimpan, ini akan menggantikan status tersimpan.

Pendakian bukit yang dimulai ulang secara acak adalah algoritma yang sangat efektif dalam banyak kasus. Ternyata seringkali lebih baik menghabiskan waktu CPU menjelajahi ruang, daripada mengoptimalkan dengan hati-hati dari kondisi awal

Masalah

Maksimum lokal

Sebuah permukaan dengan dua maxima lokal. (Hanya salah satunya adalah maksimum global.) Jika seorang pendaki bukit dimulai di lokasi yang buruk, mungkin menyatu ke maksimum yang lebih rendah.

Mendaki bukit tidak serta merta menemukan maksimum global, tetapi mungkin bertemu pada maksimum lokal. Masalah ini tidak terjadi jika heuristiknya cembung. Namun, karena banyak fungsi pendakian bukit yang tidak cembung mungkin sering gagal mencapai maksimum global. Algoritme pencarian lokal lainnya mencoba mengatasi masalah ini seperti pendakian bukit stokastik, jalan acak, dan anil simulasi.

Meskipun banyak maxima lokal dalam grafik ini, maksimum global masih dapat ditemukan dengan menggunakan simulasi annealing. Sayangnya, penerapan simulasi anil adalah masalah khusus karena bergantung pada penemuan lompatan keberuntungan yang meningkatkan posisi. Dalam contoh ekstrem seperti itu, pendakian bukit kemungkinan besar akan menghasilkan maksimum lokal.

Pegunungan dan gang

Sebuah punggungan

Punggungan adalah masalah yang menantang bagi pemanjat bukit yang mengoptimalkan dalam ruang terus menerus. Karena pemanjat bukit hanya menyesuaikan satu elemen dalam vektor pada satu waktu, setiap langkah akan bergerak dalam arah yang sejajar sumbu. Jika fungsi target membuat punggungan sempit yang menanjak ke arah yang tidak searah sumbu (atau jika tujuannya adalah meminimalkan, gang sempit yang menurun ke arah yang tidak searah sumbu), maka pemanjat bukit hanya dapat mendaki punggung bukit (atau menuruni gang) dengan zig-zag. Jika sisi punggung bukit (atau gang) sangat curam, maka pemanjat bukit mungkin terpaksa mengambil langkah yang sangat kecil karena zig-zag menuju posisi yang lebih baik. Dengan demikian, mungkin diperlukan waktu yang tidak masuk akal untuk naik ke punggung bukit (atau menuruni gang).

Sebaliknya, metode penurunan gradien dapat bergerak ke segala arah sehingga punggung bukit atau gang dapat naik atau turun. Oleh karena itu, penurunan gradien atau metode gradien konjugasi umumnya lebih disukai daripada mendaki bukit ketika fungsi target dapat dibedakan. Akan tetapi, pemanjat bukit memiliki keuntungan karena tidak memerlukan fungsi target yang dapat dibedakan, sehingga pemanjat bukit mungkin lebih disukai bila fungsi targetnya kompleks.

Dataran

Masalah lain yang terkadang terjadi dengan pendakian bukit adalah dataran tinggi. Dataran tinggi ditemui ketika ruang pencarian datar, atau cukup datar sehingga nilai yang dikembalikan oleh fungsi target tidak dapat dibedakan dari nilai yang dikembalikan untuk wilayah terdekat karena presisi yang digunakan oleh mesin untuk mewakili nilainya. Dalam kasus seperti itu, pemanjat bukit mungkin tidak dapat menentukan ke arah mana ia harus melangkah, dan mungkin mengembara ke arah yang tidak pernah mengarah pada perbaikan. 

Sumber Artikel: id.wikipedia.org

Optimasi kombinatorial adalah subbidang optimasi matematis yang terdiri dari pencarian objek yang optimal dari sekumpulan objek berhingga, dimana himpunan solusi fisibel adalah diskrit atau dapat direduksi menjadi himpunan diskrit. Masalah optimasi kombinatorial yang umum adalah masalah travelling salesman ("TSP"), masalah pohon merentang minimum ("MST"), dan masalah knapsack. Dalam banyak masalah seperti itu, seperti yang disebutkan sebelumnya, pencarian lengkap tidak dapat dilacak, sehingga algoritma khusus yang dengan cepat mengesampingkan sebagian besar ruang pencarian atau algoritma perkiraan harus digunakan sebagai gantinya.

Optimasi kombinatorial berkaitan dengan riset operasi, teori algoritma, dan teori kompleksitas komputasi. Ini memiliki aplikasi penting di beberapa bidang, termasuk kecerdasan buatan, pembelajaran mesin, teori lelang, rekayasa perangkat lunak, matematika terapan, dan ilmu komputer teoretis.

Beberapa literatur penelitian menganggap optimasi diskrit terdiri dari pemrograman integer bersama dengan optimasi kombinatorial (yang pada gilirannya terdiri dari masalah optimasi yang berhubungan dengan struktur grafik), meskipun semua topik ini memiliki literatur penelitian yang terkait erat. Ini sering melibatkan penentuan cara untuk secara efisien mengalokasikan sumber daya yang digunakan untuk menemukan solusi untuk masalah matematika.

Aplikasi

Ini adalah daftar dinamis dan mungkin tidak akan pernah dapat memenuhi standar kelengkapan tertentu. Anda dapat membantu dengan menambahkan item yang hilang dengan sumber terpercaya.

Aplikasi optimasi kombinatorial termasuk, namun tidak terbatas pada:

Logistik

• Optimalisasi rantai pasokan
• Mengembangkan jaringan jari-jari dan tujuan maskapai terbaik
• Memutuskan taksi mana dalam armada yang akan dirutekan untuk mengambil tarif
• Menentukan cara pengiriman paket yang optimal
• Mengalokasikan pekerjaan kepada orang-orang secara optimal
• Merancang jaringan distribusi air
• Masalah ilmu kebumian (misalnya laju aliran reservoir)

Metode

Ada banyak literatur tentang algoritma waktu polinomial untuk kelas khusus tertentu dari optimasi diskrit. Sejumlah besar itu disatukan oleh teori pemrograman linier. Beberapa contoh masalah optimasi kombinatorial yang dicakup oleh kerangka kerja ini adalah jalur terpendek dan pohon jalur terpendek, aliran dan sirkulasi, pohon rentang, pencocokan, dan masalah matroid.

Untuk masalah optimasi diskrit lengkap NP, literatur penelitian saat ini mencakup topik-topik berikut:

• waktu polinomial kasus khusus yang dapat dipecahkan secara tepat dari masalah yang dihadapi (misalnya, masalah yang dapat diselesaikan dengan parameter tetap)
• algoritme yang berkinerja baik pada instans "acak" (mis. untuk masalah penjual keliling)
• algoritma aproksimasi yang berjalan dalam waktu polinomial dan menemukan solusi yang mendekati optimal
• memecahkan contoh dunia nyata yang muncul dalam praktik dan tidak selalu menunjukkan perilaku kasus terburuk dalam masalah NP-lengkap (misalnya contoh TSP dunia nyata dengan puluhan ribu node [6]).

Masalah optimasi kombinatorial dapat dilihat sebagai pencarian elemen terbaik dari beberapa set item diskrit; oleh karena itu, pada prinsipnya, segala jenis algoritma pencarian atau metaheuristik dapat digunakan untuk menyelesaikannya. Mungkin pendekatan [kata musang] yang paling dapat diterapkan secara universal adalah cabang-dan-terikat (algoritma tepat yang dapat dihentikan kapan saja untuk berfungsi sebagai heuristik), cabang-dan-potong (menggunakan optimasi linier untuk menghasilkan batas), dinamis pemrograman (konstruksi solusi rekursif dengan jendela pencarian terbatas) dan pencarian tabu (algoritma swapping tipe serakah). Namun, algoritma pencarian generik tidak dijamin untuk menemukan solusi optimal terlebih dahulu, juga tidak dijamin berjalan cepat (dalam waktu polinomial). Karena beberapa masalah optimasi diskrit adalah NP-complete, seperti masalah travelling salesman (decision),[7] hal ini diharapkan kecuali P=NP.

Definisi formal

Secara formal, masalah optimisasi kombinatorial adalah empat kali lipat, di mana

•  adalah sekumpulan instance;
• diberikan contoh adalah himpunan hingga dari solusi layak;
• diberikan contoh dan solusi yang layak dari , menunjukkan ukuran , yang biasanya real positif.
• adalah fungsi tujuan, dan merupakan  atau .

Tujuannya adalah kemudian untuk menemukan beberapa contoh solusi optimal, yaitu solusi yang layak  dengan

Untuk setiap masalah optimasi kombinatorial, ada masalah keputusan terkait yang menanyakan apakah ada solusi yang layak untuk ukuran tertentu . Misalnya, jika ada graf yang berisi simpul dan , masalah pengoptimalan mungkin "menemukan jalur dari ke  yang menggunakan tepi paling sedikit". Masalah ini mungkin memiliki jawaban, katakanlah, 4. Masalah keputusan yang sesuai adalah "apakah ada jalur dari ke  yang menggunakan 10 sisi atau lebih sedikit?" Masalah ini dapat dijawab dengan sederhana 'ya' atau 'tidak'.

Bidang algoritme aproksimasi berkaitan dengan algoritme untuk menemukan solusi yang mendekati optimal untuk masalah sulit. Versi keputusan yang biasa kemudian merupakan definisi masalah yang tidak memadai karena hanya menentukan solusi yang dapat diterima. Meskipun kita dapat memperkenalkan masalah keputusan yang sesuai, masalah tersebut kemudian secara lebih alami dicirikan sebagai masalah optimasi.

Masalah optimasi NP

Masalah optimasi NP (NPO) adalah masalah optimasi kombinatorial dengan kondisi tambahan berikut.[9] Perhatikan bahwa polinomial yang dirujuk di bawah ini adalah fungsi dari ukuran input fungsi masing-masing, bukan ukuran beberapa set implisit dari instance input.

• ukuran setiap solusi yang layak dibatasi secara polinomial dalam ukuran instance yang diberikan ,
• bahasa dan  dapat dikenali dalam waktu polinomial, dan
• adalah waktu polinomial yang dapat dihitung.

Ini menyiratkan bahwa masalah keputusan yang sesuai ada di NP. Dalam ilmu komputer, masalah optimasi yang menarik biasanya memiliki sifat-sifat di atas dan oleh karena itu merupakan masalah NPO. Masalah juga disebut masalah optimasi-P (PO), jika ada algoritma yang menemukan solusi optimal dalam waktu polinomial. Seringkali, ketika berhadapan dengan kelas NPO, seseorang tertarik pada masalah optimasi yang versi keputusannya adalah NP-complete. Perhatikan bahwa hubungan kekerasan selalu berkaitan dengan beberapa pengurangan. Karena hubungan antara algoritma aproksimasi dan masalah optimasi komputasi, reduksi yang mempertahankan aproksimasi dalam beberapa hal lebih disukai untuk subjek ini daripada reduksi Turing dan Karp biasa. Contoh pengurangan seperti itu adalah pengurangan-L. Untuk alasan ini, masalah optimasi dengan versi keputusan NP-complete tidak selalu disebut NPO-complete.

NPO dibagi menjadi beberapa subkelas berikut menurut perkiraannya:

• NPO(I): Sama dengan FPTAS. Berisi masalah Knapsack.
• NPO(II): Sama dengan PTAS. Berisi masalah penjadwalan Makespan.
• NPO(III): :Kelas masalah NPO yang memiliki algoritma polinomial-waktu yang menghitung solusi dengan biaya paling banyak c kali biaya optimal (untuk masalah minimisasi) atau biaya paling sedikit {\displaystyle 1/c}1/c dari biaya optimal (untuk masalah maksimisasi). Dalam buku Hromkovi[yang mana?], yang dikecualikan dari kelas ini adalah semua masalah NPO(II) kecuali jika P=NP. Tanpa pengecualian, sama dengan APX. Berisi MAX-SAT dan metrik TSP.
• NPO(IV): :Kelas masalah NPO dengan algoritma waktu polinomial yang mendekati solusi optimal dengan rasio polinomial dalam logaritma dari ukuran input. Dalam buku Hromkovi, semua masalah NPO(III) dikeluarkan dari kelas ini kecuali P=NP. Berisi masalah set cover.
• NPO(V): :Kelas masalah NPO dengan algoritma waktu polinomial yang mendekati solusi optimal dengan rasio yang dibatasi oleh beberapa fungsi pada n. Dalam buku Hromkovic, semua masalah
• NPO(IV) dikeluarkan dari kelas ini kecuali P=NP. Berisi masalah TSP dan klik.

Masalah NPO disebut berbatas polinomial (PB) jika, untuk setiap instance dan untuk setiap solusi , ukurannya dibatasi oleh fungsi polinomial dengan ukuran . Kelas NPOPB adalah kelas masalah NPO yang berbatas polinomial.

Masalah khusus

Ini adalah daftar dinamis dan mungkin tidak akan pernah dapat memenuhi standar kelengkapan tertentu. Anda dapat membantu dengan menambahkan item yang hilang dengan sumber terpercaya.

Tur wiraniaga keliling yang optimal melalui 15 kota terbesar di Jerman. Ini adalah tur terpendek di antara 43.589.145.600 kemungkinan tur yang mengunjungi setiap kota tepat satu kali.

• Masalah tugas
• Masalah penutupan
• Masalah kepuasan kendala
• Masalah pemotongan stok
• Masalah himpunan yang mendominasi
• Pemrograman bilangan bulat
• Masalah ransel
• Variabel relevan minimum dalam sistem linier
• Pohon merentang minimum
• Masalah penjadwalan perawat
• Setel masalah penutup
• Penjadwalan toko kerja
• Masalah penjual keliling
• Masalah penjadwalan ulang kendaraan
• Masalah perutean kendaraan
• Masalah penugasan target senjata
• Masalah pengepakan tempat sampah

Sumber Artikel: id.wikipedia.org

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

1. algoritma genetika oleh Holland (1975)
2. 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: id.wikipedia.org

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: id.wikipedia.org