Методы оптимизации

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

ГОУ ВПО «Сибирский государственный индустриальный университет»

Кафедра систем автоматизации

Курсовая работа

«Методы оптимизации»

Выполнила:

студентка группы ИСУ-11

Бурулько В.А.

Проверил:

д.т.н., профессор Кулаков С. М.,

к.т.н., доцент Бондарь Н.Ф.

Новокузнецк 2014

Содержание

1. Освоение решения типовой задачи оптимизации поисковым методом Хука-Дживса

1.1 Теоретическая часть

1.2 Практическая часть

2. Анализ и модификация метода решения реальной задачи оптимизации на основе конкретной научной публикации

Список литературы

1. Освоение решения типовой задачи оптимизации поисковым методом Хука-Дживса

1.1 Теоретическая часть

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

Описание этой процедуры представлено ниже:

A. Выбрать начальную базисную точку b1 и шаг длиной hj для каждой переменной Xj , j = 1, 2,n. В приведенной ниже программе для каждой переменной используется шаг h, однако указанная выше модификация тоже может оказаться полезной.

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

1. Вычисляется значение функции f(b1) в базисной точке b1.

2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f(b1 + h1e1), где e1 -- единичный вектор в направлении оси x1. Если это приводит к уменьшению значения функции, то b1 заменяется на b1 + h1e1. В противном случае вычисляется значение функции f(b1 - h1e1), и если ее значение уменьшилось, то b1 заменяем на b1 - h1e1. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2, т. е. находится значение функции f(b1 + h2e2), и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2.

3. Если b2 = b1, т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если b2 ? b1, то производится поиск по образцу.

B. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

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

P1= b1 + 2 (b2 - b1)

В общем случае

Pi = bi + 2 (bi+1 - bi).

2. Затем исследование следует продолжать вокруг точки P1 (Pi).

3. Если наименьшее значение на шаге В.2 меньше значения в базисной точке b2 (в общем случае bi+1), то получают новую базисную точку b3 (bi+2), после чего следует повторить шаг В.1. В противном случае не производить поиск по образцу из точки b2 (bi+1), а продолжить исследования в точке b2 (bi+1).

Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.

Ниже приведена блок-схема данного метода (рисунок 1).

Рисунок 1 - Блок-схема поискового метода Хука-Дживса.

1.2 Практическая часть

На рисунке 2 изображена блок-схема алгоритма поиска минимума целевой функции методом Хука-Дживса. На рисунке 3 представлен интерфейс компьютерной программы написанной в среде программирования Delphi 7. Эта программа находит минимум целевой функции поисковым методом Хука-Дживса, при выполнении следующих ограничений: X1?0; Х2?0; X1 +Х2?4. На рисунке 4 изображен интерфейс программы с результатом поиска минимума целевой функции.

Рисунок 2 - Блок-схема алгоритма поиска минимума

Рисунок 3 - Ввод исходных данных и начала поиска

Рисунок 4 - Результаты поиска

Задача минимизации целевой функции решалась при условиях:

1. Целевая функция:

2. Ограничения: X1?0; Х2?0; X1 +Х2?4

3. Точка начального приближения: X1 = 3, Х2 = 4

4. Начальная длина шага: H = 1

5. Минимальная длина шага: Hmin = 10-8

По результатам поиска стало ясно, что минимум очевидно находится в точке (0; 0) для начальной точки (3; 4) и начального шага длиной 1. Значение целевой функции в этой точке равно 0.

Минимум найден за 127 итераций.

Точка начального приближения может быть и другой, например, при начальной точке (4; 4) минимум был найден за 108 итераций, а при начальной точке (56; 98) - за 249.

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

2. Анализ и модификация метода решения реальной задачи оптимизации на основе конкретной научной публикации

Во второй части своей курсовой работы я рассмотрю научную публикацию из журнала «Современные технологии автоматизации» (№4, 2000 г ) «Системы автоматического ведения поезда».

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

Основные типы систем автоматического ведения. Сегодня из всех систем локомотивной автоматики наиболее передовыми по части объема и сложности решаемых задач являются именно системы автоведения. Они делятся на три основные группы, в прямой зависимости от класса тягового подвижного состава:

· автоматическое ведение пригородного поезда;

· автоматическое ведение локомотива пассажирского поезда;

· автоматическое ведение локомотива грузового поезда.

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

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

Моторвагонный подвижной состав имеет значительный запас по силе тяги благодаря большому количеству движущих осей, относительно небольшой вес, а потому способен реализовывать большие ускорения (до 0,75 м/с2). Его эксплуатация связана с большим количеством остановок за поездку и частой сменой режимов движения «разгон-торможение»; обычно такие поезда используются на участках с наиболее интенсивным движением, где требуется очень точное соблюдение расписания (до 30 с).

Исходя из этого, была определена концепция системы автоматического ведения пригородного электропоезда: соблюдение перегонного времени хода; выполнение расписания поезда для каждого конкретного маршрута; соблюдение скоростного режима, исключающего превышение установленных скоростей движения, в том числе в местах действия ограничений скорости; соблюдение сигналов светофоров, требующих снижения скорости; расчёт кривой движения поезда с учетом требования минимизации расхода электроэнергии; измерение фактической скорости движения и сравнение ее с расчетной, выбор, исходя из этого, соответствующей тяговой позиции; расчет координаты местонахождения поезда (что особенно актуально в условиях недостаточной видимости); оповещение пассажиров о названиях остановочных пунктов, о закрытии автоматических дверей, о правилах проезда в пригородных поездах и др.; сообщение локомотивной бригаде необходимой информации о местах повышенной бдительности, сигналах автоматической локомотивной сигнализации (АЛСН), местах ограничения скорости, расположении устройств, мимо которых необходимо проследовать с отключенной тягой, об остановочных пунктах и станциях. Первые образцы системы автоматического ведения пригородного электропоезда (САВПЭ) были созданы во ВНИИЖТ еще в 80-е годы. Для выполнения графика движения и экономии электроэнергии в системе автоведения реализован механизм регулирования времени хода, основанный на предварительном расчете траектории движения поезда для заданного расписания. Построенная кривая движения разбивается системой на режимы ведения. Большое количество коротких перегонов и малое число ходовых позиций контроллера (всего 4), а также особенности цепей управления в электропоезде при сбросе позиций обуславливают особый режим ведения электропоезда, который в значительном числе случаев представляет собой последовательность «разгон-выбег-торможение». На более длинных перегонах система реализует схему с несколькими включениями тяги, то есть режим «разгон-выбег-тяга-выбег-тяга-...-выбег-торможение». По аналогичной схеме реализуется и поддержание скорости, например, при следовании по участку с ограниченной допустимой скоростью движения. Рассчитанные траектории обобщенно задаются в виде параметров (коэффициентов), описывающих скорость разгона и среднюю скорость. Такой подход позволил построить быстрый регулятор времени хода, весь процесс регулирования при этом укладывается в один такт измерения-управления. При этом управляющая программа получилась достаточно компактной и была реализована на процессорах 8086, которые в более поздних приборах САВПЭ были заменены на 80386SX и 80386ЕX.

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

Управлять поездом при помощи САВПЭ машинист на свое усмотрение может, переключив систему в режим автоведения или в режим подсказки в соответствии с показаниями индикатора. Значительный объем в аппаратуре систем автоведения электропоезда отводится блоку речевого информатора, который не только выполняет функции оповещения пассажиров, но и, опираясь на сигналы датчика пути и скорости и АЛСН, сообщает машинисту о приближении к переездам, мостам, тоннелям, нейтральным вставкам и токоразделам, постам обнаружения нагрева букс (приборам ПОНАБ, ДИСК), а также об ограничениях скорости, желтом и красном сигналах АЛСН. Эта функция, во-первых, способствует повышению безопасности движения, привлекая внимание локомотивной бригады к местам и событиям, требующим повышенной бдительности или соблюдения особых условий; а во-вторых, облегчает труд машиниста и его помощника, избавленных теперь от необходимости читать информационные сообщения для пассажиров.

Сегодня на электропоездах применяются унифицированные системы автоведения поезда УСАВП и УСАВП-Л. В системе УСАВП применен контроллер 6030 серии MicroPC фирмы Octagon Systems.

В задачи автоведения пассажирского электровоза входят:

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

· организация взаимодействия прибора автоведения и машиниста посредством отображения на индикаторе всей информации о режимах движения поезда (обратная связь);

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

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

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

Учеными ВНИИЖТ был предложен метод оптимизации, позволяющий строить энергооптимальную траекторию движения за разумное время (не более минуты для участка длиной 200 км, имеющего 1000 элементов профиля, 20 ограничений скорости, и 80-вагонном составе). Этот метод оптимизации позволяет автоматически (без перебора) учесть профиль и все ограничения скорости, рассчитать начало предварительных выбегов перед спусками и другие режимы.

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

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

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

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

Часто применяется режим движения, требующий адаптации скорости движения к сигналам АЛСН (езда в потоке). Существуют серьезные ограничения на выбор режима управления локомотивом, связанные с предельно допустимыми усилиями в составе. Поэтому ускорение поезда, как правило, мало и не превышает 0,1 м/с2.

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

· ограничение сил в составе на допустимом уровне в соответствии с планом и профилем пути, а также схемой формирования состава;

· формирование управляющих сигналов, обеспечивающих допустимые продольно-динамические силы в составе;

· управление локомотивом с максимальным использованием его тяговых возможностей.

Программное обеспечение системы автоведения. Программы систем автоведения представляют собой программы реального времени, имеющие циклический или событийно-циклический характер. Это означает, что во всех программах имеется, как минимум, один цикл измерения-управления: опрос датчиков -- обработка информации -- её анализ -- принятие управляющего решения -- выдача команды на исполнительные элементы. Этот цикл может быть жестко разбит на более мелкие временные интервалы (такты) для создания временной сетки. Также все программные модули могут быть привязаны только к основному циклу. Обработка внешних событий типа изменения сигнала АЛСН может происходить либо в заданном месте цикла измерения-управления, либо асинхронно, сразу в момент возникновения события. В первом случае управляющая программа имеет циклическое построение, во втором -- событийно-циклическое.

Рисунок 5 - Блок-схема системы автоведения локомотива

Заключение

Сегодня в стадии опытной эксплуатации находится система автоведения электровоза ЧС7, построенная на базе процессорного модуля Fastwel CPU686. В качестве операционной системы применена RTOS-32. Программа автоведения на борту производит расчет траектории движения, обеспечивающей минимизацию затрат энергии на тягу. Кроме того, системой решается задача подбора позиций контроллера машиниста, обеспечивающих существенное приближение к оптимальной траектории при минимизации числа переключений.

В настоящее время такими системами оборудовано более 20 локомотивов серии ЧС7, курсирующих с одной-двумя остановками или в безостановочном графике с пассажирскими поездами по участкам Москва-Вязьма (белорусское направление, 243 км), Москва-Сухиничи (киевское направление, 261 км).

Внедрение систем автоведения электропоезда изначально предполагало снижение расхода электроэнергии оборудованными составами в среднем на 5%. Реально экономия электроэнергии в разных депо составила от 3 до 18% от существующих норм расхода, что подтвердилось специально проведенными замерами в контрольных поездках. Сегодня свыше 1200 пригородных составов оборудованы различными модификациями систем автоведения. По предварительным оценкам, эксплуатация электропоездов с такими системами на борту только за 2000 год сэкономит электроэнергии на 237 млн. руб. при действующих тарифах.

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

Список использованной литературы

1. Банди. «Методы оптимизации». Поисковый метод Хука-Дживса.

2. Журнал «Современные технологии автоматизации», №4, 2000 г., с. 60-69.

Размещено на Allbest.ru