哈希函数是否与进化算法的创始假设相矛盾？

Question

1. 进化算法使用适应度函数来选择跨代的生存候选者("适者生存").我相信所有适应度函数都假设候选者的值越接近期望值,它们的输入("关键点")必须越接近所需的输入.

2. 加密散列函数具有"生成具有给定散列的消息不可行"的属性.我理解这意味着值的"接近度"与键的"接近度"之间几乎没有相关性.

将这两者放在一起,并不意味着"适者生存"假设对于加密哈希函数是错误的吗？这意味着,如果您想使用进化算法来尝试找出加密哈希值的反向,那么适应度函数会将您推向错误的方向.值的"接近度"和键的"接近度"之间的相关性是进化算法的先决条件吗？

Answer 1

是的,根据所有三个(良好)加密哈希函数的输出,构建一个始终告诉您值A比目标B更接近目标的适应度函数几乎是不可能的.这是你提到的财产.因此,进化算法无法加速反转加密哈希函数的平均情况.然而,这不应该是一个惊喜:所述属性仅在第一时间有用,因为它精确地打破了进化算法的方法(通过查看散列值相似性来加速逆转).

推广这一点,进化算法(例如,依赖于启发式指导其搜索的所有其他算法,例如A*)仅在您可以定义有意义的适应度函数(启发式)^†时才有用.显然,有可能构造不允许这样的问题(例如,通过提供太少的信息),并且完全可以认为存在一些具有相同问题的更多真实应用程序.进化算法并不能治愈癌症,但这并不奇怪(没有任何意义,否则我们会转向另一种比喻).

_{^†在旁注中,此适应度函数不必接近任何特定值,存在适应性无限增长的许多问题,例如,当优化代码以获得性能时,适应度可以是每秒的操作次数.}