Perhitungan evolusioner

Dalam ilmu komputer, komputasi evolusioner adalah sebuah keluarga algoritme untuk optimasi global yang terinspirasi oleh evolusi biologis, dan subbidang kecerdasan buatan dan komputasi lunak yang mempelajari algoritme ini. Dalam istilah teknis, mereka adalah keluarga pemecah masalah trial and error berbasis populasi dengan karakter optimasi metaheuristik atau stokastik.

Dalam komputasi evolusioner, sekumpulan kandidat solusi awal dihasilkan dan diperbarui secara berulang. Setiap generasi baru dihasilkan dengan menghapus solusi yang kurang diinginkan secara stokastik, dan memperkenalkan perubahan acak kecil serta, tergantung pada metodenya, mencampurkan informasi orang tua. Dalam terminologi biologi, sebuah populasi solusi akan mengalami seleksi alam (atau seleksi buatan), mutasi, dan kemungkinan rekombinasi. Hasilnya, populasi akan berevolusi secara bertahap untuk meningkatkan kebugaran, dalam hal ini fungsi kebugaran yang dipilih dari algoritma.

Teknik komputasi evolusioner dapat menghasilkan solusi yang sangat optimal dalam berbagai pengaturan masalah, sehingga membuatnya populer dalam ilmu komputer. Banyak varian dan ekstensi yang tersedia, yang cocok untuk kelompok masalah dan struktur data yang lebih spesifik. Komputasi evolusioner juga terkadang digunakan dalam biologi evolusioner sebagai prosedur eksperimental in silico untuk mempelajari aspek-aspek umum dari proses evolusi secara umum.

Sejarah

Konsep meniru proses evolusi untuk memecahkan masalah berasal dari sebelum munculnya komputer, seperti ketika Alan Turing mengusulkan metode pencarian genetik pada tahun 1948. Mesin-u tipe-B Turing menyerupai jaringan saraf primitif, dan hubungan antara neuron dipelajari melalui semacam algoritma genetik. Mesin-u tipe P-nya menyerupai metode pembelajaran penguatan, di mana sinyal kesenangan dan rasa sakit mengarahkan mesin untuk mempelajari perilaku tertentu. Namun, makalah Turing tidak dipublikasikan hingga tahun 1968, dan ia meninggal pada tahun 1954, sehingga karya awal ini tidak banyak berpengaruh pada bidang komputasi evolusioner yang kemudian berkembang.

Komputasi evolusioner sebagai sebuah bidang dimulai dengan sungguh-sungguh pada tahun 1950-an dan 1960-an. Ada beberapa upaya independen untuk menggunakan proses evolusi dalam komputasi pada masa ini, yang berkembang secara terpisah selama kurang lebih 15 tahun. Tiga cabang muncul di tempat yang berbeda untuk mencapai tujuan ini: strategi evolusi, pemrograman evolusioner, dan algoritma genetika. Cabang keempat, pemrograman genetik, akhirnya muncul pada awal tahun 1990-an. Pendekatan-pendekatan ini berbeda dalam metode seleksi, mutasi yang diizinkan, dan representasi data genetik. Pada tahun 1990-an, perbedaan antara cabang-cabang historis tersebut mulai kabur, dan istilah 'komputasi evolusioner' diciptakan pada tahun 1991 untuk menunjukkan sebuah bidang yang mencakup keempat paradigma tersebut.

Pada tahun 1962, Lawrence J. Fogel memprakarsai penelitian Pemrograman Evolusioner di Amerika Serikat, yang dianggap sebagai upaya kecerdasan buatan. Dalam sistem ini, mesin keadaan berhingga digunakan untuk memecahkan masalah prediksi: mesin ini akan dimutasi (menambah atau menghapus keadaan, atau mengubah aturan transisi keadaan), dan yang terbaik dari mesin yang bermutasi ini akan berevolusi lebih lanjut di generasi mendatang. Mesin finite state terakhir dapat digunakan untuk menghasilkan prediksi saat dibutuhkan. Metode pemrograman evolusioner berhasil diterapkan pada masalah prediksi, identifikasi sistem, dan kontrol otomatis. Metode ini akhirnya diperluas untuk menangani data deret waktu dan memodelkan evolusi strategi permainan.

Pada tahun 1964, Ingo Rechenberg dan Hans-Paul Schwefel memperkenalkan paradigma strategi evolusi di Jerman. Karena teknik penurunan gradien tradisional menghasilkan hasil yang mungkin terjebak pada minima lokal, Rechenberg dan Schwefel mengusulkan agar mutasi acak (yang diterapkan pada semua parameter beberapa vektor solusi) dapat digunakan untuk menghindari minima ini. Solusi anak dihasilkan dari solusi induk, dan solusi yang lebih sukses dari keduanya disimpan untuk generasi selanjutnya. Teknik ini pertama kali digunakan oleh keduanya untuk menyelesaikan masalah optimasi dalam dinamika fluida. Awalnya, teknik optimasi ini dilakukan tanpa komputer, melainkan mengandalkan dadu untuk menentukan mutasi acak. Pada tahun 1965, perhitungan dilakukan sepenuhnya oleh mesin.

John Henry Holland memperkenalkan algoritma genetika pada tahun 1960-an, dan dikembangkan lebih lanjut di Universitas Michigan pada tahun 1970-an. Sementara pendekatan lain difokuskan untuk memecahkan masalah, Holland terutama bertujuan untuk menggunakan algoritma genetika untuk mempelajari adaptasi dan menentukan bagaimana adaptasi tersebut dapat disimulasikan. Populasi kromosom, yang direpresentasikan sebagai string bit, ditransformasikan oleh proses seleksi buatan, memilih bit 'alel' tertentu dalam string bit. Di antara metode mutasi lainnya, interaksi antara kromosom digunakan untuk mensimulasikan rekombinasi DNA antara organisme yang berbeda. Sementara metode sebelumnya hanya melacak satu organisme optimal pada satu waktu (membuat anak-anak bersaing dengan orang tua), algoritma genetika Holland melacak populasi besar (membuat banyak organisme bersaing setiap generasi).

Pada tahun 1990-an, sebuah pendekatan baru untuk komputasi evolusioner yang kemudian disebut pemrograman genetik muncul, yang antara lain dianjurkan oleh John Koza. Dalam kelas algoritme ini, subjek evolusi itu sendiri adalah program yang ditulis dalam bahasa pemrograman tingkat tinggi (telah ada beberapa upaya sebelumnya pada awal tahun 1958 untuk menggunakan kode mesin, namun tidak banyak berhasil). Bagi Koza, program-program tersebut adalah ekspresi Lisp S, yang dapat dianggap sebagai pohon sub-ekspresi. Representasi ini memungkinkan program untuk menukar sub-pohon, yang mewakili semacam pencampuran genetik. Program dinilai berdasarkan seberapa baik mereka menyelesaikan tugas tertentu, dan nilai tersebut digunakan untuk seleksi buatan. Induksi urutan, pengenalan pola, dan perencanaan merupakan aplikasi yang sukses dari paradigma pemrograman genetik.

Banyak tokoh lain yang berperan dalam sejarah komputasi evolusioner, meskipun karya mereka tidak selalu masuk ke dalam salah satu cabang sejarah utama bidang ini. Simulasi komputasi evolusi yang paling awal menggunakan algoritma evolusi dan teknik kehidupan buatan dilakukan oleh Nils Aall Barricelli pada tahun 1953, dengan hasil pertama yang dipublikasikan pada tahun 1954. Pelopor lain pada tahun 1950-an adalah Alex Fraser, yang mempublikasikan serangkaian makalah tentang simulasi seleksi buatan. Seiring dengan meningkatnya minat akademis, peningkatan dramatis dalam kekuatan komputer memungkinkan aplikasi praktis, termasuk evolusi otomatis program komputer. Algoritme evolusioner sekarang digunakan untuk memecahkan masalah multi-dimensi secara lebih efisien daripada perangkat lunak yang dihasilkan oleh perancang manusia, dan juga untuk mengoptimalkan desain sistem.

Teknik

Algoritme evolusioner
Algoritma evolusioner merupakan bagian dari komputasi evolusioner yang umumnya hanya melibatkan teknik-teknik yang mengimplementasikan mekanisme yang terinspirasi dari evolusi biologis seperti reproduksi, mutasi, rekombinasi, seleksi alam, dan bertahan hidup yang terkuat. Kandidat solusi untuk masalah optimasi berperan sebagai individu dalam sebuah populasi, dan fungsi biaya menentukan lingkungan tempat solusi "hidup" (lihat juga fungsi kebugaran). Evolusi populasi kemudian terjadi setelah penerapan operator di atas secara berulang-ulang.

Dalam proses ini, ada dua kekuatan utama yang menjadi dasar sistem evolusi: Rekombinasi (misalnya persilangan) dan mutasi menciptakan keragaman yang diperlukan dan dengan demikian memfasilitasi kebaruan, sementara seleksi bertindak sebagai kekuatan yang meningkatkan kualitas.

Banyak aspek dari proses evolusi yang bersifat stokastik. Informasi yang berubah karena rekombinasi dan mutasi dipilih secara acak. Di sisi lain, operator seleksi dapat bersifat deterministik atau stokastik. Dalam kasus terakhir, individu dengan kebugaran yang lebih tinggi memiliki peluang lebih tinggi untuk dipilih daripada individu dengan kebugaran yang lebih rendah, tetapi biasanya bahkan individu yang lemah pun memiliki peluang untuk menjadi orang tua atau bertahan hidup.

Algoritme evolusi dan biologi

Algoritma genetika memberikan metode untuk memodelkan sistem biologi dan biologi sistem yang terkait dengan teori sistem dinamik, karena digunakan untuk memprediksi keadaan sistem di masa depan. Ini hanyalah cara yang jelas (tetapi mungkin menyesatkan) untuk menarik perhatian pada karakter perkembangan biologi yang teratur, terkendali dengan baik, dan sangat terstruktur.

Namun, penggunaan algoritma dan informatika, khususnya teori komputasi, di luar analogi dengan sistem dinamis, juga relevan untuk memahami evolusi itu sendiri.

Pandangan ini memiliki manfaat untuk mengakui bahwa tidak ada kontrol pusat perkembangan; organisme berkembang sebagai hasil dari interaksi lokal di dalam dan di antara sel-sel. Gagasan yang paling menjanjikan tentang paralelisme program-pengembangan tampaknya adalah gagasan yang menunjuk pada analogi yang tampaknya dekat antara proses di dalam sel, dan operasi tingkat rendah komputer modern. Dengan demikian, sistem biologis seperti mesin komputasi yang memproses informasi input untuk menghitung keadaan berikutnya, sehingga sistem biologis lebih dekat dengan komputasi daripada sistem dinamik klasik.

Lebih jauh lagi, mengikuti konsep dari teori komputasi, proses mikro dalam organisme biologis pada dasarnya tidak lengkap dan tidak dapat diputuskan (kelengkapan (logika)), menyiratkan bahwa "ada lebih dari sekadar metafora kasar di balik analogi antara sel dan komputer."

Analogi komputasi juga meluas ke hubungan antara sistem pewarisan dan struktur biologis, yang sering dianggap mengungkap salah satu masalah paling mendesak dalam menjelaskan asal-usul kehidupan.

Automata evolusioner, sebuah generalisasi dari mesin Turing Evolusioner, telah diperkenalkan untuk menyelidiki sifat-sifat yang lebih tepat dari komputasi biologis dan evolusioner. Secara khusus, mereka memungkinkan untuk mendapatkan hasil baru tentang ekspresi komputasi evolusioner. Hal ini menegaskan hasil awal tentang ketidakpastian evolusi alami dan algoritma serta proses evolusi. Evolutionary finite automata, subkelas paling sederhana dari Evolutionary automata yang bekerja dalam mode terminal dapat menerima bahasa arbitrer melalui alfabet yang diberikan, termasuk bahasa yang dapat dihitung secara non-rekursif (misalnya, bahasa diagonalisasi) dan bahasa yang dapat dihitung secara rekursif tetapi tidak rekursif (misalnya, bahasa mesin Turing universal).

Disadur dari: en.wikipedia.org

Artikel "Digital supply chain: Roadmap development and application based on Industry 4.0 principles" yang ditulis oleh Júlio Fernandes, Luciana Paula Reis, dan Sérgio Evangelista Silva, membahas tentang pengembangan  roadmap  teknologi untuk mengintegrasikan prinsip, arsitektur, dan teknologi Industri 4.0 (I4.0) dalam mewujudkan Rantai Pasok Digital (Digital Supply Chain/DSC). Studi ini dilakukan di sebuah perusahaan di industri baja yang mengadopsi teknologi I4.0 untuk meningkatkan proses manajemen rantai pasoknya.

 Latar Belakang dan Motivasi Penelitian

Penelitian ini dilatarbelakangi oleh era digital baru yang didorong oleh revolusi industri keempat, yang ditandai dengan munculnya inovasi teknologi dengan berbagai aplikasi di perusahaan. Digitalisasi rantai pasok dipandang sebagai proses cerdas baru yang memberikan nilai tambah dengan menggunakan teknologi I4.0. Meskipun konsep DSC banyak dibahas, pemahaman tentang istilah ini masih dalam tahap awal. Kesenjangan penelitian terletak pada kurangnya karya empiris tentang pengembangan I4.0 dengan pedoman yang jelas untuk digitalisasi rantai pasok.

 Kerangka Teoretis

Artikel ini membahas konsep-konsep kunci seperti rantai pasok digital (DSC), prinsip dan arsitektur Industri 4.0, serta  roadmap  teknologi. DSC mengacu pada evolusi bagaimana rantai pasok tradisional mengimplementasikan I4.0 dalam proses mereka. Teknologi I4.0 mencakup  cloud computing, big data, internet of things ,  blockchain , kecerdasan buatan, dan lain-lain, untuk meningkatkan kinerja rantai pasok.

Prinsip-prinsip I4.0 dianggap sebagai indikator yang membantu dalam evaluasi terperinci dan implementasi teknologi dari paradigma teknologi ini dalam organisasi. Hermann, Pentek dan Otto (2016) mengusulkan enam prinsip I4.0: interoperabilitas, virtualisasi, desentralisasi keputusan, kemampuan  real-time , orientasi layanan, dan modularitas.

 Roadmap  teknologi menjadi salah satu alat manajemen yang paling banyak digunakan untuk adopsi teknologi baru.  Roadmap  ini memungkinkan manajer perusahaan untuk mengoptimalkan waktu adopsi teknologi digital baru dan berguna untuk mengidentifikasi kekuatan yang dapat mendorong masa depan perusahaan dalam skenario yang berbeda.

 Metodologi Penelitian

Penelitian ini menerapkan strategi studi kasus dengan pendekatan kualitatif di departemen rantai pasok sebuah perusahaan baja global di Brasil. Pengumpulan data dilakukan dalam tiga tahap: pertemuan penyelarasan awal, wawancara, dan lokakarya. Wawancara semi-terstruktur dilakukan sesuai dengan setiap lapisan  roadmap . Lokakarya menggunakan  brainstorming  berdasarkan hasil wawancara untuk menghasilkan peta akhir yang diusulkan.

 Temuan Penelitian Utama

Penelitian ini menghasilkan  roadmap  teknologi untuk digitalisasi rantai pasok, yang divalidasi dalam sebuah pabrik baja.  Roadmap  ini mencakup prinsip-prinsip I4.0, arsitektur teknologi, dan teknologi yang relevan untuk implementasi DSC.

     Prinsip I4.0:  Penelitian ini mengidentifikasi prinsip-prinsip I4.0 yang relevan untuk rantai pasok, seperti interoperabilitas dan kemampuan  real-time .

     Arsitektur Teknologi:  Arsitektur teknologi mengacu pada kombinasi teknologi yang digunakan perusahaan untuk menstandardisasi dan mengintegrasikan proses mereka.

     Roadmap Teknologi:   Roadmap  ini memberikan panduan bagi manajer untuk menyalurkan sumber daya mereka secara efisien dalam mengadopsi teknologi digital.

 Studi Kasus dan Angka-Angka

Studi ini dilakukan di sebuah perusahaan baja global di Brasil. Data dikumpulkan melalui wawancara dengan 12 profesional dari departemen pasokan dan intelijen. Hasilnya adalah  roadmap  teknologi yang membantu manajer untuk mengimplementasikan teknologi I4.0 dalam proses mereka. Sayangnya, artikel ini tidak memberikan angka-angka spesifik mengenai dampak keuangan atau operasional dari implementasi roadmap tersebut.

 Implikasi Teoretis dan Manajerial

Penelitian ini memberikan wawasan tentang bagaimana perusahaan dapat mengembangkan dan menerapkan  roadmap  teknologi untuk digitalisasi rantai pasok mereka. Ini juga menyoroti pentingnya menyelaraskan prinsip-prinsip I4.0 dengan arsitektur teknologi dan strategi bisnis perusahaan. Secara manajerial, artikel ini memberikan panduan praktis bagi perusahaan yang ingin mengadopsi teknologi digital dalam rantai pasok mereka.

 Keterbatasan dan Penelitian Mendatang

Penelitian ini memiliki beberapa keterbatasan, termasuk fokus pada satu perusahaan di industri baja. Penelitian mendatang dapat memperluas studi ini ke industri lain dan menggunakan pendekatan kuantitatif untuk mengukur dampak dari digitalisasi rantai pasok.

 Kesimpulan

Artikel ini menyimpulkan bahwa  roadmap  teknologi dapat membantu perusahaan dalam mengintegrasikan prinsip, arsitektur, dan teknologi I4.0 untuk mencapai DSC. Studi ini memberikan kontribusi berharga bagi pemahaman tentang bagaimana perusahaan dapat memanfaatkan teknologi digital untuk meningkatkan manajemen rantai pasok mereka.

 Sumber Artikel: Fernandes, J., Reis, L. P., & Silva, S. E. (2023). Digital supply chain: Roadmap development and application based on Industry 4.0 principles.  IFAC PapersOnLine ,  56 (2), 10339-10344.

Algoritma Genetika

Dalam ilmu komputer dan riset operasi, algoritma genetika (GA) adalah metaheuristik yang terinspirasi oleh proses seleksi alam yang termasuk dalam kelas yang lebih besar yaitu algoritma evolusioner (EA). Algoritma genetika biasanya digunakan untuk menghasilkan solusi berkualitas tinggi untuk masalah optimasi dan pencarian dengan mengandalkan operator yang terinspirasi secara biologis seperti mutasi, crossover, dan seleksi. Beberapa contoh aplikasi GA termasuk mengoptimalkan pohon keputusan untuk kinerja yang lebih baik, memecahkan teka-teki sudoku, optimasi hiperparameter, inferensi sebab akibat, dan lain-lain.

Metodologi

Masalah optimasi

Dalam algoritma genetika, sebuah populasi kandidat solusi (disebut individu, makhluk, organisme, atau fenotipe) untuk sebuah masalah optimasi berevolusi menuju solusi yang lebih baik. Setiap kandidat solusi memiliki sekumpulan properti (kromosom atau genotipe) yang dapat dimutasi dan diubah; secara tradisional, solusi direpresentasikan dalam bentuk biner sebagai string 0 dan 1, tetapi pengkodean lain juga dimungkinkan.

Evolusi biasanya dimulai dari populasi individu yang dibangkitkan secara acak, dan merupakan proses yang berulang, dengan populasi di setiap iterasi disebut generasi. Pada setiap generasi, kebugaran setiap individu dalam populasi dievaluasi; kebugaran biasanya merupakan nilai dari fungsi objektif dalam masalah optimasi yang sedang dipecahkan. Individu yang lebih fit dipilih secara stokastik dari populasi saat ini, dan genom setiap individu dimodifikasi (direkombinasi dan mungkin dimutasi secara acak) untuk membentuk generasi baru. Generasi baru dari kandidat solusi kemudian digunakan dalam iterasi algoritma berikutnya. Umumnya, algoritme akan berhenti ketika jumlah generasi maksimum telah dihasilkan, atau tingkat kebugaran yang memuaskan telah dicapai untuk populasi.

Algoritma genetika pada umumnya membutuhkan
Representasi standar dari setiap kandidat solusi adalah sebagai sebuah larik bit (disebut juga bit set atau bit string).Larik dengan tipe dan struktur lain dapat digunakan dengan cara yang sama. Sifat utama yang membuat representasi genetika ini nyaman adalah bagian-bagiannya mudah disejajarkan karena ukurannya yang tetap, yang memfasilitasi operasi crossover sederhana. Representasi panjang variabel juga dapat digunakan, tetapi implementasi persilangan lebih kompleks dalam kasus ini.

Representasi seperti pohon dieksplorasi dalam pemrograman genetik dan representasi bentuk grafik dieksplorasi dalam pemrograman evolusioner; campuran kromosom linier dan pohon dieksplorasi dalam pemrograman ekspresi gen.Setelah representasi genetik dan fungsi fitness didefinisikan, GA akan menginisialisasi populasi solusi dan kemudian memperbaikinya melalui aplikasi berulang dari operator mutasi, crossover, inversi, dan seleksi.

Inisialisasi
Ukuran populasi bergantung pada sifat masalah, tetapi biasanya berisi beberapa ratus atau ribuan solusi yang mungkin. Seringkali, populasi awal dibuat secara acak, sehingga memungkinkan seluruh kemungkinan solusi (ruang pencarian). Kadang-kadang, solusi dapat "diunggulkan" di area di mana solusi optimal kemungkinan besar akan ditemukan atau distribusi probabilitas pengambilan sampel disetel untuk fokus pada area-area yang lebih diminati.

Seleksi
Selama setiap generasi yang berurutan, sebagian dari populasi yang ada dipilih untuk direproduksi untuk generasi baru. Solusi individu dipilih melalui proses berbasis kebugaran, di mana solusi yang lebih bugar (yang diukur dengan fungsi kebugaran) biasanya lebih mungkin untuk dipilih. Metode seleksi tertentu menilai kecocokan setiap solusi dan secara khusus memilih solusi terbaik. Metode lain hanya menilai sampel acak dari populasi, karena proses sebelumnya mungkin sangat memakan waktu.

Fungsi kebugaran didefinisikan melalui representasi genetik dan mengukur kualitas solusi yang direpresentasikan. Fungsi kebugaran selalu bergantung pada masalah. Sebagai contoh, dalam masalah knapsack, seseorang ingin memaksimalkan nilai total objek yang dapat dimasukkan ke dalam knapsack dengan kapasitas tertentu. Representasi dari solusi dapat berupa sebuah larik bit, di mana setiap bit merepresentasikan objek yang berbeda, dan nilai dari bit tersebut (0 atau 1) merepresentasikan apakah objek tersebut ada di dalam ransel atau tidak. Tidak semua representasi seperti itu valid, karena ukuran objek bisa saja melebihi kapasitas ransel. Kecocokan solusi adalah jumlah nilai dari semua objek di dalam knapsack jika representasi tersebut valid, atau 0 jika tidak.

Dalam beberapa masalah, sulit atau bahkan tidak mungkin untuk mendefinisikan ekspresi fitness; dalam kasus ini, simulasi dapat digunakan untuk menentukan nilai fungsi fitness dari sebuah fenotipe (misalnya dinamika fluida komputasi digunakan untuk menentukan hambatan udara dari kendaraan yang bentuknya dikodekan sebagai fenotipe), atau bahkan algoritma genetika interaktif digunakan.

Operator genetika
Langkah selanjutnya adalah menghasilkan populasi generasi kedua dari solusi-solusi yang terpilih, melalui kombinasi operator genetik: crossover (juga disebut rekombinasi), dan mutasi.

Untuk setiap solusi baru yang akan dihasilkan, sepasang solusi "induk" dipilih untuk dikawinkan dari kumpulan solusi yang telah dipilih sebelumnya. Dengan menghasilkan solusi "anak" menggunakan metode persilangan dan mutasi di atas, solusi baru dibuat yang biasanya memiliki banyak karakteristik yang sama dengan "induknya". Orang tua baru dipilih untuk setiap anak baru, dan prosesnya berlanjut hingga populasi solusi baru dengan ukuran yang sesuai dihasilkan. Meskipun metode reproduksi yang didasarkan pada penggunaan dua orang tua lebih "terinspirasi oleh biologi", beberapa penelitian menunjukkan bahwa lebih dari dua "orang tua" menghasilkan kromosom yang lebih berkualitas.

Proses-proses ini pada akhirnya menghasilkan populasi kromosom generasi berikutnya yang berbeda dari generasi awal. Secara umum, rata-rata kebugaran akan meningkat dengan prosedur ini untuk populasi, karena hanya organisme terbaik dari generasi pertama yang dipilih untuk berkembang biak, bersama dengan sebagian kecil solusi yang kurang cocok. Solusi yang kurang cocok ini memastikan keanekaragaman genetik dalam kumpulan genetik orang tua dan oleh karena itu memastikan keanekaragaman genetik generasi anak-anak berikutnya.

Terdapat perbedaan pendapat mengenai pentingnya persilangan versus mutasi. Ada banyak referensi dalam Fogel (2006) yang mendukung pentingnya pencarian berbasis mutasi.Meskipun crossover dan mutasi dikenal sebagai operator genetik utama, ada kemungkinan untuk menggunakan operator lain seperti pengelompokan ulang, kolonisasi-kepunahan, atau migrasi dalam algoritme genetik.

Perlu dilakukan tuning parameter seperti probabilitas mutasi, probabilitas crossover, dan ukuran populasi untuk menemukan pengaturan yang masuk akal untuk kelas masalah yang sedang dikerjakan. Tingkat mutasi yang sangat kecil dapat menyebabkan penyimpangan genetik (yang bersifat non-ergodik). Laju rekombinasi yang terlalu tinggi dapat menyebabkan konvergensi prematur pada algoritma genetika. Laju mutasi yang terlalu tinggi dapat menyebabkan hilangnya solusi yang baik, kecuali jika seleksi elitis digunakan. Ukuran populasi yang memadai memastikan keanekaragaman genetik yang cukup untuk masalah yang dihadapi, tetapi dapat menyebabkan pemborosan sumber daya komputasi jika diatur ke nilai yang lebih besar dari yang dibutuhkan.

Heuristik
Selain operator utama di atas, heuristik lain dapat digunakan untuk membuat perhitungan lebih cepat atau lebih kuat. Heuristik spesiasi menghukum crossover antara kandidat solusi yang terlalu mirip; hal ini mendorong keanekaragaman populasi dan membantu mencegah konvergensi dini ke solusi yang kurang optimal.

Disadur dari: en.wikipedia.org

Psikologi

Heuristik, berasal dari bahasa Yunani εὑρίσκω (heurískō), yang berarti "menemukan", adalah proses dimana orang menggunakan jalan pintas mental untuk mengambil keputusan. Ini adalah strategi sederhana yang digunakan oleh manusia, hewan, organisasi, dan bahkan mesin untuk membuat penilaian cepat, mengambil keputusan, dan menemukan solusi terhadap masalah yang kompleks. Heuristik sering kali melibatkan pemfokusan pada aspek paling relevan dari suatu masalah atau situasi untuk merumuskan solusi. Meskipun heuristik dapat memberikan jawaban dan solusi yang tepat, heuristik tidak selalu benar atau lebih akurat.

Herbert A.Simon memperkenalkan konsep heuristik pada tahun 1950an, menunjukkan batasan pengambilan keputusan yang rasional. Pada tahun 1970-an, Amos Tversky dan Daniel Kahneman melanjutkan penelitian mereka tentang bias kognitif dan memperkenalkan model heuristik tertentu. Sementara beberapa orang mengklaim bahwa heuristik muncul semata-mata karena kemalasan, yang lain mengklaim bahwa proses ini bisa lebih tepat daripada keputusan berdasarkan faktor dan konsekuensi yang diketahui, terutama dalam situasi ketidakpastian.

Filsafat

Perangkat heuristik digunakan dalam entitas. Cerita, metafora, dan sejenisnya juga dapat disebut sebagai heuristik dalam konteks ini. Sebagai contoh klasik, gagasan utopia dalam karya Plato The Republic bukanlah sesuatu yang dikejar, melainkan panduan untuk memahami hubungan antar konsep dan implikasinya.

Selain itu, istilah heuristik sering digunakan untuk menggambarkan aturan, prosedur, atau metode praktis.Para filsuf sains menekankan pentingnya heuristik untuk pemikiran kreatif dan pembangunan teori ilmiah, termasuk karya seperti The Logic of Scientific Discovery karya Karl Popper dan tulisan lain oleh Imre Lakatos, Lindley Darden, dan William C. Wimsatt.

Hukum

Dalam teori hukum, khususnya teori hukum dan ekonomi, heuristik digunakan ketika analisis kasus per kasus dianggap tidak praktis tergantung kepentingan regulator. Misalnya saja dalam sistem regulasi sekuritas, asumsi bahwa semua investor bertindak dengan rasionalitas yang tinggi tidak selalu sesuai dengan kenyataan karena investor menghadapi keterbatasan kognitif akibat bias, heuristik, dan framing effect. Misalnya, batasan usia untuk meminum minuman beralkohol yaitu 21 tahun di Amerika Serikat dianggap sebagai batas heuristik dan sewenang-wenang karena sulit untuk menentukan kapan seseorang sudah cukup umur.

Berdasarkan undang-undang paten, pemberian monopoli sementara atas suatu ide penemuan dibenarkan untuk menciptakan insentif bagi para penemu. Namun, seperti dalam kasus usia minimum untuk meminum minuman beralkohol, batas 20 tahun untuk monopoli paten dianggap heuristik dan dapat dikatakan bahwa batas tersebut diatur secara berbeda tergantung pada jenis industrinya, misalnya dalam kasus paten perangkat lunak.

Ekonomi Perilaku

Heuristik dalam ekonomi perilaku mengacu pada strategi kognitif yang digunakan individu untuk menyederhanakan proses pengambilan keputusan dalam konteks ekonomi. Heuristik yang banyak diteliti adalah penahan dan penyesuaian, dimana penahan atau informasi awal dapat mempengaruhi penilaian di masa depan meskipun tidak ada kaitannya dengan keputusan yang diambil. Penyesuaian ini melibatkan perubahan bertahap terhadap peringkat awal. Fenomena ini diamati dalam berbagai konteks, termasukkeputusan keuangan, perilaku konsumen, dan negosiasi.

Para peneliti mencari strategi untuk mengurangi dampak penahan dan adaptasi, seperti menyediakan banyak jangkar, mendorong pembentukan jangkar alternatif, dan memberikan isyarat kognitif untuk meningkatkan kehati-hatian dalam pengambilan keputusan. Heuristik lain yang diperiksa mencakup keterwakilan, di mana orang-orang dikategorikan berdasarkan kesamaan dengan contoh-contoh yang umum, dan ketersediaan, di mana kemungkinan suatu peristiwa dinilai berdasarkan kemudahan kejadian tersebut terjadi pada mereka.

Disadur dari : en.wikipedia.org

Hill Climbing

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

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

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

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

Varian

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

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

Masalah Dataran Tinggi

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

Disadur dari: en.wikipedia.org

Pencarian Lokal Teriterasi

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

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

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

Algoritma Perturbasi

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

Gangguan tolok ukur

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

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

Optimalkan gangguan

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

Disadur dari: en.wikipedia.org