|
|
Приведем список основных подпрограмм модуля.
В секции private класса TForm1 находятся следующие методы:
Процедура BringToArrs – занесение данных прайс-листов в динамические массивы.
Процедура SetSellMatr – заполнение матрицы SellMatr. В матрице элемент равен 0, если в i-ом прайс-листе не предлагается товар j, и 1, если в i-ом прайс-листе товар j предлагается.
Функция SupplSell – проверка, предлагает ли указанный поставщик (соответствующий ему прас-лист) указанный товар. Если да, то функция возвращает true, иначе – false.
Процедура Calc_BringToDB – вычисляет сумму закупки по всему заказу с учетом скидок и общую скидку на эту сумму, а также другие необходимые значения и заносит все результаты в базу выходных данных.
Процедура SolverForOne – формирование заказа на закупку товаров для одного указанного поставщика.
В секции public класса TForm1 находятся следующие методы
Функция SuDiscountCost – возвращает стоимость закупки с учетом скидки у поставщика, которому соответствует указанный прайс-лист.
Процедура MinMaxSolver(min:boolean . . .) -- формирование заказа на закупку товаров по минимальной цене, если min=true, или по максимальной цене, если min=false.
Рассмотрим теперь функционирование модуля "Формирование заказа с помощью генетического алгоритма ".
После выбора в окне модуля "Формирование заказа простыми методами " метода формирования заказа "Генетический алгоритм по минимальной стоимости" и нажатия кнопки <Сформировать> появляется окно модуля "Формирование заказа с помощью генетического алгоритма ", которое показано на рисунке 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; в атрибутах прайс-листов установлены скидки; ;количество листов заказа равно четырем и суммарная потребность -- четыре медикамента в различных количествах.
Тестировалась выборка данных в динамические массивы при различных ситуациях: задавались существующие и несуществующие даты листов, выборка по отметке производилась при наличии отмеченных листов и наоборот.
При тестировании работы методов формирования заказа вычислялись заранее выходные данные для каждого из методов формирования заказа, а затем запускались сами методы, и результаты их работы сравнивались с рассчитанными.
Затем в прайс-листах выборочно у товаров ставились нулевые цены – значит, что товар не предлагается, и опять проходило тестирование.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18
При использовании материалов активная ссылка на источник обязательна.