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

ВВЕДЕНИЕ.

ГЛАВА ПЕРВАЯ. Задачи, объекты,методы поисковой оптимизации. Проблемы симплексного поиска .II

1.1. Объекты поисковой оптимизации .II

1.2. Задачи поисковой оптимизации

1.3. Краткая характеристика методов поисковой оптимизации

1.4. Симплексные методы поисковой оптимизации

1.5. Критерии эффективности поиска

1.6. Проблемы симплексного поиска в условиях неопределенности

Выводы к первой главе.

ГЛАВА ВТОРАЯ. Повышение эффективности симплексного поиска с отражением одной вершины

2.1. Описание вероятностных свойств процесса поиска с помощью математического аппарата многосвязных цепей Маркова.

2.2. Симплексный поиск с распознаванием состояний

2.3. Синтез алгоритмов симплексного поиска с распознаванием состояний.

2.4. Пороговая фильтрация помех в алгоритмах симплексного поиска с распознаванием состояний

2.5. Повышение точности симплексного поиска

2.6. Алгоритм симплексного поиска с переменной стратегией и распознаванием состояний

2.7. Сравнение симплексного метода поиска с переменной стратегией и распознаванием состояний с другими методами поиска

Выводы ко второй главе

ГЛАВА ТРЕТЬЯ. Симплексный поиск с адаптацией числа отражаемых вершин.

3.1. Поиск со свободным отражением на каждом шаге постоянного числа вершин симплекса

3.2. Поиск со свободным отражением адаптивного числа вершин симплекса

3.3. Синтез алгоритмов с адаптацией числа отражаемых вершин симплекса

Выводы к третьей главе

ГЛАВА ЧЕТВЕРТАЯ. Симплексный поиск в задачах оптимизации динамических и нестационарных объектов в обстановке помех.

4.1. Влияние инерционности объекта на быстродействие поиска.

4.2. Симплексный поиск в задачах оптимизации динамических объектов.

4.3. Активно-пассивный симплексный поиск

4.4. Адаптивный алгоритм активно-пассивного симплексного поиска.

Выводы к четвертой главе.

ГЛАВА ПЯТАЯ. Применение симплексного поиска в задачах оптимизации и идентификации технологического процесса электролиза алюминия

5.1. Краткое описание технологического процесса электролиза алюминия

5.2. Математическое обеспечение и функциональная структура ACO.

5.3. Система управления составом электролита

5.4. Экстремальное управление процессом электролиза алюминия.

Выводы к пятой главе

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

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

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

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

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

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

В настоящей диссертационной работе на основе теоретического исследования процессов поисковой оптимизации решен ряд проблем, связанных с повышением эффективности методов симплексного поиска и созданием инженерной методики решения различных экстремальных задач в условиях неопределенности. Тема диссертации непосредственно связана с развитием экстремальных систем, с повышением эффективности автоматизированных систем оптимизации, а также с планами научно-исследовательских работ Минвуза РСФСР (приказ № 394 от 17.09.76) и Минцветмета СССР (протокол № 34 совещания у Министра от 20.12.78, план-график УГЭ Минцветмета СССР от 23.02.78, отраслевой план НИР Минцветмета СССР на 1980-1984 гг).

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

Разработка проблем симплексного поиска, основоположниками которого являются Спиндлей, Хекст и Химсворт, предложившие в 1962 году последовательный симплексный метод, была бы невозможна без теоретической основы экстремальных систем, созданной исследованиями В.Г.Горского, А.П.Дамбраускаса, С.В.Емельянова, В.В.Казакевича, А.А.Красовского, Г.К.Круга, Е.В.Марковой, Г.А. Медведева, М.Б.Моцкуса, В.В.Налимова, А.В.Нетушила, Б.Н.Петрова, Л.А.Растригина, В.П.Тарасенко, А.А.Фельдбаума, Я.З.Цыпкина, Д.Б. Юдина и других ученых.

Основные цели диссертации:

- развитие статистической теории симплексного поиска;

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

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

Диссертация состоит из введения, пяти глав, заключения, приложения и списка литературы.

Основные результаты диссертационной работы могут быть сформулированы следующим образом.

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

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

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

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

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

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

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

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

В промышленности: для оптимизации технологического процесса электролиза алюминия.

В проектно-конструкторских разработках: для оптимизации параметров антенных устройств и конструкций механизмов, в задачах проектирования АСУ ТП.

В научно-исследовательских работах: при идентификации объектов управления, разработке систем автоматического управления и проектирования.

Подтвержденный актами внедрения экономический эффект составляет 276 тысяч рублей.

Разработанные в диссертации методы оптимизации и управления входят в состав специального математического обеспечения автоматизированной системы оптимизации электролиза алюминия, которая внедряется на КрАЗе в соответствии с протоколом № 34 от 20.12.78 г. совещания у Министра цветной металлургии СССР.

ЗАКЛЮЧЕНИЕ

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

1. Растригин J1.А. Случайный поиск в процессах адаптации. Рига: Зинатне, 1973, 129 с.

2. Растригин Л.А. Системы экстремального управления. М.: Наука,1974, 630 с.

3. Батищев Д.И. Поисковые методы оптимального проектирования. М.: Советское радио, 1975, 216 с.

4. Моисеев Н.Н. Элементы теории оптимальных систем. М.: Наука,1975, 526 с.

5. Моцкус И.Б. Многоэкстремальные задачи в проектировании. М.: Наука, 1976, 216 с.

6. Островский Г.М., Волин Ю.М. Методы оптимизации сложных химико-технологических схем. М.: Химия, 1970, 311 с.

7. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972.

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

9. Современное состояние теории исследования операций. Под ред. Н.Н.Моисеева. М.: Наука, 1979.

10. Емельянов C.B., Борисов В.И., Малевич А.А., Черкашин A.M. Модели и методы векторной оптимизации."Итоги науки и техники". Техническая кибернетика, т.5. М.: ВИНИТИ, 1973, с.386-448.

11. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М.: Советское радио, 1975, 182 с.

12. Дамбраускас А.П., Кошаев О.В. Выбор параметров симплексного поиска (Алгоритмы и программы). Красноярск: КГУ, КПИ, 1977, 121 с.

13. Растригин Л.А. Случайный поиск в задачах оптимизации многопараметрических систем. Рига: Зинатне, 1965, 212 с.14