Зачем решать экстремальные задачи

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

К сожалению, не всегда можно положиться на интуицию. Допустим Вы сотрудник коммерческой фирмы и отвечаете за рекламу. Затраты на рекламу в месяц не должны превышать 10 000 денежных единиц (д.е). Минута радиорекламы стоит 5 д.е., а телерекламы 90 д.е. Фирма намерена использовать радиорекламу в три раза чаще чем телерекламу. Практика показывает, что 1 минута телерекламы обеспечивает объём продаж в 30 раз больший чем 1 минута радиорекламы.

Быстрый и простой алгоритм требующий модификации

Среди методов решения задачи коммивояжёра метод ближайшего соседа привлекает простотой алгоритма. Метод ближайшего соседа в исходной формулировке заключается в нахождении замкнутой кривой минимальной длины, соединяющей заданный набор точек на плоскости [1]. Моё внимание привлекла наиболее распространённая реализация данного алгоритма в пакете Mathcad, размещённая в сети на ресурсе [2]. Сама реализация не совсем удобна, например, нельзя вывести матрицу расстояний между пунктами или проанализировать альтернативные маршруты.

На ресурсе [2] приведена следующая вполне справедливая критика данного метода. «Маршрут не оптимальный (не самый короткий) и сильно зависит от выбора первого города. Фактически не решена задача коммивояжера, а найдена одна гамильтонова цепь графа». Там же предложен путь некоторого усовершенствования метода ближайшего соседа. «Следующий возможный шаг оптимизации — «развязывание петель» (ликвидация перекрестий). Другое решение — перебор всех городов (вершин графа) в качестве начала маршрута и выбор наикратчайшего из всех маршрутов». Однако реализация последнего предложения не приведена. Учитывая все перечисленные обстоятельства, я решил реализовать приведенный алгоритм на Python и при этом предусмотреть возможность выбора начального пункта по критерию минимальной длины маршрута.

В поисках простой модели ПИД регулятора с объектом

Моделированию работы ПИД регулятора посвящено большое количество публикаций в сети. Лидирует проектирование моделей ПИД регулятора с применением Matlab Simulink [1,2] (134 миллиона ссылок в yandex). Сам процесс создания модели какой-то однообразный. В модель переносят всё новые и новые блоки. Одно движение ручного манипулятора и нате вам ПИД контролер, ещё одно и вот передаточная функция объекта. Соединяешь блоки, настраиваешь параметры, готовишь вычислитель. Да, возможностей много, но как-то слишком всё искусственно. И уже становится совсем непонятным к чему тут дифференциальные уравнения, методы их решения и то операционное исчисление, которым долго морочили голову. Ищу реализацию ПИД в Mathcad, тут ссылок в том же yandex, поменьше, всего то 81 миллион, а математики и формул побольше. Рассматриваю пример ПИД, поставляемый вместе с пакетом Mathcad 14.


В качестве объекта колебательное звено. Много умных объяснений, но в итоге два оператора laplace и invlaplace. Общая передаточная функция имеет в числителе вторую степень оператора, а в знаменателе четвёртую. Чтобы операторы laplace и invlaplace сработали, когда подключены все три составляющих ПИД, находят ещё и корни знаменателя передаточной функции, эти корни комплексно сопряжённые.



Теперь ищу реализацию ПИД на Python. Тихо радовался 97 миллионам результатов, но не долго. О Python 2.7 только применительно к прошивке Arduino на примере ESP32. Но и это переполняет сердце гордостью за Python.

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

Проблема

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

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

Адаптивность методов повышения точности динамических измерений следует понимать, как использование прогнозирования значений дисперсий и погрешности для следующего цикла измерений. Такое прогнозирование осуществляется в каждом цикле измерений. Для этой цели применяются фильтры Винера, работающие в частотной области. В отличии от фильтра Винера, фильтр Калмана работает во временной, а не в частотной области. Фильтр Калмана был разработан для многомерных задач, формулировка которых осуществляется в матричной форме. Матричная форма достаточно подробно описана для реализации на Python в статье [1], [2]. Описание работы фильтра Калмана, приведенная в указанных статьях, рассчитана на специалистов в области цифровой фильтрации. Поэтому возникла необходимость рассмотреть работу фильтра Калмана в более простой скалярной форме.

Картинки из сети, качество желает лучшего, но они достаточно точно отражают суть опыта по визуализации фигур. Зри в корень – основа мудрости поколений.

Немного истории

Ещё в школе на уроках физики я вглядывался в осциллограф, на экране которого, сменяя друг друга, появлялись разные фигуры: сначала простые – линия, парабола, круг, эллипс, потом фигуры становились всё более насыщенные непрерывными волнообразными линиями, напоминающие мне кружева. Автором этого кружевного дива был Жюль Антуан Лиссажу французский физик, член — корреспондент Парижской АН (1879) [1]. Сами фигуры — это замкнутые траектории, прочерчиваемые точкой, совершающей одновременно два гармонических колебания в двух взаимно перпендикулярных направлениях [2]. Думаю, что в те далёкие от современности годы основной заслугой Жюля, кроме конечно накопленных опытом знаний математики и физики, была простая механическая визуализация этих фигур подручными средствами. Захотелось конструировать подобно Жулю максимально просто и наглядно, реализовать его идеи применительно к современной задаче линейных измерений. Но сделать это путём математического моделирования с графической визуализацией его результатов на Python. Но сначала рассмотрим классический вариант [3] построения фигур.

Введение

В статье [1] я в строгом соответствии с общеизвестной теорией колебательных процессов рассмотрел колебательное звено, построив переходные процессы с применением библиотек SymPy и NumPy.

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

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

Задача

В статья использованы возможности пакета SymPy совместно с пакетом NumPy. Всё сводиться к преобразованию символьных выражений в функции способные работать с другими модулями Python.

Процесс решения дифференциальных уравнений становиться наглядным и хорошо контролируемым на каждом этапе вычислений. Следует отметить, что колебательное звено в разных интерпретациях обсуждается в сетях [1,2]. Например, в [3] приводиться модель колебательного звена с подробным исследованием переходных процессов.

Надеюсь, что подобные исследования колебательного звена на Python найдут своих сторонников.

Цель работы

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

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

Зачем это нужно

Метод гармонической линеаризации широко используется для анализа нелинейных систем [1]. Этот метод используется для определения условий возникновения автоколебаний в системах второго и более высокого порядка. При гармонической линеаризации должны выполняться два следующих условия. Замкнутая линейная система должна состоять из двух частей ─ линейной и нелинейной. Линейная часть должна обладать хорошими фильтрующими свойствами для высших гармоник[2]. Системы автоматического управления и регулирования содержат исполнительные механизмы, содержащие нелинейные элементы, поэтому их анализ является весьма актуальной проблемой.

Основной алгоритм

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

Известные реализация латентно-семантического анализа (LSA) средствами языка программирования Python [1,2] обладают рядом существенных методических недостатков. Не приведены корреляционные матрицы слов и документов. Эти матрицы позволяют выявить скрытые связи. Отсутствует кластерный анализ для распределения слов и документов. Нет гибкой графической реализации для анализа семантического пространства, что крайне осложняет анализ результатов. Пользователь не имеет возможности оценить влияние исключения слов, которые встречаются один раз, метода определения семантического расстояния между словами и документами. Более того, могут возникать ситуации, когда после исключения слов, встречающихся только один раз, нарушается размерность частотной матрицы и её сингулярное разложение становиться невозможным. Пользователь получает сообщение об ошибке, не понимая их причин сетуя на недостатки программных средств Python.

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

Короткая история метода

В короткой публикации [1] под названием “Авторство писателей можно узнать по специальной формуле” сообщалось, что в научном издании «New Journal of Physics», группа шведских физиков из университета Умео под руководством Себастьяна Бернгардсона описала новый метод, который позволяет на основе статистических данных определить автора текста. Исследователи проверяли, как в текстах трех писателей — Томаса Харди, Генри Мелвилла и Дэвида Лоуренса — реализуется так называемый закон Ципфа. Исследователи обнаружили, что частота появления новых слов по мере роста объема текста меняется у разных авторов по-разному, причем эта закономерность не зависит от конкретного текста, а только от автора.

Это сообщение было опубликовано 11.12.2009, а, более двадцати лет тому назад, Джон Чарльз Бейкер [2] ввел единицу для измерения способности автора использовать новые слова (здесь понятие «новые» трактуется как ранее не используемые в данном тексте). Джон доказал, что указанная единица является индивидуальной характеристикой автора.

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

Зачем это нужно

Законы Зипфа оописывают закономерности частотного распределения слов в тексте на любом естественном языке[1]. Эти законы кроме лингвистики применяться также в экономике [2]. Для аппроксимации статистических данных для объектов, которые подчиниться Законам Зипфа используется гиперболическая функция вида:

(1)

где: a.b – постоянные коэффициенты: x – статистические данные аргумента функции (в виде списка): y- приближение значений функции к реальным данным полученным методом наименьших квадратов[3].

Обычно для аппроксимации гиперболической функцией методом логарифмирования её приводят к линейной, а затем определяют коэффициенты a,b и делают обратное преобразование [4]. Прямое и обратное преобразование приводит к дополнительной погрешности аппроксимации. Поэтому привожу простую программу на Python, для классической реализации метода наименьших квадратов.