高並列統計推論による探索問題へのアプローチ

使用高度并行的统计推断来处理搜索问题

基本信息

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

项目摘要

本研究では,遺伝的アルゴリズム(Genetic Algorithm,以下GA)における交叉オペレータの理論的な分析を通して,GAに代表される多点探索法の,高並列統計推論アルゴリズムとしての役割を考察した.具体的にはまず,κ個の2値変数により定義される解空間を対象として,解空間を独立な部分空間に分割するための仮説(線形分割仮説)を考えた.仮説の有用性を評価する基準として,「分散係数」と呼ぶ簡単な統計量を定義し,「分散係数」と2値関数系のフーリエ解析法であるWalsh係数の関係を明らかにした.また,集団遺伝子学の分野で用いられているエピスタシス分散との対応も示した.さらに「分散係数」と交叉オペレータの評価基準である交叉相関係数の関係を数学的に導き,交叉オペレータによる探索が,問題を部分問題に分割する多数の仮説を確率的に選択して,依存関係の強い部分空間の中ではランダム探索を,独立性の強い部分空間の間では重畳効果を期待した組合せ操作を適用する手法としてモデル化できることを示した.本研究により,従来より提案されてきた解空間の特徴量の相互の関連を明らかにすることができた.特に,これまで経験的にしか有効性が示されていなかった交叉相関係数の理論的な意味付けを与えた点は新しい.また現在,多点探索による柔軟な最適化手法をインターネット情報システムの中継サーバの高度化に役立てる適用を検討中であり,今後の課題となっている.

本研究采用遗传算法（Genetic Algorithm）通过对算法（GA）中交叉算子的理论分析，我们考虑了以GA为代表的多点搜索方法作为高度并行的统计推理算法的作用，我们考虑了划分解空间的假设（线性划分假设）。划分为由定义的解空间的独立子空间。作为评价该理论有用性的标准，我们定义了一个简单的统计量，称为“色散系数”，并阐明了“色散系数”与沃尔什系数之间的关系，沃尔什系数是二元傅立叶分析方法。此外，我们还展示了与群体遗传学领域中使用的上位色散的对应关系。此外，我们还展示了“色散系数”与互相关系数之间的相关性，互相关系数是交叉算子的评价标准。该关系是通过数学推导的，并且使用交叉算子的搜索随机选择许多将问题划分为子问题的假设，允许在具有强依赖性的子空间中进行随机搜索，并在具有强独立性的子空间中进行搜索，我们证明了它可以。被建模为一种应用组合运算的方法，该组合运算期望在特别是，它的新颖之处在于它为互相关系数赋予了理论意义，而互相关系数的有效性迄今为止仅在经验上得到证明。此外，我们目前正在考虑使用多点搜索的灵活优化方法来帮助提高复杂性。互联网信息系统中的中继服务器，这是一个未来的话题。