Pernyataan yang dapat dibuktikan tentang algoritma genetika

Algoritma genetika tidak mendapatkan banyak daya tarik dalam dunia teori, tetapi mereka adalah metode metaheuristik yang cukup baik digunakan (oleh metaheuristik maksud saya teknik yang berlaku secara umum di banyak masalah, seperti anil, keturunan gradien, dan sejenisnya). Faktanya, teknik mirip GA cukup efektif untuk Euclidean TSP dalam praktiknya.

Beberapa metaheuristik dipelajari dengan cukup baik secara teoritis: ada pekerjaan pada pencarian lokal , dan anil. Kami memiliki pemahaman yang cukup baik tentang bagaimana pengoptimalan bolak-balik ( seperti k-means ) bekerja. Tapi sejauh yang saya tahu, tidak ada yang benar-benar berguna yang diketahui tentang algoritma genetika.

Adakah teori algoritma / kompleksitas yang solid tentang perilaku algoritma genetika, dengan cara apa pun, bentuk atau bentuk? Sementara saya pernah mendengar hal-hal seperti teori skema , saya mengecualikannya dari diskusi berdasarkan pemahaman saya saat ini tentang area karena tidak terlalu algoritmik (tapi saya mungkin salah di sini).

Y. Rabinovich, A. Wigderson. Teknik untuk membatasi laju konvergensi algoritma genetika. Algoritma Struktur Acak, vol. 14, tidak. 2, 111-138, 1999. (Juga tersedia dari beranda Avi Wigderson )

Lihatlah karya Benjamin Doerr dari kelompok Algoritma di Max Planck (MPI). Ini semua tentang mencoba membuat kontribusi yang dapat dibuktikan untuk algoritma evolusioner.

Secara khusus, Doerr telah menyunting bersama buku terbaru yang relevan, Theory of Randomized Search Heuristics

Serta bekerja pada anil simulasi, Ingo Wegener memiliki beberapa hasil teoritis pada algoritma evolusioner. The tesis dari mahasiswa PhD Dirk Sudholt juga layak lihat.

Apakah Anda tahu makalah ini:

Jens Jägersküpper. Menggabungkan Analisis Rantai Markov dan Analisis Drift: Algoritma Evolusi (1 + 1) pada Fungsi Linear Reloaded .

$O(n\log n)$

Selama dekade terakhir, telah ada kemajuan yang signifikan dalam analisis runtime dari algoritma evolusioner, optimisasi koloni semut, dan metaheuristik lainnya. Untuk survei, silakan merujuk ke Oliveto et al. (2007) .

$O^*(n^4)$

Periksa referensi ini:

Lothar Schmitt, Teori algoritma genetika II: model untuk operator genetik atas representasi string-tensor populasi dan konvergensi ke optima global untuk fungsi kebugaran sewenang-wenang di bawah penskalaan

Shiu Yin Yuen; BKS Cheung, Batas untuk kemungkinan keberhasilan algoritma genetika klasik berdasarkan jarak tempuh

Chang CY Dorea; Judinor A. Guerra Jr .; Rafael Morgado; Andre GC Pereira, Pemodelan Rantai Multistage Markov dari Algoritma Genetika dan Hasil Konvergensi

C. Dombry, Model jalan acak tertimbang. Aplikasi untuk algoritma genetika

Ada juga makalah dari D. BHANDARI, CA MURTHY dan SK PAL (sayangnya tidak tersedia online) yang menyediakan bukti konvergensi dengan dua asumsi:

• $t$$t+1$
• Operator mutasi memungkinkan untuk beralih dari solusi apa pun ke yang lain dalam sejumlah langkah terbatas

Bukti konvergensi menggunakan model rantai Markov.

Berikut rujukannya: Dinabandhu Bhandari, CA Murthy: Algoritma Genetika dengan Model Elitist dan Konvergensinya. IJPRAI 10 (6): 731-747 (1996)

Model matematika dari algoritma genetika dengan populasi terbatas tetapi non-unitary sulit, dan sejauh ini terbukti tidak dapat dianalisis untuk semua fungsi kebugaran yang paling sepele. Menariknya, jika Anda bersedia menerima argumen simetri , argumen, dengan kata lain, tidak dibuat dalam batas-batas sistem aksiomatik formal, maka ada hasil yang menarik dan indah yang bisa didapat tentang kekuatan komputasi dari algoritma genetika.

Secara khusus, suatu algoritma genetika dengan crossover yang seragam mampu mengevaluasi sejumlah besar partisi skema kasar secara implisit dan paralel, dan dapat secara efisien mengidentifikasi partisi yang memiliki skema yang memiliki nilai kebugaran rata-rata yang berbeda. Bentuk paralelisme implisit ini sebenarnya lebih kuat daripada jenis yang dijelaskan oleh John Holland dan murid-muridnya, dan tidak seperti paralelisme implisit yang dijelaskan oleh Holland, dapat diverifikasi secara eksperimental. (Lihat posting blog ini .)

Makalah berikut ini menjelaskan bagaimana algoritma genetika dengan parlay crossover seragam paralelisme implisit menjadi tujuan umum, heuristik optimisasi global yang disebut hyperclimbing :

Menjelaskan optimasi dalam algoritma genetika dengan crossover yang seragam . Untuk muncul dalam prosiding konferensi Yayasan Genetika Algoritma 2013.

(Penafian: Saya penulis makalah ini)

Raphael Cerf melakukan tesis PhD- nya tentang Algoritma Genetika di Montpellier di bawah pengawasan Alain Berlinet, dari sudut pandang matematika. Ini sudah cukup tua, tetapi mungkin termasuk bibliografi tentang algoritma genetika.