ПОИСК Статьи Чертежи Таблицы Метод комбинирования эвристик из "Информационная поддержка наукоемких изделий. CALS-технологии " При решении задач оптимизации и структурного синтеза генетическими методами в первую очередь следует выбрать способ отображения в хромосоме структурных параметров. [c.221] Как показано выше, непосредственное представление структурных параметров часто порождает проблему недопустимых хромосом и вытекающую из этого необходимость использования операторов корректировки. Но корректировка снижает эффективность генетического поиска, поскольку приводит к дополнительным деформациям складывающихся в хромосомах полезных шаблонов (строительных блоков). [c.221] В НСМ используется возможность декомпозиции исходной задачи синтеза на ряд частных задач (подзадач). В исходной задаче требуется найти значения структурных параметров х.еХ, при которых целевая функция F(X) принимает экстремальное значение. При этом предполагается известной модель приложения, позволяющая оценивать значения целевой функции F(X). В к-к подзадаче определяются значения одного или нескольких структурных параметров, составляющих подмножество Х с X. Частные задачи решаются значительно проще общей задачи, обычно это задачи оптимизации малой размерности с локальными целевыми функциями (X ), Х с X. Например, в общей задаче синтеза расписаний частная задача - назначение для очередной работы обслуживающего сервера и определение ее положения во времени. [c.221] Реализацию НСМ можно рассматривать как экспертную систему, в которой продукциями являются эвристики, причем на каждом шаге решения может использоваться несколько продукций, выбор между ними производит генетический интерпретатор. [c.222] НСМ свободен от необходимости корректировки дочерних хромосом. В нем аллелями служат не значения проектных параметров, а имена эвристик, используемых для определения этих значений. Выполнение условий допустимости переносится в сами эвристики, что делает собственно генетический алгоритм инвариантным к различным задачам. Простой сменой набора эвристик легко осуществляется адаптация имеющихся программ синтеза к особенностям конкретного класса задач. [c.222] Другими словами, в случае НСМ г-й ген соответствует г-й подзадаче, а 1-й аллель есть номер (имя) процедуры (эвристики), реализующей локальную целевую функцию и ограничения г-й подзадачи. Согласно НСМ для каждой подзадачи должно быть сформулировано несколько альтернативных постановок (процедур), именно среди них генетический алгоритм или алгоритм локального поиска будет выбирать члены последовательности, приближаясь к оптимальной последовательности эвристик. [c.222] НСМ может быть применен к широкому кругу задач дискретной оптимизации и структурного синтеза, характеризуемых следующими особенностями. [c.222] Именно к таким задачам относятся представители охарактеризованного вьппе класса задач планирования и проектирования и прежде всего многие логистические задачи. [c.223] Эффективность генетического метода определяется степенью приближения значения целевой функции 7 при стагнации к ее оптимальному значению. В ряде приложений со сложными структурнокритериальными моделями ввиду ограничений на время решения расчеты приходится прерывать до достижения стагнации, поэтому эффективность генетического алгоритма характеризуется также скоростью достижения уровня стагнации. [c.223] Типичная структура программы выбора оптимального решения на основе НСМ приведена на рис. 2.16. Слева показаны блоки инвариантной к приложениям части программного обеспечения, ие-полняющей операторы генетического и/или локального поиска. Процедуры эвристик служат для решения подзадач, в них определяются локальные целевые функции В модели приложения вычисляется общая целевая функция (Х) для каждой хромосомы, генерируемой при формировании начального поколения или в процессе локального поиска. При переходе к новому приложению достаточно заменить показанные на рис. 2.16 справа блоки модели и эвристик. [c.224] Вернуться к основной статье