在对称解决方案空间中搜索 permutation 相关的优化问题
概括
这项研究利用群理论来识别和利用组合优化问题的对称性. 一种新的半解决方案空间搜索策略提高了计算效率和性能,用于比较问题,如TSP.
科学领域:
- 数学 数学 是一个数学.
- 计算机科学 计算机科学
- 运营研究 运营研究
背景情况:
- 对称性在自然界中普遍存在,可以通过减少冗余来优化计算效率.
- 与变换相关的组合优化问题往往表现出复杂的解决方案空间.
- 群理论为理解和分析对称结构提供了一个框架.
研究的目的:
- 通过使用群理论探索与 permutation 相关的组合优化问题的解决方案空间的对称结构.
- 开发一种新的搜索策略,利用已识别的对称特征来提高计算效率.
- 调整战略以适应不符合固有的对称性条件的情况.
主要方法:
- 集团理论和集团行动的应用,以分析 permutation 问题的解决空间.
- 设计适用于共同搜索操作者的半解决方案空间搜索策略.
- 开发维度映射方法,以便在不满足对称条件时实现战略.
- 对单行设施布局问题 (SRFLP),旅行销售员问题 (TSP) 和多目标旅行销售员问题 (MOTSP) 的基准实例进行实证评估.
主要成果:
- 根据对象函数形式和对象号码发现有意义的对称特征的条件.
- 证明半解决方案空间搜索策略可以在没有增加计算成本的情况下增强有前途的地区的探索.
- 成功地将战略应用于SRFLP,TSP和MOTSP基准实例.
- 使用该策略的算法与未利用对称性的算法相比,显示出更具竞争力的性能.
结论:
- 提出的半解决方案空间搜索策略有效地利用了组合优化中的对称性.
- 这种方法提供了一种方法,通过利用固有的结构性质来提高优化算法的性能.
- 维度映射技术将对称性利用的适用性扩展到更广泛的问题.
更多相关视频
相关概念视频
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.0K
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.0K
Properties of Fourier series II
125
Time scaling of signals is a crucial concept in signal processing that affects the Fourier series representation without altering its coefficients. The process modifies the fundamental frequency, thereby changing how the series represents the signal over time. This principle is essential in various applications, including audio and image processing, where signal manipulation is frequent. Understanding function symmetries is fundamental to simplifying the Fourier series.
A function f(t) is...
A function f(t) is...
125
Rotation of Asymmetric Top
804
By definition, a spherically symmetric body has the same moment of inertia about any axis passing through its center of mass. This situation changes if there is no spherical symmetry. Since most rigid bodies are not spherically symmetric, these require special treatment.
The relationship between the angular momentum of any rigid body and its angular velocity, both of which are vectors, involves the moment of inertia. The moment of inertia is a scalar quantity only for spherically symmetric...
The relationship between the angular momentum of any rigid body and its angular velocity, both of which are vectors, involves the moment of inertia. The moment of inertia is a scalar quantity only for spherically symmetric...
804
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
34
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
34
Problem-Solving
103
Effective problem-solving consists of two steps: 1. identifying the problem and 2. selecting the appropriate problem-solving strategy (i.e., a plan of action used to find a solution). Humans use four problem-solving strategies:
103
Stereoisomerism
11.7K
Isomerism in Complexes
Isomers are different chemical species that have the same chemical formula.
Transition metal complexes often exist as geometric isomers, in which the same atoms are connected through the same types of bonds but with differences in their orientation in space. Coordination complexes with two different ligands in the cis and trans positions from a ligand of interest form isomers. For example, the octahedral [Co(NH3)4Cl2]+ ion has two isomers (Figure 1) In the cis...
Isomers are different chemical species that have the same chemical formula.
Transition metal complexes often exist as geometric isomers, in which the same atoms are connected through the same types of bonds but with differences in their orientation in space. Coordination complexes with two different ligands in the cis and trans positions from a ligand of interest form isomers. For example, the octahedral [Co(NH3)4Cl2]+ ion has two isomers (Figure 1) In the cis...
11.7K


