Research On Constraint Solving Algorithms Based On Method Of Musical Composition

Constraint Satisfaction Problems(CSPs)are an important part of artificial intelligence.Related techniques can be widely used in the fields of configuration,scheduling,and combinatorial problem,etc.The current mainstream technology for solving CSPs is a combination of backtracking and constraint propagation.This algorithm prunes the search space effectively and reduces useless searches.When the problem has solutions,this algorithm that is also called a complete algorithm could find the solution.People often use this complete algorithm as a basis for judging whether the problem has a solution.When the size of constraint problem is increasing and constraint's number get larger,the solving problems become harder.When a complete algorithm is used to solve the problem,it can take a long time to get the solution.If time cost is constrained,the complete algorithm may not be able to get the solution.In this case,we can consider the incomplete algorithm.Although the incomplete algorithm is likely to have a worse performance than the complete algorithm,it can be guaranteed to find a feasible solution within a limited time.This paper mainly studies the metaheuristic in incomplete algorithm.Meta-heuristic has the advantages of simple method,easy operation and better effective.It is widely used in the fields of scheduling,feature selection,pattern recognition,multi-objective optimization,neural network training and combinatorial problem,etc.There are many excellent algorithms in the meta-heuristic algorithm family.These algorithms can be roughly divided into two categories: single-based meta-heuristic algorithms and population-based meta-heuristic algorithms.Singlebased meta-heuristic algorithms includes: simulated annealing algorithm,tabu search algorithm and so on.Ant colony algorithm,teaching and learning optimization algorithm,differential evolution algorithm,and method of music composition belong to the population-based meta-heuristic algorithms.Among them,method of musical composition(MMC)is a novel meta-heuristic algorithm proposed by Román Anselmo Mora Gutiérrez et al in 2012.This method mimics the composer's composing process.Composers exchange information between themselves and their environment and then use their background knowledge to create tunes.They improve the composing ability in a comprehensive way through two aspects of knowledge.So when MMC reserves the diversity,it also enhances the exploration's ability.In this paper,we study MMC's framework,and analyze the global search,convergence speed and late performance in the running process.We combine MMC with the solving problem to make the corresponding improvement.The result shows a good performance.This main work of this paper is detailed as follow:(1)Aiming at the serious limitation of the speed which the current optimal solution promotes the population evolution,MMC with Teaching strategy is proposed.Teaching strategy aims at search the current optimal solution and maximize the function of the current optimal solution in the algorithm.Then,we realize new discrete technology by Mistral solver.The algorithm is enhanced to some extent.We compare TLBO,DE,original MMC and the improved algorithm in Max CSPs which is the extension problem of CSPs.The experimental result show that our improved algorithm has obvious advantages in the stability and finding the optimal solution.(2)The limitations of MMC are analyzed in the iterative process: MMC uses the worst tune in the update of the solution as the condition to judge whether the new solution is accepted,which weakens local search's ability.In this chapter,we combine local search with MMC and propose MMC-local Search.It is applied to course timetabling problem and course scheduling problem.The result proves that MMClocal Search makes up the disadvantages of MMC.In this paper,the MMC algorithm is improved in two ways.When solving Max CSPs,the experimental results show that the current optimal solution has a significant impact on the final result.In the course table problems,due to many constraints of course timetabling problem,MMC does not show a good result.But it has a good performance in the course scheduling problem which has relatively few constraints.Therefore,we can select MMC in less constrained problems.