Содержание к диссертации
Введение
1. Применение генетического алгоритма для решения больших оптимизационных задач 19
1.1. Генетический алгоритм как метод нахождения оптимальных решений 19
1.2. Метод решения задачи одномерного раскроя на основе генетического алгоритма 23
1.2.1. Общее описание задачи одномерного раскроя материалов 23
1.2.2.Метод генерации столбцов 27
1.2.3.Математическая постановка задачи раскроя стальных листов разных размеров 30
1.2.4.Генетический алгоритм для решения задачи раскроя стальных листов 34
1.2.5.Практические результаты применения алгоритма GA-CG для задачи раскроя 36
1.3. Использования генетического алгоритма для решения задачи покрытия множества 39
1.3.1.Постановка задачи о покрытии множества 39
1.3.2. Подход, основанный на генетическом алгоритме, для нахождения минимального покрытия 41
1.3.3.Результаты использования ГА для решения задачи покрытия множества 49
1.4. Оптимизация структуры атомного кластера с помощью генетического алгоритма 53
1.4.1.Задача конфигурационной оптимизации атомного кластера 53
1.4.2.Обзор предложенных методов 55
1.4.3.Генетический алгоритм оптимизации структуры атомного кластера 60
1.4.4. Параллельная реализация 63
1.4.5. Результаты численных экспериментов нахождения оптимальной структуры атомного кластера 64
2. Метод ньютона для решения задачи линейного программирования большой размерности 67
2.1. Нахождение проекции точки на множество решений двойственной задачи линейного программирования . 67
2.2. Программная реализация и результаты вычислений метода Ньютона для решения двойственной задачи ЛП . 81
3. Параллельная реализация обобщенного метода ньютона для решения задачи линейного программирования большой размерности 88
3.1. Параллельный итерационный алгоритм 88
3.2. Основные операции параллельного алгоритма 90
3.3. Схемы разбиения данных
3.3.1.Столбцовая схема
3.3.2.Строчная схема
3.3.3.Клеточная схема
3.3.4.Безматричная схема
3.4. Результаты численных экспериментов
Выводы 102
Цитированная литература 104
- Общее описание задачи одномерного раскроя материалов
- Подход, основанный на генетическом алгоритме, для нахождения минимального покрытия
- Программная реализация и результаты вычислений метода Ньютона для решения двойственной задачи ЛП
- Основные операции параллельного алгоритма
Введение к работе
Объект исследования и актуальность темы.
С развитием человечества растет и объем обрабатываемой информации, что приводит к необходимости решать оптимизационные задачи все больших размерностей. Эта тенденция особенно заметна в таких областях как биоинженерия и экономика. Для решения задач большой размерности наряду со увеличением вычислительной мощности компьютеров необходима разработка новых алгоритмов и методов, эффективно использующих вычислительные ресурсы и позволяющих получить решения для ранее нерешаемых задач.
Было разработано множество алгоритмов и методов решения различных оптимизационных задач. Многие практические задачи характеризуются высокой размерностью, наличием трудно формализуемых ограничений, нечисловым характером части переменных. При этом как формализация, так и численное решение задач принятия решений при планировании, распределении ресурсов, оптимизации сложных процессов в различных приложениях вызывает известные трудности.
В частности, существенные затруднения связаны с высокой размерностью решаемых задач. Многие прикладные задачи экономики и управления могут быть представлены в виде задач линейного программирования (ЛП), для решения которых давно существуют численные методы и программное обеспечение, и, как могло бы показаться, не представляет никакой трудности найти оптимальное решение [1], [2]. Однако размерности современных задач порою не позволяют решить их традиционными способами, поэтому требуется разработка новых подходов решения с привлечением мощных вычислительных ресурсов. Наличие больших, более мощных и доступных мультипроцессорных компьютеров означает, что
параллельное программирование является важным и перспективным направлением современной вычислительной науки, которое целесообразно применять для решения задач большой размерности [3]. Большие практические задачи ЛП часто обладают специфической блочной структурой, для учета которых разработаны различные методы декомпозиции [4]. Большие задачи ЛП, как правило, имеют неединственное решение. Различные методы решения задач ЛП (симплекс-метод, метод внутренних точек, метод квадратичной штрафной функции) дают возможность получать различные решения в случае не единственности. Так симплекс-метод дает решение, которое принадлежит вершине многогранного множества. Методы внутренней точки сходятся к решению, в котором выполнено условие строгой дополняющей нежесткости. Метод внешней квадратичной функции дает возможность найти точное нормальное решение. В данной работе предлагается новый метод нахождения проекции заданной точки на множество решений задачи Л П.
Другие затруднения могут быть связаны с отсутствием эффективных методов решения NP-трудных задач математического программирования [5]. Это класс задач, для которых характерны такие отличительные признаки, как экспоненциальный рост вычислительной сложности. Представителями указанного класса задач являются NP-полные задачи оптимизации. NP-полные задачи обладают свойством универсальности, так как любая из NP-полных задач может быть сведена к другой NP-полной задачи за полиномиальное время. Это означает, что если будет найден полиномиальный алгоритм решения для одной задачи, то все NP-полные задачи будут решаться за полиномиальное время. К сожалению, попытки найти полиноминальный алгоритм на протяжении нескольких последних десятков лет, не увенчались успехом. Поэтому много исследований в настоящее время направлено на решение
NP-полных задач с некоторой допустимой ошибкой и за приемлемое время. К числу NP-полных задач относятся многие проектные и логистические задачи, например, синтез топологии вычислительных сетей и распределение в них трафика, раскрой материалов, компоновка оборудования, синтез расписаний производственных процессов, маршрутизация транспортных средств и др.
Нахождение глобального оптимума является общей проблемой для многих отраслей науки, техники и управления, а её решению, глобальной оптимизации, посвящен отдельный раздел прикладной математики [6]. Задачи нахождения глобального оптимума являются весьма сложными с вычислительной точки [7]. В настоящее время большинство методов поиска глобальных экстремумов относится к направленному перебору. Встречающиеся же прикладные: задачи глобальной оптимизации зачастую требуют поиска глобального минимума в пространстве достаточно большого числа переменных исследуемой функции. Примерами таких задач из области химии является поиск глобального минимума поверхности потенциальной энергии (ППЭ) ван-дер-ваальсовых комплексов [8] и предсказание третичной структуры белков [9]. '
Часто попытки решения NP-трудных задач дискретной или глобальной оптимизации большой размерности связаны с использованием тех или иных эвристических методов. В результате "решения" могут оказаться далекими от оптимальных.
В 1975г. Дж. Холландом было показано, что поиск решения оптимизационной задачи можно представить в виде эволюции группы решений [10]. Это позволило успешно моделировать процессы, происходящие в природе, для решения NP-полных задач. В последние годы разработчики методов и программ для решения сложных проектных и оптимизационных задач все чаще обращают внимание на
эволюционные методы, среди которых алгоритм муравьиной колонии, алгоритм моделирования отжига и генетические алгоритмы.
Генетический алгоритм (ГА) представляет собой технику оптимизации, которая моделирует феномен естественной эволюции (впервые открытой Ч. Дарвином) [11]. При естественной эволюции выживают и дают самое многочисленное потомство особи, наиболее адаптированные к сложным условиям окружающей среды. Степень адаптации, в свою очередь, зависит от набора хромосом конкретной особи, полученного от родителей. Это основа выживания сильнейшего -не только процесс выживания, но и участие в формировании следующего поколения. В природе выживание является определяющей и основной функцией. Генетический алгоритм не пытается оптимизировать единственное начальное решение. Он работает с группой начальных решений, которые кодируются, подобно хромосомам. Отдельные гены хромосомы представляют собой уникальные переменные для изучаемой проблемы. На каждом шаге генетического алгоритма присутствует набор объектов - особей, обладающих "генетической информацией", или "хромосом". Для пар особей определяются правила скрещивания, согласно которым, при переходе на следующий шаг алгоритма, производится потомство на основе "генетической информации" родителей. Из этого потомства при помощи критерия приспособленности выбираются особи, которые войдут в следующее поколение. При отборе "здоровых" хромосом из популяции и использовании генетических операторов (таких как рекомбинирование и мутация) в популяции остаются только те хромосомы, которые лучше всех приспособлены к окружающей среде, т.е. наиболее полно отвечают задаче. Особи могут также подвергаться случайным мутациям, в результате которых наследственная информация подвергается изменениям.
Использовавшиеся для моделирования биологической эволюции
генетические алгоритмы были обобщены для использования в глобальной оптимизации [12]. В этом случае - "генетическая информация" - это точка в пространстве аргументов, а "приспособленность" - значение целевой функции. Правила скрещивания и мутации выбираются в зависимости от строения множества, на котором определена целевая функция.
К достоинствам генетических алгоритмов относится простота принципов и использование исследуемой функции как "черного ящика", о свойствах которой может быть ничего не известно до начала оптимизации. Однако существенным недостатком является большая специфичность правил скрещивания и мутации по отношению к исследуемой функции. В рамках использования генетических алгоритмов в каждой новой задаче исследователь вынужден вновь формулировать новые правила скрещивания и мутации. Тем не менее, генетические алгоритмы являются достаточно мощным средством решения задач глобальной оптимизации, поскольку их недостатки зачастую оборачиваются их достоинствами. Во-первых, "потомки" всегда несколько похожи на "родителей", за счёт чего процедура позволяет быстро выделить фрагменты генетической информации, отвечающие наилучшей приспособленности и использовать их на следующих шагах алгоритма. Во вторых, правила мутации и скрещивания могут быть подобраны таким образом, что используют особенности задачи при минимизации. И наконец, программы с использованием генетических алгоритмов реже требуют перепроверки результатов и повторного запуска, чем программы с использование моделирования отжига. Но наибольшее преимущество генетические алгоритмы имеют при глобальной оптимизации функции дискретных переменных, когда применение других подходов затруднено.
В связи с интенсификацией производства в настоящее время вопросы
оптимизации планирования и управления производства на предприятиях очень актуальны. Перспективным направлением работ по повышению эффективности функционирования автоматизированных систем управления является разработка и реализация программных систем, позволяющих решать совокупность взаимосвязанных оптимизационных задач планирования производства. Построение оптимальных карт раскроя ресурсного материала является одной из самых трудоемких задач на заготовительной стадии производства. В то же время это одна из самых важных задач в ресурсосберегающих технологиях, поскольку напрямую ведет к экономии материала и снижению отходов. Начало теоретическим исследованиям в области методов рационального раскроя положили труды академика Л. В. Канторовича [13, 14], в которых он показал возможность эффективного решения оптимизационных задач с помощью ЭВМ. В своих работ Канторовича Л. В. впервые представил задачу раскроя одинаковых листов материала в виде задачи целочисленного линейного программирования, в которой матрица ограничений задана неявно. Эта модель стала основой для многих методов решений. На протяжении последних 70 лет исследованиям в области раскроя и разработки новых алгоритмов укладки плоских заготовок было посвящено множество отечественных и зарубежных работ [15] - [53]. Однако задача раскроя на заводах, где в качестве исходных ресурсов используют материалы различных типоразмеров, порождает очень большую матрицу ограничений, а вместе с тем и огромное количество переменных, что часто не позволяет использовать классические оптимизационные методы. В работе [54] показано, что построение эвристических алгоритмов для решения задачи раскроя материалов различных размеров необходимо, так как точные подходы не пригодны в этом случае. Разработка нового метода решения конкретной практической задачи с учетом ее специфики позволит получить
качественно лучшее решение и таким образом повысить эффективность производства.
Задача о покрытии множества (ЗПМ) системой его подмножеств [55]-[57] является математической моделью для многих важных приложений, таких как составление расписания [58], планирование сервиса, распознавание образов [59]-[61], прогнозирование, логический анализ данных, упрощение булевских выражений [57] и т.д. ЗПМ относится к классу NP-полных задач [5], поэтому построение алгоритма нахождения оптимального или приближенного решения является весьма сложной задачей. Однако структура представления реальной задачи предоставляет дополнительную информацию, позволяющую решать ЗПМ довольно больших размерностей (несколько сотен строк и несколько миллионов столбцов) с результатом, отличающимся от оптимального решения примерно на 1%, за приемлемое время счета [57]. Практические методы решения ЗПМ опираются на различные подходы и могут быть распределены по классам таким, как класс алгоритмов, основанных на теории линейного программирования, класс эвристических алгоритмов и класс алгоритмов ветвей и границ [62]. В данной работе будет приведено формальное представление задачи, а так же предложен алгоритм решения ЗПМ, основанный на принципах генетического алгоритма.
Исследования атомных и молекулярных кластеров - быстро развивающаяся область физики и химии [63]-[77]. Как видно из приведённых литературных данных, совершенствование теоретических и экспериментальных методов позволяет исследовать все более сложные системы со всё возрастающей точностью. Поверхности потенциальной энергии кластеров являются своеобразным местом встречи, где теоретические модели могут найти подтверждение со стороны экспериментальных подходов. В то же время, функции,
описывающие ППЭ кластеров, в дополнение к большому числу аргументов (степеней свободы), обладают во многих случаях большим числом стационарных точек. Правильное нахождение геометрических конфигураций кластеров, отвечающих наиболее глубоким минимумам ППЭ, важно для правильного описания свойств этих частиц. В то же время, нахождение стационарных точек и, в частности, минимумов, на сложных гиперповерхностях представляет собой отдельную проблему, для решения которой существуют специализированные численные методы. ГА является успешным методом определения глобального минимума, но иногда с физической точки зрения структуры, соответствующие более высоким локальным минимумам, могут быть более важными, чем глобальный минимум. Наконец, стоит отметить, что биологически активные формы белков, возможно, не всегда соответствуют глобальным минимумам. Таким образом, возможность ГА наряду с поиском глобального минимума находить семейство локальных минимумов, близких к глобальному, является особенностью этого метода и имеет важную практическую ценность.
В связи с вышеизложенным, целью диссертационной работы является разработка эффективных методов и их программная реализация для решения больших оптимизационных задач на примере задачи линейного программирования, раскроя материалов, покрытия множества его подмножествами и задачи глобальной оптимизации структуры атомного кластера с использованием точных и генетических алгоритмов.
В соответствии с целью исследования были поставлены и выполнены следующие конкретные задачи:
Разработка методов решения задачи линейного программирования с большим числом переменных и ограничений, программная реализация и проведение вычислительных экспериментов;
Разработка параллельных схем обобщенного алгоритма Ньютона
решения больших задач линейного программирования и их программная реализация;
Разработка алгоритма решения задачи одномерного раскроя листовых материалов различных типоразмеров на основе генетического алгоритма и алгоритма генерации столбцов;
Исследование задачи покрытия множества и разработка алгоритма ее решения на основе генетического алгоритма;
Разработка и реализация эффективных генетических алгоритмов для поиска глобальных минимумов на поверхности потенциальной энергии атомного кластера.
Научная новизна:
Разработан новый эффективный метод решения двойственной задачи ЛП с большим числом переменных и небольшим числом ограничений. Метод основан на новой выпуклой кусочно квадратичной функции с числом переменных, равным числу ограничений в задаче ЛП, и применение для ее безусловной минимизации глобального конечносходящегося обобщенного метода Ньютона. Показана возможность получения проекции точки на множество решений двойственной задачи ЛП, начиная с некоторого порогового значения коэффициента, входящего во вспомогательную функцию. Найдена оценка этого порогового значения коэффициента.
Предложены и программно реализованы параллельные схемы обобщенного метода Ньютона для вспомогательных задач безусловной оптимизации, возникающих при решении задач линейного программирования.
Предложен комбинированный алгоритм решения задачи одномерного раскроя листовых материалов различных размеров с использованием генетического алгоритма и метода генерации столбцов.
Представлен новый алгоритм нахождения минимального покрытия множества на основе генетического алгоритма, проведено сравнение полученных результатов с имеющимися результатами в известной базе данных, показавшее высокую эффективность разработанного
алгоритма.
5. Разработан генетический алгоритм оптимизации структуры
атомных кластеров. С его помощью найдены новые решения,
отсутствующие в известной Кембриджской базе данных.
Практическая ценность работы состоит в разработанных методах и их программах для решения болыпих задач оптимизации: линейного программирования, раскроя листовых материалов, задачи о покрытии множества и задачи оптимизации структуры атомного кластера.
Разработанный алгоритм решения задачи одномерного раскроя листовых материалов различных типоразмеров внедрен и успешно используется в производственном процессе трубопрокатного завода VG PIPE (Вьетнам).
Результаты, выносимые на защиту состоят в следующем:
1. Разработаны, программно реализованы генетические алгоритмы решения следующих задач:
(а) одномерного раскроя листовых материалов разных размеров;
(б) задачи о покрытии множества системой его подмножеств;
(в) глобальной оптимизации структуры атомных кластеров;
Разработан, теоретически исследован и программно реализован конечный метод нахождения проекции заданной точки на множество решений двойственной задачи ЛП с большим числом переменных;
Получена оценка порогового значения параметра, начиная с которого метод находит проекцию заданной точки на множество решений двойственной задачи ЛП;
Предложены и программно реализованы параллельные схемы обобщенного метода Ньютона для решения вспомогательных задач безусловной оптимизации при решении задач линейного программирования.
Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях:
На 13-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, Россия, 2007 г.);
На 9-м Международном семинаре по компьютерным наукам и информационным технологиям CSIT'07 (Уфа, Россия, 2007 г.);
На XIV Байкальской международной школе-семинаре (Иркутск, Байкал, Россия, 2008 г.);
На семинарах отдела прикладных проблем оптимизации ВЦ РАН (Москва, Россия, 2006-2008 гг.);
Основные результаты опубликованы в [78]-[83].
Во первой главе рассматривается генетический подход для решения больших задач оптимизации. В 1.1 дано общее описание генетического алгоритма как метода решения сложных оптимизационных задач. Далее рассмотрены две NP-полные задачи раскроя листовых материалов
и покрытия множества, а также задача глобальной оптимизации структуры атомного кластера.
В 1.2 приведена модель задачи одномерного линейного раскроя материала, предложенная Л.В. Канторовичем в [13]. Из всех известных методов решения этой задачи выбран и описан метод генерации столбцов. Представлена так же модель для расширенной задачи раскроя с различными исходными материалами на примере раскроя листов стали на трубопрокатном заводе. Показано, что для расширенной задачи .значительно возрастает степень сложности из-за роста количества переменных, и таким образом, почти невозможно решить ее целиком с помощью известных алгоритмов. Доказано, что решение "большой" задачи определено на множестве разбиений вектора заказа. На основе доказанных теорем разработан новый алгоритм решения расширенной задачи на основе комбинирования генетического алгоритма с методом генерации столбцов. Работа предложенного алгоритма продемонстрирована на наборе тестовых примеров. Результаты практического внедрения алгоритма в производственный процесс трубопрокатного завода VG PIPE (Вьетнам) показали его эффективность с точки зрения сокращении объема отходов. Отход металла уменьшился почти в 2 раза.
В параграфе 1.3 предложен эвристический алгоритм решения задачи нахождения минимального покрытия с неоднородной стоимостью. Алгоритм основан на генетическом алгоритме с операторами кроссовер и мутации, моделирующими различные свойства естественной эволюции, такие как "доминантность", "чистокровность" и "биологическое разнообразие". Работоспособность разработанного алгоритма проверена на тестовых задачах библиотеки OR-library [84], доступной в Интернете. Результаты вычисления показывают, что алгоритм может дать оптимальное решение для задач средних размерностей и качественно
лучшее решение для задач больших размерностей, чем полученное другими алгоритмами и опубликованное в библиотеке OR-library.
Задача оптимизация структуры атомного кластера подробно рассмотрена в параграфе 1.4. Дан обзор как точных, так и эвристических методов поиска минимумов поверхности потенциальной энергии. Представлен генетический алгоритм нахождения множества достаточно хороших конфигураций атомных кластеров с точки зрения минимальной потенциальной энергии без возможности доказательства оптимальности найденных решений. Предложенный алгоритм призван найти набор "хороших" структур атомного кластера за относительно малое время вычислений. Так же разработана схема параллельной реализации предложенного алгоритма, дающая возможность использования современных мощных вычислительных комплексов для нахождения оптимальных структур атомных кластеров больших размеров. Приведено сравнение работы предложенного алгоритма с алгоритмом монотонного случайного спуска по локальным минимумам (Mono-tonic Basin Hopping) для некоторых кластеров Ленарда-Джонса. Так же представлены результаты вычислений для кластеров Морса с количеством атомов 80 < Natom < 95, отсутствующие в Кембриджской базе данных [85] .
В главе 2 предлагается новый метод нахождения проекции заданной точки на множество решений двойственной задачи ЛП, который весьма эффективен для решения в системе MATLAB для однопроцессорных компьютеров задачи ЛП с большим числом переменных (до несколько десятков миллионов) и средним числом ограничений- неравенств (до 5 тысяч ограничений). Метод заключается в однократной безусловной оптимизации вспомогательной функции и находит проекцию, если параметр этой функции больше некоторого порогового значения. Получена формула для этого порогового значения.
Показано, что повторная безусловная оптимизация этой функции, в которой вместо точки проектирования взято решение двойственной задачи, дает некоторое точное решение прямой задачи ЛП. То есть решения прямой и двойственной задач ЛП можно найти в результате двукратной безусловной оптимизации вспомогательной функции, размерность переменных которой равна числу ограничений задачи ЛП. Для безусловной оптимизации предлагается использовать обобщенный метод Ньютона. Так как вспомогательная функция является выпуклой квадратичной функцией, то для ее минимизации целесообразно применять обобщенный метод Ньютона, который, как показал О. Мангасарьян [86], сходится глобально за конечное число шагов. В параграфе 2.1 приведена программа DLP, которая реализует предложенный метод в системе MATLAB. Проведены численные эксперименты на случайно сгенерированных задач ЛП. Они показали высокую эффективность предложенного метода, возможность решать задачи ЛП с несколькими миллионами переменных и до 5 тысяч ограничений за приемлемой время. Сравнение раннее предложенного метода нахождения проекции на множество решений двойственной задачи [87] с предложенным в данной работе показало явное преимущество последнего. Это связано с тем, что в [87] вспомогательная функция оптимизируется на положительном ортанте и для применения обобщенного метода Ньютона требуется учесть условия неотрицательности переменных с помощью штрафной функции. Еще раз подчеркнем, что предлагаемая в работе вспомогательная функция оптимизируется на всем пространстве обобщенным методом Ньютона.
В третьей главе предлагаются, исследуются и экспериментально проверяются четыре параллельные схемы решения задач ЛП с помощью метода, предложенного в [88]. Метод из [88] подробно исследован в [87]. Численные эксперименты и сравнение программы
EGM, реализованной в MATLAB, с известными коммерческими и исследовательскими программами показали превосходство программы EGM [89] и возможность решать задачи ЛП с 50 миллионами переменных , но с небольшим числом ограничений (не более 4 тысяч). Параллельная реализация позволила увеличить число ограничений до 200 тысяч и решать задачи ЛП за существенно меньшее время.
Общее описание задачи одномерного раскроя материалов
Задача о рациональном раскрое была одной из проблем, сформулированных видным советским ученым Л. В. Канторовичем в 1939 году в его работе «Математические методы организации и планирования производства» [13]. Проблема заключалась в определении наиболее рационального способа раскроя некоторого множества больших объектов на меньшие части. Постановка задачи, формализованная Л. В. Канторовичем в [13] представляет собой одну из типовых задач целочисленного программирования и определяется следующим информационным вектором: (т, L, 1Т — (li...lm), bT = (bi...bm)), где L - ширина листа раскраиваемого материала, m - количество различных заготовок, раскраиваемых из исходного листового материала, k - ширина заготовки типа і, а &; есть требуемое количество заготовок этого типа, т.е. заказ на этот тип продукт. Цель задачи в нахождении плана раскроя, минимизирующего количества используемого материала для выполнения заказа. Пусть N - верхняя граница количества листов материала, требующего в оптимальном решении, a Xij(i = І,..,7П, j — 1,.., N) - количество заготовок вида г, раскраиваемого из листа материала j. Зададим ijj = 1, если лист материала j использован в решении, и yj = 0, если иначе. Тогда задача имеет следующую модель: N zkant = mmY,yj (1-1) m J Uxij Lxj, j = 1,..., N (1.2) г=1 N XijeZ+, Vj E {0,1}, 4i,j. (1.4) Н.Гери и Д.Джонсон показали, что простейшая задачи одномерного раскроя (упаковки) принадлежит классу NP-полных задач [5]. Позже в работе Л. В. Канторовича и В. А. Залгаллера [14] впервые задачи линейного и гильотинного раскроя описываются моделью линейного программирования с неявно заданной информацией о столбцах матрицы (раскроя). Г. Данциг и П. Вулф в [20] предложили новую модель для преодоления недостатка со слабой непрерывной релаксацией модели (1.1)-(1.4), так называемое разложение Данцига-Вулфа. В новой модели граница вектора раскроя лежит на выпуклом оболочке всех допустимых вариантов раскроя, полученных в (1.2). В [17] была предложена аналогичная модель, в которой возможные раскройные шаблоны описываются вектором, каждый элемент которого равняется количеству заготовок заданной длины, получаемых из раскройного шаблона. Пусть материалы для раскроя на заготовок поступают на производство в виде одинаковых листов, обозначим через вектора а? — (aij...amj) Є Z, j — 1,... ,n, шаблон раскроя j с компонентами о , указывающими в нем количество заготовок типа і = 1,..,т.
Если считать, что все векторы a-7, j = 1,...,п заданы, то задача IDCSPQ является задачей линейного целочисленного программирования. Однако модель (1.6)-(1.8) является задачей целочисленного линейного программирования с количеством переменных п, растущим с экспоненциальной скоростью в зависимости от т и в общем случае невозможно осуществить перебор всех возможных решений, поэтому в [17, 18] предложен метод генерации столбцов для решения задачи релаксации линейного программирования, который стал одним из самых распространенных и эффективных методов решения задач линейного программирования большой размерности. Стоит отметить, что существуют и другие формулировки задачи раскроя, использующие графы, понятие потока по дуге и ациклические сети, основанные на модели многопродуктового потока [38], но они менее популярны.
Оптимизационные задачи комбинаторной природы, подобные задаче рационального раскроя, возникают во многих отраслях промышленности и обладают значительным экономическим потенциалом. Металл, древесина, бумага, стекло и текстиль - существует обширная номенклатура материалов, которые разрезаются на меньшие части заданной формы и размера в процессе производства готовых изделий. Даже незначительное улучшение эффективности раскроя исходного сырья способно обеспечить ощутимый экономический эффект, что связано, в первую очередь, с большими объемами промышленного производства.
Логично, что подобные задачи вызывают значительный интерес ученых всего мира, и полувековой истории активных исследований соответствует обширная библиография. За эти годы было предложено множество различных методов, направленных на получение решений задач подобного вида, пригодных для практического использования. Соответственно уточнялись и различные аспекты самих задач рационального раскроя.
Первые обзорные работы в этой области появились в начале 70-ых годов [14, 19], в них высказывались соображения о тесной взаимосвязи, существующей между задачами раскроя и упаковки. Последовательная работа по созданию единой классификации подобных задач проводилась в [21]-[24]. В работах [21, 22] представлена качественная типология в области раскроя-упаковки, принятая в мировой практике. Обзор методов решения проведен в работе [23]. Аналитический обзор в области раскроя и упаковки выполнен Э.А. Мухачевой и ее учениками в [49],[50]. Этой группой также проведено исследование по применении генетического алгоритма для решения задачи двухмерного раскроя [51].
Расширением классической задачи одномерного раскроя материала является задача раскроя материалов различных типоразмеров, рассмотренная во многих работ [30, 31, 32, 38, 54]. Одно общее утверждение состоит в том, что возможность применения материалов различных размеров улучшает оптимальность использования материала по сравнению с применением только одного типа материала. Но в [54] показано, что построение эвристических алгоритмов для решения расширенной задачи необходимо, так как точные подходы не пригодны в этом случае. Этот факт был подробнее рассмотрен в [42], где авторы предложили правило генерирования задач, у которых разница между решениями задачи непрерывной релаксации и соответствующей задачи целочисленного программирования становится очень велика, то есть свойство, подобное свойстве IRUP для задачи 1DCSP, не удовлетворяется. Авторы так же привели примеры конкретных задач, построенных на предложенном правиле. В следующем разделе будет дано описание алгоритма генерации столбцов для решения классической задачи одномерного линейного раскроя однотипного материала. Далее в главе дается содержательное описание объекта автоматизации - завода по производстве стальных труб, строится математическая модель, проводится ее исследование. В рамках построенной модели ставится оптимизационная задача нахождения рационального плана раскроя стальных листов на заготовки, соответствующие различным видам труб, для производства с минимальным количеством использованных ресурсов. Будет показано, что поставленная задача является задачей одномерного раскроя материалов различных типоразмеров. Разрабатывается эффективный алгоритм решения поставленных задач, основанный на использования генетических алгоритмов и линейного программирования. Разработанный алгоритм лег в основу программной системы, реализующей интерактивные программные средства решения оптимизационных задач планирования процессом производства на заводе по производстве стальных труб.
Подход, основанный на генетическом алгоритме, для нахождения минимального покрытия
Опишем шаги генетического алгоритма в терминах ЗПМ. Не теряя обпщости, можем предположить, что подмножества в ЗПМ упорядочены по мере возрастания стоимости, для подмножеств с одинаковой стоимостью упорядочение будет производиться в соответствии с уменьшением количества элементов, содержащихся в подмножествах.
Представление задачи и функции приспособленности Первым этапом формирования ГА является выбор подходящего представления (способа кодирования) для заданной задачи. Для решения данной задачи выбрано двоичное представление. Каждая особь к представлена хромосомой, являющейся n-мерным вектором хк , у которого j-й. элемент хк принимает значение 1, если подмножество Sj входит в покрытие, и принимает значение 0, если иначе. С таким представлением степень приспособленности fk особи хк может быть рассчитан следующим образом п i=i где Cj - стоимость подмножества Sj . Выбор родительских особей Выбор родительских пар для скрещивания дает возможность особям возрождаться. Был предложен ряд методов выбора родительских пар. В данном алгоритме будем применять метод пропорционального выбора. Согласно этому методу каждой особи будет присвоена вероятность выбора в соответствии с ее степенью приспособленности и выбор будет производиться на основе этих вероятностей. Вероятность выбора для каждой особи рассчитывается по следующей формуле Pk = - -, (1.37) і/Л к=1 где fk - степень приспособленности fc-ой особи в популяции и N - размер популяции. Нужно отметить, что ЗПМ является задачей минимизации, поэтому вероятность выбора у каждой особи обратно пропорциональна ее степени приспособленности. Оператор скрещивания (кроссовер)
Обычно в генетических алгоритмах используется одноточечный или двухточечный кроссовер. Тогда точки кроссовера, созданные случайным образом, будут делить хромосому на несколько кусков гена. Куски гена родительских пар будут обменены для получения потомков. Оператор кроссовер может быть формально определен следующим образом: Поэтому они не могут моделировать доминирующие и рецессивные характеры соответствующих пар генов родителей. Для устранения этого ограничения предлагается новый оператор кроссовер, создающий только одного потомка от каждого пара родителей и позволяющий потомку унаследовать доминирующие гены от родителей. Если гены в одном месте одинаковы для обеих родительских хромосом, то потомок просто копирует этот ген. Иначе, если соответствующие гены у родителей неодинаковы, то доминирующий ген определяется в зависимости от степени приспособленности особи и от частоты появления этого гена в популяции. Степень приспособленности особи отражает "абсолютную доминантность" комплексного отношения между генами, создающими хромосому этой особи, над хромосомам других особей. Частота появления гена в популяции отражает "относительную доминантность" гена при отдельном рассмотрении. Высокая частота появления гена в популяции подтверждает его важность в создании рассматриваемой популяции. Другими словами частота появления гена в популяции говорит о его "чистокровность" с точки зрения гена. Исходя из этой идеи предлагается следующий новый оператор кроссовера.
Пусть /J-PJ и fxp2 есть степени приспособленности родительских особей xPl и хР2 соответственно и определяются по (1.37), xCh есть потомок, полученный в результате применения оператора кроссовера над xPl и хР2.
Многие авторы предлагают использовать постоянную частоту мутации, равную 1/п. Тогда мутация будет происходить на случайно выбранном гене. Эта частота оказывается слишком мала при сходимости генетического алгоритма, особенно когда алгоритм приближается к локальному экстремуму. В локальных экстремумах особи в популяции могут быть рассмотрены как "единокровные". Поэтому для улучшения этой популяции мы должны уменьшить "единокровность" и увеличить "биологическое разнообразие" популяции. Использование переменной частоты мутации позволяет осуществить эту идею. Приведем метод определения переменной частоты мутации.
Для каждого j-ro гена, 1 j п, рассчитываем соответствующую энтропию Hj = -po(j) logpo(j) - PiU) І0еРі(Л, (1.41) 4-1 где po(j) и pi(j) - выше определенные частоты появления значения 0 и 1 в j-ом гене в популяции. Считаем, что чем меньше Hj, тем больше степень "единокровности" особей в популяции в контексте j-ro гена. Например, если для какого-то j-ro гена его значения в паре родительских особей одинаковы, тогда после описанного выше оператора кроссовер j-й ген потомка будет иметь то же значения, что и у родителей. В результате генетический алгоритм может остановиться в некотором локальном экстремуме. Ясно, что "чистокровность" и "единокровность" с какой-то точки зрения являются понятиями с противоположными эффектами, но не противоречат, а дополняют друг другу. В генетическом алгоритме операторы кроссовер и мутации частично отображают это свойство. Оператор мутации помогает расширить пространство поиска, другими словами, создает "биологическое разнообразие", позволяет алгоритму выйти из локальных экстремумов. В процессе создания популяции операторы кроссовер и мутации используются подходящим образом для балансировки между "чистокровностью" и "биологическим разнообразием".
Если популяция не имеет схему, то для всех j, 1 j П, IIj ф 0. В случае существования схемы можно разделить хромосому на отдельные участки, в которых нет схемы. Это разбиение гарантирует, что энтропии генов, лежащих в каждой участке, отличны от 0, и оператор мутации будет применен отдельно на каждой участке.
Программная реализация и результаты вычислений метода Ньютона для решения двойственной задачи ЛП
Для проведения вычислительных экспериментов с разработанным в разделе 2.1 методом был использован генератор тестовых задач, предложенный в [ПО]. Этот генератор порождал разрешимые двойственные задачи (D) с большим числом переменных (до 10 млн.) и средним числом ограничений типа неравенств (до нескольких тысяч), т.е. имело место т » п.
Генератор задач ЛП работал следующим образом. Задавались числа тип, определяющие количество строк и столбцов матрицы А, и р -плотность заполнения матрицы А ненулевыми элементами. В частности, значение р = 1 означает, что случайным образом генерировались все элементы матрицы Д а значение р — 0.01 указывает, что в матрице А генерировались только 1% элементов, а остальные полагались равными нулю. Элементы матрицы А задавались случайным образом из интервала [-50 , 50].
Решение х прямой задачи (Р) и решение w двойственной задачи (D) генерировались следующим образом. Полагалось, что в векторе ж содержится п — Зга нулевых компонент, а остальные компоненты выбирались случайным образом из интервала [0,10]. Половина компонент вектора и полагалась равными нулю, а остальные выбирались случайным образом из интервала [-10,10]. Решения ж и и использовались для вычисления коэффициентов целевой функции с и правых частей Ъ задачи (Р). Векторы Ъ и с определялись по формулам Ъ — Ах , с = АТи + , где, если ж г 0, то г = 0, если х г = 0, то компонента г выбиралась случайным образом из интервала 0 "fl г 9г. Для генерации тестовых задач использовалась следующая программа, составленная для системы MATLAB. Code 1. Генератор тестовых задач линейного программирования % Code 1: Generator random solvable LP: 7, min c x s.t. Ax=b, x =0 ; A:m-by-n % Input: m,n,d(ensity); % Output: A,b,c; (x,u): primal-dual solution pl=inline(5 (abs(x)+x)/2 ); 7»pl(us) function A=sprand(m,n,d); A=100 (A-0.5 spones(A)); u=10 spdiags((sign(pi(rand(m,1)-rand(m,1)))),0,m,m) (rand(m,l) - rand(m,l)); x=sparse(10 pl(rand(n,l)-(n-3 m)/n)); b=A x; xi=spdiags((ones(n,1)-sign(pi(x))),0,n,n) (ones(n,l) + 9 rand(n,l)); c=A u+xi; Предлагаемый метод решения прямой и двойственной задач ЛП (метод ДП) сочетает итерационный процесс (2.56)-(2.57) и обобщенный метод Ньютона, примененный для решения задачи (2.58). Метод реализован в системе MATLAB в виде программы DLP. Критерием окончания итераций (2.56)-(2.57) было условие \\uk+i - UfcHoo + \\vk+i - VjbHoo to/2. (2.60) Критерием окончания процесса безусловной максимизации по методу Ньютона было выполнение неравенства \\ys+i-ys\\oo toll. (2.61) Обычно бралось toll = Ю-12 tol2 = 1СГ7. В конце расчетов вычислялись чебышевские нормы векторов невязок: Ai = \\Ах - &оо, А2 - \стх - Ьти\, А3 = \\(Ати Л-v- с)\\х. (2.62) Ниже приводится текст программы DLP, реализующей метод (2.56)-(2.58). Code 2. Программа DLP для решения задач ЛП %DLP - Solve dual LP: max b u s.t. A u+v = с ; v =0; A:m-by-n /„m n /0Input: random generated LP; "/„Output: (xs, [us, vk]) : primal-dual solution tol=le-12; tol2=le-7; delta=le-5; itmax=50; kmax=10; %alia=0.00001; /.inputs pl=inline(3 (abs(x)+x)/2 ) ; /0pl(us) function i=0; z=0; y=ones(n,l); k=0; usl=l; us=zeros(m,1); vkk=zeros(n,1); vk=zeros(n,1); tic; tocl=toc;kriter=inf; while (kriter tol & k kmax) z=0; j=0; while ( j itmax & norm(y-z,inf) tol2) df=c-A us-A (alfa b-A y)-pi(vk-y); d2f=A A+alfa spdiags(sign(pl(vk-y)),0,n,n) + delta speye(n); z=y;y=y-d2f/df;j=j+l; end usl=us;us=usl+alfa b-A y;vkk=vk;vk=pl(vkk-y); k=k+l; kriter = sqrt(norm(us-usl,inf)2+norm(vk-vkk,inf)2); end toc2=toc;t_time=toc2ocl;xs=y/alfa; PrInfe=norm(b-A xs,inf);DuInfe=norm(A5 us+vk-c,inf); DuGap=abs(b us-c5 xs); disp([PrInfe DuGap Dulnfe]); disp([j к t_time]); Решалось 20 двойственных задач с большим числом неизвестных {т - размерность вектора и достигала 107). Число ограничений типа неравенств достигало 4000. Заполненность матрицы А бралась равной 1% и 100%. Максимальное значение а во всех расчетах было а = 0.2 .
В [87] был программно реализован (программа EGM2 для системы MATLAB) этот подход к нахождению проекции й точки й на множество решений С/ двойственной задачи. В таблице 8 приведено сравнение работ программ EGM2 и DLP. Из этой таблицы видно, что использование предложенного в параграфе 2.1 метода дает лучшие результаты по времени счета. В программе EGM2 коэффициент штрафа т был постоянным и всюду брался достаточно большим (г = 105). Этот достаточно большой коэффициент штрафа приводит к тому, что для достижения одинаковой точности решения задачи ЛП (Лі = Ю-10, Л2 = 10 8, Лз = Ю-10) требуется больше времени обобщенному методу Ньютона для решения задачи безусловной максимизации (2.66), чем для решения задачи max {-сту + йтАу - \\ab - Ау\\2 -\\\(v- у)+\\2 (2.67) в которой отсутствует коэффициент штрафа. При решении задач с большим числом ограничений или переменных, чем в таблице 8, вермя решения программой DLP было на порядок меньше, чем программой BGM2. Отметим, что между методом из [87] и результатом теоремы 2.1 имеется следующее различие: в первом случае находится проекция й Є СУ заданной точки й, а из (2.34), (2.35) находится проекция w = [й ,й»=] точки w = [u,v] на множество решений W .
Основные операции параллельного алгоритма
Параллельная реализация алгоритма 1)-7) требует распараллеливания следующих основных операций: умножение матрицы на вектор: Ар и Атх; вычисление скалярных произведений вида хту, , у Є Rm и pTq, p,q Є R"; формирование обобщенной матрицы Гессе (3.5); умножение обобщенной матрицы Гессе на вектор; Заметим, что все оставшиеся вычисления на этапах алгоритма 1) -7) являются локальными. Например, метод сопряженных градиентов требует вычисления распределенных скалярных произведений и распределенного умножения матрицы на вектор. Остальные вычисления локальны и не требуют обменов. При вычислении функционала (3.3) необходимо распределенное умножение матрицы на вектор для вычисления вектора Zk = (xs + Лтрк - /Зс)+ и для вычисления скалярного произведения 6трь Для вычисления градиента (3.4) нужна дополнительная операция умножения матрицы на вектор. С точки зрения структуры параллельного алгоритма, можно просто полагать, что решается недоопределенная линейная система с матрицей А методом наименьших квадратов, поскольку все основные трудности параллельного алгоритма возникают уже на этом этапе.
Поскольку число строк m в матрице А значительно меньше, чем число столбцов п, то при небольшом числе процессоров Пр можно использовать простую столбцовую схему разбиения данных, в которой матрица А разбивается на блочные столбцы Д примерно равного размера, как показано на рис. 3.
Таким образом, метод сопряженных градиентов для решения линейной системы (3.7) не является параллельным и его вычислительные затраты растут пропорционально числу процессоров. Обозначим через 7 отношение вычислительных затрат на решение линейной системы к оставшимся вычислительным затратам на одной итерации метода Ньютона.
Для простоты будем полагать, что m нацело делится на пр. Тогда Nr = rn/пр. Однако если хранить на каждом процессоре только соответствующую подматрицу, то при формировании обобщенной матрицы Гессе возникает необходимость обмена всех подматриц между процессорам, что означает большие коммуникационные затраты. Для избежания этих обменов на каждом процессоре матрица А хранится целиком, хотя каждый процессор г отвечает только за свою подматрицу АІ Є MNrXn. Все векторы размерности п, т.е. ж,си т.д., дублируются на каждом из процессоров. С такой схемой хранения операция умножения матрицы А на Ат становится локальной. Эта схема хранения также позволяет сократить объем коммуникационных затрат для умножения транспонированной матрицы на вектор. После умножения матрицы Aj на вектор Pi необходимо обмениваться длинными векторами (размерности п), что влечет большие коммуникационные затраты. Поэтому умножение производится не блоками, а собираются вместе все части вектора pi со всех процессоров воедино, и умножается целиком матрица Ат на вектор р. Минус этого подхода в том, что операция Атр не распараллеливается, но так как большая часть вычислений на этапе формирования системы линейных уравнений обычно приходит на построение матрицы Гессе, то эти лишние вычисления являются целесообразными для избежания больших обменов.
Для того чтобы достичь большей параллельной эффективности, можно использовать "клеточное" разбиение, в котором матрица А разбивается на прямоугольные блоки, как показано на рис. 5. Для простоты изложения предположим, что полное число процессоров можно представить в виде Пр = пг х пс, т.е. достаточно условно можно полагать, что процессоры расположены в узлах решетки размера пг хпс, при этом величина п делится нацело на пс, &т делится нацело на пг. Таким образом, п = пс х Nc и т = nr х Nr. Таким образом, матрица А состоит из подматриц Ац Є RNrXN. В этой схеме вектор х Є Кп разбивается на пс подвекторов х , а вектор р Є Rm на пг подвекторов pj, причем подвектор ХІ лежит одновременно на пг процессорах, принадлежащих j-му столбцу "решетки", так же как и все подматриц A j.
Основные распределенные операции для такого разбиения данных будут проводиться вначале в рамках процессоров одного столбца "решетки" по строчной схеме, а затем по всем процессорам одной строки, как в столбцовой схеме.
Для решения задач ЛП с большим числом переменных (порядка несколько миллионов) и большим числом ограничений (порядка несколько сотен тысяч), где критичны размерности задачи, а следовательно, и объем требуемой памяти, предлагается новая схема, наиболее экономичная по использованию памяти. Матрицы разбиваются так же, как показано на рис.4. Однако в этой схеме на каждом процессоре хранится только одна строчная подматрица АІ, а матрица Н в явном виде не хранится.
Для суммирования длинных разреженных векторов vi по всем процессорам был предложен специальный способ суммирования разреженных векторов. Это позволило в некоторой степени уменьшить коммуникационные затраты.
К сожалению, на этапе построения матрицы D требуется величина Атр, так что одного суммирования пр векторов длины п на одну итерацию метода Ньютона избежать не удается. Для оптимизации этого этапа можно использовать наложение вычислений и обменов. От "безматричного" метода трудно ожидать эффективного распараллеливания. Скорее хотелось бы, чтобы параллельная версия алгоритма не очень замедлялась "по сравнению с последовательной. Тогда паралльная реализация оказывается существенно эффективнее по сравнению с методами, использующими виртуальную память и дисковое пространство ЭВМ в случае, когда требуемая память превышает размер доступной оперативной памяти.
Решались сгенерированные случайным образом задачи ЛП с большим числом неотрицательных переменных (до нескольких десятков миллионов) и средним числом ограничений-равенств (до нескольких сотен тысяч), т.е. имело место п т.
Итак, задавались числа тип, определяющие количество строк и столбцов матрицы А, и р - плотность заполнения матрицы А ненулевыми элементами. В частности значение р = 1 означает, что случайным образом генерировались все элементы матрицы А, а значение р = 0.01 указывает, что в матрице А генерировались только 1% элементов, а остальные полагались равными нулю.
В приведенных ниже результатах расчетов считалось, что все 7г = 1 и ві = 10. Заметим, что при близких к нулю 7г величина & = (с — Лтw )i = {v d)i может также оказаться очень малой величиной. Априори неизвестная величина /? же может быть очень большой. Тогда сгенерированная задача ЛП может оказаться трудно решаемой.
Предлагаемая параллельная реализация метода решения прямой и двойственной задач ЛП, сочетающего итерационный процесс и обобщенный метод Ньютона, проделана на языке С. Для вычислений использовался вычислительный кластер МВС6000 Межведомственного суперкомпьютерного центра РАН. Численные эксперименты со случайно сгенерированными задачами ЛП показали высокую эффективность метода при решении задач ЛП с большим числом неотрицательных переменных и ограничений-равенств. Высокая эффективность этих расчетов объясняется тем, что основная вычислительная трудность предлагаемого метода приходится на решение вспомогательной задачи безусловной максимизации, которая решается обобщенным методом Ньютона. Ее размерность определяется именно количеством ограничений типа равенств, поэтому предложенные схемы параллельной реализации дают возможность решать задач большей размерности по сравнению с реализацией данного метода в системе MATLAB.
Похожие диссертации на Разработка и реализация численных методов решения оптимизационных задач большой размерности
