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

Kilkavteste 607: /* Математическое описание алгоритма */

2017-11-30T16:52:03Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 16:52, 30 ноября 2017
Строка 50:		Строка 50:
	3. Популяция		3. Популяция

	Начальная популяция будет состоять из <math> ~~10000~~ </math> особей. Каждая особь представляет собой набор трех геномов, сформированных случайным образом, как указано в п.2.		Начальная популяция будет состоять из <math> 2000 </math> особей. Каждая особь представляет собой набор трех геномов, сформированных случайным образом, как указано в п.2.

	4. Скрещивание		4. Скрещивание
Строка 67:		Строка 67:
	7. Критерий останова		7. Критерий останова

	За критерий останова взято ограниченное число поколений~~, равное <math> 512 \cdot 10^{4} </math>.~~		За критерий останова взято ограниченное число поколений.

	~~----~~

	~~Примечание: в процессе компьютерной реализации могут быть изменены некоторые точные величины~~.

	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==

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

2017-11-30T16:38:07Z

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

← Предыдущая версия		Версия от 16:38, 30 ноября 2017
Строка 171:		Строка 171:
	[[Файл:Time_genetic.jpg\|500px]] [[Файл:Efficiency_genetic.jpg\|500px]]		[[Файл:Time_genetic.jpg\|500px]] [[Файл:Efficiency_genetic.jpg\|500px]]

	На графиках заметно, что при увеличении процессоров до 64 начинает незначительно падать эффективность, засчет увеличения узлов, с которыми происходит обмен данными по принципу "все со всеми". Однако не лишним будет заметить, что параллельная работа значительно экономит время пользователя, уменьшая его практически в 2 раза при увеличении числа узлов в 2 раза, хоть и не всегда эффективно используя ресурсы.		На графиках заметно, что при увеличении процессоров до 64 начинает незначительно падать эффективность, засчет увеличения узлов, с которыми происходит обмен данными по принципу "все со всеми". Однако падение эффективности снижается при увеличении числа итераций, так как затраты на коммуникацию становятся значительно меньше, чем на решение самой задачи. Также не лишним будет заметить, что параллельная работа значительно экономит время пользователя, уменьшая его практически в 2 раза при увеличении числа узлов в 2 раза, хоть и не всегда эффективно используя ресурсы.

	== Динамические характеристики и эффективность реализации алгоритма ==		== Динамические характеристики и эффективность реализации алгоритма ==

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

2017-11-30T13:18:50Z

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

@@ Строка 157: / Строка 157: @@
 == Возможные способы и особенности параллельной реализации алгоритма ==
 == Масштабируемость алгоритма и его реализации ==
 == Динамические характеристики и эффективность реализации алгоритма ==
 == Выводы для классов архитектур ==

Kilkavteste 607: /* Существующие реализации алгоритма */

2017-11-30T12:45:19Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 12:45, 30 ноября 2017
Строка 160:		Строка 160:
	== Выводы для классов архитектур ==		== Выводы для классов архитектур ==
	== Существующие реализации алгоритма ==		== Существующие реализации алгоритма ==
			Генетический алгоритм реализован во многих пакетах программ, например, в библиотеке scipy языка Python, как алгоритм оптимизации.

	= Литература =		= Литература =

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

2017-11-30T11:51:26Z

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

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

	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==
			На вход алгоритму необходимо подать минимизируемую функцию <math>F(x)</math> с указанием ее размерности. На выходе пользователь получает минимальное значение функции.

	== Свойства алгоритма ==		== Свойства алгоритма ==

Kilkavteste 607: /* Ресурс параллелизма алгоритма */

2017-11-30T11:46:18Z

Ресурс параллелизма алгоритма

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

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
			Как можно заметить по информационному графу, приведенному в п.1.7, ресурсом параллелизма может быть количество итераций, при условии, что каждый узел в любой момент времени имеет доступ к входным данным - минимизируемой функции, а также к ее текущему минимальному значению. Также ресурсом параллелизма может являться размер популяции: вектор особей можно разделить между процессами и подвергнуть каждую часть независимому эволюционному процессу.

			Для достижения более качественного поиска минмимума можно реализовать периодический обмен (раз в несколько итераций) лучшими особями между процессами по принципу "все со всеми". Также коммуникация между процессами должна осуществлять выбор минимального значения среди всех найденных минимумов на разных процессорах.

			Необходимо заметить, что алгоритм поиска минимума, обозначенный на графе в п.1.7 узлом min нежно-зеленого цвета, также представляет собой ресурс параллелизма, однако параллельная реализация данного узла будет слишком трудозатратной из-за необходимости множественного обмена между процессорами по принципу "все со всеми" большое число раз.

	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==
	== Свойства алгоритма ==		== Свойства алгоритма ==

Kilkavteste 607: /* Информационный граф */

2017-11-30T11:35:22Z

Информационный граф

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

	== Информационный граф ==		== Информационный граф ==
	Приведем информационный граф макроструктуры алгоритма, тем самым простейшие операции не загромоздят рисунок и основная идея будет понятна. Алгоритмы-узлы подробно описаны в пунктах ~~[ДОБАВИТЬ]~~, их самостоятельная реализация не составляет труда.		Приведем информационный граф макроструктуры алгоритма, тем самым простейшие операции не загромоздят рисунок и основная идея будет понятна. Алгоритмы-узлы подробно описаны в пунктах 1.1-1.3, их самостоятельная реализация не составляет труда.
	Данный граф приведен для фиксированного набора данных: размерности минимизируемой функции: <math>DIM = 2</math>, количества особей в популяции: <math>P = 3</math> и числа итераций: <math>G = 4</math>. <br>		Данный граф приведен для фиксированного набора данных: размерности минимизируемой функции: <math>DIM = 2</math>, количества особей в популяции: <math>P = 3</math> и числа итераций: <math>G = 4</math>. <br>
	[[Файл:Graph_genetic.jpg\|700px]]		[[Файл:Graph_genetic.jpg\|700px]]

Kilkavteste 607: /* Информационный граф */

2017-11-30T11:34:38Z

Информационный граф

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

	== Информационный граф ==		== Информационный граф ==
			Приведем информационный граф макроструктуры алгоритма, тем самым простейшие операции не загромоздят рисунок и основная идея будет понятна. Алгоритмы-узлы подробно описаны в пунктах [ДОБАВИТЬ], их самостоятельная реализация не составляет труда.
			Данный граф приведен для фиксированного набора данных: размерности минимизируемой функции: <math>DIM = 2</math>, количества особей в популяции: <math>P = 3</math> и числа итераций: <math>G = 4</math>. <br>
			[[Файл:Graph_genetic.jpg\|700px]]

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==

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

2017-11-16T11:02:00Z

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

← Предыдущая версия		Версия от 11:02, 16 ноября 2017
Строка 117:		Строка 117:
	== Последовательная сложность алгоритма ==		== Последовательная сложность алгоритма ==

	Самыми частыми операциями в алгоритме являются генерация случайного числа, вычисление синуса, декодирование вещественного числа, обращение к памяти и ~~перезапись нового~~ числа. Посчитаем количество данных операций при последовательной реализации алгоритма. <br>		Самыми частыми операциями в алгоритме являются генерация случайного числа, вычисление синуса, декодирование вещественного числа, обращение к памяти и запись числа в память. Посчитаем количество данных операций при последовательной реализации алгоритма. <br>
	Обозначения: <math>P</math> - число особей в поколении, <math>DIM</math> - размерность функции приспособленности <math>F(x)</math>, <math>G</math> - количество поколений эволюции		Обозначения: <math>P</math> - число особей в поколении, <math>DIM</math> - размерность функции приспособленности <math>F(x)</math>, <math>G</math> - количество поколений эволюции (итераций).
	<math></math> <br>		<math></math> <br>

	1. Генерация случайного числа. Для генерации первого поколения необходимо <math>P\cdot DIM</math> операций. Для скрещиваний в каждом поколении нужно <math>P\cdot DIM</math> генераций случайных чисел. Для мутаций в каждом поколении минимум <math>P\cdot DIM</math> генераций, максимум <math>2\cdot P \cdot DIM</math>. Итого по всем поколениям: <math>P + P \cdot DIM \cdot G + 2 \cdot P \cdot DIM \cdot G = O(PG)</math> операций генерации случайных чисел.		1. Генерация случайного числа. Для генерации первого поколения необходимо <math>P\cdot DIM</math> операций. Для скрещиваний в каждом поколении нужно <math>P\cdot DIM</math> генераций случайных чисел. Для мутаций в каждом поколении минимум <math>P\cdot DIM</math> генераций, максимум <math>2\cdot P \cdot DIM</math>. Итого по всем поколениям: <math>P + P \cdot DIM \cdot G + 2 \cdot P \cdot DIM \cdot G = O(PG)</math> операций генерации случайных чисел. Генерация случайного числа программно равна <math>3</math> операциям умножения, что не меняет ранее найденный порядок сложности.

	2. Вычисление синуса ~~от числа~~. На ~~первой~~ популяции нужно вычислить ......		2. Вычисление синуса. На каждой популяции нужно вычислить <math>P \cdot DIM </math>. Итого <math>G \cdot P \cdot DIM = O(PG)</math> операций. <br>

			3. Декодирование. Количество операций декодирования равно количеству вычисления синуса. По сложности операция декодирования сводится к двум операциям умножения. Итого получим <math>2 \cdot G \cdot P \cdot DIM = O(PG)</math> операций умножения. <br>

			4. Обращение в память. Для работы алгоритма нужно <math>2P \cdot DIM</math> операций на начальной популяции. Так же для реализации скрещивания <math>P\cdot DIM </math> операций, для мутации не более <math>P \cdot DIM</math> обращений в память и для проверки приспособленности <math>P \cdot DIM</math> операций. Итого для всех <math>G</math> популяций <math> 2P \cdot DIM + G \cdot P \cdot DIM + G \cdot P \cdot DIM + G \cdot P \cdot DIM = O(PG)</math> операций обращения в память. <br>

			5. Запись числа в память. Для генерации начальной популяции <math>P\cdot DIM</math> операций, для скрещиваний на каждой итерации <math>P \cdot DIM</math> операций, для мутации не более <math>P \cdot DIM</math> операций. Для записи максимума требуется <math>1 + G</math> операций. Итого <math>O((P+1)G)</math> операций записи нового числа в память.


			Итого получаем сложность порядка <math>O((P+1)G)</math>.

	== Информационный граф ==		== Информационный граф ==

Kilkavteste 607 в 20:36, 15 ноября 2017

2017-11-15T20:36:47Z

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

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

			Самыми частыми операциями в алгоритме являются генерация случайного числа, вычисление синуса, декодирование вещественного числа, обращение к памяти и перезапись нового числа. Посчитаем количество данных операций при последовательной реализации алгоритма. <br>
			Обозначения: <math>P</math> - число особей в поколении, <math>DIM</math> - размерность функции приспособленности <math>F(x)</math>, <math>G</math> - количество поколений эволюции
			<math></math> <br>

			1. Генерация случайного числа. Для генерации первого поколения необходимо <math>P\cdot DIM</math> операций. Для скрещиваний в каждом поколении нужно <math>P\cdot DIM</math> генераций случайных чисел. Для мутаций в каждом поколении минимум <math>P\cdot DIM</math> генераций, максимум <math>2\cdot P \cdot DIM</math>. Итого по всем поколениям: <math>P + P \cdot DIM \cdot G + 2 \cdot P \cdot DIM \cdot G = O(PG)</math> операций генерации случайных чисел.

			2. Вычисление синуса от числа. На первой популяции нужно вычислить ......

	== Информационный граф ==		== Информационный граф ==
	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==