Предоставляемые утверждения о генетических алгоритмах

Генетические алгоритмы не пользуются большой популярностью в мире теории, но они представляют собой достаточно хорошо используемый метаэвристический метод (под метаэвристическим я подразумеваю технику, которая в целом применяется ко многим задачам, таким как отжиг, градиентный спуск и т. П.). Фактически, GA-подобный метод довольно эффективен для евклидовых TSP на практике.

Некоторые метаэвристики достаточно хорошо изучены теоретически: есть работа по локальному поиску и отжигу. У нас есть хорошее представление о том, как работает переменная оптимизация ( например, k-means ). Но, насколько я знаю, нет ничего действительно полезного о генетических алгоритмах.

Существует ли какая-либо солидная теория алгоритмизма / сложности о поведении генетических алгоритмов, в какой-либо форме, форме или форме? Хотя я слышал о таких вещах, как теория схем , я исключил это из обсуждения, основываясь на моем текущем понимании области, в которой он не особенно алгоритмичен (но я могу ошибаться здесь).

Ю. Рабинович, А. Вигдерсон. Методы ограничения скорости сходимости генетических алгоритмов. Алгоритмы случайных структур, вып. 14, нет 2, 111-138, 1999. (Также доступно на домашней странице Ави Вигдерсона )

Взгляните на работу Бенджамина Доерра из группы «Алгоритмы» Макса Планка (MPI). Все дело в попытках внести доказуемый вклад в эволюционные алгоритмы.

В частности, Doerr отредактировал недавнюю книгу « Теория рандомизированной эвристики поиска».

Помимо работы по моделированию отжига, Инго Вегенер получил некоторые теоретические результаты по эволюционным алгоритмам. Тезис его аспирантом Дирк Sudholt также стоит посмотреть.

Вы знаете эту статью:

Йенс Ягерскюппер. Объединение анализа цепей Маркова и анализа дрейфа: эволюционный алгоритм (1 + 1) для линейных функций: перезагрузка .

$O(n\log n)$

За последнее десятилетие был достигнут значительный прогресс в динамическом анализе эволюционных алгоритмов, оптимизации колоний муравьев и другой метаэвристике. Для опроса, пожалуйста, обратитесь к Oliveto et al. (2007) .

$O^*(n^4)$

Проверьте эти ссылки:

Лотар Шмитт, Теория генетических алгоритмов II: модели для генетических операторов по строково-тензорному представлению популяций и сходимости к глобальным оптимумам для произвольной функции пригодности при масштабировании

Шиу Инь Юн; Б. К. Чеунг, Оценки вероятности успеха классического генетического алгоритма на основе расстояния Хэмминга

Чанг Ти Дорея; Judinor A. Guerra Jr .; Рафаэль Моргадо; Андре Г.С. Перейра, Многоступенчатое марковское цепное моделирование генетического алгоритма и результаты сходимости

C. Домбри, взвешенная модель случайного блуждания. Приложение к генетическому алгоритму

Существует также статья D. BHANDARI, CA MURTHY и SK PAL (к сожалению, недоступна онлайн), в которой дается доказательство сходимости при двух допущениях:

• $t$$t+1$
• Оператор мутации позволяет переключаться с любого решения на другое за конечное число шагов

Для доказательства сходимости используется модель цепей Маркова.

Вот ссылка: Динабандху Бхандари, Калифорния Мурти: Генетический алгоритм с элитарной моделью и его конвергенция. IJPRAI 10 (6): 731-747 (1996)

Математические модели генетических алгоритмов с конечными, но не унитарными популяциями громоздки и до сих пор оказались не поддающимися анализу для всех, кроме самых тривиальных фитнес-функций. Интересно, что если вы готовы принять аргумент симметрии , аргумент, другими словами, не представленный в рамках формальной аксиоматической системы, то вы получите захватывающий и красивый результат о вычислительной мощи генетических алгоритмов.

В частности, генетический алгоритм с равномерным пересечением способен оценивать огромное количество грубых разделов схемы неявно и параллельно, и может эффективно идентифицировать разделы, составляющие схемы которых имеют различные средние значения пригодности. Эта форма неявного параллелизма на самом деле более мощная, чем та, которая описана Джоном Холландом и его учениками, и в отличие от неявного параллелизма, описанного Холландом, может быть проверена экспериментально. (Смотрите этот пост в блоге.)

Следующая статья объясняет, как генетические алгоритмы с равномерным кроссовером объединяют неявный параллелизм в эвристику общего назначения, называемую гиперклимбированием :

Объяснение оптимизации в генетических алгоритмах с равномерным кроссовером . Появиться в трудах конференции «Основы генетических алгоритмов 2013».

(Отказ от ответственности: я автор статьи)

Рафаэль Серф защитил кандидатскую диссертацию по генетическим алгоритмам в Монпелье под руководством Алена Берлине с математической точки зрения. Это довольно старый, но, вероятно, принадлежал бы любой библиографии о генетических алгоритмах.