автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математические модели и генетические методы решения нелинейных задач транспортного типа

на правах рукописи

Басова Алина Викторовна

Математические модели и генетические методы решения нелинейных задач транспортного типа

Специальности 05.13.18 - Математическое моделирование, численные

методы и комплексы программ 05.13.17 - Теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата технических наук

Ростов-на-Дону - 2004

Работа выполнена на кафедре прикладной математики и вычислительной техники государственного образовательного учреждения Ростовская-на-Дону государственная академия сельскохозяйственного машиностроения.

Научные руководители: заслуженный деятель науки РФ,

доктор технических наук, профессор Чернышев Ю.О.; кандидат технических наук, доцент Бураков В.А.

Официальные оппоненты: доктор технических наук,

профессор Жак СВ.; кандидат технических наук, доцент Родзин СИ.

Ведущая организация: Ростовский государственный университет

путей сообщения

Защита состоится 2004 года в часов на

заседании диссертационного совета Д 212.259.03 при Таганрогском государственном радиотехническом университете по адресу: 347928, г. Таганрог, ГСП-17 А, пер. Некрасовский, 44.

С диссертацией можно ознакомиться в библиотеке Таганрогского государственного радиотехнического университета.

Автореферат разослан

2004 г.

Ученый секретарь диссертационного совета

д-р техн. наук, проф. Целых А.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Среди приложений математического программирования существует ряд специальных задач, встречающихся на практике чаще других. К ним относятся задачи транспортного типа, возникающие там, где необходимо составить оптимальный план перевозки груза от поставщиков к потребителям, общее число которых, как правило, велико (порядка нескольких сотен). При этом целевой функцией является стоимость затрат на транспортировку груза.

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

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

Цели и задачи исследования. Основной целью работы является повышение эффективности решения нелинейных транспортных задач с использованием идеологии эволюционного моделирования. Для достижения поставленной цели необходимо:

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

• изучить возможности генетических методов и разработать системный подход к решению нелинейных задач транспортного типа с использованием модифицированных и вновь созданных генетических операторов;

• исследовать механизмы генетического поиска оптимальных вариантов транспортировки, установить наиболее эффективные параметры процесса, экспериментально обосновать стратегию получения заданного результата.

Методы исследования. В работе использованы математические методы, в том числе: теория множеств, теория графов, теория алгоритмов, методы оптимизации, методология эволюционного моделирования и генетических алгоритмов, компьютерное моделирование. Научная новизна

• Разработаны генетические методы решения нелинейных транспортных и распределительных задач с вогнутыми функциями стоимости;

• Построен новый генетический оператор кроссинговера, ориентированный на специфику нелинейных транспортной и распределительной задач;

• Разработана генетическая процедура инициализации начальной популяции для распределительной задачи, основанная на методе последовательного насыщения строк и столбцов;

• Усовершенствован известный оператор мутации с учетом нелинейности решаемых задач.

Практическая значимость диссертационной работы состоит в следующем: построена математическая модель прикладной задачи оптимизации межцеховых перевозок на промышленном предприятии с разветвленной сетью внутризаводских грузопотоков; на основе разработанных методов генетического поиска создан комплекс проблемно-ориентированных программ, позволяющий решать нелинейные прикладные задачи.

Реализация результатов работы. Разработанные алгоритмы использованы при выполнении федеральных госбюджетных научно-исследовательских работ в Ростовской-на-Дону государственной академии сельскохозяйственного машиностроения (РГАСХМ): «Теоретические основы эволюционного моделирования генетических алгоритмов», «Основы вычислительного представления генетических алгоритмов для решения оптимизационных задач», «Развитие эволюционного моделирования для решения оптимизационных задач» и «Теория поисковой адаптации для решения избранных комбинаторных задач оптимизации». Результаты диссертационной работы использованы при оптимизации межцеховых перевозок в ООО «Ростовский литейный завод». Материалы диссертации используются в учебном процессе на кафедре прикладной математики и вычислительной техники РГАСХМ при проведении лекционных и практических занятий по курсам «Основы САПР» и «Программные средства САПР». Акты об использовании результатов работы приведены в приложениях к диссертации.

Апробация работы. Основные научные и практические результаты докладывались и обсуждались на международной научно-технической конференции "Интеллектуальные САПР" (ТРТУ, Таганрог-Гурзуф, 1997), на IV всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (ТРТУ, Таганрог, 1998), на региональной конференции "Информатизация, автоматизация и роботизация в машиностроении" (РГАСХМ, Ростов-на-Дону, 1999), на международной научно-технической конференции "Проблемы совершенствования зерноуборочной техники: конструирование, организация производства, эксплуатация и ремонт" (РГАСХМ, Ростов-на-Дону, 1999), на международной научно-технической конференции «Интеграция отраслевой и вузовской науки: проблемы современного машиностроения» (PГACXM, Ростов-на-Дону, 2000), на региональной научно-технической конференции «Интеграция отраслевой и вузовской

науки: проблемы современного машиностроения» (РГАСХМ, Ростов-на-Дону, 2002, 2003), на студенческой научной конференции Ростовского государственного педагогического университета (РГПУ, Ростов-на-Дону, 2003), на XVI международной научной конференции «Математические методы в технике и технологиях» (С -ПбГТУ, Санкт-Петербург, 2003), на XXX юбилейной международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе (IT+SE'2003)» (Украина, Ялта-Гурзуф, 2003), на VI международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (МГАПИ, Москва, 2003).

Публикации. Результаты диссертации отражены в 9 печатных работах.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 101 наименования и двух приложений Содержание диссертационной работы изложено на 120 страницах, в том числе 15 рисунков, 11 таблиц

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

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

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

На практике вогнутость целевой функции связана прежде всего с так называемым законом экономии от масштаба, в соответствии с которым удельные затраты на транспортировку продукции убывают с ростом объемов перевозок. Это объясняется тем, что при перевозках больших партий некоторого груза можно получить определенную скидку с номинальной цены. При этом целевая функция имеет вид у =Аха, где А- константа, а а<1.

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

б

о,

если х = О

у(*) =

, где

+■ А2 * х, если х > О

Н1 - фиксированные затраты (денежные вложения на строительство склада); h2 - стоимость текущих затрат

Возникающие при планировании транспортного процесса задачи в общем виде формулируются таким образом:

Имеется п пунктов производства и т пунктов потребления однородного продукта. Для каждого пункта производства I задан объем производства агУО, а для каждого пункта потребления] - объем потребления в]>0. Стоимость перевозки может быть фиксированной, но на практике чаще всего это линейная, выпуклая или вогнутая функция от х, то есть количества перевозимого продукта. Требуется составить такой план перевозки, в котором все пункты потребления были бы обеспечены необходимым количеством продукта, в то же время ни из какого пункта производства не вывозилось бы продуктов больше, чем там производится, а стоимость перевозки была бы минимальной,

, где

с(х) - линейная, выпуклая или вогнутая функция стоимости. При этом условия записываются в виде:

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

При решении подобных задач применялись разные методы, отраженные в работах Йенсена и Барнеса, Хоанга Туя, С. С. Лебедева, Л.П. Падалко, С.Л. Уткина, В.М. Монтлевича, В.Р. Хачатурова. Проведенный анализ перечисленных методов показывает, что их использование не всегда эффективно и связано с высокой вычислительной сложностью,

1*1

я» _

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

Таким образом, возникает необходимость создания новых перспективных методов, основанных на современных подходах, использующих идеи моделирования эволюции.

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

Решение задачи в генетических алгоритмах представляется в виде закодированных хромосом. Для нелинейной вогнутой транспортной задачи целесообразно использовать представление в виде матрицы:

где х - количество продукта, перевозимого из пункта

производства i в пункт потребления у.

Каждая матрица решения X должна удовлетворять ограничениям:

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

В созданном алгоритме формирование стартовой популяции решений - {х°,х°, - >х1\ осуществляется с помощью идеи последовательного насыщения строк и столбцов, используемой в методе северо-западного угла и других методах.

Пусть заданы аа2....,ап - объемы производства и Ъи ¿г, ..., Ът - объемы потребления. Пусть множество Е состоит из элементов {1,2,. .,п}, а множество F - из элементов {1,2,.. ,т}.

Схема процедуры формирования начальной популяции представлена на

рис.1.

Рис.1. Схема процедуры формирования начальной популяции для транспортной

задачи.

Функция оценки годности (фитнесс) для нелинейной транспортной задачи запишется как

я т

F - Z)ZC»(X,) , где с(х) - функция стоимости.

i.ly-1

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

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

В данной работе впервые для нелинейных задач используются оператор кроссинговера Cross 1, модифицированный оператор мутации Mutation 1, a

также разработанный оператор кроссинговера Cross 2. Эти операторы генерируют решения, принадлежащие множеству допустимых решений задачи. Cross 1

Пусть две матрицы Xl=(x\j)nm и X2~(xt)n^ селектированы для скрещивания. Установим две вспомогательные матрицы А и В, которые определяются следующим образом:

a,j'z(x!¡j+x2,J/2; bl]=(xiч+х2t])mod 2, i = l,n, j = 1,m

Матрица А содержит среднее число значений обоих родителей, матрица В содержит нули и единицы. Матрица В имеет интересное свойство: число единиц в каждой строке и в каждом столбце четно. Следовательно, суммы a(i) элементов строк и суммы b(j) элементов столбцов являются четными числами. Трансформируем матрицу В в две матрицы В1 и В2, такие, что

В=В1+В2 ^ ,2г ei 7"

Тогда произведем потомков по формуле:

ХГ=А+В1, Х2 '=А+В2

Cross 2.

Пусть матрицы Х[,Х2, ...Хр селектированы для скрещивания, тогда потомкиX/' Хг'..., Хр' будут создаваться по правилу:

Mutation 1.

1. Вычислим значения ct = су(ху)

2. Найдем g наибольших з н а сц (i = l,n,j =\,т) и соответствующие им элементы матрицы X:

3. Определим множества:

I={ll, ib-: ij J={jlj2.-,jg}

4. Установим субматрицу W из элементов матрицы X следующим образом: элемент xvsXпереходит в Жтогда и только тогда, когда iel iKjeJ.

5. Зададим новые значения объемов производства и потребления a(wj nb(Wj):

6. Подключим алгоритм создания начальной популяции. В результате все ограничивающие условия для a(w) и b(wj) будут удовлетворены, а мы получим новые значения для матрицы W.

7. Заменяем выбранные элементы матрицы X на новые элементы из матрицы W.

8. Конец работы.

В результате действия оператора мутации Mutation 1 все глобальные ограничения сохраняются. Параметр g может принимать значения из множества {1,2, .... пт}, но так как мутация, чтобы не стать деструктивной, должна вносить лишь небольшие изменения в особь, предлагается выбирать число g равным 2~4 элементам.

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

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

где c(x) - линейная, выпуклая или вогнутая функция стоимости.

Подобного рода задачи зачастую возникают перед экономистами при решении проблем производственно-транспортного планирования, например, при оптимизации транспортных межцеховых перевозок предприятий с разветвленной сетью внутризаводских грузопотоков. На основе анализа существующего технологического цикла автотранспортных перевозок возможно повысить эффективность работы автотранспорта, предназначенного для межцеховых перевозок за счет снижения стоимости перевозки 1 тонны груза, уменьшения количества автотранспорта и так далее. В этом случае переменные и коэффициенты задачи имеют следующий смысл: п — количество автомобилей; т - количество маршрутов; ^ - рабочее время i-го автомобиля; bj - объем перевозок по j-тому маршруту; t.. - время на выполнение i-ым автомобилем j-того маршрута;

Ру - пузоподъемность г-того автомобиля нау-том маршруте;

сч(ху) - суммарные затраты при выполнении г-м автомобилем у-го маршрута;

Ху - юличество рейсов г-того автомобиля нау-том маршруте.

В свою очередь, рассмотренные выше параметры распределительной задачи определяются следующим образом:

где//- количество цехов; Ру=м/*кртл£. - грузоподъемность z-того автомобиля

к] - коэффициент загрузки на у-том маршруте; 1Ч =</+*2 где

г1 - среднее время холостого пробега z-того автомобиля; г2 - время загрузки z-того автомобиля на у-том маршруте; гз - время разгрузки z-того автомобиля на у-том маршруте; ^ - время перевозки груза z-тым автомобилем на у-том маршруте;

г1 = • V,), где 1к- длина к-го маршрута, V, - скорость z-гo автомобиля;

г, = , где /, - длина >го маршрута, V, - скорость z-гo автомобиля.

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

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

Для этого вычислим допустимое число рейсов ьтого автомобиля на ^ том маршруте:

и необходимое число рейсов ьтого автомобиля для перевозки грузов ]-того маршрута:

Схема разработанной процедуры инициализации начальной популяции представлена на рис.2.

Рис.2. Схема процедуры инициализации начальной популяции для распределительной задачи Процедуры кроссинговера и мутации можно использовать в том виде, в котором они были разработаны для транспортной задачи. Приведем доказательство этого утверждения для оператора кроссинговера Cross 2 при р=2

Утверждение. Пусть XI и Х2 допустимые решения, тогда Yl=cl*Xl+c2*X2 и Y2=cl*X2+c2*Xl - также допустимые решения.

Доказательство:

Для XI выполняются следующие ограничения:

/их! I + ЬгХп + ••• + Л„х1„ = 01 1г\ Х21 + /22 Х22 + • • • + /г, Хг„ = аг

1*\Хп\ 1пгХя2 + + 1ппХ<н* = &Л И

р„х] и р11хп+-+р.1х\, = Ь1 Ра Хп + Р11Х27 + ••• + Рп 2 х'.2 = Ьг

Р1» х'ш + ргтх1т+- + Р„„ хт = Ь„ Для Х2 условия выписываются аналогично. Потомок У1 будет иметь следующий вид:

ЬХи + СгХп С, х\г + СгХп ••• С1х\„ + Сгх]п С\ Хл + Сг Х21 С, Хп + Сг х1г ••• С\ х\„ + С 2 Хг„

„С1 х1| + Сг Х*1 С^г + СгХ.г - С1х'„ + Сгх1..

Докажем, что потомок У1 является допустимым решением. Допустим, что

и 1 (С1 х\I + Сг Хп) + 1хг (С| х|2 + СгХ?г) + ••■+ /,„ (С] х!„ + С2х'„) = а, /и (С| Хг1+ Сг Х21) + 1гг (С) Хгг + Сг Хгг) + - + 1г. (С\ Хгт + Сг Хг«) = Яг

/»1 (с. Хм + Сг х!,) + /я2 (с. х',2 + Сг х!г) + ••• + /»„ (С1 х!,™ + Сг х!,) = Я» И

Рп (С1 Хм + Сг Хп) + Р21 (С1Х21 + Сг Х21) + ••• + РА (С1 х'„| + Сг Хм) = 6, Лг (С| х!г + Сг Х?г) + Рг1 (с, Х22 + Сг Хгг) + ■ ■• ■■ + Рпг (с, х\г + Сг Х*г) = ¿г

(С1 х|„ + Сг Х^) + Ргт (с, х'г, + Сг х\т) + ••• + р„ (с, х! + Сг Х^) = Ьт Перегруппируем слагаемые и вынесем общий множитель за скобки:

С1 (1п Х\ 1 + /12 х'г + - + 1ы Х\») + Сг (/11 Хм + /12 Х1г + ■•• + /,« Хш) = <Я1 С1 (/г) Х21 + /22 Хгг + - + /г» Х2т) + Сг (/21 Х21 + /гг Хгг + - + /г. Хг .,) = Дг

С! 0,1 х'„1 +/.2 х!г +■■• + /„» х!,„) + Сг (/.1 Хм+ /,2 Х*г+- + /.«. х',) = йп И

С1 (Л. + Х21 + - + Л, Хм) + Сг 0>„ Хм + Рг, Хг, + - + РЛ Хм) = Ь, С1 (р,2 х]г + Ра Хи + ••• + Р.2 х\г) + Сг (рпХп + />2г Хгг + ••• + Р,г х1г) = ¿2

С| (/>,„ х!„ + />2„ х'г, ++ р.. х!™) + Сг Х?„ + Ргл Хг„ + - + Р,т X™) = Подставив в последние вьфажения формулы (1), (2), получим:

(1)

(2).

CtOi + Ciat -ai

С] а2 + с2а2 = аг С\а, + Сга, = а,

Ci bn + cib„-bm-

Из последней системы уравнений при с1+с2=7 получаем тождества.

В четвертой главе приведены экспериментальные данные о работе алгоритмов. Проведено тестирование разработанных методов с использованием математического моделирования и вычислительного эксперимента. Для каждой серии экспериментов проведен регрессионный анализ, который подтвердил теоретическую оценку о(п2) вычислительной сложности алгоритма. Разработанный генетический алгоритм был применен для решения прикладных нелинейных распределительных задач, возникших при оптимизации межцеховых (внутризаводских) перевозок ООО «Ростовский литейный завод». Для разработанных алгоритмов создан комплекс программ на языке программирования Borland Pascal 7.0.

Основные результаты работы

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

2. Разработан новый генетический оператор кроссинговера, производящий легальные (допустимые) решения. Усовершенствован оператор мутации, отличающийся от известного тем, что точки мутации определяются не случайно, а с использованием знаний о целевой функции.

3. Смоделирована генетическая процедура инициализации начальной популяции для распределительной задачи, основанная на методе последовательного насыщения строк и столбцов и имеющая вычислительную сложность о(птр), где p - размер популяции.

4. Построена математическая модель прикладной задачи оптимизации межцеховых перевозок на предприятии с разветвленной сетью внутризаводских грузопотоков.

5. Разработанные методы протестированы с использованием ЭВМ. Проведенные исследования подтвердили теоретические оценки вычислительной сложности, составившие величину порядка о(п). По сравнению с известными методами разработанные алгоритмы являются более эффективными, в частности, улучшение по качеству составило 3-12 %, а по времени 1-2 порядка.

Публикации по теме диссертационной работы

1. Чернышев Ю.О., Басова А.В. Генетические алгоритмы для решения нелинейных задач транспортного типа // Известия ТРТУ, № 2, Таганрог, 1998. - С. 259-260.

2. Басова А.В. Алгоритм решения нелинейной транспортной задачи на основе генетических процедур // IV Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления»: Тезисы доклада. - Таганрог, ТРТУ, 1998. - С. 60.

3. Басова А.В. Модифицированный генетический алгоритм для решения транспортных задач в сельском хозяйстве и на производстве.// Сборник научных трудов «Проблемы конструкторско-технологической подготовки производства на предприятиях сельскохозяйственного машиностроения». - Ростов-на-Дону, РГАСХМ, 1999. - С. 143-144.

4. Басова А.В. Транспортировка сельскохозяйственной продукции: новый подход. // Интеграция отраслевой и вузовской науки: проблемы современного машиностроения. Материалы международной научно-технической конференции. - Ростов-на-Дону, РГАСХМ, 2000. - С. 30.

5. Басова А.В. Модифицированный генетический алгоритм для нелинейных транспортных задач. // Интеграция отраслевой и вузовской науки: проблемы современного машиностроения. Материалы международной научно-технической конференции. - Ростов-на-Дону, РГАСХМ, 2000. - С. 198-199.

6. Басова А.В. Методика отбора особей для кроссинговера в генетических алгоритмах. //Сборник тезисов докладов студенческой научной конференции РГПУ. - Ростов-на-Дону, 2003. - С. 260.

7. Чернышев Ю.О., Басова А.В. Теоретическое обоснование возможности решения вогнутой распределительной задачи с помощью методов эволюционного моделирования. //Информационные технологии в науке, образовании, телекоммуникации и бизнесе. Материалы юбилейной XXX международной конференции. - Украина, Ялта-Гурзуф, 2003. - С. 147-149.

8. Басова А.В. Генетический метод отыскания глобального минимума многоэкстремальных задач. //Математические методы в технике и технологиях. Сборник трудов XVI международной научной конференции. Т.2. - Санкт-Петербург, 2003. - С. 141-143.

9. Басова А. В. Новые методы отыскания глобального минимума многоэктремальных задач.// Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права. Научные труды VI международной научно-практической конференции. Книга «Информатика». - Москва, 2003. - С.31-35.

В работах, опубликованных в соавторстве, автору принадлежат следующие

результаты: в [1] - экспериментальная обработка данных, в [7] -

генетический алгоритм решения нелинейной распределительной задачи.

Подписано к печати 19 04.04 г. Формат 60x84/16. Бумага № 3Я91720. Печать трафаретная. Объем 0.94 усл. п.л. Заказ 4/04. Тираж 100 экз.

* - 8 6 9 5

ВВЕДЕНИЕ.:.

ГЛАВА 1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ОПТИМИЗАЦИОННЫХ

ЗАДАЧ И МЕТОДЫ ИХ РЕШЕНИЯ.д

1.1 Прикладные задачи производственно-транспортного планирования как объект математического моделирования.

1.2 Основные виды многоэкстремальной оптимизации.

1.3 Математические модели и классические методы решения транспортной и распределительной задач.

1.4 Модели процессов оптимизации в природе.

1.5 Исследование методов генетического поиска.

1.6 Выводы.

ГЛАВА 2. РАЗРАБОТКА ЭФФЕКТИВНОГО ГЕНЕТИЧЕСКОГО

МЕТОДА РЕШЕНИЯ НЕЛИНЕЙНОЙ ТРАНСПОРТНОЙ ЗАДАЧИ.

2.1 Математическая модель и кодировка решения.

2.2 Моделирование начальной популяции.

2.3 Функция оценки годности.

2.4 Моделирование процессов кроссинговера и мутации.

2.5 Формирование репродукционной группы и моделирование естественного отбора.

2.6 Общая структура разработанного метода решения нелинейной транспортной задачи и его свойства.

2.7 Применение моделирования макроэволюции для повышения качества решения.

2.8 Выводы.

ГЛАВА 3. РАЗРАБОТКА ЭФФЕКТИВНОГО ГЕНЕТИЧЕСКОГО МЕТОДА РЕШЕНИЯ НЕЛИНЕЙНОЙ РАСПРЕДЕЛИТЕЛЬНОЙ

ЗАДАЧИ.

3.1 Математическая модель и кодировка решения.

3.2 Моделирование начальной популяции.

3.3 Функция оценки годности.

3.4 Обоснование применения оператора кроссинговера.

3.5 Моделирование процесса мутации.

3.6 Общая структура разработанного метода решения нелинейной распределительной задачи и его свойства.

3.7 Модифицированный ГА с усложненной структурой.

3.8 Выводы.

ГЛАВА 4. ОБОСНОВАНИЕ И ТЕСТИРОВАНИЕ РАЗРАБОТАННЫХ

МЕТОДОВ

4.1 Цели экспериментального исследования.

4.2 Исследование эффективности алгоритмов с использованием математического моделирования и вычислительного эксперимента

4.3 Применение разработанных методов и комплекса проблемно-ориентированных программ для решения прикладных задач.

4.4 Выводы.

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

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

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

Цели и задачи исследования. Основной целью работы является повышение эффективности решения нелинейных транспортных задач с использованием идеологии эволюционного моделирования. Для достижения поставленной цели необходимо:

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

• изучить возможности генетических методов и разработать системный подход к решению нелинейных задач транспортного типа с использованием модифицированных и вновь созданных генетических операторов;

• исследовать механизмы генетического поиска оптимальных вариантов транспортировки, установить наиболее эффективные параметры процесса, экспериментально обосновать стратегию получения заданного результата.

Методы исследования. В работе использованы математические методы, в том числе: теория множеств, теория графов, теория алгоритмов, методы оптимизации, методология эволюционного моделирования и генетических алгоритмов, компьютерное моделирование. Научная новизна

• Разработаны генетические методы решения нелинейных транспортных и распределительных задач с вогнутыми функциями стоимости;

• Построен новый генетический оператор кроссинговера, ориентированный на специфику нелинейных транспортной и распределительной задач;

• Разработана генетическая процедура инициализации начальной популяции для распределительной задачи, основанная на методе последовательного насыщения строк и столбцов;

• Усовершенствован известный оператор мутации с учетом нелинейности решаемых задач.

Практическая значимость диссертационной работы состоит в следующем: построена математическая модель прикладной задачи оптимизации межцеховых перевозок на промышленном предприятии с разветвленной сетью внутризаводских грузопотоков; на основе разработанных методов создан комплекс проблемно-ориентированных программ, позволяющий решать нелинейные прикладные задачи.

Реализация результатов работы. Разработанные алгоритмы использованы при выполнении федеральных госбюджетных научно-исследовательских работ в Ростовской-на-Дону государственной академии сельскохозяйственного машиностроения (РГАСХМ): «Теоретические основы эволюционного моделирования генетических алгоритмов», «Основы вычислительного представления генетических алгоритмов для решения оптимизационных задач», «Развитие эволюционного моделирования для решения оптимизационных задач» и «Теория поисковой адаптации для решения избранных комбинаторных задач оптимизации». Результаты диссертационной работы использованы при оптимизации межцеховых перевозок в ООО «Ростовский литейный завод». Материалы диссертации используются в учебном процессе на кафедре прикладной математики и вычислительной техники РГАСХМ при проведении лекционных и практических занятий по курсам «Основы САПР» и «Программные средства САПР». Акты об использовании результатов работы приведены в приложениях к диссертации.

Апробация работы. Основные научные и практические результаты докладывались и обсуждались на международной научно-технической конференции "Интеллектуальные САПР" (ТРТУ, Таганрог-Гурзуф, 1997), на IV всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (ТРТУ, Таганрог, 1998), на региональной конференции "Информатизация, автоматизация и роботизация в машиностроении" (РГАСХМ, Ростов-на-Дону, 1999), на международной научно-технической конференции "Проблемы совершенствования зерноуборочной техники: конструирование, организация производства, эксплуатация и ремонт" (РГАСХМ, Ростов-на-Дону, 1999), на международной научно-технической конференции «Интеграция отраслевой и вузовской науки: проблемы современного машиностроения» (РГАСХМ, Ростов-на-Дону, 2000), на региональной научно-технической конференции «Интеграция отраслевой и вузовской науки: проблемы современного машиностроения» (РГАСХМ, Ростов-на-Дону, 2002, 2003), на студенческой научной конференции Ростовского государственного педагогического университета (РГПУ, Ростов-на-Дону,

2003), на XVI международной научной конференции «Математические методы в технике и технологиях» (С.-ПбГТУ, Санкт-Петербург, 2003), на XXX юбилейной международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе (1Т+8Е'2003)» (Украина, Ялта-Гурзуф, 2003), на VI международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (МГАПИ, Москва, 2003).

Публикации. Результаты диссертации отражены в 9 печатных работах.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 101 наименования и двух приложений. Содержание диссертационной работы изложено на 120 страницах, в том числе 15 рисунков, 11 таблиц.

4.4. Выводы

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

2. Экспериментальным путем определена вычислительная сложность предложенных алгоритмов, составившая величину порядка о(п2), что подтвердило теоретические оценки, приведенные в главе 2 и главе 3.

3. Разработанный генетический алгоритм применен для решения прикладной нелинейной распределительной задачи оптимизации межцеховых (внутризаводских) перевозок ООО «Ростовский литейный завод».

110

ЗАКЛЮЧЕНИЕ:

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

2. Повышена эффективность решения нелинейных транспортных и распределительных задач с вогнутыми функциями стоимости за счет использования генетического подхода. Разработаны генетические методы решения нелинейных транспортной и распределительной задач с вогнутыми функциями стоимости, имеющие вычислительную сложность 0(п2), что на 1-2 порядка ниже, чем сложность известных алгоритмов.

3. Разработан оператор кроссинговера Cross 2, производящий легальные (допустимые) решения и имеющий вычислительную сложность 0(п2). Усовершенствован оператор мутации Mutation 1, отличающийся от известного тем, что точки мутации определяются не случайно, а с использованием знаний о целевой функции.

4. Смоделирована генетическая процедура инициализации начальной популяции для распределительной задачи, основанная на методе последовательного насыщения строк и столбцов матрицы допустимого плана задачи. Данная процедура имеет вычислительную сложность 0(тпр), где р - размер популяции. Сформулировано и доказано утверждение, которое позволяет использовать для распределительной задачи оператор кроссинговера Cross 2, разработанный для нелинейной транспортной задачи.

5. Построена математическая модель прикладной задачи оптимизации межцеховых перевозок на предприятии с разветвленной сетью внутризаводских грузопотоков.

6. Разработанные методы протестированы с использованием ЭВМ. Проведенные исследования подтвердили теоретические оценки вычислительной сложности методов, составившие величину порядка 0(гГ). По сравнению с известными методами разработанные алгоритмы являются более эффективными, в частности, улучшение по качеству составило 3-12 %, а по времени - на 1-2 порядка.

1. Михалевич B.C., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. — М.: Наука, 1986 259 с.

2. Михалевич B.C., Гупал A.M., Норкин В. И. Методы невыпуклой оптимизации. М.: Наука, 1987.

3. Поляк Б.Т. Введение в оптимизацию. М.: Наука,1983 - 384 с.

4. Йенсен П., Барнес Д. Потоковое программирование. М.: Радио и связь, 1984.

5. Файзуллин А.З. Разработка и исследование генетических методов размещения двумерных геометрических объектов: Автореф. дис. канд. тех. наук. Таганрог: ТРТУ, 1996.

6. Cohoon J.P., Martin W. N., Richards D.S. A multi-population genetic algorithm for solving the k-partition problem on huper-cube. San Diego, 1991.

7. Cohoon J.P., Herde S.V., Martin W. N., Richards D. S. Distributed genetic algorithms for the floorplan design problem. IEEE Trans on CAD, vol. 10, April, 1991, pp. 483-491.

8. Hitchcock F.L. Distribution of a product from several sources to numerous localities.//J. Math. Puys, 1941.

9. Holland J.H. Adaptation in natural and artificial systems: an introductory analysis with application to biology, control, and artificial intelligence. University of Michigan, 1975.

10. Adolf Hofmaifar. A new approat on the travelling salesman problem by genetic algorithms. Department of electrical engineering North Carolina A&T State University Greensboro. North Carolina.

11. Crefenstette J., Rajiv Gopal, Rosmaito В., Gurcht D.V. Genetic algorithms for the travelling salesman problem. Computer Sciens Department. Vanderbild, 1989.

12. Handbook of genetic algorithms, Edited by Lawrence Davis, Van Nostrand Reinhold, New York, 1991.

13. Goldberg D.E. Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publishing Company, inc. 1989.

14. Mange A.P., Mange E.J. Genetics: human aspects. Saunder College, Philadelphia, 1982.

15. П.Голынтейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969.

16. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977.

17. Толстой А.Н. Методы устранения нерациональных перевозок при планировании. М.: Социалистический транспорт, 1939.

18. Канторович Л.В., Гавурин М.К. Применение математических методов в вопросах анализа грузопотоков. М.: Издательство АН СССР, 1949.

19. Кун Х.У. Венгерский метод решения задачи о назначениях // В сб. «Методы и алгоритмы решения транспортной задачи. М.: Госстандарт, 1963.

20. Панов С.А. Современные экономико-математические методы в управлении и планировании на автомобильном транспорте. М.: Высшая школа, 1969.

21. Геронимус Б.Л. Математические методы планирования грузовых автомобильных перевозок. М.: Транспорт, 1972.

22. Кузубов В.И., Кузнецов Ю. Н., Волощенко А. Б. Математическое программирование. Киев, 1973.

23. Левит Б.Ю., Лившиц В.И. Нелинейные сетевые транспортные задачи. М.: Транспорт, 1972.

24. Жак С.В. Математическое программирование. Ростов-на-Дону, РГУ, 1972.

25. Юдаев С.Г. Алгоритмы и программы нелинейной оптимизации. -Новочеркасск, 1992.

26. Проблемы нелинейного программирования. Оптимизация. АН СССР. -Новосибирск, 1978.

27. Демидович О.И. Вычисление нижних оценок в многоэкстремальной задаче о потоке минимальной стоимости. М.: АН СССР, 1988.

28. Нестеров Ю. Э. Эффективные методы в нелинейном программировании. -М.: Радио и связь, 1989.

29. Демидович О.И. Метод ветвей и границ для решения задачи о многопродуктовом потоке с вогнутой функцией стоимости. М.: АН СССР, 1987.

30. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. -М.: Наука, 1988.

31. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М.: Мир, 1982.

32. Васильева Е.М., Левит Б.Ю., Лившиц В.Н. Нелинейные транспортные задачи на сетях. М.: Финансы и статистика, 1981.

33. Malek-Zavarei М., Frisch I.F. On the fixed-cost flow problem. International Journal of control, 1972.

34. Florian M., Robillard P.An implict enumeration algorithm for the concave cost network flow problem. Managment Science, 1971.

35. Klein M. A primal methpd for minimal cost flows with applications to the assignment and transportation problems. Managment science, 1967.

36. Zangwill W.A. Blacklogging model and a multi-echelon model of a dynamiic economic lot size production system a network approat. Managment science, 1969.

37. Efroymson M.A., Ray T.L. A branch and bound algorithms for plant location operations research, 1966.

38. Лебедев С.С. Конечный метод решения нелинейных задач транспортного типа // Экономика и математические методы. М.: Наука, 1965.

39. Падалко Л.П. Алгоритм решения нелинейной транспортной задачи. // Экономика и математические методы. Т4. - В6. - М.: Наука, 1968.

40. Корбут A.A. Целочисленные задачи линейного программирования.// Экономика и математические методы. ВЗ. М.: Наука, 1965.

41. Юдин Д.Б. Методы количественного анализа сложных систем // Известия АН СССР. Техническая кибернетика. М. 1965.

42. Хоанг Туй. Вогнутое программирование при линейных ограничениях// Доклады Академии наук СССР. Т 159.- М., 1964.

43. Уткин С.Л. Вычислительные алгоритмы и опыт минимизации вогнутой функции на выпуклом многограннике. М.: ВЦ АН СССР, 1990.

44. Хачатуров В.Р., Уткин С.Л. Решение многоэкстремальных задач вогнутого программирования аппроксимационно-комбинативным методом M.: ВЦ АН СССР, 1988.

45. Хачатуров В.Р., Монтлевич В.М. Решение нелинейных производственно-транспортных задач с неделимыми потребителями. М.: ВЦ АН СССР, 1987-22 с.

46. Седова C.B., Лебедев С.С. Новый алгоритм метода условных векторов целочисленного программирования // Экономика и математические методы. М.: Наука, 2002. - Т. 38. - №1. - С. 121-129.

47. Буманский С.П. Модели эффективного развития сети автомобильных дорог // Экономика и математические методы. М.: Наука, 2002. - Т. 38. -№3. - С. 54-62.

48. Ильменский М.Д., Маракуев A.B., Паринов С.И. Применение новых информационных технологий в экономических исследованиях. // Экономика и математические методы. М.: Наука, 2003. - Т. 39. - №2. -С. 155-157.

49. Дюсуше О.М. К вопросу о модели нелинейных тарифов // Экономика и математические методы. М.: Наука, 2003. - Т. 39. - №1. - С. 43-47.

50. Крутиков В.Н., Петрова T.B. Релаксационный метод минимизации с растяжением пространства в направлении субградиента // Экономика и математические методы. М.: Наука, 2003. - Т. 39. - №1. - С. 106-111.

51. Ларин П.М. О неразрешимости задач гарантированного поиска в достаточно большой области // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. М.: Изд-во Московского университета, 2000. - №1. - С. 44-48.

52. Афанасьев М.К. Конструктор генетических алгоритмов и способы кодирования хромосом // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. М.: Изд-во Московского университета, 2001. - №3. - С. 43-49.

53. Петров Д.Ф. Генетика с основами селекции. М.: Высшая школа, 1971. -410 с.

54. Большая советская энциклопедия. Третье издание. М.: Советская энциклопедия, 1975.

55. Кушев В.В. Механизмы генетической рекомбинации. Ленинград, 1971.

56. Кушев В.В. Элементарные процессы генетики. Ленинград, 1973.

57. Лукьянченко П.П. Избранные труды. М., 1973.

58. Растригин Л.А. Случайный поиск в эволюционных вычислениях// Обозрение прикладной и промышленной математики. М.: ТВП, 1996.

59. Vignaux G.A, Michalewicz Z. Genetic algorithm for the linear transportation problem. IEEE transactions on system, man, and cybernetic, 1991.

60. Курейчик В.В. Исследование и разработка генетических алгоритмов для конструкторского синтеза элементов СБИС: Автореф. дис. канд. тех. наук.- Таганрог: ТРТУ, 1995. 16 с.

61. Гудман Э. Эволюционные вычисления и ГА // Обозрение прикладной и промышленной математики. М.: ТВП, 1996.

62. Курейчик В.М. Генетические алгоритмы. Учебник для вузов. Таганрог: ТРТУ, 1998.

63. Муфтар Б. Современное линейное программирование. — М.: Мир, 1984.

64. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

65. Канторович Л.В. Экономический расчет наилучшего использования ресурсов. М.: Изд-во АН СССР, 1959.

66. Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. — М.: Радио и связь, 1982.

67. Гасс С. Линейное программирование (методы и приложения)./пер. с англ.- М.: Физматгиз, 1961.

68. Рейнфельд Н., Фогель У. Математическое программирование (методы решения произвольных и транспортных задач). М.: Изд-во иностр. литературы, 1960.

69. Пападимитриу X. Комбинаторная оптимизация. М.: Мир, 1984.

70. Юдин Д.Б., Гольшьейн Е.Г. Задачи и методы линейного программирования. М.: Сов. радио, 1961.78.3уховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. -М.: Наука, 1967.

71. Банди. Б. Основы линейного программирования. / пер. с англ. М.: Радио и связь, 1989.

72. Юдин Д.Б., Голыитейн Е.Г. Линейное программирование. Теория, методы и приложения. — М.: Наука, 1969.

73. Булувский В.А., Звягина P.A., Яковлева М.А. Численные методы линейного программирования. М.: Наука, 1976.

74. Майника Э. Алгоритмы оптимизации на сетях и графах. — М.: мир, 1981.

75. Триус Е.Б. Задачи математического программирования транспортного типа. М.: Сов. радио, 1967.

76. Чернышев Ю.О., Басова A.B. Генетические алгоритмы для решения нелинейных задач транспортного типа // Известия ТРТУ, № 2, Таганрог, 1998.-С. 259-260.

77. Басова A.B. Транспортировка сельскохозяйственной продукции: новый подход. // Интеграция отраслевой и вузовской науки: проблемы современного машиностроения. Материалы международной научно-технической конференции. Ростов-на-Дону, РГАСХМ, 2000. - С. 30.

78. Басова A.B. Методика отбора особей для кроссинговера в генетических алгоритмах. //Сборник тезисов докладов студенческой научной конференции РГПУ. Ростов-на-Дону, 2003. - С. 260.

79. Басова A.B. Генетический метод отыскания глобального минимума многоэкстремальных задач. //Математические методы в технике и технологиях. Сборник трудов XVI международной научной конференции. Т.2. Санкт-Петербург, 2003. - С. 141-143.

80. Львовский E.H. Статистические методы построения эмпирических формул. — М.: Высшая школа, 1988. 239 с.

81. Митропольский А.К. Техника статистических вычислений. М.: Наука, 1971.-576 с.

82. Адлер Ю.П. Введение в планирование эксперимента. — М.: Металлургия, 1969.- 157 с.

83. Айвазян С. А. Статистическое исследование зависимостей. — М.: Металлургия, 1968. 227 с.

84. Бешелев С.Д., Гурвич Ф.Г. Математико-статистические методы экспертных оценок. М.: Статистика, 1980. - 264 с.

85. Дрейпер Н., Смит Г. Прикладной регрессионный анализ. М.: Финансы и статистика, 1986. - 365 с.