Требуется найти оптимальное решение задачи коммивояжера любым из описанных в...

Требуется найти оптимальное решение задачи коммивояжера любым из описанных в разделе 2 пособия методом, реализовав этот метод в виде программы на известном вам языке программирования. Исходные данные задачи представлены в виде квадратной матрицы, элементы которой $m_{ij}$ интерпретируются как время переезда из города в город .

	1	2	3	4	5	6	7
1	*	4	-	5	3	1	1
2		*	6	2	-	3	-
3			*		3	-	2
4				*	1	5	6
5					*	-	-
6						*	6
7							*

Эта задача носит название задачи об укладке рюкзака и формулируется следующим образом. Имеется рюкзак объемом и различных предметов. Каждый предмет имеет известный объем W_i и стоимость $P_i(i=1,\dots,n)$ . В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем . Форма предметов здесь не учитывается.

Для решения этой задачи разработайте простой ГА, реализуйте его в виде программы на любом известном вам языке, и с помощью этой программы найдите оптимальное решение.

C=15 , а данные о предметах приведены в таблице.

№ предм.	1	2	3	4.	5
Объем	6	4	3	2	5
Объем	5	3	1	3	6

Эта задача носит название задачи об укладке рюкзака и формулируется следующим образом. Имеется рюкзак объемом и различных предметов. Каждый предмет имеет известный объем W_i и стоимость $P_i(i=1,\dots,n)$ . В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем . Форма предметов здесь не учитывается.

Для решения этой задачи разработайте простой ГА, реализуйте его в виде программы на любом известном вам языке, и с помощью этой программы найдите оптимальное решение.

C=60 , а данные о предметах приведены в таблице.

№ предм.	1	2	3	4	5	6	7	8	9	10
Объем	3	14	25	26	32	2	28	23	1	9
Объем	11	12	5	30	31	25	19	27	32	33

Эта задача носит название задачи о покрытии множества и формулируется следующим образом. Задано множество элементов $S=\{x_1,x_2,\dots,x_n\}$ и множество подмножеств $\tilde{S}=\{S_1,\dots,S_k\}$ этого множества Необходимо найти минимальное число подмножеств из $\tilde{S}$ таких, чтобы объединение этих подмножеств содержало все элементы множества .

Для решения этой задачи разработайте простой ГА, реализуйте его в виде программы на любом известном вам языке, и с помощью этой программы найдите оптимальное решение.

$S=\{x_1,x_2,\dots,x_{12}\}, \tilde{S}={S_1,S_2,\dots,S_6\},$ , где $S_3=\{x_1,x_4,x_7,x_{10}\}, S_2=\{x_5,x_6,x_8,x_9\}, S_1=\{x_1,x_2,\dots,x_6\}, S_4=\{x_2,x_5,x_7,x_8,x_{11}\}, S_5=\{x_3,x_6,x_9,x_{12}\},S_6=\{x_{10},x_{11}\},$

Эта задача носит название задачи о покрытии множества и формулируется следующим образом. Задано множество элементов $S=\{x_1,x_2,\dots,x_n\}$ и множество подмножеств $\tilde{S}=\{S_1,\dots,S_k\}$ этого множества Необходимо найти минимальное число подмножеств из $\tilde{S}$ таких, чтобы объединение этих подмножеств содержало все элементы множества .

Для решения этой задачи разработайте простой ГА, реализуйте его в виде программы на любом известном вам языке, и с помощью этой программы найдите оптимальное решение.

$S=\{x_1,x_2,\dots,x_{15}\},\tilde{S}=\{S_1,S_2,\dots,S_5\}$ , где $S_1=\{x_2,x_4,x_6,x_8\}, S_2=\{x_1,x_2,\dots,x_5\},S_3=\{x_7,x_9,x_{10},\dots,x_{15}\}, S_4=\{x_7,x_9,x_{10}\},S_5=\{x_6,x_7,x_8\}$

Пусть для представления тура при решении задачи коммивояжера с использованием ГА выбрано представление в виде матрицы смежности. Пусть заданы два тура T_1 и T_2 с помощью матриц смежности. Требуется выполнить над турами оператор двухточечного кроссинговера, используя эти матрицы, и представить полученных потомков в виде упорядоченных списков.

Пусть T_1= 1-5-4-2-3-1 и T_2=1-4-3-5-2-1 .Точками скрещивания в операторе кроссинговера являются 2 и 3.

Пусть для представления тура при решении задачи коммивояжера с использованием ГА выбрано представление в виде матрицы смежности. Пусть заданы два тура T_1 и T_2 с помощью матриц смежности. Требуется выполнить над турами оператор двухточечного кроссинговера, используя эти матрицы, и представить полученных потомков в виде упорядоченных списков.

Пусть T_1= 1-5-7-3-6-2-4-1 и T_2=1-7-4-2-5-3-6-1 .Точками скрещивания в операторе кроссинговера являются 2 и 5.

Примечание. Для объединения получающихся после кроссинговера двух подтуров в потомках достаточно замены двух ребер.

Пусть для представления тура при решении задачи коммивояжера (ЗК) с использованием ГА выбрано представление порядка. Пусть заданы число городов в ЗК, базовый упорядоченный список городов $L=(1,2,\dots,n-1,n)$ и список ссылок $e=(k_1,k_2,\dots,k_n)$ . Пусть также заданы списки e_1 и e_2 двух туров-родителей, в которых вертикальной чертой обозначена точка скрещивания при выполнении одноточечного классического оператора кроссинговера. В списках начальный указатель – первый слева номер в этом списке. Требуется: а) по списку указать задаваемый им тур; б)по спискам e_1 и e_2 , которые задают два тура-родителя, найти их двух потомков O_1 и O_2 в результате выполнения упомянутого оператора кроссинговера.

n=10;L=(1,2,3,4,5,6,7,8,9,10);e=(9,8,7,4,3,2,3,2,1,1);e_1=(3,6,3,5,|4,2,2,3,1,1);e_2=(7,8,6,4|,3,2,3,2,1,1).

Пусть для представления тура при решении задачи коммивояжера (ЗК) с использованием ГА выбрано представление порядка. Пусть заданы число городов в ЗК, базовый упорядоченный список городов $L=(1,2,\dots,n-1,n)$ и список ссылок $e=(k_1,k_2,\dots,k_n)$ . Пусть также заданы списки e_1 и e_2 двух туров-родителей, в которых вертикальной чертой обозначена точка скрещивания при выполнении одноточечного классического оператора кроссинговера. В списках начальный указатель – первый слева номер в этом списке. Требуется: а) по списку указать задаваемый им тур; б)по спискам e_1 и e_2 , которые задают два тура-родителя, найти их двух потомков O_1 и O_2 в результате выполнения упомянутого оператора кроссинговера.

n=7;L=(1,2,3,4,5,6,7);e=(5,3,5,4,3,2,1);e_1=(6,5|,4,3,2,1,1);e_2=(5,4|,2,1,3,1,1).

Решается задача поиска экстремума функции вещественной переменной y=f(x)

на отрезке [a,b]

cточностью до знаков после запятой с использованием ГА. Требуется найти диапазон представления решения задачи (особи-хромосомы)в виде двоичного числа. Отрезок [a,b]=[10,20],k=3

.

Эволюционные вычисления