遗传算法：在非常基本的数学计算中找不到最优解
Genetic Algorithm: Optimal solution not found in very basic mathematical computation
我正在 C# WinForms 中实现遗传算法，以找到一个非常简单的数学方程式的最优解。 "simple" 这里的意思是等式必须具有这些性质：
- 只包含整数
- 等式的最终结果必须是小于 1001 的正数
- 允许最少 2 个变量，最多 7 个变量
- 每个变量的系数必须在 1 到 10 之间（包括下限和上限）
- 变量值从 0 - 500
- 只允许加法
我认为我可以用这样的方程达到最优解 "easy"，有人会说。然而，我总是只能得到一个非常接近最优解的解。为了评估解决方案是否最优，我使用以下公式：
f(x) = absolute((sum_of_all_variables) - equation_result)
例如，我有以下等式：
1a + 1b = 12
如果 a 是 2 并且 b 是 3，那么该个人的 f(x) 将是 abs(2 + 3 - 12) = 7。当 f(x) 达到 0 或者我生成了 50 代时，我的代码停止。
我目前的变异率是50%，我目前的交叉率是25%。使用的选择方法是轮盘赌 selection。变异方法是随机变异，即我只是在我的基因库中随机选择一个基因来改变它的值，每代最多改变50%的基因。
我的期望：代码产生了一个f(x)值为0的解决方案（个人），这是可用的最佳解决方案之一。
当前结果：代码产生了接近最优的解决方案。 我发现的一个常见模式是，接近最优的解决方案通常会在下一代中完全复制。
我现在对问题的猜测:
我认为这与我如何进行交叉有关。我做的交叉：
- 给每个人分配一个随机值
- 如果所述随机值小于交叉率，则保存该个体的数据以供以后用于交叉
- 收集所有待交叉个体后，我随机select每个个体一个交叉点
- 我觉得是这个问题: 我对待交叉个体列表中的第一个个体和第二个个体进行交叉，合并第一个个体的基因第二个要交叉的个体。然后，继续处理第二个人和第三个人，依此类推。最后一个人将与第一个人交叉。
然而，正如我所说，它不会产生最佳结果。是我的逻辑有问题还是遗传算法在这个简单的数学方程上的预期行为？
我正在使用的交叉方法（我正在使用 C# WinForms 在 ListView 中显示数据）：
private static void Crossover(List<Chromosome> chromosomes, Random seed)
{
List<int> crossoverChromosome = new List<int>();
for (int i = 0; i < 50; i++)
{
decimal randomedValue = RandomizeValue(seed);
if (randomedValue < Population.CrossoverRate) crossoverChromosome.Add(i);
}
for (int i = 0; i < crossoverChromosome.Count; i++)
{
int crossoverPoint = seed.Next(0, chromosomes[0].GeneValues.Count);
chromosomes[crossoverChromosome[i]] = chromosomes[crossoverChromosome[i]].MixChromosome(chromosomes[crossoverChromosome[(i + 1) % crossoverChromosome.Count]], crossoverPoint);
}
}
private static decimal RandomizeValue(Random seed)
{
return Math.Round((decimal)seed.NextDouble(), 5);
}
public Chromosome MixChromosome(Chromosome mixture, int crossoverPoint)
{
List<Gene> newGenes = new List<Gene>();
newGenes.AddRange(this.GetGenes(0, crossoverPoint));
newGenes.AddRange(mixture.GetGenes(crossoverPoint, this.GeneValues.Count));
return new Chromosome(DesiredValue, OperatorData, newGenes); // Ignore the DesiredValue and Operator Data, it has nothing to do with crossover
}
private List<Gene> GetGenes(int firstIndex, int lastIndex)
{
List<Gene> slicedGenes = new List<Gene>();
for (int i = firstIndex; i < lastIndex; i++)
{
slicedGenes.Add(Genes[i].CloneGene());
}
return slicedGenes;
}
我只对具有两个变量的方程进行了大量测试。
编辑
附加信息：
- 我不使用精英主义
- 初始种群规模 = 50 人
- 每代种群数量 = 50 人
10 次等式 1a + 1b = 10 在 50 代后产生以下最佳适应值：
- 第一次重播：24
- 第二次重播：11
- 第三次重播：42
- 第四次重播：13
- 第五次重新运行：5
- 第六次重播：19
- 第七次重播：7
- 第八次重播：1
- 第九次重播：6
- 第十次重播：29
- 每次重新运行的附加信息：在 50 代中产生最佳适应值的染色体 经常在种群中重复。 例如，在第八次重新运行时，我发现染色体上出现很多值
a 4 和值 b 7.
一个主要问题是（如您假设的那样）交叉。按照你描述的方式（或者至少据我所知）你对你的解决方案的每个个体进行交叉随机选择以生成下一个群体。
遗传算法背后的基本思想是达尔文适者生存，而不是随机生存（或繁殖）。
所以我认为问题在于每个个体都有相同的繁殖机会，这在遗传算法中没有多大意义。更好的解决方案是让导致接近正确结果的个体比不会导致良好结果的个体繁殖更多。否则它会类似于随机搜索。
通常情况下，随机选择个体进行繁殖仍然很有用，因为这将导致结果并不总是最好的，而是探索更大范围的搜索区域.
一种常见的方法是使用 fitness-proportional selection，它会根据适应度值随机选择个体进行繁殖。因此，具有高适应性的个体（在您的示例中导致结果接近正确结果的个体）具有更高的繁殖机会。
另一种常见的方法是 stochastically distributed selection，它也会选择随机个体进行繁殖，更好的个体有更高的机会，但这也将保证高于平均适应度的个体至少会繁殖一次。
Fitness-Proportional-Selection 的示例实现可能如下所示（不幸的是它是 java 代码，没有 C#，但它们非常相似...... ):
import java.util.concurrent.ThreadLocalRandom;
import com.google.common.annotations.VisibleForTesting;
/**
* A selector that randomly chooses pairs to be selected for reproduction based on their probability to be selected.
*/
public class FitnessProportionalSelector implements Selector {
/**
* Select pairs of parents (by index) that are combined to build the next generation.
*
* @param selectionProbability
* The probability to be selected for every DNA in the current population (sums up to 1).
*
* @param numPairs
* The number of pairs needed (or the number of individuals needed in the next generation).
*
* @return Returns an int-array of size [numPairs * 2] including the pairs that are to be combined to create the next population (a pair is on
* position [i, i+1] for i % 2 = 0).
*/
@Override
public int[] select(double[] selectionProbability, int numPairs) {
double[] summedProbabilities = Selector.toSummedProbabilities(selectionProbability);
int[] selectionPairs = new int[numPairs * 2];
double chosenProbability;
for (int i = 0; i < numPairs * 2; i++) {
chosenProbability = getRandomNumber();
selectionPairs[i] = Selector.getSelectedIndexByBisectionSearch(summedProbabilities, chosenProbability);
}
return selectionPairs;
}
@Override
public String toString() {
return "FitnessProportionalSelector []";
}
@VisibleForTesting
/*private*/ double getRandomNumber() {
return ThreadLocalRandom.current().nextDouble();
}
}
或 Stochastically-Distributed-Selection 的解决方案（也在 java 中）：
import java.util.concurrent.ThreadLocalRandom;
import com.google.common.annotations.VisibleForTesting;
/**
* A selector that chooses the pairs to be reproduced by a stochastically distributed selection method.
*
* The selection probability is proportional to the given probability, but it's ensured, that individuals with a probability above average are chosen
* at least once.
*/
public class StochasticallyDistributedSelector implements Selector {
/**
* Select pairs of parents (by index) that are combined to build the next generation.
*
* @param selectionProbability
* The probability to be selected for every DNA in the current population (sums up to 1).
*
* @param numPairs
* The number of pairs needed (or the number of individuals needed in the next generation).
*
* @return Returns an int-array of size [numPairs * 2] including the pairs that are to be combined to create the next population (a pair is on
* position [i, i+1] for i % 2 = 0).
*/
@Override
public int[] select(double[] selectionProbability, int numPairs) {
double[] summedProbability = Selector.toSummedProbabilities(selectionProbability);
int[] selectedPairs = new int[2 * numPairs];
double startPoint = getRandomNumber();
double addedAverage = 1d / (2d * numPairs);
double stochasticallySelectedProbability;
for (int i = 0; i < numPairs * 2; i++) {
//select the pairs stochastically
stochasticallySelectedProbability = startPoint + i * addedAverage;
stochasticallySelectedProbability %= 1;
selectedPairs[i] = Selector.getSelectedIndexByBisectionSearch(summedProbability, stochasticallySelectedProbability);
}
//shuffle the pairs to distribute them stochastically
shuffle(selectedPairs);
return selectedPairs;
}
@VisibleForTesting
/*private*/ void shuffle(int[] selectedPairs) {
//shuffle the selected pairs in place
int swapIndex;
int tmp;
for (int i = selectedPairs.length - 1; i > 0; i--) {
swapIndex = (int) (getRandomNumber() * (i + 1));
tmp = selectedPairs[i];
selectedPairs[i] = selectedPairs[swapIndex];
selectedPairs[swapIndex] = tmp;
}
}
@VisibleForTesting
/*private*/ double getRandomNumber() {
return ThreadLocalRandom.current().nextDouble();
}
@Override
public String toString() {
return "StochasticallyDistributedSelector []";
}
}
我从我为硕士论文创建的遗传优化器项目中获取了这些示例代码。如果你想看看它，你可以找到它 on my github account
一些进一步的改进:
- 尝试使用 mean square error 而不是绝对值 (f(x) = absolute((sum_of_all_variables) - equation_result))
- 使用选择压力是另一种选择合适个体进行繁殖（并使参数收敛）的好方法；如果需要示例，可以在包 genetic_optimizer.selection 的 github 项目中找到解决方案。
- elitism 在这里非常有用，不会丢失您已有的最佳解决方案（至少如果您不将其保留在人口中，请在计算后将其恢复为 return）
我正在 C# WinForms 中实现遗传算法，以找到一个非常简单的数学方程式的最优解。 "simple" 这里的意思是等式必须具有这些性质：
- 只包含整数
- 等式的最终结果必须是小于 1001 的正数
- 允许最少 2 个变量，最多 7 个变量
- 每个变量的系数必须在 1 到 10 之间（包括下限和上限）
- 变量值从 0 - 500
- 只允许加法
我认为我可以用这样的方程达到最优解 "easy"，有人会说。然而，我总是只能得到一个非常接近最优解的解。为了评估解决方案是否最优，我使用以下公式：
f(x) = absolute((sum_of_all_variables) - equation_result)
例如，我有以下等式：
1a + 1b = 12
如果 a 是 2 并且 b 是 3，那么该个人的 f(x) 将是 abs(2 + 3 - 12) = 7。当 f(x) 达到 0 或者我生成了 50 代时，我的代码停止。
我目前的变异率是50%，我目前的交叉率是25%。使用的选择方法是轮盘赌 selection。变异方法是随机变异，即我只是在我的基因库中随机选择一个基因来改变它的值，每代最多改变50%的基因。
我的期望：代码产生了一个f(x)值为0的解决方案（个人），这是可用的最佳解决方案之一。
当前结果：代码产生了接近最优的解决方案。 我发现的一个常见模式是，接近最优的解决方案通常会在下一代中完全复制。
我现在对问题的猜测:
我认为这与我如何进行交叉有关。我做的交叉：
- 给每个人分配一个随机值
- 如果所述随机值小于交叉率，则保存该个体的数据以供以后用于交叉
- 收集所有待交叉个体后，我随机select每个个体一个交叉点
- 我觉得是这个问题: 我对待交叉个体列表中的第一个个体和第二个个体进行交叉，合并第一个个体的基因第二个要交叉的个体。然后，继续处理第二个人和第三个人，依此类推。最后一个人将与第一个人交叉。
然而，正如我所说，它不会产生最佳结果。是我的逻辑有问题还是遗传算法在这个简单的数学方程上的预期行为？
我正在使用的交叉方法（我正在使用 C# WinForms 在 ListView 中显示数据）：
private static void Crossover(List<Chromosome> chromosomes, Random seed)
{
List<int> crossoverChromosome = new List<int>();
for (int i = 0; i < 50; i++)
{
decimal randomedValue = RandomizeValue(seed);
if (randomedValue < Population.CrossoverRate) crossoverChromosome.Add(i);
}
for (int i = 0; i < crossoverChromosome.Count; i++)
{
int crossoverPoint = seed.Next(0, chromosomes[0].GeneValues.Count);
chromosomes[crossoverChromosome[i]] = chromosomes[crossoverChromosome[i]].MixChromosome(chromosomes[crossoverChromosome[(i + 1) % crossoverChromosome.Count]], crossoverPoint);
}
}
private static decimal RandomizeValue(Random seed)
{
return Math.Round((decimal)seed.NextDouble(), 5);
}
public Chromosome MixChromosome(Chromosome mixture, int crossoverPoint)
{
List<Gene> newGenes = new List<Gene>();
newGenes.AddRange(this.GetGenes(0, crossoverPoint));
newGenes.AddRange(mixture.GetGenes(crossoverPoint, this.GeneValues.Count));
return new Chromosome(DesiredValue, OperatorData, newGenes); // Ignore the DesiredValue and Operator Data, it has nothing to do with crossover
}
private List<Gene> GetGenes(int firstIndex, int lastIndex)
{
List<Gene> slicedGenes = new List<Gene>();
for (int i = firstIndex; i < lastIndex; i++)
{
slicedGenes.Add(Genes[i].CloneGene());
}
return slicedGenes;
}
我只对具有两个变量的方程进行了大量测试。
编辑
附加信息：
- 我不使用精英主义
- 初始种群规模 = 50 人
- 每代种群数量 = 50 人
10 次等式 1a + 1b = 10 在 50 代后产生以下最佳适应值：
- 第一次重播：24
- 第二次重播：11
- 第三次重播：42
- 第四次重播：13
- 第五次重新运行：5
- 第六次重播：19
- 第七次重播：7
- 第八次重播：1
- 第九次重播：6
- 第十次重播：29
- 每次重新运行的附加信息：在 50 代中产生最佳适应值的染色体 经常在种群中重复。 例如，在第八次重新运行时，我发现染色体上出现很多值
a4 和值b7.
一个主要问题是（如您假设的那样）交叉。按照你描述的方式（或者至少据我所知）你对你的解决方案的每个个体进行交叉随机选择以生成下一个群体。
遗传算法背后的基本思想是达尔文适者生存，而不是随机生存（或繁殖）。
所以我认为问题在于每个个体都有相同的繁殖机会，这在遗传算法中没有多大意义。更好的解决方案是让导致接近正确结果的个体比不会导致良好结果的个体繁殖更多。否则它会类似于随机搜索。
通常情况下，随机选择个体进行繁殖仍然很有用，因为这将导致结果并不总是最好的，而是探索更大范围的搜索区域.
一种常见的方法是使用 fitness-proportional selection，它会根据适应度值随机选择个体进行繁殖。因此，具有高适应性的个体（在您的示例中导致结果接近正确结果的个体）具有更高的繁殖机会。
另一种常见的方法是 stochastically distributed selection，它也会选择随机个体进行繁殖，更好的个体有更高的机会，但这也将保证高于平均适应度的个体至少会繁殖一次。
Fitness-Proportional-Selection 的示例实现可能如下所示（不幸的是它是 java 代码，没有 C#，但它们非常相似...... ):
import java.util.concurrent.ThreadLocalRandom;
import com.google.common.annotations.VisibleForTesting;
/**
* A selector that randomly chooses pairs to be selected for reproduction based on their probability to be selected.
*/
public class FitnessProportionalSelector implements Selector {
/**
* Select pairs of parents (by index) that are combined to build the next generation.
*
* @param selectionProbability
* The probability to be selected for every DNA in the current population (sums up to 1).
*
* @param numPairs
* The number of pairs needed (or the number of individuals needed in the next generation).
*
* @return Returns an int-array of size [numPairs * 2] including the pairs that are to be combined to create the next population (a pair is on
* position [i, i+1] for i % 2 = 0).
*/
@Override
public int[] select(double[] selectionProbability, int numPairs) {
double[] summedProbabilities = Selector.toSummedProbabilities(selectionProbability);
int[] selectionPairs = new int[numPairs * 2];
double chosenProbability;
for (int i = 0; i < numPairs * 2; i++) {
chosenProbability = getRandomNumber();
selectionPairs[i] = Selector.getSelectedIndexByBisectionSearch(summedProbabilities, chosenProbability);
}
return selectionPairs;
}
@Override
public String toString() {
return "FitnessProportionalSelector []";
}
@VisibleForTesting
/*private*/ double getRandomNumber() {
return ThreadLocalRandom.current().nextDouble();
}
}
或 Stochastically-Distributed-Selection 的解决方案（也在 java 中）：
import java.util.concurrent.ThreadLocalRandom;
import com.google.common.annotations.VisibleForTesting;
/**
* A selector that chooses the pairs to be reproduced by a stochastically distributed selection method.
*
* The selection probability is proportional to the given probability, but it's ensured, that individuals with a probability above average are chosen
* at least once.
*/
public class StochasticallyDistributedSelector implements Selector {
/**
* Select pairs of parents (by index) that are combined to build the next generation.
*
* @param selectionProbability
* The probability to be selected for every DNA in the current population (sums up to 1).
*
* @param numPairs
* The number of pairs needed (or the number of individuals needed in the next generation).
*
* @return Returns an int-array of size [numPairs * 2] including the pairs that are to be combined to create the next population (a pair is on
* position [i, i+1] for i % 2 = 0).
*/
@Override
public int[] select(double[] selectionProbability, int numPairs) {
double[] summedProbability = Selector.toSummedProbabilities(selectionProbability);
int[] selectedPairs = new int[2 * numPairs];
double startPoint = getRandomNumber();
double addedAverage = 1d / (2d * numPairs);
double stochasticallySelectedProbability;
for (int i = 0; i < numPairs * 2; i++) {
//select the pairs stochastically
stochasticallySelectedProbability = startPoint + i * addedAverage;
stochasticallySelectedProbability %= 1;
selectedPairs[i] = Selector.getSelectedIndexByBisectionSearch(summedProbability, stochasticallySelectedProbability);
}
//shuffle the pairs to distribute them stochastically
shuffle(selectedPairs);
return selectedPairs;
}
@VisibleForTesting
/*private*/ void shuffle(int[] selectedPairs) {
//shuffle the selected pairs in place
int swapIndex;
int tmp;
for (int i = selectedPairs.length - 1; i > 0; i--) {
swapIndex = (int) (getRandomNumber() * (i + 1));
tmp = selectedPairs[i];
selectedPairs[i] = selectedPairs[swapIndex];
selectedPairs[swapIndex] = tmp;
}
}
@VisibleForTesting
/*private*/ double getRandomNumber() {
return ThreadLocalRandom.current().nextDouble();
}
@Override
public String toString() {
return "StochasticallyDistributedSelector []";
}
}
我从我为硕士论文创建的遗传优化器项目中获取了这些示例代码。如果你想看看它，你可以找到它 on my github account
一些进一步的改进:
- 尝试使用 mean square error 而不是绝对值 (f(x) = absolute((sum_of_all_variables) - equation_result))
- 使用选择压力是另一种选择合适个体进行繁殖（并使参数收敛）的好方法；如果需要示例，可以在包 genetic_optimizer.selection 的 github 项目中找到解决方案。
- elitism 在这里非常有用，不会丢失您已有的最佳解决方案（至少如果您不将其保留在人口中，请在计算后将其恢复为 return）