Ide komputasi evolusi diperkenalkan pada tahun 1960 oleh I. Rechenberg dalam karyanya "Evolution strategi" (Evolutionsstrategie dalam dokumen asli). Idenya kemudian dikembangkan oleh peneliti lain. Algoritma Genetika (GAs) diciptakan oleh John Holland dan dikembangkan oleh dia dan para mahasiswa dan koleganya. Hal ini menyebabkan buku Belanda "adaptasi di Alam dan Buatan Sistem" diterbitkan pada tahun 1975.
Pada tahun 1992 John Koza telah menggunakan algoritma genetika untuk berevolusi program untuk melakukan tugas tertentu. Ia menyebut metodenya "pemrograman genetika" (GP). Program LISP digunakan, karena program dalam bahasa ini dapat dinyatakan dalam bentuk "pohon parse", yang merupakan obyek GA bekerja pada.
Kromosom
Semua organisme hidup terdiri dari sel-sel. Dalam setiap sel ada set yang sama kromosom. Kromosom adalah string DNA dan berfungsi sebagai model bagi seluruh organisme. Sebuah kromosom terdiri dari gen, blok DNA. Setiap gen menyandi protein tertentu. Pada dasarnya dapat dikatakan, bahwa masing-masing gen mengkodekan suatu sifat, seperti warna mata. Pengaturan yang mungkin untuk suatu sifat (misalnya biru, coklat) disebut alel. Setiap gen memiliki posisi sendiri di kromosom. Posisi ini disebut lokus.
Set lengkap materi genetik (semua kromosom) disebut genom. Khusus set gen dalam genom disebut genotipe. Genotipe ini dengan perkembangan kemudian setelah lahir dasar untuk fenotipe organisme, karakteristik fisik dan mental, seperti warna mata, kecerdasan dll
Reproduksi
Selama reproduksi, pertama terjadi rekombinasi (atau crossover). Gen dari orang tua bentuk dalam beberapa cara kromosom baru. Keturunan dibuat baru kemudian dapat bermutasi. Mutasi berarti, bahwa unsur-unsur DNA yang sedikit berubah. Perubahan ini terutama disebabkan oleh kesalahan dalam menyalin gen dari orang tua.
Kesesuaian suatu organisme diukur dengan keberhasilan organisme dalam hidupnya.
Jika kita memecahkan beberapa masalah, kita biasanya mencari beberapa solusi, yang akan menjadi yang terbaik antara lain. Ruang dari semua solusi layak (artinya objek di antara mereka solusi yang diinginkan) disebut ruang pencarian (juga ruang keadaan). Setiap titik dalam ruang pencarian merupakan salah satu solusi yang layak. Setiap solusi yang layak dapat "ditandai" oleh nilai atau kesesuaian untuk masalah. Kami sedang mencari solusi kami, yang merupakan salah satu titik (atau lebih) diantara solusi yang layak - yang merupakan salah satu titik dalam ruang pencarian.
Para mencari solusi kemudian sama dengan mencari beberapa ekstrim (minimum atau maksimum) dalam ruang pencarian. Ruang pencarian dapat menjadi utuh dikenal dengan waktu penyelesaian masalah, tetapi biasanya kita tahu hanya beberapa poin dari dan kami menghasilkan poin lain sebagai proses mencari solusi terus.
Masalahnya adalah bahwa pencarian bisa sangat rumit. Orang tidak tahu ke mana harus mencari solusi dan di mana untuk memulai. Ada banyak metode, bagaimana menemukan beberapa solusi yang sesuai (mis. belum tentu solusi yang terbaik), untuk mendaki bukit misalnya, tabu search, simulated annealing dan algoritma genetika. Solusi ditemukan oleh metode ini sering dianggap sebagai solusi yang baik, karena tidak sering mungkin untuk membuktikan apa yang optimal yang nyata.
NP-hard Masalah
Contoh masalah yang sulit, yang tidak dapat diselesaikan int "tradisional" jalan, masalah NP.
Ada banyak tugas yang kita tahu cepat (polinomial) algoritma. Ada juga beberapa masalah yang tidak mungkin diselesaikan algorithmicaly. Untuk beberapa masalah terbukti bahwa mereka tidak dipecahkan dalam waktu polinomial.
Tapi ada banyak tugas penting, yang sangat sulit untuk menemukan solusi, tapi begitu kami memilikinya, mudah untuk memeriksa solusi. Fakta ini menyebabkan masalah NP-lengkap. NP singkatan polinomial nondeterministic dan itu berarti bahwa adalah mungkin untuk "menebak" solusi (oleh beberapa algoritma nondeterministic) dan kemudian cek, baik dalam waktu polinomial. Jika kita memiliki mesin yang bisa menebak, kita akan dapat menemukan solusi pada beberapa waktu yang wajar.
Mempelajari masalah NP-lengkap untuk kesederhanaan terbatas pada masalah, di mana jawabannya bisa ya atau tidak. Karena ada tugas dengan output rumit, kelas masalah yang disebut masalah NP-hard telah diperkenalkan. Kelas ini tidak terbatas sebagai kelas masalah NP-lengkap.
Untuk NP-masalah merupakan ciri bahwa beberapa algoritma sederhana untuk menemukan solusi jelas pada pandangan pertama - hanya mencoba semua solusi yang mungkin. Tetapi algoritma ini sangat lambat (biasanya O (2 ^ n)) dan bahkan untuk sedikit contoh yang lebih besar dari masalah itu tidak dapat digunakan sama sekali.
Hari ini tidak ada yang tahu jika beberapa algoritma cepat tepat ada. Membuktikan atau tidak membuktikan ini tetap sebagai tugas besar bagi para peneliti baru (dan mungkin Anda! :-)). Saat ini banyak orang berpikir, bahwa seperti sebuah algoritma tidak ada dan sehingga mereka mencari beberapa metode alternatif - contoh metode ini algoritma genetika.
Contoh masalah NP adalah satisfiability masalah, masalah salesman keliling atau masalah ransel. Kompendium masalah NP tersedia.
Genetic Algorithm
Keterangan Dasar
Algoritma genetik terinspirasi oleh teori Darwin tentang evolusi. Solusi untuk masalah dipecahkan oleh algoritma genetika adalah berevolusi.
Algoritma dimulai dengan satu set solusi (diwakili oleh kromosom) yang disebut populasi. Solusi dari satu populasi yang diambil dan digunakan untuk membentuk populasi baru. Hal ini didorong oleh harapan, bahwa populasi baru akan lebih baik dari yang lama. Solusi yang dipilih untuk membentuk solusi baru (keturunan) yang dipilih sesuai dengan kebugaran mereka - yang lebih cocok mereka adalah lebih banyak kesempatan mereka untuk bereproduksi.
Hal ini diulang sampai beberapa kondisi (contoh untuk jumlah populasi atau peningkatan solusi yang terbaik) adalah puas.
Contoh
Seperti yang Anda sudah tahu dari bab tentang ruang pencarian, pemecahan masalah dapat sering dinyatakan sebagai mencari ekstrim fungsi. Ini adalah persis apa masalahnya ditampilkan di sini adalah. Beberapa fungsi yang diberikan dan GA mencoba untuk menemukan minimum fungsi.
Anda dapat mencoba untuk menjalankan algoritma genetika di applet berikut dengan menekan tombol Start. Grafik merupakan beberapa ruang pencarian dan garis vertikal merupakan solusi (titik-titik dalam ruang pencarian). Garis merah adalah solusi terbaik, baris hijau adalah orang-orang lain.
Tombol Start dimulai algoritma, Langkah melakukan satu langkah (yaitu membentuk satu generasi baru), Berhenti berhenti algoritma dan Reset ulang penduduk.
Pada tahun 1992 John Koza telah menggunakan algoritma genetika untuk berevolusi program untuk melakukan tugas tertentu. Ia menyebut metodenya "pemrograman genetika" (GP). Program LISP digunakan, karena program dalam bahasa ini dapat dinyatakan dalam bentuk "pohon parse", yang merupakan obyek GA bekerja pada.
Kromosom
Semua organisme hidup terdiri dari sel-sel. Dalam setiap sel ada set yang sama kromosom. Kromosom adalah string DNA dan berfungsi sebagai model bagi seluruh organisme. Sebuah kromosom terdiri dari gen, blok DNA. Setiap gen menyandi protein tertentu. Pada dasarnya dapat dikatakan, bahwa masing-masing gen mengkodekan suatu sifat, seperti warna mata. Pengaturan yang mungkin untuk suatu sifat (misalnya biru, coklat) disebut alel. Setiap gen memiliki posisi sendiri di kromosom. Posisi ini disebut lokus.
Set lengkap materi genetik (semua kromosom) disebut genom. Khusus set gen dalam genom disebut genotipe. Genotipe ini dengan perkembangan kemudian setelah lahir dasar untuk fenotipe organisme, karakteristik fisik dan mental, seperti warna mata, kecerdasan dll
Reproduksi
Selama reproduksi, pertama terjadi rekombinasi (atau crossover). Gen dari orang tua bentuk dalam beberapa cara kromosom baru. Keturunan dibuat baru kemudian dapat bermutasi. Mutasi berarti, bahwa unsur-unsur DNA yang sedikit berubah. Perubahan ini terutama disebabkan oleh kesalahan dalam menyalin gen dari orang tua.
Kesesuaian suatu organisme diukur dengan keberhasilan organisme dalam hidupnya.
Jika kita memecahkan beberapa masalah, kita biasanya mencari beberapa solusi, yang akan menjadi yang terbaik antara lain. Ruang dari semua solusi layak (artinya objek di antara mereka solusi yang diinginkan) disebut ruang pencarian (juga ruang keadaan). Setiap titik dalam ruang pencarian merupakan salah satu solusi yang layak. Setiap solusi yang layak dapat "ditandai" oleh nilai atau kesesuaian untuk masalah. Kami sedang mencari solusi kami, yang merupakan salah satu titik (atau lebih) diantara solusi yang layak - yang merupakan salah satu titik dalam ruang pencarian.
Para mencari solusi kemudian sama dengan mencari beberapa ekstrim (minimum atau maksimum) dalam ruang pencarian. Ruang pencarian dapat menjadi utuh dikenal dengan waktu penyelesaian masalah, tetapi biasanya kita tahu hanya beberapa poin dari dan kami menghasilkan poin lain sebagai proses mencari solusi terus.
Masalahnya adalah bahwa pencarian bisa sangat rumit. Orang tidak tahu ke mana harus mencari solusi dan di mana untuk memulai. Ada banyak metode, bagaimana menemukan beberapa solusi yang sesuai (mis. belum tentu solusi yang terbaik), untuk mendaki bukit misalnya, tabu search, simulated annealing dan algoritma genetika. Solusi ditemukan oleh metode ini sering dianggap sebagai solusi yang baik, karena tidak sering mungkin untuk membuktikan apa yang optimal yang nyata.
NP-hard Masalah
Contoh masalah yang sulit, yang tidak dapat diselesaikan int "tradisional" jalan, masalah NP.
Ada banyak tugas yang kita tahu cepat (polinomial) algoritma. Ada juga beberapa masalah yang tidak mungkin diselesaikan algorithmicaly. Untuk beberapa masalah terbukti bahwa mereka tidak dipecahkan dalam waktu polinomial.
Tapi ada banyak tugas penting, yang sangat sulit untuk menemukan solusi, tapi begitu kami memilikinya, mudah untuk memeriksa solusi. Fakta ini menyebabkan masalah NP-lengkap. NP singkatan polinomial nondeterministic dan itu berarti bahwa adalah mungkin untuk "menebak" solusi (oleh beberapa algoritma nondeterministic) dan kemudian cek, baik dalam waktu polinomial. Jika kita memiliki mesin yang bisa menebak, kita akan dapat menemukan solusi pada beberapa waktu yang wajar.
Mempelajari masalah NP-lengkap untuk kesederhanaan terbatas pada masalah, di mana jawabannya bisa ya atau tidak. Karena ada tugas dengan output rumit, kelas masalah yang disebut masalah NP-hard telah diperkenalkan. Kelas ini tidak terbatas sebagai kelas masalah NP-lengkap.
Untuk NP-masalah merupakan ciri bahwa beberapa algoritma sederhana untuk menemukan solusi jelas pada pandangan pertama - hanya mencoba semua solusi yang mungkin. Tetapi algoritma ini sangat lambat (biasanya O (2 ^ n)) dan bahkan untuk sedikit contoh yang lebih besar dari masalah itu tidak dapat digunakan sama sekali.
Hari ini tidak ada yang tahu jika beberapa algoritma cepat tepat ada. Membuktikan atau tidak membuktikan ini tetap sebagai tugas besar bagi para peneliti baru (dan mungkin Anda! :-)). Saat ini banyak orang berpikir, bahwa seperti sebuah algoritma tidak ada dan sehingga mereka mencari beberapa metode alternatif - contoh metode ini algoritma genetika.
Contoh masalah NP adalah satisfiability masalah, masalah salesman keliling atau masalah ransel. Kompendium masalah NP tersedia.
Genetic Algorithm
Keterangan Dasar
Algoritma genetik terinspirasi oleh teori Darwin tentang evolusi. Solusi untuk masalah dipecahkan oleh algoritma genetika adalah berevolusi.
Algoritma dimulai dengan satu set solusi (diwakili oleh kromosom) yang disebut populasi. Solusi dari satu populasi yang diambil dan digunakan untuk membentuk populasi baru. Hal ini didorong oleh harapan, bahwa populasi baru akan lebih baik dari yang lama. Solusi yang dipilih untuk membentuk solusi baru (keturunan) yang dipilih sesuai dengan kebugaran mereka - yang lebih cocok mereka adalah lebih banyak kesempatan mereka untuk bereproduksi.
Hal ini diulang sampai beberapa kondisi (contoh untuk jumlah populasi atau peningkatan solusi yang terbaik) adalah puas.
Contoh
Seperti yang Anda sudah tahu dari bab tentang ruang pencarian, pemecahan masalah dapat sering dinyatakan sebagai mencari ekstrim fungsi. Ini adalah persis apa masalahnya ditampilkan di sini adalah. Beberapa fungsi yang diberikan dan GA mencoba untuk menemukan minimum fungsi.
Anda dapat mencoba untuk menjalankan algoritma genetika di applet berikut dengan menekan tombol Start. Grafik merupakan beberapa ruang pencarian dan garis vertikal merupakan solusi (titik-titik dalam ruang pencarian). Garis merah adalah solusi terbaik, baris hijau adalah orang-orang lain.
Tombol Start dimulai algoritma, Langkah melakukan satu langkah (yaitu membentuk satu generasi baru), Berhenti berhenti algoritma dan Reset ulang penduduk.