Metode Interatif

Dalam matematika komputasi, metode iteratif adalah prosedur matematika yang menggunakan nilai awal untuk menghasilkan rangkaian perkiraan solusi yang meningkat terhadap suatu kelas masalah, dengan perkiraan ke-n diturunkan dari perkiraan sebelumnya. Implementasi khusus dari metode iteratif, termasuk kriteria terminasi, adalah algoritma metode iteratif. Suatu metode iteratif dikatakan konvergen jika barisan-barisan yang bersesuaian konvergen pada pendekatan pertama tertentu. Biasanya, analisis konvergensi yang ketat secara matematis dilakukan secara berulang; Namun, prosedur berulang berdasarkan heuristik juga umum dilakukan.

Metode langsung, sebaliknya, berupaya memecahkan masalah dengan menggunakan serangkaian operasi terbatas.Jika tidak ada kesalahan pembulatan, metode langsung memberikan solusi yang akurat (misalnya menyelesaikan sistem persamaan linear dengan eliminasi Gaussian). Untuk persamaan nonlinier, metode iteratif seringkali merupakan satu-satunya pilihan. Namun, metode iteratif juga sering berguna untuk permasalahan linier dengan banyak variabel (terkadang hingga jutaan), dimana metode langsung akan terlalu mahal (dan dalam beberapa kasus tidak mungkin) bahkan dengan daya komputasi terbaik yang tersedia.

Titik tetap yang menarik

Jika persamaan dapat ditulis sebagai f(x) = x dan penyelesaian x adalah titik tarik-menarik tetap dari f, maka kita dapat memulai dari titik x1 pada daerah tarik-menarik x dan himpunan xn+ 1 = f(xn) untuk n 1, dan barisan {xn} n 1 akan konvergen untuk menyelesaikan x. Di sini xn adalah pendekatan atau iterasi ke-n dari x dan xn+1 adalah iterasi berikutnya atau n+1 x. Alternatifnya, metode numerik sering kali menggunakan eksponen dalam tanda kurung. agar tidak mengalihkan perhatian dari petunjuk yang mempunyai arti lain. (Contoh: x(n+1) = f(x(n)).) Jika fungsi f dapat terdiferensiasi kontinu, syarat yang cukup untuk konvergensi adalah bahwa jari-jari spektral turunan dibatasi secara ketat oleh kesatuan di sekitar titik tetap.Jika kondisi ini terpenuhi pada suatu titik tertentu, maka harus ada lingkungan yang cukup kecil (cekungan daya tarik).

Sistem linier

Untuk sistem persamaan linier, dua kelas utama metode iteratif adalah metode iteratif stasioner dan metode subruang Krylov yang lebih umum.

Metode iteratif stasioner

pengantar

Metode iteratif stasioner menyelesaikan sistem linier dengan operator yang mendekati operator aslinya; dan berdasarkan kesalahan pengukuran pada hasil (sisa), buatlah “persamaan koreksi” yang proses ini diulangi. Meskipun metode ini mudah untuk diturunkan, diterapkan, dan dianalisis, konvergensi hanya dijamin untuk kelas matriks tertentu.

Definisi

Sebuah metode iteratif didefinisikan oleh

dan untuk sistem linier tertentu  dengan solusi eksak kesalahan oleh

Metode iteratif disebut linier jika terdapat matriks sedemikian itu

dan matriks ini disebut matriks iterasi. Metode iteratif dengan matriks iterasi tertentu  disebut konvergen jika berikut ini berlaku

Sebuah teorema penting menyatakan bahwa untuk suatu metode iteratif dan matriks iterasinya konvergen jika dan hanya jika jari-jari spektralnya lebih kecil daripada kesatuan, yaitu

Metode iteratif dasar bekerja dengan membagi matriks menjadi

dan di sini matriks  harus mudah dibalik. Metode iteratif sekarang didefinisikan sebagai

Dari sini berikut bahwa matriks iterasi diberikan oleh

Contoh

Contoh dasar metode iteratif stasioner menggunakan pemisahan matriks seperti

di mana hanyalah bagian diagonal dari , dan adalah bagian segitiga bawah dari . Masing-masing, adalah bagian segitiga atas dari .

Metode Richardson:

Metode Jacobi:

Metode Jacobi teredam:

Metode Gauss–Seidel:

Metode over-relaksasi (SOR):

Relaksasi berlebihan berurutan (SSOR):

Metode iteratif stasioner linier juga disebut metode relaksasi.

Metode subruang Krylov

Metode subruang Krylov terdiri dari pembuatan basis dari barisan pangkat matriks yang berurutan dikalikan dengan sisa awal (urutan Krylov). Perkiraan solusi kemudian dibuat dengan meminimalkan residu di subruang yang dibuat. Metode prototipe kelas ini adalah metode gradien konjugasi (CG), yang mengasumsikan bahwa matriks sistem A terdefinisi positif secara simetris. Untuk nilai simetris (dan mungkin tak terhingga), metode residu minimum(MINRES) dapat digunakan. Untuk matriks non-simetris, metode seperti metode residu terkecil yang digeneralisasi (GMRES) dan metode gradien bikonjugasi (BiCG) telah diturunkan.

Konvergensi metode subruang Krylov

Karena metode ini membentuk basis, terbukti bahwa metode tersebut konvergen dalam N iterasi, di mana N adalah ukuran sistem. Namun, dengan adanya kesalahan pembulatan, pernyataan ini tidak berlaku; apalagi, dalam praktiknya N bisa sangat besar, dan proses iteratif mencapai akurasi yang cukup jauh lebih awal. Analisis metode ini sulit, tergantung pada fungsi spektrum operator yang rumit.

Prakondisi

Operator aproksimasi yang muncul dalam metode iteratif stasioner juga dapat digabungkan dalam metode subruang Krylov seperti GMRES (sebagai alternatif, metode Krylov yang telah diprakondisikan dapat dianggap sebagai percepatan metode iteratif stasioner), di mana mereka menjadi transformasi dari operator asli ke kondisi yang mungkin lebih baik. satu. Konstruksi preconditioners adalah area penelitian yang besar.

Sejarah

Jamshīd al-Kāsh menggunakan metode iteratif untuk menghitung sinus 1° dan dalam Risalah tentang Akord dan Sinus dengan sangat presisi. Salah satu metode berulang pertama untuk menyelesaikan sistem linier muncul dalam surat dari Gauss kepada seorang siswa. Dia mengusulkan penyelesaian sistem persamaan 4 x 4 dengan berulang kali mencari suku dengan sisa terbesar.

Teori metode iteratif stasioner tertanam kuat dalam karya D.M. Muda sejak tahun 1950-an. Metode gradien konjugasi juga ditemukan pada tahun 1950-an, terlepas dari pengembangannya oleh Cornelius Lanczos, Magnus Hestenes dan Eduard Stiefel, namun sifat dan penerapannya masih sedikit dipahami pada saat itu. Baru pada tahun 1970-an diketahui bahwa metode adjoint bekerja sangat baik untuk persamaan diferensial parsial, khususnya persamaan elips.

Disadur dari: en.wikipedia.org

Feedback (Umpan Balik)

Feedback (Umpan balik) terjadi ketika keluaran suatu sistem kembali menjadi masukan, sehingga membentuk rantai sebab-akibat yang membentuk suatu putaran atau rangkaian. Dalam sistem umpan balik, gagasan kausalitas harus ditangani dengan hati-hati karena interaksi antara sistem pertama dan kedua saling mempengaruhi dan menciptakan argumen melingkar yang membuat penalaran berdasarkan sebab dan akibat menjadi sulit. Hal ini memerlukan analisis menyeluruh terhadap keseluruhan sistem. Karl Johan Åström dan Richard M. Murray menjelaskan bahwa umpan balik dalam bisnis adalah transmisi informasi evaluatif atau korektif tentang tindakan, peristiwa, atau proses ke sumber asli atau sumber pengendali.

Sejarah

Umpan balik memiliki sejarah yang panjang, dimulai dengan mekanisme pengaturan mandiri yang sudah ada sejak zaman kuno. Ide umpan balik pertama kali muncul dalam teori ekonomi Inggris pada abad ke-18, namun tidak diakui sebagai abstraksi universal pada saat itu. Katup pelampung, ditemukan pada tahun 270 SM. Di Mesir, ini adalah perangkat umpan balik buatan pertama yang diketahui. Prinsip umpan balik tercermin dalam mekanisme ini, di mana ketinggian air yang rendah membuka katup, menciptakan putaran umpan balikyang menjaga ketinggian air tetap konstan. Pengatur sentrifugal, yang digunakan sejak abad ke-17 untuk mengendalikan kincir angin, menjadi semakin canggih dengan desain James Watt pada tahun 1788, menghasilkan pengendalian kecepatan yang lebih tepat pada mesin uap.Pada tahun 1868, James Clerk Maxwell berkontribusi pada teori klasik kontrol umpan balik dengan artikel “On Governors.” Istilah “umpan balik” pertama kali digunakan oleh Karl Ferdinand Braun pada tahun 1909 dan merujuk pada kopling yang tidak diinginkan dalam sirkuit elektronik.

Pada tahun 1912, penggunaan umpan balik yang disengaja pada amplifier elektronik menghasilkan peningkatan penguatan, dan istilah ini menjadi umum pada tahun 1920. Sejak tahun 1940-an, sibernetika berfokus pada studi tentang mekanisme umpan balik kausal melingkar. Selama bertahun-tahun telah terjadi perdebatan mengenai definisi umpan balik, dengan Ashby (1956) menganjurkan definisi "sirkularitas tindakan", sementara Ramaprasad (1983) lebih menekankan penggunaannya dalam teori manajemen, mendefinisikannya sebagai informasi tentang kesenjangan dalam organisasi. umpan balik untuk mengubah sistem. Menutup kesenjangan melalui tindakan yang tepat.

Jenis

Feedback Positif dan Negatif

Umpan balik positif terjadi bila sinyal keluaran sefasa dengan sinyal masukan, sedangkan umpan balik negatif terjadi bila sinyal keluaran sefasa 180° dengan sinyal masukan. Sebagai contoh umpan balik negatif, perhatikan sistem kendali jelajah pada mobil dengan target kecepatan, seperti batas kecepatan. Kecepatan mobil diukur dengan speedometer dan umpan balik negatif digunakan untuk memperbaiki kesalahan kecepatan dengan mengatur throttle dan mengontrol aliran bahan bakar ke mesin.

Istilah “positif” dan “negatif” sehubungan dengan umpan balik sudah digunakan sebelum Perang Dunia Kedua. Gagasan umpan balik positif dimulai pada tahun 1920-an dan dikaitkan dengan sirkuit regeneratif.Pada tahun 1934, Harold Stephen Black merinci penggunaan umpan balik negatif dalam amplifier elektronik, dengan umpan balik positif meningkatkan penguatan sementara umpan balik negatif menurunkannya. Namun, kebingungan segera muncul karena perbedaan penafsiran istilah tersebut oleh para peneliti seperti Friis dan Jensen, yang membedakan umpan balik berdasarkan pengaruhnya terhadap penguatan, bukan tanda dari umpan balik itu sendiri. James Clerk Maxwell sebelumnya telah menjelaskan konsep umpan balikmelalui pergerakan komponen yang terkait dengan pengatur sentrifugal pada mesin uap, membedakan faktor penyebab peningkatan kebisingan atau amplitudo dengan faktor penyebab penurunan kualitas yang sama.

Terminologi

Istilah umpan balik positif dan negatif memiliki definisi berbeda tergantung pada disiplin ilmu yang digunakan. Definisi pertama mengacu pada perubahan jarak antara nilai acuan dengan nilai sebenarnya suatu parameter atau karakteristik, dimana jarak yang bertambah dianggap positif dan jarak yang berkurang dianggap negatif. Definisi kedua mengacu pada valensi tindakan atau efek umpan balik, dimana tindakan yang membuat penerimanya senang dipandang positif, sedangkan tindakan yang membuat penerimanya tidak bahagia dipandang negatif.

Namun, timbul kebingungan karena istilah ini dapat memiliki arti berbeda tergantung konteksnya. Beberapa penulis menggunakan istilah alternatif seperti penguatan diri dan koreksi diri, penguatan dan keseimbangan, peningkatan dan pengurangan kesenjangan, atau regeneratif dan degeneratif. Lebih jauh lagi, dalam definisi kedua, beberapa penulis menganjurkan penggunaan penguatan atau hukuman positif dan negatif daripada umpan balik.

Kebingungan ini mungkin disebabkan oleh sifat umpan balik yang kompleks, yang dapat digunakan untuk memberi informasi atau memotivasi dan mencakup komponen kualitatif dan kuantitatif. Banyak kebingungan juga muncul dari kenyataan bahwa bahkan dalam disiplin ilmu yang sama, istilah “umpan balik positif” atau “umpan balik negatif” dapat digunakan secara berbeda tergantung pada bagaimana nilai diukur atau dirujuk.Kebingungan ini mungkin disebabkan oleh sifat umpan balik yang kompleks, yang dapat digunakan untuk memberi informasi atau memotivasi dan mencakup komponen kualitatif dan kuantitatif. Banyak kebingungan juga muncul dari kenyataan bahwa bahkan dalam disiplin ilmu yang sama, istilah “umpan balik positif” atau “umpan balik negatif” dapat digunakan secara berbeda tergantung pada bagaimana nilai diukur atau dirujuk.

Aplikasi

Matematika dan Sistem Dinamik

Dengan menggunakan properti umpan balik, perilaku sistem dapat diubah untuk memenuhi kebutuhan aplikasi. Sistem dapat dijaga agar tetap stabil, responsif, atau konstan. Hal ini menunjukkan bahwa sistem dinamis dengan umpan balik di tepi kekacauan akan mengalami adaptasi.

Fisika

Sistem fisik memberikan umpan balik melalui interaksi timbal balik dari bagian-bagiannya. Umpan balik juga relevan untuk pengaturan kondisi eksperimental, pengurangan kebisingan, dan kontrol sinyal. Termodinamika sistem yang dikendalikan umpan balik telah menarik perhatian para fisikawan sejak zaman Maxwell, dengan kemajuan terkini mengenai konsekuensi pengurangan entropi dan peningkatan daya.

Biologi

Dalam sistem biologis seperti organisme, ekosistem, atau biosfer, banyak parameter yang harus dikontrol dalam rentang sempit di sekitar nilai optimal dalam kondisi lingkungan tertentu. Perubahan nilai parameter dapat disebabkan oleh perubahan lingkungan internal dan eksternal, dan beberapa kondisi lingkungan memerlukan penyesuaian rentang agar sistem dapat berfungsi. Sistem biologis menggunakan loop kontrol positif dan negatif untuk mempertahankan nilai parameter optimal. Contoh seperti osilasi insulinmenggambarkan salah satu mekanisme ini.

Integritas jaringan dalam sistem biologis dipertahankan melalui interaksi umpan balik antara tipe sel yang berbeda dengan mediator seperti molekul adhesi.Pada kanker, kegagalan mekanisme umpan balik utama dapat mengubah fungsi jaringan. Umpan balik juga memainkan peran penting dalam respon imun dan pemulihan dari infeksi dan cedera. Mekanisme umpan balik pertama kali dijelaskan pada bakteri, dan pada operon genetik, umpan balik bisa positif atau negatif.

Umpan balik dalam skala yang lebih besar dapat mempunyai efek menstabilkan populasi hewan, namun juga dapat mengarah pada siklus predator-mangsa. Dalam zimologi, umpan balik berfungsi sebagai pengaturan aktivitas enzimatik oleh produk hilir atau metabolit dalam jalur metabolisme.Sumbu hipotalamus-hipofisis-adrenal dikendalikan oleh umpan balik positif dan negatif.

Dalam psikologi, umpan balik positif terjadi ketika suatu stimulus memicu pelepasan suatu hormon, yang kemudian memicu pelepasan hormon lain, sehingga membentuk putaran umpan balik positif. Misalnya, orang yang mudah tersipu malu mengalami “siklus rasa malu” di mana kesadaran akan rasa malu memicu rasa malu lebih lanjut, sehingga membentuk siklus yang terus berlanjut.

Sumber: id.wikipedia.org

Matematika komputasi

Matematika komputasi memainkan peran penting dalam hubungan antara matematika dan ilmu komputer, terutama dalam pengembangan algoritma, metode numerik, dan perhitungan simbolik. Di bidang matematika komputasi terapan, fokusnya adalah pada penggunaan konsep matematika untuk meningkatkan dan mengoptimalkan penggunaan komputer dalam konteks matematika terapan. Ini melibatkan penerapan matematika untuk memecahkan masalah dunia nyata dan merancang algoritma yang efisien.

Selain itu, komputasi matematis juga mencakup penggunaan komputer dalam studi masalah matematika berbasis komputer, pencarian metode komputasi matematis yang efisien seperti aljabar komputer, dan teori kompleksitas, yang memperhitungkan perhitungan yang dapat dilakukan dengan menggunakan teknologi yang tersedia. Selain itu, matematika komputasi juga tentang melihat bukti-bukti pendukung, yaitu pembuktian matematis yang dapat dilakukan dengan komputer.Secara umum, matematika komputasi adalah pendekatan holistik yang menggabungkan matematika dan ilmu komputer untuk memecahkan berbagai tantangan matematika dan komputasi dunia nyata.

Bidang-bidang matematika komputasi

Matematika komputasi menjadi bagian tersendiri dari matematika terapan pada awal 1950-an. Sekarang, matematika komputasi memiliki arti atau meliputi:

• Ilmu komputasi, dikenal juga sebagai komputasi ilmiah atau teknik komputasi
• Bagian matematika dari komputasi ilmiah, khususnya analisis numerik, teori metode numerik
• Kompleksitas komputasi
• Aljabar komputer dan sistem aljabar komputer
• Linguistik komputasi, yaitu penggunaan teknik mathematika dan komputer dalam bahasa alami
• Geometri aljabar komputasi
• Teori grup komputasi
• Geometri komputasi
• Teori bilangan komputasi
• Topologi komputasi
• Statistika komputasi
• Teori informasi algoritmik
• Teori permainan algoritmik
• Mathematika ekonomi, yaitu penggunaan matematika dalam ekonomi, finansial dan akuntansi.

Contoh Penerapan Matematika Komputasi

Salah satu contoh penerapan matematika komputasi adalah dalam bidang ilmu komputer, khususnya dalam pengembangan algoritma dan pemodelan permasalahan kompleks. Sebagai contoh, dalam dunia kecerdasan buatan, matematika komputasi digunakan untuk merancang algoritma pembelajaran mesin yang dapat memproses dan menganalisis data besar untuk menghasilkan model yang dapat melakukan prediksi atau pengenalan pola.

Dalam simulasi kejadian fisika atau dinamika sistem kompleks, matematika komputasi juga sangat penting. Misalnya, dalam simulasi cuaca atau iklim, persamaan diferensial parsial dan metode numerik digunakan untuk menggambarkan perubahan kondisi atmosfer dan memprediksi pola cuaca di masa depan.Selain itu, dalam bidang keuangan, matematika komputasi dapat digunakan untuk mengembangkan model matematika yang kompleks untuk memahami perilaku pasar keuangan, mengevaluasi risiko investasi, dan merancang strategi keuangan yang optimal.

Dalam dunia kriptografi, matematika komputasi memainkan peran kunci dalam merancang algoritma enkripsi yang aman, pengujian primalitas, dan pengembangan teknologi keamanan informasi lainnya.Penerapan matematika komputasi juga dapat ditemukan dalam pengembangan perangkat lunak dan pemrosesan data besar, di mana teknik-teknik matematika seperti analisis numerik, aljabar linier numerik, dan metode optimisasi digunakan untuk meningkatkan kinerja algoritma dan sistem komputasi.

Disadur dari: en.wikipedia.org

Algoritma semut

Diperkenalkan oleh Moyson dan Manderick dan dikembangkan secara ekstensif oleh Marco Dorigo, algoritma Ant adalah teknik probabilistik untuk memecahkan masalah komputasi dengan menemukan jalur terbaik melalui grafik. Algoritme ini terinspirasi oleh perilaku semut saat mereka mencari jalan dari koloni menuju makanan.

Di dunia nyata, semut berkeliaran secara acak dan ketika menemukan makanan, mereka kembali ke koloninya, mengirimkan sinyal melalui jejak feromon. Ketika semut lain menemukan jejaknya, mereka tidak lagi berkeliaran secara acak tetapi mengikuti jejak tersebut dan kembali serta memperkuatnya ketika mereka akhirnya menemukan makanan.

Namun, seiring berjalannya waktu, jejak feromon akan hilang dan kekuatan tarik-menariknya akan berkurang. Semakin lama semut bergerak bolak-balik sepanjang jalur ini, semakin lama pula feromonnya menguap. Sebagai perbandingan, jalur pendek akan lebih cepat sejajar dan oleh karena itu kepadatan feromon tetap tinggi karena ia bergerak secepat penguapannya.Penguapan feromon juga mempunyai keuntungan dalam menghindari konvergensi menuju solusi optimal lokal. Jika tidak terjadi penguapan, jalur yang dipilih semut pertama akan cenderung terlalu menarik bagi semut berikutnya. Dalam kasus seperti ini, eksplorasi ruang solusi menjadi terbatas.

Jadi jika seekor semut menemukan jalur yang baik (jalur pendek) dari koloni menuju sumber makanan, semut lain akan mengikuti jalur tersebut, dan pada akhirnya semua semut akan mengikuti satu jalur. Ide dari algoritma koloni semut adalah untuk meniru perilaku ini melalui “semut buatan” yang berjalan mengelilingi grafik yang mewakili masalah yang harus dipecahkan

.Algoritma optimisasi koloni semut telah digunakan untuk menghasilkan penyelesaian yang mendekati optimal pada masalah salesman yang melakukan perjalanan. Algoritme semut lebih menguntungkan daripada pendekatan penguatan tiruan (simulaten annealing) dan algoritme genetik saat grafik mungkin berubah secara dinamis; algoritme koloni semut dapat berjalan secara kontinu dan menyesuaikan dengan perubahan secara waktu nyata (real time). Hal ini menarik dalam routing jaringan dan sistem transportasiurban.

Algoritma dan Rumus 

Dalam algoritma optimasi koloni semut, semut buatan bertindak sebagai agen komputasi sederhana yang tujuannya adalah menemukan solusi optimal untuk masalah optimasi yang diberikan. Untuk menerapkan algoritma ini, masalah optimasi harus diubah menjadi masalah pencarian jalur terpendek dalam graf berbobot. Pada langkah pertama setiap iterasi, setiap semut secara stokastik membangun solusi dengan menyusun rangkaian sisi dalam grafik. Langkah kedua adalah membandingkan jalur yang ditemukan oleh semut yang berbeda. Langkah terakhir adalah memperbarui nilai feromon pada setiap sisi grafik.Dengan pendekatan ini, setiap semut berkontribusi dalam pencarian solusi optimal, menciptakan kolaborasi dan kemampuan beradaptasi untuk menemukan jalur terpendek menuju masalah optimasi tertentu.

Aplikasi

Algoritme optimasi koloni semut telah diterapkan pada banyak masalah optimasi kombinatorial mulai dari penugasan kuadrat hingga pelipatan protein atau perutean kendaraan, dan banyak metode turunan telah disesuaikan dengan masalah dinamis dalam variabel nyata, masalah stokastik, tujuan ganda, dan implementasi paralel. Ini juga telah digunakan untuk menemukan solusi yang mendekati optimal terhadap masalah penjual. Mereka memiliki keunggulan dibandingkan pendekatan simulasi anildan algoritma genetika untuk masalah serupa ketika grafik dapat berubah secara dinamis; Algoritma koloni semut dapat berjalan terus menerus dan beradaptasi terhadap perubahan secara real time. Hal ini menarik untuk perutean jaringan dan sistem transportasi perkotaan.

Algoritma ACO, seperti Ant System, mengimplementasikan seperangkat aturan yang terinspirasi oleh perilaku semut biologis. Setiap semut dalam algoritma ini memiliki tujuan untuk mengunjungi setiap kota tepat satu kali dalam perjalanan yang dipilih. Konsep visibilitas diterapkan, dengan kota-kota yang lebih jauh mempunyai kemungkinan yang lebih kecil untuk dipilih, hal ini mencerminkan kecenderungan semut untuk memilih jalur yang lebih dekat. Selain itu, keberhasilan suatu tepi dalam melakukan perjalanan dipengaruhi oleh kekuatan jejak feromon yang ada pada tepi tersebut. Semakin kuat jejak feromon, semakin besar kemungkinan semut memilih tepian tersebut.

Setelah menyelesaikan perjalanannya, semut menyimpan feromon tambahan di semua sisi jalurnya, terutama jika perjalanannya singkat.Hal ini mencerminkan cara semut biologis meninggalkan jejak feromon untuk memandu temannya menuju sumber daya yang mereka temukan. Namun, untuk menghindari konvergensi menuju solusi optimal lokal, jejak feromon menghilang setelah setiap iterasi. Pendekatan ini menciptakan dinamika yang mirip dengan siklus alami semut biologis, di mana feromon yang ditinggalkan semut sebelumnya secara bertahap berkurang seiring berjalannya waktu. Dengan menerapkan aturan-aturan ini, algoritma ACO menghasilkan totalsolusi optimal atau mendekati optimal terhadap masalah penjual yang kompleks. 

Masalah Penjadwalan

Permasalahan perencanaan produksi meliputi Sequential Order Problem (SOP), Job Shop Scheduling Problem (JSP), Open Shop Scheduling Problem (OSP), Permutation Flow Shop Problem (PFSP), Single Machine Total Lateness Problem (SMTTP) dan masalah penundaan. Single Machine Weighted Total (SMTWTP), Resource Constrained Project Scheduling Problem (RCPSP), Group Shop Scheduling Problem (GSP), Single Machine Total Delay Problem dengan Time Sequence Dependent Configuration(SMTTPDST), Multistage Flow Shop Scheduling Problem (MFSP) dengan Sequence Waktu Pengaturan/perubahan yang bergantung dan masalah Perencanaan Urutan Perakitan (ASP).

Masalah perutean kendaraan 

Permasalahan pada domain routing kendaraan mencakup berbagai aspek seperti capacity vehicle routing problem (CVRP), multi-depot vehicle routing problem (MDVRP), periodic vehicle routing problem (PVRP), split delivery vehicle routing problem (SDVRP) dan permasalahan berkendara. kendaraan. Masalah Stokastik (SVRP), Masalah Perutean Kendaraan dengan Penjemputan dan Pengantaran (VRPPD), Masalah Perutean Kendaraan dengan Jendela Waktu (VRPTW), Masalah Perutean KendaraanBergantung Waktu dengan Waktu Jendela Waktu (TDVRPTW) dan Masalah Perutean Kendaraan dengan Waktu dan Waktu Pekerja Layanan Multi-Jendela (VRPTWMS).

Sumber: id.wikipedia.org

Algoritme genetik

Algoritma genetika adalah teknik pencarian dalam ilmu komputer untuk menemukan solusi perkiraan untuk masalah optimasi dan pencarian. Algoritma genetika adalah kelas khusus dari algoritma evolusi yang menggunakan teknik yang terinspirasi oleh biologi evolusi seperti pewarisan, mutasi, seleksi alam dan rekombinasi (atau persilangan). Algoritma genetika pertama kali dikembangkan pada tahun 1970an oleh John Holland di New York, AS. Dia, murid-muridnya dan rekan-rekannya menerbitkan sebuah buku pada tahun 1975 berjudul “Adaptasi dalam Sistem Alam dan Buatan.”

Algoritme genetik biasanya diimplementasikan sebagai simulasi komputer di mana populasi representasi abstrak (disebut kromosom) dari solusi potensial (disebut unit) terhadap masalah optimasi berkembang menuju solusi yang lebih baik. Secara tradisional, solusi dalam format biner direpresentasikan sebagai string "0" dan "1", meskipun berbagai pengkodean juga dimungkinkan.Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi.

Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritme.

Prosedur Algoritma Genetik

Algoritma genetika umum memerlukan definisi dua hal: (1) representasi genetik dari solusi, (2) fungsi kemampuan untuk mengevaluasinya.

Representasi defaultnya adalah array bit. Dengan cara yang sama, Anda dapat menggunakan array dengan tipe dan struktur lain. Alasan utama keakuratan representasi genetik ini adalah karena bagian-bagiannya dapat dengan mudah disusun karena ukurannya yang konstan, sehingga memudahkan operasi persilangan yang sederhana. Representasi panjang variabel juga digunakan, namun dalam kasus ini implementasi crossover lebih kompleks.Representasi pohon dipelajari dalam pemrograman genetik dan representasi bebas di HBGA.

Fungsi kapasitas ditentukan berdasarkan representasi genetik dan mengukur kualitas solusi yang disajikan. Fungsi kapasitas selalu bergantung pada masalahnya. Misalnya saja jika kita ingin memaksimalkan jumlah barang (benda) yang dapat ditampung dalam tas ransel dengan kapasitas tetap tertentu. Representasi solusinya dapat berupa bit array, dimana setiap bit merepresentasikan objek yang berbeda dan nilai bit (0 atau 1) menggambarkan apakah objek tersebut berada di dalam backpack atau tidak.Tidak semua representasi seperti itu berhasil karena ukuran benda tersebut mungkin melebihi kapasitas ransel.

Kapasitas solusi, jika direpresentasikan dengan benar, adalah jumlah dari nilai semua benda di dalam ransel, jika tidak maka akan menjadi 0. Dalam beberapa soal, mendefinisikan simbol kapasitas sulit atau tidak mungkin, sehingga IGA digunakan dalam kasus ini. .Setelah representasi genetik dan fungsi kebugaran ditentukan, algoritme genetika memproses inisialisasi acak populasi pada resolusi dan memperbaikinya dengan menerapkan operator mutasi, persilangan, dan seleksi berulang kali.

Secara sederhana, algoritme umum dari algoritme genetik ini dapat dirumuskan menjadi beberapa langkah, yaitu:

1. Membentuk suatu populasi individual dengan keadaan acak
2. Mengevaluasi kecocokan setiap individual keadaan dengan hasil yang diinginkan
3. Memilih individual dengan kecocokan yang tertinggi
4. Bereproduksi, mengadakan persilangan antar individual terpilih diselingi mutasi
5. Mengulangi langkah 2 - 4 sampai ditemukan individual dengan hasil yang diinginkan

Sumber: id.wikipedia.org

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