权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

集合分割問題のためのヒューリスティック統計推論の提案と情報検索システムへの適用

集合划分问题的启发式统计推断的提出及其在信息检索系统中的应用

基本信息

批准号：
07750468
负责人：
相澤彰子
金额：
$ 0.7万
依托单位：
National Institute of Informatics
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至无数据
项目状态：
已结题

项目摘要

本研究は,Walsh関数によるだまし問題の解析やEpistasis Varianceと呼ばれる情報基準による問題の容易性/困難性の判定など,遺伝的アルゴリズム(Genetic Algorithm,以下GA)における理論研究の流れを組むものであり,GAに代表される多点探索法を,探索空間の確率的なサンプリングによる超並列な統計推論として位置付けたことが特徴となっている.本研究の1年間の研究活動による成果は以下のとおりである.まず,探索空間の特徴づけに関する理論的な考察では,L個の2値変量によって定義される実数値関数を対象として,大きさ2^Lの探索空間をk個の変数の値により2^k個の部分空間に分割した場合のばらつき(分散)に注目した.そして,この統計量とWalsh係数の間の関係を明らかにすることにより,分割により得られる部分集合の平均値の分散が,選ばれたk個の変数の依存関係の強さを表すマクロな特徴量であることを示した.次に,高並列な統計推論に関する理論的な展開では,上記の特徴量が,Epistasis Varianceや相関度分析(Correlation Analysis)など,従来より提案されてきたGAの理論分析手法の一般化となっていることを示した.これに基づきGAの交叉オペレータの数学的な意味を解析し、解空間の中に潜む依存関係を統計的かつ高並列に推測して,依存関係のある部分空間に対してランダム探索を,独立な部分空間に対しては重畳効果を期待した組合せ操作を適用する手法としてGAを再定義した.さらに実験による評価では,特徴的な複数のテスト問題を用いて上記の特徴量を計算し,実際にGAを適用して最適化を行った場合の性能との一致性を検証した.本研究は,探索空間のマクロ的な特徴(分割された部分空間の間のばらつき)とミクロ的な特徴(Walsh係数)を対応づけ,既存の代表的な分析法であるWalsh関数分析,Epistasis Variance,および相関度分析の間の関係を明らかにした点で新しいものである.また本研究では,従来生物学とのアナロジーで論じられてきたGAを,依存関係仮説のランダムな選択に基づく確率的なサンプリングとして捉えており,これより情報検索システムのクラスタリングなど,従来の枠組を超えた問題への適用が期待される.

In this study,Walsh correlation analysis, Epistasis Variation, and information criteria are used to determine the ease/difficulty of the problem, and Genetic Algorithm (GA) is used to analyze the flow of theoretical research. GA represents the multi-point search method to explore the spatial accuracy rate. The results of the research activities in the past year are as follows. In this paper, the theoretical investigation of the characteristics of the exploration space is to define the number of values related to the number of objects, and to define the number of values related to the number of objects. The relationship between these statistics and Walsh coefficients is shown in Table 1. Second, high parallel statistical inference related to the theory of development, the characteristics of the above,Epistasis Variation Analysis (Correlation Analysis), to propose a general approach to GA theoretical analysis. The mathematical meaning of the intersection of the basic space GA is analyzed, the latent dependence relationship in the solution space is estimated, the dependence relationship in the partial space is explored, and the independent partial space is redefined. In this case, the evaluation of the characteristics of the complex number of test problems is used to calculate the characteristics of the above, and in practice, GA is applied to optimize the performance and consistency of the case. This study is to explore the characteristics of space (partition of partial space) and the characteristics of space (Walsh coefficient). The existing representative analysis methods include Walsh correlation analysis,Epistasis Variation, and correlation analysis. In this paper, we discuss the relationship between genetic and biological factors, and the relationship between genetic and biological factors.