Автоматизация тендерных закупок фонда гос имущества

1.2.4 Основные  требования к разрабатываемому  программному обеспечению.

СППР для торгово-закупочного  предприятия должна  удовлетворять  следующим общим требованиям:

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

При проектировании и  разработке информационного обеспечения  необходимо решить такие задачи, как:

• определение состава данных, используемых при решении комплексов задач и их формализация;
• унификация входной и выходной информации, определение рациональных форм документооборота;
• разработка способов представления и хранения информации на всех этапах ее движения и обработки;
• разработка способов контроля вводимой информации;
• определение состава и структуры нормативно-справочной информации.

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

1.3 Выбор и  обоснование математического метода  решения задачи

1.3.1 Аналитический  обзор состояния проблемы

Чтобы найти  оптимальный заказ по закупочной стоимости необходимо учитывать не только минимальные цены товаров, но и скидки, предлагаемые поставщиками на общую стоимость закупки. Таким образом, оптимальным заказом будет компромисс между минимальными ценами товаров и скидками на стоимость закупаемых у поставщиков партий товаров. Чтобы найти этот компромисс надо проанализировать все возможные варианты решений задачи. Такой подход называется методом перебора  (см. п.1.3.3). Но из-за большого размера области значений алгоритм будет работать очень долго. Следовательно надо искать другой подход к решению задачи.

Функция, составленная по нашей задаче, не является линейной. Поэтому для решения этой задачи не могут использоваться методы линейного  программирования. При использовании метода нелинейного программирования, градиентного спуска (см. п.1.3.3), будет найдено неоптимальное решение, так как, достигнув локального экстремума алгоритм останавливается, и, следовательно, для поиска глобального оптимума потребуются дополнительные усилия. Поэтому для решения поставленной задачи требуется применение кокого-либо другого алгоритма.

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

1.3.2 Генетические  алгоритмы

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

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

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

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

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

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

1.3.3 Возможные  случаи применения генетического  алгоритма 

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

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

Но бывают случаи, когда  генетический алгоритм не работает эффективно.

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

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

Комбинируя переборный и градиентный методы, можно получить хотя бы приближенное решение, точность которого будет возрастать при  увеличении времени расчета. Генетический алгоритм является таким комбинированным методом. Механизмы скрещивания и мутации аналогичны переборной части метода, а отбор лучших решений - градиентному спуску.

1.3.4 Символьная  модель генетического алгоритма

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

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

Каждая хромосома (строка) представляет собой конкатенацию ряда подкомпонентов называемых генами. Гены располагаются в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями. В представлениях с бинарными строками, ген - бит, локус - его позиция в строке, и аллель - его значение (0 или 1). Биологический термин "генотип" относится к полной генетической модели особи и соответствует структуре в генетического алгоритма. Термин "фенотип" относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров. Простой пример - задача максимизации функции от нескольких переменных.

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

Установить соответствие между генотипом и фенотипом  закодированных особей можно, разделив соответствующее двоичное целое  число на ( ). Например, 0000000000 соответствует 0/1023 или 0, тогда как 1111111111 соответствует 1023/1023 или 1. Оптимизируемая структура данных - N*10-битная строка, представляющая конкатенацию кодировок N переменных. Первая переменная размещается в крайних левых 10 разрядах, тогда как последняя – в правой части генотипа особи (N*10-битовой строке).

Генотип - точка в N*10-мерном хеммининговом пространстве, исследуемом генетическим алгоритмом. Фенотип - точка в N пространстве параметров.

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