如何使用遗传算法求解节点之间的最短路径？
如果我有一个节点网络，如何使用遗传算法计算任意两个节点之间的最短路径？
If I have a network of nodes, how can I use genetic algorithms to calculate the shortest path between any two nodes?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
使用GA来解决TSP问题怎么样？
TSP 是一个 NP 完全问题。也就是说不可能找到一个
在多项式时间内解决 TSP 问题。然而，给定一个
解可以验证是否是多项式时间内的解。
可以研究遗传算法等元启发式方法
作为解决 TSP 问题的工具，因为基于人口
他们的运作方式。这样他们就可以“处理”大量的
算法运行时的解决方案。使用 GA 解决任何问题
我们需要定义以下内容：
适应度函数：这里的适应度函数很容易定义。它
应该是推销员在一定时间内必须经过的距离
可以游览城市。我们力求在 TSP 中尽量减少这种情况。
染色体：染色体可以简单地定义如下 - 假设
我们有五个城市 A、B、C、D 和 E。然后想象一条长度为 1 的染色体
5，染色体的每个“槽”包含 5 个中的任意一个
城市。例如，在我们的例子中，A、C、D、B、E 是有效的染色体。
交叉算子：交叉算子在 GA 中用于“混合”两个
家长们都希望能生出更健康的孩子。各种交叉
遗传算法文献中提供了算子，每个算子都有不同的
达到同样目的的方法。例如，考虑单点
交叉。它随机选择一个交叉点然后互换
两者之间的位。无需进入其他专业
交叉运算符，让我们看看什么是好的交叉
我们的运营商。在我们的例子中，两条亲代染色体各有一个
A、B、C、D、E 的排列。无论我们选择什么交叉方法，我们都有
这里要注意一个事实：交叉运算符不应该
创建一个孩子，其中一个城市多次出现，即
无效染色体。一种这样的交叉算子是“Order
交叉” (OX) 可以在这里使用。
变异：变异可以像简单地交换两个位置一样简单
在这里的一条染色体上。
总的来说，这是使用 GA 的 TSP 的工作方式：
您创建一个个体群体，每个个体的大小为 5，
并包含 A、B、C、D、E 的排列（会有很多
相同排列的重复）
您启动 GA，并在每次运行中评估每个个体
通过使用计算距离来确定适应度函数的基础
给你的距离参数
交叉，变异改进个体，最后是最好的
解决方案将是拥有最佳旅行的个人，即。最优的
A,B,C,D,E的排列。
希望有帮助！
How about using GA to solve the TSP problem?
TSP is a NP complete problem. That is it is not possible to find a
solution to the TSP problem in Polynomial time. However, given a
solution it can be verified if it is a solution in polynomial time.
Meta-heuristic methods such as Genetic Algorithms can be investigated
as a tool to solve a TSP problem because of the population based
approach they operate. This way they can "process" a huge number of
solutions in on run of the algorithm. To solve any problem using GAs
we need to define the following:
Fitness function: Here the fitness function is easy to define. It
should be the distance that the salesman has to traverse for a certain
tour of the cities possible. We seek to minimize this in TSP.
Chromosome: A chromosome can be defined simply as following- Suppose
we have five cities A,B,C,D and E. Then imagine a chromosome of length
5, with each "slot" of the chromosome containing either of the 5
cities. For eg, A,C,D,B,E is a valid chromosome in our case.
Crossover operator: A crossover operator is used in a GA to "mix" two
parents with the hope to get fitter children. Various crossover
operators are available in GA literature with each having a different
way to achieve the same thing. For eg, consider the single point
crossover. It randomly selects a crossover point and then interchanges
the bits between the two. Without getting into other specialized
crossover operators, let us see what would be a good crossover
operator for us. In our case, two parent chromosomes will each have a
permutation of A,B,C,D,E. Whatever crossover method we choose, we have
to take care of one fact here: the crossover operator should not
create a child in which one city is present more than once, that is a
invalid chromosome. One such crossover operator is the "Order
Crossover " (OX) which can be used here.
Mutation: Mutation can be as simple as simply swapping two positions
in a single chromosome here.
Overall this is how a TSP using GA would work:
You create a population of individuals with each being of size 5,
and containing a permutation of A,B,C,D,E (there will be lots of
repetitions of the same permutation)
You start the GA and in every run, you evaluate each individual on
the basis of the fitness function by calculating the distance using
the distance parameters given to you
Crossover, Mutation improves the individuals and finally the best
solution would be the individual with the best tour, ie. the optimal
permutation of A,B,C,D,E.
Hope that helps!