ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ 4
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.0.Практические результаты применения алгоритма СА-СС
для задачи раскроя...................................... 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.0бзор предложенных методов.............................. 55
2
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. Схемы разбиения данных............................... 91
3.3.1.Столбцовая схема..................................... 9]
3.3.2.Строчная схема...................................... 93
3.3.3.Клсточиая схема..................................... 95
3.3.4.Всзматричиая схема.................................. 96
3.4. Результаты численных экспериментов................... 97
ВЫВОДЫ 102
ЦИТИРОВАННАЯ ЛИТЕРАТУРА 104
3
ВВЕДЕНИЕ
Объект исследования и актуальность темы.
С развитием человечества растет и объем обрабатываемой информации, что приводит к необходимости решать оптимизационные задачи все больших размерностей. Эта тенденция особенно заметна в таких областях как биоинженерия и экономика. Для решения задач большой размерности наряду со увеличением вычислительной мощности компьютеров необходима разработка новых алгоритмов и методов, эффективно использующих вычислительные ресурсы и позволяющих получить решения для ранее нерешаемых задач.
Выло разработано множество алгоритмов и методов решения различных оптимизационных задач. Многие практические задачи характеризуются высокой размерностью, наличием трудно формализуемых ограничений, нечисловым характером части переменных. При этом как формализация, так и численное решение задач принятия решений при планировании, распределении ресурсов, оптимизации сложных процессов в различных приложениях вызывает известные трудности.
В частности, существенные затруднения связаны с высокой размерностью решаемых задач. Многие прикладные задачи экономики и управления могут быть представлены в виде задач линейного программирования (ЛП), для решения которых давно существуют численные методы и программное обеспечение, и, как могло бы показаться, не представляет никакой трудности найти оптимальное решение [1], [2]. Однако размерности современных задач порою не позволяют решить их традиционными способами, поэтому требуется разработка новых подходов решения с привлечением мощных вычислительных ресурсов. Наличие больших, более мощных и доступных мультипроцессорных компьютеров означает, что
4
параллельное программирование является важным и перспективным направлением современной вычислительной науки, которое целесообразно применять для решения задач большой размерности [3]. Большие практические задачи ЛИ часто обладают специфической блочной структурой, для учета которых разработаны различные методы декомпозиции [4]. Большие задачи ЛП, как правило, имеют неединственное решение. Различные методы решения задач ЛП (симплекс-метод, метод внутренних точек, метод квадратичной штрафной функции) дают возможность получать различные решения в случае не единственности. Так симплекс-метод дает решение, которое принадлежит вершине многогранного множества. Методы внутренней точки сходятся к решению, в котором выполнено условие строгой дополняющей исжесткости. Метод внешней квадратичной функции дает возможность найти точное нормальное решение. В данной работе предлагается новый метод нахождения проекции заданной точки ка множество решений задачи Л П.
Другие затруднения могут быть связаны с отсутствием эффективных методов решения КР-трудных задач математического программирования [5]. Это класс задач, для которых характерны такие отличительные признаки, как экспоненциальный рост вычислительной сложности. Представителями указанного класса задач являются КР-полные задачи оптимизации. 1ЧР-полные задачи обладают свойством универсальности, так как любая из !ЧтР-иолных задач может быть сведена к другой ИР-полной задачи за полиномиальное время. Это означает, что если будет найден полиномиальный алгоритм решения для одной задачи, то все КР-полные задачи будут решаться за полиномиальное время. К сожалению, попытки найти полиноминальный алгоритм на протяжении нескольких последних десятков лет, не увенчались успехом. Поэтому много исследований в настоящее время направлено на решение
5
КР-полных задач с некоторой допустимой ошибкой и за приемлемое время. К числу МР-полных задач относятся многие проектные и логистические задачи, например, синтез топологии вычислительных сетей и распределение в них трафика, раскрой материалов, компоновка оборудования, синтез расписаний производственных процессов, маршрутизация транспортных средств и др.
Нахождение глобального оптимума является общей проблемой для многих отраслей науки, техники и управления, а её решению, глобальной оптимизации, посвящен отдельный раздел прикладной математики [6]. Задачи нахождения глобального оптимума являются весьма сложными с вычислительной точки [7]. В настоящее время большинство методов поиска глобальных экстремумов относится к направленному перебору. Встречающиеся же прикладные: задачи глобальной оптимизации зачастую требуют поиска глобального минимума в пространстве достаточно большого числа переменных исследуемой функции. Примерами таких задач из области химии является поиск глобального минимума поверхности потенциальной энергии (ППЭ) ван-дер-ваальсовых комплексов [8] и предсказание третичной структуры белков [9]. •
Часто попытки решения ^-трудных задач дискретной или глобальной оптимизации большой размерности связаны с использованием тех или иных эвристических методов. В результате “решения” могут оказаться далекими от оптимальных.
В 1975г. Дж. Холландом было показано, что поиск решения оптимизационной задачи можно представить в виде эволюции группы решений [10]. Это позволило успешно моделировать процессы, происходящие в природе, для решения ХР-полных задач. В последние годы разработчики методов и программ для решения сложных проектных и оптимизационных задач все чаще обращают внимание на
О
эволюционные методы, среди которых алгоритм муравьиной колонии, алгоритм моделирования отжига и генетические алгоритмы.
Генетический алгоритм (ГА) представляет собой технику оптимизации, которая моделирует феномен естественной эволюции (впервые открытой Ч. Дарвином) [11]. При естественной эволюции выживают и дают самое многочисленное потомство особи, наиболее адаптированные к сложным условиям окружающей среды. Степень адаптации, в свою очередь, зависит от набора хромосом конкретной особи, полученного от родителей. Это основа выживания сильнейшего -не только процесс выживания, но и участие в формировании следующего поколения. В природе выживание является определяющей и основной функцией. Генетический алгоритм не пытается оптимизировать единственное начальное решение. Он работает с группой начальных решений, которые кодируются, подобно хромосомам. Отдельные гены хромосомы представляют собой уникальные переменные для изучаемой проблемы. На каждом шаге генетического алгоритма присутствует набор объектов - особей, обладающих “генетической информацией”, или ‘хромосом”. Для нар особей определяются правила скрещивания, согласно которым, при переходе на следующий шаг алгоритма, производится потомство на основе “генетической информации” родителей. Из этого потомства при помощи критерия приспособленности выбираются особи, которые войдут в следующее поколение. При отборе “здоровых” хромосом из популяции и использовании генетических операторов (таких как рекомбинирование и мутация) в популяции остаются только те хромосомы, которые лучше всех приспособлены к окружающей среде, т.е. наиболее полно отвечают задаче. Особи могут также подвергаться случайным мутациям, в результате которых наследственная информация подвергается изменениям.
Использовавшиеся для моделирования биологической эволюции
генетические алгоритмы были обобщены для использования в глобальной оптимизации [12]. В этом случае - “генетическая информация” - это точка в пространстве аргументов, а “приспособленность” - значение целевой функции. Правила скрещивания и мутации выбираются в зависимости от строения множества, на котором определена целевая функция.
К достоинствам генетических алгоритмов относится простота принципов и использование исследуемой функции как “черного ящика”, о свойствах которой может быть ничего не известно до начала оптимизации. Однако существенным недостатком является большая специфичность правил скрещивания и мутации но отношению к исследуемой функции. В рамках использования генетических алгоритмов в каждой новой задаче исследователь вынужден вновь формулировать новые правила скрещивания и мутации. Тем не менее, генетические алгоритмы являются достаточно мощным средством решения задач глобальной оптимизации, поскольку их недостатки зачастую оборачиваются их достоинствами. Во-первых, “потомки” всегда несколько похожи на “родителей”, за счёт чего процедура позволяет быстро выделить фрагменты генетической информации, отвечающие наилучшей приспособленности и использовать их на следующих шагах алгоритма. Во вторых, правила мутации и скрещивания могут быть подобраны таким образом, что используют особенности задачи при минимизации. И наконец, программы с использованием генетических алгоритмов реже требуют перепроверки результатов и повторного запуска, чем программы с использование моделирования отжига. Но наибольшее преимущество генетические алгоритмы имеют при глобальной оптимизации функции дискретных переменных, когда применение других подходов затруднено.
В связи с интенсификацией производства в настоящее время вопросы
8
оптимизации планирования и управления производства на предприятиях очень актуальны. Перспективным направлением работ по повышению эффективности функционирования автоматизированных систем управления является разработка и реализация программных систем, позволяющих решать совокупность взаимосвязанных оптимизационных задач планирования производства. Построение оптимальных карт раскроя ресурсного материала является одной из самых трудоемких задач на заготовительной стадии производства. В то же время это одна из самых важных задач в ресурсосберегающих технологиях, поскольку напрямую ведет к экономии материала и снижению отходов. Начало теоретическим исследованиям в области методов рационального раскроя положили труды академика Л. В. Канторовича [13, 14], в которых он показал возможность эффективного решения оптимизационных задач с помощью ЭВМ. В своих работ Канторовича Л. В. впервые представил задачу раскроя одинаковых листов материала в виде задачи целочисленного линейного программирования, в которой матрица ограничений задана неявно. Эта модель стала основой для многих методов решений. На протяжении последних 70 лет исследованиям в области раскроя и разработки новых алгоритмов укладки плоских заготовок было посвящено множество отечественных и зарубежных работ [15] - [53]. Однако задача раскроя на заводах, где в качестве исходных ресурсов используют материалы различных типоразмеров, порождает очень большую матрицу ограничений, а вместе с тем и огромное количество переменных, что часто не позволяет использовать классические оптимизационные методы. В работе [54] показано, что построение эвристических алгоритмов для решения задачи раскроя материалов различных размеров необходимо, так как точные подходы не пригодны в этом случае. Разработка нового метода решения конкретной практической задачи с учетом ее специфики позволит получить
9
I
- Київ+380960830922