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

Упражнение 1:

---

Номер 1

Эта задача носит название задачи об укладке рюкзака и формулируется следующим образом. Имеется рюкзак объемом  и  различных предметов. Каждый предмет  имеет известный объем  и стоимость . В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем . Форма предметов здесь не учитывается.

Для решения этой задачи разработайте простой ГА, реализуйте его в виде программы на любом известном вам языке, и с помощью этой программы найдите оптимальное решение.
, а данные о предметах приведены в таблице.
№ предм.
1
2
3
4.
5
Объем 
6
4
3
2
5
Объем 
5
3
1
3
6

Ответ:

---

Номер 2

Эта задача носит название задачи об укладке рюкзака и формулируется следующим образом. Имеется рюкзак объемом  и  различных предметов. Каждый предмет  имеет известный объем  и стоимость . В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем . Форма предметов здесь не учитывается.

Для решения этой задачи разработайте простой ГА, реализуйте его в виде программы на любом известном вам языке, и с помощью этой программы найдите оптимальное решение.
, а данные о предметах приведены в таблице.
№ предм.
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

Ответ:

---

Упражнение 2:

---

Номер 1

Эта задача носит название задачи о покрытии множества и формулируется следующим образом. Задано множество элементов  и множество подмножеств  этого множества  Необходимо найти минимальное число подмножеств из  таких, чтобы объединение этих подмножеств содержало все элементы множества .

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

Ответ:

---

Номер 2

Эта задача носит название задачи о покрытии множества и формулируется следующим образом. Задано множество элементов  и множество подмножеств  этого множества  Необходимо найти минимальное число подмножеств из  таких, чтобы объединение этих подмножеств содержало все элементы множества .

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

Ответ:

---

Упражнение 3:

---

Номер 1

Пусть для представления тура при решении задачи коммивояжера (ЗК) с использованием ГА выбрано представление порядка. Пусть заданы число городов в ЗК, базовый упорядоченный список городов  и список ссылок . Пусть также заданы списки  и  двух туров-родителей, в которых вертикальной чертой обозначена точка скрещивания при выполнении одноточечного классического оператора кроссинговера. В списках начальный указатель – первый слева номер в этом списке. Требуется: а) по списку  указать задаваемый им тур; б)по спискам  и , которые задают два тура-родителя, найти их двух потомков  и  в результате выполнения упомянутого оператора кроссинговера.
		

Ответ:

---

Номер 2

Пусть для представления тура при решении задачи коммивояжера (ЗК) с использованием ГА выбрано представление порядка. Пусть заданы число городов в ЗК, базовый упорядоченный список городов  и список ссылок . Пусть также заданы списки  и  двух туров-родителей, в которых вертикальной чертой обозначена точка скрещивания при выполнении одноточечного классического оператора кроссинговера. В списках начальный указатель – первый слева номер в этом списке. Требуется: а) по списку  указать задаваемый им тур; б)по спискам  и , которые задают два тура-родителя, найти их двух потомков  и  в результате выполнения упомянутого оператора кроссинговера.
		

Ответ:

---

Упражнение 4:

---

Номер 1

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

Ответ:

---

Номер 2

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

Ответ:

---

Упражнение 5:

---

Номер 1

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

Ответ:

---

Номер 2

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

Ответ:

---

Упражнение 6:

---

Номер 1

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

Ответ:

---

Номер 2

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

Ответ:

---

Упражнение 7:

---

Номер 1

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

Ответ:

---

Номер 2

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

Ответ:

---

Упражнение 8:

---

Номер 1

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

Ответ:

---

Номер 2

Если задана квадратная матрица  из нулей и единиц размерности ,то при каких условиях она представляет правильный тур?

Ответ:

---

Упражнение 9:

---

Номер 1

Требуется найти оптимальное решение задачи коммивояжера любым из описанных в разделе 2 пособия методом, реализовав этот метод в виде программы на известном вам языке программирования. Исходные данные задачи представлены в виде квадратной матрицы, элементы которой  интерпретируются как время переезда из города  в город . 
1
2
3
4
5
1
*
4
2
-
5
2
*
-
1
9
3
*
3
4
4
*
11
5
*

Ответ:

---

Номер 2

Требуется найти оптимальное решение задачи коммивояжера любым из описанных в разделе 2 пособия методом, реализовав этот метод в виде программы на известном вам языке программирования. Исходные данные задачи представлены в виде квадратной матрицы, элементы которой  интерпретируются как время переезда из города  в город . 
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
*

Ответ:

---