关于解决双目标最小跨树问题的单个目标子图形基基突变
Jakob Bossek1, Christian Grimme2
1AI Methodology, Department of Computer Science, RWTH Aachen University, Germany bossek@aim.rwth-aachen.de.
Evolutionary computation
|June 8, 2023
概括
本研究为多目标最小跨树问题 (moMST) 引入了新的进化计算运算符. 这些高效的基于子图的突变运算符甚至在有限的计算资源下也超过了现有的方法.
科学领域:
- 计算机科学 计算机科学
- 运营研究 运营研究
- 人工智能的人工智能
背景情况:
- 多目标最小跨树问题 (moMST) 是一个具有计算挑战性的NP-hard问题.
- 接近moMST的帕雷托集对于理解多目标优化中的权衡至关重要.
研究的目的:
- 开发高效的进化计算运算符来近似moMST问题的帕雷托集.
- 分析帕雷托最佳跨度树的邻居结构,以设计有效的突变运算符.
主要方法:
- 为进化算法设计和实施基于子图的新型突变运算符.
- 运行时间复杂性和拟议运算符的帕雷托效益性质的分析.
- 与已建立的基线算法进行广泛的实验基准测试.
主要成果:
- 与基线算法相比,开发的基于子图的运算符表现出优异的性能.
- 即使在有限的计算预算下,也实现了对帕雷托集的有效接近.
- 运算符在各种各样的图形类中表现出实际适用性,具有不同的帕雷托前方形状.
结论:
- 提出的进化计算方法为解决moMST问题提供了一种有效的方法.
- 基于子图的突变运算符在接近帕雷托最佳解决方案方面取得了重大进展.
- 该研究证实了新运营商在多目标优化中的实际可行性和效率.
相关概念视频
Point and Frameshift Mutations
38
Point mutations are genetic alterations involving the change of a single nucleotide base pair in DNA. Depending on how the alteration affects protein synthesis, they can lead to various consequences.Point mutations fall into the following types:Silent mutations occur when a nucleotide change does not alter the amino acid sequence due to the redundancy of the genetic code. For instance, changing ACC to ACA still encodes threonine, leaving the protein function unaffected. This occurs because...
38
Mismatch Repair
4.9K
Organisms are capable of detecting and fixing nucleotide mismatches that occur during DNA replication. This sophisticated process requires identifying the new strand and replacing the erroneous bases with correct nucleotides. Mismatch repair is coordinated by many proteins in both prokaryotes and eukaryotes.
The Mutator Protein Family Plays a Key Role in DNA Mismatch Repair
The human genome has more than 3 billion base pairs of DNA per cell. Prior to cell division, that vast amount of genetic...
The Mutator Protein Family Plays a Key Role in DNA Mismatch Repair
The human genome has more than 3 billion base pairs of DNA per cell. Prior to cell division, that vast amount of genetic...
4.9K
Mutation, Gene Flow, and Genetic Drift
58.7K
In a population that is not at Hardy-Weinberg equilibrium, the frequency of alleles changes over time. Therefore, any deviations from the five conditions of Hardy-Weinberg equilibrium can alter the genetic variation of a given population. Conditions that change the genetic variability of a population include mutations, natural selection, non-random mating, gene flow, and genetic drift (small population size).
58.7K
Mutations
83.8K
Overview
83.8K
Survival Tree
119
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
Building a Survival Tree
Constructing a...
Building a Survival Tree
Constructing a...
119
Mutations in Microorganisms
36
Mutations are heritable changes in an organism’s genome involving alterations in the base sequence of DNA or RNA. These changes can influence cellular processes and phenotypic traits, potentially transforming the unaltered wild type into a mutant form. Such changes, termed forward mutations, are pivotal in shaping the genetic diversity of organisms.RNA viruses exhibit the highest mutation rates due to the absence of robust proofreading mechanisms during genome replication. In contrast,...
36


