Материал: Оптимизация и моделирование в автоматизированных системах. труд. ФГБОУ В.О., Воронежский г.т.и

Рис. 2. Распределение температуры на поверхность шара при граничных условиях u(R,Τ ) в виде 3-D поверхности

Литература

1.Голоскоков, Д. П. Уравнения математической физики: учебник для вузов / Д. П. Голоскоков. СПб: СПбГУВК, 2004. 513 с.

2.Арсенин, С. Я. Методы математической физики и специальные

функции / С. Я. Арсенин. М.: Главная редакция физико-математической литературы, 1984. 385 с.

3. Владимиров, В. С. Уравнения математической физики / В. С. Владимиров. М.: Наука. 1971. 456 с.

Воронежский государственный технический университет

УДК 519.873

К. А. Айвазян, С. А. Олейникова

АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ И АЛГОРИТМОВ РЕШЕНИЯ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ О РЮКЗАКЕ

Объектом исследования в данной работе является задача о ранце. Ее основная идея заключается в выборе из множества объектов наиболее ценного подмножества в условиях ограниченного объема ресурсов (например, размера рюкзака). Данная задача и ее варианты широко используются в прикладной математике, криптографии, экономике, логистике, генетике т.д. Поэтому для задачи о рюкзаке существуют, как её модификации, так и разные методы ее решения, которые будут рассмотрены во второй части статьи.

101

1. Постановка задачи и ее особенности

Задача о рюкзаке может быть сформулирована следующим образом. Имеется множество предметов i = 1, 2, …, n, каждый из которых характеризуется своим весом pi и ценностью ci. Имеется рюкзак емкостью R. Необходимо принять решение о предметах, которые следует поместить в ранец таким образом, чтобы суммарная ценность всех предметов была бы максимальной.

Математически данную задачу можно сформулировать следующим образом:

NP-полной, то есть для нее не существует полиномиального алгоритма, решающего её за приемлемое время [2]. Таким образом, необходимо использовать или быстрый алгоритм без гарантии получения оптимального результата, или точный алгоритм, который позволит найти наилучшее решение, но данный поиск займет слишком много времени. Проанализируем данные алгоритмы.

2. Обзор методов решения задачи о рюкзаке 2.1. Точные алгоритмы

Самый простой из методов решения данной задачи – полный перебор. Допустим, есть N предметов, которые нужно поместить в рюкзак. Для каждого из них существует 2 варианта: 1 – предмет кладется в рюкзак, 0 - нет. Таким образом, перебор всех комбинаций даст ʹ вариантов , что удовлетворяет лишь малому количеству предметов. С ростом числа предметов, методом полного перебора данную задачу решать нецелесообразно. Поэтому возникает необходимость применения методов, которые, снизив количество перебираемых значений, позволили бы найти решение, оптимальное или близкое к нему за приемлемое время.

Одним из вариантов ускорения процесса является отбрасывание подмножеств заведомо неоптимальных решений. Эта идея улучшенного перебора применяется в методе ветвей и границ. Данный метод отличается от полного перебора тем, что просмотр значений осуществляется, начиная с более перспективных с точки зрения целевой функции. Все множество на каждом этапе разбивается на два подмножества, первое из которых, согласно предположением, должно содержать оптимальное решение. Данная процедура повторяется итеративно до тех пор, пока интересующее множество не будет состоять из единственного элемента – потенциального решения. Сравнив значение целевой функции в данной точке и оценки для всех «отброшенных»

102

подмножеств, делается вывод о завершении поиска или продолжении в том подмножестве, оценка целевой функции для которого «лучше». Способность метода ветвей и границ уменьшать количество вариантов перебора сильно опирается на входные данные. Его целесообразно применять только в том случае, когда удельные ценности предметов отличаются значительно. Как и метод полного перебора, он позволяет найти оптимальное решение и относится к точным алгоритмам.

Метод динамического программирования является одним из наиболее эффективных алгоритмов для задач, обладающих так называемой оптимальной подструктурой [3]. Согласно данному методу в данный момент времени надо принимать такое решение, чтобы суммарный выигрыш на данном шаге и всех последующих шагах был бы максимальным». Данный метод для задачи о рюкзаке даёт точное решение, причём одновременно вычисляются решения для всех размеров рюкзака от 1 до W (максимального веса). Временная сложность алгоритма будет порядка O(N·W).

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

2.2. Приближенные алгоритмы

Среди приближенных методов решения задачи следует, в первую очередь, выделить эвристические (т.е. не обоснованных строго математически, но логичных с точки зрения здравого смысла) и метаэвристические (т.е. основанные на обобщении и/или синтезе эвристик) методы.

К эвристическим методам относятся жадные алгоритмы, предлагающие на каждом шаге выбирать такую стратегию, которая в данный момент приводит к оптимальному результату. Для решения задачи о рюкзаке жадным алгоритмом сначала необходимо отсортировать входные данные по их удельным ценностям (отношение ценности к весу). Итоговая сложность алгоритма O(N*log(N)) при необходимости сортировки и O(N) при уже отсортированных данных [3].

Это один из самых быстрых способов решения задачи о рюкзаке (особенно, для больших размерностей). Однако, к сожалению, данный метод далеко не всегда позволяет получить решения, близкие к оптимальным. Рассмотрим это на следующем примере.

Пример. Пусть вместимость рюкзака W = 50. Исходные данные представлены в таблице. В третьем столбце рассчитана удельная ценность предметов.

Применим жадный алгоритм. Среди предметов из таблицы, разумно бы было взять второй и третий предметы, но при работе жадного алгоритма,

103

выбираются предметы один и два, что является не самым оптимальным решением в данном случае.

Таблица

Таким образом, жадные алгоритмы не применимы для решения задачи о рюкзаке.

Генетический алгоритм это метаэвристический алгоритм, за основу работы которого взяты процессы эволюции в природе [1]. Данный алгоритм ориентирован на поиск субоптимального решения в условиях невозможности полного перебора вариантов. Имитируя процесс естественного отбора, генетические алгоритмы способны «разрабатывать» решения реальных задач, если они правильно закодированы. Рассмотрим основные этапы генетического алгоритма:

1.Формирование начальной популяции.

2.Пока не будет выполнен критерий остановки, выполнять:

2.1. селекция 2.2 скрещивание

2.3мутация.

Вкачестве критериев остановки можно выбрать следующие:

глобальное оптимальное (или субоптимальное) решение найдено;

число поколений, отпущенных на эволюцию, исчерпано;

время, отпущенное на эволюцию, исчерпано.

Можно использовать некоторый синтез из предложенных вариантов. Оператор селекции предназначен для выбора из множества потомков

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

Далее идет выбор родительской пары. Очевидно, что при выборе родителей следует учитывать близость значений их целевых функций к желаемому результату (чем «лучше» некоторый родитель (больше или меньше значение целевой функции), тем в формировании большего числа потомков он должен участвовать). Существуют разные варианты для выбора родителей (например, случайный выбор; первый родитель выбирается случайно, а второй

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

104