База ответов ИНТУИТ

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

<<- Назад к вопросам

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

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

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

№ предм.12345678910
Объем W_i3142526322282319
Объем P_i1112530312519273233

(Отметьте один правильный вариант ответа.)

Варианты ответа
В рюкзак укладываются предметы с номерами 1,6,8,9,10.
В рюкзак укладываются предметы с номерами 1,2,4,6,8,10.
В рюкзак укладываются предметы с номерами 1,2,6,7,10.
В рюкзак укладываются предметы с номерами 1,2,4,6,9,10.(Верный ответ)
Похожие вопросы

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

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

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

№ предм.1234.5
Объем W_i64325
Объем P_i53136

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

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

12345
1*42-5
2*-19
3*34
4*11
5*

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

1234567
1*4-5311
2*62-3-
3*3-2
4*156
5*--
6*6
7*
Пусть имеется популяция, содержащая 12 особей a_1,\dots,a_{12}, для которых известны значения фитнесс-функции : f(a_i):f(a_1)=10,92;f(a_2)=11,05;f(a_3)=8,07;f(a_4)=12,05;f(a_5)=6,22;f(a_6)=14,11;f(a_7)=2,35;f(a_8)=5,2;f(a_9)=1,12;f(a_{10})=6,34;f(a_{11})=15,27;f(a_{12})=34,7. Требуется произвести детерминированный турнирный отбор родителей в этой популяции за m туров.

m=3, случайным образом получено 4 тура: (4,5,7), (6,8,9), (10,12,1), (3,2,11).

Пусть имеется популяция, содержащая 12 особей a_1,\dots,a_{12}, для которых известны значения фитнесс-функции : f(a_i):f(a_1)=10,92;f(a_2)=11,05;f(a_3)=8,07;f(a_4)=12,05;f(a_5)=6,22;f(a_6)=14,11;f(a_7)=2,35;f(a_8)=5,2;f(a_9)=1,12;f(a_{10})=6,34;f(a_{11})=15,27;f(a_{12})=34,7. Требуется произвести детерминированный турнирный отбор родителей в этой популяции за m туров.

m=4, случайным образом получено 4 тура: (4,5,7,6), (11,8,9,1), (10,12,2,3).

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

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

Пусть имеется популяция, содержащая 12 особей a_1,\dots,a_{12}, для которых известны значения фитнесс-функции : f(a_i):f(a_1)=10,92;f(a_2)=11,05;f(a_3)=8,07;f(a_4)=12,05;f(a_5)=6,22;f(a_6)=14,11;f(a_7)=2,35;f(a_8)=5,2;f(a_9)=1,12;f(a_{10})=6,34;f(a_{11})=15,27;f(a_{12})=34,7. Требуется произвести детерминированный турнирный отбор родителей в этой популяции за m туров.

m=2, случайным образом получено 6 туров: (5,7), (6,8), (12,1), (3,2),(4,11),(9,10).