ЛР2_Алексеева_Отчет

Министерство науки и высшего образования РФ

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Уфимский государственный авиационный технический университет»

Факультет информатики и робототехники

Кафедра вычислительной математики и кибернетики

Отчет по лабораторной работе №2

на тему «Решение NP-трудных задач комбинаторной оптимизации»

по дисциплине

«Компьютерное моделирование»

Выполнила: студентка группы ПРО-323

Алексеева А. В.

Проверила: к.т.н., доцент каф. ВМиК

Валеева А. Ф.

Уфа 2022

Задание на лабораторную работу:

1. Решить задачу одномерной упаковки или раскроя в условиях единичного производства и описать алгоритм для ее решения.

2. Провести численные эксперименты на тестовых примерах из международной библиотеки OR-library.

Математическая модель

Пусть искомое число контейнеров (стержней) .

= 1, если предмет есть в контейнере

0, иначе

Найти

при условиях

, для всех 1  j  m.

Искомую матрицу можно преобразовать в приоритетный список L^*, который принять за решение задачи:

приоритетный список из номеров предметов: L^* = {i₁, i₂,…, i_n}.

Ход работы:

Эксперимент проводился на тестовых примерах из международной библиотеки OR-library. В качестве тестового набора был выбран файл binpack2.txt, содержащий 20 тестовых примеров. Каждый тестовый пример содержит следующую информацию:

• Название тестового примера;

• Вместимость одного контейнера;

• Количество предметов;

• Количество контейнеров в лучшем известном решении;

• Список размеров предметов

Генетический алгоритм (Алексеева А. В.)

Решение задачи – приоритетный список из номеров предметов:

Алгоритм:

1. Выбор начальной популяции, запись рекорда (минимальное количество контейнеров).

• Начальная популяция генерируется случайным образом. Номера предметов размешиваются в случайном порядке. Популяция состоит из 10 приоритетных списков. Каждый список содержит в себе индексы предметов

2. Выполнять следующие шаги до тех пор, пока k < 100000:

   1. Первый родитель выбирается как лучший среди всей популяции;

   2. Второй родитель выбирается случайным образом;

   3. Новое решение получаем путем скрещивания обоих родителей:

• Пусть S₁, S₂ – два решения, задаваемые приоритетными списками L¹, L²;

• Случайным образом выбираем количество предметов l из диапазона [0, n-1]

• Новое решение (приоритетный список) L получает первые l предметов от L¹;

• К концу L присоединяется вектор L²;

• Из L удаляются все повторяющиеся значения.

4. Выполняем мутацию над полученным решением:

Для каждого i предмета из S:

• Получаем случайное число q;

• Если q < , где n – количество предметов, то:

• Находим новый предмет j из решения, отличающийся номером от i;

• Меняем i и j местами.

5. Добавляем в популяцию новое решение;

6. Удаляем из популяции наихудшее решение.

Пример работы:

Общий тестовый пример был выбран из задания:

Дано: W=5, m=7, w = (2, 1, 3, 4, 3, 2, 1).

Пример работы:

Начальная популяция:

Рекорд в популяции: min = 5, index = 0

Первый родитель (наилучший):

Второй родитель (случайный):

Оператор скрещивания:

l =3;

Оператор мутации:

• Для i =3:

• Получить случайное число q = 0.1528

• Найти новый предмет j = 5 из решения;

• Поменять i и j местами

• Для i=4:

• Получить случайное число q = 0.1528

• Найти новый предмет j=6 из решения;

• Поменять i и j местами

, q< 1/n

Добавление нового решения и удаление наихудшего:

Результаты численного эксперимента на тестовых примерах:

Номер тестового набора	ГА	Лучший результат
1	111	99
2	112	100
3	114	102
4	111	100
5	113	101
6	113	101
7	113	102
8	116	104
9	118	105
10	112	101
11	116	105
12	113	101
13	117	106
14	115	103
15	112	100
16	118	105
17	109	97
18	110	100
19	112	100
20	113	102