用于离散霍普菲尔德神经网络中B型随机2-可满足性问题的自适应精英主义选举算法
《Neurocomputing》:Adaptive elitism election algorithm for b-type random 2-satisfiability in discrete hopfield neural network
【字体:
大
中
小
】
时间:2026年05月03日
来源:Neurocomputing 6.5
编辑推荐:
杨彬彬|李国祥|Mohd Shareduwan Mohd Kasihmuddin|Nurul Atiqah Romli|余宝荣|曹兆勤|郭月玲|甘玉健
中国-东盟统计研究所,广西财经大学,南宁,530003,中国
**摘要**
将元启发式算法引入非系统性逻辑的主要目
杨彬彬|李国祥|Mohd Shareduwan Mohd Kasihmuddin|Nurul Atiqah Romli|余宝荣|曹兆勤|郭月玲|甘玉健
中国-东盟统计研究所,广西财经大学,南宁,530003,中国
**摘要**
将元启发式算法引入非系统性逻辑的主要目标是最小化成本函数。然而,关于这些算法对含有冗余文字的逻辑中成本函数影响的研究有限。为了解决这一差距并提高元启发式算法在非系统性逻辑中的效率,本研究提出了一种改进的选举算法变体,该算法嵌入了基于K-模式的党派初始化和自适应精英策略。该算法应用于离散Hopfield神经网络中B型随机2-可满足性逻辑的学习阶段,以提高学习效率。与八种最先进的元启发式算法相比,所提出的算法平均迭代次数减少了约85.84%,并且全局最小解的识别能力提高了约66.23%。实验结果表明,该算法显著增强了全局搜索能力,提高了学习阶段的效率,并增加了全局最小解的数量和多样性。优化学习阶段不仅加快了模型收敛速度,还通过增加全局最小解的数量和多样性提高了鲁棒性。
**引言**
可满足性逻辑(SAT)在人工智能中占据基础性地位。SAT解决的是一个布尔公式是否可以通过对其文字至少分配一个真值来满足的问题[1]。作为第一个被证明是NP完全问题的逻辑公式,SAT成为包括人工智能[2]、自动推理[3]和模式识别[4]在内的多个领域的基石。基于这一核心地位,持续的研究致力于开发新的表示方法和计算框架,以扩展SAT的理论深度和实际应用范围。在这种背景下,最近将SAT逻辑嵌入离散Hopfield神经网络(DHNN)引起了广泛关注,为推进神经网络理论提供了新的视角。为了有效地将SAT整合到神经网络中,[5]提出了一种方法,将SAT逻辑规则作为符号指令嵌入DHNN的突触连接中。在这个框架中,逻辑文字对应于神经元,而突触权重是通过将逻辑规则导出的成本函数与李雅普诺夫能量函数进行比较来确定的。在此基础上,DHNN整合了系统规则(如2-可满足性(2SAT)[14]以及后来的非系统变体,包括随机2SAT(RAN2SAT)[6]、加权随机2-可满足性(r2SAT)[7]和S型随机2SAT[8],从而增强了处理复杂任务的灵活性,并相应地扩展了神经元状态空间和应用范围。尽管有这些贡献,但将逻辑形式限制为非冗余子句限制了DHNN中对重叠知识的表示。[9]通过将B型随机2-可满足性(BRAN2SAT)嵌入DHNN形成了DHNN-BR2SAT,其中冗余的二阶子句多样化了突触连接,并在检索过程中实现了自适应权重更新。然而,随着神经元数量的增加,学习性能仍然有限。
DHNN的学习阶段对于确保有效的检索阶段至关重要,因为未满足的逻辑规则可能会阻止最优突触权重的识别,并使网络陷入局部最小值。先前的研究探索了元启发式算法来改进这一阶段。例如,[10]将遗传算法(GA)引入DHNN中的K-SAT,通过交叉和变异优化了神经元适应性,显著提高了收敛速度。[11]提出了一种混合变异禁忌搜索算法用于PRO2SAT模型,结合了GA变异操作符和禁忌搜索,从而提高了全局搜索能力和收敛速度。同样,[12]开发了二进制蚁群优化算法(BOSACO),提高了学习效率,并实现了100%的全局解发现率。此外,[13]将混合差分进化算法和群体变异集成到DHNN中,改进了学习和检索阶段,并实现了单次迭代中的收敛。尽管有这些进展,但在DHNN中对含有冗余文字的非系统性SAT的元启发式算法仍然研究不足,需要进一步的研究和优化。
选举算法(EA)以其强大的结构表达能力和多样的操作机制而闻名,能够在离散优化问题中实现有效的全局搜索。最初由[15]为组合优化提出,EA模拟了总统选举过程,其中种群被划分为不同的党派,并根据适应性选择代表。这种基于党派的搜索过程允许不同的群体并行探索解空间,适用于离散子句适应性优化。由于其基于党派的组织和诸如广告和联盟等社会政治操作符,EA已被应用于各种离散优化问题,特别是在DHNN中SAT的学习阶段与离散双极搜索特别兼容。例如,[16]在DHNN中的RAN3SAT学习阶段应用了EA,使用正面和负面广告以及联盟形成等操作符来提高神经元适应性。该算法在学习过程中达到了全局最优解,从而提高了检索性能。然而,EA依赖于随机党派分配且缺乏精英策略,导致初始解次优、收敛速度慢以及局部最优解的风险增加。改进这些方面对于提高EA的鲁棒性和有效性至关重要。
为了解决这些限制,提出了一种称为具有K-模式聚类的自适应精英选举算法(AEAKM)的改进变体,以改进DHNN-BR2SAT中的子句适应性优化。K-模式聚类[17]与自适应精英策略[18]相结合。初始种群在汉明空间中被聚类以形成同质的党派,从而减少随机党派分配引起的无效探索。然后应用精英调度来保留高质量的代表并稳定收敛轨迹。具有K-模式聚类的自适应精英选举算法被视为针对问题的选举算法的增强版本。这一概念性的贡献在于将这两种机制与DHNN学习中的离散双极状态空间的基于党派的操作符结构耦合起来。这种设计的动机是BRAN2SAT中的冗余子句增加了景观的崎岖性,加剧了非精英选择的弱点。所提出模型的关键贡献如下:
(i) 提出了一种具有K-模式聚类的改进自适应选举算法。该算法将K-模式聚类技术与新设计的自适应精英策略相结合。使用K-模式聚类对种群进行划分以提高搜索效率。同时,自适应精英策略根据种群的进化状态动态调整精英保留策略,从而在探索和利用之间取得更好的平衡,提高全局搜索能力和鲁棒性。
(ii) 在DHNN-BR2SAT模型的学习阶段应用了具有K-模式聚类的改进选举算法。该算法显著提高了定位对应于B型随机2-可满足性逻辑的最优神经元状态的能力,从而使网络能够有效地确定最优突触权重。
(iii) 在学习和检索阶段将所提出的模型与其他最先进方法的性能进行比较。所有模型都使用多种指标进行评估,包括学习误差、能量曲线、解的变体以及相似性分析。
本文的其余部分结构如下:第2节介绍了所提出改进的理论动机和设计理由。第3节详细介绍了离散Hopfield神经网络中B型随机2-可满足性的实现。第4节介绍了用于学习阶段的具有K-模式聚类的改进选举算法。第5节概述了仿真设置、性能指标、基线方法和其他实现细节。第6节使用各种评估指标将所提出的学习模型与其他先进算法进行了比较。最后,第7节总结了研究并讨论了潜在的未来研究方向。
**章节摘要**
**动机**
本节从问题特征和算法机制的角度阐述了将AEAKM引入DHNN-BR2SAT学习阶段的必要性。在这个阶段,BRAN2SAT必须识别在高维双极离散空间内具有一致解释的神经元状态。冗余的二阶子句的存在增加了约束重叠和耦合,使得成本函数景观更加崎岖,从而增加了局部最优解的可能性。
**DHNN中的B型随机2-可满足性**
BRAN2SAT被采用作为调节DHNN中神经元连接的逻辑表示。与[6]的工作不同,BRAN2SAT结合了冗余的二阶子句和非冗余的一阶和二阶子句,为神经表示提供了更丰富的子句结构。
**选举算法**
选举算法(EA)是一种基于种群的元启发式算法,模拟了选举过程中的竞争、信息传播和联盟形成。在每次迭代中,种群被划分为不同的党派,并通过广告和联盟操作符进行更新,逐步提高解决方案的质量。
**实验设置**
本节描述了用于评估DHNN-BR2SAT框架中AEAKM的实验设置,包括整体设置、基线算法、计算环境、评估指标、统计测试以及敏感性和消融分析的设置。
**结果与讨论**
本节评估了在不同神经元大小下AEAKM与八种元启发式基线的性能。讨论重点关注四个方面:学习效率和计算成本、学习过程中的收敛行为、达到全局最小状态的能力以及所得全局解的多样性。为简洁起见,AEAKM被表示为AEAKM,而其余的DHNN-BR2SAT变体则以其相应的算法名称表示。
**结论**
本研究将一种称为AEAKM的改进自适应选举算法与K-模式聚类集成到DHNN-BR2SAT模型中,并将其与八种代表性的元启发式方法(即GA、QACO、PSO、ABC、SA、EDA和QLGA)进行了比较。比较涵盖了学习阶段、检索阶段、相似性分析、超参数敏感性分析和消融研究,所有模型都使用多种评估指标进行了定量评估。
**未引用的参考文献**
[21], [24], [33], [34], [35], [36], [37], [38], [39]
**作者贡献声明**
杨彬彬:写作——审阅与编辑、原始草稿撰写、可视化、方法论。
李国祥:可视化、数据整理。
Mohd Shareduwan Mohd Kasihmuddin:监督。
Nurul Atiqah Romli:调查、形式分析。
余宝荣:写作——审阅与编辑、验证。
曹兆勤:写作——审阅与编辑。
郭月玲:可视化、验证。
甘玉健:监督、项目管理、方法论。
**利益冲突声明**
作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。
**致谢**
作者感谢匿名审稿人的宝贵评论和建议。本工作得到了广西大学中青年教师研究能力提升项目(#2023KY1293)的支持和资助。
杨彬彬在中国南宁师范大学获得了学士和硕士学位,目前正在马来西亚科学大学(USM)攻读博士学位。她的当前研究兴趣包括元启发式方法、神经网络、人工智能、布尔逻辑和数据挖掘。
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号