Отправить статью по E-mail Об одном методе поиска глобального экстремума непрерывной функции на симплексе
- Авторы: Лившиц М.Ю.1, Сизиков А.П.1
-
Учреждения:
- Самарский государственный технический университет
- Выпуск: Том 20, № 4 (2016)
- Страницы: 755-768
- Раздел: Статьи
- URL: https://ogarev-online.ru/1991-8615/article/view/20554
- DOI: https://doi.org/10.14498/vsgtu1500
- ID: 20554
Цитировать
Полный текст
Аннотация
Рассматривается невыпуклая задача математического программирования, допустимой областью которой является симплекс. Для приближенного решения задачи предложен двухэтапный алгоритм. На первом этапе определяется область глобального оптимума, на втором осуществляется локальная «доводка» решения. Первый этап реализуется методом Ψ-преобразования, который менее чувствителен к размерности задачи, чем прямой случайный поиск. Метод состоит в построении и использовании Ψ-функции. Построение Ψ-функции осуществляется эмпирически, по результатам статистических испытаний. Для проведения испытаний используется генератор случайных точек, равномерно распределенных в допустимой области. Получение равномерного распределения в симплексе осуществляется путем аффинных и линейных преобразований точек, равномерно распределенных в единичном гиперкубе. Для уточнения приближенного решения, полученного на первом этапе, применяется метод отражения правильных симплексов. Алгоритм представляет собой череду серий. Каждая очередная серия начинается с уменьшения длины ребра «рабочего» симплекса и переноса последнего в область лучшей точки предыдущей серии. Рассматриваемая задача имеет важное прикладное значение. К ней сводятся задачи смешения, возникающие в нефтепереработке, нефтехимии, строительстве. В статье представлен пример использования разработанного алгоритма для оптимизации компонентного состава углеводородной смеси.
Полный текст
Открыть статью на сайте журналаОб авторах
Михаил Юрьевич Лившиц
Самарский государственный технический университет
Email: mikhaillivshits@gmail.com
(д.т.н., проф.; mikhaillivshits@gmail.com), заведующий кафедрой, каф. управления и системного анализа теплоэнергетических и социотехнических комплексов Россия, 443100, Самара, ул. Молодогвардейская, 244
Александр Павлович Сизиков
Самарский государственный технический университет
Email: apsizikov@mail.ru
(к.э.н., доц.; apsizikov@mail.ru; автор, ведущий переписку), докторант, каф. управления и системного анализа теплоэнергетических и социотехнических комплексов Россия, 443100, Самара, ул. Молодогвардейская, 244
Список литературы
- Zhigljavsky A., Žilinskas A. Stochastic Global Optimization / Springer Optimization and Its Applications. vol. 9. Berlin: Springer, 2008. xiii+262 pp. doi: 10.1007/978-0-387-74740-8.
- Marti K. Stochastic Optimization Methods / Applications in Engineering and Operations Research. Berlin: Springer, 2015. xxiv+368 pp. doi: 10.1007/978-3-662-46214-0.
- Пантелеев А. В. Метаэвристические алгоритмы поиска глобального экстремума. М.: МАИ Принт, 2009. 159 с.
- M. Tim Jones AI Application Programming / Programming Series. Boston: Charles River Media, 2003. 496 pp.
- Савин А. Н., Тимофеева Н. Е. Применение алгоритма оптимизации методом имитации отжига на системах параллельных и распределённых вычислений // Изв. Сарат. унта. Нов. сер. Сер. Математика. Механика. Информатика, 2012. Т. 12, № 1. С. 110-116.
- Botev Z. I., Kroese D. P. Global likelihood optimization via the cross-entropy method, with an application to mixture models / Proceedings of the 2004 Winter Simulation Conference. Washington: IEEE, 2004. pp. 529-535. doi: 10.1109/wsc.2004.1371358.
- Ernst D., Glavic M., Stan G.-B., Mannor S., Wehenkel L. The cross-entropy method for power system combinatorial optimization problems / 2007 IEEE Lausanne Power Tech. Washington: IEEE, 2007. pp. 1290-1295. doi: 10.1109/pct.2007.4538502.
- Evans G. E., Keith J. M., Kroese D. P. Parallel cross-entropy optimization / 2007 Winter Simulation Conference. Washington: IEEE, 2007. pp. 2196-2202. doi: 10.1109/wsc.2007.4419854.
- Zhigljavsky A. Theory of Global Random Search / Mathematics and Its Applications (Soviet Series). vol. 65. Berlin: Springer, 1991. xviii+341 pp. doi: 10.1007/978-94-011-3436-1.
- Феоктистов А. Г., Горский С. А. Реализация метода мультистарта в пакете Градиент // Вестник НГУ Серия: Информационные технологии, 2007. Т. 5, № 2. С. 78-82.
- Cohoon J., Karro J., Lienig J. Evolutionary Algorithms for the Physical Design of VLSI Circuits / Advances in Evolutionary Computing / Natural Computing Series; eds. A. Ghosh, S. Tsutsui. Berlin: Springer, 2003. pp. 683-712. doi: 10.1007/978-3-642-18965-4_27.
- Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. М.: Физматлит, 2006. 320 с.
- Гладков Л. А., Гладкова Н. В. Особенности использования нечетких генетических алгоритмов для решения задач оптимизации и управления // Известия ЮФУ. Технические науки, 2009. № 4(93). С. 130-136.
- Skiena S. S. The Algorithm Design Manual. London: Springer, 2008. xvi+730 pp. doi: 10.1007/978-1-84800-070-4.
- Chichinadze V. K. Solution of nonlinear nonconvex optimization problems by Ψ-transformation method // Computers & Mathematics with Applications, 1991. vol. 21, no. 6-7. pp. 7-15.
- Чичинадзе В. К. Решение невыпуклых нелинейных задач оптимизации. Метод Ψпреобразования. М.: Наука, 1983. 256 с.
- Ахмадиев Ф. Г., Гильфанов Р. М. Математическое моделирование и оптимизация “состав-свойство” многокомпонентных смесей // Известия КГАСУ, 2012. № 2(20). С. 289-297.
- Новоселов А. А. Равномерное распределение на стандартном симплексе в Rn , http: //risktheory.novosyolov.com/lectures/unifs.pdf (дата обращения: 23.10.2016).
- Русин Ю. В. Алгоритмы статистического моделирования вероятностных распределений. Ярославль: ЯрГУ, 2006. 58 с.
- Зедгинидзе И. Г. Планирование эксперимента для исследования многокомпонентных систем. М.: Наука, 1976. 390 с.
- Чинакал В. О. Оптимизация рецептуры светлых нефтепродуктов / Оптимизация, исследование операций, бионика. М.: Наука, 1973. С. 198-205.
- Никитин В. А., Мусаев А. А. Оптимизация компаундирования углеводородных смесей // Тр. СПИИРАН, 2007. Т. 4. С. 327-336.
Дополнительные файлы
