プログラムの維持・改良システム、及びコンピュータ読み取り可能なプログラム
【課題】プログラムをより安定して維持・改良すること。
【解決手段】対象プログラムを実行する実行手段（２０）と、所定の記憶手段に記憶された削除待ち行列に従って対象プログラムを削除する削除手段（２２）と、実行終了した対象プログラムについて、数値化された実行結果が目標値と合致した場合に最大値を評価値として出力すると共に数値化された実行結果が目標値から離れるに従って小さくなる値を評価値として出力する傾向を有する評価関数によって、評価を行なう評価手段（２４）と、評価手段による評価値に基づいて、対象プログラムの前記削除待ち行列における削除順位を変更する削除順位変更手段（２６）と、評価手段による評価値に基づいて、対象プログラムを複製する複製手段（２８）と、を備えるプログラムの維持・改良システム（１）。
【解決手段】対象プログラムを実行する実行手段（２０）と、所定の記憶手段に記憶された削除待ち行列に従って対象プログラムを削除する削除手段（２２）と、実行終了した対象プログラムについて、数値化された実行結果が目標値と合致した場合に最大値を評価値として出力すると共に数値化された実行結果が目標値から離れるに従って小さくなる値を評価値として出力する傾向を有する評価関数によって、評価を行なう評価手段（２４）と、評価手段による評価値に基づいて、対象プログラムの前記削除待ち行列における削除順位を変更する削除順位変更手段（２６）と、評価手段による評価値に基づいて、対象プログラムを複製する複製手段（２８）と、を備えるプログラムの維持・改良システム（１）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラムを複製及び評価することによりプログラムの維持・改良を図るコンピュータシステム、及びコンピュータを当該システムとして機能させるためのコンピュータ読み取り可能なプログラムに関する。
【背景技術】
【０００２】
従来、コンピュータシステムにより最適解を求める方法として、遺伝的アルゴリズム（Genetic Algorithm；ＧＡ）が知られている。これは、遺伝子に見立てた複数のデータ（解の候補）に対して交叉・突然変異などの遺伝的操作を繰り返し、ルーレット選択方式、トーナメント選択方式、エリート戦略等の組み合わせにより、生成されたデータのうち適応度が相対的に高いものを生存させることによって最適解を求めるものである。
【０００３】
遺伝的アルゴリズムを応用した学習装置等についての発明が開示されている（例えば、特許文献１参照）。この装置では、初期設定として記憶された個体及びこれに遺伝的操作を行なって生成される個体等に対して、適応度に基づく選択と、適応度とは無関係な選択と、を組み合わせて生存選択を行なっており、局所最適解に陥りやすい等の遺伝的アルゴリズムの問題点を部分的に解消している。
【０００４】
また、遺伝的アルゴリズムを拡張したものとして、遺伝的プログラミング（Genetic Programming；ＧＰ）が知られている。これは、遺伝子型の表現に木構造を用いることにより、扱うデータをプログラムにまで拡張したものである。
【特許文献１】特開２００３−１６８１０１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、遺伝的プログラミングにおいては、例えば、複数のプログラムの実行が完了した時点で、外部から与えられた目的を相対的に高く達成したプログラムを優先的に生存させる処理が行なわれるため、プログラムの一部が正常に終了しなかった場合（例えばハングアップした場合等）に全体の処理が中断し、外部から与えられた目的を達成するのに適したプログラムを生成するに至らない場合が生じる。
【０００６】
本発明はこのような課題を解決するためのものであり、プログラムをより安定して維持・改良することが可能なプログラムの維持・改良システム、及びコンピュータを当該システムとして機能させるためのコンピュータ読み取り可能なプログラムを提供することを、主たる目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するための本発明の第１の態様は、
対象プログラムを実行する実行手段と、
所定の記憶手段に記憶された削除待ち行列に従って前記対象プログラムを削除する削除手段と、
実行終了した前記対象プログラムについて、数値化された実行結果が目標値と合致した場合に最大値を評価値として出力すると共に数値化された実行結果が目標値から離れるに従って小さくなる値を評価値として出力する傾向を有する評価関数によって、評価を行なう評価手段と、
前記評価手段による評価値に基づいて、前記対象プログラムの前記削除待ち行列における削除順位を変更する削除順位変更手段と、
前記評価手段による評価値に基づいて、前記対象プログラムを複製する複製手段と、
を備えるプログラムの維持・改良システムである。
【０００８】
ここで、「対象プログラム」とは、ＯＳを構成するモジュールやアプリケーションプログラム等、如何なるものであってもよい。
【０００９】
また、「評価関数に基づいて」とは、評価手段の直近の評価値に基づいて（例えば、閾値と比較する等して）対象プログラムを複製等すること、及び評価手段の評価値の履歴に基づいて（同上）対象プログラムを複製等することの双方を含む。
【００１０】
また、「目標値」を「目標領域」に置換してもよい。すなわち、目標値自体に一定の幅をもたせ、対象プログラムの実行結果が目標領域の範囲内であれば最大値を出力するものとしてもよい。
【００１１】
この本発明の第１の態様によれば、他の対象プログラムとの比較ではなく、当該対象プログラムの絶対評価を出力する評価関数を用いて対象プログラムの優劣が評価されるため、対象プログラムのうちいずれかが正常に終了しない場合であっても他の対象プログラムの評価が可能となり、システム全体の作動が停止する事態が生じるのを抑制することができる。従って、プログラムをより安定して維持・改良することが可能となる。
【００１２】
また、対象プログラムは上記任意の目的に対する達成度を適切に示す指標値である評価値に基づいて複製及び削除されるため、優秀なプログラムを適切に残存させることができ、プログラムを適切に進化させることができる。
【００１３】
本発明の第１の態様において、前記削除順位変更手段は、前記評価手段による評価値が前記最大値である場合に、該評価された対象プログラムの前記削除待ち行列における削除順位が下がるように、前記対象プログラムの前記削除待ち行列における削除順位を変更する手段であるものとしてもよい。こうすれば、正常に終了しない対象プログラムは、削除順位変更手段により削除順位が下げられないため、いずれ削除手段により削除されることとなる。従って、プログラムを適切に進化させることができる。
【００１４】
また、本発明の第１の態様において、対象プログラムに変異を生じさせる変異処理手段を備えることが望ましい。
【００１５】
また、本発明の第１の態様において、前記評価関数の設定又は変更に関する外部からの入力を受け付ける評価関数入力受付手段を備えるものとしてもよい。
【００１６】
また、本発明の第１の態様において、前記評価手段の評価値を記憶する評価値記憶手段を備え、前記複製手段は、前記評価値記憶手段に記憶された評価値の履歴に基づいて、前記対象プログラムを複製する手段であるものとしてもよい。こうすれば、対象プログラムを複製する具体的手法の幅を広げることができる。
【００１７】
この場合、前記複製手段は、前記評価値記憶手段に記憶された評価値の累計値に基づく値が所定の複製基準値を超えた場合に対象プログラムを複製する手段であるとすることが考えられる。これにより、目標を達成できなかった対象プログラムであっても、何回か実行を繰り返すうちに複製の機会が与えられることとなる。従って、対象プログラムが目標達成から外れた進化を遂げた場合であっても、更なる進化によって元の対象プログラムよりも優れたものとなる可能性を残すことができる。
【００１８】
更にこの場合、前記評価関数は、最低値として累計可能な値を出力する関数であるものとすると、好適である。こうすれば、何らかの外部要因や進化の過程により目標を達成できる対象プログラムが少数になり、ないし無くなってしまった場合でも、時間が経過すれば対象プログラムが目標を達成できる対象プログラムに進化できる可能性を残している。従って、目標を達成できる対象プログラムの維持という観点から、最低限の保証を得ることができる。
【００１９】
また、本発明の第１の態様は、宇宙空間で使用されることを特徴とするものとすると、特に好適である。
【００２０】
また、変異処理手段を有する本発明の第１の態様において、前記変異処理手段は、自己の作動に依らない対象プログラムの変異発生率に応じて前記対象プログラムに変異を生じさせる確率を変更する手段であるものとしてもよい。
【００２１】
本発明の第２の態様は、コンピュータを、本発明の第１の態様のプログラムの維持・改良システムとして機能させるための、コンピュータ読み取り可能なプログラムである。
【発明の効果】
【００２２】
本発明によれば、プログラムをより安定して維持・改良することが可能なプログラムの維持・改良システム、及びコンピュータを当該システムとして機能させるためのコンピュータ読み取り可能なプログラムを提供することができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を実施するための最良の形態について、添付図面を参照しながら実施例を挙げて説明する。
【実施例】
【００２４】
以下、本発明の一実施例に係るプログラムの維持・改良システム１（以下、単に「システム１」と称する）について説明する。本実施例のシステム１は、対象プログラムを変異させながら複製・削除する処理を繰り返し、変異した対象プログラムを目標達成により適したものとすること、及び目標を達成できる対象プログラムが継続して存在するように維持することを目的とする。以下、対象プログラムが変異によって元の対象プログラムと異なるものとなることを、「進化」と称する。
【００２５】
図１は、システム１を実現するためのハードウエア構成の一例を示す図である。システム１は、例えば、ＣＰＵ（Central Processing Unit）１０、ＲＯＭ（Read Only Memory）１１、ＲＡＭ（Random Access Memory）１２、ＨＤＤ（Hard Disk Drive）１３、入力受付装置１４、バス１５、その他タイマー、カウンター、マウス、キーボード等によって実現される。入力受付装置１４は、例えば、キーボードやＣＤ−ＲＯＭドライブ、ＤＶＤ装置、ＵＳＢ（Universal Serial Bus）等の汎用インターフェイス、有線又は無線による通信装置等が用いられる。なお、本構成はあくまで一例であり、本発明の適用上、ハードウエア構成に関する制限は何ら存在しない。例えば、後述する複数の対象プログラム毎に担当ＣＰＵを備える構成であってもよい。
【００２６】
図２は、システム１において、ＣＰＵ１０がＲＯＭ１１に記憶されたシステム実行プログラム（請求項１０における「コンピュータ読み取り可能なプログラム」に相当する）を実行することにより機能する機能ブロック、及びシステム１の作動に際してＲＡＭ１２等に記憶される情報を示す図である。システム１は、機能ブロックとして、対象プログラム実行部２０と、対象プログラム削除部２２と、対象プログラム評価部２４と、削除順位変更部２６と、対象プログラム複製部２８と、変異処理部３０と、を備える。また、ＲＡＭ１２等の所定領域には、対象プログラムリスト３２、削除待ち行列３４、及び評価値履歴３６が記憶される。
【００２７】
対象プログラム実行部２０は、対象プログラムリスト３２に記憶された複数の（システムの始動当初は単独である）対象プログラムを、例えばスライス実行方式によって並行して実行する。すなわち、対象プログラムリスト３２に含まれる対象プログラムがｎ個存在するとして、対象プログラムｋ（１≦ｋ≦ｎ）の１単位の命令を実行すると、次に対象プログラムｋ+１の１単位の命令を実行する。これをｋ＝1から順に実行し、対象プログラムｎまで実行し終えると、対象プログラム１に戻り、次の１単位の命令を実行する。図３は、対象プログラム実行部２０がスライス実行方式により複数の対象プログラムを並行して実行する様子を概念的に示す図である。なお、対象プログラム毎にＣＰＵを備える構成の場合、必ずしもスライス実行方式を採用する必要はなく、各対象プログラムが並行して同時に実行されてよい。
【００２８】
なお、対象プログラムの性質、属性等に特段の制限は存在せず、いわゆるアプリケーションプログラムやＯＳ（Operating System）、ミドルウエア等、如何なるソフトウエアを対象プログラムとしてもよい。
【００２９】
対象プログラム削除部２２は、所定のタイミングで、削除待ち行列３４に記憶された削除待ち行列に従って、対象プログラムリスト３２に含まれる対象プログラムのうち、削除順位の最も高いものを削除する。削除待ち行列は、その時点で対象プログラムリスト３２に記憶され、対象プログラム実行部２０により実行されている全ての対象プログラムを一次元に並べたものである。なお、「所定のタイミング」とは、後述する処理フローの１ルーチン毎、或いは所定時間毎等、定期的ないし周期的なものであればよい。
【００３０】
対象プログラム評価部２４は、対象プログラム実行部２０による実行が終了した対象プログラムについて、評価を行なって評価値を出力する。対象プログラムの評価は、所定の評価関数を用いて行なわれる。この評価関数は、数値化された実行結果ＥＸが目標値（以下、目標値Targetと称する）と合致した場合に最大値（以下、MAX_FITNESSと称する）を評価値（以下、評価値fitnessと称する）として出力すると共に、数値化された実行結果ＥＸが目標値Targetから離れるに従って小さくなる値を評価値fitnessとして出力する特性形状を有する関数である。図４に、本発明に係る評価関数の特性形状として考え得るものを列挙した。なお、本図はあくまで例示であり、上記の特性を満たす限りにおいて、いかなる変形・置換も許容される。これらから明らかなように、評価値fitnessは、任意の目的に対する達成度を示す指標値である。対象プログラム評価部２４の出力する評価値は、出力された順に評価値履歴３６に記憶される。なお、目標値Targetは、１点である必要はなく、所定の幅をもった目標領域であっても構わない。図４（Ｆ）〜（Ｈ）は、目標領域（Target領域）を定める場合の評価関数特性を例示したものである。数値化された実行結果ＥＸは、例えばレジスタやＲＡＭ、フラッシュメモリ等に、随時記憶される。
【００３１】
また、「数値化された実行結果ＥＸが目標値Targetから離れるに従って小さくなる」とは、厳密に単調減少傾向を有する必要まではなく、図１４（Ａ）〜（Ｅ）に示す如く、第２、第３…の峰部を有しても構わない。
【００３２】
更に、目標値Targetが必ずしも単独である必要はなく、目標値Targetが複数存在しても構わない。例えば、実行結果ＥＸが所定周期を経て同一結果とみなされるような場合や、符号を反転させると同一結果とみなされるような場合に、目標値Targetが複数存在しうる（注；例示であり、目標値Targetが複数存在する場合は、これらに限られない）。この場合、評価関数の特性形状は、図１４（Ｆ）〜（Ｈ）に示す如く、複数のピーク値を有する形状となる。
【００３３】
図４（Ａ）に示す評価関数の一般式は、次式（１）の如くである。評価値の最小値を値１に設定する理由については後述する。
【００３４】
fitness ＝（MAX_FITNESS／Target）×EX （EX≦Target）
or MAX_FITNESS×２−（MAX_FITNESS／Target）×EX （EX＞Target）
但し、min(fitness)＝１ …（１）
【００３５】
評価関数は、予めＲＯＭ１１等に記憶されているものとする。なお、複数の評価関数が予め記憶され、対象プログラムが実行する処理内容（タスク）に応じて適宜選択されてもよいし、後述する第２実施例の如く、外部から評価関数が入力又は選択されてもよい。
【００３６】
本実施例のシステム１は、対象プログラムの評価に際して他の対象プログラムの状態・出力を考慮していない。従って、対象プログラムのうちいずれかが正常に終了しない場合であっても、他の対象プログラムの評価が可能となり、システム全体の作動が停止する事態が生じるのを抑制することができる。
【００３７】
削除順位変更部２６は、対象プログラム評価部２４が出力する評価値fitnessが最大値MAX FITNESSである場合に、当該対象プログラムの削除待ち行列における削除順位が下がる（後回しにされる）ように、削除待ち行列における削除順位を変更する。すなわち、目標を達成した対象プログラムが削除されるのを先延ばしにする（寿命を延ばす）処理を行なう。これにより、目標値Targetを達成することができる対象プログラムを優先的に存続させることとなるため、与えられた目標を達成することが可能なプログラムを安定的に維持することができる。
【００３８】
対象プログラム複製部２８は、直近に評価がなされた対象プログラムについて、評価値履歴３６に記憶された評価値の履歴に基づく判定を行なって、判定結果に基づき当該対象プログラムを複製し、対象プログラムリスト３２に追加する。本実施例においては、対象プログラム複製部２８は、次式（２）を満たす場合に、当該対象プログラムを複製するものとする。なお、対象プログラム複製部２８により複製された対象プログラムは、後述する如く、元の対象プログラムと若干異なる可能性がある。
【００３９】
Σfitness ≧MAX_FITNESS …（２）
【００４０】
但し、複製が行なわれた際には、当該対象プログラムに係る評価値の履歴を全て消去すると共に、ΣfitnessからMAX_FITNESSを差し引いた値を当該対象プログラムに係る新たな評価値の履歴とする。これにより、目標値Targetを達成できなかった対象プログラムであっても、何回か実行を繰り返すうちに複製の機会が与えられることとなる。なお、新たな評価値の履歴を値ゼロから開始しても構わない。
【００４１】
これにより、後述する変異処理部３０による変異処理及び外部環境による突然変異によってプログラムが目標達成から外れた進化を遂げた場合であっても、更なる進化によって元の対象プログラムよりも優れたものとなる可能性を残すことができる。また、Σfitnessを判定要素とすることで、目標達成に近い対象プログラムに与えられる複製の機会を多く、目標達成に遠い対象プログラムに与えられる複製の機会を少なくするため、遺伝的アルゴリズムにおけるルーレット選択方式、トーナメント選択方式、エリート戦略等の如く、より好ましいものの生存（複製）機会を多くして、対象プログラムを効率的に進化させ、目標値Targetを達成できるものにすることができる。
【００４２】
また、複製のたびに初期化（評価値ゼロからスタートする）するのではなく、ΣfitnessからMAX_FITNESSを差し引いた値を当該対象プログラムに係る新たな評価値の履歴とするため、複製後もそれまでに得られた評価値fitnessを無駄なく使うことになり、評価値fitnessの値に応じて適切に複製を行なうことができる。例えば、最大値MAX_FITNESSが１００として、評価値fitnessが７０と評価される対象プログラムであれば、初めはΣfitnessが１４０となる２回目の実行で複製の条件を満たすことになるが、その次には、残りの４０が評価値の履歴となっているため、Σfitnessが１１０となる１回目の実行で複製の機会が得られることとなる。
【００４３】
更に、評価関数の最低値が値１（注；累計可能であれば他の値であってもよい）とされているため、目標値達成から遠く外れてしまった対象プログラムであっても、多くともMAX_FITNESS回実行を繰り返せば複製されるので、その後の進化により目標値Targetを達成できるものとなる可能性を残している。従って、何らかの外部要因や進化の過程により目標値Targetを達成できる対象プログラムが少数になり、ないし無くなってしまった場合でも、時間が経過すれば上記の対象プログラムが目標値Targetを達成できる対象プログラムに進化できる可能性を残している。従って、目標値Targetを達成できる対象プログラムの維持という観点から、最低限の保証を得ることができる。
【００４４】
なお、Σfitnessの比較対象値が必ずしも最大値MAX_FITNESSである必要はなく、最大値MAX_FITNESSと異なる値（例えば、最大値MAX_FITNESSに、値０．９〜１．１程度を乗じた値）であってよい。
【００４５】
変異処理部３０は、所定の確率で（下記の各手法によって確率が異なってよい）対象プログラムに変異を生じさせる。本実施例における変異処理は、例えば、遺伝的アルゴリズムの手法を適用し、突然変異、交叉等の形式で行なわれる。すなわち、（１）任意のタイミングで対象プログラムの一部にビット反転（値０と値１で規定されたプログラムの１箇所又は数箇所について値０と値１を入れ替える）を生じさせたり、（２）任意のタイミングで対象プログラムをランダムに変更したり、（３）対象プログラム複製部２８による複製の際に複製された対象プログラムについて同様にビット反転を生じさせたり、（４）対象プログラム複製部２８による複製の際に複製された対象プログラムの一部を他の対象プログラムの一部と置換したりする。なお、変異処理部３０の処理内容は、対象プログラムの一部を所定の確率で変更する性質のものであれば、上記のものに限定されない。
【００４６】
以下、こうした機能ブロックの協働により実行される具体的な処理の流れについて説明する。図５は、本実施例のシステム１が実行する特徴的な処理の流れを示すフローチャートの一例である。前述した如く、本フローは、ＲＯＭ１１に記憶されたシステム実行プログラに従ってＣＰＵが実行する。なお、以下の説明における各対象プログラムの評価値やプログラムカウンタ、全プログラム数等の値は、ＣＰＵ１０のレジスタ、或いはＲＡＭ１２等に適宜記憶されるものとする。
【００４７】
まず、ＣＰＵ１０は、最初の対象プログラム（対象プログラム１）となる初期プログラムをＲＡＭ１２に記憶させる（Ｓ１００）。初期プログラムは、ＲＯＭ１１に記憶されているものとしてもよいし、入力受付装置１４を介して入力されてもよい。
【００４８】
次に、ＣＰＵ１０は、評価関数をＲＡＭ１２に記憶させる（Ｓ１０２）。評価関数は、初期プログラムと同様に、ＲＯＭ１１に記憶されているものとしてもよいし、入力受付装置１４を介して入力されてもよい。
【００４９】
続いて、初期値を設定する（Ｓ１０４）。本ステップでは、全プログラム数を表すｎに値１を、実行プログラム番号を示すｉに値１を、対象プログラムｉの評価値を示すＦ［ｉ］に値ゼロを、対象プログラムｉのプログラムカウンタ（実行命令の行）を示すＰＣ［ｉ］に値１を、それぞれ設定する。
【００５０】
そして、ＰＣ［ｉ］を実行する（Ｓ１０６）。すなわち、対象プログラムｉのＰＣ［ｉ］行目の命令を実行する。
【００５１】
ＰＣ［ｉ］を実行すると、これにより対象プログラムｉの実行が完了したか否かを判定する（Ｓ１０８）。
【００５２】
Ｓ１０８において対象プログラムｉの実行が完了していないと判定された場合は、ＰＣ［ｉ］に値１を加える（Ｓ１１０）。これにより、次回に対象プログラムｉが実行される際には、今回実行された行の次の行が実行されることとなる。
【００５３】
ここで、ＣＰＵ１０は、確率Ｐ１で対象プログラムリスト３２に含まれる対象プログラムのいずれか（複数であってもよい）に対して変異を生じさせると共に、削除待ち行列３４に従って対象プログラムの削除処理を実行する（Ｓ１１２）。後者の処理の具体例は、例えば、削除待ち行列３４の先頭に位置する対象プログラムを、その時点における全プログラム数ｎに応じて増加する傾向の所定確率で削除する。こうすることにより、対象プログラムリスト３２に含まれる対象プログラムが多数である場合には高い確率で対象プログラムの削除が行なわれ、少数である場合には低い確率で対象プログラムの削除が行なわれるため、全プログラム数ｎを適切な数に制御することができる。対象プログラムの削除が行なわれた場合は、全プログラム数ｎを値１減少させる。
【００５４】
なお、これに限らず、所定時間毎や、本フローにおける他の実行タイミングで定期的に、削除処理を行なってもよい。また、確率Ｐ１についても全プログラム数ｎに応じて変化させてよい。また、変異処理と削除処理は同じタイミングで行なわれる必要はなく、本フローにおける他のタイミングで実行されてもよい。
【００５５】
対象プログラムの削除処理を実行すると、次式（３）の計算によりｉを再設定して、Ｓ１０６以下の処理を実行する（Ｓ１１４）。なお、式（３）は、対象プログラム１〜ｎまで順に実行し、対象プログラムｎに至ると再度プログラム１から順に実行する処理の流れを実現するためのものである。ここで、ｍｏｄ（ｉ，ｎ）は、値ｉを値ｎで除したときの余りを表す。
【００５６】
ｉ＝ｍｏｄ（ｉ，ｎ）＋１ …（３）
【００５７】
一方、Ｓ１０８において対象プログラムｉの実行が完了したと判定された場合は、評価関数に従ってＦ［ｉ］（対象プログラムｉの評価値fitnessを意味する）を計算する（Ｓ１１６）。
【００５８】
そして、Ｆ［ｉ］が最大値MAX_FITNESSに一致するか否かを判定する（Ｓ１１８）。Ｆ［ｉ］が最大値MAX_FITNESSに一致した場合は、対象プログラムｉの削除待ち行列における削除順位を一つ下げる（Ｓ１２０）。なお、図５においてはMAX_FITNESSを「MAX_F」と略記した。
【００５９】
続いて、ΣＦ［ｉ］（対象プログラムｉのΣfitnessを意味する）が最大値MAX_FITNESS以上であるか否かを判定する（Ｓ１２２）。前述の如く、比較対象値は必ずしも最大値MAX_FITNESSである必要はなく、最大値MAX_FITNESSと異なる値であってよい。
【００６０】
ΣＦ［ｉ］が最大値MAX_FITNESS以上であると判定された場合は、対象プログラムｉから対象プログラムｊを複製し、これに付随する諸処理を行なう（Ｓ１２４）。すなわち、対象プログラムの削除によって生じた空き番号のいずれかをプログラム番号ｊに設定し（空き番号が存在しない場合は、ｊ＝ｎ+1となる）、全プログラム数ｎを値１増加させ、Ｆ［ｊ］に値ゼロを設定し、ＰＣ［ｊ］に値１を設定する。この際に、複製された対象プログラムｊに確率Ｐ２で変異を生じさせる。ここで、確率Ｐ２は前述の確率Ｐ１と異なる値であってもよいし、同じ値であってもよい。また、複製された対象プログラムｊに生じさせる変異は、突然変異と交叉の組み合わせであってよい。
【００６１】
続いて、対象プログラムｊを削除待ち行列の最後尾にセットし（Ｓ１２６）、ΣＦ［ｉ］から最大値MAX_FITNESSを差し引く（Ｓ１２８）。
【００６２】
Ｓ１１６〜１２８を実行すると、ＰＣ［ｉ］に値１を設定して、Ｓ１１４に進む（Ｓ１３０）。従って、次回からは複製の元となった対象プログラムｉが１行目から実行されることとなる。
【００６３】
以上の説明から判るように、本実施例のシステム１では、スライス実行方式により対象プログラムの実行が行なわれ、対象プログラムの実行終了時点を基準として複製や削除順位の変更が行なわれるため、早く実行終了する対象プログラムほど、複製及び削除順位を下げられる機会が多く与えられることとなる。これにより、目標値Targetを達成でき（或いは目標値Targetに近い評価値fitnessを得られ）、且つ早く実行終了することができる優秀な対象プログラムをより高い確率で存続させることができる。
【００６４】
また、本実施例のシステム１は、対象プログラムの評価に際して他の対象プログラムの状態・出力を考慮していない。従って、対象プログラムのうちいずれかが正常に終了しない場合であっても、他の対象プログラムの評価が可能となり、システム全体の作動が停止する事態が生じるのを抑制することができる。
【００６５】
そして、対象プログラムの評価は、任意の目的に対する達成度を示す指標値である評価値fitnessを出力する評価関数を用いて適切に行なわれる。これにより、目的を達成することが可能な、或いは目的達成に近い対象プログラムが適切に判別され、その結果、優秀な対象プログラムを残すことができる。
【００６６】
従って、プログラムをより安定して維持・改良することができる。
【００６７】
＜適用例＞
上記の如く、本実施例のシステム１は、通常のコンピュータシステムとして使用されても十分な効果を奏するものであるが、宇宙空間で使用されることによって特に顕著な効果を奏するものである。以下、これについて述べる。
【００６８】
宇宙空間には、地上よりもはるかに多くの放射線が絶えず飛び交っている。メモリなどの半導体素子はそのような状況にさらされると、記憶されていた情報のビットが反転し、誤動作を起こす可能性がある。これは、ＳＥＵ(Single Event Upset)といい、入射するエネルギーが半導体素子の蓄えられるエネルギー量を超えたときに起こる現象である。
【００６９】
これに対してとられている対策は、シールドを張る方法や，論理回路の多重化といったハードウエアからのアプローチであり、シールドを張る方法によりコストが増大し、論理回路の多重化により必要なスペースが大きくなることが問題となっている。また、ビット反転の可能性を減らすために、ＣＰＵにはプロセスルールの太いものが採用されており、現在地上で用いられているコンピュータに比して計算能力の低いコンピュータが用いられているのが現状である。
【００７０】
そこで、本発明のプログラムの維持・改良システムを適用すると好適である。すなわち、ソフトウエアによる解決であるため、ハードウエアによる解決に比して、低コストで、大きなスペースを必要とせず、より高速で処理を行なうことができる。
【００７１】
そして、本システムを常時実行させることにより、正常なプログラムを維持することができるのみならず、環境の変化に適応したより優秀なプログラムを得ることができる可能性もある。
【００７２】
しかも、宇宙空間では、プログラムやシステムの正常性が継続的に維持されることが要求されるところ、本実施例のシステム１は、対象プログラムの評価に際して他の対象プログラムの状態・出力を考慮しておらず、システム全体の作動が停止する事態が生じるのを抑制することができる点で好適である。
【００７３】
なお、宇宙空間で使用される場合、評価関数は、無線通信によって地上から送信されるのが現実的である。また、対象プログラムは、ハングアップを回避するために、Tierra型のジャンプ構造を有することが好ましい。すなわち、ジャンプする際に，直接メモリのアドレスを指すのではなく、ジャンプ命令の後に表記された数字と相補的な関係にある数字の表記されたアドレスにジャンプする。この場合、相補的な関係にあるアドレスが見つからなければ，ジャンプしないことになるため、対象プログラムにおけるジャンプ命令の部分にビット反転による変化があったとしても、予期せぬアドレスにジャンプすることにより対象プログラムが回復不能な状態となる可能性が低減される。なお、Tierraとは、進化生物学者Thomas S.Ray博士が開発した仮想コンピュータシステムである。
【００７４】
また、ＳＥＵによるビット反転の発生頻度を計測し、これに応じて変異処理部３０による突然変異の発生確率Ｐ１等を調節してもよい。予め最適な発生確率が得られているような場合、ＳＥＵによるビット反転が発生する分、突然変異の発生確率Ｐ１等を減少させるのが適切だからである。
【００７５】
＜シミュレーション実験＞
本発明の発明者は、簡単な対象プログラムに対して本実施例のシステム１を適用し、シミュレーション実験を行なった。以下にその内容について述べる。
【００７６】
（設定）
本実験における対象プログラムに含まれる命令は、プログラムの開始テンプレートと終了テンプレートを表現するnop０及びnop１、incE（あるレジスタＥＸの値を１増加させる）、decE（レジスタＥＸの値を１減少させる）、shlE（レジスタＥＸの値を左シフトさせる＝２倍する）、shrE（レジスタＥＸの値を右シフトさせる＝２で除する）等であり（図６参照）、対象プログラムは、当初値ゼロに設定されているレジスタＥＸの値を、四則演算を繰り返して目標値Targetにすることを目的とする。
【００７７】
変異処理は、突然変異、及び交叉を含むものとした。交叉は後述する２種類の交叉を含むものとし、変異確率は、（Ａ）１ルーチン毎（１命令毎）に生じる突然変異、（Ｂ）複製時に生じる突然変異、複製時に生じる（Ｃ）上書き交叉、（Ｄ）置き換え交叉のそれぞれについて値１／３２であるものとした。
【００７８】
ここで、「上書き交叉」は、複製された対象プログラム（以下、娘プログラムと称する）のサイズから所定以内のサイズ差を有する対象プログラム（以下、相手プログラムと称する）を抽出し（相手プログラム候補が複数存在する場合は、プログラム番号順、ランダム、サイズ差が最も小さいもの等を基準に選択する）、1から娘プログラムのサイズｓ１と相手プログラムのサイズｓ２のうち小さい方の値未満の値をランダムに選択してこれをCrossPointと定め、CrossPointを交叉の位置とし、この位置を境に娘プログラムの後半に相手プログラムを上書き（或いは、その逆）を行なう（図７参照）。これによるサイズの変更は起こらない。
【００７９】
また、「置き換え交叉」は、ランダムに相手プログラムを選び、娘プログラム、相手プログラム別々に、1からｓ1までの値と、１からｓ２までの値をランダムに決定する。そして、娘プログラムと相手プログラムそれぞれのCrossPointを境に、前半、後半をあわせたものを新たな娘プログラムとする（同様に、図７参照）。この場合、サイズが異なる可能性がある。
【００８０】
上記の「上書き交叉」並びに「置き換え交叉」において、娘プログラムが前半になるか後半になるかは、例えば、娘プログラムのサイズｓ１がCrossPointの２倍よりも小さい場合には、CrossPoint以降の娘プログラムの中身が相手プログラムに置き換わる(前半が娘プログラム、後半が相手プログラムとなる)。一方、娘プログラムのサイズｓ１がCrossPointの２倍よりも大きい場合には、娘プログラムの開始位置からCrossPointまでが置き換わる(前半が相手プログラム、後半が娘プログラムとなる)。
【００８１】
なお、突然変異についても、ビット反転による突然変異と、ランダムな突然変異があってよい（図８参照）。すなわち、対象プログラムに含まれる命令には順番に0 〜 2n - 1（n：命令のビット数）までの整数の番号が割り当てられており、それをビットで表したものの１ヵ所がビット反転して別の命令になる場合や、ランダムに別の命令に置き換わる場合がある。以下の実験では、２０%の確率でビット反転が、８０%の確率でランダムな突然変異が、それぞれ生じるものとした。図８は5ビットの命令を表しており、上が元の命令のビット列、下が変化後のビット列であり、ビット反転は右から２番目が反転したものであり、ランダムは元の命令から全く別のものに変わったものである。
【００８２】
（実験）
まず、目標値Targetを固定し、初期プログラムを色々と変化させて実験を行なった。これは、対象プログラムがＳＥＵ等による変異から回復できるかどうかを検証するものである。具体的には、以下の３点のケースについて検証を行なった。[a] 正常なプログラムは正常な状態を維持できるか、[b] バグを含むプログラムは正常な状態に戻れるか、[c] ほとんど何もない状態でも正常な状態になれるか。
【００８３】
特に[a]については、ＳＥＵを考慮したものであり、ＳＥＵによって引き起こされる命令の変化に対しての耐性があるかどうかを調べた。[b]については、プログラムにつきもののバグが混入した場合を想定したものであり、人間によるものやプログラムの送信時のエラーに対して、正常な状態に戻れるかどうかを見たものである。最後に[c]については、目的のみを与えても正常に動作が可能であるかどうかを考慮したものであり、何らかのトラブルにより、プログラムのそのものを送信することが困難な状況に陥ったことを想定したものである。なお、目標値Targetは値１２６とした。
【００８４】
初期プログラムとしては、以下のものを用意した。
【００８５】
[a] 正常なもの（評価値fitness =１００を得るもの）として、＃０１３４、＃００２０、＃００１７を用意した（図９参照）。
【００８６】
＃０１３４は、全てがincEで構成されているため、進化の余地が十分に残されたものである（図９（Ａ）参照）。これは、incEを１２６回実行することにより、レジスタＥＸの値を目標値Targetにする。これを実行すると、EXレジスタの値は１、２、３、…、１２６と変化する。
【００８７】
＃００２０は、incEとshlEが交互に並んだ形になっている(図９（Ｂ）参照)。これを実行すると、EXレジスタの値は１、２、３、６、７、１４、１５、３０、３１、６２、６３、１２６と変化する。
【００８８】
＃００１７は、shlEを多用し、decEで微調整を加えたものである。(図９（Ｃ）参照) これを実行すると、EXレジスタの値は１、２、４、８、１６、３２、６４、６３、１２６と変化する。
【００８９】
[b] バグを含むもの（評価値fitness =９０〜１００未満を得るもの）として、＃０１３５、＃０１３３、＃００２１、＃００１９、＃００１８、＃００１７を用意した。
【００９０】
＃０１３５は、＃０１３４からincEを一つ追加したものである。また、＃０１３３は、＃０１３４からincEを一つ削除したものである。
【００９１】
＃００２１は、＃００２０の途中にincEを付け加えたものである。（図１０（Ａ）参照）。また、＃００１９は、＃００２０の最後のincEを取り除いたものである（図１０（Ｂ）参照）。
【００９２】
＃００１８は、＃００１７の途中にincEを追加したものである。（図１０（Ｃ）参照）。また、＃００１６は、＃００１７からdecEを削除したものである。(図１０（Ｄ）参照)。
【００９３】
[c] ほとんど何もない状態のものとして、＃０００９を用意した。これは、テンプレート以外には、incEが一つだけあるものである（図１１参照）。
【００９４】
以上についてシミュレーション実験を各１２回行なった。図１２は、その結果を示すものである。図中、「進化後」の部分が実験終了時に得られていた対象プログラムを示し、そのうち数字の左の部分がサイズを表し、「＊」を挟んで右側の最初の数字が１×１０８命令までのプログラム数、「：」を挟んで右側の数字がそれ以降のプログラム数を表す。「：」がない場合は１×１０８命令以降の変化が見られなかったものである。また、MAX_FITNESSにならなかったプログラムについては「etc」としている。
【００９５】
どの初期プログラムを与えた場合も、より優秀な対象プログラムである＃００１１、又は＃００１４（図１３参照）に収束する結果が存在した。但し、[c] の場合において収束しない結果が１２回中５回存在した。これについては、ループ回数（プログラムを実行する回数）や評価関数の特性形状、変異確率等の適合要素を最適化することにより結果を改善することができる可能性を残している。
【００９６】
この実験からは、[a] 正常なプログラムは正常な状態を維持できるか、及び[b] バグを含むプログラムは正常な状態に戻れるか、については十分に良好な結果が得られ、[c] ほとんど何もない状態でも正常な状態になれるか、についても上記適合要素の変更により改善可能と考えられる程度に良好な結果が得られている。従って、本実施例のシステム１は、対象プログラムを安定して維持・改良することができる点について、一定の検証を得たものと考えられる。
【００９７】
＜変形例＞
以上、本発明を実施するための最良の形態について実施例を用いて説明したが、本発明はこうした実施例に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変形及び置換を加えることができる。
【００９８】
例えば、削除順位の変更は、評価値fitnessが最大値MAX_FITNESSを達成した場合に削除順位を下げるのみのではなく、評価値fitnessが最大値MAX_FITNESSを達成しなかった場合に削除順位を上げるものとしてもよいし、達成できなかった程度に応じて削除順位を何段階か上げるものとしてもよい。
【産業上の利用可能性】
【００９９】
本発明は、コンピュータソフトウエア産業、宇宙開発産業等に利用可能である。
【図面の簡単な説明】
【０１００】
【図１】システム１を実現するためのハードウエア構成の一例を示す図である。
【図２】システム１において、ＣＰＵ１０がＲＯＭ１１に記憶されたシステム実行プログラムを実行することにより機能する機能ブロック、及びシステム１の作動に際してＲＡＭ１２等に記憶される情報を示す図である。
【図３】対象プログラム実行部２０がスライス実行方式により複数の対象プログラムを並行して実行する様子を概念的に示す図である。
【図４】本発明に係る評価関数の特性形状を例示する図である。
【図５】本実施例のシステム１が実行する特徴的な処理の流れを示すフローチャートの一例である。
【図６】本発明に係るシミュレーション実験における対象プログラムの構造を示す図である。
【図７】交叉が行なわれる様子を概念的に示す図である。
【図８】ビット反転による突然変異が行なわれる様子と、ランダムな突然変異が行なわれる様子を概念的に示す図である。
【図９】本発明に係るシミュレーション実験において用意された初期プログラムの一部を示す図である。
【図１０】本発明に係るシミュレーション実験において用意された初期プログラムの一部を示す図である。
【図１１】本発明に係るシミュレーション実験において用意された初期プログラムの一部を示す図である。
【図１２】本発明に係るシミュレーション実験の結果を示す図である。
【図１３】本発明に係るシミュレーション実験の結果として得られた、より優秀な対象プログラムを示す図である。
【図１４】本発明に係る評価関数の特性形状の他の例を示す図である。
【符号の説明】
【０１０１】
１ プログラムの維持・改良システム（システム）
１０ ＣＰＵ
１１ ＲＯＭ
１２ ＲＡＭ
１３ ＨＤＤ
１４ 入力受付装置
１５ バス
２０ 対象プログラム実行部
２２ 対象プログラム削除部
２４ 対象プログラム評価部
２６ 削除順位変更部
２８ 対象プログラム複製部
３０ 変異処理部
３２ 対象プログラムリスト
３４ 削除待ち行列
３６ 評価値履歴
【技術分野】
【０００１】
本発明は、プログラムを複製及び評価することによりプログラムの維持・改良を図るコンピュータシステム、及びコンピュータを当該システムとして機能させるためのコンピュータ読み取り可能なプログラムに関する。
【背景技術】
【０００２】
従来、コンピュータシステムにより最適解を求める方法として、遺伝的アルゴリズム（Genetic Algorithm；ＧＡ）が知られている。これは、遺伝子に見立てた複数のデータ（解の候補）に対して交叉・突然変異などの遺伝的操作を繰り返し、ルーレット選択方式、トーナメント選択方式、エリート戦略等の組み合わせにより、生成されたデータのうち適応度が相対的に高いものを生存させることによって最適解を求めるものである。
【０００３】
遺伝的アルゴリズムを応用した学習装置等についての発明が開示されている（例えば、特許文献１参照）。この装置では、初期設定として記憶された個体及びこれに遺伝的操作を行なって生成される個体等に対して、適応度に基づく選択と、適応度とは無関係な選択と、を組み合わせて生存選択を行なっており、局所最適解に陥りやすい等の遺伝的アルゴリズムの問題点を部分的に解消している。
【０００４】
また、遺伝的アルゴリズムを拡張したものとして、遺伝的プログラミング（Genetic Programming；ＧＰ）が知られている。これは、遺伝子型の表現に木構造を用いることにより、扱うデータをプログラムにまで拡張したものである。
【特許文献１】特開２００３−１６８１０１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、遺伝的プログラミングにおいては、例えば、複数のプログラムの実行が完了した時点で、外部から与えられた目的を相対的に高く達成したプログラムを優先的に生存させる処理が行なわれるため、プログラムの一部が正常に終了しなかった場合（例えばハングアップした場合等）に全体の処理が中断し、外部から与えられた目的を達成するのに適したプログラムを生成するに至らない場合が生じる。
【０００６】
本発明はこのような課題を解決するためのものであり、プログラムをより安定して維持・改良することが可能なプログラムの維持・改良システム、及びコンピュータを当該システムとして機能させるためのコンピュータ読み取り可能なプログラムを提供することを、主たる目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するための本発明の第１の態様は、
対象プログラムを実行する実行手段と、
所定の記憶手段に記憶された削除待ち行列に従って前記対象プログラムを削除する削除手段と、
実行終了した前記対象プログラムについて、数値化された実行結果が目標値と合致した場合に最大値を評価値として出力すると共に数値化された実行結果が目標値から離れるに従って小さくなる値を評価値として出力する傾向を有する評価関数によって、評価を行なう評価手段と、
前記評価手段による評価値に基づいて、前記対象プログラムの前記削除待ち行列における削除順位を変更する削除順位変更手段と、
前記評価手段による評価値に基づいて、前記対象プログラムを複製する複製手段と、
を備えるプログラムの維持・改良システムである。
【０００８】
ここで、「対象プログラム」とは、ＯＳを構成するモジュールやアプリケーションプログラム等、如何なるものであってもよい。
【０００９】
また、「評価関数に基づいて」とは、評価手段の直近の評価値に基づいて（例えば、閾値と比較する等して）対象プログラムを複製等すること、及び評価手段の評価値の履歴に基づいて（同上）対象プログラムを複製等することの双方を含む。
【００１０】
また、「目標値」を「目標領域」に置換してもよい。すなわち、目標値自体に一定の幅をもたせ、対象プログラムの実行結果が目標領域の範囲内であれば最大値を出力するものとしてもよい。
【００１１】
この本発明の第１の態様によれば、他の対象プログラムとの比較ではなく、当該対象プログラムの絶対評価を出力する評価関数を用いて対象プログラムの優劣が評価されるため、対象プログラムのうちいずれかが正常に終了しない場合であっても他の対象プログラムの評価が可能となり、システム全体の作動が停止する事態が生じるのを抑制することができる。従って、プログラムをより安定して維持・改良することが可能となる。
【００１２】
また、対象プログラムは上記任意の目的に対する達成度を適切に示す指標値である評価値に基づいて複製及び削除されるため、優秀なプログラムを適切に残存させることができ、プログラムを適切に進化させることができる。
【００１３】
本発明の第１の態様において、前記削除順位変更手段は、前記評価手段による評価値が前記最大値である場合に、該評価された対象プログラムの前記削除待ち行列における削除順位が下がるように、前記対象プログラムの前記削除待ち行列における削除順位を変更する手段であるものとしてもよい。こうすれば、正常に終了しない対象プログラムは、削除順位変更手段により削除順位が下げられないため、いずれ削除手段により削除されることとなる。従って、プログラムを適切に進化させることができる。
【００１４】
また、本発明の第１の態様において、対象プログラムに変異を生じさせる変異処理手段を備えることが望ましい。
【００１５】
また、本発明の第１の態様において、前記評価関数の設定又は変更に関する外部からの入力を受け付ける評価関数入力受付手段を備えるものとしてもよい。
【００１６】
また、本発明の第１の態様において、前記評価手段の評価値を記憶する評価値記憶手段を備え、前記複製手段は、前記評価値記憶手段に記憶された評価値の履歴に基づいて、前記対象プログラムを複製する手段であるものとしてもよい。こうすれば、対象プログラムを複製する具体的手法の幅を広げることができる。
【００１７】
この場合、前記複製手段は、前記評価値記憶手段に記憶された評価値の累計値に基づく値が所定の複製基準値を超えた場合に対象プログラムを複製する手段であるとすることが考えられる。これにより、目標を達成できなかった対象プログラムであっても、何回か実行を繰り返すうちに複製の機会が与えられることとなる。従って、対象プログラムが目標達成から外れた進化を遂げた場合であっても、更なる進化によって元の対象プログラムよりも優れたものとなる可能性を残すことができる。
【００１８】
更にこの場合、前記評価関数は、最低値として累計可能な値を出力する関数であるものとすると、好適である。こうすれば、何らかの外部要因や進化の過程により目標を達成できる対象プログラムが少数になり、ないし無くなってしまった場合でも、時間が経過すれば対象プログラムが目標を達成できる対象プログラムに進化できる可能性を残している。従って、目標を達成できる対象プログラムの維持という観点から、最低限の保証を得ることができる。
【００１９】
また、本発明の第１の態様は、宇宙空間で使用されることを特徴とするものとすると、特に好適である。
【００２０】
また、変異処理手段を有する本発明の第１の態様において、前記変異処理手段は、自己の作動に依らない対象プログラムの変異発生率に応じて前記対象プログラムに変異を生じさせる確率を変更する手段であるものとしてもよい。
【００２１】
本発明の第２の態様は、コンピュータを、本発明の第１の態様のプログラムの維持・改良システムとして機能させるための、コンピュータ読み取り可能なプログラムである。
【発明の効果】
【００２２】
本発明によれば、プログラムをより安定して維持・改良することが可能なプログラムの維持・改良システム、及びコンピュータを当該システムとして機能させるためのコンピュータ読み取り可能なプログラムを提供することができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を実施するための最良の形態について、添付図面を参照しながら実施例を挙げて説明する。
【実施例】
【００２４】
以下、本発明の一実施例に係るプログラムの維持・改良システム１（以下、単に「システム１」と称する）について説明する。本実施例のシステム１は、対象プログラムを変異させながら複製・削除する処理を繰り返し、変異した対象プログラムを目標達成により適したものとすること、及び目標を達成できる対象プログラムが継続して存在するように維持することを目的とする。以下、対象プログラムが変異によって元の対象プログラムと異なるものとなることを、「進化」と称する。
【００２５】
図１は、システム１を実現するためのハードウエア構成の一例を示す図である。システム１は、例えば、ＣＰＵ（Central Processing Unit）１０、ＲＯＭ（Read Only Memory）１１、ＲＡＭ（Random Access Memory）１２、ＨＤＤ（Hard Disk Drive）１３、入力受付装置１４、バス１５、その他タイマー、カウンター、マウス、キーボード等によって実現される。入力受付装置１４は、例えば、キーボードやＣＤ−ＲＯＭドライブ、ＤＶＤ装置、ＵＳＢ（Universal Serial Bus）等の汎用インターフェイス、有線又は無線による通信装置等が用いられる。なお、本構成はあくまで一例であり、本発明の適用上、ハードウエア構成に関する制限は何ら存在しない。例えば、後述する複数の対象プログラム毎に担当ＣＰＵを備える構成であってもよい。
【００２６】
図２は、システム１において、ＣＰＵ１０がＲＯＭ１１に記憶されたシステム実行プログラム（請求項１０における「コンピュータ読み取り可能なプログラム」に相当する）を実行することにより機能する機能ブロック、及びシステム１の作動に際してＲＡＭ１２等に記憶される情報を示す図である。システム１は、機能ブロックとして、対象プログラム実行部２０と、対象プログラム削除部２２と、対象プログラム評価部２４と、削除順位変更部２６と、対象プログラム複製部２８と、変異処理部３０と、を備える。また、ＲＡＭ１２等の所定領域には、対象プログラムリスト３２、削除待ち行列３４、及び評価値履歴３６が記憶される。
【００２７】
対象プログラム実行部２０は、対象プログラムリスト３２に記憶された複数の（システムの始動当初は単独である）対象プログラムを、例えばスライス実行方式によって並行して実行する。すなわち、対象プログラムリスト３２に含まれる対象プログラムがｎ個存在するとして、対象プログラムｋ（１≦ｋ≦ｎ）の１単位の命令を実行すると、次に対象プログラムｋ+１の１単位の命令を実行する。これをｋ＝1から順に実行し、対象プログラムｎまで実行し終えると、対象プログラム１に戻り、次の１単位の命令を実行する。図３は、対象プログラム実行部２０がスライス実行方式により複数の対象プログラムを並行して実行する様子を概念的に示す図である。なお、対象プログラム毎にＣＰＵを備える構成の場合、必ずしもスライス実行方式を採用する必要はなく、各対象プログラムが並行して同時に実行されてよい。
【００２８】
なお、対象プログラムの性質、属性等に特段の制限は存在せず、いわゆるアプリケーションプログラムやＯＳ（Operating System）、ミドルウエア等、如何なるソフトウエアを対象プログラムとしてもよい。
【００２９】
対象プログラム削除部２２は、所定のタイミングで、削除待ち行列３４に記憶された削除待ち行列に従って、対象プログラムリスト３２に含まれる対象プログラムのうち、削除順位の最も高いものを削除する。削除待ち行列は、その時点で対象プログラムリスト３２に記憶され、対象プログラム実行部２０により実行されている全ての対象プログラムを一次元に並べたものである。なお、「所定のタイミング」とは、後述する処理フローの１ルーチン毎、或いは所定時間毎等、定期的ないし周期的なものであればよい。
【００３０】
対象プログラム評価部２４は、対象プログラム実行部２０による実行が終了した対象プログラムについて、評価を行なって評価値を出力する。対象プログラムの評価は、所定の評価関数を用いて行なわれる。この評価関数は、数値化された実行結果ＥＸが目標値（以下、目標値Targetと称する）と合致した場合に最大値（以下、MAX_FITNESSと称する）を評価値（以下、評価値fitnessと称する）として出力すると共に、数値化された実行結果ＥＸが目標値Targetから離れるに従って小さくなる値を評価値fitnessとして出力する特性形状を有する関数である。図４に、本発明に係る評価関数の特性形状として考え得るものを列挙した。なお、本図はあくまで例示であり、上記の特性を満たす限りにおいて、いかなる変形・置換も許容される。これらから明らかなように、評価値fitnessは、任意の目的に対する達成度を示す指標値である。対象プログラム評価部２４の出力する評価値は、出力された順に評価値履歴３６に記憶される。なお、目標値Targetは、１点である必要はなく、所定の幅をもった目標領域であっても構わない。図４（Ｆ）〜（Ｈ）は、目標領域（Target領域）を定める場合の評価関数特性を例示したものである。数値化された実行結果ＥＸは、例えばレジスタやＲＡＭ、フラッシュメモリ等に、随時記憶される。
【００３１】
また、「数値化された実行結果ＥＸが目標値Targetから離れるに従って小さくなる」とは、厳密に単調減少傾向を有する必要まではなく、図１４（Ａ）〜（Ｅ）に示す如く、第２、第３…の峰部を有しても構わない。
【００３２】
更に、目標値Targetが必ずしも単独である必要はなく、目標値Targetが複数存在しても構わない。例えば、実行結果ＥＸが所定周期を経て同一結果とみなされるような場合や、符号を反転させると同一結果とみなされるような場合に、目標値Targetが複数存在しうる（注；例示であり、目標値Targetが複数存在する場合は、これらに限られない）。この場合、評価関数の特性形状は、図１４（Ｆ）〜（Ｈ）に示す如く、複数のピーク値を有する形状となる。
【００３３】
図４（Ａ）に示す評価関数の一般式は、次式（１）の如くである。評価値の最小値を値１に設定する理由については後述する。
【００３４】
fitness ＝（MAX_FITNESS／Target）×EX （EX≦Target）
or MAX_FITNESS×２−（MAX_FITNESS／Target）×EX （EX＞Target）
但し、min(fitness)＝１ …（１）
【００３５】
評価関数は、予めＲＯＭ１１等に記憶されているものとする。なお、複数の評価関数が予め記憶され、対象プログラムが実行する処理内容（タスク）に応じて適宜選択されてもよいし、後述する第２実施例の如く、外部から評価関数が入力又は選択されてもよい。
【００３６】
本実施例のシステム１は、対象プログラムの評価に際して他の対象プログラムの状態・出力を考慮していない。従って、対象プログラムのうちいずれかが正常に終了しない場合であっても、他の対象プログラムの評価が可能となり、システム全体の作動が停止する事態が生じるのを抑制することができる。
【００３７】
削除順位変更部２６は、対象プログラム評価部２４が出力する評価値fitnessが最大値MAX FITNESSである場合に、当該対象プログラムの削除待ち行列における削除順位が下がる（後回しにされる）ように、削除待ち行列における削除順位を変更する。すなわち、目標を達成した対象プログラムが削除されるのを先延ばしにする（寿命を延ばす）処理を行なう。これにより、目標値Targetを達成することができる対象プログラムを優先的に存続させることとなるため、与えられた目標を達成することが可能なプログラムを安定的に維持することができる。
【００３８】
対象プログラム複製部２８は、直近に評価がなされた対象プログラムについて、評価値履歴３６に記憶された評価値の履歴に基づく判定を行なって、判定結果に基づき当該対象プログラムを複製し、対象プログラムリスト３２に追加する。本実施例においては、対象プログラム複製部２８は、次式（２）を満たす場合に、当該対象プログラムを複製するものとする。なお、対象プログラム複製部２８により複製された対象プログラムは、後述する如く、元の対象プログラムと若干異なる可能性がある。
【００３９】
Σfitness ≧MAX_FITNESS …（２）
【００４０】
但し、複製が行なわれた際には、当該対象プログラムに係る評価値の履歴を全て消去すると共に、ΣfitnessからMAX_FITNESSを差し引いた値を当該対象プログラムに係る新たな評価値の履歴とする。これにより、目標値Targetを達成できなかった対象プログラムであっても、何回か実行を繰り返すうちに複製の機会が与えられることとなる。なお、新たな評価値の履歴を値ゼロから開始しても構わない。
【００４１】
これにより、後述する変異処理部３０による変異処理及び外部環境による突然変異によってプログラムが目標達成から外れた進化を遂げた場合であっても、更なる進化によって元の対象プログラムよりも優れたものとなる可能性を残すことができる。また、Σfitnessを判定要素とすることで、目標達成に近い対象プログラムに与えられる複製の機会を多く、目標達成に遠い対象プログラムに与えられる複製の機会を少なくするため、遺伝的アルゴリズムにおけるルーレット選択方式、トーナメント選択方式、エリート戦略等の如く、より好ましいものの生存（複製）機会を多くして、対象プログラムを効率的に進化させ、目標値Targetを達成できるものにすることができる。
【００４２】
また、複製のたびに初期化（評価値ゼロからスタートする）するのではなく、ΣfitnessからMAX_FITNESSを差し引いた値を当該対象プログラムに係る新たな評価値の履歴とするため、複製後もそれまでに得られた評価値fitnessを無駄なく使うことになり、評価値fitnessの値に応じて適切に複製を行なうことができる。例えば、最大値MAX_FITNESSが１００として、評価値fitnessが７０と評価される対象プログラムであれば、初めはΣfitnessが１４０となる２回目の実行で複製の条件を満たすことになるが、その次には、残りの４０が評価値の履歴となっているため、Σfitnessが１１０となる１回目の実行で複製の機会が得られることとなる。
【００４３】
更に、評価関数の最低値が値１（注；累計可能であれば他の値であってもよい）とされているため、目標値達成から遠く外れてしまった対象プログラムであっても、多くともMAX_FITNESS回実行を繰り返せば複製されるので、その後の進化により目標値Targetを達成できるものとなる可能性を残している。従って、何らかの外部要因や進化の過程により目標値Targetを達成できる対象プログラムが少数になり、ないし無くなってしまった場合でも、時間が経過すれば上記の対象プログラムが目標値Targetを達成できる対象プログラムに進化できる可能性を残している。従って、目標値Targetを達成できる対象プログラムの維持という観点から、最低限の保証を得ることができる。
【００４４】
なお、Σfitnessの比較対象値が必ずしも最大値MAX_FITNESSである必要はなく、最大値MAX_FITNESSと異なる値（例えば、最大値MAX_FITNESSに、値０．９〜１．１程度を乗じた値）であってよい。
【００４５】
変異処理部３０は、所定の確率で（下記の各手法によって確率が異なってよい）対象プログラムに変異を生じさせる。本実施例における変異処理は、例えば、遺伝的アルゴリズムの手法を適用し、突然変異、交叉等の形式で行なわれる。すなわち、（１）任意のタイミングで対象プログラムの一部にビット反転（値０と値１で規定されたプログラムの１箇所又は数箇所について値０と値１を入れ替える）を生じさせたり、（２）任意のタイミングで対象プログラムをランダムに変更したり、（３）対象プログラム複製部２８による複製の際に複製された対象プログラムについて同様にビット反転を生じさせたり、（４）対象プログラム複製部２８による複製の際に複製された対象プログラムの一部を他の対象プログラムの一部と置換したりする。なお、変異処理部３０の処理内容は、対象プログラムの一部を所定の確率で変更する性質のものであれば、上記のものに限定されない。
【００４６】
以下、こうした機能ブロックの協働により実行される具体的な処理の流れについて説明する。図５は、本実施例のシステム１が実行する特徴的な処理の流れを示すフローチャートの一例である。前述した如く、本フローは、ＲＯＭ１１に記憶されたシステム実行プログラに従ってＣＰＵが実行する。なお、以下の説明における各対象プログラムの評価値やプログラムカウンタ、全プログラム数等の値は、ＣＰＵ１０のレジスタ、或いはＲＡＭ１２等に適宜記憶されるものとする。
【００４７】
まず、ＣＰＵ１０は、最初の対象プログラム（対象プログラム１）となる初期プログラムをＲＡＭ１２に記憶させる（Ｓ１００）。初期プログラムは、ＲＯＭ１１に記憶されているものとしてもよいし、入力受付装置１４を介して入力されてもよい。
【００４８】
次に、ＣＰＵ１０は、評価関数をＲＡＭ１２に記憶させる（Ｓ１０２）。評価関数は、初期プログラムと同様に、ＲＯＭ１１に記憶されているものとしてもよいし、入力受付装置１４を介して入力されてもよい。
【００４９】
続いて、初期値を設定する（Ｓ１０４）。本ステップでは、全プログラム数を表すｎに値１を、実行プログラム番号を示すｉに値１を、対象プログラムｉの評価値を示すＦ［ｉ］に値ゼロを、対象プログラムｉのプログラムカウンタ（実行命令の行）を示すＰＣ［ｉ］に値１を、それぞれ設定する。
【００５０】
そして、ＰＣ［ｉ］を実行する（Ｓ１０６）。すなわち、対象プログラムｉのＰＣ［ｉ］行目の命令を実行する。
【００５１】
ＰＣ［ｉ］を実行すると、これにより対象プログラムｉの実行が完了したか否かを判定する（Ｓ１０８）。
【００５２】
Ｓ１０８において対象プログラムｉの実行が完了していないと判定された場合は、ＰＣ［ｉ］に値１を加える（Ｓ１１０）。これにより、次回に対象プログラムｉが実行される際には、今回実行された行の次の行が実行されることとなる。
【００５３】
ここで、ＣＰＵ１０は、確率Ｐ１で対象プログラムリスト３２に含まれる対象プログラムのいずれか（複数であってもよい）に対して変異を生じさせると共に、削除待ち行列３４に従って対象プログラムの削除処理を実行する（Ｓ１１２）。後者の処理の具体例は、例えば、削除待ち行列３４の先頭に位置する対象プログラムを、その時点における全プログラム数ｎに応じて増加する傾向の所定確率で削除する。こうすることにより、対象プログラムリスト３２に含まれる対象プログラムが多数である場合には高い確率で対象プログラムの削除が行なわれ、少数である場合には低い確率で対象プログラムの削除が行なわれるため、全プログラム数ｎを適切な数に制御することができる。対象プログラムの削除が行なわれた場合は、全プログラム数ｎを値１減少させる。
【００５４】
なお、これに限らず、所定時間毎や、本フローにおける他の実行タイミングで定期的に、削除処理を行なってもよい。また、確率Ｐ１についても全プログラム数ｎに応じて変化させてよい。また、変異処理と削除処理は同じタイミングで行なわれる必要はなく、本フローにおける他のタイミングで実行されてもよい。
【００５５】
対象プログラムの削除処理を実行すると、次式（３）の計算によりｉを再設定して、Ｓ１０６以下の処理を実行する（Ｓ１１４）。なお、式（３）は、対象プログラム１〜ｎまで順に実行し、対象プログラムｎに至ると再度プログラム１から順に実行する処理の流れを実現するためのものである。ここで、ｍｏｄ（ｉ，ｎ）は、値ｉを値ｎで除したときの余りを表す。
【００５６】
ｉ＝ｍｏｄ（ｉ，ｎ）＋１ …（３）
【００５７】
一方、Ｓ１０８において対象プログラムｉの実行が完了したと判定された場合は、評価関数に従ってＦ［ｉ］（対象プログラムｉの評価値fitnessを意味する）を計算する（Ｓ１１６）。
【００５８】
そして、Ｆ［ｉ］が最大値MAX_FITNESSに一致するか否かを判定する（Ｓ１１８）。Ｆ［ｉ］が最大値MAX_FITNESSに一致した場合は、対象プログラムｉの削除待ち行列における削除順位を一つ下げる（Ｓ１２０）。なお、図５においてはMAX_FITNESSを「MAX_F」と略記した。
【００５９】
続いて、ΣＦ［ｉ］（対象プログラムｉのΣfitnessを意味する）が最大値MAX_FITNESS以上であるか否かを判定する（Ｓ１２２）。前述の如く、比較対象値は必ずしも最大値MAX_FITNESSである必要はなく、最大値MAX_FITNESSと異なる値であってよい。
【００６０】
ΣＦ［ｉ］が最大値MAX_FITNESS以上であると判定された場合は、対象プログラムｉから対象プログラムｊを複製し、これに付随する諸処理を行なう（Ｓ１２４）。すなわち、対象プログラムの削除によって生じた空き番号のいずれかをプログラム番号ｊに設定し（空き番号が存在しない場合は、ｊ＝ｎ+1となる）、全プログラム数ｎを値１増加させ、Ｆ［ｊ］に値ゼロを設定し、ＰＣ［ｊ］に値１を設定する。この際に、複製された対象プログラムｊに確率Ｐ２で変異を生じさせる。ここで、確率Ｐ２は前述の確率Ｐ１と異なる値であってもよいし、同じ値であってもよい。また、複製された対象プログラムｊに生じさせる変異は、突然変異と交叉の組み合わせであってよい。
【００６１】
続いて、対象プログラムｊを削除待ち行列の最後尾にセットし（Ｓ１２６）、ΣＦ［ｉ］から最大値MAX_FITNESSを差し引く（Ｓ１２８）。
【００６２】
Ｓ１１６〜１２８を実行すると、ＰＣ［ｉ］に値１を設定して、Ｓ１１４に進む（Ｓ１３０）。従って、次回からは複製の元となった対象プログラムｉが１行目から実行されることとなる。
【００６３】
以上の説明から判るように、本実施例のシステム１では、スライス実行方式により対象プログラムの実行が行なわれ、対象プログラムの実行終了時点を基準として複製や削除順位の変更が行なわれるため、早く実行終了する対象プログラムほど、複製及び削除順位を下げられる機会が多く与えられることとなる。これにより、目標値Targetを達成でき（或いは目標値Targetに近い評価値fitnessを得られ）、且つ早く実行終了することができる優秀な対象プログラムをより高い確率で存続させることができる。
【００６４】
また、本実施例のシステム１は、対象プログラムの評価に際して他の対象プログラムの状態・出力を考慮していない。従って、対象プログラムのうちいずれかが正常に終了しない場合であっても、他の対象プログラムの評価が可能となり、システム全体の作動が停止する事態が生じるのを抑制することができる。
【００６５】
そして、対象プログラムの評価は、任意の目的に対する達成度を示す指標値である評価値fitnessを出力する評価関数を用いて適切に行なわれる。これにより、目的を達成することが可能な、或いは目的達成に近い対象プログラムが適切に判別され、その結果、優秀な対象プログラムを残すことができる。
【００６６】
従って、プログラムをより安定して維持・改良することができる。
【００６７】
＜適用例＞
上記の如く、本実施例のシステム１は、通常のコンピュータシステムとして使用されても十分な効果を奏するものであるが、宇宙空間で使用されることによって特に顕著な効果を奏するものである。以下、これについて述べる。
【００６８】
宇宙空間には、地上よりもはるかに多くの放射線が絶えず飛び交っている。メモリなどの半導体素子はそのような状況にさらされると、記憶されていた情報のビットが反転し、誤動作を起こす可能性がある。これは、ＳＥＵ(Single Event Upset)といい、入射するエネルギーが半導体素子の蓄えられるエネルギー量を超えたときに起こる現象である。
【００６９】
これに対してとられている対策は、シールドを張る方法や，論理回路の多重化といったハードウエアからのアプローチであり、シールドを張る方法によりコストが増大し、論理回路の多重化により必要なスペースが大きくなることが問題となっている。また、ビット反転の可能性を減らすために、ＣＰＵにはプロセスルールの太いものが採用されており、現在地上で用いられているコンピュータに比して計算能力の低いコンピュータが用いられているのが現状である。
【００７０】
そこで、本発明のプログラムの維持・改良システムを適用すると好適である。すなわち、ソフトウエアによる解決であるため、ハードウエアによる解決に比して、低コストで、大きなスペースを必要とせず、より高速で処理を行なうことができる。
【００７１】
そして、本システムを常時実行させることにより、正常なプログラムを維持することができるのみならず、環境の変化に適応したより優秀なプログラムを得ることができる可能性もある。
【００７２】
しかも、宇宙空間では、プログラムやシステムの正常性が継続的に維持されることが要求されるところ、本実施例のシステム１は、対象プログラムの評価に際して他の対象プログラムの状態・出力を考慮しておらず、システム全体の作動が停止する事態が生じるのを抑制することができる点で好適である。
【００７３】
なお、宇宙空間で使用される場合、評価関数は、無線通信によって地上から送信されるのが現実的である。また、対象プログラムは、ハングアップを回避するために、Tierra型のジャンプ構造を有することが好ましい。すなわち、ジャンプする際に，直接メモリのアドレスを指すのではなく、ジャンプ命令の後に表記された数字と相補的な関係にある数字の表記されたアドレスにジャンプする。この場合、相補的な関係にあるアドレスが見つからなければ，ジャンプしないことになるため、対象プログラムにおけるジャンプ命令の部分にビット反転による変化があったとしても、予期せぬアドレスにジャンプすることにより対象プログラムが回復不能な状態となる可能性が低減される。なお、Tierraとは、進化生物学者Thomas S.Ray博士が開発した仮想コンピュータシステムである。
【００７４】
また、ＳＥＵによるビット反転の発生頻度を計測し、これに応じて変異処理部３０による突然変異の発生確率Ｐ１等を調節してもよい。予め最適な発生確率が得られているような場合、ＳＥＵによるビット反転が発生する分、突然変異の発生確率Ｐ１等を減少させるのが適切だからである。
【００７５】
＜シミュレーション実験＞
本発明の発明者は、簡単な対象プログラムに対して本実施例のシステム１を適用し、シミュレーション実験を行なった。以下にその内容について述べる。
【００７６】
（設定）
本実験における対象プログラムに含まれる命令は、プログラムの開始テンプレートと終了テンプレートを表現するnop０及びnop１、incE（あるレジスタＥＸの値を１増加させる）、decE（レジスタＥＸの値を１減少させる）、shlE（レジスタＥＸの値を左シフトさせる＝２倍する）、shrE（レジスタＥＸの値を右シフトさせる＝２で除する）等であり（図６参照）、対象プログラムは、当初値ゼロに設定されているレジスタＥＸの値を、四則演算を繰り返して目標値Targetにすることを目的とする。
【００７７】
変異処理は、突然変異、及び交叉を含むものとした。交叉は後述する２種類の交叉を含むものとし、変異確率は、（Ａ）１ルーチン毎（１命令毎）に生じる突然変異、（Ｂ）複製時に生じる突然変異、複製時に生じる（Ｃ）上書き交叉、（Ｄ）置き換え交叉のそれぞれについて値１／３２であるものとした。
【００７８】
ここで、「上書き交叉」は、複製された対象プログラム（以下、娘プログラムと称する）のサイズから所定以内のサイズ差を有する対象プログラム（以下、相手プログラムと称する）を抽出し（相手プログラム候補が複数存在する場合は、プログラム番号順、ランダム、サイズ差が最も小さいもの等を基準に選択する）、1から娘プログラムのサイズｓ１と相手プログラムのサイズｓ２のうち小さい方の値未満の値をランダムに選択してこれをCrossPointと定め、CrossPointを交叉の位置とし、この位置を境に娘プログラムの後半に相手プログラムを上書き（或いは、その逆）を行なう（図７参照）。これによるサイズの変更は起こらない。
【００７９】
また、「置き換え交叉」は、ランダムに相手プログラムを選び、娘プログラム、相手プログラム別々に、1からｓ1までの値と、１からｓ２までの値をランダムに決定する。そして、娘プログラムと相手プログラムそれぞれのCrossPointを境に、前半、後半をあわせたものを新たな娘プログラムとする（同様に、図７参照）。この場合、サイズが異なる可能性がある。
【００８０】
上記の「上書き交叉」並びに「置き換え交叉」において、娘プログラムが前半になるか後半になるかは、例えば、娘プログラムのサイズｓ１がCrossPointの２倍よりも小さい場合には、CrossPoint以降の娘プログラムの中身が相手プログラムに置き換わる(前半が娘プログラム、後半が相手プログラムとなる)。一方、娘プログラムのサイズｓ１がCrossPointの２倍よりも大きい場合には、娘プログラムの開始位置からCrossPointまでが置き換わる(前半が相手プログラム、後半が娘プログラムとなる)。
【００８１】
なお、突然変異についても、ビット反転による突然変異と、ランダムな突然変異があってよい（図８参照）。すなわち、対象プログラムに含まれる命令には順番に0 〜 2n - 1（n：命令のビット数）までの整数の番号が割り当てられており、それをビットで表したものの１ヵ所がビット反転して別の命令になる場合や、ランダムに別の命令に置き換わる場合がある。以下の実験では、２０%の確率でビット反転が、８０%の確率でランダムな突然変異が、それぞれ生じるものとした。図８は5ビットの命令を表しており、上が元の命令のビット列、下が変化後のビット列であり、ビット反転は右から２番目が反転したものであり、ランダムは元の命令から全く別のものに変わったものである。
【００８２】
（実験）
まず、目標値Targetを固定し、初期プログラムを色々と変化させて実験を行なった。これは、対象プログラムがＳＥＵ等による変異から回復できるかどうかを検証するものである。具体的には、以下の３点のケースについて検証を行なった。[a] 正常なプログラムは正常な状態を維持できるか、[b] バグを含むプログラムは正常な状態に戻れるか、[c] ほとんど何もない状態でも正常な状態になれるか。
【００８３】
特に[a]については、ＳＥＵを考慮したものであり、ＳＥＵによって引き起こされる命令の変化に対しての耐性があるかどうかを調べた。[b]については、プログラムにつきもののバグが混入した場合を想定したものであり、人間によるものやプログラムの送信時のエラーに対して、正常な状態に戻れるかどうかを見たものである。最後に[c]については、目的のみを与えても正常に動作が可能であるかどうかを考慮したものであり、何らかのトラブルにより、プログラムのそのものを送信することが困難な状況に陥ったことを想定したものである。なお、目標値Targetは値１２６とした。
【００８４】
初期プログラムとしては、以下のものを用意した。
【００８５】
[a] 正常なもの（評価値fitness =１００を得るもの）として、＃０１３４、＃００２０、＃００１７を用意した（図９参照）。
【００８６】
＃０１３４は、全てがincEで構成されているため、進化の余地が十分に残されたものである（図９（Ａ）参照）。これは、incEを１２６回実行することにより、レジスタＥＸの値を目標値Targetにする。これを実行すると、EXレジスタの値は１、２、３、…、１２６と変化する。
【００８７】
＃００２０は、incEとshlEが交互に並んだ形になっている(図９（Ｂ）参照)。これを実行すると、EXレジスタの値は１、２、３、６、７、１４、１５、３０、３１、６２、６３、１２６と変化する。
【００８８】
＃００１７は、shlEを多用し、decEで微調整を加えたものである。(図９（Ｃ）参照) これを実行すると、EXレジスタの値は１、２、４、８、１６、３２、６４、６３、１２６と変化する。
【００８９】
[b] バグを含むもの（評価値fitness =９０〜１００未満を得るもの）として、＃０１３５、＃０１３３、＃００２１、＃００１９、＃００１８、＃００１７を用意した。
【００９０】
＃０１３５は、＃０１３４からincEを一つ追加したものである。また、＃０１３３は、＃０１３４からincEを一つ削除したものである。
【００９１】
＃００２１は、＃００２０の途中にincEを付け加えたものである。（図１０（Ａ）参照）。また、＃００１９は、＃００２０の最後のincEを取り除いたものである（図１０（Ｂ）参照）。
【００９２】
＃００１８は、＃００１７の途中にincEを追加したものである。（図１０（Ｃ）参照）。また、＃００１６は、＃００１７からdecEを削除したものである。(図１０（Ｄ）参照)。
【００９３】
[c] ほとんど何もない状態のものとして、＃０００９を用意した。これは、テンプレート以外には、incEが一つだけあるものである（図１１参照）。
【００９４】
以上についてシミュレーション実験を各１２回行なった。図１２は、その結果を示すものである。図中、「進化後」の部分が実験終了時に得られていた対象プログラムを示し、そのうち数字の左の部分がサイズを表し、「＊」を挟んで右側の最初の数字が１×１０８命令までのプログラム数、「：」を挟んで右側の数字がそれ以降のプログラム数を表す。「：」がない場合は１×１０８命令以降の変化が見られなかったものである。また、MAX_FITNESSにならなかったプログラムについては「etc」としている。
【００９５】
どの初期プログラムを与えた場合も、より優秀な対象プログラムである＃００１１、又は＃００１４（図１３参照）に収束する結果が存在した。但し、[c] の場合において収束しない結果が１２回中５回存在した。これについては、ループ回数（プログラムを実行する回数）や評価関数の特性形状、変異確率等の適合要素を最適化することにより結果を改善することができる可能性を残している。
【００９６】
この実験からは、[a] 正常なプログラムは正常な状態を維持できるか、及び[b] バグを含むプログラムは正常な状態に戻れるか、については十分に良好な結果が得られ、[c] ほとんど何もない状態でも正常な状態になれるか、についても上記適合要素の変更により改善可能と考えられる程度に良好な結果が得られている。従って、本実施例のシステム１は、対象プログラムを安定して維持・改良することができる点について、一定の検証を得たものと考えられる。
【００９７】
＜変形例＞
以上、本発明を実施するための最良の形態について実施例を用いて説明したが、本発明はこうした実施例に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変形及び置換を加えることができる。
【００９８】
例えば、削除順位の変更は、評価値fitnessが最大値MAX_FITNESSを達成した場合に削除順位を下げるのみのではなく、評価値fitnessが最大値MAX_FITNESSを達成しなかった場合に削除順位を上げるものとしてもよいし、達成できなかった程度に応じて削除順位を何段階か上げるものとしてもよい。
【産業上の利用可能性】
【００９９】
本発明は、コンピュータソフトウエア産業、宇宙開発産業等に利用可能である。
【図面の簡単な説明】
【０１００】
【図１】システム１を実現するためのハードウエア構成の一例を示す図である。
【図２】システム１において、ＣＰＵ１０がＲＯＭ１１に記憶されたシステム実行プログラムを実行することにより機能する機能ブロック、及びシステム１の作動に際してＲＡＭ１２等に記憶される情報を示す図である。
【図３】対象プログラム実行部２０がスライス実行方式により複数の対象プログラムを並行して実行する様子を概念的に示す図である。
【図４】本発明に係る評価関数の特性形状を例示する図である。
【図５】本実施例のシステム１が実行する特徴的な処理の流れを示すフローチャートの一例である。
【図６】本発明に係るシミュレーション実験における対象プログラムの構造を示す図である。
【図７】交叉が行なわれる様子を概念的に示す図である。
【図８】ビット反転による突然変異が行なわれる様子と、ランダムな突然変異が行なわれる様子を概念的に示す図である。
【図９】本発明に係るシミュレーション実験において用意された初期プログラムの一部を示す図である。
【図１０】本発明に係るシミュレーション実験において用意された初期プログラムの一部を示す図である。
【図１１】本発明に係るシミュレーション実験において用意された初期プログラムの一部を示す図である。
【図１２】本発明に係るシミュレーション実験の結果を示す図である。
【図１３】本発明に係るシミュレーション実験の結果として得られた、より優秀な対象プログラムを示す図である。
【図１４】本発明に係る評価関数の特性形状の他の例を示す図である。
【符号の説明】
【０１０１】
１ プログラムの維持・改良システム（システム）
１０ ＣＰＵ
１１ ＲＯＭ
１２ ＲＡＭ
１３ ＨＤＤ
１４ 入力受付装置
１５ バス
２０ 対象プログラム実行部
２２ 対象プログラム削除部
２４ 対象プログラム評価部
２６ 削除順位変更部
２８ 対象プログラム複製部
３０ 変異処理部
３２ 対象プログラムリスト
３４ 削除待ち行列
３６ 評価値履歴
【特許請求の範囲】
【請求項１】
対象プログラムを実行する実行手段と、
所定の記憶手段に記憶された削除待ち行列に従って前記対象プログラムを削除する削除手段と、
実行終了した前記対象プログラムについて、数値化された実行結果が目標値と合致した場合に最大値を評価値として出力すると共に数値化された実行結果が目標値から離れるに従って小さくなる値を評価値として出力する傾向を有する評価関数によって、評価を行なう評価手段と、
前記評価手段による評価値に基づいて、前記対象プログラムの前記削除待ち行列における削除順位を変更する削除順位変更手段と、
前記評価手段による評価値に基づいて、前記対象プログラムを複製する複製手段と、
を備えるプログラムの維持・改良システム。
【請求項２】
前記削除順位変更手段は、前記評価手段による評価値が前記最大値である場合に、該評価された対象プログラムの前記削除待ち行列における削除順位が下がるように、前記対象プログラムの前記削除待ち行列における削除順位を変更する手段である、請求項１に記載のプログラムの維持・改良システム。
【請求項３】
前記対象プログラムに変異を生じさせる変異処理手段を備える、請求項１又は２に記載のプログラムの維持・改良システム。
【請求項４】
前記評価関数の設定又は変更に関する外部からの入力を受け付ける評価関数入力受付手段を備える、請求項１ないし３のいずれか１項に記載のプログラムの維持・改良システム。
【請求項５】
前記評価手段の評価値を記憶する評価値記憶手段を備え、
前記複製手段は、前記評価値記憶手段に記憶された評価値の履歴に基づいて、前記対象プログラムを複製する手段である、請求項１ないし４のいずれか１項に記載のプログラムの維持・改良システム。
【請求項６】
前記複製手段は、前記評価値記憶手段に記憶された評価値の累計値に基づく値が所定の複製基準値を超えた場合に対象プログラムを複製する手段である、請求項５に記載のプログラムの維持・改良システム。
【請求項７】
前記評価関数は、最低値として累計可能な値を出力する関数である、請求項６に記載のプログラムの維持・改良システム。
【請求項８】
宇宙空間で使用されることを特徴とする、請求項１ないし７のいずれか１項に記載のプログラムの維持・改良システム。
【請求項９】
前記変異処理手段は、自己の作動に依らない対象プログラムの変異発生率に応じて前記対象プログラムに変異を生じさせる確率を変更する手段である、請求項３、又は請求項３に係る請求項４ないし８のいずれか１項に記載のプログラムの維持・改良システム。
【請求項１０】
コンピュータを、請求項１ないし９のいずれか１項に記載のプログラムの維持・改良システムとして機能させるための、コンピュータ読み取り可能なプログラム
【請求項１】
対象プログラムを実行する実行手段と、
所定の記憶手段に記憶された削除待ち行列に従って前記対象プログラムを削除する削除手段と、
実行終了した前記対象プログラムについて、数値化された実行結果が目標値と合致した場合に最大値を評価値として出力すると共に数値化された実行結果が目標値から離れるに従って小さくなる値を評価値として出力する傾向を有する評価関数によって、評価を行なう評価手段と、
前記評価手段による評価値に基づいて、前記対象プログラムの前記削除待ち行列における削除順位を変更する削除順位変更手段と、
前記評価手段による評価値に基づいて、前記対象プログラムを複製する複製手段と、
を備えるプログラムの維持・改良システム。
【請求項２】
前記削除順位変更手段は、前記評価手段による評価値が前記最大値である場合に、該評価された対象プログラムの前記削除待ち行列における削除順位が下がるように、前記対象プログラムの前記削除待ち行列における削除順位を変更する手段である、請求項１に記載のプログラムの維持・改良システム。
【請求項３】
前記対象プログラムに変異を生じさせる変異処理手段を備える、請求項１又は２に記載のプログラムの維持・改良システム。
【請求項４】
前記評価関数の設定又は変更に関する外部からの入力を受け付ける評価関数入力受付手段を備える、請求項１ないし３のいずれか１項に記載のプログラムの維持・改良システム。
【請求項５】
前記評価手段の評価値を記憶する評価値記憶手段を備え、
前記複製手段は、前記評価値記憶手段に記憶された評価値の履歴に基づいて、前記対象プログラムを複製する手段である、請求項１ないし４のいずれか１項に記載のプログラムの維持・改良システム。
【請求項６】
前記複製手段は、前記評価値記憶手段に記憶された評価値の累計値に基づく値が所定の複製基準値を超えた場合に対象プログラムを複製する手段である、請求項５に記載のプログラムの維持・改良システム。
【請求項７】
前記評価関数は、最低値として累計可能な値を出力する関数である、請求項６に記載のプログラムの維持・改良システム。
【請求項８】
宇宙空間で使用されることを特徴とする、請求項１ないし７のいずれか１項に記載のプログラムの維持・改良システム。
【請求項９】
前記変異処理手段は、自己の作動に依らない対象プログラムの変異発生率に応じて前記対象プログラムに変異を生じさせる確率を変更する手段である、請求項３、又は請求項３に係る請求項４ないし８のいずれか１項に記載のプログラムの維持・改良システム。
【請求項１０】
コンピュータを、請求項１ないし９のいずれか１項に記載のプログラムの維持・改良システムとして機能させるための、コンピュータ読み取り可能なプログラム
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２００９−４３１５２（Ｐ２００９−４３１５２Ａ）
【公開日】平成２１年２月２６日（２００９．２．２６）
【国際特許分類】
【出願番号】特願２００７−２０９６１７（Ｐ２００７−２０９６１７）
【出願日】平成１９年８月１０日（２００７．８．１０）
【出願人】（５０４１３３１１０）国立大学法人 電気通信大学 (383)
【Ｆターム（参考）】
【公開日】平成２１年２月２６日（２００９．２．２６）
【国際特許分類】
【出願日】平成１９年８月１０日（２００７．８．１０）
【出願人】（５０４１３３１１０）国立大学法人 電気通信大学 (383)
【Ｆターム（参考）】
[ Back to top ]