После выбора в окне модуля
"Формирование заказа простыми методами " метода формирования заказа
"Генетический алгоритм по минимальной стоимости" и нажатия кнопки <Сформировать>
появляется окно модуля "Формирование заказа с помощью генетического алгоритма
", которое показано на рисунке 2.11.
|
|
Рис. 2.11 Окно модуля
"Формирование заказа с помощью генетического алгоритма "
|
|
В этом окне пользователь должен
настроить генетический алгоритм:
n ввести количество особей в популяции;
n выбрать операторы, которые должны
выполняться над особями популяции, и задать вероятность выполнения там, где это
необходимо;
n ввести количество выводимых наилучших
решений в базу данных заказов.
После нажатия кнопки <Старт ГА> генетический
алгоритм начинает свою работу в соответствии с выбранными установками.
На рисунке 2.12 показана блок-схема
работы генетического алгоритма.
Приведем список основных подпрограмм
модуля.
В секции private класса TForm2 находятся следующие методы:
1) Методы для преобразования кода Грея в десятичное
число:
Процедура SetGraySeq– генерация
последовательности переходов
Функция IntToBin – преобразование
числа (0..127) в двоичный код
Функция GrayToDec – Код Грея -->
Десятичное число
2) Методы реализации генетического алгоритма (ГА)
Функция SupplSellDrug – проверка,
предлагает ли указанный поставщик (значение гена -- порядковый номер
соотвествующий номеру прайс-листа поставщика) данный товар локус -- номер гена
в хромосоме, соответствующий номеру товара);
Функция SetFirstPopulat – генерация
хромосомного набора начальной популяции, удовлетворяющего требованиям,
предъявляемым к символьной модели задачи;
Функция SupplierCost -- возвращает
стоимость закупки данного товара без учета скидки у поставщика, прайс-лист
которого указан;
Функция OneFtnDegree – преобразование
строки в коде Грея в соответствующий ей вектор управляемых переменных и
вычисление общей скидки,стоимости с учетом скидок и степени приспособленности
особи;
Функция GetAvgDegree – вычисление
средней степени приспособленности по популяции;
Функция RemoveBeforeSkresch –
предварительное отстранение особей, имеющих степени приспособленности меньше
средней, от участия в скрещивании;
Процедура SetSelectVerSect –
вычисление отрезков распределения вероятностей выбора особей, которые могут
участвовать в скрещивании, на интервале [0,1];
Процедура SetOneVerSect – разбиение
интервала [0,1] на 2 отрезка: Р и 1-Р , где Р -- указанная вероятность;
Процедура SetEquipVerSect –
формирование отрезков распределения равных вероятностей на [0,1];
Функция Select – выбор объекта
(особи, гена, точки) на основе отрезков распределения вероятностей выбора;
Функция Elit – стратегия элитизма:
возвращает индекс особи в популяции, степень приспособленности которой
максимальна;
Процедура Interchange – обмен
хромосом участками, состоящими из одного или более генов (один участок первой
хромосомы ßà один участок второй хромосомы);
Процедура OnePntCrossover –
размножение по схеме "Одноточечный кроссовер";
Функция SetGeterList – формирует
список номеров гетерозиготных генов в родительских хромосомах и возвращает
порядковый номер в списке последнего номера гетерозиготного гена;
Процедура Dominant – вычисляет для
аллельных форм каждого гетерозиготного гена указанного родителя вероятность
доминантности, равную частоте данной аллельной формы в текущей популяции;
Процедура GenosRecomb – размножение
по схеме "Рекомбинация генов";
Функция PntMutatInGen – точечная
мутация в конкретном гене (Если мутированный ген в указанном локусе
удовлетворяет требованиям, предъявляемым к символьной модели задачи (см.
описание предыдущей функции), то функция возвращает true, иначе мутация
производится в каком-либо другом бите гена и т.д., до тех пор, пока
мутированный ген не станет удовлетворять требованиям задачи или, пока не будет
пройдено предельное число шагов. Если требования задачи так и не будут
удовлетворены, то выдается false, и значение переданного через параметр гена
остается неизменным.);
Процедура PntMutation – Точечная
мутация производится в случайно выбранном гене хромосомы до тех пор, пока
мутированный ген не станет удовлетворять требованиям задачи (см. функцию
PntMutatInGen); Если требования задачи так и не будут удовлетворены, то у особи
останется старый (немутированный) ген;
Процедура GenMutation – генная
мутация;
Процедура MacroPntMut -- макромутация
точечная (использует функцию PntMutation);
Процедура MacroGenMut – макромутация
генная (использует функцию GenMutation);
Процедура Inverse – инверсно-точечная
мутация (Если ген в новом локусе не удовлетворяет требованиям задачи, то он
подвергается точечной мутации до тех пор, пока не станет удовлетворять им (см.
функцию PntMutatInGen). Если требования задачи так и не будут удовлетворены, то
он заменяется на старый ген.);
Функция SetReprodGroup – формирование
репродуктивной группы по второй селекционной схеме (в репродуктивную группу
попадают те особи, у которых степень приспособленности больше или равна
средней);
Процедура NatureSelect – Естественный
отбор в (t_+1)-ю популяцию из репродуктивной группы по жесткой" схеме,
если isElit=false, иначе членами (t_+1)-й популяции будут все произведенные
особи плюс 1 элитная. Размер всех популяций одинаков, равен размеру первой.
Функция AllelDifference – функция
возвращает аллельное разнообразие популяции (граничные случаи: если все
хромосомы равны, то результат -- 0; если все аллели всех хромосом различны, то
результат -- 1);
Функция WorldLimToGraphic –
возвращает значение итоговой стоимости заказа с учетом скидок для графика
эволюции минимальной стоимости;
Функция ConvertFitness –
преобразование особи в вектор управляемых переменных;
Процедура BringToDB – занесение
результатов одного заказа (одного вектора управляемых переменных) в базу
данных;
2.4 Методы уменьшения затрат
машинного времени, методы отладки и тестирования
Реальные данные для разработанного
программного обеспечения занимают большие объемы: в одном рпайс-листе может
быть около пяти тысяч записей, листы заказов также могут содержать до тысячи
записей. Количество прайс-листов, хранимых в базе данных также велико – около
двухсот набирается несколько месяцев эксплуатации программы. Количество листов
заказа примерно такое же. Кроме того сформированные заказы и разнарядки имеют
большие объемы, так как они сохраняются для сравнения сформированных заказов
между собой.
Входными данными программы являются
прайс-листы и листы заказов. В процессе своей работы программа должна получать
информацию из листов заказа о потребностях в том или ином медикаменте и
прайс-листов – о наличии медикамента в листе и о цене медикамента, а также
происходит обращение к прайс-листам для того, чтобы узнать скидки,
предоставляемые поставщиком в прайс-листе. В процессе работы генетического
алгоритма обращений к базе данных особенно много, так как существующих решений
во много раз больше, чем для других рассматриваемых в работе методов, потому
что генетический алгоритм работает со скидками.
Для того, чтобы сократить затраты
машинного времени при работе программы был применен следующий подход – после
запуска программы пользователь указывает необходимые для рассмотрения
прайс-листы и листы заказа, и они перекачиваются в динамические массивы. В
результате этого программе не надо будет при поиске оптимального решения
обращаться к базе данных, что значительно увеличивает быстродействие программы.
Для отладки и тестирования программы
были применены следующие методы: установка контрольных точек в программе,
прогон программы по шагам на тестовых данных.
Тестовые данные для отладки и
тестирования небольшие: четыре прайс-листа, в каждом из которых предлагается по
пять медикаментов, причем цены в первом прайс-листе у всех товаров равны 1,1;
во втором – 2,2; в третьем – 3,3; в четвертом – 4,4; в атрибутах прайс-листов
установлены скидки; ;количество листов заказа равно четырем и суммарная
потребность -- четыре медикамента в различных количествах.
Тестировалась выборка данных в
динамические массивы при различных ситуациях: задавались существующие и
несуществующие даты листов, выборка по отметке производилась при наличии отмеченных
листов и наоборот.
При тестировании работы методов
формирования заказа вычислялись заранее выходные данные для каждого из методов
формирования заказа, а затем запускались сами методы, и результаты их работы
сравнивались с рассчитанными.
Затем в прайс-листах выборочно у
товаров ставились нулевые цены – значит, что товар не предлагается, и опять
проходило тестирование.
При отладке и тестировании работы
генетического алгоритма на каждом шаге выводились значения вех особей
популяции, их потомков, мутантов и т.д.; проверялось выполнение всех операторов
генетического алгоритма.
3 ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА
РАЗРАБОТАННОГО
ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
3.1. Испытание системы
Последней задачей дипломного проекта
должна быть апробация системы на реальном предприятии.
Реальным предприятием, как уже ранее
упоминалось, является Белгородский территориальный фонд ОМС. Здесь товарами
являются лекарственные средства, изделия медицинского назначения и расходные
материалы, а заказчиками – лечебно-профилактические учреждения города и
области. В настоящее время Белгородский территориальный фонд ОМС закупает
медикаменты на сумму двенадцать – тринадцать миллионов рублей.
Для испытания "Системы поддержки
принятия решений для формирования заказа на торгово-закупочном
предприятии" были взяты следующие исходные данные:
n прайс-листы 12 (двенадцати)
поставщиков;
n листы заказа, потребности которых в
общем объеме составляют 277 (двести семьдесят семь) медикаментов;
В итоге сложность алгоритма перебора,
формирующего заказ по минимальным ценам невелика: 12*277=3324. Но сложность
алгоритма перебора, формирующего заказ по минимальной стоимости с учетом
скидок колоссальна: ,
поэтому алгоритм перебора здесь неуместен. А генетический алгоритм находит оптимальное
решение или близкие к оптимальному решения за реальное время.
В ходе испытаний были сформированы
заказы всеми методами, реализуемыми в программе:
n по максимальным ценам;
n на одного поставщика;
n по минимальным ценам;
n генетический алгоритм по минимальной
стоимости учетом скидок.
Результаты работы генетического
алгоритма с различными настройками были сравнены с результатами работы других
методов на столбчатой диаграмме, предоставляемой в программе специально для
этих целей. Сравнительная оценка показала преимущество генетического алгоритма
при формировании заказа с учетом скидок над методами, не использующие этот
подход (см. рисунки 2.13, 2.14, 2.15, 2.16). Здесь порядок заказов,
сформированных различными методами такой же, как и при перечислении выше. На
рисунке 2.13 представлен первый эксперимент.
Рис. 2.13 Первый эксперимент
|
|
На рисунке 2.14 представлен второй
эксперимент.
На рисунке 2.15 представлен третий
эксперимент.
На рисунке 2.16 представлен четвертый
эксперимент.
3.2. Оценка надежности
Надежность работы разработанного
программного обеспечения была обеспечена за счет:
n написания триггеров для баз данных;
n написания для баз данных триггеров,
вызывающих исключения;
n введения различных ограничений в
базы данных;
n за счет проверки вводимой
пользователем информации при работе программы.
Триггеры в базах данных выполняют
действия, которые обеспечивают корректное заполнение баз данных, каскадные
обновления и многие другие удобства при работе с базами данных. Триггеры действуют
тогда, когда запись вставляется, изменяется или удаляется. Основные, имеющиеся
в базах данных триггеры указаны в описании баз входных данных (см. п. 2.3.3.2)
и описании баз выходных данных (см. п. 2.3.3.3).
Триггеры, вызывающие исключения,
выдают сообщения об ошибке тогда, когда пользователь пытается удалить из базы
данных необходимую для ее корректной работы информацию, например, на удаляемую
из таблицы запись есть ссылка в другой таблице.
Ограничения в базах данных применены
следующие:
n первичные ключи;
n ненулевые поля.
В установки программы пользователь
может ввести некорректную информацию: неправильно указать дату или число,
ввести дату несуществующих прайс-листов или листов заказа и т.д. Программа анализирует
введенную пользователем информацию и в зависимости от серьезности случая выдает
сообщение об ошибке и ждет нового ввода, выдает предупреждение и продолжает
работу, просто информирует и продолжает работу.
В результате использования вышеперечисленных
методов надежность программы повышается и устраняется возможность возникновения
фатальных ошибок при работе программы.
4 ОЦЕНКА ЭКОНОМИЧЕСКОЙ
ЭФФЕКТИВНОСТИ ПРОЕКТА
Применение
вычислительной техники на предприятии ведет к экономии затрат на заработную
плату за счет сокращения численности персонала, к уменьшению отчислений на
социальные нужды, экономии материальных ресурсов за счет сокращения количества
и унификации отчетных форм, приросту прибыли за счет выполнения дополнительных
объемов работы, сокращению потерь за счет принятия своевременных и обоснованных
управленческих решений. В результате применения вычислительной техники с
соответствующим программным обеспечением облегчается труд работников
предприятия и увеличивается быстрота принятия управленческих решений.
Одним из
основных аспектов деятельности любого торгово-закупочного предприятия является
закупка различных товаров. Получив серию заказов, в торгово-закупочном
предприятии анализируют предложения фирм-поставщиков и поступившие заказы и составляют
итоговый заказ на закупку товаров у поставщиков.
Одним из методов
формирования заказа является метод "по минимальным ценам товаров"— в
заказ включается те поставщики, у которых цены на требуемые товары минимальны.
Многие
предприятия-поставщики предоставляют гибкие системы скидок.
Таким образом предприятие может
добиваться уменьшения общей стоимости приобретаемой продукции не за счет выбора
поставщика, предлагающего товар по минимальной цене, но за счет скидок,
варьируя размер партий закупаемых товаров у определенных поставщиков, что может
привести к тому, что стоимость заказа, сформированного с учетом скидок
будет меньше стоимости заказа, составленного по минимальным ценам.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
|