Автор работы: Пользователь скрыл имя, 24 Декабря 2012 в 09:47, реферат
Генетический алгоритм — это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым или сложно-решаемым проблемам через последовательный подбор и комбинирование искомых параметров с использованием механизмов, напоминающих биологическую эволюцию.
Генетические алгоритмы являются частью более общей группы методов, называемой эволюционными вычислениями, которые объединяют различные варианты использования эволюционных принципов для достижения поставленной цели.
1. Введение 2
1.1 Мягкие вычисления 2
1.2 Эволюционные вычисления 2
2. История 3
2.1 Несколько открытий в биологии 3
2.2 Ключевые работы 3
3. Классический ГА 4
3.1 Постановка задачи и функция приспособленности 4
3.2 Принцип работы ГА 5
3.3 Алгоритм работы 5
3.4 Отбор 6
3.5 Скрещивание 7
3.6 Мутация 7
3.7 Критерии останова 7
4. Теория 8
4.1 Шаблоны 8
4.2 Неявный параллелизм 9
4.3 Теорема шаблонов 9
5. Настройка ГА 10
6. Различные модификации ГА 11
6.1 Кодирование 11
6.2 Стратегии отбора 12
6.3 Кроссовер 12
6.4 Стратегии формирования нового поколения 12
7. Некоторые модели ГА 13
7.1 Genitor (Whitley) 13
7.2 CHC (Eshelman) 13
7.3 Hybrid algorithm (Davis) 13
7.4 Island Models 14
8. Факторы, создающие сложность для ГА 15
9. Выводы 16
10. Ссылки 17
Исследования показали, что поиск гиперплоскостей происходит лучше, а сходимость быстрее, чем у классического ГА.
CHC – это Cross generational elitist selection, Heterogenous recombination, Cataclysmic mutation.
Для нового поколения выбираются N лучших различных особей среди родителей и детей. Дублирование строк не допускается.
Для
скрещивания все особи
При скрещивании используется так называемый HUX-оператор (Half Uniform Crossover), разновидность однородного кроссовера – каждому потомку переходит ровно половина битов каждого родителя.
Размер популяции небольшой. Этим оправдано использование однородного кроссовера.
Данный алгоритм довольно быстро сходится из-за того, что в нем нет мутаций. В этом случае CHC применяет cataclysmic mutation: все строки, кроме самой приспособленной, подвергаются сильной мутации (изменяется около трети битов). Таким образом, алгоритм перезапускается и далее продолжает работу, применяя только кроссовер.
Использование гибридного алгоритма позволяет объединить преимущества ГА с преимуществами классических методов.
Дело в том, что ГА являются робастными алгоритмами, т.е. позволяют находить хорошее решение, но нахождение оптимального зачастую оказывается намного более трудной задачей в силу стохастичности принципов работы алгоритма. Поэтому возникла идея использовать ГА на начальном этапе для эффективного сужения пространства поиска вокруг глобального экстремума, а затем, взяв лучшую особь, применить один из "классических" методов оптимизации.
Однако можно использовать "классические" методы (hill-climbing, например) и внутри самих ГА. На каждом поколении каждый полученный потомок оптимизируется этим методом, таким образом, каждая особь достигает локального максимума, вблизи которого она находится, после чего подвергается отбору, скрещиванию и мутации. Такой метод ухудшает способность алгоритма искать решение с помощью отбора гиперплоскостей, но зато возрастает вероятность того, что одна из особей попадет в область глобального максимума и после оптимизации окажется решением задачи.
Островная модель (island model) — модель параллельного генетического алгоритма. Разобьем популяцию на несколько подпопуляций. Каждая их них будет развиваться отдельно с помощью некого генетического алгоритма. Таким образом, можно сказать, что мы расселили особи по нескольким изолированным островам.
Изредка (например, каждые 5 поколений) происходит миграция – острова обмениваются несколькими хорошими особями.
Так как населённость островов невелика, то подпопуляции будут склонны к преждевременной сходимости. Поэтому важно правильно установить частоту миграции:
Генетические алгоритмы стохастичны, поэтому при разных его запусках популяция может сходиться к разным хорошим решениям. Островная модель позволяет запустить алгоритм сразу несколько раз и совместить «достижения» разных островов для получения наилучшего решения.
Свойства функций приспособленности, создающие сложность для ГА.
На картинке изображен график функции Растригина с одним аргументом.
Пример: пусть строка состоит из 10-ти четырехбитных подстрок. Пусть равно количеству единиц в i-той подстроке. Зададим функцию g(u) следующей таблицей:
u |
0 |
1 |
2 |
3 |
4 |
g(u) |
3 |
2 |
1 |
0 |
4 |
и пусть функция
приспособленности равна сумме