diklatkerja | Optimasi kombinatorial : Pengertian, Aplikasi, Metode dan Masalah Optimasi

Optimasi kombinatorial

Optimasi kombinatorial merupakan 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

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 $A$ adalah empat kali lipat $(I,f,m,g)$ , di mana

$I$ adalah sekumpulan instance;
diberikan contoh $x\in I$ adalah himpunan hingga dari solusi layak;
diberikan contoh $x$ dan solusi yang layak $y$ dari $x$ , $m(x,y)$ menunjukkan ukuran $y$ , yang biasanya real positif.
$g$ adalah fungsi tujuan, dan merupakan $\min$ atau $\max$ .

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

$m(x,y)=g\{m(x,y')\mid y'\in f(x)\}.$

Untuk setiap masalah optimasi kombinatorial, ada masalah keputusan terkait yang menanyakan apakah ada solusi yang layak untuk ukuran tertentu $m_{0}$ . Misalnya, jika ada graf $G$ yang berisi simpul $u$ dan $v$ , masalah pengoptimalan mungkin "menemukan jalur dari $u$ ke $v$ yang menggunakan tepi paling sedikit". Masalah ini mungkin memiliki jawaban, katakanlah, 4. Masalah keputusan yang sesuai adalah "apakah ada jalur dari $u$ ke $v$ 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 $y\in f(x)$ dibatasi secara polinomial dalam ukuran instance yang diberikan $x$ ,
bahasa $\{\,x\,\mid \,x\in I\,\}$ dan $\{\,(x,y)\,\mid \,y\in f(x)\,\}$ dapat dikenali dalam waktu polinomial, dan
$m$ 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 $x$ dan untuk setiap solusi $y\in f(x)$ , ukurannya $m(x,y)$ dibatasi oleh fungsi polinomial dengan ukuran $x$ . 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

Disadur dari: en.wikipedia.org