Разработка генетического алгоритма слабовзаимодействующих популяций для оптимизации несущих систем

Размещено на http://www.allbest.ru/

РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА СЛАБОВЗАИМОДЕЙСТВУЮЩИХ ПОПУЛЯЦИЙ ДЛЯ ОПТИМИЗАЦИИ НЕСУЩИХ СИСТЕМ

И.Н. Серпик, К.В. Шевченко

Предложен генетический алгоритм оптимизации несущих конструкций, использующий несколько слабовзаимодействующих популяций с различными параметрами изменения. Рассмотрены вопросы ускорения поиска оптимального решения и построения критериев остановки вычислений. На тестовых примерах проиллюстрирована высокая эффективность представленной итерационной схемы.

Ключевые слова: оптимизация, генетический алгоритм, несущие конструкции, слабовзаимодействующие популяции, координатный спуск.

Оптимизация несущих систем связана с решением достаточно сложных задач математического программирования. Обычно постановка задач такого типа включает минимизацию целевой функции при значительном числе ограничений в виде равенств и неравенств. При этом во многих случаях приходится сталкиваться с необходимостью поиска на дискретных множествах варьируемых параметров (профилей стержней, толщин листов, марок материалов и т.д.).

Наиболее существенные проблемы возникают при структурной оптимизации, которая предусматривает учет изменения схем взаимодействия между элементами деформируемого объекта. Кроме того, здесь необходимо принимать во внимание дополнительное ограничение, связанное с исключением возможности появления геометрически изменяемых или мгновенно изменяемых систем. Структурная оптимизация может быть сведена к задаче параметрического синтеза путем введения дополнительных дискретных параметров, управляющих наличием или отсутствием элементов расчетной схемы, однако это связано с еще большим увеличением числа варьируемых параметров. В результате классические подходы к поиску экстремумов становятся неприемлемыми, так как либо приводят к чрезмерным затратам машинных ресурсов, либо вообще не позволяют выполнять оптимальное проектирование реальных объектов.

Данная проблема, тем не менее, может найти свое решение на основе методов современных информационных технологий. Одним из таких подходов, позволяющих осуществлять оптимальный структурно-параметрический синтез достаточно сложных несущих конструкций, являются генетические алгоритмы [1-5], иначе называемые эволюционным моделированием, которые функционируют по принципам совершенствования видов в живой природе. Эти вычислительные схемы дают возможность достаточно эффективно проводить поиск глобального минимума и при этом не требуют непрерывности варьируемых параметров.

Генетические алгоритмы предусматривают создание группы (популяции) особей, определяемых набором параметров (генов); отбор особей по критерию выживаемости, связанному со значением целевой функции; последовательную смену поколений для обеспечения минимального (или максимального) значения целевой функции. Процесс модификации поколений осуществляется на основе операторов кроссинговера и мутации. Кроссинговер предполагает обмен значениями параметров между двумя или более особями. Под мутацией понимается случайное изменение этих параметров. Проблеме разработки генетических алгоритмов посвящено большое число исследований, в том числе применительно к оптимизации деформируемых систем. Тем не менее вопросы ускорения синтеза оптимальных объектов и выработки рационального подхода к завершению вычислительного процесса еще требуют дальнейшего изучения.

В настоящей статье предлагается генетический алгоритм, позволяющий повысить эффективность эволюционного синтеза при проектировании несущих систем. Главной особенностью данного алгоритма является параллельное использование в каждом поколении нескольких взаимодействующих между собой популяций. При этом для каждой популяции указываются свои параметры изменения. Для обмена лучшими особями между популяциями вводится механизм примешивания - периодического заимствования некоторого количества особей из других популяций. Такая схема алгоритма позволяет реализовать поиск как вблизи найденных ранее оптимальных значений, когда незначительно изменяется небольшое число генов, так и вдали от уже имеющихся решений, когда изменению подвергается относительно большое число генов. С целью ускорения процедуры в операторах кроссинговера и мутации учитывается характер влияния изменения генов на целевую функцию, а на этапе, когда генетическое разнообразие популяций становится малым, реализуется метод координатного спуска.

Расчет напряженно-деформированного состояния фермы выполняется с помощью метода конечных элементов в форме метода перемещений на базе программного комплекса DSMFem, позволяющего за счет использования специализированного языка достаточно просто модифицировать расчетные схемы оптимизируемых систем.

Постановка задачи. Остановимся на классической проблеме синтеза ферм по условию минимума массы, так как на тестовых задачах такого типа обычно оценивается производительность генетических алгоритмов [1; 2]. Запишем целевую функцию в виде

,

алгоритм оптимизация несущий конструкция

где M - масса стержней; - число стержней в исходной структуре фермы; - коэффициент учета наличия j-го стержня в текущей конфигурации фермы (, если стержень учитывается, и , если стержень отсутствует); , , - площадь поперечного сечения, длина и плотность материала j-го стержня.

Считается, что в общем случае могут варьироваться площади и параметры . Рассматриваются следующие ограничения [1; 2]:

· условие мгновенной неизменяемости объекта;

· равновесие узлов конечноэлементной модели;

· условия прочности в форме задания допускаемых напряжений;

· условия жесткости в форме максимально допустимых по модулю перемещений в заданных направлениях.

Ограничения по напряжениям и перемещениям учитываются путем введения штрафной функции вида

,

где I - общее число ограничений, не удовлетворенных для рассматриваемого варианта конструкции; - коэффициент, нормирующий степень важности учета ограничения i; - функция, отражающая превышение получаемой величины над допускаемым значением для этого ограничения.

Алгоритм решения задачи. При выполнении итерационного процесса используем n основных популяций, включающих по N особей. Эти особи подвергаются изменениям с помощью генетических операторов. Некоторые популяции при переходе от поколения к поколению могут меняться относительно слабо, но при этом достаточно часто учитывать результаты отбора в донорских популяциях, а некоторые - модифицироваться достаточно интенсивно. Одна из основных популяций назначается контрольной. Для нее выполняются проверки условий завершения итерационной процедуры. Кроме того, вводится вспомогательная популяция элитных особей, в которой собираются наиболее приспособленные особи из основных популяций. Размер вспомогательной популяции также равен N. Элитные особи используются в итерационной схеме в качестве перспективного генетического материала. Все получаемые результаты сохраняются в базе данных, позволяющей повторно учитывать результаты расчетов для особей с одинаковым генетическим набором. При принятии решения об остановке итерационного процесса учитывается стабилизация в контрольной популяции генетического состава и значений целевой функции.

Общая структура рассматриваемого генетического алгоритма приведена на рис. 1. Разъясним основные этапы этой итерационной схемы.

1. Ввод исходной информации. Задаются сведения о расчетной схеме объекта, множествах допустимых значений варьируемых параметров, параметрах управления итерационным процессом.

2. Формирование начальных популяций. Строятся хромосомы особей основных популяций. При этом в каждой популяции создаются:

· особь, имеющая минимальные значения варьируемых параметров;

· особь, имеющая максимальные значения;

· особи со случайными значениями генов.

Популяция элитных особей формируется из лучших особей основных популяций.

3. Расчет чувствительности функции цели к изменению значений генов. Считается, что допустимые значения каждого гена отсортированы по возрастанию. В популяции элитных особей, отсортированной по возрастанию целевой функции, выделяются субпопуляция A из N/3 лучших особей и субпопуляция B из N/3 худших особей. Осредненная по особям чувствительность функции цели к изменению значения k-го гена оценивается выражением

где - номер варианта допустимого значения k-го гена i-й особи.

Параметр показывает, в каком направлении желательно изменять ген: в сторону увеличения или в сторону уменьшения.

4. Создание особей на основе кроссинговера или координатного спуска. Если популяция еще не стабилизировалась по генетическому составу, реализуется одноточечный или многоточечный кроссинговер. Вероятность отбора родительской особи должна быть тем выше, чем лучше значение целевой функции. Для этого популяция сортируется по возрастанию целевой функции. Номер i особи выбирается из упорядоченной последовательности в пределах от 1 до N с помощью выражения

,

где Gnorm(m,у) - генератор целых чисел, распределенных по нормальному закону; m - медиана этой величины, соответствующая i=1; у = (N-1)/3 - среднее квадратичное отклонение распределения.

Результирующий номер значения каждого k-го гена будет определяться зависимостью

где значения генов родительских особей;

K - число допустимых значений гена; gnorm - генератор вещественных чисел, распределенных по нормальному закону.

Если популяция стабилизировалась, вместо кроссинговера осуществляется смещение значений генов методом координатного спуска. Данный подход предполагает последовательное тестирование функции цели при изменении каждого гена на один уровень в меньшую или большую сторону.

Размещено на http://www.allbest.ru/

5. Создание особей на основе мутации. Значения варьируемых генов выбираются случайным образом из множеств допустимых значений:

,

где Pr - значение гена для родительской особи, рассматриваемой до выполнения кроссинговера или координатного спуска.

6. Примешивание особей из связанных популяций. Для рассматриваемой популяции копируются лучшие особи из других основных популяций и из популяции элитных особей. При этом осуществляется перемешивание генетического материала. Использование элитных особей позволяет удерживать всю совокупность популяций в окрестностях с наименьшими значениями целевой функции.

7. Отбор лучших особей. Из группы особей, полученных в результате осуществления кроссинговера или координатного спуска, мутации и примешивания, отбираются N лучших особей, которые образуют новое поколение для популяции.

8. Определение признаков стабилизации популяции. Для каждой основной популяции оценивается идентичность всех особей по генетическому составу и значению функции цели. Данные признаки в дальнейшем используются для принятия решения о необходимости выполнения процедуры координатного спуска или завершения всего итерационного процесса.

9. Проверка условий завершения процедуры. Как только одно из условий стабилизации выполняется на протяжении заданного числа итераций, считается, что искомое решение найдено.

В табл. 1 отражены основные рассматриваемые параметры управления вычислительным процессом. Для определения числа особей, используемых в операциях кроссинговера, мутации или примешивания, соответствующий коэффициент (, или ) умножается на число N.

Таблица 1

Параметры управления итерационным алгоритмом

Примеры оптимизации ферм. Для анализа сходимости разработанного генетического алгоритма рассматривались два примера; в первом выполнялась структурная оптимизация однопролетной двухопорной фермы, избыточная структура которой показана на рис. 2а, во втором - параметрическая оптимизация консольной фермы (рис. 2б).

Пример 1. Для однопролетной фермы задавались: ширина панелей , площадь поперечного сечения стержней , величины сосредоточенных сил , . В качестве значений девяти варьируемых параметров принимались флаги, определяющие наличие или отсутствие каждой из пар симметрично расположенных стержней, не входящих в нижний пояс фермы. Задавались допускаемые напряжения, равные 100 МПа. Глобальный минимум здесь достигается при получении одной из структур, приведенных на рис. 3.

Рис. 2. Схемы оптимизируемых конструкций для примеров 1 (а) и 2 (б)

Размещено на http://www.allbest.ru/

Рис. 3. Оптимальные схемы ферменной конструкции для примера 1

Исследовалось влияние числа используемых популяций и условий остановки процедуры на результат оптимизации. Рассматривались итерационные схемы с введением одной и трех основных популяций. При выполнении итерационного процесса принималось: . Ряд других параметров управления генетическим алгоритмом дан в табл. 2, где для под «max» понимается максимально возможное (предельное) число разрезов в хромосоме. В табл. 3 для каждого набора величин G, V дано число рассчитанных уникальных вариантов конструкции и число сгенерированных поколений при выполнении только одной реализации генетического алгоритма. Ячейки таблицы для реализаций, в которых не удалось получить оптимальную конструкцию затушеваны. Отметим, что при повторном запуске на счет оптимальная конструктивная система могла быть найдена для любых рассматриваемых значений G и V. Из представленных в табл. 3 данных видно, что использование системы трех основных популяций позволило обеспечить существенно бульшую стабильность достижения результата по сравнению со случаем введения только одной основной популяции.

Пример 2. Данная ферма является наиболее известным классическим примером для исследования работоспособности генетических алгоритмов [1; 2]. Рассматривается параметрическая оптимизация с независимым варьированием площади поперечного сечения каждого из 10 стержней. Принимается, что модуль упругости материала стержней равен 689,48 МПа, сила P=445,37 кН, плотность материала равна 2768 кг/м3. Вводятся ограничения по напряжениям в стержнях и перемещениям узлов в горизонтальном и вертикальном направлениях. Допускаемые напряжения равны 172,37 МПа, перемещения - 5,08 см. В качестве допускаемых значений каждого из изменяемых параметров задаются следующие 30 величин (см2): 0,64516; 223,87052; 283,8704; 347,74124; 615,48264; 697,41796; 757,41784; 859,99828; 959,99808; 1138,06224; 1381,93272; 1739,99652; 1806,448; 2019,3508; 2299,9954; 2459,99508; 3099,9938; 3839,99232; 4239,99152; 4639,99072; 5499,989; 5999,988; 6999,986; 8599,9828; 9219,3364; 11077,3972; 12374,1688; 14838,68; 18116,0928; 21741,892.

Таблица 2

Параметры итерационного процесса для примера 1

Таблица 3

Сведения о стабильности алгоритма для примера 1

В расчете использовались 3 основные популяции. При выполнении оптимизации принималось: , , , . . Параметры популяций вычислительного процесса приведены в табл. 4.

Таблица 4

Параметры популяций итерационной схемы для примера 2

Результат оптимального синтеза (площади поперечных сечений для результирующей конструкции) выглядит следующим образом:

Максимальное напряжение составило 140 МПа, перемещение -5,073 см. Масса стержней данной конструкции равна 2357,47 кг. График изменения наименьшей массы для получавшихся в итерациях вариантов несущей системы представлен на рис. 4. При этом за 61 поколение, потребовавшееся для нахождения решения задачи, было рассчитано напряженно-деформированное состояние для 4418 уникальных вариантов конструкции.

Рядом авторов были получены варианты фермы с наименьшей массой в пределах от 2424,6359 до 2472,8205 кг [1], т. е. предлагаемый алгоритм дал возможность найти более эффективное решение по сравнению с этими результатами.

Таким образом, численные эксперименты для разработанного генетического алгоритма показали, что введение системы слабовзаимодействующих популяций позволяет существенно повысить стабильность итерационной схемы. При этом вычислительная процедура такого типа показала высокую эффективность на классическом тестовом примере оптимизации консольной фермы.

Рис. 4. Изменение массы стержней наилучшей особи в зависимости от номера поколения

СПИСОК ЛИТЕРАТУРЫ

1. Togan, V. An improved genetic algorithm with initial population strategy and self adaptive member grouping / V. Togan, A.T. Dolaglu // Comp. Struct. - 2008. - Vol. 86. - P. 1204-1218.

2. Nanakorn, P. An adaptive penalty function in genetic algorithms for structural design optimization / P. Nanakorn, K. Meesomklin // Comp. Struct. - 2001. - Vol. 79. - Р. 2527-2539.

3. Серпик, И.Н. Генетическая процедура синтеза несущих конструкций вагонов / И.Н. Серпик, В.В. Мирошников, М.И. Серпик, А.И. Тютюнников // Качество машин: сб. тр. IV Междунар. науч.-техн. конф. - Брянск: БГТУ, 2001. - Т. 1. - С. 75-77.

4. Серпик, И.Н. Структурно-параметрическая оптимизация стержневых металлических конструкций на основе эволюционного моделирования / И.Н. Серпик, А.В. Алексейцев, Ф.Н. Левкович, А.И. Тютюнников // Изв. вузов. Строительство. - 2005. - №8. - С. 16-24.

5. Серпик, И.Н. Эволюционное моделирование в проектировании несущих систем вагонов / И.Н. Серпик, В.Г. Сударев, А.И. Тютюнников, Ф.Н. Левкович // Вестн. ВНИИЖТ. - 2008. - № 5. - С. 21-25.

Размещено на Allbest.ru