# TSP-VRP-GENETICS-ALGORITHM
Implementation of TSP and VRP algorithms using a Genetic Algorithm
## Genetic Algorithms for TSP and VRP
Genetic Algorithms for solving the travelling salesman problem and the vehicle routing problem (TSP, VRP)
This practical assignment requires to develop, using Python, an implementation of genetic algorithms for solving the Travelling Salesman Problem -- TSP and the Vehicle Routing Problem -- VRP (at least should include TSP)
Travelling Salesman Problem. Find the optimum itinerary for a salesman that needs to visit a set of cities, visiting each city exactly once, except the city where the trip started, that must be the last city to visit.
Vehicle Routing Problem. Find routes for shipping supplies to a set of customers having different demands. The routes should be adjusted to the available fleet of trucks in order to get minimum costs.
## First part: genetic operators
A full standard genetic algorithm should be implemented in Python, including several (at least one) permutation-specific operators. For example:
- Partially Mapped Crossover (PMX) (slides 41 and 42).
- Edge Crossover (slides 45, 46 and 47).
- Order Crossover (slides 39 and 40).
- Insert mutation (slide 34).
- Swap mutation (slide 35).
- Inverse mutation (slide 36).
## Second part: Variants over the standard GA
Modify the standard version of genetic algorithms developed in the previous step, by choosing only one of the following:
**Genetic Algorithm with Varying Population Size**
The idea is to introduce the concept of "ageing" into the population of chromosomes. Each individual will get a "life-expectancy" value, which directly depends on the fitness. Parents are selected randomly, without paying attention to their fitness, but at each step all chromosomes gain +1 to their age, and those reaching their life-expectancy are removed from the population. It is very important to design a good function calculating life-expectancy, so that better individuals survive during more generations, and therefore get more chances to be selected for crossover.
**Cellular Genetic Algorithm**
The idea is to introduce the concept of "neighbourhood" into the population of chromosomes (for instance, placing them into a grid-like arrangement), in such a way that each individual can only perform crossover with its direct neighbours.
## Third part: Experimentation
Run over the same instances both the standard GA (from first part) as well as the modified version (from second part). Compare the quality of their results and their performance. Due to the inherent randomness of GA, the experiments performed over each instance should be run several times.
## Final part: Documentation
A pdf report explaining the details of the implementations developed:
- representation for genes and individuals, crossover and mutation operations, etc.
- modifications performed over the standard algorithm, instances considered,
- number of executions for each instance, showing average statistics and best result found,
- bibliography.
## Bibliography
- Chapters 2 and 3 of the book Introduction to Evolutionary Computing by A.E. Eiben and J.E. Smith. Chapter 2 is available at the book's web page. Although full version of Chapter 3 might be useful for the assignment, it may be sufficient to check the slides corresponding to this chapter that can be found at an online course using this textbook.
It is also allowed to search the web for further references and/or related material. It is mandatory to include in the bibliography all references used.
- Artificial Intelligence: A Modern Approach. S. Russell and P. Norvig.
- GAVaPS - a Genetic Algorithm with Varying Population Size. J. Arabas, Z. Michalewicz, and J. Mulawla. Proc. 1st IEEE Conf. on Evolutionary Computation, pp. 73 - 78.
- The direct link might require to have an IP within the campus to grant the download, but you can access from home via the library catalog (Fama).
- Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms . E. Alba and B. Dorronsoro. LNCS 3004, pp. 11-20.
- Other books available at the University library. For instance:
- Algoritmos Evolutivos: Un enfoque práctico. L. Araujo, C. Cervigón.
- Genetic algorithms and genetic programming : modern concepts and practical applications. M. Affenzeller...[et al.]
- Genetic algorithms + data structures = Evolution programs. Z. Michalewicz.
没有合适的资源?快使用搜索试试~ 我知道了~
使用遗传算法实现 TSP 和 VRP算法_python_代码_下载
共6个文件
pdf:2个
py:2个
md:1个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 15 下载量 102 浏览量
2022-06-18
17:47:01
上传
评论 6
收藏 1.73MB ZIP 举报
温馨提示
使用遗传算法实现 TSP 和 VRP 算法 TSP 和 VRP 的遗传算法 解决旅行商问题和车辆路线问题(TSP,VRP)的遗传算法这个实际作业需要使用 Python 开发遗传算法的实现,以解决旅行商问题 - TSP 和车辆路线问题 - VRP (至少应该包括TSP) 旅行推销员问题。为需要访问一组城市的推销员找到最佳行程,每个城市只访问一次,除了旅行开始的城市,那必须是最后一个访问的城市。车辆路线问题。寻找将供应品运送给具有不同需求的一组客户的路线。路线应根据可用的卡车车队进行调整,以获得最低成本。 第一部分:遗传算子 一个完整的标准遗传算法应该在 Python 中实现,包括几个(至少一个)特定于排列的运算符。例如: 部分映射交叉 (PMX)(幻灯片 41 和 42)。 边缘交叉(幻灯片 45、46 和 47)。 订单交叉(幻灯片 39 和 40)。 插入突变(幻灯片 34)。 交换突变(幻灯片 35)。 反向突变(幻灯片 36)。 第二部分:标准遗传算法的变体 修改上一步中开发的遗传算法的标准版本,仅选择以下选项之一: 具有不同种群大小的遗传算法 该想法是将“
资源推荐
资源详情
资源评论
收起资源包目录
TSP-VRP-GENETICS-ALGORITHM-master.zip (6个子文件)
TSP-VRP-GENETICS-master
Genetics Algoritm.pdf 1.23MB
TSP.py 16KB
Doc.pdf 622KB
LICENSE 34KB
VRP.py 16KB
README.md 4KB
共 6 条
- 1
快撑死的鱼
- 粉丝: 1w+
- 资源: 9157
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
- 3
前往页