Содержание к диссертации
Введение
ГЛАВА 1. Математические модели оптимизационных задач и методы их решения
1.1 Прикладные задачи производственно-транспортного
планирования как объект математического моделирования 9
1.2 Основные виды многоэкстремальной оптимизации 12
1.3 Математические модели и классические методы решения транспортной и распределительной задач 13
1.4 Модели процессов оптимизации в природе 24
1.5 Исследование методов генетического поиска 29
1.6 Выводы 43
ГЛАВА 2. Разработка эффективного генетического метода решения нелинейной транспортной задачи 45
2.1 Математическая модель и кодировка решения 45
2.2 Моделирование начальной популяции 45
2.3 Функция оценки годности 47
2.4 Моделирование процессов кроссинговера и мутации 48
2.5 Формирование репродукционной группы и моделирование естественного отбора 54
2.6 Общая структура разработанного метода решения нелинейной транспортной задачи и его свойства 56
2.7 Применение моделирования макроэволюции для повышения качества решения 60
2.8 Выводы 65
ГЛАВА 3. Разработка эффективного генетического метода решения нелинейной распределительной задачи 66
3.1 Математическая модель и кодировка решения 66
3.2 Моделирование начальной популяции 68
3.3 Функция оценки годности 70
3.4 Обоснование применения оператора кроссинговера 70
3.5 Моделирование процесса мутации 73
3.6 Общая структура разработанного метода решения нелинейной распределительной задачи и его свойства 74
3.7 Модифицированный ГА с усложненной структурой 77
3.8 Выводы 80
ГЛАВА 4. Обоснование и тестирование разработанных методов 81
4.1 Цели экспериментального исследования 81
4.2 Исследование эффективности алгоритмов с использованием математического моделирования и вычислительного эксперимента . 82
4.3 Применение разработанных методов и комплекса проблемно-ориентированных программ для решения прикладных задач 105
4.4 Выводы 109
Заключение 110
Библиографический список 112
- Математические модели и классические методы решения транспортной и распределительной задач
- Общая структура разработанного метода решения нелинейной транспортной задачи и его свойства
- Общая структура разработанного метода решения нелинейной распределительной задачи и его свойства
- Применение разработанных методов и комплекса проблемно-ориентированных программ для решения прикладных задач
Введение к работе
Актуальность темы. Среди приложений математического программирования существует ряд специальных задач, встречающихся на практике чаще других. К ним относятся задачи транспортного типа, возникающие там, где необходимо составить оптимальный план перевозки груза от поставщиков к потребителям, общее число которых, как правило, велико (порядка нескольких сотен). При этом целевой функцией является стоимость затрат на транспортировку груза.
Рациональное планирование транспортного технологического процесса невозможно без использования математических методов и компьютерной техники, а возникающие при этом вычислительные сложности обусловлены большим количеством переменных (большой размерностью) задач и многоэкстремальностью целевой функции. В связи с этим использование классических методов математического программирования с экспоненциальной вычислительной сложностью становится неэффективным из-за необходимости обработки очень больших объемов информации.
Таким образом для решения данной проблемы необходимо создать новые, более эффективные методы решения нелинейных задач транспортного типа с использованием современных подходов, основанных на генетических представлениях изучаемых процессов.
Цели и задачи исследования. Основной целью работы является повышение эффективности решения нелинейных транспортных задач с использованием идеологии эволюционного моделирования. Для достижения поставленной цели необходимо:
исследовать математические модели, адекватно отражающие сущность нелинейных задач транспортного типа, и известные методы решения этих задач с учетом особенностей целевых функций;
изучить возможности генетических методов и разработать системный подход к решению нелинейных задач транспортного типа с
5 использованием модифицированных и вновь созданных генетических операторов;
исследовать механизмы генетического поиска оптимальных вариантов
транспортировки, установить наиболее эффективные параметры
процесса, экспериментально обосновать стратегию получения
заданного результата.
Методы исследования. В работе использованы математические методы, в том числе: теория множеств, теория графов, теория алгоритмов, методы оптимизации, методология эволюционного моделирования и генетических алгоритмов, компьютерное моделирование.
Научная новизна
Разработаны генетические методы решения нелинейных транспортных и распределительных задач с вогнутыми функциями стоимости;
Построен новый генетический оператор кроссинговера, ориентированный на специфику нелинейных транспортной и распределительной задач;
Разработана генетическая процедура инициализации начальной популяции для распределительной задачи, основанная на методе последовательного насыщения строк и столбцов;
Усовершенствован известный оператор мутации с учетом нелинейности решаемых задач.
Практическая значимость диссертационной работы состоит в следующем: построена математическая модель прикладной задачи оптимизации межцеховых перевозок на промышленном предприятии с разветвленной сетью внутризаводских грузопотоков; на основе разработанных методов создан комплекс проблемно-ориентированных программ, позволяющий решать нелинейные прикладные задачи.
Реализация результатов работы. Разработанные алгоритмы использованы при выполнении федеральных госбюджетных научно-исследовательских работ в Ростовской-на-Дону государственной академии
сельскохозяйственного машиностроения (РГАСХМ): «Теоретические основы эволюционного моделирования генетических алгоритмов», «Основы вычислительного представления генетических алгоритмов для решения оптимизационных задач», «Развитие эволюционного моделирования для решения оптимизационных задач» и «Теория поисковой адаптации для решения избранных комбинаторных задач оптимизации». Результаты диссертационной работы использованы при оптимизации межцеховых перевозок в ООО «Ростовский литейный завод». Материалы диссертации используются в учебном процессе на кафедре прикладной математики и вычислительной техники РГАСХМ при проведении лекционных и практических занятий по курсам «Основы САПР» и «Программные средства САПР». Акты об использовании результатов работы приведены в приложениях к диссертации.
Апробация работы. Основные научные и практические результаты докладывались и обсуждались на международной научно-технической конференции "Интеллектуальные САПР" (ТРТУ, Таганрог-Гурзуф, 1997), на IV всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (ТРТУ, Таганрог, 1998), на региональной конференции "Информатизация, автоматизация и роботизация в машиностроении" (РГАСХМ, Ростов-на-Дону, 1999), на международной научно-технической конференции "Проблемы совершенствования зерноуборочной техники: конструирование, организация производства, эксплуатация и ремонт" (РГАСХМ, Ростов-на-Дону, 1999), на международной научно-технической конференции «Интеграция отраслевой и вузовской науки: проблемы современного машиностроения» (РГАСХМ, Ростов-на-Дону, 2000), на региональной научно-технической конференции «Интеграция отраслевой и вузовской науки: проблемы современного машиностроения» (РГАСХМ, Ростов-на-Дону, 2002, 2003), на студенческой научной конференции Ростовского государственного педагогического университета (РГПУ, Ростов-на-Дону,
7 2003), на XVI международной научной конференции «Математические методы в технике и технологиях» (С.-ПбГТУ, Санкт-Петербург, 2003), на XXX юбилейной международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе (IT+SE'2003)» (Украина, Ялта-Гурзуф, 2003), на VI международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (МГАПИ, Москва, 2003).
Публикации. Результаты диссертации отражены в 9 печатных работах.
Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 101 наименования и двух приложений. Содержание диссертационной работы изложено на 120 страницах, в том числе 15 рисунков, 11 таблиц.
Во введении обоснована актуальность диссертационной работы, сформулирована цель работы, приведены сведения о научной новизне и практической значимости, апробации диссертационной работы, дано краткое содержание основных разделов диссертации.
В первой главе описаны математические модели нелинейных транспортных и распределительных задач с вогнутыми функциями стоимости. Дан краткий анализ существующих методов решения нелинейных транспортной и распределительной задач. Изучены процессы эволюции в живой природе, представляющие интерес в аспекте генетических алгоритмов. Проведено теоретическое исследование существующих генетических операторов и схем селекции с целью изучения возможности их применения в разрабатываемых алгоритмах решения транспортной и распределительной задач.
Во второй главе представлен разработанный генетический алгоритм решения нелинейной транспортной задачи. Описаны способ кодирования решения и процедура инициализации начальной популяции. Разработан новый оператор кроссинговера, модернизирован известный оператор
8 мутации, а также описан оператор кроссинговера, впервые использованный для решения нелинейной транспортной задачи с вогнутой функцией стоимости. Приведена оценка быстродействия разработанного алгоритма. Предложен модифицированный генетический алгоритм решения задачи, в котором использованы идеи моделирования макроэволюции.
В третьей главе разработана математическая модель задачи оптимизации межцеховых перевозок на предприятии с разветвленной сетью внутризаводских грузопотоков, являющаяся распределительной задачей. Предложен генетический алгоритм решения нелинейной распределительной задачи. Разработана процедура инициализации начальной популяции, ориентированная на специфику решаемой задачи. Приведена оценка быстродействия алгоритма.
В четвертой главе сформулированы цели экспериментального исследования. Проведено тестирование разработанных методов с использованием математического моделирования и вычислительного эксперимента. Обосновано применение данных методов и комплекса проблемно-ориентированных программ для решения прикладных задач.
Математические модели и классические методы решения транспортной и распределительной задач
Рассмотренная выше задача минимизации вогнутой целевой функции на транспортных многогранниках различных типов является нелинейной и многоэкстремальной. Задачи минимизации вогнутой функции на выпуклом множестве относятся к классу задач математического программирования, для которых время нахождения точного решения растет не менее чем экспоненциально с ростом числа переменных. Это следует из того, что даже простейшие из задач этого класса относятся к числу iVP-полных задач [1]. Но, несмотря на столь обескураживающие факты, большая практическая значимость вышеперечисленных задач диктует нам необходимость поиска новых, нестандартных подходов к их решению.
В случае, когда функция многоэкстремальна, проблема отыскания глобального минимума очень сложна. Если функция f(x) вогнутая, то большинство методов, как правило, сходится к произвольной точке локального минимума. Важно подчеркнуть, что при этом ни один метод не дает гарантии попадания в глобальный минимум. Все методы многоэкстремальной оптимизации можно разделить на две группы: точные и эвристические. Для первых существуют какие-либо точные утверждения об их сходимости к глобальному минимуму (хотя сама по себе теорема о сходимости отнюдь не гарантирует работоспособности метода), для вторых приходится ограничиваться некоторыми правдоподобными рассуждениями. Отдельной категорией среди эвристических методов выделяются стохастические методы, использующие случайный поиск.
К точным методам относятся метод ветвей и границ, метод неявного перебора и др. В этих методах делается попытка максимального сокращения объема перебора за счет мощных приемов построения оценок, позволяющих опознать бесперспективные частичные решения, в результате чего от дерева поиска на одном шаге отсекается целая ветвь. Эти алгоритмы весьма просты для понимания, легко программируются на ЭВМ, обладают простой математической структурой. К сожалению, они имеют существенный недостаток - экспоненциальную временную сложность. Существуют и другие точные методы решения NP-полных задач, но все они имеют низкую эффективность.
Эффективные алгоритмы - такие, у которых трудоемкость и память являются степенными функциями от размерности задачи (исходных данных). Неэффективный алгоритм состоит в переборе всевозможных вариантов, число которых экспоненциально относительно размерности задачи. Особую актуальность имеют эффективные приближенные методы. Эти подходы включают прием, который можно назвать "снижение требований". Он заключается в отказе от поиска оптимального решения и в нахождении вместо этого хорошего решения за приемлемое время. Приближенные алгоритмы дают "почти оптимальное" решение "почти всегда".
Для большинства практических задач достаточно получить хорошее приближенное решение за приемлемое время. Методы, применяемые для построения алгоритмов такого типа, сильно зависят от специфики задачи.
Перспективным направлением в поиске приближенных эффективных методов для решения NP-полных задач является генетический подход. В нем применяются случайные правила поиска, что позволяет избежать локальные "ловушки" [4-16].Транспортная задача в силу своей актуальности всегда вызывала к себе повышенный интерес. Ниже приведена ее классическая постановка [17-24].
Имеется п пунктов производства и т пунктов потребления однородного продукта. Для каждого пункта производства і задан объем производства а[і] 0, а для каждого пункта потребления j - объем потребления e[j] 0. Стоимость перевозки количества продукта х из / в j равна c[iJJ x. Матрица С[А,В] задана. Требуется составить план перевозки продукта в котором все пункты потребления были бы обеспечены необходимым количеством продукта, ни из какого пункта производства не вывозилось бы продуктов больше, чем там производится, а стоимость перевозки была бы минимальной.
Однако далеко не всегда удается иметь дело с такой простой постановкой задачи. Функция стоимости перевозки может быть линейной, выпуклой или вогнутой функцией от х (количества перевозимого продукта). В этом случае говорят о нелинейной транспортной (распределительной) задаче [25-34]. Если функция стоимости выпуклая, то ее возможно аппроксимировать кусочно-линейными функциями, так как в выпуклых и линейных задачах локальный минимум является также и глобальным. Поэтому способы и процедуры, позволяющие обнаружить локальный минимум, пригодны и для выделения глобального минимума. Среди решений вогнутой задачи может быть много локальных минимумов. В процессе поиска решения вогнутой задачи следует каким-либо образом просматривать и сравнивать все локальные минимумы, чтобы выбрать среди них глобальный (Рис. 1.2.). Организация процедуры поиска и сравнения всех локальных минимумов представляет собой очень сложную вычислительную проблему, относящуюся к классу NP-полных задач. Трудоемкость всех существующих алгоритмов решения отдельных NP-полных задач можно оценить экспоненциальными функциями, а это значит, что вычислительные затраты возрастают, как о(ехр(п)) [4].
Математическая модель нелинейной транспортной задачи следующая: где Cj/Xjj) - линейная, выпуклая или вогнутая ценовая функция. Математическая модель нелинейной распределительной задачи записывается аналогично. Существует много алгоритмов решения данных задач [4, 35-59]. Рассмотрим некоторые из них.
Общая структура разработанного метода решения нелинейной транспортной задачи и его свойства
Необходимость в создании макроэволюционного процесса объясняется тем, что после некоторого числа поколений хромосомы в отдельной популяции становятся очень похожими, разнообразие генетического материала теряется и дальнейшее развитие популяции может быть неэффективным. Одним и способов преодоления этой проблемы является независимая обработка отдельных популяций. Так как ГА включают в себя элементы случайного поиска, независимая эволюция отдельных популяций будет направлять процесс в различные области пространства решений. Это связано с тем, что в каждой популяции генетические операторы работают по-разному, что определяется различными процессами: выбором особей для кроссинговера, мутации, а также с различием начального генетического материала в популяциях. По этим причинам, в каждой популяции получают свои субоптимальные решения, отличающиеся по своей структуре. Комбинирование этих решений из разных популяций приводит к улучшению окончательного решения.
Число взаимодействий между субпопуляциями является очень важным фактором эффективности ГА. При наличии большого числа взаимодействий преимущества использования субпопуляций оказываются потерянными, так как хорошие хромосомы из одной субпопуляции, и эволюция недолго остается независимой. Простейший случай коммуникации - миграция по одному индивиду из субпопуляции каждое поколение сводит макроэволюцию к действию простого последовательного ГА. Создавая эффект расстояния по аналогии с естественными процессами, можно понижать норму взаимодействия некоторых субпопуляций с той целью, чтобы они, как более изолированные, могли бы создать уникальные хромосомы. Необходимо найти такое количество поколений, после которого коммуникация была бы эффективной. Коммуникацию имеет смысл осуществлять, когда в какой-либо субпопуляции не наблюдается прогресса. Этот момент можно определить по такому критерию: если сумма отклонений фитнесса за последние несколько итераций не превосходит некоторого заданного положительного числа є, то субпопуляция пришла в тупик.
На основе анализа математической модели нелинейной транспортной задачи предложено использование способа кодирования решения в виде матрицы, а не в виде двоичного вектора, как это принято в теории моделирования эволюции. 2. Впервые для нелинейных задач использованы алгоритм инициализации начальной популяции Start 1, а также оператор кроссинговера Cross 7, генерирующие решения, удовлетворяющие начальным условиям. 3. Разработан оператор кроссинговера Cross 2, производящий легальные (допустимые) решения, имеющий вычислительную сложность 0(п). Усовершенствован оператор мутации Mutation 1, отличающийся от известного тем, что точки мутации определяются не случайно, а с использованием знаний о целевой функции. Определена моделирующая функция (функция оценки годности) полученных решений. 4. Приведено теоретическое обоснование выбора схемы селекции особей для кроссинговера, а также анализ схем формирования репродукционной группы и стратегии отбора индивидов для формирования новой популяции. 5. Проведено исследование эффективности разработанного генетического метода и сравнение с классическими методами. Разработанный алгоритм имеет вычислительную сложность 0(п2), может решать задачи с вогнутыми функциями стоимости и дает улучшение по качеству на 3-6%. 6. Обосновано применение моделирования макроэволюции для повышения качества решений задачи. Приведена общая схема модифицированного ГА с усложненной структурой, связанной с распараллеливанием ГА, структурированием популяции, миграцией хромосом. Решается нелинейная распределительная задача следующего вида: ху 0, і = 1,и, j = l,m, где с(х) - линейная, выпуклая или вогнутая ценовая функция. Подобного рода задачи зачастую возникают перед экономистами при решении проблем производственно-транспортного планирования, например, при оптимизации транспортных межцеховых перевозок крупных предприятий с разветвленной сетью внутризаводских грузопотоков [28]. На основе анализа существующего технологического цикла автотранспортных перевозок предприятия возможно повысить эффективность работы автотранспорта, предназначенного для межцеховых перевозок за счет снижения стоимости перевозки 1 т. груза, уменьшения количества автотранспорта и т.д.
Общая структура разработанного метода решения нелинейной распределительной задачи и его свойства
Проведение экспериментальных исследований включало в себя три основных этапа: Исследование механизмов генетического поиска разработанных алгоритмов, которое заключалось в определении оптимальных управляющих параметров, таких как тип скрещивания особей, тип кроссинговера, вероятности кроссинговера и мутации, способы отбора особей и т.д. на качество получаемого решения и быстродействие алгоритма. Исследование эффективности предложенных алгоритмов, которое заключалось в определении их вычислительной сложности и сравнении полученных результатов с оптимальными и с результатами, полученными другими алгоритмами.
Применение разработанного генетического алгоритма для решения прикладной нелинейной распределительной задачи, возникшей при оптимизации межцеховых (внутризаводских) перевозок ООО «Ростовский литейный завод».
Для разработанных алгоритмов создан пакет программ на языке программирования Borland Pascal 7.0. Программное обеспечение для каждого ГА расположено в четырех файлах (основная программа ГА; инициализация (входные данные); моделирующая функция; генетические операторы). В первом файле определяется максимальный размер популяции и максимальный размер индивидуальности. Определяется размер популяции, вероятность применения ГО. Сюда включены методы селекции, отбора, сортировки. Во втором файле содержатся входные данные, процедура инициализации. В третьем описана процедура вычисления МФ. В четвертом файле описываются все процедуры для реализации ГО.
Основной целью исследований является выявление зависимостей и влияния на качество решения различных комбинаций управляющих параметров и структур генетического поиска. Для проведения исследований были подобраны тестовые примеры различной размерности. Рассмотрим поставку зерна п фермерскими хозяйствами на т элеваторов. Требуется составить план перевозки зерна, в котором все элеваторы были бы обеспечены необходимым количеством продукта, ни из какого фермерского хозяйства не вывозилось бы зерна больше, чем там производится, а стоимость перевозки была бы минимальной. При этом используется функция стоимости с фиксированными доплатами Су(ху)=а+Ьху. Решим данную нелинейную транспортную задачу с помощью разработанного алгоритма. Пример 1. п=3, т=4. Пример 2. п=4, т=5. Пример 3. п=5, т=8. Пример 4. п=8, т=10. Пример 5. п—10, т=20.
Исследования были направлены на то, чтобы определить наилучшие значения параметров рм и рк, наиболее приемлемый размер популяции Р, оптимальное значение констант сі и с2 в Crossl, наиболее предпочтительный тип селекции. Для каждого эксперимента зафиксируем номер генерации, после которой не наблюдается улучшения оценки. В таблицах отражены минимальное и максимальное число генераций, а также рассчитано среднее число генераций. Одновременно фиксируется число экспериментов, в которых было получено оптимальное решение; число экспериментов, в которых решение отличалось от оптимального менее, чем на 10% и число экспериментов, в которых решение отличалось от оптимального более, чем на 10%. Для каждой структуры сначала зафиксируем параметр рм и будем изменять параметр рк. Проведем серию из 10 экспериментов для каждого фиксированного набора параметров. Пусть рм =0.2.
Применение разработанных методов и комплекса проблемно-ориентированных программ для решения прикладных задач
Во время экспериментальных исследований для распределительной и транспортной задачи необходимо установить зависимость времени решения от размерности задачи. Эта зависимость относится к «парным» зависимостям типа y=f(x). Процедура линейного регрессионного анализа заключается в определении линии регрессии таким образом, чтобы сумма квадратов отклонений вдоль оси случайной величины (OY) от проведенной линии y=f(x) была минимальной [93-100].
Таким образом, задача регрессионного анализа сводится, в случае линейной регрессии к определению коэффициентов do, ai уравнения (4.1), а в случае нелинейной регрессии, к определению коэффициентов ао, а], ...ар уравнения (4.2). Методики определения этих коэффициентов для линейной и нелинейной регрессии различны. Обычно делается визуальная оценка характера зависимости, после которой выбирается та или иная методика расчетов. Существует два основных метода определения полинома нелинейной зависимости: метод наименьших квадратов и аппроксимация ортогональными полиномами Чебышева. При использовании метода наименьших квадратов недостатком является то, что в случае увеличения степени полинома возникает необходимость перерасчета ранее вычисленных коэффициентов. При применении метода Чебышева аппроксимирующий многочлен строится в виде суммы повышающихся степеней, причем добавление новых слагаемых не изменяет вычисленных ранее коэффициентов. Поэтому при проведении регрессионного анализа будет использоваться метод Чебышева. Рассмотрим построение парной нелинейной зависимости по методу Чебышева. Пусть даны два столбца, содержащие п значений двух параметров х и у. Требуется построить нелинейный полином степени m с числом неизвестных коэффициентов т+1. Сущность способа Чебышева состоит в том, что аппроксимирующий полином отыскивают в виде комбинации многочленов, которые выбирают специальным образом. Можно записать искомый многочлен в виде:
После построения полинома заданной степени делается проверка значимости уравнения регрессии. Для этого вычисляются значения общей и остаточной дисперсии. Общая дисперсия s2 рассчитывается по формуле: где п - число наблюдений, у( — значение выходного параметра і-того испытания, у - среднее арифметическое выходного параметра. Остаточная дисперсия s2y ост определяется по формуле: где у - значение выходного параметра, вычисленное по построенному уравнению регрессии. Затем вычисляется критерий Фишера по формуле: Критерий Фишера показывает, во сколько раз уравнение регрессии предсказывает результаты опытов лучше, чем среднее арифметическое от yt. Считается, что уравнение регрессии предсказывает результаты опытов лучше среднего, если F достигает или превышает границу значимости F при выбранном уровне значимости (обычно принимают e-l-q=5%). Значение F определяется по таблице F-распределения Фишера для параметров V/ и v , определяемых по формулам:
Проведение полного факторного эксперимента затруднительно из-за больших временных затрат на его проведение. Поэтому рационально провести сокращенную серию экспериментов с последующим применением регрессионного анализа для определения уравнения кривых. При проведении экспериментальных исследований для того, чтобы составленная на основании наблюдения частичная совокупность отражала свойства общей совокупности, необходимо брать каждую единицу наудачу. После проведения экспериментов необходимо для каждой их серии оценить, какому закону распределения подчиняются полученные данные. Для этой цели строится гистограмма частот распределения.
Для построения гистограммы данные в полученной выборке необходимо сгруппировать в разряды, то есть разбить ряд случайных величин на интервалы. Разбиение на интервалы включает определение числа интервалов и размеров интервалов. Для определения количества интервалов используется правило Штюргеса:
где утах — максимальное значение случайной величины; утЫ — минимальное значение случайной величины. После построения гистограммы необходимо перейти к этапу подбора подходящего для данного случая наиболее приемлемого теоретического закона распределения вероятностей. Визуальное сравнение с кривыми теоретических распределений позволяет предположить, какую гипотезу можно принять в данном случае. Затем применяется метод, использующий размах варьирования R.
