Что такое генетический алгоритм
Сообщение кандидата технических наук Валерия Симбиркина (БелНИИС) "Оптимальное проектирование строительных конструкций с помощью генетического алгоритма", сделанное им на международной научно-технической конференции "Пространственные конструктивные системы зданий и сооружений, методы расчета, конструирования и технология возведения"
Как известно, эффективность и экономичность любой конструкции зависит не только от ее статического и динамического расчета, но и от конструкторской реализации результатов этого расчета.
То есть для того чтобы успешно запроектировать конструкцию, необходимо решить соответствующую задачу оптимизации.
На практике подобные задачи очень часто оказываются довольно сложными. Они включают целевые функции, которые могут быть и дискретными, и недифференцируемыми, и не существующими за пределами допустимой области, в пределах же допустимой области они могут иметь несколько локальных и даже глобальных экстремумов.
В подобных случаях не представляется возможным использовать традиционные градиентные методы оптимизации. Существуют, впрочем, стохастические методы оптимизации, один из которых носит название "генетический алгоритм".
Безусловно, применение стохастических методов не гарантирует того, что оптимальное решение непременно будет найдено. Однако они достаточны для нахождения нескольких решений, вполне приемлемых для решения практических задач.
При построении генетических алгоритмов, или алгоритмов поколений, задается начальное поколение (или множество) решений, после чего осуществляется оценка этих решений и формируется новое поколение решений. Описанные итерации выполняются до тех пор, пока очередное поколение решений не удовлетворит критериям остановки.
Разнообразие генетических алгоритмов обусловлено разнообразием способов формирования нового поколения решений. Достаточно хорошо изучены и широко используются методы Монте-Карло.
В течение же последних 20 лет не менее широко стал применяться генетический алгоритм, который основан на моделировании процессов биологической эволюции (селекции, скрещивания, мутации) по Дарвину.
Какие задачи удалось решить с использованием генетического алгоритма исследователям БелНИИС?
Было рассмотрено поведение под различными нагрузками стальных двухпролетных рам промзданий, включающих и плоскостные сварные элементы, и элементы переменного сечения.
Целью решения данной задачи было сокращение до минимума расхода стали при изготовлении таких рам. Переменными величинами в данном случае являлись размеры поперечных сечений, то есть речь шла о распределении жесткостей по расчетной схеме рамы.
В качестве аналога была принята расчетная схема одного из промзданий, построенных в Германии.
Вес исходной рамы составлял более 4 т. Решения же, полученные как с использованием генетического алгоритма, так и по методу Монте-Карло, дали несколько меньшие результаты.
Во всех случаях генетический алгоритм оказался на 8-9% эффективнее метода Монте-Карло.
Наиболее экономичным подходом оказался тот, который предусматривал использование сварных элементов переменного сечения.
Вообще же при конструировании подобных рам применение стоек переменного сечения вовсе не приводит к существенной экономии стали.
Были рассмотрены также конструкции однопролетных рам промзданий. В этом случае удалось проследить несколько иную закономерность - заметной экономии стали не способствует применение ригелей переменного сечения.
Для названных объектов были определены оптимальные соотношения длины пролета и шага поперечных рам.
Было рассмотрено также несколько простых задач для железобетона. В данном случае исследователи ориентировались на конструкции каркасных зданий, в которых используются статически неопределимые элементы. Здесь можно применять перераспределение усилий, в том числе искусственное их регулирование, и за счет этого добиваться сокращения расхода арматуры при конструировании элементов железобетонных рам.
Был рассмотрен стержневой элемент, по своим размерам совпадающий с ригелем сборно-монолитного каркаса системы БелНИИС и несущий распределенную нагрузку, равную 50 кН/м.
Были рассмотрены различные классические случаи опирания элементов. В итоге наиболее эффективным оказался вариант, предусматривающий защемление элемента с обоих концов пролета. В этом случае удалось снизить расход арматуры по сравнению со статически определимым элементом с обычным балочным (шарнирным) опиранием практически в 3 раза.
Было получено подтверждение того, что использование в расчетных схемах статически неопределимых элементов приводит к уменьшению расхода арматуры по сравнению со статически определимыми. Это еще раз доказывает экономическую эффективность применения в каркасах статически неопределимых неразрезных конструкций.
Выполненное перераспределение изгибающих моментов показало, что опирание, в соответствиии с которым опорный момент равен ql2/12, а пролетный - ql2/24, близко к оптимальному.
Было рассмотрено поведение многоэтажных железобетонных рам, то есть ригелей совместно с колоннами.
Оказалось, что моменты в крайних опорных узлах несколько меньше, чем во всех остальных, соответственно армирование этих узлов может быть менее мощным. Проектировщики иногда пользуются этим обстоятельством, а иногда (в целях унификации армирования) - нет.
Была рассмотрена и каркасная схема с шарнирным опиранием ригелей. Разумеется, в этом случае был получен расход арматуры, намного больший, чем по варианту с жесткими заделками.
Нужно сказать, что для получения наиболее эффективного решения с помощью генетического алгоритма необходимо правильно задавать его параметры. В частности, были исследованы влияния размера популяции (то есть количества задаваемых первоначальных решений), а также мутаций. Оказалось, что мутации очень сильно влияют на сходимость алгоритма, точнее, на конечный результат при малом размере популяции.
В случае увеличения размера популяции мутации практически не сказываются на конечном результате.
Аналогично размер популяции, в свою очередь, оказывает влияние на работу алгоритма при малом уровне мутации (малой ее вероятности).
В целом же и увеличение размера популяции, и увеличение вероятности мутации приводит к увеличению области поиска, исследуемой алгоритмом.
В этом случае можно добиться того, что алгоритм будет сходиться медленно. Нужно лишь тем или иным путем находить оптимальный вариант задания параметров алгоритма.Подготовил Федор СПИРИДОНОВ
Как известно, эффективность и экономичность любой конструкции зависит не только от ее статического и динамического расчета, но и от конструкторской реализации результатов этого расчета.
То есть для того чтобы успешно запроектировать конструкцию, необходимо решить соответствующую задачу оптимизации.
На практике подобные задачи очень часто оказываются довольно сложными. Они включают целевые функции, которые могут быть и дискретными, и недифференцируемыми, и не существующими за пределами допустимой области, в пределах же допустимой области они могут иметь несколько локальных и даже глобальных экстремумов.
В подобных случаях не представляется возможным использовать традиционные градиентные методы оптимизации. Существуют, впрочем, стохастические методы оптимизации, один из которых носит название "генетический алгоритм".
Безусловно, применение стохастических методов не гарантирует того, что оптимальное решение непременно будет найдено. Однако они достаточны для нахождения нескольких решений, вполне приемлемых для решения практических задач.
При построении генетических алгоритмов, или алгоритмов поколений, задается начальное поколение (или множество) решений, после чего осуществляется оценка этих решений и формируется новое поколение решений. Описанные итерации выполняются до тех пор, пока очередное поколение решений не удовлетворит критериям остановки.
Разнообразие генетических алгоритмов обусловлено разнообразием способов формирования нового поколения решений. Достаточно хорошо изучены и широко используются методы Монте-Карло.
В течение же последних 20 лет не менее широко стал применяться генетический алгоритм, который основан на моделировании процессов биологической эволюции (селекции, скрещивания, мутации) по Дарвину.
Какие задачи удалось решить с использованием генетического алгоритма исследователям БелНИИС?
Было рассмотрено поведение под различными нагрузками стальных двухпролетных рам промзданий, включающих и плоскостные сварные элементы, и элементы переменного сечения.
Целью решения данной задачи было сокращение до минимума расхода стали при изготовлении таких рам. Переменными величинами в данном случае являлись размеры поперечных сечений, то есть речь шла о распределении жесткостей по расчетной схеме рамы.
В качестве аналога была принята расчетная схема одного из промзданий, построенных в Германии.
Вес исходной рамы составлял более 4 т. Решения же, полученные как с использованием генетического алгоритма, так и по методу Монте-Карло, дали несколько меньшие результаты.
Во всех случаях генетический алгоритм оказался на 8-9% эффективнее метода Монте-Карло.
Наиболее экономичным подходом оказался тот, который предусматривал использование сварных элементов переменного сечения.
Вообще же при конструировании подобных рам применение стоек переменного сечения вовсе не приводит к существенной экономии стали.
Были рассмотрены также конструкции однопролетных рам промзданий. В этом случае удалось проследить несколько иную закономерность - заметной экономии стали не способствует применение ригелей переменного сечения.
Для названных объектов были определены оптимальные соотношения длины пролета и шага поперечных рам.
Было рассмотрено также несколько простых задач для железобетона. В данном случае исследователи ориентировались на конструкции каркасных зданий, в которых используются статически неопределимые элементы. Здесь можно применять перераспределение усилий, в том числе искусственное их регулирование, и за счет этого добиваться сокращения расхода арматуры при конструировании элементов железобетонных рам.
Был рассмотрен стержневой элемент, по своим размерам совпадающий с ригелем сборно-монолитного каркаса системы БелНИИС и несущий распределенную нагрузку, равную 50 кН/м.
Были рассмотрены различные классические случаи опирания элементов. В итоге наиболее эффективным оказался вариант, предусматривающий защемление элемента с обоих концов пролета. В этом случае удалось снизить расход арматуры по сравнению со статически определимым элементом с обычным балочным (шарнирным) опиранием практически в 3 раза.
Было получено подтверждение того, что использование в расчетных схемах статически неопределимых элементов приводит к уменьшению расхода арматуры по сравнению со статически определимыми. Это еще раз доказывает экономическую эффективность применения в каркасах статически неопределимых неразрезных конструкций.
Выполненное перераспределение изгибающих моментов показало, что опирание, в соответствиии с которым опорный момент равен ql2/12, а пролетный - ql2/24, близко к оптимальному.
Было рассмотрено поведение многоэтажных железобетонных рам, то есть ригелей совместно с колоннами.
Оказалось, что моменты в крайних опорных узлах несколько меньше, чем во всех остальных, соответственно армирование этих узлов может быть менее мощным. Проектировщики иногда пользуются этим обстоятельством, а иногда (в целях унификации армирования) - нет.
Была рассмотрена и каркасная схема с шарнирным опиранием ригелей. Разумеется, в этом случае был получен расход арматуры, намного больший, чем по варианту с жесткими заделками.
Нужно сказать, что для получения наиболее эффективного решения с помощью генетического алгоритма необходимо правильно задавать его параметры. В частности, были исследованы влияния размера популяции (то есть количества задаваемых первоначальных решений), а также мутаций. Оказалось, что мутации очень сильно влияют на сходимость алгоритма, точнее, на конечный результат при малом размере популяции.
В случае увеличения размера популяции мутации практически не сказываются на конечном результате.
Аналогично размер популяции, в свою очередь, оказывает влияние на работу алгоритма при малом уровне мутации (малой ее вероятности).
В целом же и увеличение размера популяции, и увеличение вероятности мутации приводит к увеличению области поиска, исследуемой алгоритмом.
В этом случае можно добиться того, что алгоритм будет сходиться медленно. Нужно лишь тем или иным путем находить оптимальный вариант задания параметров алгоритма.Подготовил Федор СПИРИДОНОВ
Строительство и недвижимость. Статья была опубликована в номере 41 за 2001 год в рубрике менеджмент
