Математические модели и генетические методы решения нелинейных задач транспортного типа тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Басова, Алина Викторовна

• Басова, Алина Викторовна
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Басова, Алина Викторовна

ВВЕДЕНИЕ.:.

ГЛАВА 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 порядка.

Список литературы диссертационного исследования кандидат технических наук Басова, Алина Викторовна, 2004 год

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 с.