メインメニューを開く

差分

進化的計算

4,539 バイト追加, 11 年前
英語版の最新版までの主な更新を翻訳してマージ
[[計算機科学]]において、'''進化的計算'''(evolutionary computation)は[[組合せ最適化]]問題を含む[[人工知能]](より狭義には[[計算知能]])の一分野である。[[進化的アルゴリズム]]が一般に[[生殖]]、[[突然変異]]、[[遺伝子組み換え]]、[[自然淘汰]]、[[適者生存]]などのメカニズムを実装するための技術を指すのに対して、進化的計算は
 
進化的計算は、[[人口]]増加のような反復的過程を用いる。その人口は目的の結果に合うように誘導された[[ランダム]]かつ並列的な探索によって[[人為選択]]される。このような過程は、[[進化]]の生物学的機構にヒントを得ている。
* 反復的な発展、成長、または開発
* [[人口]]をベースとしたもの
* 誘導[[ランダム]]な探索
* 並列処理
* (しばしば)生物学にヒントを得たもの
 
== 歴史 ==
のような緩やかな基準によって特徴付けられ、主に以下のような[[メタヒューリスティック]]な[[最適化]][[アルゴリズム]]が含まれる。
1950年代、コンピュータが広く使われる以前に、[[ダーウィニズム]]の原理を自動問題解決に使うという発想が生まれた。[[1960年代]]、この考え方の具体化が3つの場所で独立に行われた。
 
[[アメリカ合衆国]]では、[[ローレンス・J・フォーゲル]]が[[進化的プログラミング]]を提唱した。また、[[ジョン・H・ホランド]]が[[遺伝的アルゴリズム]]と呼ばれる技法を生み出した。[[ドイツ]]では Ingo Rechenberg と Hans-Paul Schwefel が[[進化戦略]]を提唱した。これらは約15年間、独立して研究が進められた。[[1990年代]]初め、これらが1つの技術を表していることが明らかとなり、総称して進化的計算と呼ばれるようになった。また、同じころ第四の技法として[[遺伝的プログラミング]]が登場した。
 
== 技法 ==
のような緩やかな基準によって特徴付けられ、主進化的技法以下のような[[メタヒューリスティック]]な[[最適化]][[アルゴリズム]]が含まれる。
 
* [[進化的アルゴリズム]]([[遺伝的アルゴリズム]]、[[進化的プログラミング]]、[[進化戦略]]、[[遺伝的プログラミング]]から構成される)
また、他にも以下のような分野も含む。
 
* [[自己組織化写像]]、成長するニューラルガスネットワーク、[[競合学習]]などの[[自己組織化]][http://www.neuroinformatik.ruhr-uni-bochum.de/ini/VDM/research/gsn/DemoGNG/GNG.html demo applet]
* [[微分進化]]
* [[人工生命]](また、[[デジタル有機体]]を参照されたい)
* 文化的アルゴリズム
* [[人工免疫系]]
* [[:en:Learnable Evolution Model|Learnable Evolution Model]]
 
== 進化的アルゴリズム ==
{{main|進化的アルゴリズム}}
[[進化的アルゴリズム]]は、進化的計算の一部であり、[[生殖]]、[[突然変異]]、[[遺伝子組み換え]]、[[自然選択説|自然淘汰]]、[[適者生存]]などの生物学的[[進化]]から発想されたメカニズムを実装する技術にのみ関わる。最適化問題の解候補は、それぞれが個体の役割を果たし、コスト関数によって与えられた環境でその解が「生き残る」かどうかが決定される。個体群の[[進化]]は、上述の作用を繰り返し適用することでなされる。
 
この過程には、進化系の基盤を形成する2つの主な力が存在する。'''組み換え'''と'''突然変異'''によって必要な多様性を生成する一方、'''選択'''によって性能/品質を向上させる。
 
このような進化的過程は様々な意味で確率的である。情報のうち組み換えや突然変異で変化する部分はランダムに選ばれる。一方、選択手法は決定的なものと確率的なものがありうる。後者の場合、適応度が高い個体ほど選択される確率が高いが、弱い固体であっても生き残って子孫を残す可能性がある。
 
== 主な会議とワークショップ ==
* The Genetic and Evolutionary Computation Conference (GECCO)
* IEEE Congress on Evolutionary Computation (CEC)
* Parallel Problem Solving from Nature (PPSN)
* The Foundations of Genetic Algorithms workshop (FOGA)
* The [http://iridia.ulb.ac.be/~ants/ants2006/ Workshop on Ant Colony optimization and Swarm Intellligence (ANTS)]
* The Evo* and EuroGP [http://evonet.lri.fr/eurogp2006/ workshops]
 
== 学会誌 ==
* ''[http://mitpress.mit.edu/catalog/item/default.asp?ttype=4&tid=25 Evolutionary Computation]''
* ''[http://ieee-cis.org/pubs/tec/ IEEE Transactions on Evolutionary Computing(英語)Computation]''
* ''[http://www.springer.com/journal/10710/ Genetic Programming and Evolvable Machines]''
 
==関連項目==
* [[ノーフリーランチ定理]]
 
== 参考文献 ==
* A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, 2003, ISBN 3-540-40184-9
* A.E. Eiben and M. Schoenauer, Evolutionary computing, Information Processing Letters, 82(1): 1-6, 2002.
* W. Banzhaf, P. Nordin, R.E. Keller, and F.D. Francone. Genetic Programming — An Introduction. Morgan Kaufmann, 1998.
* D. B. Fogel. Evolutionary Computation. Toward a New Philosophy of Machine Intelligence. IEEE Press, Piscataway, NJ, 1995.
* H.-P. Schwefel. Numerical Optimization of Computer Models. John Wiley & Sons, New-York, 1981. 1995 – 2nd edition.
* Th. Bäck and H.-P. Schwefel. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1(1):1–23, 1993.
* J. R. Koza. Genetic Programming: On the Programming of Computers by means of Natural Evolution. MIT Press, Massachusetts, 1992.
* D. E. Goldberg. Genetic algorithms in search, optimization and machine learning. Addison Wesley, 1989.
* J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.
* I. Rechenberg. Evolutionstrategie: Optimierung Technisher Systeme nach Prinzipien des Biologischen Evolution. Fromman-Hozlboog Verlag, Stuttgart, 1973.
* L. J. Fogel, A. J. Owens, and M. J. Walsh. Artificial Intelligence through Simulated Evolution. New York: John Wiley, 1966.
 
== 外部リンク ==
*[http://www.evolutionary-computing.eu Evolutionary Computing Research Community Europe]
*[http://ieee-cis.org/pubs/tec/ IEEE Transactions on Evolutionary Computing(英語)]
*[http://www.fmi.uni-stuttgart.de/fk/evolalg/ Evolutionary Computation Repository(英語)Repository]
*[http://www.cse.dmu.ac.uk/~rij/gafaq/top.htm Hitch-Hiker's Guide to Evolutionary Computation (FAQ for comp.ai.genetic)]
*[http://www.vita-sciences.org/ VitaSCIENCES]
 
[[category:アルゴリズム|しんかてきけいさん]]
25,487

回編集