그래서 시작하기 전에 이 TSP 문제에 대해 자세히 설명하겠습니다. 디지털 모델링을 해본 적이 있거나 지능형 최적화 또는 기계 학습에 노출된 친구들은 모두 이것을 알아야 합니다. 물론 이 기사의 보편적인 독자를 위해 우리는 이를 최대한 완벽하고 명확하게 만들기 위해 최선을 다할 것입니다. 여기서 실제로 문제를 해결할 수 있습니다.
문제는 실제로 간단합니다.
N차원 평면에서 오늘 우리가 이야기하고 있는 것은 이 2차원 평면에 많은 도시가 있습니다. 도시 도시들은 서로 연결되어 있습니다. 이제 모든 도시를 방문할 수 있는 최단 경로를 찾아야 합니다. 예를 들어 도시 A, B, C, D, E가 있습니다. 이제 도시 사이의 좌표를 알았으니, 이는 도시 사이의 거리를 아는 것과 같습니다. 이제 모든 도시 A, B, C, D, E까지 최단 경로를 만들 수 있는 시퀀스를 찾을 수 있습니다. 예를 들어 계산하면 B-->A-->C-->E-->D가 될 수 있다. 즉, 이 순서를 찾으십시오.
이 문제를 먼저 해결하려면 실제로 많은 솔루션이 있습니다. 직설적으로 말하면 경로의 합을 최소화할 수 있는 순서를 찾으면 됩니다. 그러면 가장 쉬운 방법은 열거입니다. 예를 들어, A를 먼저 이동시킨 다음 A에서 가장 가까운 거리가 B인지 확인한 다음 B로 이동한 다음 B에서 이동합니다. 물론 이것은 지역적 탐욕 전략이며 지역적 최적에 도달하기 쉽습니다. 그러면 이번에는 DP를 고려할 수 있습니다. 즉, 여전히 A에서 시작한다고 가정하고 2개의 도시가 다음과 같다는 것을 보장합니다. 3개 도시가 가장 짧고, 4개와 5개 도시가 가장 짧습니다. 마지막으로 B에서도 같은 일을 가정합니다. 아니면 모든 상황을 직접 열거하고 거리를 계산해 보세요. 그러나 어쨌든 도시의 수가 증가할수록 복잡성도 증가할 것이기 때문에 현시점에서 우리는 컴퓨팅이 인간의 전문 지식을 활용할 수 있는 방법을 찾아야 합니다. 나는 그것을 "실명"이라고 부릅니다.
이제 이 지능형 알고리즘과 이를 사용하는 이유에 대해 이야기해 보겠습니다. 이전 솔루션은 대용량 데이터에 대해 많은 계산이 필요하며 작성이 반드시 쉽지는 않다고 말했습니다. 그래서 이때 우선 TSP 문제에 대해서만 우리가 원하는 것은 시퀀스, 반복되지 않는 시퀀스입니다. 그렇다면 이때 더 간단한 해결책은 없을까요? 그리고 데이터가 충분히 크다면 가깝기만 하면 완전히 정확하고 완전히 최소한의 솔루션이 꼭 필요한 것은 아닙니다. 따라서 이때 기존 알고리즘을 사용하면 하나는 우리의 규칙에 따라서만 계산되며 표준 답이 무엇인지 실제로 알 수 없습니다. 전통적인 알고리즘 . 그러나 우리 인간에게는 '행운'이라는 것이 있습니다. 어떤 사람들은 너무 운이 좋아서 영혼에 들어오자마자 답이 혼란스러울 수도 있습니다. 따라서 우리의 지능형 알고리즘은 실제로 "원숭이"와 약간 유사합니다. 하지만 사람들은 실력에 주목합니다. 예를 들어, 경험에 따르면 긴 것 세 개와 짧은 것 한 개가 가장 짧습니다. 또는 블로거만큼 잘생긴 남자 친구를 찾을 때 이 기술을 사용할 수 있습니다. 40시리즈만 있으면 됩니다. (30개도 괜찮습니다.) 그래픽카드는 쉽게 빼낼 수 있습니다. Meng에는 기술이 필요하며 우리는 이것을 전략이라고 부릅니다.
그래서 우리가 방금 이야기한 이 기술, 이 트릭입니다. 지능형 알고리즘에서 이 마스크는 우리의 전략 중 하나입니다. 우리의 솔루션이 더욱 합리적이 되도록 어떻게 이를 제거할 수 있습니까? 그러면 이때 백 송이의 꽃이 피기 시작합니다. 여기서는 가장 고전적인 두 가지 알고리즘을 예로 들겠습니다. 하나는 유전자 알고리즘이고 다른 하나는 입자 떼 알고리즘(PSO)입니다. 예를 들어, 그들은 자연 선택을 시뮬레이션하여 처음에 여러 솔루션과 시퀀스를 무작위로 생성한 다음 자연 선택 전략을 사용하여 솔루션을 생성하는 등의 암호 해독 전략을 사용합니다. 그런 다음 이러한 솔루션을 사용하여 새롭고 더 나은 솔루션을 찾으십시오. 이렇게 왔다 갔다 하다가 좋은 해결책을 얻었습니다. 입자군집도 비슷합니다. 이 부분은 사용하면서 자세히 설명하겠습니다.
이제 우리는 이 전략을 알았습니다. 알고리즘이란 실제로 이러한 전략을 구현하는 단계이며, 이것이 바로 우리의 코드, 루프 및 데이터 구조입니다. 우리는 방금 언급한 TSP와 같은 자연 선택, 수많은 솔루션을 무작위로 생성하는 방법 등을 깨달아야 합니다.
자, 여기서는 몇 가지 기본 개념에 대해 이야기했습니다. 이제 이 TSP 문제를 어떻게 표현하는지 살펴보겠습니다. 우리 입장에서는 매우 간단합니다. 여기에 14개의 도시가 있다고 가정해 보겠습니다. 이 도시에 대한 데이터는 다음과 같습니다.
1 2 3 4 |
|
이 데이터 세트를 나중에 테스트에 사용할 예정이며 이제 14개의 도시가 있습니다.
그럼 솔루션을 시작하겠습니다
좋아요, 그럼 우리의 유전자 알고리즘이 무엇인지 이야기한 다음 이를 사용하여 이 TSP 문제를 해결하겠습니다.
이제 우리의 유전자 알고리즘이 어떻게 속는지 살펴보겠습니다.
遗传算法其实是在用计算机模拟我们的物种进化。其实更加通俗的说法是筛选,这个就和我们袁老爷爷种植水稻一样。有些个体发育良好,有些个体发育不好,那么我就先筛选出发育好的,然后让他们去繁衍后代,然后再筛选,最后得到高产水稻。其实也和我们社会一样,不努力就木有女朋友就不能保留自己的基因,然后剩下的人就是那些优秀的人和富二代的基因,这就是现实呀。所以得好好学习,天天向上!
那么回到主题,我们的遗传算法就是在模拟这一个过程,模拟一个物竞天择的过程。
所以在我们的算法里面也是分为几大块
首先我们的种群需要先繁殖。这样才能不断产生优良基于,那么对应我们的算法,假设我们需要求取
Y = np.sin(10 * x) * x + np.cos(2 * x) * x
的最大值(在一个范围内)那么我们的个体就是一组(X1)的解。好的个体就会被保留,不好的就会被pass,选择标准就是我们的函数 Y 。那么问题来了如何模拟这个过程?我们都知道在繁殖后代的时候我们是通过DNA来保留我们的基因信息,在这个过程当中,父母的DNA交互,并且在这个过程当中会产生变异,这样一来,父母双方的优秀基于会被保存,并且产生的变异有可能诞生更加优秀的后代。
所以接下来我们需要模拟我们的DNA,进行交叉和变异。
这个交叉过程和我们的生物其实很像,当然我们在我们的计算机里面对于数字我们可以将其转化为二进制,当做我们的DNA
交叉的方式有很多,我们这边选择这一个,进行交叉。
那这个在我们这里就更加简单了
我们只需要在交叉之后,再随机选择几个位置进行改变值就可以了。当然变异的概率是很小的,并且是随机的,这一点要注意。并且由于变异是随机的,所以不排除生成比原来还更加糟糕的个体。
最后我们按照一定的规则去筛选这个些个体就可以了,然后淘汰原来的个体。那么在我们的计算机里面是使用了两个东西,首先我们要把原来二进制的玩意,给转化为我们原来的十进制然后带入我们的函数运算,然后保存起来,之后再每一轮统一筛选一下就好了。
这个咋说呢,说好听点叫逆转,难听点就算,对于一些新的生成的不好的解,我们是要舍弃的。
那么这部分用代码描述的话就是这样的:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
|
这个代码是以前写的,逆转没有写上(下面的有)
ok,刚刚的例子是拿的解方程,也就是说是一个连续问题吧,当然那个连续处理的话并不是很好,只是一个演示。那么我们这个的话其实类似的。首先我们的DNA,是城市的路径,也就是A-B-C-D等等,当然我们用下标表示城市。
首先我们确定了使用城市的序号作为我们的个体DNA,例如咱们种群大小为100,有ABCD四个城市,那么他就是这样的,我们先随机生成种群,长这个样:
1 2 3 4
2 3 4 5
3 2 1 4
...
那个1,2,3,4是ABCD的序号。
这里面的话,值得一提的就是,由于暂定城市需要是不能重复的,且必须是完整的,所以如果像刚刚那样进行交叉或者变异的话,那么实际上会出点问题,我们不允许出现重复,且必须完整,对于我们的DNA,也就是咱们瞎蒙的个体。
由于咱们每一步在代码里面都有注释,所以的话咱们在这里就不再进行复述了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 |
|
ok,我们来看看运行的结果:
위 내용은 TSP(여행 세일즈맨 문제)를 해결하기 위해 Python을 사용하여 유전자 알고리즘을 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!