РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ РАНЖИРОВАНИЯ И ОПТИМИЗАЦИИ ТЕНДЕРНЫХ ТОРГОВНА ОСНОВЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

Дмитриева О.А., Волошинова Д.C.

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

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

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

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

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

Для участия в тендере по выполнению m работ j=1..m, соревнуются n-компаний i=1..n. Известно что i-ый участник тендера за выполнение j-й работы требует платы х_ij. Критерием отбора предприятий является общая стоимость выполнения работ в указанные сроки. Группировка ключевых параметров в вектор переменных придает им статус генетической информации. Рядом стоящие фрагменты не отделяются друг от друга какими-либо маркерами, но при декодировании хромосомы в вектор переменных на протяжении всего моделируемого периода эволюции применяется одна и та же маска картирования. Таким образом, для кодирования информации о предприятии используется хромосома, содержащая в себе информацию об участниках, претендующих на выполнение различных работ. Применяется бинарное двухбитовое кодирование каждого элемента массива, при котором можно не только описать все указанные варианты, но и оставить резерв для дальнейшей модификации алгоритма при его адаптации. Таким образом генерируется исходная популяция бинарных хромосом: всевозможные сочетания участников в позициях выполнения различных работ. Из них выбираются претенденты на скрещивание, т.е. наборы участников, у которых общая стоимость выполнения работ наименьшая. В отличие от других методов оптимизации, используемые в работе генетические алгоритмы анализируют различные области пространства решений одновременно и более приспособлены к нахождению новых областей с лучшими значениями целевой функции за счёт объединения квазиоптимальных решений из разных популяций

Литература