TSP遗传算法中的交叉运算 [英] Crossover operation in genetic algorithm for TSP

问题描述

我正在尝试用旅行销售员问题（TSP） = http://en.wikipedia.org/wiki/Genetic_algorithm rel = nofollow noreferrer>遗传算法。我的基因组是图形中顶点的排列（推销员的路径）。

I'm trying to solve the Travelling Salesman Problem (TSP) with Genetic algorithm. My genome is a permutation of a vertex in graph (path for salesman).

我应该如何在基因组上进行交叉操作？

How should I perform the crossover operation over my genomes?

在哪里可以找到我的问题的实现方法？ C＃？

Where can I find implementations of my problem in C#?

推荐答案

您应选中 避免特殊交叉和变异的TSP遗传算法解决方案。它概述了用于排列的特殊交叉运算符，并提出了与标准交叉（例如，交叉两个排列始终会产生两个排列）配合使用的巧妙排列表示。

You should check "Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation" by Gokturk Ucoluk. It gives an overview of the special crossover operators for permutations and proposes a clever representation of permutations that works well with standard crossover (i.e. crossing over two permutations always produces two permutations).

关键见解是将排列表示为其反转序列，即对于每个元素 i ，存储在 a [i] 排列中 i 左边的 i 左边有多少个元素。与直接表示不同， a [i] 的唯一约束是局部的，即 a [i] 不能更大小于 N-i 。这意味着两个有效反转序列的简单交叉总是产生两个有效反转序列-无需特殊处理重复元素。

The key insight is to represent the permutation as its inversion sequence, i.e. for each element i, store in a[i] how many elements larger than i are to the left of i in the permutation. Unlike the direct representation, the only constraint on a[i] is local, i.e. a[i] cannot be larger than N - i. This means that simple crossover of two valid inversion sequences always produces two valid inversion sequences - no need for special handling of repeating elements.

这篇关于TSP遗传算法中的交叉运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！