Автор относится к тем несчастным (или, наоборот - счастливым), которые всю жизнь изобретают велосипед, то есть - уже изобретенное. Справедливости ради, не только это, да и чаще это оказывается вовсе не велосипед, по своему функциональному назначению, а скорее лишь нечто напоминающее велосипед.
Теорию относительности и опыт Майкельсона - Морли я точно не опровергал и не пытался (а я знаю и таких велосипедистов, и как - нибудь выложу фото соответствующей "установки").
Но именно генетические алгоритмы (ГА) я пере-изобрел в самом прямом смысле в районе 1995 г, программируя на Lisp в его реализации компанией Autodesk - AutoLisp, сиречь в Autocad-е. Каково же было мое разочарование, когда я узнал о работах Джона Холланда, выполненных еще 60-х гг.
(Переведенная статья Дж. Холланда в журнале "В мире науки" - русскоязычной версии Scientific American)
Базовая структура данных Lisp - список - сама напрашивается на то, чтобы применить к ней кроссовер (или кроссинговер) - ключевую (кроме мутаций) операцию над хромосомами в ГА: Взял "половинку" от одного списка, взял другую "половинку" от другого списка, склеил их - вот тебе новый список. Хромосома - это кандидат на искомое "оптимальное" (в том или ином смысле) решение. ГА состоит в том, что заводится целая популяция хромосом, и над ними запускается процесс компьютерной "эволюции", состоящий в том, что хромосомы мутируют и скрещиваются, пока кто-то не решит, что большинство хромосом собрались возле некоторой одной структуры, которое и признается решением.
Зачем? Как было в классике советского эстрадного юмора - "вопрос конечно интересный". По сути, у меня была такая же цель, как у Холланда, хотя я не сразу это отрефлексировал - мне нужно было "широкими мазками" прошерстить пространство решений в какой-то задаче.
Вообще, кроссовер изначально объясняют на битовых строках (массивах битов):
Автор сразу работал именно со списками. Внешне список очень похож на массив, но только - если это простой (плоский) список. А так-то элементами списка могут быть другие списки:
((a, b, c), d, e, ((f, g), h))
Такой список с вложениями представляет собой, по сути, дерево. Кроссовер в дереве означает обмен целыми ветками, причем на место того, что было "маленькой" веткой или листом, вдруг может встать довольно "толстый", разветвленный сук. И вот таким автор с самого начала и занялся в AutoLisp, и только потом узнал, что можно было начать и попроще :D
Зачем нужен кроссовер?
Это позволяет резко набрать скорость поиска высоко - продуктивных "частей" решения, причем сразу в нужных комбинациях.
Вообще, в целом, ГА - именно о постепенном составлении конечного решения из каких-то полезных кусков. Если один родитель нашел какую-то важную частичную комбинацию битов или символов (это называется блок - см. далее), и другой родитель тоже нашел какую-то другую важную комбинацию - почему бы их не объединить?
Тут можно вспомнить старый, можно сказать - легендарный - анекдот (или быль) про какую-то голливудскую диву, которая предложила Эйнштейну пожениться, ведь их дети будут такими же умными, как Эйнштейн, и такими же красивыми, как она. "А если наоборот?" - ответил Эйнштейн вопросом.
Вопрос более чем резонный. Ответ на него такой: сочетание невыгодных признаков или невыгодное сочетание признаков, вроде бы выгодных по отдельности, будет выпилено отбором (на то и ГА, что все кандидаты в решение, объединенные в "популяцию", подвергаются отбору, то есть тестирование на пригодность - fitness - для искомого критерия). А вот полезные комбинации отдельных кусков - наоборот, будут распространяться в в популяции, найденное хорошее решение будет только усиливаться. Поэтому, кстати, важен размер популяции - чтобы было куда размножаться, по доле от общего количество, носителям правильных, хороших комбинаций.
Интуитивно ясно, что чем короче комбинация битов в строке, тем у нее больше шансов сохраниться при множественных кроссоверах, потому что тем менее вероятно, что нож кроссовера разрубит эту комбинацию. Такие короткие устойчивые комбинации, сохраняющиеся в процессе эволюции, получили название блоков. Окончательное" решение, которое найдет ГА, будет, по сути, комбинацией, составленных именно из таких блоков.
На уровне теоретического анализа есть "теорема о шаблонах" самого Холланда. Там получено уравнение, чем-то напоминающее уравнения Больцмана или Фоккера-Планка в статистической физике, описывающее развитие во времени относительных долей разных блоков. Не буду врать, что я специалист в этом деле, но у меня сложилось впечатление, что количественного понимания это уравнение не дает, скорее помогает правильно рассуждать при программировании ГА - но реальная настройка ГА под каждую конкретную задачу - вопрос экспериментальный, и зависит от опыта и искусства программиста.
Стэн Улам - еще до Холланда
Напомню - главный смысл кроссовера в ускорении эволюции, которая сходится к эффективному решению (при этом ГА ищет только приближенное решение, для этого он и нужен, ибо прямой перебор оказывается невозможным ввиду гигантского числа возможных вариантом - так называемые NP задачи, если кто не в курсе).
Но в случае ГА это ускорение не вполне очевидно. Выше я очень грубо объяснил, почему оно происходит. Теорема о шаблонах пытается внести сюда какую-то более наукоподобную точность, но получается так себе.
Однако, оказывается, что почти одновременно с Холландом почти этот же самый вопрос рассмотрел ни кто иной, как сам Стэн Улам - физик теоретик, который стоял у истоков не только компьютерного моделирования, но и компьютеров в их современном (после ВМВ) понимании как таковых. В статье 1970 г (но вычисления были выполнены раньше, в середине 60-х) Some Elementary Attempts at Numerical Modeling of Problems Concerning Rates of Evolutionary Processes Улам предложил целую иерархию очень простых моделей эволюции (обычной биологической эволюции, произошедшей на Земле). Первая модель называется Adam, а каждая следующая модель построена как надстройка над предыдущей.
В моделях Улама нет никаких хромосом, они гораздо проще. Улама и его коллег интересовало всего лишь, как быстро некоторая популяция наберет некоторое необходимое число мутаций. При этом, все мутации безликие, как одинаковые камушки или шарики - важно только их количество.
Скрещивание геномов при половом размножении появляется у Улама уже при первой модификации исходной модели, которая ожидаемо называется EVE (Ева). Но раз мутации безликие, в отличие от хромосом ГА, то Уламу пришлось выдумывать разные политики, по которым особи обмениваются мутациями (хотели уйти от структуры генома - пришлось ввести сложную структуру процедуры обмена мутациями). Эти политики создали все последующие вариации Евы.
Так или иначе, простой и главный результат Улама: именно обмен мутациями, более или менее сложный и структурированный, ускоряет эволюцию.
При чем здесь Герцен?
Я решил упомянуть Александра Ивановича вовсе не для красного словца. Александр Иванович, как и многие европейские философы стали говорить о "закате" Западной цивилизации и культуры. Я не буду здесь закапываться в историю этого направления мысли философов, и откуда вообще взялась эта проблема (ну, если разразилась Первая Мировая, то все разговоры были совсем небезосновательны).
Лепта А. И. Герцена в той дискуссии состояла в предположении, что западная (европейская) культура никуда не денется, но она диссоциирует и перейдет в другие культуры своими частями. Западная мысль, писал Герцен, войдет в структуру будущих культур так же, как наши тела рано или поздно войдут в траву и животных.
На мой взгляд, для 19 века это совершенно нетривиальное утверждение. Оно нетривиальное до сих пор, поскольку, скажем так, снобизм современных обществ настолько высок, что не допускает утраты своей целостности. Между тем, пора привыкать к мысли, что культурная эволюция не может протекать как-то сильно иначе, чем биологическая эволюция, и должна с неизбежностью включать в себя какое - то скрещивание и перемешивание информации.