基于音乐作曲优化的约束求解算法研究

发布时间：2020-06-12 12:22

【摘要】：约束满足问题(Constraint Satisfaction Problems,CSPs)是人工智能的一个重要组成部分。相关求解技术在配置、规划、调度等问题上有着广泛的应用。当前求解CSPs的主流技术是回溯与约束传播相结合的算法,该算法对搜索空间进行有效剪枝,减少无用搜索。当问题存在解时,回溯与约束传播相结合的算法一定能找到解,是完备算法,经常作为判断问题是否有解的依据。随着求解问题的规模不断增大、约束不断增多,使得问题求解的难度大幅上升。完备算法虽然能够求得解,但花费的时间较长。当限定问题求解时间时,完备算法有可能得不到解。在这种情况下可考虑采用不完备算法。不完备算法虽然求解效果不一定优于完备算法,但能保证在限定的时间内找到可行解。本文主要研究不完备算法中的元启发式算法。元启发式算法具有方法简单、易操作且求解效果较好等优点,在调度、特征选择、模式识别、多目标优化、神经网络训练、组合优化等领域有着广泛应用。元启发式算法家族中有很多优秀的算法。这些算法大致可分为两类:基于单一解的元启发式算法和基于种群的元启发式算法。基于单一解的元启发式算法包括:模拟退火算法、禁忌算法等。基于种群的元启发式算法包括蚁群算法、教与学优化算法、差分进化算法、音乐作曲优化算法等。其中,音乐作曲优化算法(Method of Musical Composition,MMC)是由Román Anselmo Mora Gutiérrez等人在2012年提出的一种新型元启发式算法。该算法模拟了作曲家作曲过程,使用了自身学习和与其他作曲家交流这两种方法创作曲调。所以MMC在保证多样性的同时提高了集中探索能力。本文研究了MMC的框架结构。分析了算法在运行过程中的全局搜索能力、收敛情况及MMC在后期的运算过程。将MMC与求解问题相结合做出相应的改进,提升了算法求解能力。主要研究内容包括:(1)针对求解过程中当前最优解推动种群进化的速度受到严重制约的现象,提出了基于引领策略的MMC。引领策略有针对性的搜索当前最优解,尽最大可能发挥最优解在算法中的作用。我们基于Mistral求解器实现新的离散方法,通过与TLBO、DE和原MMC求解CSPs的扩展问题—Max CSPs进行实验对比。实验表明:改进算法无论在求解的稳定性还是找到的最优解都具有显著优势。(2)深入分析MMC在求解过程中的劣势:在解更新过程中使用最差曲调作为接受新解的标准,导致其局部搜索能力较弱。我们将MMC与局部搜索算法相结合,提出了MMC-local Search并应用到课程时间表问题和课程调度问题中,实验表明改进算法有效弥补原有MMC的不足。本文使用了两种方式对MMC进行了相应的改进,实验结果证明在求解Max CSPs时,当前最优解对最终结果有着显著影响。在课程表问题中,由于课程时间表问题的约束限制较多,MMC没有展现出很好的求解效果,但在约束相对较少的课程调度问题上具有很好的性能,因此求解约束较少的问题时,可以选择MMC。
【图文】：

约束满足问题,赋值,中变

1 51 4{ ,..., }( ) { , , }, 1,2,...,5( ,..., )iX x xdom x a b c iC c c ———约束范围如下：1 1 22 2 3 43 3 54 4 5( ) { , }( ) { , , }( ) { , }( ) { , }scope c x xscope c x x xscope c x xscope c x x 我们假设约束中的值是按 scope 中变量顺序进行赋值。定义的约束如下，信息由图 2.1 表示：{( , ),( , )}{( , , ),( , , ),( , , ),( , , ),( , , )}{( , ),( , ),( , ),( , )}{( , ),( , ),( , ),( , )}1234c a a a cc a a a a a b a b b b b b c c cc a a a b b c c cc a a b b b c c c

抽象层次

第 2 章背景知识本数据类组成，用来描述求解的问题。它的作用是维护搜索空间的状态，、保存输入/输出数据。Helpers 文件保存了描述问题的代码和执行搜索作。例如：NeighborhoodExplorer 负责邻域相关事情：选择移动、移动更新等。在复合搜索的情况下，可以多个 NeighborhoodExplorer 结合使elpers 文件中类相互合作。例如 NeighborhoodExplorer 类不具备成本函能，，需要委托给处理状态属性的 StageManager 类。需要注意的是 Helpers具有自己的内部数据，需要依赖 Runners 进行数据操作。
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18

【参考文献】