Участник:Sergey Ivanov/Генетические алгоритмы - История изменений

Sergey Ivanov: /* Масштабируемость алгоритма и его реализации */

2017-12-03T18:13:48Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 18:13, 3 декабря 2017
Строка 130:		Строка 130:
	== Масштабируемость алгоритма и его реализации ==		== Масштабируемость алгоритма и его реализации ==

	На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.1. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2		На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.01. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2

	[[file:GeneticOptimizationStrongScalability.png\|thumb\|center\|600px\|Рис.2. Сильная масштабируемость генетической оптимизации]]		[[file:GeneticOptimizationStrongScalability.png\|thumb\|center\|600px\|Рис.2. Сильная масштабируемость генетической оптимизации]]

Sergey Ivanov: /* Последовательная сложность алгоритма */

2017-12-03T18:07:43Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 18:07, 3 декабря 2017
Строка 69:		Строка 69:

	== Последовательная сложность алгоритма ==		== Последовательная сложность алгоритма ==
	Предположим, что сложность одного вычисления функции ~~<math>F</math>~~ имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:		Предположим, что сложность одного вычисления фитнес-функции имеет сложность <math>F</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

	Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;		Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Sergey Ivanov: /* Входные и выходные данные алгоритма */

2017-11-30T15:48:57Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 15:48, 30 ноября 2017
Строка 108:		Строка 108:
	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==

	'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>		'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>;
	<math>\mathbb{X}</math> должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.		<math>\mathbb{X}</math> должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

Sergey Ivanov: /* Входные и выходные данные алгоритма */

2017-11-30T15:48:42Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 15:48, 30 ноября 2017
Строка 109:		Строка 109:

	'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>		'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>
	\mathbb{X} должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.		<math>\mathbb{X}</math> должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

	'''Выходные данные''': субоптимальный <math>x \in \mathbb{X}</math>		'''Выходные данные''': субоптимальный <math>x \in \mathbb{X}</math>

Sergey Ivanov: /* Входные и выходные данные алгоритма */

2017-11-30T15:48:12Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 15:48, 30 ноября 2017
Строка 111:		Строка 111:
	\mathbb{X} должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.		\mathbb{X} должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

	'''Выходные данные''': субоптимальный <math>x in \mathbb{X}</math>		'''Выходные данные''': субоптимальный <math>x \in \mathbb{X}</math>

	'''Параметры''':		'''Параметры''':

Sergey Ivanov: /* Структура алгоритма */

2017-11-30T15:47:52Z

Структура алгоритма

← Предыдущая версия		Версия от 15:47, 30 ноября 2017
Строка 31:		Строка 31:
	На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>		На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

	== Возможные вариации ==		=== Возможные вариации ===

	Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:		Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:
Строка 39:		Строка 39:
	* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.		* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

	=== Вычислительное ядро алгоритма ===		== Вычислительное ядро алгоритма ==
	В типичной ситуации [[глоссарий#Вычислительное ядро\|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:		В типичной ситуации [[глоссарий#Вычислительное ядро\|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
	* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.		* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.

Sergey Ivanov в 15:22, 30 ноября 2017

2017-11-30T15:22:15Z

← Предыдущая версия		Версия от 15:22, 30 ноября 2017
Строка 88:		Строка 88:
	На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.		На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

	[[file:GA_Graph.png\|thumb\|center\|~~300px~~\|Рис.1. Информационный граф генетического поиска]]		[[file:GA_Graph.png\|thumb\|center\|500px\|Рис.1. Информационный граф генетического поиска]]

	Формально граф на рис.1 состоит из следующих элементов:		Формально граф на рис.1 состоит из следующих элементов:
Строка 132:		Строка 132:
	На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.1. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2		На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.1. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2

	[[file:~~GA_Graph~~.png\|thumb\|center\|~~300px~~\|Рис.2. Сильная масштабируемость генетической оптимизации]]		[[file:GeneticOptimizationStrongScalability.png\|thumb\|center\|600px\|Рис.2. Сильная масштабируемость генетической оптимизации]]

	Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины <math>D=100</math> от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.		Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины <math>D=100</math> от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.

Sergey Ivanov в 15:20, 30 ноября 2017

2017-11-30T15:20:13Z

Внесённые изменения

Sergey Ivanov в 15:18, 30 ноября 2017

2017-11-30T15:18:46Z

@@ Строка 115: / Строка 115: @@
 '''Параметры''':
 * размер популяции (100-1000)
-* количество особей для отбора (например, относительно объёма размера популяции; обычно 10-50%)
+* количество особей для отбора (например, относительно объёма размера популяции; обычно 5-50%)
-* операция кроссинговера <math>Crossover: \mathbb{X} \to \mathbb{R} </math>
+* операция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно это одна из типично используемых процедур: поэлементное среднее, какая-либо её стохастическая модификация, случайный выбор для каждого гена, от какого родителя взять значение.
 = Литература =
 <references />

Sergey Ivanov: /* Входные и выходные данные алгоритма */

2017-11-30T15:03:03Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 15:03, 30 ноября 2017
Строка 107:		Строка 107:

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===
	В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: ~~векторы~~, ~~матрицы, скаляры, множества~~, ~~плотные или разреженные структуры данных, их объем~~. ~~Полезны предположения относительно диапазона значений или структуры,~~ например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-~~то значений к машинному нулю, характер разреженности матриц и другие.~~
			'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>
			\mathbb{X} должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

			'''Выходные данные''': субоптимальный <math>x in \mathbb{X}</math>

			'''Параметры''':
			* размер популяции (100-1000)
			* количество особей для отбора (например, относительно объёма размера популяции; обычно 10-50%)
			* операция кроссинговера <math>Crossover: \mathbb{X} \to \mathbb{R} </math>

	= Литература =		= Литература =
	<references />		<references />