Введение к работе
Актуальность темы.
Работа посвящена разработке приближенного метода поиска экстремума функции, без предположения о ее дифференцируемости, основанного на законе гравитационного притяжения, а также решению с его помощью ряда прикладных задан, в том числе из области физики элементарных частиц и сферы проблем транспортировки нефти, v/
В рамках данной работы рассматриваются задачи поиска экстремума нелинейной функции с действительными переменными. В практических приложениях целевая функция нередко не удовлетворяет необходимым условиям для возможности применения той или иной методики. В связи с этим при решении прикладных экстремальных задач наряду с традиционными методами широко используются приближенные алгоритмы, ко-1 торые с одной стороны имеют меньшую трудоемкость и с другой - позволяют снизить требования на гладкость целевой функции. Но даже в случае, когда целевая функция дифференцируема достаточное число раз, остро встает вопрос о близости начального приближения к точке экстремума, что является необходимым требованием применения локальных быстросходящихся алгоритмов [3, 6].
Последнее десятилетие в связи с развитием вычислительной техники V при исследовании различных задач моделирования успешно используются алгоритмы, основанные на «естественных» аналогиях. Разработка мате-\ матической модели на основе законов эволюции живой природы позволила создать эффективные алгоритмы, успешно применяемые в теории экстремальных задач, при проектировании самообучающихся систем, в задачах распознавания и т.п. Примерами могут служить генетические алгоритмы и эволюционные стратегии [9, 10, 11]. Смежным направлением, также использующим биологические аналогии, является нейропро-граммирование (нейронные сети). В русле данного подхода рассматриваются методы исследования экстремальных задач с использованием алгоритмов, основанных на законах механики [8]. В настоящее время развиваются энтропийные методы моделирования сложных систем, в частности, «гравитационные модели» задач транспортного типа и размещения [2]. Попытки выявить закономерности, лежашие в основе пространственных взаимодействий между городами (перемещение людей, грузов, информации, диффузии нововведений, другие виды взаимодействий), также привели к идее воспользоваться аналогиями с фундаментальным законом всемирного тяготения [5].
Необходимость решения сложных научных и производственных проблем, сводящихся к задаче поиска экстремума функции, заданной в непрерывном пространстве поиска, при отсутствии сведений о ее гладкости,
количестве экстремумов и т.д., с одной стороны, и повышение интереса к приближенным алгоритмам оптимизации, ориентированным на практические приложения и использующим аналогии с реальными процессами -с другой, легли в основу проведенных исследований.
Цель работы: решение ряда прикладных производственных задач при помощи разработанного эвристического, основанного на гравитационных аналогиях, метода поиска экстремума нелинейной, в общем случае, недифференцируемой функции.
Научная новизна. К новым результатам диссертации относятся: использование гравитационных аналогий в методе поиска экстремума функции, основанном на коллективном взаимодействии набора рабочих точек; малые возмущения системы гравитирующих частиц за счет применения аналога оператора рекомбинации эволюционных алгоритмов, позволяющие повысить эффективность предложенного метода; установление связи направления смещения рабочей точки алгоритма поиска экстремума функция, построенного на базе модели гравитирующей системы частиц переменной массы, с производной целевой функции; математическая модель задачи минимизации суммарных затрат по производству некоторого продукта для непрерывно распределенных величин; точное решение задачи минимизации суммарных затрат без учета технологических ограничений при дополнительных предположениях относительно вида целевой функции.
Практическая и теоретическая ценность результатов работы: разработан приближенный метод поиска экстремума нелинейной функции с действительными переменными без предположения о ее дифференцируемое - «гравитационный» метод; метод, основанный на гравитационных аналогиях, применен при решении задачи минимизации многоэкстремальной функции, возникающей в экспериментах физики высоких энергий, проводимых в ОИЯИ РАН (г. Дубна); в соавторстве с Р.Т. Файзулли-ным, К.В. Логиновым, С.Л. Семиным создан пакет программ «Гидравлический расчет и выбор оптимальных режимов работы разветвленного магистрального нефтепровода», в настоящее время используемый в ОАО «Транссибнефть» (г. Омск).
Методы исследования. При решении поставленных задач использовались приближенные алгоритмы поиска экстремума функции, геометрическое моделирование в пространстве произвольной размерности, конеч-норазностные методы решения обыкновенных дифференциальных уравнений (ОДУ) и систем ОДУ, компьютерное моделирование, а также современная методология экспериментальных исследований с применением вычислительной техники.
Апробация работы. Результаты работы докладывались на Международной научно-технической конференции «Динамика систем, механизмов и машин» (Омск, 1995), Международной конференции «Проблемы оптимизации и экономические приложения» (Омск, 1997), Второй научной конференции молодых ученых и специалистов ОИЯИ (Дубна, 1998), Третьем Сибирском конгрессе по прикладной и индустриальной математике «ИКПРЙМ-98» (Новосибирск, 1998), XI-ой Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 1999), Четвертом Сибирском конгрессе по прикладной и индустриальной математике «ШШРИМ-00» (Новосибирск, 2000), а также на семинарах кафедры математического моделирования Омского государственного университета, на спецсеминаре «Моделирование систем. Информационная экология» Омского филиала института математики им. С.Л. Соболева СО РАН, на семинаре кафедры теории управления и оптимизации Челябинского государственного университета.
Публикации. Основные результаты диссертации опубликованы в 11 печатных работах [12] - [22]. Різ совместных публикаций в диссертацию вошли результаты, полученные непосредственно соискателем.
Основные положения, выносимые на защиту:
«гравитационный» метод поиска приближенного экстремума функции с действительными переменными без предположения о ее дифференци-руемости, основанный на модели динамической системы гравитирующих частиц с переменной массой;
математическая модель и точное решение задачи минимизации суммарных затрат по производству некоторого продукта для непрерывно распределенных величин;
алгоритм выбора оптимальных режимов работы разветвленного нефтепровода, использующий гравитационные аналогии;
Достоверность полученных результатов обеспечивается данными численных экспериментов, успешным применением разработанных алгоритмов и программ в смежных научных исследованиях и использованием их в производственной практике.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и приложения. Объем составляет 160 страниц. Библиографический список насчитывает 97 наименований.