问题标签 [hill-climbing]

我想知道是否有人知道提供 2D 模型搜索空间来测试 GA 的来源。我相信我不久前读到有一堆标准搜索空间，通常在评估这些类型的算法时使用。

如果不是，是否只是每次自己随机生成这些数据的情况？

编辑：从上方和侧面查看。

具体来说，最速爬山、随机爬山和模拟退火。广义时间复杂度也可以。谢谢。

I'm having trouble generating neighbors for implementing hill climbing algorithms.

Here's the code I'm currently working with.

The problem I'm having is that each new board I generate saves the last move, I'd like each neighbor board to have a step size of one. Here is the (wrong) output:

Here is the output I'd like.

As you can see, it is saving the move from the previous step. Can anybody help?

我想实现应用爬山算法的机器人路径规划程序。

我了解爬山算法的基础知识，但我想不出任何想法！

我也用谷歌搜索了爬山算法，但我找不到任何关于使用爬山算法进行机器人路径规划的信息。

使用 Bresenham 的线算法很难实现开始功能、选择邻居功能和检查/绘制路径。

我一直在关注这本电子书，但我被他们的一个自我检查问题困住了，这个问题是这样的：

自检

这是一个自我检查，真正涵盖了到目前为止的所有内容。你可能听说过无限猴子定理？该定理指出，一只猴子在打字机键盘上随机敲击无限时间的键几乎肯定会键入给定的文本，例如威廉·莎士比亚的全集。好吧，假设我们用 Python 函数替换猴子。你认为一个 Python 函数只生成一个莎士比亚的句子需要多长时间？我们要拍摄的句子是：“我认为它就像一只黄鼠狼”</p>

你不想在浏览器中运行这个，所以启动你最喜欢的 Python IDE。我们将模拟这种情况的方法是编写一个函数，该函数通过从字母表中的 26 个字母加上空格中选择随机字母来生成一个 27 个字符长的字符串。我们将编写另一个函数，通过将随机生成的字符串与目标进行比较，对每个生成的字符串进行评分。

第三个函数将重复调用 generate 和 score，然后如果 100% 的字母是正确的，我们就完成了。如果字母不正确，那么我们将生成一个全新的字符串。为了更容易跟踪程序的进度，第三个函数应该打印出迄今为止生成的最佳字符串及其每 1000 次尝试的得分。

自检挑战

看看您是否可以通过保持正确的字母并仅修改迄今为止最好的字符串中的一个字符来改进自检中的程序。这是“爬山”算法中的一种算法，也就是说，我们只保留比前一个更好的结果。

我编写了一些代码，使用生成的字符串和所需字符串之间的 Levenshtein 距离来完成这个挑战的第一部分。

我不知道如何在 TODO 中生成更好的字符串 - 在迭代之前使用最好的字符串和给定的方法。

tl;dr： 我如何编写一个爬山算法，使用 Levenshtein 距离作为其启发式算法，直到它生成某个字符串？请概述过程。

我在 7D 空间中有以下函数（表示 x=(x1,x2,x3,x4,x5,x6,x7)），我想在 matlab 中通过爬山找到这个函数的最小值。

我发现这个链接很有用，但我不知道如何在 Matlab 中实现我的功能。

更新：

我实现了下面的代码，但我真的不知道它是否正确。

我正在编写一个 python 脚本来破解一个 playfair 密码，只有密文。首先，我生成大约 30-100 个解密密钥并在密文上运行它们，根据它的有向图频率对每个密钥进行排名。到下一代“/迭代”，我复制得分最高的那些。然后它们被变异（字母在 5x5 网格中交换位置）并重新添加到下一次迭代中，再次进行排名，依此类推。

我注意到脚本经常找到一个局部最大值——一个给出类似分布的键，但不是真正的交易。我认为解决该问题的方法是为密钥的数量引入更多变化（在脚本结束时，它们几乎都相同）。

我试图通过向每一代添加几个完全随机的密钥来实现它，但它们几乎立即被淘汰。有什么更好的方法呢？我也想过模拟退火之类的策略，但不知道它们会有多大帮助。

编辑：按要求提供示例密文（关键：playfair 示例）

as el ir ul vine uz qk dm kz qe ca qe tb qc pv zb md nv om lo gv qo od er qc zg pv vk ov 或 iw zg ro nz ge ro af yp qe zi lo rk pr ad xl dl ix cl qr rk dq vu sa zb xv qe ho dm dn ok eb xe do bm iz kd de as kv ef kc rd lv om dm vy km ur et xe aq zb xe tx om rt gh rk hc fg mk py dr qo af zs xv nv ac df ad dl yr do bm ef pm zs lo ce yl ai ca nv ca fy wi dm ov ne tx zb bm kn ul bn ar km uz fo ka ro do gp lo kv dm ml qe zi lo rk pr ad xl tx zb le nv oc py dr lo ca le dx xa mo pr oi yp en dy oc dk zb as kv ix ol pr dr oq pb dr gb eo ak vg xe do df re zb pv nl cr do ya an ad iu dm re dm eo qm dm am pu ad xl nl er nv kz qn oq yg df pb uz fo ya ay dk vu lo gd ex ip ya bp up xv yf nv vk pz dm vq vo vk pr kz ro

I am doing an algorithm for a hill climbing search, and for some reason, the stack that I'm supposed to have at the end of the loop seems to be overwritten with the last iteration of the state that the loop generated.

Basically, here is a rundown of what this algorithm is doing:

This algorithm is being used to solve the N queens problem. All of the underlying code with the state class works perfectly fine. With this algorithm, it iterates through all possible successor states of the current state. It stores the next successor state within the neighborState variable (as seen in the code below). If a state cost is less than the current cost, it will add the neighborState with that new low cost into a neighborNode and store that into a stack. Any new min values that get detected will wipe the stack and insert the new lowest minimum nodes.

I've done a few tests within the loop to see what the outputs look like from what is being inserted into the stack. All of them seem to be correctly outputting. However, when I am outside the loop and check the stack, all the nodes in the stack have their states replaced to the last generated successor state from the loop. It seems that in every node that has the neighborState stored, each time the neighborState updates, it changes all the node neighborState values as well. I just can't seem to find a way to fix this though.

Some advice as to how I can fix this would be greatly appreciated!

*Note: Disregard the code after the for loop starting at the if statement, as it is still incomplete.

Here is the code:

}

}

有没有办法（仅使用 R 编程语言）使用自定义学习函数（而不是反向传播）来实现 ANN 算法？我测试过的所有 R 包（nnet、neuralnet、AMORE）似乎都有学习函数来训练权重的选项，但它们似乎都没有包含插入自定义函数的可选性（例如，爬山作为示例）。

我更喜欢使用 R 而不是另一种语言，所以如果有人知道任何可以提供帮助的软件包，请告诉我。

谢谢！

嗨，我正在尝试编写一些简单的代码来使用随机突变爬山来解决旅行商问题。我已经创建了一个 Tour 类：-

我的 RMHC 方法如下所示：-

我遇到的问题是，当我在 RMHC 中调用我的 smallChange 方法时，它似乎改变了旧解决方案和新解决方案的 Tour。我在一个 48 大小的数据集上运行了几次迭代，得到了以下输出：-