Компьютерное моделирование наводнений

В связи с глобальным потеплением, вызванным парниковым эффектом происходит таяние ледников и повышение уровня мирового океана. Также с изменением климата все чаще происходят разливы рек, тайфуны, например ураган “Сенди”, образовавшийся в конце октября 2012 года и затронувший Ямайку, Кубу, Багамские острова, Гаити, побережье Флориды и, впоследствии, северо-восток США и восточную Канаду. Но наиболее ощутимо для русского населения было наводнение на Дальнем востоке в 2013 году, разрушившее дома десятков тысяч людей. По подсчетам мировой Организации экономического сотрудничества и развития (ОЭСР) к 2050 году ежегодный ущерб от наводнений во всех 136 прибрежный городах достигнет триллиона долларов. Поэтому становится актуальным разработка программного комплекса способного моделировать глобальные наводнения и разрабатывать оптимальную систему защиты от них. На данный момент разработаны программы по моделированию наводнений, такие как Mike Flood созданные для предсказания последствия наводнений. Существенным недостатком разработанных программ является отсутствие в них опций моделирования защитных сооружений против наводнений. Именно поэтому целью нашей работы было создание программы способной моделировать кроме самих наводнений еще и оптимальную систему защиты, способную предотвращать пагубные последствия наводнений. Так как защитная система состоит из дорогостоящих сооружений (дамбы, плотины), то особенно важно оптимизировать их структуру, чтобы снизить их конечную стоимость. Задача в общем виде имеет экспоненциальную размерность, поэтому простым перебором ее решить не возможно. В нашем проекте для преодоления этой сложности используется Генетический алгоритм. Он показал хорошую сходимость для различных типов карт, сравнительно быстро находил оптимальную структуру дамб.

Проблема: Ежегодно увеличиваются пагубные последствия от наводнений и экономические затраты на их предотвращение. А существующие программные комплексы не позволяют моделировать оптимальную систему защиты от наводнений.

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

Объект исследования: Наводнения средства их предотвращения. 

Предмет исследования: Защитная структура от наводнений.

Задачи исследования:

1) Разработать программу, моделирующую наводнения с помощью алгоритмов клеточных автоматов.

2)  Реализовать генетический алгоритм поиска оптимальной структуры дамб.

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

В ходе выполнения работы использовались следующие методы и приёмы: изучение литературных источников, математическое моделирование, программное моделирование на языке C++.

                                    Описание алгоритма моделирования наводнений.

Наводнение моделируется с помощью алгоритма заливка, связанной по 4 сторонам света. Карта задается в виде пикселей имеющих свой цвет. Каждому цвету соответствует своя высота по шкале RGB. Краткий алгоритм заливки, реализованный в проекте:

Заливка (элемент, заменяемый цвет, цвет заливки):

1. Если цвет элемента не заменяемый цвет, возврат.

 2. Установить цвет элемента в цвет заливки.

 3. Заливка (шаг на запад от элемента, заменяемый цвет, цвет заливки).

    Заливка (шаг на восток от элемента, заменяемый цвет, цвет заливки).

    Заливка (шаг на север от элемента, заменяемый цвет, цвет заливки).

    Заливка (шаг на юг от элемента, заменяемый цвет, цвет заливки).

 4. Возврат.

Синий цвет – вода. Белый цвет - затопленная местность. Зеленый цвет – суша, причем, чем ярче цвет, тем выше она располагается. В дальнейшем дамбы мы будем обозначать красными линиями.

Моделирование оптимальной структуры дамб.

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

В качестве популяции в нашей программе мы выбрали массив структур, состоящих из координат концов дамб и их высоты. Начальную популяцию мы задали случайным образом строго в пределах залитой местности для ускорения работы алгоритма и уменьшении цены дамбы. Далее мы определяли для каждой “хромосомы” (единицы популяции) свой коэффициент выживаемости, далее находим этот коэффициент уже для всей популяции. Так если при генерации нового поколения его коэффициент будет ниже родительского, то будет задействован алгоритм мутации. Мутация также проходит в пределах затапливаемой местности, чтобы искать только “полезные” дамбы. Fitness функция (функция определения выживаемости хромосомы, ценность дамбы) определялась следующим образом:  суммируются затраты на строительство дамбы с учетом ее длинны и высоты а также ущерб, нанесенный затопленной части и вычитается стоимость спасенной части ландшафта. Таким образом наша целевая функция одновременно минимизирует общие затраты на изготовление дамб и суммарные ущерб от последствий наводнений. Программу можно подстраивать под разные экономические ситуации, то есть можно задавать стоимость ландшафта и строительства единицы дамбы. Так для каждой отдельной экономической ситуации программа делает акцент либо на наиболее дешевую дамбу если земля имеет не высокую цену, а затраты на строительство высоки, либо если стоимость земли очень велика, как например, в Европейских странах, то максимально уменьшает площадь затопления. Алгоритм заканчивает свою работу когда заканчивается количество итераций или Fitness функция достигает заранее установленного значения. Примеры работы программы приведены на рисунке. На левом рисунке белым цветом указано затопление до построения дамб, на правом после.

1.    Программа протестирована на различных картах ландшафта. Для этого создан удобный алгоритм быстрой генерации реалистичной местности. Алгоритм показал высокую сходимость для различный конфигураций карт, более чем на 100 тестах. На реалистичных параметрах (цена дамбы, затопленной части) программа находила оптимальное решение менее чем за 15000 итераций. Критерий оптимальности определялся следующим образом: бралось отношение всех на затопление и строительство дамб к затоплению всего ландшафта без учета дамб. Таким образом, программа находила оптимальное решение, которое в среднем экономило 20% от общих затрат, что является существенным результатом учитывая колоссальные масштабы потерь от наводнений.

Перспективы проекта:

1.      Доработка алгоритма моделирования наводнений с учетом параметров местности.

2.      Динамическое моделирование наводнений.                                                                                                           

3.      Применение программного комплекса для расчета структур защитных сооружений для реальных задач.

4.      Совершенствование генетического алгоритма путем ускорения его работы с помощью методов параллельного программирования. 
Полезно почитать по теме компьютерное моделирование наводнений
Клеточные автоматы

Поделиться: