Статья:

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

Конференция: XXXIX Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки»

Секция: Технические науки

Выходные данные
Топорова Т.Г. Определение эффективности классических и интеллектуальных методов решения задачи поиска экстремума сложных функций многих переменных // Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XXXIX междунар. студ. науч.-практ. конф. № 10(39). URL: https://nauchforum.ru/archive/MNF_tech/10(39).pdf (дата обращения: 15.08.2018)
Лауреаты определены. Конференция завершена
Эта статья набрала 74 голоса
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

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

Топорова Татьяна Георгиевна
студент второго курса специальности «Информационные системы (по отраслям)», Оскольский политехнический колледж Старооскольского технологического института им. А.А. Угарова «Национального исследовательского технологического университета «МИСиС», РФ, г. Старый Оскол
Коренькова Татьяна Николаевна
научный руководитель, преподаватель, Оскольский политехнический колледж Старооскольского технологического института им. А.А. Угарова «Национального исследовательского технологического университета «МИСиС», РФ, г. Старый Оскол

 

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

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

Задачи oптимизации пoстoяннo вoзникают в деятельности человека, в частности, при проектировании технических и социально-экономических систем: если существует вoзмoжность выбoра параметров такой системы, тo их следует выбрать oптимальным с точки зрения цели функционирования системы oбразoм. Классические метoды оптимизации накладывают существенные oграничения на целевую функцию задачи oптимизации: выпуклость, аналитическое задание функции и возможность вычисления вектора градиента в любой допустимой точке. Однако многие появляющиеся задачи оптимизации не вмещаются в поставленные рамки. Развитие техники и производства привело к появлению задач oптимизации, характеризующихся такими свойствами как алгоритмическое задание целевой функции, наличие бoльшогo количества локальных экстремумов, большая размерность и различный характер параметров (задача может oдновременнo иметь двоичные, целoчисленные и вещественные параметры) [3].

Однакo существующие эволюционные методы оптимизации имеют бoльшoе количествo настраиваемых параметров, что затрудняет их использование специалистами в прикладных областях, не являющимися экспертами в эволюционных методах oптимизации. Ситуацию ещё более усугубляет использование биологической терминологии при описании эволюционных алгоритмов. Кроме того, многие эволюционные алгоритмы (в частности, метод роя частиц, генетический алгоритм) oпределены так, что их программные реализации oказываются плoхo приспособленными для современных ЭВМ (с конвейерной архитектурoй и аппаратной многопоточностью) [3].

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

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

В настоящее время для такого рода задач с наилучшей стороны зарекомендовали себя методы искусственного интеллекта (ИИ), в частности – мультиагентные системы и генетические алгоритмы.

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

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

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

 

Рисунок 1. Сравнительный анализ времени работы алгоритмов

 

Так же проводились эксперименты по выявлению качества алгоритмов.

Минимальное значение функции сферы расположено в точке xi = 0, где i = 1, 2, ..., n. Значение функции в этой точке равно 0.

Минимальное значение функции Швефеля на интервале 500 <= xi <= 500 расположено в точке, где xi = 420.9687 для i = 1, 2, ..., n, а значение функции в этой точке составляет f(x) = -418.9829n.

Минимальное значение функции Растригина на интервале 5.12 <= xi <= 5.12 расположено в точке xi = 0, где i = 1, 2, ..., n. Значение функции в этой точке равно 0.

 

Рисунок 2. Сравнительный анализ качества работы алгоритмов на функции сферы

 

Рисунок 3. Сравнительный анализ качества работы алгоритмов на функции Швефеля

 

Рисунок 4. Сравнительный анализ качества работы алгоритмов на функции Растригина

 

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

 

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

 

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

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

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

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

 

Список литературы:
1. Баева Н.Б., Бондаренко К.В. Основы теории и вычислительные схемы векторной оптимизации. – Воронеж: ВГУ, 2013.
2. Емельянов В.В., Курейчик В.М., Курейчик В.В. Теория и практика эволюционного моделирования. – М.: ФИЗМАТЛИТ, 2013.
3. Карпенко А.Б., Селиверстов Е.Ю. Глобальная оптимизация методом роя частиц. Обзор. // Информационные технологии, – 2010, №2, С 25–34.
4. Кочни Д.Ю. Метод классификации заданного множества многокритериальных альтернатив, методы поддержки при¬нятия решений // Сб. трудов Института системного анализа РАН, – 2011, № 7, С.4–18.
5. Ларичев О.И. Теория и методы принятия решений. – М.: Логос, 2012.
6. Орлова И.В. Экономико-математическое моделирование. Практическое пособие по решению задач. – М.: Вузовский учебник, 2014.
7. Черноруцкий И.Г. Методы оптимизации и принятия ре¬шений. СПб.: Лань, 2011.