Участник:AlexeyP - История изменений

AlexeyP: /* Вычисление минимума по числу уникальных площадок среди всех игроков */

2024-12-11T20:39:48Z

Вычисление минимума по числу уникальных площадок среди всех игроков

← Предыдущая версия		Версия от 20:39, 11 декабря 2024
Строка 72:		Строка 72:

	Мы проходим по всем игрокам, для каждого игрока по всем турам и считаем число уникальных. Итого получаем, что сложность - <math>O(T * P)</math>, где T - число туров, P - число игроков		Мы проходим по всем игрокам, для каждого игрока по всем турам и считаем число уникальных. Итого получаем, что сложность - <math>O(T * P)</math>, где T - число туров, P - число игроков


	Итого для получения приспособленности всех существ нам нужно <math>O(S * T * P^2)</math>, где S - размер популяции, T - число туров, P - число игроков		Итого для получения приспособленности всех существ нам нужно <math>O(S * T * P^2)</math>, где S - размер популяции, T - число туров, P - число игроков

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

2024-12-11T20:37:55Z

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

← Предыдущая версия		Версия от 20:37, 11 декабря 2024
Строка 151:		Строка 151:
	* Каждый тур может инициализироваться независимо от других		* Каждый тур может инициализироваться независимо от других
	* Каждый тур необходимо заполнять парами номеров площадок, которые необходимо предварительно сгенерировать		* Каждый тур необходимо заполнять парами номеров площадок, которые необходимо предварительно сгенерировать

			Следовательно ресурс параллелизма <math>O(S * T)</math>, где <math>S</math> — размер популяции, <math>T</math> — число туров

	==== Вычисление приспособленности существ (fitness) ====		==== Вычисление приспособленности существ (fitness) ====
Строка 158:		Строка 160:

	Необходимо найти минимальное значение из полученных метрик игроков		Необходимо найти минимальное значение из полученных метрик игроков

			Следовательно ресурс параллелизма <math>O(S * P)</math>, где <math>S</math> — размер популяции, <math>P</math> — число игроков

	==== Отбор лучших существ (selection) ====		==== Отбор лучших существ (selection) ====
Строка 165:		Строка 169:
	В рамках турнира необходимы последовательные сравнения		В рамках турнира необходимы последовательные сравнения

	~~После отбора необходимо обновить популяцию с учётом отобранных существ~~		Следовательно ресурс параллелизма <math>O(S)</math>, где <math>S</math> — размер популяции

	==== Скрещивание существ (crossover) ====		==== Скрещивание существ (crossover) ====
Строка 176:		Строка 180:
	* Каждое существо может мутировать независимо,		* Каждое существо может мутировать независимо,
	* В каждом туре мутации могут проходить независимо		* В каждом туре мутации могут проходить независимо

			Следовательно ресурс параллелизма <math>O(S * T)</math>, где <math>S</math> — размер популяции, <math>T</math> — число туров

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

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

2024-12-11T20:22:16Z

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

← Предыдущая версия		Версия от 20:22, 11 декабря 2024
Строка 121:		Строка 121:

	Создаётся массив номеров площадок. Для каждого тура каждого существа случайно распределяются номера площадок из списка так, чтобы в одном туре номер площадки встречался дважды		Создаётся массив номеров площадок. Для каждого тура каждого существа случайно распределяются номера площадок из списка так, чтобы в одном туре номер площадки встречался дважды

	~~[[Файл:Init.jpg\|обрамить\|центр]]~~

	==== Вычисление приспособленности существ (fitness) ====		==== Вычисление приспособленности существ (fitness) ====

	Используя текущую популяцию создаётся таблица приспособленности для каждого вида		Используя текущую популяцию создаётся таблица приспособленности для каждого вида

	~~[[Файл:Fitness.jpg\|обрамить\|центр]]~~

	==== Отбор лучших существ (selection) ====		==== Отбор лучших существ (selection) ====

	Существа отбираются в турнир случайным образом из текущей популяции. Используя таблицу приспособленности существа отбираются в следующую популяцию		Существа отбираются в турнир случайным образом из текущей популяции. Используя таблицу приспособленности существа отбираются в следующую популяцию

	~~[[Файл:Selection.jpg\|обрамить\|центр]]~~

	==== Скрещивание существ (crossover) ====		==== Скрещивание существ (crossover) ====

	Из текущей популяции отбираются существа, у них обмениваются гены, новые существа заменяют предыдущие в популяции		Из текущей популяции отбираются существа, у них обмениваются гены, новые существа заменяют предыдущие в популяции

	~~[[Файл:Crossover.jpg\|обрамить\|центр]]~~

	==== Мутации существ (mutation) ====		==== Мутации существ (mutation) ====
Строка 146:		Строка 138:
	В каждом существе текущей популяции происходит обмен генов. Новое существо заменяет предыдущее в популяции		В каждом существе текущей популяции происходит обмен генов. Новое существо заменяет предыдущее в популяции

	[[Файл:~~Mutation~~.jpg\|обрамить\|центр]]		[[Файл:GeneticInformationGraph.jpg\|обрамить\|центр]]

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

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

2024-12-11T19:14:59Z

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

← Предыдущая версия		Версия от 19:14, 11 декабря 2024
Строка 102:		Строка 102:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

	1. Начальная инициализация популяции - <math>O(S * T * P)</math>, <math>S</math> — размер популяции, ~~где~~ <math>T</math> — число туров, <math>P</math> — число игроков		1. Начальная инициализация популяции - <math>O(S * T * P)</math>, где <math>S</math> — размер популяции, <math>T</math> — число туров, <math>P</math> — число игроков

	2. Циклически рассчитываем заданное число поколений - <math>O(G * S * (T * P^2 + N))</math>, G - число поколений, S - размер популяции, ~~где~~ T - число туров, P - число игроков, где N - число существ участвующих в турнире отбора		2. Циклически рассчитываем заданное число поколений - <math>O(G * S * (T * P^2 + N))</math>, где G - число поколений, S - размер популяции, T - число туров, P - число игроков, где N - число существ участвующих в турнире отбора

	2.1 Подсчёт приспособленности существ - <math>O(S * T * P^2)</math>, S - размер популяции, ~~где~~ T - число туров, P - число игроков		2.1 Подсчёт приспособленности существ - <math>O(S * T * P^2)</math>, где S - размер популяции, T - число туров, P - число игроков

	2.2 Отбор существ - <math>O(S * N)</math>, S - размер популяции, ~~где~~ N - число существ участвующих в турнире отбора		2.2 Отбор существ - <math>O(S * N)</math>, где S - размер популяции, N - число существ участвующих в турнире отбора

	2.3 Скрещивание существ - <math>O(S * T * P)</math>, S - размер популяции, ~~где~~ T - число туров, P - число игроков		2.3 Скрещивание существ - <math>O(S * T * P)</math>, где S - размер популяции, T - число туров, P - число игроков

	2.4. Мутации получившихся существ - <math>O(S * T * P)</math>, S - размер популяции, ~~где~~ T - число туров, P - число игроков		2.4. Мутации получившихся существ - <math>O(S * T * P)</math>, где S - размер популяции, T - число туров, P - число игроков

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

AlexeyP: /* Вычисление минимума по числу уникальных площадок среди всех игроков */

2024-12-11T19:14:12Z

Вычисление минимума по числу уникальных площадок среди всех игроков

← Предыдущая версия		Версия от 19:14, 11 декабря 2024
Строка 74:		Строка 74:


	Итого для получения приспособленности всех существ нам нужно <math>O(S * T * P^2)</math>, S - размер популяции, ~~где~~ T - число туров, P - число игроков		Итого для получения приспособленности всех существ нам нужно <math>O(S * T * P^2)</math>, где S - размер популяции, T - число туров, P - число игроков

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===

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

2024-12-11T19:13:09Z

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

← Предыдущая версия		Версия от 19:13, 11 декабря 2024
Строка 189:		Строка 189:
	==== Входные данные ====		==== Входные данные ====

	* Размер популяции		Все значения - обычные числа
	* Максимальное число поколений

	* ~~Число существ в турнире отбора~~		* Размер популяции (S)
	* ~~Вероятность скрещивания существ~~		* Максимальное число поколений (G)
	* Вероятность мутации гена существа

	* Число туров		* Число существ в турнире отбора (N)
	* Число игроков		* Вероятность скрещивания существ (C)
	* Число площадок		* Вероятность мутации гена существа (M)

			* Число туров (T)
			* Число игроков (P)
			* Число площадок (Pg)

	==== Выходные данные ====		==== Выходные данные ====

	* ~~Популяции~~ существ		* Популяция существ — трёхмерный массив размерами <math>S * T * P</math>, где <math>S</math> — размер популяции, <math>T</math> — число туров, <math>P</math> — число игроков
	* Метрики существ
	* Лучшая получившаяся таблица турнира		* Метрики существ — двумерный массив размерами <math>S * 2</math>, где <math>S</math> — размер популяции, 2, т.к. приспособленность вычисляется из пары значений минимального числа оппонетов и минимального числа площадок для любого участника турнира
			* Лучшее существо в популяции (Лучшая получившаяся таблица турнира) — двумерный массив размерами <math>T * P</math>, где <math>T</math> — число туров, <math>P</math> — число игроков

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==

AlexeyP: /* Вычислительное ядро алгоритма */

2024-12-11T18:59:32Z

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

← Предыдущая версия		Версия от 18:59, 11 декабря 2024
Строка 61:		Строка 61:
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

	~~Вычислительное ядро~~ состоит из ключевых блоков ~~генетического алгоритма~~		Генетический алгоритм состоит из несколько ключевых блоков, но самое большое время занимает подсчёт приспособленности существ

	~~==== Вычисление~~ приспособленности существ ~~(fitness) ====~~

	Для вычисление приспособленности существ мы проходим по всех существа в популяции и считаем приспособленность каждого из них		Для вычисление приспособленности существ мы проходим по всех существа в популяции и считаем приспособленность каждого из них

	~~Вычисление приспособленности существа состоит из 2 этапов:~~		==== Вычисление минимума по числу уникальных оппонентов среди всех игроков ====

	===== Вычисление минимума по числу уникальных оппонентов среди всех игроков =====

	Мы проходим по всем игрокам, для каждого игрока по всем турам, для каждого тура по всем противникам данного игрока и считаем число уникальных. Итого получаем, что сложность - <math>O(T * P^2)</math>, где T - число туров, P - число игроков		Мы проходим по всем игрокам, для каждого игрока по всем турам, для каждого тура по всем противникам данного игрока и считаем число уникальных. Итого получаем, что сложность - <math>O(T * P^2)</math>, где T - число туров, P - число игроков

	===== Вычисление минимума по числу уникальных площадок среди всех игроков =====		==== Вычисление минимума по числу уникальных площадок среди всех игроков ====

	Мы проходим по всем игрокам, для каждого игрока по всем турам и считаем число уникальных. Итого получаем, что сложность - <math>O(T * P)</math>, где T - число туров, P - число игроков		Мы проходим по всем игрокам, для каждого игрока по всем турам и считаем число уникальных. Итого получаем, что сложность - <math>O(T * P)</math>, где T - число туров, P - число игроков
Строка 79:		Строка 75:

	Итого для получения приспособленности всех существ нам нужно <math>O(S * T * P^2)</math>, S - размер популяции, где T - число туров, P - число игроков		Итого для получения приспособленности всех существ нам нужно <math>O(S * T * P^2)</math>, S - размер популяции, где T - число туров, P - число игроков

	~~==== Отбор лучших существ (selection) ====~~

	~~Существуют несколько вариантов отбора существ<ref>https://qai.narod.ru/GA/strategies.html</ref>~~

	~~Например рассмотрим Турнирный отбор (Tournament selection)<ref>https://en.wikipedia.org/wiki/Tournament_selection</ref>~~

	Для турнирного отбора мы проходимся по всей популяции, берём случайные N существ и среди них выбираем наиболее приспособленного, который перейдёт в следующую популяцию. Итого нам нужно <math>O(S * N)</math>, S - размер популяции, где N - число существ турнира

	~~==== Скрещивание существ (crossover) ====~~

	Мы проходим по всей популяции и скрещиваем существ, меняя часть туров одного из существ с соответствующими турами другого существа. Итого получаем <math>O(S * T * P)</math>, S - размер популяции, где T - число туров, P - число игроков

	~~==== Мутации существ (mutation) ====~~

	Мы проходим по всей популяции, и для каждого существа в каждом туре меняем оппонентов. Итого получаем <math>O(S * T * P)</math>, S - размер популяции, где T - число туров, P - число игроков

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===

AlexeyP в 17:59, 10 декабря 2024

2024-12-10T17:59:13Z

← Предыдущая версия		Версия от 17:59, 10 декабря 2024
Строка 226:		Строка 226:
	* Лучшая получившаяся таблица турнира		* Лучшая получившаяся таблица турнира

	== Выводы для классов архитектур ==		== Программная реализация алгоритма ==

			=== Выводы для классов архитектур ===

	В данном алгоритме можно менять реализации его ключевых этапов (подсчёт приспособленности, отбор, скрещивание, мутации), что позволяет оптимизировать выполнение для конкретных архитектур компьютеров		В данном алгоритме можно менять реализации его ключевых этапов (подсчёт приспособленности, отбор, скрещивание, мутации), что позволяет оптимизировать выполнение для конкретных архитектур компьютеров

AlexeyP: /* Существующие реализации генетического алгоритма для решения задач расписаний */

2024-12-10T17:58:11Z

Существующие реализации генетического алгоритма для решения задач расписаний

← Предыдущая версия		Версия от 17:58, 10 декабря 2024
Строка 230:		Строка 230:
	В данном алгоритме можно менять реализации его ключевых этапов (подсчёт приспособленности, отбор, скрещивание, мутации), что позволяет оптимизировать выполнение для конкретных архитектур компьютеров		В данном алгоритме можно менять реализации его ключевых этапов (подсчёт приспособленности, отбор, скрещивание, мутации), что позволяет оптимизировать выполнение для конкретных архитектур компьютеров

	== Существующие реализации генетического алгоритма для решения задач расписаний ==		=== Существующие реализации генетического алгоритма для решения задач расписаний ===

	Составление расписания спортивных тренировок		Составление расписания спортивных тренировок

AlexeyP: 1.7

2024-12-10T17:57:25Z

1.7

← Предыдущая версия		Версия от 17:57, 10 декабря 2024
Строка 140:		Строка 140:
	==== Инициализации популяции ====		==== Инициализации популяции ====

	~~Все~~ существа		Создаётся массив номеров площадок. Для каждого тура каждого существа случайно распределяются номера площадок из списка так, чтобы в одном туре номер площадки встречался дважды

			[[Файл:Init.jpg\|обрамить\|центр]]

	==== Вычисление приспособленности существ (fitness) ====		==== Вычисление приспособленности существ (fitness) ====

			Используя текущую популяцию создаётся таблица приспособленности для каждого вида

			[[Файл:Fitness.jpg\|обрамить\|центр]]

	==== Отбор лучших существ (selection) ====		==== Отбор лучших существ (selection) ====

			Существа отбираются в турнир случайным образом из текущей популяции. Используя таблицу приспособленности существа отбираются в следующую популяцию

			[[Файл:Selection.jpg\|обрамить\|центр]]

	==== Скрещивание существ (crossover) ====		==== Скрещивание существ (crossover) ====

			Из текущей популяции отбираются существа, у них обмениваются гены, новые существа заменяют предыдущие в популяции

			[[Файл:Crossover.jpg\|обрамить\|центр]]

	==== Мутации существ (mutation) ====		==== Мутации существ (mutation) ====

			В каждом существе текущей популяции происходит обмен генов. Новое существо заменяет предыдущее в популяции

			[[Файл:Mutation.jpg\|обрамить\|центр]]

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