目前，我正在学习遗传算法（个人兴趣，不是必须的），并遇到了一些我不熟悉或只是基本熟悉的主题，它们是：
- 搜索空间
- 函数的“极值”
我知道搜索空间是所有可能解决方案的集合，但我也想知道如何确定搜索空间的范围。此外，我想知道在函数中什么是“极值”，以及如何计算。
我知道我可能应该理解这些，但到目前为止，我只学过代数2和几何学，但我自己还涉足物理、矩阵/向量数学和数据结构，请原谅我如果看起来有些天真。
6个回答
5
通常，所有在项目集合中查找特定项目的算法都被称为搜索算法。当项目集合由数学函数定义（与存在于数据库中相对），它被称为搜索空间。
这类问题中最著名的之一是旅行商问题，该问题寻求一种算法，给定城市列表及其距离，找到只访问每个城市一次的最短路径。对于此问题，唯一的精确解决方案是检查所有可能的路线（即整个搜索空间），并找到最短的那一条（具有最小距离的路径，即搜索空间中的极值）。这样一个算法（称为穷举搜索）的最佳时间复杂度是指数级别的（尽管仍然可能存在更好的解决方案），这意味着最坏情况下运行时间随着城市数量的增加呈指数级增长。
这就是遗传算法发挥作用的地方。与其他启发式算法类似，遗传算法通过迭代改进候选解决方案来接近最优解，但不能保证实际找到最优解。
这种迭代方法存在一个问题，即算法很容易在尝试改进解决方案的过程中陷入局部极值，而不知道可能有更好的解决方案在更远的地方：
因此，总结如下：
- 穷举搜索 - 检查整个搜索空间（时间长） - 找到全局极值 - 启发式（例如遗传算法） - 检查部分搜索空间（时间短） - 找到局部极值
这类问题中最著名的之一是旅行商问题，该问题寻求一种算法，给定城市列表及其距离，找到只访问每个城市一次的最短路径。对于此问题，唯一的精确解决方案是检查所有可能的路线（即整个搜索空间），并找到最短的那一条（具有最小距离的路径，即搜索空间中的极值）。这样一个算法（称为穷举搜索）的最佳时间复杂度是指数级别的（尽管仍然可能存在更好的解决方案），这意味着最坏情况下运行时间随着城市数量的增加呈指数级增长。
这就是遗传算法发挥作用的地方。与其他启发式算法类似，遗传算法通过迭代改进候选解决方案来接近最优解，但不能保证实际找到最优解。
这种迭代方法存在一个问题，即算法很容易在尝试改进解决方案的过程中陷入局部极值，而不知道可能有更好的解决方案在更远的地方：
因此，总结如下：
- 穷举搜索 - 检查整个搜索空间（时间长） - 找到全局极值 - 启发式（例如遗传算法） - 检查部分搜索空间（时间短） - 找到局部极值
- vgru
2
遗传算法在调整到局部最优点上并不擅长。如果您想要找到全局最优点，至少应该能够接近或找到一种接近局部最优点的策略。最近已经开发了一些改进措施以更好地寻找局部最优解。
“用于从小波包分解中选择信息基函数的遗传算法，并应用于使用声发射进行腐蚀识别” http://gbiomed.kuleuven.be/english/research/50000666/50000669/50488669/neuro_research/neuro_research_mvanhulle/comp_pdf/Chemometrics.pdf
“用于从小波包分解中选择信息基函数的遗传算法，并应用于使用声发射进行腐蚀识别” http://gbiomed.kuleuven.be/english/research/50000666/50000669/50488669/neuro_research/neuro_research_mvanhulle/comp_pdf/Chemometrics.pdf
- user3116431
1
通常，“搜索空间”意味着你正在寻找什么类型的答案。例如，如果你正在编写一个遗传算法来构建桥梁、测试它们，然后再建造更多的桥梁，那么你要寻找的答案就是桥梁模型（以某种形式）。另一个例子是，如果你试图找到一个与一组样本输入在某些点上相符的函数，你可以尝试找到一个具有这个属性的多项式。在这种情况下，你的搜索空间可能是多项式。你可以通过限制项数、多项式的最高次数等方式使其更简单。因此，你可以指定你想要搜索的整数幂次在[-4, 4]范围内的多项式。在遗传算法中，搜索空间是你可以生成的可能解集合。在遗传算法中，你需要仔细限制你的搜索空间，以避免完全愚蠢的答案。在我的前任大学，一位物理学生编写了一个计算分子中原子最佳配置以具有低能量特性的GA程序：他们发现了一个几乎没有能量的好解决方案。不幸的是，他们的解决方案把所有的原子都放在了分子的正中心，这在物理上是不可能的 :-）。遗传算法真正磨练你的适应度函数的好解决方案，因此选择你的搜索空间非常重要，这样它就不会产生具有良好适应度但实际上是“不可能答案”的解决方案。
关于函数的“极值”。这只是函数取得最大值的点。在遗传算法方面，您希望找到解决问题的最佳方案。如果您正在建造一座桥梁，您要寻找最好的桥梁。在这种情况下，您有一个适应度函数，可以告诉您“这座桥梁可以承受80磅的重量”和“那座桥梁可以承受120磅的重量”，然后您寻找具有更高适应度值的解决方案。有些函数具有简单的极值：您可以使用简单的高中微积分找到多项式的极值。其他函数没有简单的方法来计算它们的极值。值得注意的是，高度非线性函数的极值可能很难找到。遗传算法通过巧妙的搜索技术寻找这些解决方案，先寻找高点，然后再找到其他点。值得注意的是，还有其他算法也可以做到这一点，尤其是山地攀登者。使遗传算法不同的是，如果您找到了局部最大值，其他类型的算法可能会被“卡住”，盲目地追求局部良好的解决方案，以至于他们永远看不到在搜索空间中更好的解决方案。还有其他方法可以使山地攀登者适应这种情况，例如模拟退火算法。
关于函数的“极值”。这只是函数取得最大值的点。在遗传算法方面，您希望找到解决问题的最佳方案。如果您正在建造一座桥梁，您要寻找最好的桥梁。在这种情况下，您有一个适应度函数，可以告诉您“这座桥梁可以承受80磅的重量”和“那座桥梁可以承受120磅的重量”，然后您寻找具有更高适应度值的解决方案。有些函数具有简单的极值：您可以使用简单的高中微积分找到多项式的极值。其他函数没有简单的方法来计算它们的极值。值得注意的是，高度非线性函数的极值可能很难找到。遗传算法通过巧妙的搜索技术寻找这些解决方案，先寻找高点，然后再找到其他点。值得注意的是，还有其他算法也可以做到这一点，尤其是山地攀登者。使遗传算法不同的是，如果您找到了局部最大值，其他类型的算法可能会被“卡住”，盲目地追求局部良好的解决方案，以至于他们永远看不到在搜索空间中更好的解决方案。还有其他方法可以使山地攀登者适应这种情况，例如模拟退火算法。
- Kristopher Micinski
1
选择范围通常需要对你要解决的问题具有直观的理解，对问题领域有一定的专业知识。实际上没有保证能够选择到最佳的范围的方法。
极值就是函数的最小值和最大值。
例如，如果你只是为了练习编程而编写一个遗传算法来寻找 f(x) = x^2 的最小值，那么你很清楚你的范围应该是+/-某个值，因为你已经知道答案在x=0处。但即使这样，你也不会使用遗传算法，因为你已经有了答案，即使你没有答案，你也可以使用微积分来找到答案。
遗传算法中的一个技巧是将一些现实世界的问题（通常是工程或科学问题）转化成某个可以被最小化或最大化的数学函数。但如果你这样做，你可能已经对解决方案的位置有了一些基本的概念，所以情况并不像听起来那么绝望。
- Novak
0
搜索空间简单来说就是所有可能解决方案的空间。如果你正在寻找最短的路径，那么搜索空间包括所有可能形成的路径。然而，要注意它并不是所有可行解决方案的空间！这取决于您的编码方式。如果您的编码方式是排列，那么搜索空间的大小为n！（阶乘）。如果您想要最小化某个函数，带有实值输入的搜索空间将受到实值输入超立方体的限制。它基本上是无限的，但当然受计算机精度的限制。
如果您对遗传算法感兴趣，也许您会对我们的软件进行试验。我们正在使用它来教授启发式优化课程。它具有GUI驱动和基于Windows操作系统，因此您可以立即开始使用。我们已经包括了一些问题，例如实值测试函数、旅行推销员、车辆路径规划等。这使您可以查看某个TSP的最佳解决方案如何随着各代的改进而逐渐提高。它还揭示了元启发式参数化问题，并让您找到更好的参数以更有效地解决问题。您可以在http://dev.heuristiclab.com处获取它。
- Andreas
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接