摘要
要为解决现实应用中的类似于小规模旅行商问题的组合优化问题,提出了一种新的近似算法——群体竞争搜索算法(PCS).使用了一种新的局部搜索算子2e/1p-opt,并按照"搜索-选优-变异-搜索"的迭代策略设计了群体竞争搜索算法.与CLK算法进行了比较,对于280城市以下的旅行商问题,在计算速度和计算结果两方面都有较好表现.将高校排考中的场次排序优化问题转化为TSP并用算法求解,能在1秒内得到大幅改进的结果.
To solve the practical combinatorial optimization problem similar to small-scale 1 ~1~, an emclem algorithm named Population Competitive Search（PCS） is presented. A new local search operator named 2e/lp-opt is used, and t algorithm is designed based on the iterative strategy of ＂search-select-mutate-search＂. Compared with CLK on TSP instances witch city numbers not more than 280, PCS has better performance in speed and results. PCS is applied for examination timetabling and achieves greatly improved results in 1 second.
出处
《微电子学与计算机》
CSCD
北大核心
2018年第1期56-60,共5页
Microelectronics & Computer
基金
广东省教育厅2015重大平台和科研项目(2015KTSCX177)
关键词
旅行商问题
局部搜索
群体进化算法
排考
travelling salesmen problem
local search
evolutionary algorithms
examination timetabling
