Участник:Kilkavteste 607/Генетический алгоритм: различия между версиями
| Строка 2: | Строка 2: | ||
== Общее описание алгоритма == | == Общее описание алгоритма == | ||
| + | Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. | ||
| + | |||
| + | Можно выделить следующие этапы генетического алгоритма: | ||
| + | |||
| + | *Задание целевой функции (функции приспособленности) для особей популяции | ||
| + | *Создание начальной популяции | ||
| + | *Цикл (пока не выполнится критерий останова): | ||
| + | |||
| + | **Размножение (скрещивание) | ||
| + | **Мутирование | ||
| + | **[Кросиннговер] - по желанию | ||
| + | **Вычисление значения целевой функции для всех особей, полученных в результате предыдущих этапов цикла | ||
| + | **Формирование нового поколения (селекция) | ||
| + | |||
| + | Критериями останова могут служить: | ||
| + | |||
| + | *нахождение глобального, либо субоптимального решения; | ||
| + | *исчерпание числа поколений, отпущенных на эволюцию; | ||
| + | *исчерпание времени, отпущенного на эволюцию. | ||
| + | |||
| + | Необходимо заметить, что не существует общепринятых стандартов реализации генетического алгоритма, поэтому каждый может самостоятельно решить, как именно он будет реализовывать конкретный этап эволюционного процесса. | ||
| + | |||
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
== Вычислительное ядро алгоритма == | == Вычислительное ядро алгоритма == | ||
Версия 15:55, 15 октября 2017
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Можно выделить следующие этапы генетического алгоритма:
- Задание целевой функции (функции приспособленности) для особей популяции
- Создание начальной популяции
- Цикл (пока не выполнится критерий останова):
- Размножение (скрещивание)
- Мутирование
- [Кросиннговер] - по желанию
- Вычисление значения целевой функции для всех особей, полученных в результате предыдущих этапов цикла
- Формирование нового поколения (селекция)
Критериями останова могут служить:
- нахождение глобального, либо субоптимального решения;
- исчерпание числа поколений, отпущенных на эволюцию;
- исчерпание времени, отпущенного на эволюцию.
Необходимо заметить, что не существует общепринятых стандартов реализации генетического алгоритма, поэтому каждый может самостоятельно решить, как именно он будет реализовывать конкретный этап эволюционного процесса.
