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

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

Feasible Region

Dalam optimasi matematis, wilayah, himpunan, ruang pencarian, atau ruang solusi yang layak adalah himpunan semua titik yang mungkin (kumpulan nilai dari variabel yang dipilih) dari suatu masalah optimasi yang memenuhi batasan masalah tersebut. , yang mungkin mengandung kesenjangan, persamaan dan ketidaksetaraan. pembatasan bilangan bulat. Ini adalah rangkaian solusi pertama yang mungkin untuk mengatasi masalah tersebut sebelum mempersempit kelompok kandidat.

Misalnya, pertimbangkan masalah meminimalkan fungsi sehubungan dengan variabel dan , tunduk pada dan Di sini himpunan layak adalah himpunan pasangan (x,y) yang nilai x paling sedikit 1 dan paling banyak 10 dan nilai y paling sedikit 5 dan paling banyak 12. Himpunan masalah yang layak terpisah dari fungsi tujuan, yang menyatakan kriteria yang akan dioptimalkan dan yang dalam contoh di atas adalah

Dalam banyak permasalahan, himpunan layak mencerminkan batasan bahwa satu atau lebih variabel tidak boleh negatif. Untuk permasalahan pemrograman yang hanya menggunakan bilangan bulat, himpunan bilangan bulat (atau bagiannya) adalah himpunan yang diperbolehkan. Dalam permasalahan program linier, himpunan layak adalah politop cembung: wilayah ruang multidimensi yang batasnya dibentuk oleh bidang hiper dan simpulnya adalah simpul.

Kepuasan kendala adalah proses menemukan titik di wilayah yang layak.

Daerah fisibel tertutup dari masalah program linier dengan tiga variabel adalah polihedron cembung.

Himpunan layak cembung

Dalam masalah pemrograman linier, serangkaian kendala linier menghasilkan wilayah layak cembung dari nilai-nilai yang mungkin untuk variabel-variabel tersebut. Dalam kasus dua variabel daerah ini berbentuk poligon sederhana cembung.

Himpunan layak cembung adalah himpunan yang ruas garis yang menghubungkan dua titik layak hanya melalui titik layak lainnya dan tidak melalui suatu titik di luar himpunan layak tersebut. Himpunan layak cembung muncul dalam banyak jenis masalah, termasuk masalah program linier, dan sangat menarik karena masalah dengan fungsi tujuan konveks yang dimaksimalkan umumnya lebih mudah diselesaikan jika ada solusi cembung. set yang diizinkan, dan setiap maksimum lokal juga merupakan maksimum global.

Tidak ada set yang layak

Jika kendala dari masalah optimasi saling bertentangan, tidak ada titik yang memenuhi semua kendala dan dengan demikian wilayah yang layak adalah himpunan nol. Dalam hal ini masalah tidak memiliki solusi dan dikatakan tidak layak.

Himpunan layak terbatas (atas) dan himpunan layak tak terbatas (bawah). Set di bagian bawah berlanjut selamanya ke arah kanan.

Himpunan layak terbatas dan tidak terbatas

Himpunan layak terbatas (atas) dan himpunan layak tak terbatas (bawah). Set di bagian bawah berlanjut selamanya ke arah kanan.

Himpunan yang dapat diwujudkan bisa terbatas atau tidak terbatas. Misalnya, himpunan nilai realisasi yang ditentukan oleh himpunan batasan {x ≥ 0, y ≥ 0} tidak terhingga karena tidak ada batasan jarak yang dapat ditempuh dalam arah tertentu selama berada dalam rentang nilai realisasi tetap. Sebaliknya, himpunan kemungkinan yang dibentuk oleh himpunan batasan {x ≥ 0, y ≥ 0, x + 2y ≤ 4} adalah terbatas karena amplitudo pergerakan ke segala arah dibatasi oleh batasan tersebut.

Untuk masalah program linier dengan n variabel, kondisi yang diperlukan tetapi tidak cukup untuk membatasi himpunan kemungkinan adalah jumlah batasan paling sedikit n + 1 (seperti yang ditunjukkan pada contoh di atas).

Ketika himpunan kemungkinan tidak terbatas, optimalitas mungkin terjadi atau tidak tergantung pada spesifikasi fungsi tujuan.Misalnya, jika wilayah layak ditentukan oleh himpunan batasan {x ≥ 0, y ≥ 0}, maka permasalahan pemaksimalan x + y adalah suboptimal karena setiap solusi yang mungkin dapat diperbaiki dengan meningkatkan x atau y; Namun jika permasalahannya meminimalkan x + y, maka terdapat permasalahan optimal (terutama pada (x, y) = (0, 0)).

Solusi kandidat

Dalam optimasi dan cabang matematika lainnya, serta dalam algoritma pencarian (cabang ilmu komputer), solusi kandidat adalah anggota dari himpunan solusi yang mungkin dalam domain yang mungkin dari suatu masalah tertentu. Solusi kandidat tidak harus berupa solusi yang mungkin atau masuk akal terhadap suatu masalah, namun hanya solusi yang memenuhi semua batasan; yaitu, dalam serangkaian solusi yang mungkin. Algoritma untuk menyelesaikan berbagai jenis masalah optimasi sering kali mereduksi himpunankemungkinan solusi menjadi subkumpulan solusi layak yang poin-poinnya tetap menjadi solusi layak, sementara solusi lain yang mungkin kemudian dikeluarkan sebagai kandidat.

Ruang semua kandidat solusi sebelum mengecualikan titik layak disebut wilayah layak, himpunan layak, ruang pencarian, atau ruang solusi. Ini adalah himpunan semua solusi yang mungkin yang memenuhi kondisi batas masalah. Kepuasan Kendala adalah proses menemukan titik-titik dalam suatu himpunan yang mungkin.

Algoritma genetika

Dalam kasus algoritma genetik thm, solusi kandidat adalah individu dalam populasi yang dikembangkan oleh algoritma.

Kalkulus

Dalam kalkulus, pencarian solusi optimal dilakukan dengan menggunakan uji turunan pertama: turunan pertama dari fungsi yang dioptimalkan ditetapkan sama dengan nol, dan nilai apa pun dari variabel terpilih yang memenuhi persamaan ini diperlakukan sebagai kandidat solusi (sementara mereka yang tidak dikecualikan dari daftar peringkat). Solusi potensial mungkin bukan solusi aktual dalam beberapa hal. Pertama, ini mungkin merupakan titik terendah ketika bertujuan untuk mencapai titik tertinggi (atau sebaliknya), dan kedua, mungkin tidak memberikan titik terendah atau tertinggi pada, melainkan sebuah pelana atau titik balik ketika ada jeda sementara dalam pertumbuhan lokal. . Jika tidak, fungsinya akan hilang. Solusi kandidat tersebut dapat dikecualikan dengan uji turunan kedua, yang pemenuhannya cukup untuk membuat solusi kandidat setidaknya optimal secara lokal.Ketiga, solusi potensial mungkin optimal secara lokal namun tidak optimal secara global.

Dalam mengambil antiturunan dari monomial bentuk  solusi kandidat menggunakan rumus kuadratur Cavalieri adalah Kandidat solusi ini sebenarnya benar kecuali jika

Pemrograman linier

Serangkaian kendala pemrograman linier pada dua variabel menghasilkan wilayah nilai yang mungkin untuk variabel tersebut. Masalah dua variabel yang dapat diselesaikan akan memiliki wilayah layak dalam bentuk poligon sederhana cembung jika dibatasi. Dalam algoritma yang menguji titik-titik yang layak secara berurutan, setiap titik yang diuji pada gilirannya merupakan solusi kandidat.

Dalam metode simpleks penyelesaian masalah program linier, sebuah simpul dari politop yang layak dipilih sebagai kandidat solusi awal dan diuji optimalitasnya; Jika ditolak sebagai titik optimal, simpul-simpul tetangga dianggap sebagai kandidat solusi berikutnya. Proses ini berlanjut hingga solusi yang diusulkan dianggap optimal.

Disadur dari: en.wikipedia.org

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

Pengenalan Dynamic Programming
Pemrograman dinamis adalah metode optimasi matematis dan paradigma algoritmik. Metode ini dikembangkan oleh Richard Bellman pada tahun 1950-an dan telah digunakan di berbagai bidang, mulai dari teknik dirgantara hingga ekonomi. Dalam kedua konteks ini mengacu pada penyederhanaan masalah yang kompleks dengan memecahnya secara rekursif menjadi sub-masalah yang lebih sederhana. Meskipun beberapa masalah pengambilan keputusan tidak dapat diurai dengan cara ini, keputusan yang mencakup beberapa titik waktu sering kali diurai secara rekursif. Hal yang sama berlaku dalam ilmu komputer: Jika suatu masalah dapat diselesaikan secara optimal dengan membaginya menjadi sub-masalah dan kemudian secara rekursif mencari solusi optimal untuk sub-masalah tersebut, maka ini disebut substruktur optimal.Jika submasalah dapat disarangkan secara rekursif dalam masalah yang lebih besar sehingga metode pemrograman dinamis dapat diterapkan, maka terdapat hubungan antara nilai masalah yang lebih besar dan nilai submasalah tersebut. Dalam literatur optimasi, hubungan ini disebut persamaan Bellman.

Persamaan Matematis

Dalam optimasi matematis, pemrograman dinamis mengacu pada penyederhanaan keputusan dengan memecahnya menjadi serangkaian langkah keputusan dari waktu ke waktu. Proses ini melibatkan pendefinisian barisan fungsi nilai V1, V2, ..., Vn, yang mewakili keadaan sistem pada waktu i dari 1 sampai n, dimana Vn(y) adalah nilai dalam keadaan y pada saat terakhir. Utara.Nilai Vi pada waktu sebelumnya dapat dicari mundur dengan menggunakan persamaan Bellman. Untuk i = 2, ..., n, Vi-1 pada setiap state dihitung dari Vi dengan memaksimumkan fungsi keuntungan dari keputusan pada waktu i-1 dan fungsi Vi pada state baru pada saat pengambilan keputusan tersebut.Proses ini menghasilkan Vi-1 untuk status yang diperlukan. Pada keadaan awal sistem, V1 merupakan nilai solusi optimal. Nilai optimal dari variabel keputusan dapat dikembalikan secara individual setelah perhitungan dilakukan.

Computer Science

Ada dua atribut utama yang harus dimiliki suatu masalah agar pemrograman dinamis dapat diterapkan: substruktur optimal dan submasalah yang tumpang tindih. Ketika suatu masalah dapat diselesaikan dengan menggabungkan solusi optimal untuk sub-masalah yang tidak tumpang tindih, strategi ini disebut “membagi dan menaklukkan.”Oleh karena itu, pengurutan gabungan dan pengurutan cepat tidak diklasifikasikan sebagai masalah pemrograman dinamis.

Substruktur optimal berarti bahwa solusi terhadap masalah optimasi tertentu dapat diperoleh dengan kombinasi solusi optimal dari submasalahnya. Substruktur optimal biasanya dijelaskan dengan rekursi.Misalnya, pada graf G = (V, E), jalur terpendek p dari simpul u ke simpul v mewakili substruktur optimal: ambil setiap simpul perantara w pada lintasan terpendek p. Jika p memang merupakan jalur terpendek, jalur tersebut dapat dibagi menjadi subjalur p1 dari u ke w dan p2 dari w ke v, sehingga jalur ini adalah yang terpendek di antara simpul-simpul yang bersesuaian (menggunakan metode potong-dan-tempel yang dijelaskan pada
argumen). Pengantar algoritma). Oleh karena itu, solusi dapat dengan mudah dirumuskan untuk mencari jalur terpendek secara rekursif, seperti halnya dengan algoritma Bellman-Ford atau algoritma Floyd-Warshall.

Tumpang tindih submasalah berarti ruang submasalah harus kecil, yaitu. H. algoritma rekursif apa pun yang menyelesaikan masalah harus menyelesaikan submasalah yang sama berulang kali, bukan membuat submasalah baru. Misalnya, perhatikan rumus rekursif untuk menghasilkan deret Fibonacci: Fi = Fi-1 + Fi-2, dengan kasus dasar F1 = F2 = 1. Maka F43 = F42 + F41 dan F42 = F41 + F40. Sekarang F41 diisi menjadi subpohon rekursif dari F43 dan juga F42. Meskipun jumlah totalsubmasalah sangat kecil (hanya 43), jika kita menggunakan solusi rekursif naif seperti ini, kita akan menyelesaikan masalah yang sama berulang kali.Pemrograman dinamis memperhitungkan fakta ini dan menyelesaikan setiap sub-masalah hanya satu kali.

Hal ini dapat dicapai dengan salah satu dari dua cara:

• Top down approach: Ini adalah akibat langsung dari perumusan masalah secara rekursif. Jika solusi suatu masalah dapat dirumuskan secara rekursif menggunakan solusi dari submasalahnya dan submasalah tersebut tumpang tindih, kita dapat dengan mudah mencatat atau menyimpan solusi dari submasalah tersebut dalam sebuah tabel. Setiap kali kita mencoba memecahkan submasalah baru, pertama-tama kita memeriksa tabel untuk melihat apakah submasalah tersebut sudah terpecahkan. Jikasolusi telah dicatat, kita dapat menggunakannya secara langsung, jika tidak, kita selesaikan submasalah dan tambahkan solusinya ke tabel.

• Bottom up approach: Setelah kita merumuskan solusi suatu masalah secara rekursif dalam bentuk submasalah, kita dapat mencoba merumuskan kembali masalah dari bawah ke atas: pertama-tama kita mencoba menyelesaikan submasalah terkecil dan membangun solusi berdasarkan solusinya. Sub-masalahnya adalah yang terbesar. Hal ini juga biasanya dilakukan dalam bentuk tabel, dengan menghasilkan solusi secara berulang untuk submasalah yang semakin besar menggunakan solusi
  untuk submasalah yang lebih kecil. Misalnya kita sudah mengetahui nilai F41 dan F40, kita bisa langsung menghitung nilai F42.

Beberapa bahasa pemrograman dapat secara otomatis menyimpan hasil pemanggilan fungsi dengan serangkaian argumen tertentu untuk mempercepat evaluasi panggilan berdasarkan nama (mekanisme ini disebut panggilan demi permintaan). Beberapa bahasa mengizinkan hal ini secara portabel (misalnya Skema, Common Lisp, Perl, atau D). Beberapa bahasa memiliki hafalan otomatis, seperti: B. Prolog dan J Tabled, yang mendukung hafalan dengan kata keterangan M. Namun, ini hanya mungkin untuk fungsi yang transparan secara referensial. Penghafalan juga ditemukan sebagai pola desain yang mudah diakses dalam bahasa berbasis penulisan ulang seperti Bahasa Wolfram.

Contoh Algoritma :

• Algoritma Dijkstra untuk masalah jalur terpendek
• Deret Fibonacci

Disadur dari : en.wikipedia.org

Pengambilan Keputusan

Dalam psikologi, pengambilan keputusan adalah proses kognitif yang mengarah pada pemilihan suatu keyakinan atau tindakan di antara beberapa alternatif pilihan. Proses ini bisa rasional atau irasional dan didasarkan pada asumsi nilai, preferensi dan keyakinan pengambil keputusan. Setiap proses pengambilan keputusan mengarah pada keputusan akhir, yang mungkin mengarah pada tindakan atau tidak. Penelitian di bidang ini juga berkaitan dengan pemecahan masalah, khususnya dalam penelitian psikologi diEropa.

Gambaran Umum

Pengambilan keputusan merupakan suatu kegiatan pemecahan masalah yang menghasilkan suatu solusi yang dianggap optimal atau memuaskan. Proses ini bisa rasional atau irasional dan melibatkan pengetahuan eksplisit atau diam-diam. Kinerja manusia dalam pengambilan keputusan diperiksa dari sudut pandang psikologis, kognitif dan normatif. Ada dua jenis pengetahuan, pengetahuan eksplisit dan tacit, yang digunakan bersama dalam proses pengambilan keputusan. Prosesnya melibatkan analisis alternatif yang terbatas berdasarkan kriteria evaluasi. Analisis keputusan multi-kriteria (MCDA) menjadi sorotan namun kontroversial karena metodenya dapat memberikan hasil yang berbeda. Lingkungan pengambilan keputusan, termasuk kompleksitasnya, berperan penting dalam proses pengambilan keputusan dan dapat mempengaruhi fungsi kognitif. Keputusan logis adalah elemen kunci dalam banyak profesi ilmiah, namun situasi tertentu dapat mendorong pengambilan keputusan yang intuitif atau kurang terstruktur.

Karakteristik Pengambilan Keputusan

Pengambilan keputusan melibatkan serangkaian fitur dan langkah yang umumnya diikuti untuk membuat model keputusan yang dapat membantu menentukan rencana produksi yang optimal. Pertama, tujuan harus didefinisikan dengan jelas dan kemudian diurutkan dan diurutkan berdasarkan kepentingannya. Tindakan alternatif kemudian dikembangkan sebagai respons terhadap tujuan yang telah ditetapkan. Alternatif-alternatif ini kemudian dievaluasi terhadap seluruh target yang diklasifikasikan sebagai. Keputusan awal dibuat dan alternatif yang dapat mencapai semua tujuan yang ditetapkan dipilih.

Keputusan antara kemudian dievaluasi berdasarkan kemungkinan konsekuensinya. Setelah penilaian ini, tindakan tegas diambil dan tindakan tambahan diambil untuk menghindari konsekuensi negatif yang mungkin timbul. Proses ini mencakup langkah-langkah pengambilan keputusan yang kompleks. Dalam situasi konflik, permainan peran dapat membantu dalam memprediksi keputusan pihak-pihak yang terlibat. Seluruh sistem, termasuk analisis masalah dan pengambilan keputusan, dapat dimulai ulang daridan seterusnya jika diperlukan.

Teknik Pengambilan Keputusan

Teknik pengambilan keputusan dapat dibagi menjadi dua kategori besar: teknik pengambilan keputusan kelompok dan teknik pengambilan keputusan individu.

Saat mengambil keputusan kelompok, metode konsensus berupaya mencapai kesepakatan tanpa menentukan pihak mana yang menang atau kalah. Pemungutan suara mayoritas, pluralitas, pemungutan suara poin, dan pemungutan suara kuadrat merupakan metode yang dapat digunakan dalam pengambilan keputusan kelompok. Selain itu, metode seperti Delphi dan demokrasi juga digunakan untuk memfasilitasi komunikasi kelompok dan pengambilan keputusan. Pengambilan keputusan partisipatif melibatkan sekelompok orang yang terlibat dalam proses pengambilan keputusan. Rekayasa keputusan menggunakan visualisasi proses pengambilan keputusan dan dapat diotomatisasi menggunakan alat pemodelan keputusan.

Di sisi lain, dalam pengambilan keputusan individu, terdapat pendekatan seperti keseimbangan keputusan, optimalisasi nilai yang diharapkan, kepuasan, kesepakatan dengan otoritas, anti-otoritarianisme, flipisme, dukungan keputusan otomatis, dan sistem kendali. Pendukung keputusan. Masing-masing metode ini mencakup peluang unik untuk analisis dan pengambilan keputusan.

Disadur dari : en.wikipedia.org