进化算法和量子计算在优化问题中应用研究

摘要

优化问题是从众多备选方案中选择最优的方案以达到时间、工程量、经济等方面的最优化。传统的优化问题主要是基于数值计算的方法来求解各种复杂工程优化应用问题，但基于数值计算的方法对数学建模要求较高，比如目标函数可微分、解的区域是连通的等，这使得大多数复杂工程优化问题难以解决。随着计算机技术的高速发展以及优化算法的进步，各种优化问题的理论及实际应用发展迅速。
　　 伴随着计算机技术发展，部分超大规模的优化问题得以解决，优化问题理论和方法在工程设计、生产管理、运营调度得到广泛应用，成为一门活跃的学科。本文通过对进化算法和量子计算的深入研究与探索，针对背包问题、函数优化问题以及具体的应用，研究改进新的算法，进行算法性能的理论分析，具体的研究内容包括：
　　 (1)自适应柯西进化规划在优化问题中应用研究
　　 经典进化规划CEP采用高斯变异操作，其搜索的步长较短适用于局部搜索，但当搜索点位于局部最优值附近时容易陷入问题的局部最优解；快速进化规划FEP采用了柯西变异操作，搜索的步长增大，但在进化的后期由于步长关系其收敛速度明显放慢。我们建立了新的自适应柯西进化规划ACEP，它依据目前搜索点和全局最优点位置在一定的周期内自适应的调整柯西变异操作的参量严来改变搜索步长，从而快速到达问题的最优解，文中详细分析了高斯步长与柯西步长在搜索空间中的差异、选择操作的时间复杂度，通过算法的马尔可夫分析与算法的空间搜索能力分析从理论上证实了其快速收敛性质，最后的函数测试实验表明了ACEP算法的优越性。
　　 (2)玻利进化量子算法在优化问题中应用研究
　　 量子计算是基于经典物理学理论的量子力学与信息科学相交叉而形成的一门新兴学科，它采用了微观世界的粒子运动规律即量子力学的各种性质，如叠加态、纠缠态、相干性、可测性等来处理经典计算机难以求解的问题。量子进化算法QEA实质是一种概率演化算法，而未使用进化算法中的变异，交叉等概念，因此会在某些问题陷入局部最优。我们提出一种改进型的算法：带玻利变异的算法PEQA，它采用了量子比特编码、量子旋转门，融合了量子计算中的玻利变异，只需要单个个体的演化便可在较短时间内取得问题的最优解。通过马尔可夫链与信息熵的分析从理论上验证了算法的收敛性，最后0/1背包问题的实验表明了玻利进化量子算法PEQA优越性。
　　 (3)贷款组合问题研究
　　 以信息化为代表的计算机技术在银行领域应用广泛，它改变了传统的银行运营模式，同时人工智能技术也被逐渐使用到银行决策领域中。针对银行贷款组合的最优化问题，我们在玻利进化量子算法的基础上，引入了风险因子的概念，对贷款者进行风险评估分级，建立了带风险因子的计算模型，以使其在一定风险下期望的收益最大化，最后通过实验验证了算法的合理性。