Heuristika

Heuristik adalah seni dan sains yang berkaitan dengan penemuan, berasal dari kata dasar yang sama dengan “eureka”, yang berarti “menemukan”. Heuristik dalam konteks pemecahan masalah merupakan suatu cara membimbing pemikiran seseorang untuk memecahkan suatu masalah hingga berhasil diselesaikan. Meskipun proses heuristik ini mungkin tidak selalu memberikan hasil yang diinginkan atau bahkan menimbulkan masalah baru, namun sangat berharga dalam memperkaya proses berpikir. Heuristik yang baik dapat secara signifikan mengurangi waktu yang dibutuhkan untuk menyelesaikan suatu masalah dengan menghilangkan kebutuhan untuk mempertimbangkan kemungkinan atau hubungan yang mungkin tidak relevan ketika masalah tersebut muncul.

Gambaran Umum

Heuristik adalah strategi yang didasarkan pada pengalaman sebelumnya dengan masalah serupa. Bergantung pada informasi yang dapat diakses, heuristik digunakan untuk memandu solusi masalah abstrak manusia dan mesin. Salah satu heuristik paling dasar adalah trial and error, yang diterapkan dari permasalahan sederhana hingga penyelesaian variabel dalam permasalahan aljabar. Dalam matematika, heuristik mencakup penggunaan representasi visual, asumsi tambahan, penalaran maju/mundur, dan penyederhanaan. George Pólya, dalam bukunya “How to Solve It,” menyarankan beberapa heuristik umum, seperti menggambar ketika sulit untuk menyelesaikannya. memahami masalah, menggunakan solusi yang diasumsikan untuk mengeksplorasi ide, mempelajari contoh-contoh konkret ketika masalah bersifat abstrak, dan menangani solusi umum. Masalah pertama, mengikuti paradoks penemu, yang menyatakan bahwa perencanaan yang lebih ambisius mempunyai peluang keberhasilan yang lebih besar.

Sejarah

Heuristika sebagai prosedur preskriptif

Metode heuristik pertama kali muncul dalam filsafat dan matematika abad ke-13 bersama Raimundus Lullus, yang mengembangkan pendekatan skolastik Aristoteles untuk memecahkan masalah menggunakan algoritma tradisional. Pada abad ke-17, Gottfried Wilhelm Leibniz mencoba mengembangkan algoritma universal untuk mewakili semua masalah yang mungkin terjadi. René Descartes merumuskan aturan sederhana untuk menyelesaikan masalah dengan memusatkan perhatian pada aspek-aspek yang relevan. Pada tahun 1, Bernard Bolzano mengembangkan heuristik untuk agensi epistemik, menyadari bahwa heuristik mencakup prosedur umum dan tidak jelas untuk mendorong pemikiran kreatif.

George Pólya memberikan apresiasi yang lebih besar terhadap heuristik dalam matematika modern pada abad ke-20, menekankan pencarian analogi, reduksi masalah, serta dekomposisi dan rekombinasi masalah sebagai pendekatan yang efektif.Prinsip kepuasan dalam heuristik keputusan, yang dikembangkan oleh Herbert A. Simon, memperkenalkan konsep bahwa pengambil keputusan sering kali memilih solusi yang “cukup baik” yang memenuhi persyaratan minimum. Pada tahun 1970an dan 1980an, Amos Tversky dan Daniel Kahneman memperluas studi heuristik dalam pengambilan keputusan manusia dengan mengakui bahwa pengambil keputusan sering bertindak dengan cara yang rasional dan menciptakan istilah "memuaskan" untuk menggambarkan situasi di mana solusi dianggap memadai. diketahui meskipun belum optimal.

Heuristika sebagai strategi model komputasi

Pada tahun 1970-an, kemunculan komputer sebagai alat komputasi dan metafora pikiran memicu upaya untuk mensimulasikan perilaku cerdas pada mesin, khususnya dalam pemecahan masalah komputasi. Dalam konteks ini, beberapa heuristik diidentifikasi, dengan penelitian sistematis yang mengklasifikasikan aturan keputusan berdasarkan dimensi tertentu. Gigerenzer (2001) memperkenalkan “Adaptive Toolbox,” yang menggambarkan heuristik melalui tiga modul: aturan pencarian, aturan penghentian, dan aturan keputusan.Prinsip dasar model komputasi disesuaikan dengan tugas, situasi dan keputusan pembuatnya serta menggabungkan dua pendekatan dari literatur dalam bentuk formal. Model tersebut membentuk komponen dasar berbagai heuristik yang berkaitan dengan peralatan adaptif dan klasifikasi Svenson (1979).Konsep baru heuristik Gigerenzer (2001) dalam strategi ekologi rasional menantang keyakinan bahwa heuristik selalu memberikan hasil terbaik kedua dan bahwa optimalisasi selalu lebih baik daripada perangkat adaptif.

Penilaian probabilitas dan frekuensi

Strategi pemecahan masalah heuristik dapat dibagi menjadi empat bagian yang mempengaruhi penilaian probabilitas dan frekuensi. Pertama, heuristik ketersediaan didasarkan pada gagasan bahwa sesuatu yang mudah diingat dianggap lebih penting daripada solusi alternatif. Kedua, heuristik keterwakilan digunakan untuk menilai probabilitas subjektif dengan mempertimbangkan derajat kemiripan suatu peristiwa terhadap fitur-fitur penting atau fitur-fitur yang menonjol. Ketiga, heuristik penahan dan penyesuaianmemengaruhi penilaian probabilitas intuitif dengan memulai dari titik referensi tertentu dan membuat penyesuaian berdasarkan informasi tambahan. Terakhir, heuristik keakraban mengevaluasi peristiwa sebagai sesuatu yang lebih umum atau penting karena peristiwa tersebut lebih familier dalam ingatan dan menggunakan pengalaman masa lalu sebagai kerangka acuan untuk berperilaku dalam situasi baru dan familier.

Kecerdasan Buatan

Saat mencari ruang solusi, heuristik dapat digunakan dalam sistem kecerdasan buatan. Heuristik ini diperoleh dengan menggunakan berbagai fungsi yang dimasukkan ke dalam sistem oleh perancang atau dengan menyesuaikan bobot cabang, yang ditentukan oleh probabilitas setiap cabang mengarah ke node target.

Kritik dan Kontroversi

Konsep heuristik menuai kritik dan kontroversi. Kritik terhadap Kita Tidak Bisa Sebodoh Itu berpendapat bahwa rata-rata orang memiliki sedikit kemampuan untuk membuat penilaian efektif berdasarkan data.

Sumber: id.wikipedia.org

Dinamika Sistem

Dinamika sistem (dikenal dalam bahasa Inggris sebagai System Dynamics) adalah metode pemodelan yang diperkenalkan oleh Jay Forrester pada tahun 1950-an dan dikembangkan di Massachusetts Institute of Technology, AS. Tujuan utama dari metode ini adalah untuk mempelajari tren dinamis dalam sistem yang kompleks, yaitu pola perilaku yang berkembang seiring waktu. Paradigma dinamika sistem mengasumsikan bahwa pola dinamika berkelanjutan dalam sistem kompleks apa pun muncul daristruktur sebab akibat yang membentuk sistem tersebut. Oleh karena itu, model dinamika sistem masuk dalam kategori model matematika kausal atau teori sebab-akibat.

Prinsip-prinsip

Metodologi dinamika sistem pada dasarnya menggunakan hubungan sebab akibat dalam membangun model sistem yang kompleks sebagai dasar untuk mengenali dan memahami perilaku dinamis sistem. Dengan kata lain, penggunaan metodologi dinamika sistem lebih fokus pada tujuan meningkatkan pemahaman kita tentang bagaimana perilaku sistem muncul dari strukturnya. Permasalahan yang dapat dimodelkan secara memadai dengan menggunakan metodologi dinamika sistem adalah permasalahan yang bersifat dinamis (berubah terhadap waktu) dan struktur fenomenanya mengandung paling sedikit satu struktur umpan- balik (feedback structure).

Prinsip-prinsip untuk menciptakan model dinamis, seperti yang dijelaskan oleh Sterman (1981), meliputi pemisahan antara keadaan yang diinginkan dan keadaan sebenarnya, representasi struktur aliran dan keberadaan nyata, pemisahan aliran konseptual, penggunaan informasi yang diberikan kepada aktor dalam sistem. tersedia, kesesuaian struktur aturan pengambilan keputusan dengan praktik pengelolaan dan keberlanjutan model dalam kondisi ekstrim.

Sedangkan untuk ketahanan suatu model, menurut Sterman, perlu dilakukan sejumlah pengujian agar pada gilirannya kepercayaan pengguna terhadap kemampuan model dalam mengekspresikan sistem yang diwakilinya meningkat. Keyakinan inilah yang menjadi dasar validitas model. Setelah validitas model tercapai, simulasi dapat digunakan untuk merancang kebijakan yang efektif.

Struktur dan Hubungan Dalam Model

Model dinamika sistem muncul karena adanya hubungan sebab-akibat yang mempengaruhi struktur di dalamnya, baik secara langsung antara dua struktur maupun akibat dari berbagai hubungan yang terjadi pada struktur yang berbeda, sehingga membentuk suatu putaran umpan balik (causal loop). Struktur umpan balik ini adalah blok penyusun model, yang diekspresikan melalui hubungan sebab-akibat loop tertutup dari variabel.

Terdapat dua jenis hubungan sebab akibat dalam sistem, yaitu hubungan sebab akibat positif dan hubungan sebab akibat negatif. Selain itu, ada dua jenis umpan balik, yaitu umpan balik positif terkait pertumbuhan (growth) dan umpan balik negatif terkait pencapaian tujuan (goalpurse).

Saat merepresentasikan aktivitas dalam putaran umpan balik, dua jenis variabel utama digunakan: stok dan aliran (juga disebut level dan laju atau stok dan aliran). Inventaris mewakili keadaan sistem pada setiap saat.Dalam teknologi, sistem inventaris lebih dikenal dengan istilah sistem keadaan variabel. Persediaan terakumulasi dalam sistem. Persamaan tarif variabel adalah struktur kebijakan yang menjelaskan mengapa dan bagaimana suatu keputusan dibuat berdasarkan informasi yang tersedia dalam sistem.Arus adalah satu-satunya variabel dalam model yang dapat mempengaruhi saham.

Selain variabel stok dan aliran, terdapat variabel pembantu lainnya, konstanta dan penundaan dalam pemodelan dinamika sistem. Variabel bantu adalah variabel yang dapat berubah seiring berjalannya waktu. Perubahan tersebut dapat disebabkan oleh hubungan sebab akibat antar variabel dalam model atau oleh variabel eksternal yang independen. Konstanta adalah variabel dengan nilai tetap yang tidak berubah seiring waktu. Sedangkan lag merupakan variabel waktu dalam perubahan perilaku yang tidak terjadi dengan segera (tertunda) pada proses yang terjadi pada hubungan antar struktur dan mempengaruhi perilaku model.

Penggunaan

Awalnya Forrester menerapkan metodologi systemdynamics untuk menyelesaikan permasalahan di industri (bisnis). Model dinamika sistem pada awalnya membahas masalah manajemen umum seperti fluktuasi persediaan, ketidakstabilan tenaga kerja, dan penurunan pangsa pasar perusahaan (lihat Forrester, 1961). Perkembangannya terus meningkat sejak penggunaannya dalam permasalahan sistem sosial yang sangat berbeda, dilakukan dan digunakan olehpemegang polis.

Pemanfaatan Perangkat Lunak

Model dinamika sistem biasanya dibuat menggunakan perangkat lunak yang dikembangkan secara khusus. Perangkat lunak ini mencakup Powersim, Vensim, Stella dan Dynamo. Perangkat lunak ini digunakan untuk membuat model secara grafis dengan simbol variabel dan hubungannya. Namun, tidak menutup kemungkinan bahwa perangkat lunak yang mampu memproses operasi matematika tipe spreadsheet, seperti Microsoft Excel atau Lotus, juga dapat digunakan untuk memodelkan dinamika sistem.

Perkembangan Dinamika Sistem di Indonesia

Di Indonesia, Institut Teknologi Bandung (ITB) merupakan salah satu lembaga pendidikan yang mengajarkan dinamika sistem. Di ITB, dinamika sistem diajarkan melalui mata kuliah pemodelan pada program Magister Studi Pembangunan (S2). Selain itu, ITB juga menawarkan kesempatan mempelajari dinamika sistem melalui kursus. Dalam bidang ilmu transportasi, dinamika sistem diajarkan melalui mata kuliah Pemodelan Transportasi Laut di Jurusan Transportasi Laut (S1), Sistem Informasi (S1, Magister, PhD)bidang pemodelan dan simulasi dari tahun 2006 serta teknik sistem dan industri. . di lembaga pendidikan Institut Teknologi Sepuluh Nopember (ITS) dan pada mata kuliah Pemodelan dan Sistem Dinamis pada jurusan Sistem Informasi Bisnis (SIB) Institut Sains dan Teknologi Terpadu (ISTTS) Surabaya sejak tahun 2021.

Khusus Institut Teknologi Sepuluh Nopember (ITS), sejak tahun 2020, Departemen Kajian Sistem Informasi mempunyai guru besar bidang pemodelan sistem dinamik bernama Prof.Erma Suryani, ST, MT, Ph.D. yang dikukuhkan pada 14 April 2021.

Selain itu, terdapat lembaga swasta yang mengajarkan dan mempopulerkan dinamika sistem, yaitu System Dynamics Center (SDC) yang bekerja sama dengan universitas-universitas di Indonesia untuk mengembangkan dan mempopulerkan pemodelan dinamika sistem, dengan tujuan memberikan Indonesia skenario terbaik untuk membangun .

Sumber: id.wikipedia.org

Trial and error 

Trial and error, metode dasar pemecahan masalah, melibatkan upaya berulang dan bervariasi yang berlanjut hingga kesuksesan tercapai atau praktisi berhenti mencoba. C. Lloyd Morgan menciptakan istilah ini setelah bereksperimen dengan ungkapan serupa seperti “percobaan dan kegagalan” dan “percobaan dan praktik.” Dalam kanon, perilaku hewan dijelaskan secara sederhana dan, dengan asumsi melibatkan proses mental yang lebih tinggi, dapat dijelaskan sebagai pembelajaran melalui coba-coba. Misalnya, Edward Lee Thorndike menggunakan kucing dalam eksperimen laboratorium untuk mendemonstrasikan hukum pengaruh terhadap pembelajaran dan menemukan bahwa hasil positif mendorong pembelajaran.

B. F. Skinner kemudian memperluas konsep ini dengan pengkondisian operan. Trial and error juga digunakan dalam ilmu komputer sebagai metode "build and test" dan dalam matematika, misalnya dalam menyelesaikan persamaan dengan menebak dan memeriksa. Meskipun trial and error adalah salah satu pendekatan dasar pemecahan masalah, ada juga metode perantara seperti empirisme terbimbing, yang memandu proses pemecahan masalah dengan menggunakan teori.Pendekatan yang mencerminkan rasionalisme kritis Karl Popper ini merupakan bagian dari kerangka pemikiran yang dapat digunakan dalam konteks berbeda.

Metodologi

Pendekatan coba-coba (trial-and-error) paling berhasil digunakan pada permasalahan dan permainan sederhana dan sering kali menjadi pilihan terakhir ketika aturan yang jelas tidak dapat diterapkan. Hal ini tidak berarti bahwa pendekatan ini pada dasarnya ceroboh, karena seseorang bisa saja bersifat metodis dalam memanipulasi variabel untuk menyingkirkan kemungkinan-kemungkinan yang dapat membawa kesuksesan. Namun cara ini sering digunakan oleh orang-orang yang memiliki sedikit pengetahuan di bidangsoal. Pendekatan coba-coba diperiksa dari perspektif komputasi alami.

Aplikasi paling sederhana

Ashby (1960) menyajikan tiga strategi sederhana untuk memecahkan masalah pelatihan dasar yang sama dengan efisiensi yang sangat berbeda. Misalnya, jika kita mengatur 1000 tombol hidup/mati dalam kombinasi tertentu dengan percobaan acak, setiap percobaan berlangsung selama satu detik, maka strateginya adalah sebagai berikut:

Metode perfeksionis, di mana segala sesuatu harus berjalan baik atau tidak sama sekali tanpa upaya mempertahankan keberhasilan parsial, diperkirakan akan memakan waktu lebih dari 10^301 detik. Kemudian, rangkaian pengujian sakelar, di mana beberapa berhasil, memiliki durasi rata-rata 500 detik. Terakhir, pengujian paralel namun individual terhadap semua sakelar pada waktu yang sama hanya memerlukan waktu satu detik.

Perlu diketahui bahwa yang mendasari anggapan tersebut adalah anggapan bahwa kecerdasan atau persepsi tidak digunakan untuk menyelesaikan masalah. Namun, kehadiran beberapa strategi memberikan peluang untuk mempertimbangkan domain pemrosesan terpisah atau “tingkat lebih tinggi”, yang dikenal sebagai “tingkat meta,” di atas mekanisme manajemen saklar. Pada tingkat ini, strategi yang berbeda dapat dipilih secara acak, sehingga menciptakan pendekatan coba-coba dengan karakteristik berbeda.

Hirarki

Buku Ashby mengembangkan konsep "meta-level" menjadi urutan level rekursif yang disusun satu di atas yang lain dalam hierarki yang sistematis. Dalam kerangka ini, Ashby berpendapat bahwa kecerdasan manusia muncul dari organisasi seperti itu, yang sangat bergantung pada pendekatan “trial and error” pada setiap tahap baru, namun pada akhir proses tersebut berkembang menjadi apa yang kita sebut “kecerdasan” tahu. Oleh karena itu, tingkat teratas hierarki pada setiap tahap mungkin masih bergantung pada trial and error sederhana.

Traill (1978-2006) mencatat bahwa hierarki yang diusulkan oleh Ashby mungkin tumpang tindih dengan teori tahapan perkembangan Piaget yang terkenal. Menurut Piaget, anak-anak pertama-tama belajar melalui aktivitas yang kurang lebih acak dan kemudian harus belajar dari konsekuensinya, mirip dengan pendekatan “trial and error” acak yang dijelaskan oleh Ashby dalam konteks hierarki tersebut.Hal ini menciptakan kesejajaran antara konsep Ashby dan teori Piaget tentang pembelajaran manusia dan perkembangan kognitif.

Aplikasi

Traill (2008, khususnya Tabel “S” di halaman 31) mengikuti pendekatan Jerne dan Popper dan berasumsi bahwa strategi coba-coba dapat menjadi dasar bagi semua sistem penangkapan pengetahuan, terutama pada tahap awal pengembangannya. . Dalam studinya, Traill mengidentifikasi empat sistem utama yang terlibat dalam penerapan strategi coba-coba: seleksi alam, yang "mendidik" DNA spesies, otak individu (yang baru saja kita bahas), "otak" sosial seperti cabang ilmu pengetahuan masyarakat dan sistem imun adaptif. Konsep ini mendukung pandangan bahwa trial and error tidak hanya sekedar metode pemecahan masalah, tetapi juga dapat menjadi dasar berbagai sistem untuk membangun dan mengembangkan pengetahuan.

Fitur

Trial and error memiliki beberapa karakteristik yang dapat dikenali. Pertama, metode ini berorientasi pada solusi, artinya metode ini tidak berusaha memahami mengapa suatu solusi berhasil melalui trial and error, namun hanya berfokus pada fakta bahwa solusi tersebut dapat ditemukan. Kedua, pendekatan ini bersifat spesifik terhadap permasalahan yang dihadapi dan tidak cenderung menggeneralisasi solusi terhadap permasalahan lainnya. Selain itu, trial and error dianggap suboptimal karena tujuannya biasanya untuk menemukan solusi, bukan keseluruhan spektrum solusi, dan solusi terbaik tidak selalu ditemukan. Terakhir, metode coba-coba dapat dilakukan dengan sedikit atau tanpa pengetahuan tentang subjek yang ada, menjadikannya pendekatan yang layak dan tidak memerlukan pemahaman mendalam.

Metode trial and error dapat digunakan untuk mencari semua solusi atau solusi terbaik dalam situasi dimana terdapat beberapa kemungkinan solusi. Untuk menemukan semua solusi, orang dapat menuliskan setiap solusi yang mereka temukan dan terus mencobanya hingga semua opsi telah dicoba. Untuk mencari solusi terbaik, setelah semua solusi ditemukan, individu dapat membandingkannya berdasarkan kriteria yang telah ditentukan. Adanya kriteria tersebut merupakan prasyarat untuk menemukansolusi terbaik. Ketika hanya ada satu solusi yang mungkin, seperti ketika menyusun sebuah puzzle, solusi yang ditemukan adalah satu-satunya dan dianggap yang terbaik.

Contoh

Secara tradisional, metode utama yang digunakan dalam penemuan obat baru seperti antibiotik adalah trial and error, di mana ahli kimia menguji bahan kimia yang dipilih secara acak untuk menemukan bahan kimia yang mempunyai efek yang diinginkan. Dalam pendekatan yang lebih canggih, mereka memilih sejumlah kecil bahan kimia dan menggunakan hubungan struktur-aktivitas. Metode ini juga digunakan dalam berbagai disiplin ilmu, misalnya pada bidang teknik polimer. Dalam konteks video game, pemain menggunakan trial and error untuk mengatasirintangan atau mengalahkan bos dengan mencoba berbagai strategi. Tim olahraga menggunakan pendekatan ini untuk lolos dan maju ke babak playoff dengan mencoba berbagai taktik dan formasi.

Dalam metode ilmiah, terjadi trial and error dalam merumuskan dan menguji hipotesis. Evolusi biologis dapat dipandang sebagai bentuk coba-coba melalui mutasi acak dan variasi genetik seksual. Contoh lain termasuk algoritma genetika, simulasi anil dan pembelajaran penguatan. Meskipun Bogosort tidak efisien, ini dapat dipandang sebagai metode penyortiran trial-and-error. Laba-laba pelompat dari genus Portia menggunakan trial and error untuk menemukan dan menghafal taktik baru melawan mangsa yang tidak diketahui.Penelitian menunjukkan bahwa bahkan di lingkungan buatan, laba-laba ini dapat menggunakan trial and error untuk mencapai tujuan tertentu.

Disadur dari : https://en.wikipedia.org/wiki/Trial_and_error

Traveling Salesman Problem

Traveling Salesman Problem (TSP), menanyakan pertanyaan berikut: “Mengingat daftar kota dan jarak antara setiap pasangan kota, rute terpendek manakah yang dapat mengunjungi setiap kota tepat satu kali?” dan untuk kembali? Dia? Kampung halaman?” Ini adalah masalah NP-hard dalam optimasi kombinatorial, penting dalam ilmu komputer teoretis dan riset operasi. Masalah pembelanja yang bepergian dan masalah rute kendaraan merupakan generalisasi dari TSP.

Dalam teori kompleksitas komputasi, versi keputusan TSP (dengan panjang L, tugasnya adalah memutuskan apakah grafik memiliki paling banyak satu jalur dengan panjang L) termasuk dalam kelas masalah NP-lengkap.Oleh karena itu, ada kemungkinan bahwa waktu eksekusi kasus terburuk untuk algoritma TSP meningkat secara superpolinomik (tetapi tidak lebih dari eksponensial) dengan jumlah kota.

Masalah ini pertama kali dirumuskan pada tahun 1930 dan merupakan salah satu masalah optimasi yang paling banyak dipelajari. Ini digunakan sebagai titik referensi untuk banyak metode optimasi. Meskipun permasalahannya sulit secara komputasi, banyak heuristik dan algoritma yang sesuai telah diketahui, sehingga beberapa kejadian dengan puluhan ribu kota dapat diselesaikan sepenuhnya, dan bahkan permasalahan dengan jutaan kota dapat didekati dengan sepersekian 1%.

Sejarah

Asal usul masalah pekerja lapangan tidak jelas. Panduan perjalanan tahun 1832 menyebutkan masalah tersebut dan menyertakan contoh perjalanan di Jerman dan Swiss, tetapi tidak memuat penjelasan matematis.

TSP dirumuskan secara matematis pada abad ke-19 oleh matematikawan Irlandia William Rowan Hamilton dan matematikawan Inggris Thomas Kirkman. Permainan Icosian Hamiltonian adalah teka-teki rekreasional yang didasarkan pada penemuan siklus Hamiltonian. Bentuk umum TSP tampaknya pertama kali dipelajari pada tahun 1930-an oleh ahli matematika di Wina dan Harvard, terutama Karl Menger, yang mendefinisikan masalahnya, mempertimbangkan algoritma brute force yang terdefinisi dengan baik, dan mengamati ketidakoptimalan.

Traveling Salesman Problem (TSP) awalnya muncul pada tahun 1930an ketika Merrill M. Flood mencoba memecahkan tantangan perencanaan rute bus sekolah secara matematis. Menariknya, Hassler Whitney dari Universitas Princeton memberikan sentuhan pribadi pada masalah ini dengan menyebutnya sebagai “masalah 48 negara bagian,” sehingga memicu minat awal terhadap topik tersebut. Pada tahun 1950an dan 1960an, popularitas TSP meningkat setelah RAND Corporation menawarkan hadiah kepada mereka yang dapat menyelesaikannya.

Namun, titik kritis dalam pengembangan TSP terjadi pada tahun 1950an dan 1960an, ketika George Dantzig, Delbert Ray Fulkerson, dan Selmer M.Johnson dari RAND Corporation mengembangkan metode bidang potong untuk mengatasi masalah ini. Meskipun kontribusi ini tidak memberikan solusi algoritmik langsung, kontribusi ini memberikan dasar yang sangat penting untuk pengembangan metode solusi yang lebih akurat di masa depan.

Akhirnya, pada tahun 1959, Jillian Beardwood, JH Halton, dan John Hammersley memberikan solusi praktis dengan teorema Beardwood-Halton-Hammersley, menandai perkembangan lebih lanjut dalam pengobatan PST. Pada tahun 1960-an, ada pendekatan baru yang berfokus pada pembuatan batas bawah dengan mengalikan pohon rentang minimum suatu grafik. 

Hal ini membuka jalan bagi metode cabang-dan-gabung, yang menjadi pendekatan penting untuk mengatasi TSP.Selama dekade berikutnya, kemajuan signifikan dicapai pada akhir tahun 1970an dan 1980an, ketika Grötschel, Padberg, Rinaldi, dan peneliti lain memecahkan kasus TSP di 2.392 kota. Pada tahun 1990-an, muncul program Concorde dan TSPLIB yang berperan penting dalam pengembangan dan benchmarking algoritma TSP. Sebuah tonggak sejarah dicapai pada tahun 2006 dengan perhitungan rute optimal untuk 85.900 contoh masalah distribusi microchip perkotaan.Semua ini mencerminkan kemajuan luar biasa dalam pengobatan TSP selama beberapa dekade terakhir.

Deskrpsi 

Sebagai Masalah Grafik

TSP dapat dimodelkan sebagai graf tak berarah berbobot, sehingga kota adalah simpul dari graf tersebut, jalan adalah sisinya, dan jarak suatu lintasan adalah bobot sisinya. Ini adalah masalah minimalisasi yang dimulai pada titik tertentu dan berakhir setelah mengunjungi titik lain tepat satu kali. Seringkali modelnya berupa graf lengkap (yaitu setiap pasangan simpul dihubungkan oleh sebuah sisi). Jika tidak ada jalur antara dua kota, menambahkan sisi yang cukup panjang akan melengkapi grafik tanpa mempengaruhi jalur optimal.

Asimetris dan simetris
Pada TSP simetris, jarak antara dua kota sama besar pada setiap arah yang berlawanan sehingga membentuk grafik tidak berarah. Simetri ini mengurangi separuh jumlah solusi yang mungkin. Dalam TSP asimetris, jalur di kedua arah mungkin tidak ada atau jaraknya mungkin berbeda, sehingga menghasilkan grafik berarah. Kemacetan lalu lintas, jalan satu arah, dan tarif penerbangan kota dengan biaya keberangkatan dan kedatangan yang berbeda menjadi pertimbangan nyata yang secara asimetris dapat menimbulkan masalah TSP.

Disadur dari: en.wikipedia.org

Tabu Search

Tabu Search (TS) adalah metode pencarian metaheuristik yang menggunakan metode pencarian lokal untuk optimasi matematis. Metode ini diciptakan oleh Fred W. Glover pada tahun 1986 dan diformalkan pada tahun 1989.

Pencarian lokal mengambil solusi potensial untuk suatu masalah dan memeriksa tetangga-tetangganya secara langsung (solusi yang mirip kecuali beberapa detail kecil) dengan harapan menemukan solusi yang lebih baik. Metode pencarian lokal memiliki kecenderungan untuk terjebak di wilayah suboptimal atau di dataran tinggi di mana banyak solusi memiliki tingkat kecocokan yang sama.

Tabu Search meningkatkan kinerja pencarian lokal dengan melonggarkan aturan dasarnya. Pertama, pada setiap langkah, gerakan yang memperburuk solusi dapat diterima jika tidak ada gerakan yang memperbaiki yang tersedia (seperti ketika pencarian terjebak pada minimum lokal yang ketat). Selain itu, larangan (dari situlah istilah "tabu" berasal) diberlakukan untuk mencegah pencarian kembali ke solusi yang sudah dikunjungi sebelumnya.

Implementasi dari Tabu Search menggunakan struktur memori yang menggambarkan solusi yang telah dikunjungi atau aturan-aturan yang diberikan oleh pengguna. Jika solusi potensial telah dikunjungi dalam periode waktu tertentu atau telah melanggar suatu aturan, maka solusi tersebut ditandai sebagai "tabu" (dilarang), sehingga algoritma tidak mempertimbangkan kemungkinan tersebut secara berulang-ulang.

Latar Belakang

Tabu Search adalah algoritma metaheuristik untuk memecahkan masalah optimasi kombinatorial (masalah yang memerlukan konfigurasi optimal dan pemilihan opsi).Aplikasi Tabu Search saat ini mencakup bidang-bidang seperti perencanaan sumber daya, telekomunikasi, desain VLSI, analisis keuangan, penjadwalan, perencanaan ruang, distribusi energi, teknik molekuler, logistik, pemilahan pola, manufaktur fleksibel, pengelolaan limbah, eksplorasi mineral, analisis biomedis, dan lingkungan.

Konservasi alam dan banyak lagi. Dalam beberapa tahun terakhir, jurnal dari berbagai bidang telah menerbitkan artikel tutorial dan studi komputasi yang mendokumentasikan keberhasilan Tabu Search dalam memperluas batas-batas masalah yang dapat diatasi secara efektif dan menghasilkan solusi yang kualitasnya seringkali jauh melebihi metode yang digunakan sebelumnya. Daftar lengkap penerapannya, termasuk penjelasan singkat tentang manfaat yang dihasilkan dari penerapan praktis.

Tipe Memory

Tabu Search, sebuah algoritma metaheuristik untuk optimasi kombinatorial, membawa inovasi dalam penanganan masalah kompleks dengan memanfaatkan metode pencarian lokal. Struktur memori Tabu Search, terbagi menjadi memori jangka pendek, menengah, dan panjang, memberikan keunggulan dalam mengatasi kendala-kendala yang umumnya dihadapi oleh metode pencarian lokal tradisional. Memori jangka pendek mencatat solusi-solusi terkini, melarang revisi hingga kadaluwarsa, sementara memori jangka menengah dan panjang menentukan aturan intensifikasi dan diversifikasi untuk membimbing pencarian ke arah yang optimal.

Implementasinya mencakup struktur memori yang merinci solusi-solusi yang sudah dikunjungi atau aturan-aturan pengguna. Keberhasilan Tabu Search terlihat dalam berbagai aplikasi, termasuk perencanaan sumber daya, desain VLSI, logistik, dan sektor lainnya, sering kali menghasilkan solusi yang melampaui kualitas metode-metode sebelumnya. Dengan penekanan pada struktur memori yang adaptif, Tabu Search memberikan kontribusi berharga dalam penyelesaian efisien masalah optimasi kompleks.

Contoh : Traveling Salesman Problem

Pencarian Tabu digunakan untuk menyelesaikan masalah traveling salesman (TSP). TSP sendiri adalah pertanyaan sederhana: Apa rute terpendek yang mengunjungi semua kota dalam daftar kota? Misalnya, jika Kota A dan Kota B berdekatan sedangkan Kota C berjauhan, maka total jarak perjalanan akan lebih pendek jika kota A dan B dikunjungi secara berurutan sebelum mengunjungi Kota C. Karena mencari solusi optimal sangatlah sulit (NP-hard),menggunakan metode pendekatan heuristik seperti pencarian lokal untuk mendapatkan solusi mendekati optimal.Untuk mendapatkan solusi TSP yang baik, penting untuk memanfaatkan struktur grafis.Pencarian Tabu sangat cocok sebagai metode metaheuristik untuk memecahkan masalah ini.

Ada strategi khusus yang terkait dengan pencarian Tabu, yang disebut metode rantai penggusuran, yang memungkinkan diperolehnya solusi TSP berkualitas tinggi secara efisien.Di sisi lain, pencarian tabu sederhana dapat digunakan untuk menemukan solusi yang memuaskan di TSP. Artinya solusi ini memenuhi kriteria cukup, meskipun belum seoptimal solusi yang memanfaatkan struktur grafik dengan baik. Proses pencarian dimulai dengan solusi awal, yang dapat dihasilkan secara acak atau dengan suatu algoritma.Untuk menciptakan solusi baru, kami menukar urutan kunjungan kedua kota tersebut dengan solusi potensial.

Total jarak yang ditempuh digunakan untuk mengevaluasi keunggulan suatu solusi dibandingkan dengan solusi lainnya. Untuk menghindari terjebak dalam pola kunjungan berulang atau solusi lokal yang lebih baik, solusi ditambahkan ke daftar tabu ketika solusi tersebut diterima dalam wilayah solusi tertentu.Proses pencarian berlanjut hingga kriteria penghentian tercapai, misalnya sejumlah iterasi tertentu. Setelah pencarian tabu sederhana dihentikan, hasil akhir akan mengembalikan solusi terbaik yang ditemukan selama proses eksekusi.

Disadur dari : en.wikipedia.org

Dinamika sistem

Dinamika sistem (SD) adalah pendekatan untuk memahami perilaku nonlinear dari sistem yang kompleks dari waktu ke waktu menggunakan stok, aliran, loop umpan balik internal, fungsi tabel, dan penundaan waktu.

Stok dinamis dan diagram alir model Adopsi produk baru (model dari artikel oleh John Sterman 2001 - True Software)

Ringkasan

Dinamika sistem adalah pendekatan matematis untuk memodelkan dan memahami masalah kompleks dengan mempertimbangkan interaksi antar variabel dari waktu ke waktu. Ini dikembangkan pada tahun 1950an dan digunakan baik di sektor publik maupun swasta. Perangkat lunak ini, dengan antarmuka pengguna grafis (GUI), menjadi lebih ramah pengguna pada tahun 1990an. Model dinamika sistem mengatasi masalah konkurensi dengan memperbarui variabel pada interval waktu kecil menggunakan umpan balik positif dan negatif serta penundaan waktu.

Waktu. Model yang terkenal termasuk The Limits to Growth tahun 1972, yang memperkirakan keruntuhan ekonomi abad ke-21 karena pertumbuhan eksponensial dan terbatasnya sumber daya.Dinamika sistem adalah cabang teori sistem yang mengakui bahwa struktur sistem melibatkan hubungan melingkar, penundaan waktu, dan kompleksitas yang mempengaruhi perilaku secara keseluruhan. Contoh penerapannya termasuk teori chaos dan dinamika sosial. Ditekankan bahwa perilaku umum tidak selalu dapat dijelaskan oleh perilaku individu dalam sistem.

Sejarah

Dinamika sistem, ditemukan pada tahun 1950an oleh profesor MIT Jay Forrester, pada awalnya bertujuan untuk memahami masalah mendasar dalam manajemen bisnis. Menggunakan observasi dari siklus tiga tahun di pabrik General Electric (GE), Forrester mengembangkan konsep dinamika sistem melalui simulasi manual. Pada akhir 1950-an, Forrester dan tim mahasiswanya beralih ke pemodelan komputer formal menggunakan bahasa seperti SIMPLE dan DYNAMO. “Dinamika Industri,” buku pertama Forrester yang diterbitkan pada tahun 1961, menjadi buku klasik di bidangnya.

Awalnya digunakan untuk masalah perusahaan, dinamika sistem diperluas ke aplikasi non-perusahaan setelah buku Urban Dynamics karya Collins-Forrester Collaboration pada tahun 1968.Usulan kedua muncul ketika Forrester diundang oleh Club of Rome pada tahun 1970 untuk mengatasi krisis global. Forrester menciptakan model dinamika sistem pertama untuk sistem sosial ekonomi global yang disebut WORLD1, yang kemudian diperbarui menjadi WORLD2. Pada tahun 1972, Forrester menerbitkan World Dynamics, yang memperkenalkan dinamika sistem ke dalam domain global untuk memecahkan masalah-masalah manusia yang tersebar luas.

Topik dalam dinamika sistem

Elemen utama diagram dinamika sistem adalah umpan balik, akumulasi aliran ke inventaris, dan waktu tunda.Sebagai contoh pemanfaatan dinamika sistem, pertimbangkan sebuah organisasi yang berencana memperkenalkan produk konsumen yang baru, tahan lama, dan inovatif. Perusahaan perlu memahami kemungkinan dinamika pasar untuk merancang rencana pemasaran dan produksi.

Causal loop diagrams (Diagram lingkaran sebab akibat)

Dalam metodologi dinamika sistem, suatu masalah atau sistem (misalnya ekosistem, sistem politik, atau sistem mekanis) dapat direpresentasikan sebagai diagram lingkaran sebab akibat. Diagram lingkaran sebab akibat adalah peta sederhana suatu sistem dengan seluruh komponennya dan interaksinya. Dengan menangkap interaksi dan putaran umpan balik berikutnya (lihat gambar di bawah), diagram lingkaran sebab akibat mengungkapkan struktur sistem. Dengan memahami struktur suatu sistem, dimungkinkan untuk menentukan perilaku sistemselama periode waktu tertentu.

Diagram lingkaran sebab-akibat dari pengenalan produk baru mungkin terlihat sebagai berikut:

Gambar: Diagram lingkaran kausal dari model adopsi produk baru

Diagram mengilustrasikan dua putaran umpan balik dalam suatu sistem. Lingkaran penguatan positif di sebelah kanan (R) menunjukkan bahwa semakin banyak orang mengadopsi produk baru, semakin kuat pengaruh promosi dari mulut ke mulut, yang menyebabkan peningkatan rekomendasi, demo, dan ulasan produk. Siklus ini berpotensi menghasilkan pertumbuhan penjualan lebih lanjut.Di sebelah kiri ada putaran umpan balik kedua (B), yaitu penguatan negatif atau “keseimbangan”. Pertumbuhan tidak dapat berlanjut tanpa batas waktu karena semakin banyak orang yang mengadopsi, semakin sedikit potensi yang mengadopsinya.Kedua loop ini bekerja sama dan kekuatannya dapat bervariasi pada waktu yang berbeda. Meskipun pada awalnya mungkin terjadi peningkatan penjualan, lama kelamaan mungkin terjadi penurunan. Namun, representasi visual dalam diagram lingkaran sebab akibat tidak cukup untuk menentukan perilaku sistem secara keseluruhan.

Stock and flow diagrams (Diagram stok dan flow)

Diagram lingkaran sebab akibat membantu memvisualisasikan dan menganalisis secara kualitatif struktur dan perilaku sistem. Untuk analisis kuantitatif yang lebih detail, diagram causal loop diubah menjadi diagram inventaris dan diagram alir. Model stok dan aliran membantu memeriksa dan menganalisis sistem secara kuantitatif. Model-model ini biasanya dibuat dan disimulasikan menggunakan perangkat lunak komputer.“Saham” adalah istilah untuk setiap unit yang terakumulasi atau berkurang seiring berjalannya waktu. Arus adalah laju perubahan saham.

Gambar: Aliran adalah tingkat akumulasi stok

Dalam contoh kami, ada dua stok: Pengadopsi potensial dan Pengadopsi. Ada satu aliran: Pengadopsi baru. Untuk setiap pengadopsi baru, stok pengadopsi potensial berkurang satu, dan stok pengadopsi bertambah satu.

Gambar: Diagram stok dan aliran model adopsi produk baru

Persamaan

Kekuatan nyata dari dinamika sistem dimanfaatkan melalui simulasi. Meskipun dimungkinkan untuk melakukan pemodelan dalam spreadsheet, ada berbagai paket perangkat lunak yang telah dioptimalkan untuk ini.

Langkah-langkah yang dilakukan dalam simulasi adalah:

• Tentukan batas masalah
• Identifikasi stok dan arus paling penting yang mengubah tingkat stok ini
• Mengidentifikasi sumber informasi yang berdampak pada arus
• Identifikasi loop umpan balik utama
• Gambarlah diagram lingkaran sebab akibat yang menghubungkan stok, aliran, dan sumber informasi
• Tuliskan persamaan yang menentukan aliran
• Perkirakan parameter dan kondisi awal. 
• Simulasikan model dan analisis hasilnya.

Dalam contoh ini, persamaan yang mengubah dua stok melalui aliran adalah:

Persamaan dalam waktu diskrit

Daftar semua persamaan dalam waktu diskrit, dalam urutan pelaksanaannya di setiap tahun, untuk tahun 1 sampai 15 :

Hasil simulasi dinamis
Hasil simulasi dinamis menunjukkan bahwa perilaku sistem akan memiliki pertumbuhan pengadopsi yang mengikuti bentuk kurva-s klasik.
Peningkatan pengadopsi sangat lambat pada awalnya, kemudian pertumbuhan eksponensial untuk suatu periode, akhirnya diikuti oleh kejenuhan.

Gambar: Stok dinamis dan diagram alir model adopsi produk baru

Gambar: Nilai stok dan aliran selama bertahun-tahun = 0 hingga 15

Persamaan dalam waktu kontinu

Untuk mendapatkan nilai menengah dan akurasi yang lebih baik, model dapat berjalan dalam waktu yang berkelanjutan: kita mengalikan jumlah unit waktu dan membagi nilai secara proporsional yang mengubah tingkat stok. Dalam contoh ini kita mengalikan 15 tahun dengan 4 untuk mendapatkan 60 kuartal, dan kita membagi nilai arus dengan 4.
Membagi nilai adalah yang paling sederhana dengan metode Euler, tetapi metode lain dapat digunakan sebagai gantinya, seperti metode Runge–Kutta.

Daftar persamaan dalam waktu kontinu untuk trimester = 1 sampai 60 :

Mereka adalah persamaan yang sama seperti pada bagian Persamaan waktu diskrit di atas, kecuali persamaan 4.1 dan 4.2 diganti dengan yang berikut:

Dalam diagram stok dan aliran di bawah ini, aliran perantara 'Valve New adopters' menghitung persamaan:

Gambar: Stok dinamis dan diagram alir model adopsi produk baru dalam waktu kontinu

Aplikasi

Dinamika sistem memiliki beragam aplikasi di berbagai bidang seperti: Misalnya sistem kependudukan, pertanian, ekologi dan ekonomi yang seringkali saling berinteraksi. Dalam manajemen “terbelakang”, dinamika sistem digunakan sebagai alat untuk mengajarkan refleks berpikir sistem, menganalisis asumsi dan model mental, memperoleh wawasan kualitatif tentang cara kerja sistem, dan mengenali arketipe sistem yang tidak berfungsi.Penggunaan perangkat lunak memungkinkan simulasi model dinamika sistem, memungkinkan pengujian bagaimana-jika kebijakan tertentu untuk memahami perubahan dalam sistem dari waktu ke waktu. Dinamika sistem, mirip dengan pemikiran sistem, menciptakan diagram lingkaran sebab akibat, namun melangkah lebih jauh dan menggunakan simulasi untuk menguji perilaku sistem dan dampak dari kebijakan alternatif.Dinamika sistem juga digunakan dalam studi ketergantungan sumber daya dan masalah pengembangan produk.Minsky, pendekatan makroekonomi yang dikembangkan oleh ekonom Steve Keen, menggunakan dinamika sistem untuk memodelkan perilaku perekonomian global dari periode stabilitas hingga krisis keuangan yang tidak terduga pada tahun 2007-2008.

Contoh: Pertumbuhan dan penurunan perusahaan

Gambar: Causal loop diagram dari model yang memeriksa pertumbuhan atau penurunan perusahaan asuransi jiwa

Gambar di atas adalah diagram lingkaran sebab akibat dari model dinamika sistem yang dibuat untuk menganalisis pertumbuhan atau penurunan perusahaan asuransi jiwa di Inggris. Fitur penting dari diagram ini mencakup putaran umpan balik negatif yang disebut putaran balik (C), penggunaan batang ganda untuk menunjukkan penundaan yang signifikan antara sebab dan akibat, garis yang lebih tebal untuk mengidentifikasi putaran umpan balik dan koneksi untuk disorot, dan tingkat kesulitanuntuk pengambil keputusan dapat secara dinamis Memahami perilaku hanya dengan menggunakan gambar. Konvensi diagram dinamika sistem umumnya digunakan untuk menyampaikan informasi ini.

Contoh: gerak piston

1. Tujuan: mempelajari sistem batang penghubung engkol.
Kami ingin memodelkan sistem batang penghubung engkol melalui model sistem dinamis. Dua deskripsi lengkap yang berbeda dari sistem fisik dengan sistem persamaan terkait dapat ditemukan di sini (dalam bahasa Inggris) dan di sini (dalam bahasa Prancis); mereka memberikan hasil yang sama. Dalam contoh ini, engkol, dengan jari-jari variabel dan frekuensi sudut, akan menggerakkan piston dengan panjang batang penghubung variabel.

2. Pemodelan dinamis sistem: sistem sekarang dimodelkan, menurut logika dinamis sistem stok dan aliran.
Gambar di bawah ini menunjukkan diagram stok dan aliran

Gambar: Diagram stok dan aliran untuk sistem batang penghubung engkol

3. Simulasi: perilaku sistem dinamis batang penghubung engkol kemudian dapat disimulasikan.
Gambar selanjutnya adalah simulasi 3D yang dibuat menggunakan animasi prosedural. Variabel model menganimasikan semua bagian animasi ini: engkol, radius, frekuensi sudut, panjang batang, dan posisi piston.

Gambar: Animasi prosedural 3D dari sistem batang penghubung engkol yang dimodelkan 

Disadur dari : en.wikipedia.org