动态旅行商问题的研究

传统的旅行商问题都是静态的,但在现实中许多问题是动态的。该文提出动态旅行商问题,问题的规模随时间不断变化。实时问题对算法的求解效率要求很高,为此设计了基于模糊规则的在线遗传算法,可以根据求解问题的变化,在线精炼模糊控制规则来控制算法的参数。仿真实验验证了算法的有效性。

基于仿真的遗传算法求解动态旅行商问题

以标准旅行商问题的扩展问题——动态旅行商问题为对象,分析了动态旅行商问题中由于道路流量实时变化所引起的标准旅行商问题的数学建模与优化求解的问题复杂性。通过建立其计算机仿真模型再现动态旅行商问题中众多复杂的非平稳、随机因子。进而提出了基于计算机仿真模型的遗传算法,即根据计算机仿真的结果,应用改造后的遗传算法搜索原问题的优化解。最后,在多智能体仿真平台上实现该优化算法,并以此求解20个城市的动态旅行商问题,计算结果验证了算法的有效性。

基于移民策略求解动态TSP问题的遗传算法

在标准遗传算法(SGA)中加入移民策略可以丰富种群多样性,使SGA能够更好的适应环境的变化。为了改善基于移民策略的遗传算法在搜索空间内的探索能力,受原对偶映射思想的启发,设计了基于原对偶映射的移民策略(Primal-Dual based Immigrants,PDI),并将这种策略加入到遗传算法中,求解动态旅行商问题(Dynamic Travelling Salesman Problem,DTSP)。仿真结果表明,与基于其他移民策略的遗传算法相比,PDIGA能够更好的适应环境的变化。

自适应蚁群算法求解最短路径和TSP问题

对传统蚁群算法的初始化信息素浓度加入方向引导,避免蚁群在初始阶段盲目地随机搜索浪费较多的时间;在全局信息素更新过程中加入双曲正切函数作为动态因子,自适应地更新每次迭代较优解路径的信息素浓度,增大算法获取全局最优解的可能性。两个算例采用改进的蚁群算法进行优化,优化的结果与实际情形具有良好的一致性,说明了改进算法的有效性和实用性。

包含多重嵌套封闭环的平面切割建模与优化

为解决在平面图形切割领域中采用不同的切割顺序以及切割起止点导致切割路径空行程相差甚远的问题,提出一种包含多重嵌套封闭环的平面切割路径优化算法.首先提出一种多重嵌套封闭环识别子算法,并以四向链表节点为基础构建包含多重嵌套封闭环的平面切割路径模型;然后考虑各封闭环的几何特征以及彼此之间的关系,将切割路径优化问题转化为多个关联的动态旅行商问题组合;最后通过逐层多次调用禁忌贪婪算法对切割路径进行优化求解,在优化中同时考虑封闭环之间的切割顺序及各封闭环切割起止点的选择.仿真实验结果表明,该算法对包含多重嵌套封闭环的平面切割路径建模和优化是可行和有效的.

基于DXF文件的平面切割路径优化

平面切割中的文件往往是经由排样软件处理后的DXF文件,如果根据DXF文件中图元顺序初步生成的加工轨迹作为切割加工的顺序,那么将导致空行程增多,生产效率降低,并且加大设备损耗。提出一种基于动态旅行商问题(DTSP)模型的贪婪算法对切割路径进行优化,并通过运算实例说明了本算法的有效性。