Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов

Скачать 417.12 Kb.

Название	Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов
страница	2/11
Дата публикации	07.07.2013
Размер	417.12 Kb.
Тип	Документы

100-bal.ru > Информатика > Документы

1 2 3 4 5 6 7 8 9 10 11

Глава 2.Общие концепции генетического и автоматного программирования

Генетические алгоритмы

Генетический алгоритм (genetic algorithm) [1–4] представляет собой стохастический метод оптимизации. Основная идея генетических алгоритмов состоит в использовании принципа естественного отбора, который составляет основы теории эволюции живых организмов, предложенной Чарльзом Дарвином.

Основы генетических алгоритмов были заложены Дж. Холландом (J. Holland) – в 1975 году он опубликовал книгу «Адаптация в естественных и искусственных системах». Описанный в ней подход был в дальнейшем развит Холландом и его учениками в Мичиганском университете.

Кратко сформулировать принцип естественного отбора можно следующим образом: наименее приспособленные особи умирают раньше, а наиболее приспособленные выживают и дают потомство. Потомство выживших особей оказывается в среднем более приспособленным, но среди них опять выделяются более приспособленные особи, и так далее.

В генетическом алгоритме все то же самое. В качестве особей выступают элементы пространства возможных решений некоторой задачи (маршруты коммивояжера, диаграммы переходов автомата и т. п.). Задан набор генетических операций, с помощью которых из существующих особей формируются новые. Кроме этого определена так называемая функция приспособленности (fitness-function), которая показывает, насколько «хорошим» решением задачи является особь.

Процесс работы генетического алгоритма состоит в генерации поколений особей до тех пор, пока не будет выполнено некоторое условие останова (например, достигнуто целевое значение функции приспособленности или сгенерировано заданное число поколений). На рис. 1 приведена общая схема работы генетического алгоритма.

Рис. 1. Общая схема работы генетического алгоритма

По сравнению с традиционными методами оптимизации генетические алгоритмы имеют ряд преимуществ:

генетические алгоритмы легко модифицируются для параллельных вычислений;

они хорошо подходят для оптимизации недиффернцируемых функций.

Основными недостатками генетических алгоритмов являются:

высокая трудоемкость, ограничивающая их область применения;

сложность оценки степени пригодности конкретных генетических операций для конкретной задачи.

2.1.1Традиционный генетический алгоритм

В этом разделе приведено краткое описание традиционного генетического алгоритма (conventional genetic algorithm) [4] с одноточечной рекомбинацией и мутацией. В этом алгоритме каждая особь представляет собой битовую строку длины l, а размер популяции равен n.

Шаг 1. Генерации начальной популяции

. Для этого, например, можно сгенерировать n битовых строк, в которых каждый из l битов равен 0 или 1 с одинаковой вероятностью.

Шаг 2. Вычислить функцию приспособленности f(x) для каждой особи из текущей популяции. Этот шаг обычно является наиболее трудоемким по времени во всем алгоритме. Отметим, что при вычислении функции приспособленности, как правило, необходимо осуществить декодирование некоторого объекта из двоичной строки.

Шаг 3. Переход к следующему поколению популяции. При создании нового поколения могут использоваться различные стратегии. Далее будет описан так называемый алгоритм рулетки (roulette wheel selector) [2].

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

После этого с некоторой наперед заданной вероятностью происходит рекомбинация (кроссовер, скрещивание) родительских особей. В результате образуются их «потомки» - z₁ и z₂. Происходит это следующим образом: случайно (с равномерным распределением на множестве {1, 2, …, l}) выбирается число k. Хромосомы «потомков» z₁ и z₂ теперь строятся следующим образом: для z₁ – первые k символов совпадают с первыми k символами x, последние (l-k) – с последними (l-k) символами y, для z₂ – наоборот. Например, если l=7, x=1001010, y=0001001, k=3, то z₁=1001001, z₂=0001010. «Забудем» теперь о «родителях» x и y, обозначив x=z₁, y=z₂.

После этого равновероятно выбирается одна из особей x либо y – выбранную особь обозначим как z.

С некоторой (как правило, порядка 0.01) вероятностью происходит мутация особи z – в ней случайно выбирается один бит и изменяется.

Получившаяся в результате особь z добавляется в следующее поколение.

Шаг 4. Повторять шаги 2 и 3 до тех пор, пока не будет выполнено условие останова (максимальная приспособленность в популяции достигла целевого значения, прекратился рост максимальной приспособленности, число поколений достигло некоторого предела и т.д.).

Отметим, что кроме описанных выше одноточечного кроссовера, алгоритма рулетки и мутации изменением случайного бита, существуют и другие методы – обзор таких методов приведен в [5].

2.1.2Математический аппарат традиционного генетического алгоритма

Вопрос о том, почему традиционный генетический алгоритм работает, то есть происходит в вероятностном смысле постепенная оптимизация функции приспособленности обсуждается в [3, 6–9]. В [3,9] приводится, по сути неформальное, объяснение функционирования генетических алгоритмов, в [6] – формализованное, но при условии достаточно сильных ограничений на функцию приспособленности. Математическая модель традиционного генетического алгоритма описана в [7, 8].

1 2 3 4 5 6 7 8 9 10 11

Похожие:

	Разработка методов совместного применения генетического и автоматного программирования Комитета по скалолазанию, тренерского совета и спортсменов-скалолазов, членов сборной команды Украины		Разработка методов совместного применения генетического и автоматного программирования Учебник предназначен для студентов технических вузов по специальности 010100 математика. Работа студентов по этому учебнику позволит...
	Развитие формализма метода подвижных клеточных автоматов для изучения...		Методическая разработка по внедрению проектного метода на уроках географии Данная методическая разработка предполагает проведение уроков по дисциплине География с использованием элементов проектного метода...
	Разработка метода и адаптивных алгоритмов компрессии с гарантированной... Работа выполнена на кафедре «Математического обеспечения и применения эвм» Технологического института Южного федерального университета...		Министерство образования Российской Федерации Санкт Петербургский... Задачи курса: Изучить основные математические результаты и методы, лежащие в основе метода конечных элементов и других вариационных...
	План: Общие понятия об алгоритме Способы записи алгоритмов История... Так, чтобы решить полное квадратное уравнение, необходимо знать конкретные значения коэффициентов а, b и с (начальные условия). В...		Электронные образовательные ресурсы для учащихся Лев Николаевич Толстой (Война и Мир), Федор Михайлович Достоевский (Преступление и наказание, Идиот). Большое собрание стихотворений...
	Разработка урока Автор: Целюрик Юлия Петровна Тема: «Знакомство со... Используемые программные приложения из пакета спо: Среда программирования Скретч (Scratch)		Прогнозирование трещиностойкости бетона на основе метода конечных элементов Реальное строение материала и особенности его поведения под нагрузкой отражено в структурных теориях прочности. Однако практическое...
	Урок по алгебре и математическому анализу в 10 классе по теме «Решение... Обучающая цель: Изучить возможности применения метода интервалов для решения тригонометрических неравенств		26. Мельников Федор Михайлович Мельников Федор Михайлович родился 31 июля 1942 года в дер. Остречиха Сандовского района Калининской области
	Программное обеспечение для решения задач линейного программирования... Линейными ограничениями. Основой программы служит алгоритм симплекс метода для неограниченного числа условий и переменных. В алгоритме...		Студента 617 группы фртк давидюка Дмитрия Сергеевича Научный к т.... Поэтому, когда мы измеряем биологические потенциалы, мы видим результат синхронной деятельности совокупности клеток мозга, и эта...
	Доклад ронжина Андрея Леонидовича по диссертационной работе «Разработка... «Разработка адаптивного метода робастного понимания слитной речи на основе интегральной обработки данных», представленной на соискание...		Методическая разработка «Одномерные массивы» на языке программирования... «Одномерные массивы» на языке программирования pascal в теории и практике школьного курса «Информатика и икт»/ Методическая разработка....

Школьные материалы

Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов

Глава 2.Общие концепции генетического и автоматного программирования

Генетические алгоритмы

2.1.1Традиционный генетический алгоритм

2.1.2Математический аппарат традиционного генетического алгоритма

Похожие: