Анализ существующих подходов к решению задач структурного синтеза в проектировании и логистике. Разработка новых генетических методов структурного синтеза проектных решений. Параметры, управление которыми повышает эффективность генетических алгоритмов.
Аннотация к работе
Однако по мере усложнения проектируемых изделий возможности человека в решении задач сужаются, растут затраты времени на проектирование, зачастую принимаются решения, далекие от оптимальных. Основные преимущества ГА следующие: 1) применимы к задачам как с числовыми, так и предметными переменными, т.е. позволяют осуществлять поиск в неметризуемых пространствах параметров; 2) адаптируются и «обучаются» в течение своего исполнения; 3) имеют параллельность внутренних процессов. Для повышения эффективности ГА в работах этих и других исследователей разработана совокупность алгоритмов выполнения генетических операторов, однако выделить среди них наилучшие для любых задач не представляется возможным. Анализу подвергнуты эволюционные методы: базовый генетический алгоритм, метод «поведения толпы» и метод «колонии муравьев». Теорема шаблонов утверждает, что K(H, t 1) = K(H, t) ps Fav(H)/ F0, (1) где K(H, t) - число экземпляров схемы Н в поколении с номером t; Fav(H) - усредненная полезность экземпляров со схемой H; F0 - усредненная полезность всех экземпляров популяции; ps= 1-d(H)/(n-1) - вероятность выживания схемы Н (вероятность, с которой при простом одноточечном кроссовере в хромосому потомка попадет схема); n - длина хромосомы (число генов в хромосоме).
Список литературы
Главным научным результатом работы является разработка и обоснование эффективности новых генетических методов структурного синтеза и дискретной оптимизации для систем автоматизированного проектирования и логистической поддержки.
Основные научные теоретические и практические результаты работы состоят в следующем.
Поскольку эффективность применения того или иного варианта реализации генетических операторов зависит от характера задачи и часто от ситуации, складывающейся во время решения задачи (начальный этап поиска или приближение к стагнации), целесообразна разработка и применение адаптивных генетических методов.
В результате анализа процессов разрушения/генерации шаблонов установлены наличие оптимальных длин фрагментов, на которые делятся хромосомы при кроссовере, и предпочтительность многоточечного кроссовера.
Разработан смешанный эволюционный метод, основанный на использовании многоточечного кроссовера и селекции с участием нескольких родительских хромосом.
Автоматический выбор значений параметров и типов генетических операторов в процессе генетического поиска реализован в метагенетическом алгоритме. Как и для определения значений управляемых параметров исходной оптимизационной задачи, для выбора значений параметров и типов операторов использованы генетические алгоритмы. К числу адаптируемых параметров в разработанном алгоритме также относятся длина фрагмента L для смешанного эволюционного метода, а также глубина и частота применения макромутаций в циклическом генетическом методе.
Предотвращение преждевременной стагнации при генетическом поиске возможно, если при макромутациях обеспечить, во-первых, сохранение накопленного генного материала, во-вторых, соизмеримость начальной полезности всех хромосом популяции.
Экспериментальная оценка эффективности новых генетических методов - смешанного эволюционного метода и метода комбинирования эвристик - показала, что однородный и одноточечный кроссоверы не относятся к лучшим вариантам ГА. При этом метод комбинирования эвристик HCM-m(m) превосходит по эффективности метод CGA-m(m) с обычным кодированием хромосом. Смешанный генетический метод HCM-m(m) с многими родителями превосходит по эффективности метод HCM-m(2), в котором при кроссовере происходит скрещивание генов только двух родителей.
Результаты диссертационной работы внедрены в ЗАО «СИНОПСИС АРМЕНИЯ», в КБ ИГАС «Волна» (г. Москва) и в учебный процесс МГТУ им. Н.Э. Баумана.
ОСНОВНЫЕ ПОЛОЖЕНИЯ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ
Норенков И.П., Арутюнян Н.М. Состояние проблемы структурного синтеза в проектировании и логистике //Наука и образование. Инженерное образование: Электронный журнал. - 2007. - № 9.