反向学习模型及其在离散空间中的应用研究

Diverse forms of opposition are already existent virtually everywhere around us, and sometimes we apply the opposition concept in our regular life unconsciously. The idea of opposition-based learning is approved more and more by the academic and industry world. However, the further enrichment and improvement of related concepts are ignored by some researchers frequently, the interaction mechanism of contradictions is not clear yet, and the theoretical basis for opposition-based learning is also very weak. These factors have seriously discouraged its applications in real world. Firstly, the basic properties of opposition-based learning are summarized, and then a uniform model is built to more meet human cognitive ability. Secondly, some unique performance evaluation indices are proposed based on the features of opposition-based learning, the properties, such as convergence, stability and diversity, of novel algorithms are proved by mathematics, and the dialectical relationships of performance promotion and cost are discussed carefully. As a result, the theoretical framework of opposition-based learning can be established perfectly. With the help of the same algorithm platform, the performance of opposition-based soft computing is evaluated to show the technical characteristics of different models of opposition-based learning. Lastly, as shown by graph coloring and TSP problems, the models of opposition-based learning are applied successfully in engineering optimization and scientific computing. Especially, we try to solve some technical problems, such as how to define and how to evaluate the opposition-based solutions in discrete domain. Then the opposition-based learning is extended to a new technology or idea of algorithm design.

在客观世界中，广泛存在着不同表现形式的反向概念，人们在日常生活中也会无意识地应用到它。反向学习的思想逐步得到学术界和工业界的认可。然而，研究者忽略了概念本身的丰富和提升，而且矛盾双方相互作用的机理尚不明晰，理论基础比较薄弱，这些因素严重制约了反向学习模型的实际应用。本项目，首先凝练反向学习的基本属性，建立更加符合人类认知的统一的反向学习模型。然后，基于反向学习模型的特殊性，提出若干有自身特色的性能评价指标，论证新算法的收敛性、稳定性、多样性等特性，讨论性能提升与所付出代价之间的辩证关系，初步构建反向学习模型的理论框架。依托公共算法平台，评估基于反向学习软计算的性能，彰显不同反向学习模型的技术特征。最后，以图着色和TSP问题为例，探讨在工程优化和科学计算领域应用反向学习模型的可行性，着力解决在离散空间中，科学定义和评价反向解这一技术瓶颈。在此基础上，将其拓展为一种新的算法设计的技术或思想。

反向学习逐渐发展成为人工智能的一个独立方向，得到学术界和工业界的普遍认可。我们系统梳理了反向学习模型的研究现状，深入分析了主流反向学习模型的技术特征，结合团队近年来工作和研究的客观条件，最终确定了本项目的研究内容，并取得了一系列研究成果。.在理论探索方面，以新颖的评价函数为基础，提出基于中心的反向学习策略，并探讨评价各种反向学习策略的通用方法，初步构建了统一的反向学习模型。首先，从理论上讲，基于中心的反向学习策略得到的反向解以及相应的候选解，距离最优解的平均距离最小。理论分析和仿真结果均表明，该反向学习策略具有较优的局部搜索能力。其次，分别给出计算该评价函数的精确方法（一维空间）和近似方法（高维空间）。通过比较该评价函数的数学期望，能够方便地评价各种反向学习策略的性能优劣。.在算法设计方面，提出新的反向路径的定义方式，提高求解大规模旅行商问题的效率，并探讨各种改进措施对于算法性能的影响。新的反向路径能够同时考虑候选路径的节点次序和相邻节点间距离，使得反向路径与原路径距离当前最优解的距离基本相当。仿真结果表明，新算法表现优异，且该良好的性能完全归功于新颖的反向路径的定义方式。鉴于新算法收敛速度较慢的缺陷，我们还探讨了种群初始化、交叉操作、局部优化操作、贪婪算法等改进措施，并确定了一种较理想的组合措施。.在工程应用方面，以函数优化和选择性维修问题为例，探讨反向学习模型在科学计算和工程优化等领域应用的可行性和有效性，并尝试将其扩展为一种算法策略。首先，构建反向回溯搜索算法的基本框架，展现出反向学习模型的普适性。仿真结果表明，反向个体的利用率与性能改善的幅度之间存在一定的正相关性。其次，构建基于经济相关性的多状态系统选择性维修问题的数学模型，利用反向差分进化算法求解该复杂的离散优化问题，能够在合理的时间内搜索到最优解，且算法鲁棒性较好。