© Владимир Абрамов
Целью данной работы является введение и демонстрация структуры решения проблем оптимизации при помощи агент-ориентированных моделей (АОМ). Структура была реализована в двух компьютерных программах: в статистическом пакете Microsoft Excel и NetLogo. Основная проблема заключается в том, что количество возможных решений оптимизационной задачи слишком велико для исчисления. Следовательно, для решения этой задачи требуется использование эвристических методов, в которых ключевым фактором является простота вычислений. В связи с этим использование метода масштабируемой аппроксимации может быть очень полезным. В то время как масштабируемая модель точно имитирует реальную динамику, её применение позволяет решить оптимизационную задачу с более низким временем выполнения и меньшей вычислительной сложностью. Структура решения оптимизационных проблем отражена на рисунке 1.
Рисунок 1. Структура решения оптимизационных проблем: анализ, масштабирование и оптимизация.
Достоверность данных.
Ключевым фактором анализа АОМ является стохастичность. Данный подход предполагает изучение изменения средних в зависимости от количества запусков модели.
Часто в АОМ используется «сетка», которая отражает пространство модели. В данной работе используется метод масштабирования , целью которого является упрощение модели до степени, при которой не нарушается её динамика. В терминах оптимизации определяется до какой степени модель может быть упрощена для оптимального управления. В работе была использована взвешенная Коэна k. Пусть pobs - это реальные результаты полученные в результате масштабирования и pexp - ожидаемые показатели полученные со случайной вероятностью. Тогда k = (pobs − pexp)/(1 − pexp).
Оптимизация по Парето.
После использования масштабирования необходимо применить эвристические алгоритмы для определения локальных оптимальных решений. При этом необходимо задать вес каждому полученному показателю. Для этого можно применить оптимизацию по Парето. Данный алгоритм вместо единственного решения возвращает набор решений. Программный код алгоритма представлен ниже.
Алгоритм 1. Программный код NetLogo процесса оптимизации по Парето.
Две модели.
Модель кроликов.
В первой модели на каждом такте кролики перемещаются и поедают траву, если она присутствует на занятой клетке. Контроль над процессом заключается в решении применения яда, убивающего кроликов. В данном случае целью является определить план появления яда u, при котором минимизируется популяция кроликов и частота применения яда. На рис. 2 отражены три случайно выбранных «плана контроля» (control shedule).
(a) 10 контрольных дней
(b) 30 контрольных дней
(c) 50 контрольных дней
Рисунок 2. Средняя численность в сопоставимых значениях при 50 запусках модели.
Далее среднее количество кроликов в выбранных случаях было ранжировано. В табл. 1 отражено, какое число симуляций может быть запущено для редуцированных моделей в течении 3 сек.
Таблица 1. Число возможных симуляций, запускаемых в эквивалентное время.
| Размерность | Число симуляций | Среднее время запуска (сек.) |
| 50 | 50 | 3.04 |
| 40 | 75 | 3.00 |
| 30 | 135 | 3.05 |
| 20 | 290 | 3.03 |
| 10 | 1100 | 3.03 |
| 5 | 3500 | 3.01 |
| 3 | 5700 | 3.03 |
На рис. 3 приведены значения взвешенного k для различных размерностей и разного времени запуска. Из данных можно сделать следующие выводы: для достижения наибольшего значения k стоит не менять размерность модели. Кроме того, стоит отметить, что при необходимости сокращения времени прогона лучше использовать меньшее количество пробегов для в оригинальной размерности, чем большее количество пробегов в сокращенной размерности.
Рисунок 3. Взвешенная Коэна k для различных размерностей и времени прогона.
Целью оптимизации по Парето является определение границы пространства управляющих воздействий модели. Для этого в редуцированных моделях происходит проверка исходных параметров на Парето оптимальность. На рис. 4 отражены результаты проверки для низких значений взвешенной k. Видно, что пороговое значение k = 0.5
Рисунок 4. Области Парето для моделей с низким значением взвешенной k.
На рис. 5 отражены аналогичные результаты для высоких значений k. Видно, что область Парето при k = 0.89 практически совпадает с областью оригинальной модели. Пороговое значение в данном случае – k = 0.76
Рисунок 5. Области Парето для моделей с высоким значением взвешенной k.
Сахарная модель.
Вторая модель была разработана Джошуа Эпштейном в 1996 г. В модели на сетке размещается популяция агентов, которая занимается поиском пищи (сахара). Сетка состоит из регионов с различным содержанием сахара (см. рис. 8). Более темные регионы содержат больше сахара, чем светлые. Муравьи (агенты) в зависимости от своего местоположения, зрения и метаболизма затрачивают различное количество энергии. Кроме того, модель была модифицирована. Была добавлена возможность облагать агентов налогами, то есть отнимать у них определенное количество сахара. В итоге, задача оптимизации в данной модели заключалась в максимизации «налогообложения» и минимизации количества смертей муравьев.
Рисунок 6. Сетка сахарной модели размерностью 50x50.
Было произведено 100 запусков модели с тремя различными уровнями налогообложения (см. рис. 7). На графиках видно, что изменения стандартного отклонения и среднего при числе прогонов больше 50 незначительны, поэтому данное количество запусков достаточно.
Масштабированию модели подверглись размерность и число агентов. Метаболизм агентов не менялся.
Количество возможных прогонов редуцированных моделей в эквивалентное время показано в табл. 2.
(a) Средний уровень налогообложения 0.125
(b) Средний уровень налогообложения 0.25
(c) Средний уровень налогообложения 0.375
Рисунок 7. Средние значения числа смертей (сплошная линия) и доход от налогов (прерывистая линия) на протяжении 50 модельных прогонов.
Таблица 2. Число симуляций в эквивалентное время.
| Размерность | Число симуляций | Среднее время запуска (сек.) |
| 50 | 50 | 8.51 |
| 40 | 88 | 8.48 |
| 30 | 173 | 8.49 |
| 20 | 427 | 8.52 |
| 10 | 1375 | 8.53 |
| 5 | 3900 | 8.48 |
На рис. 8 отражены величины взвешенных k в различных редуцированных моделях.
Рисунок 8. Взвешенные k по количеству смертей (сверху) и доходу от налогов (снизу).
После Парето оптимизации был сделан вывод, что во всех трех случаях, в которых k равно 0.15, 0.27 и 0.43, наблюдаются значительные расхождения показателей с нередуцированной моделью, в результате чего можно говорить о минимальном значении взвешенной k, ниже которого модели теряют адекватность. Статистические результаты можно увидеть на рис. 9.
Рисунок 9. Результаты оптимизации сахарной модели по Парето.
Оригинал статьи: [Oremland, Matthew and Laubenbacher, Reinhard (2014) 'Optimization of Agent-Based Models: Scaling Methods and Heuristic Algorithms' Journal of Artificial Societies and Social Simulation 17 (2) 6].