非数值离散优化问题的填充函数算法研究

填充函数算法是由中国人提出的用于求解连续全局优化问题的有代表性的算法之一，我们已对其作改进，并提出了求解非线性整数规划问题的填充函数算法。此前的填充函数算法是针对数值型的问题，而针对非数值型问题的填充函数算法目前只有项目申请者提出的一个初步的求解对称旅行售货员问题的算法。本项目将针对非数值型的约束满足问题、图着色问题以及对称和非对称旅行售货员问题的性质和结构，从初始点的选取、邻域的构造以及在邻域内搜索的方式、特殊填充函数的构造等方面来研究求解这三类问题的填充函数算法，研究算法的概率1收敛性，研究具有理论依据的算法终止准则。本项目的研究成果将把填充函数算法的研究领域从数值型的问题拓展到非数值型的问题，将为填充函数函数算法的进一步应用打下基础。