特許ウォッチ

公開番号2024180020
公報種別公開特許公報(A)
公開日2024-12-26
出願番号2023099425
出願日2023-06-16
発明の名称プログラム生成装置、プログラム生成方法及びプログラム
出願人日本電信電話株式会社,国立大学法人大阪大学
代理人弁理士法人ITOH,個人,個人,個人
主分類G06F 8/30 20180101AFI20241219BHJP(計算;計数)
要約【課題】自動的に生成されるプログラムが局所最適解に陥る可能性を低下させること。
【解決手段】プログラム生成装置は、所定の入出力を満たすプログラムが生成されるまで遺伝的アルゴリズムを利用して世代ごとに複数のプログラムを生成するように構成されている生成部と、前記世代ごとに、当該世代において生成された複数のプログラムのそれぞれについて所定の評価関数の値を導出するように構成されている評価部と、を有し、前記生成部は、世代ごとの前記値の順位の履歴が所定条件を満たすプログラムが遺伝的アルゴリズムに基づく新たな世代のプログラムの生成に利用される確率を、前記所定条件を満たさないプログラムよりも低下させるように構成されている。
【選択図】図2
特許請求の範囲【請求項１】
所定の入出力を満たすプログラムが生成されるまで遺伝的アルゴリズムを利用して世代ごとに複数のプログラムを生成するように構成されている生成部と、
前記世代ごとに、当該世代において生成された複数のプログラムのそれぞれについて所定の評価関数の値を導出するように構成されている評価部と、
を有し、
前記生成部は、世代ごとの前記値の順位の履歴が所定条件を満たすプログラムが遺伝的アルゴリズムに基づく新たな世代のプログラムの生成に利用される確率を、前記所定条件を満たさないプログラムよりも低下させるように構成されている、
ことを特徴とするプログラム生成装置。
続きを表示（約 720 文字）【請求項２】
前記所定条件は、世代ごとの前記値の順位に応じて異なる加算値の総和が閾値以上であることである、
ことを特徴とする請求項１記載のプログラム生成装置。
【請求項３】
前記加算値は、前記値の順位が前であるほど大きい、
ことを特徴とする請求項２記載のプログラム生成装置。
【請求項４】
所定の入出力を満たすプログラムが生成されるまで遺伝的アルゴリズムを利用して世代ごとに複数のプログラムを生成する生成手順と、
前記世代ごとに、当該世代において生成された複数のプログラムのそれぞれについて所定の評価関数の値を導出する評価手順と、
をコンピュータが実行し、
前記生成手順は、世代ごとの前記値の順位の履歴が所定条件を満たすプログラムが遺伝的アルゴリズムに基づく新たな世代のプログラムの生成に利用される確率を、前記所定条件を満たさないプログラムよりも低下させる、
ことを特徴とするプログラム生成方法。
【請求項５】
所定の入出力を満たすプログラムが生成されるまで遺伝的アルゴリズムを利用して世代ごとに複数のプログラムを生成する生成手順と、
前記世代ごとに、当該世代において生成された複数のプログラムのそれぞれについて所定の評価関数の値を導出する評価手順と、
をコンピュータに実行させ、
前記生成手順は、世代ごとの前記値の順位の履歴が所定条件を満たすプログラムが遺伝的アルゴリズムに基づく新たな世代のプログラムの生成に利用される確率を、前記所定条件を満たさないプログラムよりも低下させる、
ことを特徴とするプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、プログラム生成装置、プログラム生成方法及びプログラムに関する。
続きを表示（約 2,200 文字）【背景技術】
【０００２】
近年、社会全体のＩＴ化が進む一方で、ＩＴ人材の不足が大きな問題となっている。経済産業省の試算によると、２０２５年には約３６万人のＩＴ人材が不足すると予測されている。特に専門的な知識を必要とする実装工程におけるＩＴ人材の不足は喫緊の課題であり、自動でプログラミングを行う自動プログラミング技術の研究開発が求められている。
【０００３】
自動プログラミング技術の１つとして遺伝的プログラミングと呼ばれる技術が存在する（非特許文献１）。遺伝的プログラミングはプログラムのような木構造のデータに対して遺伝的アルゴリズムを用いた手法である。遺伝的プログラミングでは評価関数に基づき、プログラムを生物の進化に見立て、選択、交叉、突然変異というプロセスを経て世代を重ねて進化させていくことで、最終的に所望のプログラムを得る。評価関数としては仕様となる入出力例を満たす数などが用いられる。
【先行技術文献】
【非特許文献】
【０００４】
Milad Taleby Ahvanooey, Qianmu Li, Ming Wu, Shuo Wang, "A Survey of Genetic Programming and Its Applications," KSII Transactions on Internet and Information Systems, vol. 13, no. 4. Korean Society for Internet Information (KSII), 30-Apr-2019
【発明の概要】
【発明が解決しようとする課題】
【０００５】
遺伝的プログラミングの課題として、探索中に局所最適解に陥る可能性があることが挙げられる。局所最適解とは、その近くでは最も良い解だが、全体では最も良いとは限らない解のことである。一度、局所最適解に陥るとその近傍から抜け出せず、探索が滞ることが知られている。
【０００６】
本発明は、上記の点に鑑みてなされたものであって、自動的に生成されるプログラムが局所最適解に陥る可能性を低下させることを目的とする。
【課題を解決するための手段】
【０００７】
そこで上記課題を解決するため、プログラム生成装置は、所定の入出力を満たすプログラムが生成されるまで遺伝的アルゴリズムを利用して世代ごとに複数のプログラムを生成するように構成されている生成部と、前記世代ごとに、当該世代において生成された複数のプログラムのそれぞれについて所定の評価関数の値を導出するように構成されている評価部と、を有し、前記生成部は、世代ごとの前記値の順位の履歴が所定条件を満たすプログラムが遺伝的アルゴリズムに基づく新たな世代のプログラムの生成に利用される確率を、前記所定条件を満たさないプログラムよりも低下させるように構成されている。
【発明の効果】
【０００８】
自動的に生成されるプログラムが局所最適解に陥る可能性を低下させることができる。
【図面の簡単な説明】
【０００９】
本発明の実施の形態におけるプログラム生成装置１０のハードウェア構成例を示す図である。
本発明の実施の形態におけるプログラム生成装置１０の機能構成例を示す図である。
プログラム生成装置１０が実行する処理手順の一例を説明するためのフローチャートである。
プログラム部品リストの一例を示す図である。
入出力例セットの一例を示す図である。
入出力例セットを満たす合成コードの一例を示す図である。
評価値が上位Ｎ位までの合成コードの登場スコアを登場プログラムリストへ追加する処理手順の一例を説明するためのフローチャートである。
本実施の形態の具体例を説明するための図である。
【発明を実施するための形態】
【００１０】
本実施の形態では、遺伝的プログラミングによるプログラムの探索中に局所最適解に陥った可能性が有ると判定された場合、その原因となったプログラムをブラックリストに登録し、ブラックリスト中のプログラムの評価関数の値を恣意的に下げることで局所最適解から脱出する。結果として所望のプログラムを得られやすくする。より詳しくは、本実施の形態では、以下の手順で所望のプログラムが探索される。
（１）遺伝的プログラミングでプログラムを進化させていく。この時、各世代で評価関数の値が上位Ｎ位に入るプログラム（個体）を、各世代における評価値の順位に基づく値（以下、「登場スコア」という。）と共に登場プログラムリストに保存する。
（２）登場プログラムリストにおいて、世代ごとの評価値の順位の履歴が所定条件を満たすプログラム（登場スコアが閾値以上であるプログラム）が発生したら、当該プログラムをブラックリストに入れる。
（３）入出力例を満たすプログラムが得られるまで（１）、（２）を繰り返す。この間、ブラックリストに入っているプログラムの評価値は最低値とすることで、当該プログラムが遺伝的操作の対象とされる確率が下げられる。
（【００１１】以降は省略されています）

関連特許