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

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

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

Задачи 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 переменных. Только преимущество канонического роя частиц еще более заметно, а отставание классического алгоритма по скорости работы становится весьма ощутимым.