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

ВВЕДЕНИЕ.

ГЛАВА ПЕРВАЯ. Задачи и проблемы симплексного поиска . . . . ^

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

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

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

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

1.5. Некоторые проблемы симплексного поиска

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

ГЛАВА ВТОРАЯ. Поиск с переменной стратегией.

2.1. Теоретические предпосылки поиска с переменной стратегией.

2.2. Алгоритм симплексного поиска с переменной стратегией

2.3. Постановка задачи выбора параметров поиска для алгоритма с переменной стратегией

2.4. Методика выбора параметров для алгоритмов симплексного поиска на этапе доводки

2.5. Методика выбора параметров для алгоритмов симплексного поиска на этапе восхождения

2.6. Алгоритм выбора параметров поиска.

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

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

ГЛАВА ТРЕТЬЯ. Исследование и построение алгоритмов симплексного поиска с элементами пороговой фильтрации и адаптации.

3.1. Многосвязные цепи Маркова и их использование для описания процесса поисковой оптимизации • • • • •

3.2. Модификация алгоритма последовательного симплексного метода с использованием пороговой фильтрации

3.3. Методика определения переходных вероятностей многосвязной цепи Маркова для алгоритмов с пороговой фильтрацией.

3.4. Статистические характеристики симплексного поиска для ПСМ с элементами пороговой фильтрации

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

3.6. Синтез оптимальных алгоритмов симплексногопоиска

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

ГЛАВА ЧЕТВЕРТАЯ. Оптимизация нестационарных объектов с использованием алгоритмов симплексного поиска

4.1. Симплексные методы поиска с учетом контролируемых возмущений.

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

4.3. Статистические характеристики поиска при дрейфе цели вдали от экстремума

4.4. Исследование алгоритмов симплексного поиска с применением многосвязных цепей Маркова при отслеживании дрейфующей цели.

4.5. Алгоритм для определения статистических характеристик симшюксного поиска при отслеживании дрейфующей цели.

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

ГЛАВА ПЯТАЯ. Симплексный поиск в задачах оптимизации и идентификации. . П

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

5.2. Математическое обеспечение и функциональная структурная схема АСО.-^

5.3. Алгоритм управления положением анода

5.4. Оптимальное управление межполюсным расстоянием

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

5.6. Оптимизация геометрии однофазных асинхронных двигателей с экранированными полюсами (АДЭ) и активным распределенным слоем (АРС) статора . . Выводы к пятой главе.;

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

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

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

Разработка инвариантных и адаптивных методов оптимизации и идентификации, повышение их работоспособности, создание алгоритмов и программ этих методов для использования в АСУ ТП, построенных на базе современных средств вычислительной техники, позволяет преодолевать эти трудности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Разработаны методики для определения переходных вероятностей многосвязных цепей Маркова, описывающих процесс поисковой оптимизации.

7. Разработан алгоритм, позволяющий автоматизировать анализ поисковых систем, построенных на базе алгоритмов симплексного поиска, на этапе отслеживания цели.

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

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

АСУ ТП.

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

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

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

ЗАКЛЮЧЕНИЕ

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

2. Дамбраускас А.П., Кошаев О.В. Алгоритм симплексного поиска с переменной стратегией,- В кн.: Алгоритмы и программы. М.: ВНТИЦ, ГФАП СССР, 1980, £ 6(38), с.18-19.

3. Дамбраускас А.П., Кащеев В.А., Кошаев О.В., Пахомов С.В., Ткачев Н.Н. Адаптивный алгоритм активно-пассивного симплексного гоиска.- В кн.: Алгоритмы и программы. М.: ВНТИЦ, ГФАП СССР, 1978, № (26), с.39-42.

4. Разработка автоматизированной системы оптимизации процесса электролиза алюминия (технический проект, ч.1, т.1). Отчет НИР, !Ь гос.регистр.76030438. Красноярск: КПИ, 1978, 275 с.

5. Разработка автоматизированной системы оптимизации процесса электролиза алюминия (технический проект, ч.П). Отчет НИР,гос.регистр.76030438. Красноярск: КПИ, 1979, 227 с.

6. Дамбраускас А.П., Кошаев О.В. Алгоритм симплексного поиска с переменным шагом.- В кн.: Алгоритмы и программы. М.: ВНТИЦ, ГФАП СССР, 1980, № 6(38), с.19-20.

7. Применение симплексного метода для оптимизации режимов работы электролизера. Отчет НИР, № гос.регистр.74062843. Красноярск: КПИ, 1975, 63 с.

8. Применение экспериментально-статистических методов для оптимизации и идентификации электролиза алюминия. Отчет НИР, В гос.регистр.75009144. Красноярск: КПИ, 1975, 42 с.

9. Применение экспериментально-статистических методов для оптимизации и идентификации электролиза алюминия. Отчет

10. НИР, № гос.регистр. 75009144, Красноярск: КПИ, 1976, 78с.

11. Разработка автоматизированной системы оптимизации процесса электролиза алюминия. Отчет НИР, J6 гос.регистр.76030438. Красноярск: КПИ, 1977, 140 с.

12. Встовский А.Л., Кошаев О.В. Определение оптимальной геометрии торцевого электродвигателя.- В кн.: Оптимизация режимов работы систем электроприводов. Красноярск: КРУ, КПИ, 1978, с.71-74.