Может, пора обобщать?

nikvic16 ноября 2004Data Mining18 комментариев

В теории ГА в известном смысле нет математики - нет теорем, кроме теоремы шим и утверждений про очередные рац. предложения. Может, пора обобщать?

Без сомнения, ГА является частным случаем алгоритмов оптимизации неизвестной алгоритму функции с использованием внешнего датчика случайных чисел. Такие алгоритмы можно представить как случайный процесс, порождающий следующую точку по конечному множеству (вариант - последовательности) пар
аргумент/значение, полученному на предыдущих этапах.
Насколько мне (не)известно, отсутствуют содержательные примеры пар алгоритм/КлассФункций, для которых, при сложности функций, сравнимых с обычно рассматриваемыми для ГА (скажем, задача коммивояжёра), такого сорта алгоритм в каком-то смысле был бы гораздо лучше, чем случайный перебор. Что скажете на это?

В случае классического ГА "потомок" явно зависит от всех особей предыдущей популяции и, вообще говоря, от номера в новой популяции, но известны и варианты "однородные во времени": потомок замещает самого плохого представителя популяции (и программировать легче).
Впрочем, вернёмся к классике. Популяцию вместе со значениями целевой функции (целочисленной, ограниченной) назовём СОСТОЯНИЕМ. Имеем конечное число состояний и вероятности перехода от одного состояния в другое (зависят от функции) - однородная цепь Маркова налицо. Она имеет финальное/предельное распределение (благодаря ненулевой вероятности любого перехода). Фактически процесс обрываем на ранней стадии, начав его из произвольного распределения (т.е. взяв в качестве начального равномерное распределение). Наши игры с ГА и данной функцией имеют смысл только в том
случае, если финальное распределение "гораздо лучше" - и вот здесь опять констатирую, что теорем-то нету...