对于组合优化的概率提升技术
1Department of Computer Engineering, Faculty of Engineering, Chiang Mai University, Chiang Mai, Chang Wat Chiang Mai, Thailand.
PeerJ. Computer science
|December 9, 2024
概括
本研究为组合优化问题引入了一种更快的随机化策略,与确定性方法相比,大大提高了找到特定项目的效率.
科学领域:
- 计算机科学 计算机科学
- 算法分析 算法分析
- 离散的数学 离散的数学
背景情况:
- 组合优化问题通常需要从更大的n项集合中识别满足某些属性的k项的特定子集.
- 对于这些问题的确定性算法可能是低效的,需要对项目集进行广泛的验证.
- 随机方法也可能在计算上昂贵,验证成本随着设置大小的快速增长而迅速增加.
研究的目的:
- 介绍一种新的,更快的随机化策略来解决组合优化问题.
- 为了提高成功识别k项目的目标集的概率.
- 在实际场景中证明这种概率提升技术的适用性和优越性.
主要方法:
- 开发一种概率提升技术,以扩大选择所需的k项组的概率.
- 这种技术应用于三个不同的组合优化问题.
- 对新的随机算法与其决定性对应的比较分析.
主要成果:
- 拟议的随机化策略显著加快了找到k项目的目标集的过程.
- 增加概率的技术显然增加了成功识别的机会.
- 使用这种技术的算法在所有测试的应用中都比确定性算法表现出更高的性能.
结论:
- 概率提升技术提供了一种更有效的方法来解决一个类别的组合优化问题.
- 这种随机化策略为传统的决定性方法提供了一个强大的替代方案.
- 该方法在各种优化任务中显示了广泛的适用性和显著的性能增长.
相关概念视频
Binomial Probability Distribution
10.2K
A binomial distribution is a probability distribution for a procedure with a fixed number of trials, where each trial can have only two outcomes.
The outcomes of a binomial experiment fit a binomial probability distribution. A statistical experiment can be classified as a binomial experiment if the following conditions are met:
There are a fixed number of trials. Think of trials as repetitions of an experiment. The letter n denotes the number of trials.
There are only two possible outcomes,...
The outcomes of a binomial experiment fit a binomial probability distribution. A statistical experiment can be classified as a binomial experiment if the following conditions are met:
There are a fixed number of trials. Think of trials as repetitions of an experiment. The letter n denotes the number of trials.
There are only two possible outcomes,...
10.2K
Factorial Design
13.0K
Factorial Analysis is an experimental design that applies Analysis of Variance (ANOVA) statistical procedures to examine a change in a dependent variable due to more than one independent variable, also known as factors. Changes in worker productivity can be reasoned, for example, to be influenced by salary and other conditions, such as skill level. One way to test this hypothesis is by categorizing salary into three levels (low, moderate, and high) and skills sets into two levels (entry level...
13.0K
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
40
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...
40
Randomized Experiments
6.7K
The randomization process involves assigning study participants randomly to experimental or control groups based on their probability of being equally assigned. Randomization is meant to eliminate selection bias and balance known and unknown confounding factors so that the control group is similar to the treatment group as much as possible. A computer program and a random number generator can be used to assign participants to groups in a way that minimizes bias.
Simple randomization
Simple...
Simple randomization
Simple...
6.7K
Probability in Statistics
12.4K
Probability is the likelihood of an event occurring. The term event is defined as a collection of results of a procedure. An event is a simple event when an outcome cannot be divided into simpler parts.
An example of a simple event is a coin toss. The result of a coin toss is either a head or a tail. Here, head and tail are two simple events. These two simple events make up the sample space. Further, the probability of an event occurring falls within the range of 0 to 1. The probability of an...
An example of a simple event is a coin toss. The result of a coin toss is either a head or a tail. Here, head and tail are two simple events. These two simple events make up the sample space. Further, the probability of an event occurring falls within the range of 0 to 1. The probability of an...
12.4K
Decision Making: P-value Method
5.3K
The process of hypothesis testing based on the P-value method includes calculating the P- value using the sample data and interpreting it.
First, a specific claim about the population parameter is proposed. The claim is based on the research question and is stated in a simple form. Further, an opposing statement to the claim is also stated. These statements can act as null and alternative hypotheses: a null hypothesis would be a neutral statement while the alternative hypothesis can...
First, a specific claim about the population parameter is proposed. The claim is based on the research question and is stated in a simple form. Further, an opposing statement to the claim is also stated. These statements can act as null and alternative hypotheses: a null hypothesis would be a neutral statement while the alternative hypothesis can...
5.3K


