具有交叉和约束修复的解决子图的演变群体
Jiwon Lee1, Mahya Salimi Gamasaei2, Andrew M Sutton3
1Algorithmic Evolution Lab, Department of Computer Science, University of Minnesota Duluth lee02761@d.umn.edu.
Evolutionary computation
|January 14, 2026
概括
本研究介绍了一种基于人口的算法,用于解决参数化的图形问题,如k-vertex cover. 它在子图上演变解决方案,使用一个新的交叉运算符来有效地为更大的图找到最佳解决方案.
科学领域:
- 计算机科学 计算机科学
- 图形理论 图形理论
- 算法设计 算法设计
背景情况:
- 参数化图形问题涉及找到满足特定标准的小顶点集.
- 现有的方法可能会在复杂的图形结构的可扩展性和效率方面扎.
研究的目的:
- 开发一种新的基于人口的方法来解决参数化的图形问题.
- 为结合子图解引入一个通用的等位基交叉运算符.
- 分析拟议方法的运行时间复杂性和实际适用性.
主要方法:
- 基于人口的进化算法在子图上演变解决方案.
- 引入一个概括的等位基交叉运算符,概括统一的交叉.
- 使用RLS风格和受约束突变对k-vertex覆盖的预期运行时间的分析.
主要成果:
- 该算法在预期时间O ((4km+m4logn) 中通过RLS样式的突变解决了k-顶点覆盖问题.
- 运行时间改进到O ((4km+m2nklogn) 与受约束的突变.
- 一个经过修改的算法在 Ω(2km3log2n) 运行时间内找到具有高概率的最大 k 覆盖的子图.
- 经验结果表明,生成的子图保留了源图的结构性质.
结论:
- 提出的基于人口的方法为参数化图表问题提供了一种有效的方法.
- 一般化的等位基交叉运算符有效地将子图的解决方案结合起来.
- 生成结构代表性的子图的能力对图形基准测试有影响.
相关概念视频
Crossing Over
169.0K
Unlike mitosis, meiosis aims for genetic diversity in its creation of haploid gametes. Dividing germ cells first begin this process in prophase I, where each chromosome—replicated in S phase—is now composed of two sister chromatids (identical copies) joined centrally.
The homologous pairs of sister chromosomes—one from the maternal and one from the paternal genome—then begin to align alongside each other lengthwise, matching corresponding DNA positions in a process...
The homologous pairs of sister chromosomes—one from the maternal and one from the paternal genome—then begin to align alongside each other lengthwise, matching corresponding DNA positions in a process...
169.0K
Crossing Over
6.2K
Crossing over is the exchange of genetic information between homologous chromosomes during prophase I of meiosis I. Genetic recombination gives rise to allelic diversity in the newly formed daughter cells. In humans, crossing over produces genetically distinct haploid egg and sperm cells that undergo fertilization to produce unique offspring. Before cell division starts, the germ cell’s chromosome(s) undergo duplication in the S phase of the cell cycle. As the cells enter prophase I,...
6.2K
Gene Conversion
10.6K
Other than maintaining genome stability via DNA repair, homologous recombination plays an important role in diversifying the genome. In fact, the recombination of sequences forms the molecular basis of genomic evolution. Random and non-random permutations of genomic sequences create a library of new amalgamated sequences. These newly formed genomes can determine the fitness and survival of cells. In bacteria, homologous and non-homologous types of recombination lead to the evolution of new...
10.6K
Gene Conversion
2.9K
2.9K
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.8K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.8K
Long-patch Base Excision Repair
7.9K
Since the discovery of the two BER pathways, there has been a debate about how a cell chooses one pathway over the other and the factors determining this selection. Numerous in vitro experiments have pointed out multiple determinants for the sub-pathway selection. These are:
7.9K


