Назад в библиотеку

---

Экономическое агентное моделирование с использованием конечных автоматов

Автор: Gnilomedov I., Nikolenko S.

Автор перевода: Кайдановский К.А.
Источник: Agent-Based Economic Modeling

Аннотация

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

1. Введение

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

Мы стремимся к созданию общей равновесной модели, представляющей рынок компаний, производящих разнообразные товары с различными производственными процессами, к созданию модели, которая будет точно отражать поведение предложения, спроса и цен в реальном секторе экономики. Классическая модель этого рынка — известная Модель Вальраса для N различных товаров, произведенных из М различных ресурсов (факторы производства), где общее равновесие достигается за счет максимизации прибыли каждого агента; для более детального описания смотреть (Black, 1995). Модель общего равновесия приводит к приемлимым математическими свойствами (закон Вальраса и др.). Однако, эта модель предполагает, что каждый агент совершенно рационален и неограничен в вычислении, и общее равновесие является статическим, в то время как реальный мировой рынок пытается достигнуть равновесия в постоянно меняющемся мире. Таким образом, возникает необходимость разработки агентных моделей с ограниченными и обучающими агентами.

(Zimmermann, Neuneier и Grothmann, 2001) предлагает агентную модель FX-рынка, где агенты основывают свои решения на неполной информации, приходящей из ограниченного числа подверженным ошибкам источникам информации. Агенты моделируются как исправляющие ошибки нейронные сети. (Kooths, Mitze и Ringhut, 2004) и (Kooths, 1999) создали макроэкономическую модель, где агенты моделируются как нейронные сети с дополнительными нечеткими правилами, представляющими знания об экономике. Другие подходы также были протестированы; для подробного обзора экономических агентных моделей смотреть (LeBaron, 2006), (Tesfatsion, 2006) и ссылки в них.

Агентные модели с агентами представленными в виде конечных автоматов широко используются в компьютерной анимации (см., например, (Rudomin, Millan, и Hernandez, 2005)), в то время как изучение конечных автоматов уже было применено в автоматном программировании, разработаном следующими учеными: (Shalyto и Tukkel, 2001).

Разработанные системы реактивных агентов с конечными автоматов были предложены (Naumov, Shalyto, 2003). Авторы утверждают, что их подход может позволить создавать системы самообучающийся адаптивных агентов. Подход получил дальнейшее развитие (Shalyto, Naumov, Korneev, 2005), где взаимодействие между объектами было рассмотрено как взаимодействие между конечными автоматами. Наконец, теория была применена к созданию реактивной Многоагентной среды в реальных условиях, а именно системы роботов, которые доставляют товары из одного места в другое ((Yartsev, Korneev, Shalyto, Kotov, 2005). Все роботы в этой системе контролировались логикой конечных автоматов.

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

Статья организована следующим образом. Раздел 2 описывает саму модель: в 2.1, мы покажем, как создать модель компании с конечными автоматами, и 2.2 описывает рынок модели в нашем подходе, и показывает конкретный пример производственного цикла. Раздел 3 дает перечень результатов экспериментов; мы показываем, что модель ведет себя так же, как и было условлено в экономическом законе, что, таким образом, устанавливает, что модель работает.

2. Описание модели

2.1. Моделирование производства с конечными автоматами

Машина c конечными состояниями является ориентированным графом с подписями по краям FA=(V,E,∑), где V есть множество вершин, ∑ является алфавитом автомата, (набор входных событий), и E={e=(ν₁,ν₂,σ)|ν₁,ν₂ ∈ V, σ ∈ ∑} это множество ребер (возможных переходов). Ребро e=(ν₁,ν₂,σ) означает, что переход от ν₁ до ν₂ с входным событием σ возможeн. Конечные автоматы имеют два вида специальных вершин: уникальную s ∈ V, помеченную в качестве начальной вершины и некоторые {t₀,...,t_K} ∈ V, представляющие множество терминальных вершин. Иногда бывает целесообразно связать как входящие, так и выходящие события с каждой вершиной. Тогда Tr=(V,E,∑,∏), E={e(ν₁,ν₂,σ,π)|ν₁,ν₂ ∈ V, σ ∈ ∑, π ∈∏} (эти автоматы, как правило, называют преобразователями). Путь в конечном автомате есть упорядоченное множество P=(ν₀,e₀,ν₁,e₁,...,ν_L)|e₀=(ν₀,ν₁,σ₀,π₁), e₁=(ν₁,ν₂,σ₁,π₁),...,e_L-1=(ν₀,ν₁,σ_L-1,π_L-1). Мы называем термином ILabel(P)=σ₀,σ₁,...,σ_L-1 входную метку пути Р, а под выходной меткой мы понимаем OLabel(P) =π₀,π₁,...,π_L-1. Цикл представляет собой путь с одинаковым стартом и финишем: ν₀=ν_L.

Мы опишем полный рабочий пример производственного цикла конечного автомата ниже; более подробную информацию о конечных автоматах можно найти в (Lothaire 2005).

Мы моделируем производственный цикл каждого агента, как конечный автомат. Состояние конечного автомата соответствует определенной стадии производственного процесса. Начальное состояние соответствует нулевой стадии производства; продукт затем путешествует из одного производственного отдела в другой, как конечный автомат из одного из одного состояния в другое.

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

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

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

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

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

Наконец, в реальном мире поведение агентов является только субоптимальными: агенты не обладают полной информацией о рынке и иногда не могут вычислить лучшую стратегию. Имея это в виду, мы моделируем агентов, имеющих довольно простые стратегии. Агент моделируется как пара конечный автомат FMS — стратегия S.

2.2. Моделирование рынка

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

Обратите внимание, как модель естественно представляет взаимодополняющие товары и заменителей. В экономике, товары называются дополнительными если перекрестная эластичность их спроса

E_c=((Q₁^B-Q₀^B)(P₁^A+P₀^A))/((Q₁^B+Q₀^B)(P₁^A-P₀^A))

положительна, и товары являются взаимозаменяемыми, если перекрестная эластичность отрицательна (здесь Q₀^B, Q₁^B — значения спроса для товара B до и после того, как цена товара А изменились, P₁^A, P₀^A — цены на товар А). В модели конечных автоматов, дополнительные товары часто появляются на последовательных концах производства конечного автомата, в то время товаров-субституты появляются на параллельных краях или краях параллельных путей конечного автомата. Это приводит к тому, что когда агент покупает определенный товара, его спрос на взаимодополняемости увеличивается (он находится на полпути к концу производства, поэтому он нуждается, чтобы завершить его), а его спрос на заменители уменьшается (он уже прошел через определенный путь, и он не вернется к параллельному краю в этом цикле).

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

Начальное состояние помечается как 0, а 3 и 5 — конечные состояния. Этикетки с − и + обозначают ресурс затрат и ресурсов исходов, соответственно; пример имеет четыре различных ресурса, от R1 до R4. Далее следует пример производственного цикла.

1. Регистрация предложений. Предположим, что другие агенты F₁... F_N зарегистрировали следующие предложения:
   <R1, price=1.0, amount=12.0>,
   <R1, price=2.0, amount=34.0>,
   <R1, price=3.0, amount=45.0>,
   <R2, price=10.0, amount=67.0>,
   <R3, price=4.0, amount=89.0>.
   
2. Решение по производственному пути. Агент D анализирует ситуацию на рынке и решает, что пути {0, 1, 2, 3} будут лучше, чем путь {0, 4, 5}. Мы не уточняем здесь, как агент D выбирает свой путь; он может руководствоваться усиленным обучающим алгоритмом или полным статистическим анализом истории рынка.
3. Покупка ресурсов. Чтобы начать свой производственный цикл, А необходимо купить 1,0 ресурса R1. Он посылает запрос на покупку R1. Рынок случайным образом выбирает подмножество зарегистрированных предложений, скажем,
   <R1, Price=1.0, amount=12.0>,
   <R1, Price=3.0, amount=45.0>,
   и показывает, что это множество D. Агент D выбирает наиболее выгодное предложение с ценой 1,0 и делает свою покупку.
4. Переход. Агент D теперь имеет необходимые ресурсы для завершения первого этапа своей стратегии и перейти в состояние 1.
   Обратите внимание, что после этих шагов агент D полностью привязан к своему выбранному производственному пути; он не может переключиться на производство R4, пока не завершен цикл R3, даже если в состоянии 2 он вдруг обнаруживает, что рынку отчаянно не хватает R4, и цены могут оказаться непомерно высокими. Мы пропустим несколько шагов, как D собирает все необходимые ресурсы и завершает свой производственный цикл. Предположим, что А только что сделал переход из состояния 3 в состояние 0 и получил 10,0 единиц R3.
5. Регистрация предложения о продаже. Так как D теперь имеет избыток R3, он будет желають зарегистрировать предложение продать R3. Опять же, мы не точно определили решение правила, но в качестве входа D должен учитывать, как его производственную стоимость, так и ситуацию на рынке, которую он способен выбрать из просмотра случайного подмножества предложений на R3. После этого шага происходит повторение производственного цикла. У D появляется возможность выбрать другой путь.

3. Эксперименты

Мы внедрили модель конечных автоматов на рынок и поставили опыты, которые были направлены на проверку основных экономических фактов о модели; они должны служить как «санитарная проверка» для нашего метода моделирования. В общем, модель оказалась чрезвычайно жизнеспособной, в определенные случаи всегда все выполняет так, как экономическая теория предсказывает. Таким образом, мы ожидаем у нее определенную степень предсказуемости, но это должно быть поддержано дальнейшими практическими экспериментами. В этом разделе мы опишем проведенные эксперименты.

3.1. Граница производственного потенциала

Граница производственного потенциала представляет собой кривую, которая показывает максимальный объем производства определенного товара, который зависит от уровня производства другого товара. Эта функция должна снижаться, а повышение уровня производства определенного товара должно снизить количество ресурсов, которые рынок готов назначить для производства других товаров. Кроме того, она должна быть выпуклой, как в переходе от товаров А к товарным B, рынок будет в первую очередь менять ресурсы, которые наиболее полезны для B и наименее полезны для А.

Наш экспериментальный сценарий включал два товара: А (автомобили) и B (одеяла). Каждый агент имеет возможность производить оба товара, и конечный автомат агента имеет несколько путей, соответствующих различным выходам соотношения (автомобилей) / (одеял) из товаров, которые этот агент производит во время производственного цикла. Кроме того, у каждого агента есть персонализированное производство конечного автомата, которое имеет свою собственные случайно изменяющиеся затраты производства в A / B соотношении. Определенный «командный центр» приказывает некоторым агентам переключиться из производства А в Б, и агенты (с некоторой задержкой, как описано выше) меняют производство; оставшиеся агенты действуют в своих собственных интересах. На рис. 2 представлены результаты этого эксперимента: граница производственного потенциала почти выпуклая, с небольшие колебаниями, которые могут быть связаны с оптимальным поведение агентов.

3.2. Перенасыщение

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

На рис. 3 представлены результаты эксперимента; диаграмма справа показывает, как ведут себя цены со временем, график в середине показывает, сколько активных агентов производят что-либо в это время, и график справа показывает валовый объем продаж. Обе кривые ведут себя, как и было предсказано при достижении равновесия.

3.3. Равновесие

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

3.4. Сырье и конечные продукты

В этом эксперименте мы разделили девять товаров модели на две группы: {r0, r1, r2} и {r3, ..., r8}. Предположим, что производство товара сильно зависит от других товаров своей группы и гораздо в меньшей степени от товаров другой группы. Во время 1000, введем агента, который покупает много r0, что повышает цены. В результате, цены на R1 и R2 также возрастают, а цены на R3, ..., R8 остаются практически прежними. Рис. 5а показывает график цены.

3.5. Взаимодополнители и заменители

В первой части этого эксперимента r0, r1 и r2 являются взаимодополняемыми, то есть, мы увеличиваем вероятность того, что они появляются на последовательных краях производства конечных автоматов. Увеличение цен на r0 должно вызывать снижение спроса на R1 и R2.

Рис. 5b показывает, что происходит, если в момент времени 1000 мы введем агента, который покупает много r0. Рынок реагирует ростом всех цен, за исключением R1 и R2: так как производители покупают меньше r0, им также требуется меньше R1 и R2. На рис. 6а показан тот же эксперимент, однако, только с эти три товара осталось на рынке, а на рис. 6b показаны результаты эксперимента с тремя товарами, среди которых r0 и r2 являются взаимодополняемыми: увеличение цены r0 приводит к увеличению цены r2.

Во второй части этого эксперимента, представим r0, r1 и r2 в качестве заменителей, то есть увеличим вероятность того, что они появляются на параллельных путях в производстве конечных автоматов. В момент времени 600, мы ввели агента, который покупает много r0, тем самым увеличивая его цену; в результате агенты начинают использовать меньше r0 и больше r1 и r2. Рис. 6a показывает графики объема цены для трех ресурсов в этом эксперименте. Рис. 7 показывает объем спроса для эксперимента с заменой товара.

4. Заключение

В данной работе мы ввели новый подход к моделированию агентов, которые выступают в качестве производителей и потребителей на рынке. Мы cмоделировали производство агента в виде конечных автоматов с отработанными и произведенными ресурсами, как входные и выходные действия. Мы показали, что конечный автомат является естественным способом моделирования производства компании, и показали, как моделировать основные свойства экономического агента и основные типы сырьевого рынка посредством конечных автоматов. Мы реализовали предложенную модель и выполнили эксперименты для того, чтобы убедиться, что модель работает, и она, действительно, работает: во всех экспериментах использованная модель вела себя, как и ожидалось.

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

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

Сcылки

1. F. Black. 1995. Exploring General Equilibrium. The MIT Press, Cambridge, Massachusetts.
2. G. Zimmermann, R. Neuneier and R. Grothmann. 2001. Multi-agent FX-Market Modeling Based on Cognitive Systems. In Proceedings of the Artificial Neural Networks, ICANN 2001, Lecture Notes in Computer Science, Vol. 2130, pp. 767–774.
3. S. Kooths. 1999. Modelling Rule- and Experience-Based Expectations Using Neuro-Fuzzy Systems. In Computing in Economics and Finance — Fifth Conference of the Society for Computational Economics, Boston.
4. S. Kooths, T. Mitze and E. Ringhut. 2004. Forecasting the EMU Inflation Rate: Linear Econometric Versus Non-Linear Computational Models Using Genetic Neural Fuzzy Systems. Advances in Econometrics, Vol. 19, pp. 145–173.
5. B. LeBaron. 2006. Agent-based Computational Finance, in Handbook of Computational Economics, L. Tesfatsion and K. Judd (eds.). North-Holland, Amsterdam, pp. 1187–1232.
6. L. Tesfatsion. 2006. Agent-Based Computational Economics: A Constructive Approach to Economic Theory, in Handbook of Computational Economics, L. Tesfatsion and K. Judd (eds.). North-Holland, Amsterdam, pp. 831–880.
7. I. Rudomin, E. Millan and Hernandez, B. 2005. Fragment shaders for agent animation using finite state machines. Simulation Modelling Practice and Theory, Vol. 13, Issue 8, pp. 741–751.
8. A. Shalyto and N. Tukkel. 2001. SWITCH-Technology: An Automated Approach to Developing Software for Reactive Systems. Programming and Computer Software, Vol. 27, No. 5, pp. 260–276.
9. L. Naumov and A. Shalyto. Automata Theory for Multi-Agent Systems Implementation Integration of Knowledge Intensive Multi-Agents Systems (KIMAS’03), IEEE Boston Section, 2003, pp. 65–70.
10. A. Shalyto, L. Naumov and G. Korneev. Methods of Object-Oriented Reactive Agents Implementation on the Basis of Finite Automata Integration of Knowledge Intensive Multi-Agents Systems (KIMAS’05), USA, MA: IEEE Boston Section, 2005, pp. 460–465.
11.B. Yartsev, G. Korneev, A. Shalyto and V. Kotov. Automata-Based Programming of the Reactive Multi-Agent Control System Integration of Knowledge Intensive Multi-Agents Systems (KIMAS’05), USA, MA: IEEE Boston Section, 2005, pp. 449–453.
12. M. Lothaire. 2005. Applied Combinatorics on Words. Cambridge University Press.