Apakah mendefinisikan titik henti dari algoritma genetika mengalahkan tujuan dari algoritma?

Wikipedia mendefinisikan titik terminasi GA untuk hal ini:

Secara umum, algoritma berakhir ketika jumlah generasi maksimum telah dihasilkan, atau tingkat kebugaran yang memuaskan telah dicapai untuk populasi. Jika algoritma telah diakhiri karena jumlah generasi maksimum, solusi yang memuaskan mungkin atau mungkin belum tercapai.

Sekarang, jika itu berakhir ketika tingkat kebugaran yang memuaskan telah tercapai, dan Anda adalah orang yang menentukan tingkat kebugaran itu, mengapa Anda tidak dapat hanya membuat genom "sempurna" dari awal sendiri, karena Anda sudah tahu karakteristiknya genom yang sempurna ini?

Saya kira saya hanya sedikit bingung di sini. Saya pikir tujuan GA adalah untuk terus-menerus berevolusi dan menunjukkan kepada kami kemungkinan solusi yang lebih baik daripada yang kami pikirkan, dan fungsi kebugaran kami hanyalah sesuatu yang membantunya, bukan sesuatu yang kami pakai sebagai alas pengakhiran " negara "sempurna. Bukankah itu menghancurkan intinya?

Fungsi kebugaran mengevaluasi output dari algoritma Anda. Sangat mungkin untuk mengenali output ideal ketika Anda melihatnya, tetapi tidak tahu langkah-langkah untuk menghasilkan output dari input yang diberikan. Di situlah algoritma genetika paling berguna.

Sebagai contoh, salah satu aplikasi menyenangkan GA yang umum adalah dalam memproduksi animasi yang dapat memindahkan makhluk virtual dengan cara yang efisien. Mudah untuk mengetahui apakah makhluk itu bergerak dengan kecepatan tertentu dalam garis yang relatif lurus. Itu fungsi kebugaran Anda. Jauh lebih sulit untuk mengatakan urutan gerakan "otot" yang tepat untuk melakukannya.

Sering kali Anda dapat menentukan kesesuaian suatu solusi tetapi tidak dapat langsung menentukan solusinya. Katakanlah Anda mencoba mengembangkan kelinci cepat, dan ada beberapa gen yang memengaruhi kecepatan kelinci. Anda dapat menguji kecepatan kelinci, tetapi menghitung semua kombinasi gen yang berhubungan dengan kecepatan akan menjadi tidak praktis. Dalam kasus seperti itu, Anda mungkin memiliki GA yang memacu kelinci dan membiakkan yang tercepat. Anda bisa melakukannya selamanya, tetapi Anda mungkin lebih suka berhenti ketika:

• Anda telah menemukan kelinci yang lebih cepat dari X, atau
• peningkatan bertahap selama n generasi telah turun di bawah ambang batas tertentu, atau
• Anda telah memelihara kelinci dari generasi ke generasi

Inti dari GA adalah memberi Anda solusi untuk masalah yang memiliki tingkat kebugaran itu. Solusi ini akan sangat sulit ditemukan menggunakan algoritma pencarian lain yang lebih konvensional, yang biasanya menjadi alasan Anda menggunakan GA.

Atau alih-alih batas nilai kebugaran, Anda dapat memutuskan berapa banyak generasi yang ingin Anda jalankan (semakin banyak generasi yang Anda jalankan, semakin besar peluang yang Anda miliki untuk menemukan nilai kebugaran yang semakin tinggi). Misalnya, dalam masalah salesman keliling, mendapatkan jalur yang memiliki biaya terendah di antara kota-kota yang perlu Anda lalui.

Apakah kondisi berhenti Anda adalah tingkat kebugaran tertentu yang dapat diterima atau kendala waktu tertentu (menjalankan GA untuk periode waktu maksimum atau sejumlah generasi terbatas untuk aplikasi kritis waktu seperti pathfinding atau aplikasi AI) biasanya ditentukan oleh masalah Anda domain.

Secara intuitif, tujuan dari algoritma genetika adalah untuk merumuskan solusi algoritmik untuk masalah yang tidak cocok dengan analisis logis langsung. Setelah tujuan itu tercapai, GA tidak perlu mengejar lebih jauh.

Tentu saja, jika diperlukan "kebugaran" yang lebih baik, algoritma genetika dapat dibiarkan berjalan untuk melihat apakah ia dapat menemukan solusi yang lebih optimal, atau algoritma genetika itu sendiri dapat diubah untuk melihat apakah ia akan bertemu pada solusi yang lebih baik.

Algoritme genetik membutuhkan beberapa cara untuk menghargai gen yang baik dengan propagasi yang lebih besar. Jika Anda tidak tahu gen baik dari gen jahat, Anda tidak bisa menggunakan algoritma genetika sama sekali.

Agar algoritma genetika berfungsi, Anda harus memperbolehkan solusi yang lebih cocok untuk mereproduksi lebih disukai daripada solusi yang kurang pas. Jika tidak, Anda hanya akan mencoba solusi acak.

Berikut adalah contoh khas dari pengalaman saya sendiri: Mengembangkan salah satu sistem panggilan suara pertama, kami mengalami kesulitan menemukan algoritma untuk mencocokkan nama yang diucapkan dengan salinan tersimpan dari nama yang sama. Kami diberitahu bahwa akurasi 95% memilih satu nama dari 25 sudah cukup. Kami memiliki kumpulan orang yang disimpan yang mengatakan 25 nama masing-masing 10 kali.

Pertama, kami mengembangkan sistem input yang mengukur panjang kata yang diucapkan dan energi frekuensi dalam beberapa potongan normal itu. Kemudian kami mengembangkan algoritma yang menetapkan bobot pada kecocokan pada parameter tersebut dan membandingkan dua set parameter melalui bobot tersebut.

Sekarang, kami memiliki satu langkah terakhir - apa seharusnya nilai bobot tersebut?

Kami menciptakan 1.000 set bobot acak dan mengujinya terhadap korpus. Kami membuang 500 yang berkinerja terburuk. Untuk sisa 500, kami menduplikasi masing-masing dan di salah satu dari mereka, secara acak menaikkan atau menurunkan salah satu dari bobot.

Kami mengulangi proses ini di komputer selama sekitar dua minggu hingga akhirnya memiliki serangkaian bobot yang memenuhi kriteria akurasi 95%. Kemudian kami mengujinya pada data yang tidak ada dalam korpus. Itu sekitar 92% akurat. Jadi kami berlari lebih lama untuk mendapatkan akurasi 98% pada corpus dan set bobot itu menghasilkan akurasi 95% pada data yang tidak ada dalam corpus.

Jadi, intinya adalah, Anda harus memiliki fungsi kebugaran untuk menjalankan algoritma genetika. Jika Anda tidak memiliki cara untuk mengatakan gen baik dari gen jahat, bagaimana Anda bisa memastikan gen baik bereproduksi dan gen jahat tidak?

Iterate sampai solusi tidak berbeda dari iterasi sebelumnya. Untuk yang sangat banyak, harap dipahami toleransi tetap.

Solution in iteration n-6: 600
Solution in iteration n-5: 800
Solution in iteration n-4: 768
Solution in iteration n-3: 780 
Solution in iteration n-2: 778
Solution in iteration n-1: 778.23
Solution in iteration n: 780.18
Solution in iteration n+1: 780.1815

Dalam contoh ini, jika toleransi tetap Anda adalah 0,01 maka (n +1) memberitahu Anda untuk berhenti karena abs (solusi (n +1) -solusi (n)) <0,01.

Melanjutkan, saat itulah algoritma Anda dapat mengatakan: ini tidak akan menjadi lebih baik!

Untuk jawaban cepat untuk Anda, pertanyaan utama: Ada perbedaan besar antara mengetahui apa yang ingin Anda capai, dan mengetahui bagaimana mencapainya.

Lebih rinci, misalnya, dengan salah satu masalah paling populer diselesaikan dengan menggunakan algoritma genetika / evolusi, biasanya studi kasus di kelas, menemukan rute optimal dalam grafik. Ini sering digunakan dalam jaringan untuk menemukan rute termurah dari satu ujung ke ujung lainnya. Saat Anda menentukan biaya (# hop, biaya dari setiap lompatan, dll ...) Anda juga menentukan biaya target Anda (tingkat kebugaran) di mana Anda senang dengan hasilnya. Algoritme Anda mungkin tidak menemukan yang terbaik, tetapi akan menemukan optimal yang dapat diterima secara algoritmik. Maksud saya, hubungan biaya / manfaat untuk menemukan jawaban yang lebih baik adalah terlarang.

Dengan GA / EA Anda akan menemukan bahwa itu adalah perilaku normal bahwa Anda sangat cepat menemukan 95% + jawaban optimal, tetapi mempersempit 5% terakhir secara eksponensial lebih mahal. Jadi teorinya adalah bahwa Anda menentukan optimum yang dapat diterima untuk mencapai hasil terbaik dalam waktu paling sedikit. Karena biaya penemuan, katakanlah 1% teratas, mungkin lebih besar daripada manfaatnya di atas 5% teratas, Anda menentukan optimum yang dapat diterima.

Singkatnya, Anda tidak sekarang jawaban untuk masalah tertentu, Anda hanya mendefinisikan, per masalah, optimum Anda yang dapat diterima, titik di mana menemukan jawaban yang lebih baik tidak praktis.

Ada beberapa penelitian untuk memperbaiki bug di C dengan algoritma genetika dengan menyediakan test case negatif dan positif sebagai fungsi kebugaran, bersama dengan kode yang rusak sebagai input. Ini adalah contoh masalah yang bisa dipecahkan oleh manusia, tetapi lebih mudah dilakukan oleh algoritma genetika. Penting untuk diperhatikan:

Meskipun metode yang dijelaskan dalam makalah ini tidak mengembangkan program baru dari awal, mereka menunjukkan bagaimana mengembangkan perangkat lunak warisan untuk memperbaiki kesalahan yang ada.

Namun, program - program baru telah dikembangkan dari awal — tidak hanya di C. Beberapa program nontrivial yang ditulis dalam bahasa pemrograman esoterik Malbolge memiliki semua (setahu saya) telah dikembangkan, bukan ditulis. Bahasa ini terlalu rumit untuk digunakan oleh seorang programmer, dan terlalu berbelit-belit untuk menyimpulkan program secara efisien dari logika saja, sehingga sebagian besar program yang ditulis di dalamnya dihasilkan oleh algoritma genetika. Fungsi kebugaran umumnya adalah jarak edit ke output yang diharapkan.

Ini melingkar dengan baik. Dengan mengamati bahwa kode genetik kompleks ditulis oleh proses evolusi, kita dapat mensimulasikan proses evolusi untuk menghasilkan kode dalam bahasa kompleks yang berbeda, bahkan tanpa mengetahui cara kerja kode tersebut!