Алгоритмы решения задачи о рюкзаке
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к производственной практике
на тему «Решение задачи о ранце с помощью генетического алгоритма»
Автор проекта (работы) __________________ А.Ю.Кабатов
подпись
Направление/специальность, профиль/специализация:
09.03.04 «Программная инженерия»
Группа ВПР31
Руководитель практики: __________________ доцент О.А. Золотых
Подпись
Проект (работа) защищен(а): _________ _________
дата оценка подпись
Ростов-на-Дону
2016
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГООБРАЗОВАНИЯ
«ДОНСКОЙ ГОСУДАРСВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
(ДГТУ)
Кафедра «Программное обеспечение вычислительной техники
и автоматизированных систем»
Заведующий кафедрой«ПОВТиАС»
_______________ А.Н.Карапетянц
« » 2016г.
ЗАДАНИЕ
на производственную практику
СтудентКабатовАндрейЮрьевич Код 09.03.04 Группа ВПР31
Тема«Решение задачи о ранце с помощью генетического алгоритма»
Срок предоставления отчета к защите «___» _______ 20___г.
Руководитель работы: __________________ О.А. Золотых
подпись,дата
Задание принял к исполнению: __________________ А.Ю. Кабатов
подпись,дата
Ростов-на-Дону
2016
АННОТАЦИЯ
Отчет содержит: листов - 43, рисунков – 12, блок-схем – 2, графиков - 1.
Ключевые слова: ГОЛДБЕРГ, ЗАДАЧА,РАНЕЦ, ГЕНЕТИЧЕСКИЙ АЛГОРИТМ.
Предметом данной работы являются создание программного средства реализующего возможности решения простейшей задачи моделью Голденберга.
Объектом внедрения данной работы является использование базового функционала языков программирования для реализации механизмов решения простейшей задаче о ранце с помощью модифицированной модели Голденберга.
Целью работы - является разработка программного средства, позволяющего обеспечить решение простейшей задаче о ранце с помощью модифицированной модели Голденберга.Рассматривается алгоритмическое конструирование всех компонентов разрабатываемого программного средства.Представлены алгоритмы и программная реализация на языке программирования Сс помощью .NetFramework.
Классическая задача о рюкзаке (о загрузке) известна очень давно, ниже приведена ее формализация. Пусть есть N разных предметов, каждый предмет имеет вес wi и полезность pi , так же имеется максимальный вес W, который можно положить в рюкзак. Требуется собрать такой набор предметов P, чтобы полезность их была наибольшей, а суммарный вес не превышал W.[6]. Конечно, никто не собирается писать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в поход или в путешествие, тут все слишком просто, и никто не задумывается об этом, но существует и более широкое применение.
СОДЕРЖАНИЕ
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
| Разраб. |
| Голубенко Д.Е. |
| Провер. |
| Землянухин В.Н. |
| Н. Контр. |
| Котельникова И.В. |
| Утверд. |
| Карапетянц А.Н. |
| Решение простейшей задачи о ранце с помощью модифицированной модели Голденберга Пояснительная записка |
| Лит. |
| Листов |
| ДГТУ |
ВВЕДЕНИЕ 6
1 Обзор источников по теме “Генетический алгоритм” и “Задача о рюкзаке” 7
1.1 Понятие генетического алгоритма и задачи о ранце 7
1.2 Варианты задачи о ранце 7
1.3 Алгоритмы решения задачи о рюкзаке. 8
1.4 Генетический алгоритм 8
1.5Постановка задач10
2 Алгоритмическое конструирование 11
2.1 Основные принципы работы 11
2.2 Алгоритм работы программы. 12
3 Программное конструирование 14
3.1 Обоснование выбора языка программирования 14
3.2 Описание классов 15
3.3 Описание основных функций 15
3.4 Тестирование программного средства 16
ЗАКЛЮЧЕНИЕ 20
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 21
ПРИЛОЖЕНИЕ А. ТЕХНИЧЕСКОЕ ЗАДАНИЕ НА ПРОГРАММНОЕ 22
ПРИЛОЖЕНИЕ Б. UML - ДИАГРАММА КЛАССОВ 26
ПРИЛОЖЕНИЕ В. ОПИСАНИЕ КЛАССОВ 27
ПРИЛОЖЕНИЕ Г. КОД ПРОГРАММЫ 30
ВВЕДЕНИЕ
Генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. [4] Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. Размножение в генетических алгоритмах обычно половое — чтобы произвести потомка, нужны несколько родителей, обычно два. Размножение в разных алгоритмах определяется по-разному — оно, конечно, зависит от представления данных. Главное требование к размножению — чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Задача о загрузке (задача о рюкзаке) и различные её модификации широко применяются на практике в прикладной математике, криптографии, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д.
Обзор программного средства
1.1
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Генетический алгоритм – это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования, путем случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. [4] Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер.Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Задача о ранце – одна из задач комбинаторной оптимизации. Название свое получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что общий объем всех предметов, способных поместиться в рюкзак, ограничен. [3] Задачи о загрузке (о рюкзаке) и её модификации часто возникают в экономике, прикладной математике, криптографии, генетике и логистике для нахождения оптимальной загрузки транспорта (самолёта, поезда, трюма корабля) или склада. В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
Варианты задачи о ранце
Существует множество разновидностей задачи о ранце, отличия заключаются в условиях, наложенных на рюкзак, предметы или их выбор.
1) Рюкзак 0-1: не более одного экземпляра каждого предмета;
2)
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
3) Неограниченный рюкзак: произвольное количество экземпляров каждого предмета;
4) Рюкзак с мультивыбором;
5) Мультипликативный рюкзак: есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить.
6) Многомерный рюкзак:вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна.
Генетический алгоритм
Генетические алгоритмы были предложены Джоном Генри Холландом в 1970 году и относятся к так называемым метаалгоритмам. Идея — составление алгоритмов поиска на основе биологической модели механизмов естественного отбора. Базовыми понятиями являются: популяция, отбор, мутация, скрещивание.
Популяция. Составляется набор бинарных строк (хромосом), возможных решений. На основе первой («старой») популяции строится вторая («новая») популяция решений, которая служит «старой» для третьей популяции и т.д.
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Скрещивание хромосом. «Родители» обмениваются последними пятью битами и образуют новые хромосомы — «потомки». Скрещивание предоставлено на рисунке 1.
Рисунок 1 –Скрещивание хромосом
Скрещивание. Для пары строк («родителей») с определенной длиной r выбирается произвольное число 
. «Родители» обмениваются между собой битами с s+1-го по r-й и получаются две новые строки («потомки»).
Мутация. Изменение, происходящее с определенной вероятностью.
График времени заполнения рюкзаков с вместимостью 100, 500 и 900 с количеством предметов 50:
Чем больше объем рюкзака, тем больше время его заполнения.
1.5
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Цель данной работы - выделить основные методы решения задачи о загрузке, классифицировать и сравнить эти методы.
Рассматриваемая нами задача является NP - полной, то есть для нее не существует полиномиального алгоритма , решающего её за разумное время, в этом и есть проблема. Либо мы выбираем быстрый алгоритм, но он как известно не всегда решает задачу наилучшим образом, либо выбираем точный, который опять же не является работоспособным для больших значений. Существует несколько модификаций задачи.
1. Каждый предмет можно брать только один раз.
2. Каждый предмет можно брать сколько угодно раз.
3. Каждый предмет можно брать определенное количество раз
4. На размер рюкзака имеется несколько ограничений.
5. Некоторые вещи имею больший приоритет, чем другие.
Подробное описание поставленных задач и необходимых требований к программному средству представлено в ПРИЛОЖЕНИИ А.
2
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Основные принципы работы
Для взаимодействия с пользователем был разработано меню и следующий алгоритм работы программного средства (рис. 2):
1) При запуске пользователю откроется консольное окно, где будет представлено меню, состоящее из 3 пунктов: инициализация, алгоритм, выход.
2) При выборе пункта 1 меню, вам предложено ввести максимальный объем рюкзака.
3) Далее вы вводите количество предметов.
4) Затем вводите размер популяции.
5) После этого вводите шанс кроссинговера и мутации.
6) На экране появляется результат, а именно показаны массы предметов.
7) Далее происходит возврат в меню.
8) При выборе пункта 2 – алгоритм, происходит процесс работы генетического алгоритма и заполнение с его помощью рюкзака. В конце указывается результат.
Реализовать алгоритмы решения классической задачи о рюкзаке. Протестировать их и разбить их на две группы: точные и приближенные, сравнить по скорости решения, по точности. Определить в каких случаях следует использовать тот или иной подход к решению задачи.
Алгоритмы решения можно разделить на два типа: точные и приближенные. Точные: применение динамического программирования, полный перебор, метод ветвей и границ (сокращение полного перебора). Приближенные алгоритмы: Жадный алгоритм.
| Нет |
| Да |
| Меню |
| N=1 |
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Рисунок 2 – Механизм работы программного средства
Описание классов
ClassChromosome – класс который создает хромосому.
ClassBackpack – класс рюкзак, который содержит набор необходимых методов для работы с рюкзаком.
ClassGoldberg – класс, который содержит основные методы генетического алгоритма.
ClassProgram – класс для работы с меню.
Описание основных функций
Для полноценной реализации программного средства был разработан ряд методов, которые выполняют заполнение рюкзака, кроссинговер, мутацию и т.д.
Все эти методы описываются в классеclassGoldberg:
1) voidInit() – метод служит для инициализации кроссинговера и мутации.
2) voidInitBackpack() – метод служит для заполнения рюкзака.
3) voidInitPopulation(intlength) – метод служит для инициализации размера популяции.
4) voidWork() – метод работы алгоритма.
5) voidMutation(Chromosomechild) – метод служит для проведения мутации.
6) void NewPopulation(Chromosome childOne, Chromosome childTwo) – методсозданияновойпопуляции.
7) voidPrintBackpack() – метод вывода на экран масс предметов.
8) voidPrintPopulation() – метод вывода на экран популяции.
9) voidCrossover(intone, inttwo) – метод служит для проведения скрещивания двух особей.
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
А.1 Введение
А.1.2 Область применения
Сфера информатизации.
А.1.3 Объект внедрения
P.S. Будет использовано в рамках учебного процесса
А.3 Назначение разработки
А.4 Требования к программному средству
А.4.1 Требования к функциональным характеристикам
Функции программного средства:
1)Заполнение ранца;
2)проведение скрещивания;
3)проведение мутации.
А.4.2 Требования к надежности
Для обеспечения устойчивого функционирования программы необходимо:
Организация бесперебойного питания компьютера;
Отказы программы возможны вследствие некорректных действий оператора при взаимодействии с исходным кодом продукта.
А.4.3 Условия эксплуатации
Для функционирования программного продукта необходимо соблюдение всех требований и правил эксплуатации компьютерной техники и программного обеспечения. Такими требованиями могут выступать: температура окружающего воздуха, относительная влажность, запыленность.
А.4.4 Требования к составу и параметрам технических средств
Требования к составу аппаратных средств мобильного устройства:
1)процессор с тактовой частотой не менее 500 МГц;
2) объем памяти не менее 512 Мб;
3) видеокарта объемом не менее 256 Мб;
4) свободного пространства на жёстком диске не менее 20мб;
5) операционной системой семейства Windows.
Требования к информационной и программной совместимости
Требования к информационным структурам и методам решения
Информационная структура серверной части должна постоянно хранить и предоставлять краткую статистическую информацию об активности в объектах системы.
Требования к исходным кодам и языкам программирования
Работа с системой не требует знания языков программирования и специальных знаний.
А.4.6 Требования к маркировке и упаковке
Требования к маркировке и упаковке не предъявлены.
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Требования к транспортированию и хранению не предъявлены.
А.4.8 Специальные требования
Специальные требования не предъявлены.
А.5 Требования к программной документации
Программная документация должна состоять из следующих разделов:
- техническое задание;
- исходный текст программного средства;
А.7 Стадии разработки
1) Этапы разработки программного средства:
2) изучение тематики и методов решения (с 5.05 по 24.05)
3) разработка алгоритмов (с 7 .05 по 20.05);
4) реализация разработанных алгоритмов (с1.05 по 18.05);
5) тестирование программы (с 6.05 по 14.05);
6) составление программной документации (с 8.05 по 19.05).
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к производственной практике
на тему «Решение задачи о ранце с помощью генетического алгоритма»
Автор проекта (работы) __________________ А.Ю.Кабатов
подпись
Направление/специальность, профиль/специализация:
09.03.04 «Программная инженерия»
Группа ВПР31
Руководитель практики: __________________ доцент О.А. Золотых
Подпись
Проект (работа) защищен(а): _________ _________
дата оценка подпись
Ростов-на-Дону
2016
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГООБРАЗОВАНИЯ
«ДОНСКОЙ ГОСУДАРСВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
(ДГТУ)
Кафедра «Программное обеспечение вычислительной техники
и автоматизированных систем»
Заведующий кафедрой«ПОВТиАС»
_______________ А.Н.Карапетянц
« » 2016г.
ЗАДАНИЕ
на производственную практику
СтудентКабатовАндрейЮрьевич Код 09.03.04 Группа ВПР31
Тема«Решение задачи о ранце с помощью генетического алгоритма»
Срок предоставления отчета к защите «___» _______ 20___г.
Руководитель работы: __________________ О.А. Золотых
подпись,дата
Задание принял к исполнению: __________________ А.Ю. Кабатов
подпись,дата
Ростов-на-Дону
2016
АННОТАЦИЯ
Отчет содержит: листов - 43, рисунков – 12, блок-схем – 2, графиков - 1.
Ключевые слова: ГОЛДБЕРГ, ЗАДАЧА,РАНЕЦ, ГЕНЕТИЧЕСКИЙ АЛГОРИТМ.
Предметом данной работы являются создание программного средства реализующего возможности решения простейшей задачи моделью Голденберга.
Объектом внедрения данной работы является использование базового функционала языков программирования для реализации механизмов решения простейшей задаче о ранце с помощью модифицированной модели Голденберга.
Целью работы - является разработка программного средства, позволяющего обеспечить решение простейшей задаче о ранце с помощью модифицированной модели Голденберга.Рассматривается алгоритмическое конструирование всех компонентов разрабатываемого программного средства.Представлены алгоритмы и программная реализация на языке программирования Сс помощью .NetFramework.
Классическая задача о рюкзаке (о загрузке) известна очень давно, ниже приведена ее формализация. Пусть есть N разных предметов, каждый предмет имеет вес wi и полезность pi , так же имеется максимальный вес W, который можно положить в рюкзак. Требуется собрать такой набор предметов P, чтобы полезность их была наибольшей, а суммарный вес не превышал W.[6]. Конечно, никто не собирается писать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в поход или в путешествие, тут все слишком просто, и никто не задумывается об этом, но существует и более широкое применение.
СОДЕРЖАНИЕ
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
| Разраб. |
| Голубенко Д.Е. |
| Провер. |
| Землянухин В.Н. |
| Н. Контр. |
| Котельникова И.В. |
| Утверд. |
| Карапетянц А.Н. |
| Решение простейшей задачи о ранце с помощью модифицированной модели Голденберга Пояснительная записка |
| Лит. |
| Листов |
| ДГТУ |
ВВЕДЕНИЕ 6
1 Обзор источников по теме “Генетический алгоритм” и “Задача о рюкзаке” 7
1.1 Понятие генетического алгоритма и задачи о ранце 7
1.2 Варианты задачи о ранце 7
1.3 Алгоритмы решения задачи о рюкзаке. 8
1.4 Генетический алгоритм 8
1.5Постановка задач10
2 Алгоритмическое конструирование 11
2.1 Основные принципы работы 11
2.2 Алгоритм работы программы. 12
3 Программное конструирование 14
3.1 Обоснование выбора языка программирования 14
3.2 Описание классов 15
3.3 Описание основных функций 15
3.4 Тестирование программного средства 16
ЗАКЛЮЧЕНИЕ 20
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 21
ПРИЛОЖЕНИЕ А. ТЕХНИЧЕСКОЕ ЗАДАНИЕ НА ПРОГРАММНОЕ 22
ПРИЛОЖЕНИЕ Б. UML - ДИАГРАММА КЛАССОВ 26
ПРИЛОЖЕНИЕ В. ОПИСАНИЕ КЛАССОВ 27
ПРИЛОЖЕНИЕ Г. КОД ПРОГРАММЫ 30
ВВЕДЕНИЕ
Генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. [4] Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. Размножение в генетических алгоритмах обычно половое — чтобы произвести потомка, нужны несколько родителей, обычно два. Размножение в разных алгоритмах определяется по-разному — оно, конечно, зависит от представления данных. Главное требование к размножению — чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Задача о загрузке (задача о рюкзаке) и различные её модификации широко применяются на практике в прикладной математике, криптографии, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д.
Обзор программного средства
1.1
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Генетический алгоритм – это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования, путем случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. [4] Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер.Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Задача о ранце – одна из задач комбинаторной оптимизации. Название свое получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что общий объем всех предметов, способных поместиться в рюкзак, ограничен. [3] Задачи о загрузке (о рюкзаке) и её модификации часто возникают в экономике, прикладной математике, криптографии, генетике и логистике для нахождения оптимальной загрузки транспорта (самолёта, поезда, трюма корабля) или склада. В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
Варианты задачи о ранце
Существует множество разновидностей задачи о ранце, отличия заключаются в условиях, наложенных на рюкзак, предметы или их выбор.
1) Рюкзак 0-1: не более одного экземпляра каждого предмета;
2)
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
3) Неограниченный рюкзак: произвольное количество экземпляров каждого предмета;
4) Рюкзак с мультивыбором;
5) Мультипликативный рюкзак: есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить.
6) Многомерный рюкзак:вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна.
Алгоритмы решения задачи о рюкзаке
1) К точным алгоритмам относят:
1)Полный перебор;
2) Метод ветвей и границ;
2) К приближенным алгоритмам относят жадный алгоритм;
3) К метаалгоритмам относят генетический алгоритм.
Генетический алгоритм
Генетические алгоритмы были предложены Джоном Генри Холландом в 1970 году и относятся к так называемым метаалгоритмам. Идея — составление алгоритмов поиска на основе биологической модели механизмов естественного отбора. Базовыми понятиями являются: популяция, отбор, мутация, скрещивание.
Популяция. Составляется набор бинарных строк (хромосом), возможных решений. На основе первой («старой») популяции строится вторая («новая») популяция решений, которая служит «старой» для третьей популяции и т.д.
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Скрещивание хромосом. «Родители» обмениваются последними пятью битами и образуют новые хромосомы — «потомки». Скрещивание предоставлено на рисунке 1.
Рисунок 1 –Скрещивание хромосом
Скрещивание. Для пары строк («родителей») с определенной длиной r выбирается произвольное число . «Родители» обмениваются между собой битами с s+1-го по r-й и получаются две новые строки («потомки»).
Мутация. Изменение, происходящее с определенной вероятностью.
График времени заполнения рюкзаков с вместимостью 100, 500 и 900 с количеством предметов 50:
Чем больше объем рюкзака, тем больше время его заполнения.
1.5
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Цель данной работы - выделить основные методы решения задачи о загрузке, классифицировать и сравнить эти методы.
Рассматриваемая нами задача является NP - полной, то есть для нее не существует полиномиального алгоритма , решающего её за разумное время, в этом и есть проблема. Либо мы выбираем быстрый алгоритм, но он как известно не всегда решает задачу наилучшим образом, либо выбираем точный, который опять же не является работоспособным для больших значений. Существует несколько модификаций задачи.
1. Каждый предмет можно брать только один раз.
2. Каждый предмет можно брать сколько угодно раз.
3. Каждый предмет можно брать определенное количество раз
4. На размер рюкзака имеется несколько ограничений.
5. Некоторые вещи имею больший приоритет, чем другие.
Подробное описание поставленных задач и необходимых требований к программному средству представлено в ПРИЛОЖЕНИИ А.
2
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Основные принципы работы
Для взаимодействия с пользователем был разработано меню и следующий алгоритм работы программного средства (рис. 2):
1) При запуске пользователю откроется консольное окно, где будет представлено меню, состоящее из 3 пунктов: инициализация, алгоритм, выход.
2) При выборе пункта 1 меню, вам предложено ввести максимальный объем рюкзака.
3) Далее вы вводите количество предметов.
4) Затем вводите размер популяции.
5) После этого вводите шанс кроссинговера и мутации.
6) На экране появляется результат, а именно показаны массы предметов.
7) Далее происходит возврат в меню.
8) При выборе пункта 2 – алгоритм, происходит процесс работы генетического алгоритма и заполнение с его помощью рюкзака. В конце указывается результат.
Реализовать алгоритмы решения классической задачи о рюкзаке. Протестировать их и разбить их на две группы: точные и приближенные, сравнить по скорости решения, по точности. Определить в каких случаях следует использовать тот или иной подход к решению задачи.
Алгоритмы решения можно разделить на два типа: точные и приближенные. Точные: применение динамического программирования, полный перебор, метод ветвей и границ (сокращение полного перебора). Приближенные алгоритмы: Жадный алгоритм.
| Нет |
| Да |
| Меню |
| N=1 |
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 09.03.04.960000.000.ПЗ |
Рисунок 2 – Механизм работы программного средства