Competent Genetic Algorithms can efficiently address problems in which the linkage between variables is limited to a small order k. Problems with higher order dependencies can only be addressed efficiently if further problem properties exist that can be exploited. An important class of problems for which this occurs is that of hierarchical problems. Hierarchical problems can contain dependencies between all variables (k=n) while being solvable in polynomial time.An open question so far is what precise properties a hierarchical problem must possess in order to be solvable efficiently. We study this question by investigating several features of hierarchical problems and determining their effect on computational complexity, both analytically and empirically. The analyses are based on the Hierarchical Genetic Algorithm (HGA), which is developed as part of this work. The HGA is tested on ranges of hierarchical problems, produced by a generator for hierarchical problems.
展开▼
机译：能够有效的遗传算法可以有效地解决了哪些问题，其中变量之间的连接限制为小订单 k 。如果存在可以利用的进一步问题属性，则只能有效地解决更高订单依赖性的问题。发生这种情况的重要类别是分层问题的问题。分层问题可以包含所有变量（k = n）之间的依赖性，同时在多项式时间中可解决。到目前为止的开放问题是分层问题必须拥有的精确属性，以便有效可解决。我们通过调查分层问题的若干特征并确定它们对计算复杂性的影响，分析和经验来研究这个问题。分析基于分层遗传算法（HGA），该遗传算法（HGA）是作为这项工作的一部分开发的。 HGA在由发电机产生的分层问题的范围内进行测试，以进行分级问题。
展开▼
