基于基因表达式编程的TSP问题求解

doi:10.3778/j.issn.1002-8331.2008.23.016

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (23): 53-55.DOI: 10.3778/j.issn.1002-8331.2008.23.016

基于基因表达式编程的TSP问题求解

朱明放

陕西理工学院计算机系，陕西汉中 723003

收稿日期:2007-10-17 修回日期:2007-12-26 出版日期:2008-08-11 发布日期:2008-08-11
通讯作者: 朱明放

Method of TSP problem based on gene expression programming

ZHU Ming-fang

Department of Computer Science & Technology，Shaanxi University of Technology，Hanzhong，Shaanxi 723003，China

Received:2007-10-17 Revised:2007-12-26 Online:2008-08-11 Published:2008-08-11
Contact: ZHU Ming-fang

摘要/Abstract

摘要： 利用遗传算法求解组合优化问题时，需要特有的遗传算子，才能在候选解空间中有效搜索和进化。基因表达式编程（GEP）是进化计算家族的新成员。旅游商问题（TSP）是典型的组合优化问题，得到了广泛的研究，它的研究成果将对求解NP类问题产生重要影响。基于基因表达式编程（GEP）来解决TSP问题，引入适用组合优化的遗传算子：逆串，基因串的删/插等，最后进行了实验，展示GEP解决TSP问题的方法。实验表明GEP能有效解决TSP问题，设计的系统是强壮健康，其求解速度快且解的质量好。

关键词: TSP问题, 基因表达式编程, 逆串算子, 插/删串算子

Abstract: Combinatorial optimization problem requires specific genetic operators so that populations of candidate solution can evolve efficiently.Gene Expression Programming（GEP） is a new member of computational algorithms.TSP problem delegates a classic combinatorial optimization problem.It is also one of combinatorial optimization which has been gained extensive research.The research fruit will help to solve to NP-hard question.Solving TSP problem based on gene expression programming will be presented this paper.Especial genetic operators are introduced inversion and insertion/deletion gene.At last the study of experiment is presented，the results indicate this algorithm is fast and can obtain good quality solutions.

Key words: TSP problem, Gene Expression Programming（GEP）, inversion, insertion/deletion sequence

朱明放. 基于基因表达式编程的TSP问题求解[J]. 计算机工程与应用, 2008, 44(23): 53-55.

ZHU Ming-fang. Method of TSP problem based on gene expression programming[J]. Computer Engineering and Applications, 2008, 44(23): 53-55.

[1]	张晓婷，何朗，黄樟灿，谈庆. 基于MFR-GEP的高阶常微分方程预测模型[J]. 计算机工程与应用, 2019, 55(21): 247-253.
[2]	郭勇1，张国锋1，刘丽萍2. 基因沉默机制的基因表达式编程[J]. 计算机工程与应用, 2018, 54(23): 131-136.
[3]	崔未，王卫华，黄樟灿，谈庆. 基于GEP算法的高阶常微分方程预测模型[J]. 计算机工程与应用, 2018, 54(18): 256-262.
[4]	张子成，韩伟. 求解TSP问题的自适应离散型布谷鸟算法[J]. 计算机工程与应用, 2017, 53(10): 48-54.
[5]	张柯，张德平. 基于基因表达式编程的错误定位方法[J]. 计算机工程与应用, 2016, 52(9): 6-11.
[6]	王斌1，张迅2，盛津芳1，陈新3，史秀志3. 优化的GEP算法在爆破振动预测中的应用[J]. 计算机工程与应用, 2016, 52(22): 212-217.
[7]	陈威虎，向凌云. 基于开放读码框架的GEP遗传算子[J]. 计算机工程与应用, 2016, 52(18): 57-61.
[8]	朱明放1，2，叶飞跃1，2，丁小未2. 基于GEP的任务指派问题的求解算法[J]. 计算机工程与应用, 2014, 50(22): 50-53.
[9]	王晓1，何锫1，2. 一种新型GEP解码方法[J]. 计算机工程与应用, 2012, 48(3): 43-45.
[10]	柳益君，朱明放，习海旭，朱广萍，蒋红芬，陈丹. 基于最大隶属度原则的基因表达式编程分类[J]. 计算机工程与应用, 2012, 48(26): 48-52.
[11]	莫海芳1，李康顺2. 基因表达式编程的一种新遗传算子[J]. 计算机工程与应用, 2011, 47(7): 23-24.
[12]	袁锋1，陈守强2. 一种冠心病介入术后复发预测组合模型的构建[J]. 计算机工程与应用, 2011, 47(35): 228-231.
[13]	王艳春^1，2. 蛋白质二级结构预测方法研究[J]. 计算机工程与应用, 2009, 45(36): 44-46.
[14]	张雪东¹，饶元^2，3，元昌安³，赵传信^2，4. 应用禁忌基因表达式编程提高模型精度[J]. 计算机工程与应用, 2009, 45(28): 35-38.
[15]	王艳春^1,2. 基因表达式编程的LFC方法及其应用[J]. 计算机工程与应用, 2009, 45(15): 70-71.

基于基因表达式编程的TSP问题求解

Method of TSP problem based on gene expression programming

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics