Использование генетических алгоритмов для генерации конечных автоматов
Автор: Лобанов П.Г.
Источник: http://is.ifmo.ru/disser/...
Автор: Лобанов П.Г.
Источник: http://is.ifmo.ru/disser/...
Для различных биологических объектов характерна оптимальность, а также согласованность и эффективностью их работы. Многих исследователей давно интересовал «философский» вопрос – возможно ли эффективное построение значимых и полезных для человека систем на основе принципов биологической эволюции? Подобные идеи возникали у ряда исследователей. В 1962 г. Л. Фогель начал моделировать интеллектуальное поведение индивида и его развитие в процессе эволюции [6]. При этом поведение индивида задавалось конечным автоматом. Продолжая эти исследования, Л. Фогель, А. Оуэнс и М. Уолш предложили в 1966 г. схему эволюции конечных автоматов, решающих задачи предсказания [3]. Примерно в это же время (в середине 60-х годов) Дж. Холланд разработал новый метод поиска оптимальных решений – генетические алгоритмы. Результатом его исследований стала книга [7], вышедшая в 1975 г. Эти работы заложили основы эволюционных
вычислений. Приведем ряд определений, которые играют важную роль в теории эволюционных вычислений и необходимы для описания генетических алгоритмов.
Популяция – это совокупность особей на рассматриваемой стадии эволюции.
Индивид (особь) – единичный представитель популяции.
Хромосома – структура, содержащая генетический код индивида. Ген – определенная часть хромосомы, кодирующая врожденное качество
индивида.
Функция приспособленности (fitness-функция, приспособленность) – определяет, как близка особь к решению задачи. Генетические алгоритмы [5] – это оптимизационный метод, базирующийся на принципах естественной эволюции популяции особей (индивидов). Задача оптимизации состоит в максимизации функции приспособленности (фитнес-функции). В процессе эволюции (в результате отбора, скрещивания и мутаций особей, а также других операторов генетических алгоритмов) происходит поиск особей с высокой приспособленностью. По сравнению с другими оптимизационными методами генетические алгоритмы имеют особенности: параллельный поиск, случайные мутации
и скрещивание уже найденных хороших решений. Приведем описание генетических операторов. Стратегия отбора определяет каким образом формируется новое поколение особей. Известны различные стратегии отбора, например, отбор отсечением [8], турнирный отбор [9], элитизм [9] и пропорциональный отбор [8]. Кратко опишем особенности каждой из этих стратегий:
• Отбор отсечением использует отсортированную по убыванию приспособленности популяцию. Число особей для скрещивания определяется в соответствии с порогом. Порог определяет какая доля особей, начиная с самой первой (самой приспособленной), будет принимать участие в отборе.
• Турнирный отбор работает следующим образом: из популяции случайным образом выбирается t особей. Наиболее приспособленная из этих особей допускается к скрещиванию (между особями проводится турнир).
• Пропорциональный отбор подразумевает, что сначала подсчитывается приспособленность каждой особи fi и вычисляется средняя приспособленность особей в популяции fi= =N i 1 ср i f f . После этого строится промежуточная популяция, причем вероятность попадания особи в эту популяцию определятся соотношением ср i f f . Например, если дробь равна 2.36, то особь будет добавлена в промежуточную популяцию два раза. С вероятностью 0.36 она будет добавлена третий раз. Особи для скрещивания выбираются из промежуточной популяции случайным равновероятным образом.
• Элитизм подразумевает, что несколько лучших родительских особей добавляются в новое поколение. Использование элитизма позволяет не потерять хорошее промежуточное решение, но в тоже время из-за него алгоритм может застрять в локальном экстремуме. Как известно, в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков отвечает оператор, который называется скрещивание. В литературе по генетическим алгоритмам этот оператор называют также кроссинговер, кроссовер или рекомбинация. Итак, скрещивание – процесс обмена генетическим материалом. Это операция, при которой две хромосомы обмениваются своими частями.
Мутация – случайное изменение одной или нескольких позиций в хромосоме. Мутации могут иметь как отрицательные, так и положительные последствия – приводить к появлению у индивида новых признаков. Таким образом, мутации являются двигателем естественного отбора, так как обеспечивают поддержание разнообразия особей в популяции. Порядок генов в хромосоме является часто критическим. В ряде работ были предложены методы для переупорядочения позиций генов в хромосоме во время работы алгоритма. Цель переупорядочения состоит в том, чтобы попытаться найти порядок генов, который имеет лучший эволюционный потенциал. Одним из таких методов является инверсия, выполняющая реверс порядка генов между двумя случайно выбранными позициями в хромосоме. Когда используются методы переупорядочения, гены должны содержать некоторую «метку», такую, чтобы их можно было правильно идентифицировать независимо от их позиции в хромосоме. Многие исследователи использовали инверсию в своих работах, однако мало кто из них пытался обосновать инверсию и определить ее вклад в работу генетического алгоритма в целом.
Переупорядочение также значительно расширяет область поиска. Мало того, что генетический алгоритм пытается находить «хорошие» множества генов, но он также одновременно пробует находить хорошее упорядочение генов. Еще раз отметим, что оператор переупорядочения изменяет структуру хромосомы. Как правило, выделяют еще один оператор для генетических алгоритмов – оператор генерации случайной особи, который может быть использован при создании начальной популяции, при пополнении популяции случайными особями и при некоторых мутациях. Для генетических алгоритмов характерна относительно простая структура особей. J. Koza [10] предложил задавать особи в виде деревьев решений. Генетические алгоритмы, основанные на таких структурах, получили название генетическое программирование. Термины «генетические алгоритмы» и «генетическое программирование» понимаются в широком смысле – для обозначения эволюционных вычислений. Для обозначения генетических алгоритмов, оперирующих с битовыми строками фиксированной длины (описанных, например, в работе [2]), используется термин «традиционные генетические алгоритмы».
Один из создателей эволюционного программирования Л.Фогель рассматривал интеллектуальное поведение индивида, как способность успешно предсказывать поведение среды, в которой он находится, и в соответствии с этим действовать. В 60-x годах прошлого века Л. Фогель поставил ряд экспериментов [3] по созданию искусственных систем, способных адаптироваться к первоначально не известной им
среде.
В проведенных экспериментах Л. Фогель моделировал поведение простейшего живого существа, названного «флиб», которое способно предсказывать изменения параметра среды, обладающего периодичностью. Это существо моделировалось конечным автоматом с действиями на переходах – автоматом Мили [11]. В качестве среды выступала последовательность символов над двоичным алфавитом, например, (1111010010). На вход автомата в каждый момент времени подавалась битовое значение параметра окружающей среды. Автомат формировал значение выходной переменной – возможное значение рассматриваемого параметра в следующий момент времени.
Задача состояла в эволюционном построении автомата, способного как можно более точно в смысле выбранной функции приспособленности (например, числа совпавших символов) предсказывать поведение среды – угадывать следующий символ последовательности. Кроме того, Л. Фогель накладывал ограничения на сложность порождаемого автомата, так как строить автоматы с числом состояний, равным длине обозреваемой последовательности, не представляет труда. Таким образом, предпочтение отдавалось автоматам, угадывающим как можно лучше, и в то же время имеющим как можно меньшее число состояний. В начале эксперимента [3] задавалась периодическая последовательность символов над двоичным алфавитом, например (101110011101) и выбирался префикс данной последовательности малой длины. После этого создавалась популяция автоматов с небольшим числом состояний (например, пять). Затем каждый из автоматов путем одной из описанных ниже пяти мутаций (выбираемой случайным образом равномерно) производил потомка. Далее над потомком подобным образом производилось еще несколько мутаций (их число определялось случайным образом). Получившийся в результате мутаций автомат добавлялся в популяцию. При этом были допустимы следующие мутации автомата:
• добавление состояния;
• удаление состояния (в случае, если число состояний больше единицы);
• замена начального состояния (в случае, если число состояний больше единицы);
• замена перехода;
• замена действия на переходе.
После добавления потомков в популяцию на всех ее особях вычислялась функция приспособленности. Половина наиболее приспособленных особей переносилась в популяцию следующего поколения, а менее приспособленные автоматы – отбрасывались. Таким образом, размер популяции оставался постоянным. Стоит отметить, что в силу ограниченных возможностей компьютеров того времени, размер популяции был мал – всего несколько особей. Данный процесс продолжался до тех пор, пока не удавалось достичь желаемого результата – максимальное значение функции приспособленности не превосходило заданного порога. После этого к битовой последовательности, которая определяла среду, добавлялся очередной символ, и эволюционный процесс переходил в очередную фазу. По мнению Л. Фогеля, результаты экспериментов показали, что эволюционное программирование может быть успешно применено для построения интеллектуальных искусственных систем. При этом было отмечено, что построение вручную автоматов столь же результативных и простых, как те, что были построены эволюционным алгоритмом, является крайне сложной задачей.
1. Шалыто А. А. Технология автоматного программирования / Труды первой Все- российской конференции “Методы и средства обработки информации”. МГУ. 2003, с. 150-152. http://is.ifmo.ru/works/tech_aut_prog
2. Mitchell M. An Introduction to Genetic Algorithms. MA: The MIT Press, 1996
3. Fogel L., Owens A., Walsh M. Artificial Intelligence through Simulated Evolution. NY: Wiley. 1966. (Фогель Л., Оуэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. М.: Мир, 1969)
4. Букатова И. Л. Эволюционное моделирование и его приложения. М.: Наука, 1979
5. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. М.: Физматлит, 2006
6. Fogel L. Autonomous Automata // Industrial Research. 1962. V.4, pp. 14–19
7. Hillis W. Co-Evolving Parasites Improve Simulated Evolution as an Optimization Procedure / In Artificial Life II. MA: Addison-Wesley, 1992. pp. 313?324
8. Whitley, D. A Genetic Algorithm Tutorial, Technical Report CS-93-103, Colorado State University, 1993
9. Blickle, T., and Thiele, L. A Comparison of Selection Schemes used in Genetic Algorithms. Technical Report №. 11. Gloriastrasse 35, CH-8092 Zurich: Swiss Federal Institute of Technology (ETH) Zurich, Computer Engineering and Communications Networks Lab (TIK), 1995
10. Koza J. R. Genetic programming. On the Programming of Computers by Means of Natural Selection. MA.: The MIT Press, 1998
11. Шалыто А. А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998. 102
12. Frey C., Leugering G. Evolving Strategies for Global Optimization – A Finite State Machine Approach /Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001). Morgan Kaufmann. 2001, pp. 27–33. http://citeseer.ist.psu.edu/456373.html
13. Tu M., Wolff E., Lamersdorf W. Genetic Algorithms for Automated Negotiations: A FSM-based Application Approach /Proceedings of the 11-th International Conference on Database and Expert Systems. 2000. http://ieeexplore.ieee.org/iel5/7035/18943/00875153.pdf
14. Naidoo A., Pillay N. The Induction of Finite Transducers Using Genetic Programming / Proceedings of Euro GP. Springer. 2007.