1.3.1.Эксперименты Фогеля
Один из создателей эволюционного программирования Л.Фогель рассматривал интеллектуальное поведение индивида, как способность успешно предсказывать поведение среды, в которой он находится, и сообразно с этим действовать. В 60-x годах прошлого века Фогель поставил ряд экспериментов [] по созданию искусственных систем, способных адаптироваться к первоначально не известной им среде. В проведенных экспериментах Л. Фогель моделировал поведение простейшего живого существа, которое способно предсказывать изменения параметра среды, обладающего периодичностью. Это живое существо моделировалось конечным автоматом с действиями на переходах – автоматом Мили. В качестве среды выступала последовательность символов над двоичным алфавитом, например, (1111010010)*. На вход автомата в каждый момент времени подавалась битовое значение параметра окружающей среды. Автомат формировал значение выходной переменной – возможное значение рассматриваемого параметра в следующий момент времени. На 1.3.1 приведен один из возможных автоматов, который построен для распознавания, указанной выше последовательности.
|
|
|
Задача состояла в эволюционном построении автомата, способного как можно более точно в смысле какой-либо разумной функции приспособленности от входа и выхода (например, числа совпавших символов) предсказывать среду – угадывать следующий символ последовательности. Кроме того, Фогель накладывал ограничения на сложность порождаемого автомата, так как строить автоматы равные длине обозреваемой последовательности не представляет труда. Таким образом, предпочтение отдавалось автоматам, угадывающим как можно лучше, и в то же время имеющим как можно меньше состояний. В начале эксперимента задавалась периодическая последовательность символов над двоичным алфавитом, например (101110011101)*. На начальной фазе выбирался префикс данной последовательности малой длины. После этого создавалась популяция автоматов с небольшим числом состояний (около пяти). Затем каждый из автоматов путем одной из пяти мутаций (выбираемой случайным образом равномерно) производил потомка. Далее над потомком подобным образом производилось еще несколько мутаций (их число определялось случайным образом). Получившийся в результате мутаций автомат добавлялся в популяцию. Были допустимы следующие мутации автомата:
добавление состояния;
удаление состояния (в случае, если число состояний больше единицы);
замена стартового состояния (в случае, если число состояний больше единицы);
замена перехода;
замена действия на переходе.
После добавления потомков в популяцию на всех ее особях вычислялась функция приспособленности. Половина наиболее приспособленных особей переносилась в популяцию следующего поколения, а менее приспособленные автоматы – отбрасывались. Таким образом, размер популяции оставался постоянным (стоит отметить, что в силу ограниченных возможностей компьютеров того времени, он был мал – всего несколько особей). Данный процесс продолжался до тех пор, пока не удавалось достигнуть желаемого результата – максимальное значение функции приспособленности не превосходило заданного порога. После этого к битовой последовательности, которая определяла среду, добавлялся очередной символ, и эволюционный процесс переходил в очередную фазу. По мнению Л. Фогеля, результаты экспериментов показали, что эволюционное программирование может быть успешно применено для построения «интеллектуальных» искусственных систем. При этом было отмечено, что построение вручную автоматов столь же результативных и простых, как те, что были построены эволюционным алгоритмом, является крайне сложной задачей. ^