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

Введение
Генетические алгоритмы (ГА) – это один из современных способов решения задач функциональной оптимизации в различных предметных областях, предполагающий путем манипуляций с различными наборами входных параметров получение оптимальных наборов-решений. Оптимальность оценивается с помощью заданного алгоритма или формулы путем отыскания минимума или максимума в рамках построенной математической модели.
Генетические алгоритмы, наряду с эволюционными стратегиями, алгоритмами генетического программирования и др., являются представителями класса эволюционных алгоритмов [17, 5]. Эти алгоритмы берут начало в работах Л. Фогеля [12] и Дж. Холланда [14], где было предложено использовать биологический процесс эволюции для получения эффективных структур и обучения искусственного интеллекта. Почти одновременно А.Г. Ивахненко и Л.А. Растригиным были созданы методы группового учена аргументов [6] и случайного поиска [10], где тоже были использованы принципы эволюции и случайной мутации.
Для решения минимаксных задач существует множество классических математических методов, но при огромном количестве входных параметров и высокой сложности математической модели многие из них не справляются с поиском решения за разумное время или с использованием разумного количества вычислительных ресурсов. И в этих случаях возможно применение генетических алгоритмов. ЭА, в частности и ГА, могут быть использованы в решении различных задач в управлении, планировании, проектировании, задачах нечеткой логики и других [2,7,8,11].
Задача оптимизации издержек деятельности современного предприятия требует и оперативности, и невысокой стоимости, и низкой потребности в вычислительных, алгоритмических и человеческих ресурсах.
Целью настоящей работы является решение задачи об оптимальном обеспечении предприятия материальными ресурсами, максимизации возможной прибыли, сокращения издержек.
Для достижения цели работы было необходимо решить ряд задач:
1) Построить экономико-математическую модель для оценки обеспеченности предприятия ресурсами;
2) Осуществить исследование классических и генетических алгоритмов поиска оптимального решения;
3) Построить генетический алгоритм для решения полученной задачи и создать программный код алгоритмов;
4) Проанализировать результаты математического моделирования.
Первая глава работы содержит в себе понятие генетических алгоритмов, их сравнение с классическими алгоритмами и обоснование большей эффективности применение генетических алгоритмов в рассматриваемой предметной области.
Вторая глава посвящена описанию построения экономико-математической модели и описанию применения генетических алгоритмов для решения практических задач на основе созданной модели.
Третья глава описывает программную реализацию алгоритма, включая описание входных и выходных данных, содержит результаты работы программы для различных наборов входных параметров и анализ полученных результатов.



 
Глава 1. Генетические вычисления
1.1. Сущность эволюционных вычислений
Генетические алгоритмы появились уже достаточно давно, но прежде чем перейти к их описанию рассмотрим несколько классических алгоритмов решения задач оптимизации и оценим причины, по которым генетические алгоритмы появились и становятся всё более популярны.
Прежде всего следует заметить, что многопараметрические задачи оптимизации получили свое решение в современном виде только с развитием вычислительной техники, и лишь тогда, когда компьютеры стали доступны настолько, чтобы применяться не только в узкоспециализированных научных задачах, но и в более прикладных. Естественным образом это оказались задачи статистического анализа и прогнозирования, задачи оптимизации различных социальных и экономических процессов.
Основные, по частоте применения, численные методы решения оптимизационных задач следующие:
Задача линейного программирования и метод наименьших квадратов. Задача оптимизации сводится к решению систем линейных алгебраических уравнений. Методы давно известны и прекрасно зарекомендовали себя в задачах интерполяции, однако для задач предсказания (экстраполяции) используются редко. Оба метода прекрасно зарекомендовали себя при решении задач оптимизации с небольшим количеством параметров, однако вычислительная сложность алгоритма [Зависимость времени работы алгоритма от размерности задачи и вычислительной сложности приведена в Приложении 1.] довольно высока (она составляет O(n2), где n – размерность задачи, соответствующая числу входных параметров) и особенности методов не всегда даже в теории позволяют достичь заданной точности вычислений.
Симплекс-метод. Метод был разработан специально для решения оптимизационных задач, позволяет найти точное решение за конечное число шагов. Но вычислительная сложность алгоритма составляет O(n3), что ограничивает его использование в практических задачах. Однако если требуется найти решение не с заданной точностью, а точное – у этого метода нет альтернативы. Симплекс-метод является итерационным методом.
Метод проективного градиентного спуска (в сегодняшних теориях изучается и применяется как метод проксимального градиентного спуска). Решением оптимизационной задачи является набор параметров, лучшим образом удовлетворяющий условию максимизации (минимизации) заданной функции, являющейся моделью системы. Алгоритм является итерационным, на каждом шаге его работы происходит переход от начальной точки (начального значения параметров) к новой, при этом новое значение вычисляется на основе градиента целевой функции в «старой» точке, то есть значение параметров обновляется таким образом, чтобы новая полученная точка была ближе к искомому экстремуму функции. Алгоритм имеет вычислительную сложность O(n3), является достаточно исследованным и стабильным, поэтому часто используется.
Существуют и другие численные методы решения оптимизационных задач, но все их объединяет одно – их вычислительная емкость достаточно высока, то есть поиск точного решения или решения с заданной точностью может потребовать значительного времени при росте размерности задачи (при введении в рассмотрение новых параметров, по которым требуется оптимизация системы). Именно это и привело к дальнейшим исследованиям, результатом которых стало появление эволюционных вычислений.
Идея эволюционных вычислений позаимствована в природных процессах смены поколений живых существ и использует такие понятия (основанные на генетике), как «популяция», «скрещивание», «мутация», «выживание», «селекция» (отбор) и другие. Генетические алгоритмы являются подвидом эволюционных вычислений, их особенности обозначим ниже, а для начала требует описание суть работы алгоритма эволюционных вычислений.
В общем случае для решения какой-либо задачи оптимизации можно просто перебрать всё возможное множество решений. Но это звучит гораздо проще, чем реализуется на практике, потому что возможны ситуации, когда количество возможных решений задачи бесконечно, а осуществить бесконечный перебор невозможно. Поэтому эволюционные алгоритмы (и генетические, как их подвид) перебирают не все возможные решения задачи, а только лучшие из них. Алгоритм эволюционных вычислений имеет линейную сложность O(n), является итерационным и состоит из следующих условных «шагов»: