應用原罪遺傳演算法於古典賽事旅行成本最小化問題

摘要

运动赛事的进行是现代人所经常引起关切的话题，一年四季皆会有特定的赛事供球员彼此较劲，提供观看者感官娱乐与运动员获取荣誉及奖金的机会。赛程的安排往往是费时且耗人力的，需要考虑到许多复杂的问题。本研究以Easton, 2001学者所创立的旅行成本问题作为研究对象，赛事的体制采取双循环的赛制，希望能在不违反软性限制的情况下，求解出适用且最小成本的赛程。此问题已被定义为NP-Hard问题，曾有许多学者提出作业研究的方法以及启发式的演算法中的模拟退火法、禁忌搜寻法来求解。本研究提出以遗传演算法来求解此问题，希望藉由交配的概念来提升演化的复杂度，更加上新观念「原罪」的导入，使演化更贴近於大自然界。而从实验的成果中也藉由多种不同的参数分析证实「原罪」的引进对於求解问题时更为复杂且有效。