文化アルゴリズム（Cultural Algorithm）について <2.28 更新>
初めに
1月29日に行われた「人工知能のための哲学塾 第三期 第参夜」に参加した時、三宅陽一郎さんの講演の中で文化アルゴリズム（文化的アルゴリズム）についての話があり、興味を持ったので調べてみました。
ただ、日本語で分かりやすく書いた文献というのはぱっと見てみた（Google検索）ところではありませんでした。そのため、自分なりに文化アルゴリズムとはどのようなものなのかについてまとめて行きたいと思います。
ここでは、哲学塾で使われた三宅陽一郎さんの資料[1]（下）も含め、特に最近の資料であると考えられる文化アルゴリズムの提唱者のReynolds (2018) [2]の文献を参照しながらまとめていきます。
www.slideshare.net
注意点
しかしながら、前提知識が不足しているところも多く、読んでまとめるのには時間がかかりそうなので、出来るところから記事にしていきアップデートしていく形で書いていきます。また、まとめたものには間違い等もあるかもしれませんのでご了承ください（お気づきの点等ございましたらTwitterにお願いします）。
文化アルゴリズムとは
文化アルゴリズムは、Robert G. Reynoldsが1979年に提案した[]進化的計算モデル（evolutionary comuputational model）で、文化の進化過程から着想を得たモデルになっています。
このアルゴリズムは計算モデルであり、その目的は与えられた問題を解くことです。そこに文化の進化過程を取り入れたということはどのようなことでしょうか。
まず、文化アルゴリズムにおける文化の進化過程の様子を以下の図1に示します。
では、アルゴリズムにおいてはどのように表現されているのでしょうか。以下の図2に文化アルゴリズムの疑似コード（[2]より）を示します。
ここでは、図3の文化アルゴリズムのモデル図（[2]を参考に作成）をもとに大まかな流れを見ていきます（アルゴリズムの詳細については別記事にする予定です）。
まず、図中のPopulation spaceが各個体が集まった個体群を表しています。そして、各個体が経験した知識がBelief Spaceにaccept()によって集められます。そして、このBelief SpaceでのUpdate()によって知識が継承されます。ここでの継承とはBelief Space内にある知識を更新することに当たります。そして、継承された知識が、influence()によってPopulation spaceに影響し、新たな世代が生まれる（generate()）という流れになっています。
以上が文化アルゴリズムとは何かについての簡単な説明となります。
Population SpaceとBelief Spaceについてもう少し詳しく
文化アルゴリズムにおいては、Population SpaceとBelief Spaceとのやり取りが重要になるため、これらが何を表しているのかについて、改めてまとめおきます。
- Population Space → 知識を継承していく（進化していく）個体群を管理する場所
まず、Population Spaceは、ある世代における個体群（Individals）を持っています。この個体というのは、問題を解くためのエージェントまたは変数を表しています。ここで集められた知識がBelief Spaceを通して、次の世代へ継承されていくという流れです。
- Belief Space → 知識を継承させていく場所
一方、Belief Spaceはある世代の個体群から知識を集めた知識を用いて、蓄積された知識を更新します。そして、次の世代へと引き継ぐことによって知識を継承させていきます。
文化アルゴリズムの応用
文化アルゴリズムの応用は幅広くされており、文献[2]において、自然言語処理やマルチエージェントシステム、ゲームプログラミング分野へ応用した研究が参考文献として挙げられています（ゲームプログラミングへの応用研究として挙げられていた文献は[13],[14],[15],[16]）。
しかしながら、人工知能の哲学塾の講演で三宅陽一郎さんが触れられていましたが、日本で研究されている方は少ないそうで、先に述べたように日本語で手に入れることができる文化アルゴリズムを主題にした文献（書籍や論文、サイト等）は見つけることができませんでした。このため、全て詳細に目を通した訳ではないですが探していて気になった文献は参考文献として載せていきますので、そちらもご確認ください。
参考文献および文献集
（記述形式がバラバラですみません）
文化アルゴリズム
[1] https://www.slideshare.net/youichiromiyake/ss-129681897 <2019/2/9アクセス>
[2] R. G. Reynolds, "An Introduction to Cultural Algorithms", in Proceedings of the 3rd Annual Conference on Evolutionary Programming, 1994.
- 作者: Robert G. Reynolds
- 出版社/メーカー: Springer
- 発売日: 2018/05/02
- メディア: Kindle版
- この商品を含むブログを見る
https://link.springer.com/book/10.1007/978-3-319-74171-0
[3] Reynolds RG, (1979) An adaptive computer model of the evolution of agriculture in the valley of Oaxaca. Mexico Dissertation, University of Michigan, Ann Arbor
[4] R. G. Reynolds, "An Introduction to Cultural Algorithms", in Proceedings of the 3rd Annual Conference on Evolutionary Programming, 1994.
[5] C.–J. Chung and R. G. Reynolds, "A Testbed for Solving Optimization Problems Using Cultural Algorithms", in Evolutionary Programming V: Proceedings of the Fifth Annual Conference on Evolutionary Programming, 1996.
[6] Jason Brownlee (2015) "Clever Algorithms: Nature-Inspired Programming Recipes",
http://www.cleveralgorithms.com/nature-inspired/physical/cultural_algorithm.html
<2019/2/9アクセス>
文化アルゴリズムの応用例（主に文献[2]に挙げられていたもの）
・自然言語処理
[7] Stefan J, Reynolds RG, Fotouhi F, Aristar A, Lu S, Dong M (2003). Evolution based approaches to the preservation of endangered natural languages. In: Proceedings of the IEEE international congress on evolutionary computation, Australia, pp 1980–1987
・マルチエージェントシステム
[8] Reynolds RG, Kobti Z, Kohler T (2003) A multi-agent simulation using cultural algorithms: the effect of culture on the resilience of social systems. In: Proceedings 2003 I.E. proceedings of congress on evolutionary computation, Canberra, Australia, 8–12 Dec 2003, pp 1743–1750
[9] Reynolds RG, Kobti Z, Kohler T (2004) The effect of culture on the resilience of social systems in the village multi-agent simulation. In: Proceedings of IEEE international congress on evolutionary computation, Portland, OR, 19, 24 June 2004, pp 1743–1750
[10] Reynolds RG (2003) Predicting the past using multi-agent models of cultural evolution, 16–19 April. Midwest Sociological Society, Chicago, IL
[11] Reynolds RG, Chung C (1997) A cultural algorithm to evolve multi-agent cooperation using cultural algorithms. In: Angeline PJ, Reynolds RG, McDonnell JR, Eberhart R (eds) Evolutionary programming VI. Springer, Berlin, pp 323–334
[12] Lazar A, Reynolds RG (2002) Evolution-based learning of ontological knowledge for a large-scale multi-agent simulation. In: Proceedings of the 6th joint conference on information science, USA, pp 659–662
・ゲームプログラミング
[13] Loiacono D, Togelius J, Lanzi PL, Kinnaird-Heether L, Lucas SM, Simmerson M, Perez D, Reynolds RG, Saez Y (2008) The WCCI 2008 simulated car racing competition. In: Proceedings of the IEEE symposium on computational intelligence and games
[14] Reynolds RG, Ali MZ, Alomari RS (2006) Optimization problem solving using predator/prey games and cultural algorithms. In: CIG 2006, pp 119–125
[15] Reynolds RG, O’Shea J, Che X, Gawasmeh YA, Meadows G, Fotouhi F (2011) Agile design of reality games online. In: Chen S-H, Kambayashi Y, Sato H (eds) Multi-agent applications with evolutionary computation and biologically inspired technologies: intelligent techniques for ubiquity and optimization. IGI Global, Hershey, PA
[16] Vitale K, Reynolds RG, O’Shea J, Che X (2011) Learning group behavior in games: using cultural algorithms: the land bridge game engine example. In: Swarm intelligence IEEE symposium, pp 1–9
・工学デザイン
[17] Yan, Xuesong et al. “Cultural Algorithm for Engineering Design Problems.” (2012).
https://www.semanticscholar.org/paper/Cultural-Algorithm-for-Engineering-Design-Problems-Yan-Li/1db777ea10d113e5c95e0662bf384626960453c9 から入手可能
・イメージマッチング
[18] Xuesong Yan, Tao Song, and Qinghua Wu. 2017. An improved cultural algorithm and its application in image matching. Multimedia Tools Appl. 76, 13 (July 2017), 14951-14968.
その他
・進化的計算について
[19] 進化計算とは(what is evolutional algorythm) <2019/2/9アクセス>
[20] 進化的計算 - Wikipedia <2019/2/9アクセス>
