遺伝的アルゴリズムの設計理論の確立およびその大規模分散システム設計への応用

遗传算法设计理论的建立及其在大规模分布式系统设计中的应用

基本信息

批准号：
13780182
负责人：
棟朝雅晴
金额：
$ 1.73万
依托单位：
Hokkaido University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

项目摘要

本研究においては、線型・非線型および単調・非単調性を調べることによって関連する遺伝子座のまとまりであるリンケージ集合を同定し、効果的な交叉を実現する手法に関してその理論的基礎を確立するとともに、理論に基づいた遺伝的アルゴリズムの設計、特に交叉手法の改良を行うことで、大規模な最適化問題におけるアルゴリズムの性能を評価した。リンケージ集合の構造として、これまでの研究では比較的単純な線形の構造が仮定されていたが、本研究では階層構造を有するリンケージの同定を行う手法である、hLIEM(hierarchical Linkage Identification with Epistasis Measure)およびhLIEM^2(hierarchical Linkage Identification with Epistasis Measure considering Monotonicity)を開発した。これら手法においては、小さなリンケージ集合をまとめてより大きなリンケージ集合を生成するという過程を繰り返すことで、現実問題の多くが有すると考えられる問題の階層構造を同定することが可能となり、交叉など遺伝的操作をさらに効率的に適用することが可能となった。本研究で開発した階層型のリンケージ同定アルゴリズムの有効性を、階層型のトラップ関数に代表される各種のテスト関数において確認したが、さらに現実の問題として都市圏ネットワーク設計問題へと適用し、その有効性を確かめた。大規模なネットワークを設計する場合、ゆるやかな階層構造を有するようなネットワークとして設計を行うことが考えられるが、本研究で提案するアルゴリズムにより、人間の設計者が介在することなく、計算機により自動的に適切な階層構造を有するネットワークを構成することができ、従来の手法に比べて、より低コストで高性能なネットワークを設計することができた。

在这项研究中，我们确定了链接集，这些链接集通过检查线性，非线性和单调性来分组相关的基因座，并确定了实现有效交叉的方法的理论基础，并评估了算法在大规模优化问题中的性能，通过设计基于理论的遗传算法，尤其是改进交叉方法。先前的研究假设相对简单的线性结构是连锁集的结构，但是在这项研究中，我们开发了与上位数测度（HLIEM）（HLIEM）和HLIEM^2（层次链接识别与Epistasis shipipasis shouldotonicity的层次链接识别）的层次结合识别，这些方法是考虑与单个结构识别链接的方法。在这些方法中，通过重复将小链接集合在一起以生成较大的链接集的过程，可以确定许多实际问题可能存在的问题的层次结构，并且可以更有效地应用诸如交叉的遗传操作。在本研究中开发的层次链接识别算法的有效性已在各种测试功能（例如分层陷阱函数）中得到了证实，但是作为一个真正的问题，它被应用于城市区域网络设计问题，并确认了其有效性。在设计大型网络时，可以将网络设计为具有柔和层次结构的网络，但是本研究中提出的算法使计算机可以自动构建适当的层次结构，而无需人工设计人员的干预，从而使网络具有更低的成本和比传统方法更高的性能。