超平面処理に基づく集団型探索アルゴリズムの研究

基于超平面处理的集体搜索算法研究

基本信息

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

项目摘要

本研究は平成6年度の単年度で,柔らかい最適化手法として注目される集団型探索法に関する基礎的な検討を行うものであり,解空間上で定義される超平面の統計モデルに基づく新しい解探索アルゴリズムの提案および評価を目的としている.1年間の研究活動による本研究の成果は以下のとおりである.まず,集団型探索法における局所処理の考案では,超平面で表現された部分空間上での解探索を正規分布からのサンプリングとしてモデル化して,「スキーマ貧欲」(schemata expliting)と呼ぶ局所探索メカニズムを定義した.そして,この「スキーマ貧欲」な局所探索を,解候補の集団から優れた部分集合を選択する問題に対応づけ,「確率的スキーマ貧欲法」(stochastic schemata exploiter,以下SSE)と呼ぶ新しい解探索アルゴリズムを提案した.次に,集団型探索法における最適化問題の分析では,超平面内に存在する解の平均および分散の観測値に基づき優れた超平面の選択の容易性を予測し,与えられた問題の容易/困難性を判断する方法を提案した.この分析法は最適解が既知であることを必要とするが,分析の結果を視覚的に把握でき大規模な問題に適用可能な点が特徴である.さらに,容易/困難なテスト問題を用いた評価では,提案したSSEと代表的な集団型探索アルゴリズムである遺伝的アルゴリズムの性能を比較した.実験の結果,SSEが局所探索に優れ,はやい収束特性を持つこと,および大域探索に関してはほぼ同等の能力を持つことを示した.また,ランダム探索とのハイブリッド化によるだまし問題の克服,ヒューリスティク探索とのハイブリッド化による近傍探索の改善,の2つについて両者の適性を評価し,SSEのはやい収束特性が他の探索手法とのハイブリッド化において有利であることを示した.本研究で提案した手法は,超平面上の処理を部分集合の選択問題に還元して領域に依存しない効率的な探索法を提供するものである.選択確率の計算法の検討などにより,さらに新しいアルゴリズムへと発展することが期待される.

这项研究是1994年的一项为期一年的研究，旨在提供有关集体搜索方法的基本研究，该研究吸引了作为软优化方法的关注，并旨在根据解决方案空间中定义的超平面统计模型提出和评估一种新的解决方案搜索算法。一年研究活动的这项研究结果如下。首先，在集体搜索方法中设计本地处理时，将在超平面中表达的子空间上的解决方案搜索被建模为从正常分布中的采样，以及一种局部搜索机制，称为“ schemata dismiting”。然后将此“模式贪婪”的本地搜索映射到从一组解决方案候选物中选择上级子集的问题，然后用于随机示例示例。我们提出了一种称为exploiter的新解决方案搜索算法（以下称为SSE）。接下来，在分析集体类型搜索方法中的优化问题时，我们根据对超平面中存在的溶液的平均值和溶液的均值和方差的观察来预测优质超平面的选择，并提出了一种确定给定问题的易于/难度的方法。该分析方法要求已知最佳解决方案，但其特征是可以在视觉上掌握分析结果并将其应用于大规模问题。此外，在使用易于/难度测试问题的评估中，比较了拟议的SSE和遗传算法的性能（一种典型的集体型搜索算法）。实验的结果表明SSE已定位。结果表明，它具有出色的搜索，具有快速的收敛特征，并且具有几乎相同的全球搜索功能。此外，对两种类型的两种类型的适用性进行了评估：通过与随机搜索杂交并通过与启发式搜索杂交来克服欺骗性问题，并表明SSE的快速收敛特征在与其他搜索方法中杂交具有优势。这项研究中提出的方法将在超平面上的处理减少到子集选择问题，从而提供了独立于域的有效搜索方法。可以预期，通过检查计算选择概率的方法，将进一步开发为新的算法。