2

我编写了一个遗传算法，为了优化它的性能，我决定对个体的适应度测试进行并行化。为了了解这对我的算法产生了什么样的变化，我重新进行了我在并行化之前所做的测试运行，在该运行中我测试了 GA 针对不断增长的人口规模的性能。

GA 的并行版本实际上比原始版本花费了大约 50% 的时间。我意识到有时并行化的开销实际上可能比它节省的时间更多，但我怀疑这是否应该适用于这种情况——我的适应性测试正在寻找 Sheckel 的 Foxholes 函数的全局最小值（http://extreme.adorio -research.org/download/mvf/html/node51.html），我的人口规模从 10 到 1000 不等。我希望在并行执行 1000 次 sheckel 散兵坑时，节省的时间将大大超过并行化的开销。

所以我的问题是：为什么并行化会减慢算法的速度（并且如此显着）？

作为记录，我正在使用 Java 进行编码，并且正在使用 CountDownLatch 进行并行化，该 CountDownLatch 在继续之前等待所有线程（适应性测试）执行。

4

3 回答 3

3

根据您的评论，您似乎在做相当合理的事情，除了线程数。但是你提到你正在使用 CountDownLatch 让我思考......

我强烈建议您使用 an 来代替您自己的代码ExecutorService/Executors进行并行化。将你的类设为 a Callable，创建一堆，然后调用 invokeAll()。这样，训练有素（不确定他们是否高薪）的专家完成了大部分编码工作。

有了Executors，就很容易控制最大线程数。您可以调用Runtime.availableProcessors()以了解一次运行多少个线程，然后进行一些测试和调整。

编辑：刚刚发布了将算法转换为使用 ExecutorService 的介绍。享受，并欢迎评论/反馈。

于 2012-06-14T23:01:21.820 回答
1

好的，答案是它并没有像你想象的那样并行化。问题是“为什么？” 不看代码就很难得到答案。但是有一些明显的地方可以看：

  • 确保（你会讨厌这个）你为 Thread 使用了正确的入口点。保证您的线程将序列化并且不告诉您任何事情的一种方法是调用run()方法而不是start()方法。这听起来很傻，但我已经被这个咬了。

  • 使用例如 jconsole 确保线程完全同时运行。如果没有，你有一个意想不到的锁定某事。

  • 检查您同步的内容。检查您正在使用的集合类。其中一些根本不是线程安全的，其中一些是线程安全的，因为它们具有内部同步。在线程之间共享的任何 Collection 类都可能是不法之徒。

  • 如果没有任何结果，请与同事一起在纸上完成代码执行并手写出线程。

于 2012-06-14T19:25:39.990 回答
1

所以我弄清楚了问题所在——我曾假设我的体能测试花费的时间足够长，以至于并行化是值得的，但事实并非如此。我填充了适应度测试，人为地延长了它（它只是我用来监控 GA 性能的测试适应度测试），我现在看到执行时间存在显着差异 - 现在人口规模的增长导致将执行时间延长 1000 秒，而不是 10 秒。我应该指出，这是在实施 Executor 之前，正如我们所建议的那样。

感谢大家的帮助！

于 2012-06-16T02:58:46.187 回答