Фрагментарные генетические алгоритмы - Статья

ФРАГМЕНТНЫЕ ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫГенетические алгоритмы (ГА) относятся к средствам решения широкого круга задач оптимизации и структурного синтеза, причем для некоторых задач синтеза применение ГА практически является безальтернативным. К сожалению, эффективность ГА, определяемая погрешностью получаемых решений и затратами вычислительных ресурсов, не всегда оказывается удовлетворительной. И если проблемы, обусловленные высокой трудоемкостью ГА, в той или иной мере преодолеваются благодаря росту производительности используемых вычислительных средств, то опасность получения результатов невысокой точности остается основным недостатком ГА (поскольку, как правило, отсутствуют возможности оценки допущенных погрешностей). Одним из основных операторов, определяющих эффективность генетического поиска, является кроссовер (кроссинговер), его исследованию посвящено большое число работ.Фрагментами будем называть участки, на которые делятся хромосомы при кроссовере. В пределах каждого фрагмента выполняются свои операции выбора родительской пары и одноточечного кроссовера, но оценка целевой функции осуществляется по отношению ко всей хромосоме. На рис.2 показаны результаты применения ФК при решении некоторых тестовых задач: - синтез многостадийных расписаний (рис.2а); компоновка конструктивов в блоки (рис.2в) - здесь, в отличие от остальных задач, выполнялась максимизация целевой функции; Данные, представленные на рис.2, позволяют заключить, что имеется некоторое оптимальное значение L, лежащее в зависимости от характера задачи в диапазоне 2…10.В качестве тестовых задач использовались NP-трудные задачи дискретной оптимизации: · многостадийная задача синтеза расписаний (SP - Scheduling Problem); В задаче SP требуется составить расписание минимальной стоимости Z при соблюдении временных ограничений для обслуживания n работ с их распределением во времени и по имеющимся машинам. Каждая работа проходит q стадий обслуживания, на каждой стадии для работы выбирается одна из mk машин, k=1,…q, общее число машин равно M. Заданы матрица P=[pij], где pij - время обслуживания i-й работы на j-й машине. Заданы также времена и стоимости переналадок машин, цены одного часа работы каждой машины, временные ограничения на завершение обслуживания каждой работы.Результаты численных экспериментов представлены в таблице, в которой исследуемые методы обозначены четырехразрядным двоичным кодом x1,x2,x3,x4, причем x1 =1, если используется ФК; x2 =1, если применяется МР; x3=1 при применении ФМ; x4=1, если выполняется ФХ. В задаче SP достигнутое минимальное значение F целевой функции фиксировалось после 480 смен поколений, что соответствует приблизительно T=100…120 тысячам вычислений целевой функции. В задаче TS расчеты заканчивались после выполнения 200 тысяч оценок целевой функции, размер популяции N=60, Т=150, L=5. По полученным оценкам F целевой функции, представленным в колонках 6-9 таблицы, рассчитывались нормированные показатели полезности Kij исследуемых методов для задач SP, TS, PP: Kij=(Fmaxi-Fij)/( Fmaxi-Fmini), где Fmaxi, Fmini и Fij - максимальное, минимальное и полученное с помощью j-го метода значение целевой функции в i-й задаче, i=1,2,3.Введение в генетический алгоритм как фрагментного кроссовера, так и фрагментных макромутаций приводит к более точному решению задач.