All language subtitles for 病毒为何不停变异？旅行推销员问题和遗传算法
Afrikaans
Akan
Albanian
Amharic
Arabic
Armenian
Azerbaijani
Basque
Belarusian
Bemba
Bengali
Bihari
Bosnian
Breton
Bulgarian
Cambodian
Catalan
Cebuano
Cherokee
Chichewa
Chinese (Simplified)
Chinese (Traditional)
Corsican
Croatian
Czech
Danish
Dutch
Esperanto
Estonian
Ewe
Faroese
Filipino
Finnish
French
Frisian
Ga
Galician
Georgian
German
Greek
Guarani
Gujarati
Haitian Creole
Hausa
Hawaiian
Hebrew
Hindi
Hmong
Hungarian
Icelandic
Igbo
Indonesian
Interlingua
Irish
Italian
Japanese
Javanese
Kannada
Kazakh
Kinyarwanda
Kirundi
Kongo
Korean
Krio (Sierra Leone)
Kurdish
Kurdish (Soranî)
Kyrgyz
Laothian
Latin
Latvian
Lingala
Lithuanian
Lozi
Luganda
Luo
Luxembourgish
Macedonian
Malagasy
Malay
Malayalam
Maltese
Maori
Marathi
Mauritian Creole
Moldavian
Mongolian
Myanmar (Burmese)
Montenegrin
Nepali
Nigerian Pidgin
Northern Sotho
Norwegian
Norwegian (Nynorsk)
Occitan
Oriya
Oromo
Pashto
Persian
Polish
Portuguese (Brazil)
Portuguese (Portugal)
Punjabi
Quechua
Romanian
Romansh
Runyakitara
Russian
Samoan
Scots Gaelic
Serbian
Serbo-Croatian
Sesotho
Setswana
Seychellois Creole
Shona
Sindhi
Sinhalese
Slovak
Slovenian
Somali
Spanish
Spanish (Latin American)
Sundanese
Swahili
Swedish
Tajik
Tamil
Tatar
Telugu
Thai
Tigrinya
Tonga
Tshiluba
Tumbuka
Turkish
Turkmen
Twi
Uighur
Ukrainian
Urdu
Uzbek
Vietnamese
Welsh
Wolof
Xhosa
Yiddish
Yoruba
Zulu
Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
00:00:00,340 --> 00:00:01,260
各位同學大家好
2
00:00:01,260 --> 00:00:02,340
我是李永樂老師
3
00:00:02,440 --> 00:00:03,300
最近一段時間
4
00:00:03,320 --> 00:00:06,579
新冠病毒奧密克戎變異毒株依然在全世界肆虐
5
00:00:06,659 --> 00:00:09,000
這種病毒相比於兩年前剛出現的時候
6
00:00:09,019 --> 00:00:10,579
傳染性有了很大增強
7
00:00:10,659 --> 00:00:13,119
而致病性 病死率都有所降低
8
00:00:13,119 --> 00:00:15,119
這是符合病毒遺傳學規律的
9
00:00:15,139 --> 00:00:17,480
因為更強的傳染性和更低的致病性
10
00:00:17,500 --> 00:00:19,239
更有利於病毒的傳播
11
00:00:19,340 --> 00:00:22,380
但是奧密克戎一定不是新冠病毒變異的終點
12
00:00:22,380 --> 00:00:25,219
未來依然有可能會出現新型的變異病毒
13
00:00:25,539 --> 00:00:27,199
其實不僅僅是病毒
14
00:00:27,219 --> 00:00:30,400
細菌 真菌等微生物 植物 動物等高等生物
15
00:00:30,420 --> 00:00:32,440
也都始終處於變異之中
16
00:00:32,558 --> 00:00:33,840
有小朋友就問我說
17
00:00:33,840 --> 00:00:35,920
生命為什麼會發生變異呢
18
00:00:35,920 --> 00:00:37,320
這是一個生物學問題
19
00:00:37,320 --> 00:00:39,500
但它背後也蘊藏著數學的原理
20
00:00:39,599 --> 00:00:41,880
今天我就想通過一個數學問題
21
00:00:41,880 --> 00:00:43,199
旅行推銷員問題
22
00:00:43,199 --> 00:00:46,760
給大家介紹一下生物界遺傳和變異的重要意義
23
00:00:47,119 --> 00:00:49,300
我們首先來描述一下這個問題
24
00:00:49,599 --> 00:00:58,280
這個問題叫做旅行的推銷員 旅行的推銷員
25
00:00:59,599 --> 00:01:00,440
意思是說
26
00:01:00,559 --> 00:01:03,780
有一個推銷員要到許多個城市推銷自己的產品
27
00:01:03,800 --> 00:01:06,099
推銷完了還要回到出發的城市
28
00:01:06,199 --> 00:01:08,559
那麼每兩個城市之間都有機票
29
00:01:08,559 --> 00:01:10,519
而且機票的價格是不一樣的
30
00:01:10,599 --> 00:01:11,300
我們舉個例子
31
00:01:11,400 --> 00:01:14,260
比如說這個推銷員他出發點叫A
32
00:01:14,619 --> 00:01:18,559
他想到B C D這三個城市進行推銷
33
00:01:18,579 --> 00:01:21,440
那麼每兩個城市之間都有機票
34
00:01:21,539 --> 00:01:23,159
可以坐飛機過去
35
00:01:23,320 --> 00:01:26,320
那麼這個機票的價格它也是很容易查到的
36
00:01:26,320 --> 00:01:29,619
比如說A和B這兩個城市機票價格是3元
37
00:01:29,900 --> 00:01:31,219
來回都是3元
38
00:01:31,300 --> 00:01:33,380
B和C價格貴一點 是7元
39
00:01:33,380 --> 00:01:34,940
C到D是20元
40
00:01:34,940 --> 00:01:36,780
A和D之間是5元
41
00:01:36,780 --> 00:01:38,679
B和D之間是6元
42
00:01:38,699 --> 00:01:40,800
而A和C之間是10元
43
00:01:40,820 --> 00:01:42,599
好 假如我們已經知道了
44
00:01:42,619 --> 00:01:44,320
所有城市之間的機票價格了
45
00:01:44,340 --> 00:01:46,480
而且去和回價格是一樣的
46
00:01:46,599 --> 00:01:47,300
我們現在就問
47
00:01:47,320 --> 00:01:52,000
那麼什麼樣的路線 什麼樣的一個路線
48
00:01:52,000 --> 00:01:55,360
這個路線是從A出發 最終又回到A
49
00:01:55,519 --> 00:02:01,659
那麼總共的價格最低 總共的價格最低
50
00:02:01,860 --> 00:02:04,739
那這個問題就稱之為旅行推銷員問題
51
00:02:04,739 --> 00:02:07,139
當然了 它的城市可能不只有3個
52
00:02:07,139 --> 00:02:08,699
可能是10個 可能是100個
53
00:02:08,699 --> 00:02:09,979
甚至有可能會更多
54
00:02:09,979 --> 00:02:11,739
我們看起來好像這個問題並不復雜
55
00:02:11,760 --> 00:02:13,400
你看C D之間價格是20
56
00:02:13,480 --> 00:02:15,380
所以我們盡量不走它就好了 對不對
57
00:02:15,400 --> 00:02:16,820
但是城市一旦多起來
58
00:02:16,960 --> 00:02:18,460
這個算法可能就會比較複雜
59
00:02:18,579 --> 00:02:22,400
比如說我們有一種算法 一種顯而易見的算法
60
00:02:22,400 --> 00:02:23,800
那就是暴力搜索
61
00:02:24,059 --> 00:02:28,699
我們可以把所有的路線都把它列出來
62
00:02:28,699 --> 00:02:30,699
然後看一下這個
63
00:02:30,699 --> 00:02:33,260
每一個路線中它的價格是多少 是吧
64
00:02:33,260 --> 00:02:35,360
比較一下 找到最優價格就可以了
65
00:02:35,480 --> 00:02:37,920
比如說這個推銷員不是從A出發嗎
66
00:02:38,000 --> 00:02:39,579
那麼他面臨幾條路啊
67
00:02:39,599 --> 00:02:41,559
它可以走B 對吧
68
00:02:41,559 --> 00:02:44,519
你也可以走C 你也可以走D
69
00:02:44,519 --> 00:02:47,159
這是第一次你出發的時候可以走路徑
70
00:02:47,320 --> 00:02:49,800
然後你如果到了B之後你還可以去哪
71
00:02:49,880 --> 00:02:52,840
你還可以去C 你還可以去D 對不對
72
00:02:52,840 --> 00:02:55,039
如果你去了C 那最後一站只能是D
73
00:02:55,039 --> 00:02:56,719
如果你去了D 最後一站只能是C
74
00:02:56,719 --> 00:02:58,320
然後你再回到A 對不對
75
00:02:58,719 --> 00:03:00,300
這是你的兩條路
76
00:03:00,300 --> 00:03:01,820
當然你要是走C的話
77
00:03:02,099 --> 00:03:04,820
你也可以去B或者去D
78
00:03:04,920 --> 00:03:06,539
然後我們把它補齊 是吧
79
00:03:07,239 --> 00:03:09,059
這樣的話又有兩個路徑
80
00:03:09,280 --> 00:03:10,639
當然還有 是吧
81
00:03:10,659 --> 00:03:12,639
如果你先走D的話也是一樣
82
00:03:12,659 --> 00:03:17,179
B C C B最後你再回到A
83
00:03:17,260 --> 00:03:19,719
好 這一共就是6條路徑
84
00:03:19,739 --> 00:03:23,000
我們可以計算每一條路徑所花費的機票總價
85
00:03:23,139 --> 00:03:25,699
比如說A B C D A這一條路徑
86
00:03:25,699 --> 00:03:30,260
價格就是3+7+20+5 對吧
87
00:03:30,260 --> 00:03:31,460
一共加起來是多少
88
00:03:31,460 --> 00:03:34,079
是 35元 對不對
89
00:03:34,099 --> 00:03:36,400
仿照這樣的寫法我就把所有的都列好
90
00:03:36,840 --> 00:03:39,619
好 6種情況的機票價格咱們都列出來了
91
00:03:39,639 --> 00:03:41,099
我們顯而易見地發現
92
00:03:41,639 --> 00:03:44,039
有兩條路價格是最低的 是28元
93
00:03:44,039 --> 00:03:45,980
而且你有沒有發現這6種情況
94
00:03:45,980 --> 00:03:47,340
好像分為3組 對吧
95
00:03:47,340 --> 00:03:50,980
35 35 39 39 28 28
96
00:03:50,980 --> 00:03:51,739
為什麼呢
97
00:03:51,739 --> 00:03:54,920
你看你順著走有一條路A B C D A
98
00:03:54,940 --> 00:03:57,039
你反著走叫A D C B A
99
00:03:57,059 --> 00:03:58,739
那不就是這條路嗎 對不對
100
00:03:58,739 --> 00:04:01,179
所以這兩條路它實際上是一正一反
101
00:04:01,179 --> 00:04:02,219
它是對稱的
102
00:04:02,440 --> 00:04:04,820
因為機票價格跟你去和返沒有關係
103
00:04:04,820 --> 00:04:07,980
所以這兩條路其實應該算是一種情況 對吧
104
00:04:07,980 --> 00:04:09,420
那麼按照這樣的方法
105
00:04:09,420 --> 00:04:12,199
我們就可以暴力搜索出每一種情況
106
00:04:12,219 --> 00:04:13,280
找到最優解了
107
00:04:13,519 --> 00:04:15,760
如果我們只有四個城市 這個事好辦
108
00:04:15,780 --> 00:04:17,099
但是如果城市多了
109
00:04:17,380 --> 00:04:19,579
假如咱們有n個城市的話
110
00:04:19,639 --> 00:04:23,199
你看一看需要多少個路徑呢
111
00:04:23,219 --> 00:04:25,420
咱們思考一下 如果你有n個城市的話
112
00:04:25,420 --> 00:04:27,059
你從其中一個城市出發
113
00:04:27,139 --> 00:04:30,219
你第一次面臨著n-1種選擇
114
00:04:31,300 --> 00:04:34,320
第二次 你又面臨著n-2種選擇
115
00:04:34,539 --> 00:04:36,599
第三次n-3 第四次n-4
116
00:04:36,619 --> 00:04:39,559
一直到最後一次 應該是面臨著一種選擇
117
00:04:39,639 --> 00:04:42,480
但是因為一正一反 兩條路價格是一樣的
118
00:04:42,480 --> 00:04:44,000
所以我們可以把它除以2
119
00:04:44,079 --> 00:04:46,139
也就是說剛才我算了6種情況
120
00:04:46,139 --> 00:04:47,539
它其實對應的是3組
121
00:04:47,559 --> 00:04:48,659
我應該把它除以2
122
00:04:48,679 --> 00:04:51,179
把它寫成一個階乘的形式
123
00:04:51,260 --> 00:04:54,820
就是(n-1)!/2
124
00:04:54,900 --> 00:04:57,039
階乘的意思就是1×2×3×4×...
125
00:04:57,059 --> 00:04:58,679
一直乘到n-1 對不對
126
00:04:58,699 --> 00:05:00,480
所以如果你有n個城市的話
127
00:05:00,500 --> 00:05:04,480
你的搜索的次數應該至少是這麼多次 對不對
128
00:05:04,480 --> 00:05:06,039
好 咱們來算一算這有多少
129
00:05:06,159 --> 00:05:09,360
假如說你有10個城市
130
00:05:09,480 --> 00:05:11,619
那麼你所搜索的次數f
131
00:05:12,039 --> 00:05:15,659
應該是181440次
132
00:05:15,880 --> 00:05:17,780
看起來好像還不太多 對不對
133
00:05:17,860 --> 00:05:20,199
但是如果你有30個城市
134
00:05:20,300 --> 00:05:22,119
你知道搜索多少次嗎
135
00:05:22,139 --> 00:05:27,119
它需要搜索4.4×10³⁰這麼多
136
00:05:27,260 --> 00:05:30,400
現在的超級計算機一秒鐘可以計算1萬億次
137
00:05:30,420 --> 00:05:31,320
咱們假如說
138
00:05:31,340 --> 00:05:34,079
超級計算機一秒鐘可以搜索一條路徑的話
139
00:05:34,099 --> 00:05:35,519
你要搜索這麼多路徑
140
00:05:35,539 --> 00:05:37,800
超級計算機需要算1400億年
141
00:05:37,880 --> 00:05:41,280
可見30個城市暴力求解已經不現實了
142
00:05:41,280 --> 00:05:42,860
那如果你要是有100個城市
143
00:05:43,360 --> 00:05:44,500
100個城市的話
144
00:05:44,519 --> 00:05:48,900
你就要搜索4.7×10¹⁵⁵
145
00:05:48,920 --> 00:05:49,820
這麼多條路徑
146
00:05:49,840 --> 00:05:51,420
就算宇宙中所有的原子
147
00:05:51,440 --> 00:05:53,179
每個原子都變成一個超級計算機
148
00:05:53,199 --> 00:05:55,420
從宇宙誕生之初算到現在
149
00:05:55,420 --> 00:05:56,079
你也不可能
150
00:05:56,079 --> 00:05:58,559
把100個城市的旅行推銷員問題算完
151
00:05:59,159 --> 00:06:01,559
所以暴力搜索這種方法
152
00:06:01,559 --> 00:06:04,239
理論上來講是可以找到最優解的
153
00:06:04,239 --> 00:06:05,340
我們稱之為準
154
00:06:05,599 --> 00:06:07,800
但是它實際上是不可行的
155
00:06:08,039 --> 00:06:09,599
因為它不夠快
156
00:06:10,239 --> 00:06:12,440
它的搜索複雜度太高
157
00:06:12,440 --> 00:06:14,559
以至於稍微問題複雜一點
158
00:06:14,559 --> 00:06:16,519
我們就沒有辦法得到最優解了
159
00:06:16,519 --> 00:06:19,059
所以這種方法基本上在現實中是不可以的
160
00:06:19,320 --> 00:06:20,059
是不可行的
161
00:06:20,260 --> 00:06:21,860
那麼有什麼更好的方法嗎
162
00:06:21,880 --> 00:06:23,980
比如說咱們換一個更快的方法
163
00:06:24,099 --> 00:06:29,139
這個方法人們叫它貪心算法 貪心算法
164
00:06:29,559 --> 00:06:30,820
之所以叫貪心算法
165
00:06:31,000 --> 00:06:31,900
是因為這種算法
166
00:06:32,039 --> 00:06:34,659
就非常像一個鼠目寸光的貪心的人
167
00:06:34,679 --> 00:06:36,260
他只能看到眼前的利益
168
00:06:36,699 --> 00:06:38,639
這個貪心算法的意思是什麼呢
169
00:06:38,659 --> 00:06:40,719
就是它每一次
170
00:06:41,159 --> 00:06:46,260
每一次都去這個機票最便宜的城市
171
00:06:46,780 --> 00:06:50,079
機票最低的城市
172
00:06:50,559 --> 00:06:53,760
每一次你面對著幾個城市去哪個呢
173
00:06:53,760 --> 00:06:56,280
你就去那個機票價格最便宜的城市
174
00:06:56,360 --> 00:06:58,920
也就是說每一次我都怎麼樣
175
00:06:58,920 --> 00:07:00,960
都找到了最優解
176
00:07:00,960 --> 00:07:03,639
我們每一次每一個步驟
177
00:07:03,739 --> 00:07:05,260
都是最優的
178
00:07:06,840 --> 00:07:09,260
我們看一下會發生什麼
179
00:07:09,380 --> 00:07:09,880
舉個例子
180
00:07:10,099 --> 00:07:12,119
你看 假如說我們從A出發
181
00:07:12,139 --> 00:07:13,920
那麼第一步你應該往哪走呢
182
00:07:13,940 --> 00:07:15,480
你往B走是3塊錢
183
00:07:15,500 --> 00:07:16,800
你往C走10塊
184
00:07:16,820 --> 00:07:17,880
你往D走5塊
185
00:07:17,900 --> 00:07:19,039
走誰 走B
186
00:07:19,139 --> 00:07:20,440
那麼因為你是貪心的
187
00:07:20,780 --> 00:07:22,760
你非常短視 所以你就走到B了
188
00:07:22,780 --> 00:07:25,400
因此這個貪心算法你應該從A
189
00:07:25,579 --> 00:07:28,039
第一步先到B 就花了3塊錢
190
00:07:28,139 --> 00:07:29,780
那麼到了B之後你往哪走呢
191
00:07:29,780 --> 00:07:30,539
你不會回A
192
00:07:30,860 --> 00:07:32,019
你會走C或者D
193
00:07:32,019 --> 00:07:33,980
一個6塊 一個7塊 選D
194
00:07:34,380 --> 00:07:36,099
因為D比較便宜
195
00:07:36,099 --> 00:07:37,420
他花了6塊錢
196
00:07:37,619 --> 00:07:40,280
到D了之後你面臨著只能走C了
197
00:07:40,300 --> 00:07:43,099
那因為你還要走所有的路徑再回去
198
00:07:43,300 --> 00:07:45,480
所以你要到C去 到C要花20
199
00:07:45,559 --> 00:07:46,760
這個時候沒有辦法
200
00:07:47,199 --> 00:07:48,760
因為你只剩一個C了
201
00:07:48,760 --> 00:07:49,719
最後C走完了
202
00:07:49,719 --> 00:07:51,360
你回到出發點就回到了A
203
00:07:52,199 --> 00:07:54,559
回到了A 那最後是花了10塊
204
00:07:54,639 --> 00:07:57,059
咱們來算一算這總共的價格是多少
205
00:07:57,079 --> 00:08:00,179
總共的價格是3+6+20+10
206
00:08:00,280 --> 00:08:02,639
一共是39元
207
00:08:03,440 --> 00:08:05,559
我每一步都是最優解
208
00:08:05,559 --> 00:08:07,039
但最終的結果是什麼
209
00:08:07,039 --> 00:08:10,360
我反而選了一個價格最高的路線
210
00:08:10,579 --> 00:08:11,880
這說明了什麼道理
211
00:08:11,960 --> 00:08:14,639
這說明在局部有最優解
212
00:08:14,639 --> 00:08:16,800
整體這個問題不一定是最優解
213
00:08:16,800 --> 00:08:18,600
一個精緻的利己主義者
214
00:08:18,600 --> 00:08:21,479
不一定會獲得一個成功的人生 對不對
215
00:08:21,560 --> 00:08:23,979
所以這種方法它很快
216
00:08:24,159 --> 00:08:26,739
你很快就能找到你想要走的方法
217
00:08:26,760 --> 00:08:27,939
但是它不准
218
00:08:28,260 --> 00:08:31,760
在某些情況下貪心算法也許是合理的
219
00:08:31,779 --> 00:08:33,079
但是也有很多問題
220
00:08:33,179 --> 00:08:35,719
用貪心算法基本上是得不到最優解的
221
00:08:35,859 --> 00:08:38,539
那我們能不能把這兩種方法稍微結合一下
222
00:08:38,539 --> 00:08:41,300
找到一種又快又準的方法
223
00:08:41,720 --> 00:08:43,500
可能準沒有暴力搜索準
224
00:08:43,520 --> 00:08:45,220
快也沒有貪心算法快
225
00:08:45,220 --> 00:08:46,619
但是它又快又準
226
00:08:46,640 --> 00:08:47,899
有沒有這樣的方法呢
227
00:08:47,979 --> 00:08:52,100
有 人們模仿生物的進化找到了一種遺傳算法
228
00:08:52,100 --> 00:08:53,220
咱們來擦一下黑板
229
00:08:53,640 --> 00:08:54,800
好黑板擦完了
230
00:08:54,800 --> 00:08:56,039
為了了解遺傳算法
231
00:08:56,199 --> 00:08:58,920
我們首先先來簡單的說一說
232
00:08:59,279 --> 00:09:04,119
生物學上的遺傳和變異到底是怎麼回事
233
00:09:04,420 --> 00:09:06,399
然後我們再來說一說這個遺傳算法
234
00:09:06,420 --> 00:09:08,800
是怎麼模擬這個生物的遺傳和變異的
235
00:09:09,500 --> 00:09:13,479
說到遺傳變異 我們得從達爾文說起
236
00:09:13,880 --> 00:09:16,520
達爾文以及其他的一些科學家
237
00:09:16,520 --> 00:09:18,479
提出了自然選擇的學說
238
00:09:18,960 --> 00:09:23,939
自然選擇或者我們也可以管它叫進化論
239
00:09:24,659 --> 00:09:26,220
這個自然選擇是怎麼回事呢
240
00:09:26,220 --> 00:09:29,600
它說生物有一個基本需求 那就是繁殖
241
00:09:29,720 --> 00:09:32,300
而且生物總是傾向於過度繁殖
242
00:09:32,720 --> 00:09:36,340
吃飽了就想生孩子 過度繁殖
243
00:09:36,680 --> 00:09:40,140
但問題是這個自然資源是有限的
244
00:09:40,159 --> 00:09:44,340
所以過度繁殖的結果就是會存在生存的鬥爭
245
00:09:44,760 --> 00:09:47,260
可能是種群內部的鬥爭
246
00:09:47,500 --> 00:09:50,979
也可能是種群之間甚至是生物與自然的鬥爭
247
00:09:51,060 --> 00:09:53,539
那麼這種生存鬥爭的結果是什麼呢
248
00:09:53,539 --> 00:09:56,979
就是有的生物會存留下來 有的生物會滅絕
249
00:09:56,979 --> 00:10:00,520
這是因為它們具有遺傳和變異
250
00:10:01,119 --> 00:10:01,920
遺傳和變異
251
00:10:01,920 --> 00:10:05,279
比如說有一些鹿它的脖子變長了
252
00:10:05,279 --> 00:10:07,159
有一些鹿脖子變短了
253
00:10:07,239 --> 00:10:10,100
脖子變長的就能夠吃到樹葉就活了
254
00:10:10,119 --> 00:10:12,220
脖子變短了 吃不到樹葉就死了
255
00:10:12,239 --> 00:10:17,979
所以就有了自然的選擇 自然的選擇
256
00:10:18,220 --> 00:10:23,340
那麼我們中國把它翻譯成物競天擇 對不對
257
00:10:23,340 --> 00:10:26,819
這個生物生存鬥爭 然後最後自然選擇
258
00:10:26,899 --> 00:10:28,899
選擇完了剩下的這些生物怎麼樣
259
00:10:28,899 --> 00:10:31,479
繼續過度繁殖 然後繼續生存鬥爭
260
00:10:31,500 --> 00:10:33,020
如此形成一個循環
261
00:10:33,020 --> 00:10:36,720
那麼在這個循環中遺傳和變異是非常重要的
262
00:10:36,920 --> 00:10:40,000
遺傳保證了子代都會長得像親代
263
00:10:40,000 --> 00:10:41,199
兒子長得像父母
264
00:10:41,199 --> 00:10:43,199
但是他又跟父母不完全一樣
265
00:10:43,659 --> 00:10:45,439
遺傳和變異究竟是怎麼發生的
266
00:10:45,579 --> 00:10:47,039
達爾文其實並不清楚
267
00:10:47,199 --> 00:10:50,140
這件事是由後來的孟德爾還有摩爾根
268
00:10:50,560 --> 00:10:51,739
他最早發現的
269
00:10:51,760 --> 00:10:55,439
孟德爾就是種豌豆的那個 孟德爾
270
00:10:56,119 --> 00:10:58,359
還有摩爾根就是養果蠅的
271
00:10:58,920 --> 00:11:00,960
這個在我們的生物書上
272
00:11:00,960 --> 00:11:03,680
都有提到他們兩個發現的規律
273
00:11:03,760 --> 00:11:08,140
我們都可以稱之為基因的重組 基因重組
274
00:11:08,340 --> 00:11:12,000
基因重組它也是變異的一種方式
275
00:11:12,100 --> 00:11:13,680
那麼孟德爾究竟發現了什麼
276
00:11:13,779 --> 00:11:15,359
如果用我們現在的話來說
277
00:11:15,579 --> 00:11:17,279
就是我們人有很多條染色體
278
00:11:17,300 --> 00:11:19,439
而且都是成對的 23對46條
279
00:11:20,060 --> 00:11:23,119
比如說父親他有一對染色體
280
00:11:23,279 --> 00:11:27,260
這是一對染色體叫做同源染色體
281
00:11:27,960 --> 00:11:29,800
在一個細胞之中 是不是
282
00:11:29,819 --> 00:11:33,319
然後這個母親也有同源染色體
283
00:11:33,460 --> 00:11:36,060
也有同源的染色體
284
00:11:36,420 --> 00:11:38,500
也是在一個細胞之中
285
00:11:38,500 --> 00:11:40,859
然後當他們進行繁殖的時候
286
00:11:40,859 --> 00:11:44,140
首先這些個細胞會復制一次 然後分裂兩次
287
00:11:44,140 --> 00:11:45,100
這叫減數分裂
288
00:11:45,659 --> 00:11:48,159
於是就會形成配子 形成配子
289
00:11:48,340 --> 00:11:50,779
父親形成的配子相當於是
290
00:11:50,779 --> 00:11:53,220
把這個同源染色體給分開了
291
00:11:53,300 --> 00:11:56,000
形成了這兩種不同的配子
292
00:11:56,020 --> 00:11:58,560
母親也是把同源染色體分開了
293
00:11:58,720 --> 00:12:01,260
形成了兩種不同的配子
294
00:12:02,119 --> 00:12:03,619
形成了兩種不同的配子
295
00:12:03,619 --> 00:12:05,619
然後這些個配子又可以怎麼樣
296
00:12:05,779 --> 00:12:08,060
又可以自由的組合
297
00:12:08,140 --> 00:12:10,680
也就是說孩子可以選擇父母各一條配子
298
00:12:10,699 --> 00:12:12,159
這個和這個合到一塊
299
00:12:12,500 --> 00:12:15,640
這個孩子他的這個基因就變成了這樣
300
00:12:15,659 --> 00:12:17,079
於是我們通常就說
301
00:12:17,380 --> 00:12:20,319
這個孩子一半的基因來自於父親
302
00:12:20,340 --> 00:12:22,479
一半的基因來自於母親
303
00:12:22,619 --> 00:12:24,100
孩子長得像父母
304
00:12:24,100 --> 00:12:26,579
但是又跟父母不完全一樣 對不對
305
00:12:26,579 --> 00:12:29,579
這個就是孟德爾發現的就是基因的分離
306
00:12:30,359 --> 00:12:33,779
自由分離和組合的規律
307
00:12:34,979 --> 00:12:39,420
所以父母他的基因會有一部分傳遞給孩子
308
00:12:39,619 --> 00:12:41,340
後來摩爾根又發現了什麼呢
309
00:12:41,420 --> 00:12:42,180
摩爾根又發現
310
00:12:42,340 --> 00:12:45,500
這個孩子的這一條染色體雖然來源於母親
311
00:12:45,500 --> 00:12:47,819
但是他很有可能跟母親也不完全一樣
312
00:12:47,920 --> 00:12:48,659
為什麼呢
313
00:12:48,680 --> 00:12:50,979
因為在染色體複製的過程之中
314
00:12:51,279 --> 00:12:54,659
這個兩條同源染色體它有可能會互相交換
315
00:12:54,680 --> 00:12:57,380
當然實際上是在四分體時候互相交換的
316
00:12:57,600 --> 00:12:59,039
我們可以大體這麼理解
317
00:12:59,060 --> 00:13:01,359
就是母親為了形成配子
318
00:13:01,380 --> 00:13:02,800
它的這個染色體要復制
319
00:13:02,819 --> 00:13:04,439
而在復制的過程中
320
00:13:04,460 --> 00:13:07,159
有可能同源染色體交換了一部分
321
00:13:07,260 --> 00:13:08,739
比如說我中間切開
322
00:13:08,819 --> 00:13:11,220
這一條跑這來了 這一條跑這來了
323
00:13:11,220 --> 00:13:13,939
於是母親形成的兩個配子是這樣的
324
00:13:14,920 --> 00:13:18,119
是這個樣子的 這個樣子的
325
00:13:18,340 --> 00:13:20,300
就是在形成配子的過程之中
326
00:13:20,659 --> 00:13:23,779
這個母親產生了兩條新的染色體
327
00:13:23,859 --> 00:13:26,460
這兩條新的染色體的每一個部分
328
00:13:26,460 --> 00:13:27,819
都來源於原來的染色體
329
00:13:27,819 --> 00:13:29,579
但它們因為彼此交換了
330
00:13:29,699 --> 00:13:31,479
所以長得跟母親是不一樣的
331
00:13:31,560 --> 00:13:34,439
然後假如說孩子從父親這繼承了一個染色體
332
00:13:34,439 --> 00:13:36,960
又和母親這個變了之後的染色體合起來了
333
00:13:37,420 --> 00:13:39,539
那麼它就會形成一個新的孩子
334
00:13:39,539 --> 00:13:42,460
而這個新的孩子裡邊他的染色體
335
00:13:42,899 --> 00:13:44,939
就和母親不完全一樣了
336
00:13:44,939 --> 00:13:47,899
因為它是母親經過互換
337
00:13:47,899 --> 00:13:49,979
染色體經過互換得到的
338
00:13:50,579 --> 00:13:52,000
這個就是第一個子女
339
00:13:52,020 --> 00:13:53,800
這就是第二個子女
340
00:13:53,800 --> 00:13:57,239
那摩爾根就發現了基因連鎖互換定律
341
00:13:58,039 --> 00:14:01,800
不管是分離和自由組合還是基因連鎖互換
342
00:14:01,800 --> 00:14:04,239
孩子的基因都跟父母不完全一樣
343
00:14:04,239 --> 00:14:05,760
這就稱之為基因重組
344
00:14:05,859 --> 00:14:08,699
基因重組的時候生物體就發生了變異
345
00:14:08,699 --> 00:14:10,819
可以把有利的基因積攢下來
346
00:14:11,439 --> 00:14:13,319
但同時基因除了重組之外
347
00:14:13,319 --> 00:14:15,800
其實還有一條叫做基因的變異
348
00:14:16,600 --> 00:14:19,279
就算你不考慮重組 基因也會存在變異
349
00:14:19,279 --> 00:14:22,199
變異的意思是我們都知道染色體上有DNA
350
00:14:22,199 --> 00:14:23,960
而DNA上面有基因
351
00:14:23,960 --> 00:14:25,920
基因就是鹼基序列
352
00:14:25,920 --> 00:14:30,800
比如說ATCGAT等等一系列基因序列
353
00:14:30,819 --> 00:14:34,760
變異的意思就是比如說這個T和C這兩個鹼基
354
00:14:34,779 --> 00:14:36,920
它們交換了位置變成CT了
355
00:14:37,340 --> 00:14:38,520
複製的時候出錯了
356
00:14:38,539 --> 00:14:42,119
或者中間有一個鹼基G它跑了
357
00:14:42,420 --> 00:14:45,439
或者這個A和T中間它又多複制的一個A
358
00:14:45,460 --> 00:14:46,680
重複了 對吧
359
00:14:46,680 --> 00:14:49,439
這些情況也會造成染色體的變異
360
00:14:49,439 --> 00:14:52,279
當然相比來講在我們人類身上變異比較少
361
00:14:52,279 --> 00:14:55,960
主要是這種基因的分離組合以及互換
362
00:14:56,399 --> 00:14:57,159
不管怎麼說
363
00:14:57,159 --> 00:14:59,800
人們從分子的角度理解了遺傳和變異
364
00:14:59,819 --> 00:15:01,039
究竟是怎麼發生的
365
00:15:01,060 --> 00:15:02,279
自然界就是這樣
366
00:15:02,300 --> 00:15:04,319
從一個原始的地球 原始的生命
367
00:15:04,340 --> 00:15:06,640
經過不斷的遺傳變異和自然選擇
368
00:15:06,659 --> 00:15:08,520
形成了今天豐富多彩的世界
369
00:15:08,520 --> 00:15:10,220
而我們的遺傳變異算法
370
00:15:10,220 --> 00:15:13,020
其實就是模仿了生物的這個過程
371
00:15:13,100 --> 00:15:18,380
我們來說說遺傳算法究竟怎麼樣解決
372
00:15:18,800 --> 00:15:20,199
旅行推銷員問題
373
00:15:20,840 --> 00:15:22,380
它和遺傳過程非常像
374
00:15:22,399 --> 00:15:25,260
首先你先要把這個問題初始化
375
00:15:25,380 --> 00:15:28,920
初始化的意思就是設置一個原始的生物
376
00:15:29,340 --> 00:15:31,960
初始化 有一個原始的種群
377
00:15:33,159 --> 00:15:34,359
初始化了之後
378
00:15:35,079 --> 00:15:39,279
下一步我們就要求個體的適應度
379
00:15:39,380 --> 00:15:42,539
個體的適應度
380
00:15:42,539 --> 00:15:46,060
就是看你這個個體它適不適合環境的生存
381
00:15:46,500 --> 00:15:48,300
如果你更加的適應了
382
00:15:48,300 --> 00:15:49,100
你怎麼樣
383
00:15:49,100 --> 00:15:51,060
你就發生遺傳
384
00:15:51,420 --> 00:15:52,579
你就發生遺傳
385
00:15:52,739 --> 00:15:56,819
然後你還有可能會發生變異 變異
386
00:15:57,140 --> 00:15:59,659
發生了遺傳和變異之後 怎麼樣呢
387
00:15:59,659 --> 00:16:02,819
我們要繼續去考察你的個體適應度
388
00:16:02,819 --> 00:16:03,859
適不適應環境
389
00:16:04,220 --> 00:16:05,819
然後繼續遺傳 繼續變異
390
00:16:05,819 --> 00:16:07,659
然後再繼續考察你的適應度
391
00:16:07,819 --> 00:16:10,699
最終我們認為你這個適應度已經足夠好了
392
00:16:10,699 --> 00:16:12,500
你這個解已經是我們所需的
393
00:16:12,500 --> 00:16:13,859
那麼我們就結束
394
00:16:13,939 --> 00:16:17,060
我們就找到了一個最優的路線
395
00:16:17,140 --> 00:16:18,260
那具體是怎麼回事呢
396
00:16:18,260 --> 00:16:19,020
我們舉個例子
397
00:16:19,020 --> 00:16:21,300
比如說一共有6個城市
398
00:16:21,779 --> 00:16:24,659
有一個旅行商他要去6個城市
399
00:16:24,659 --> 00:16:27,859
那麼你首先6個城市應該是有60種算法
400
00:16:28,140 --> 00:16:30,539
我們5!/2等於60
401
00:16:30,539 --> 00:16:31,779
你只要遍歷這60種
402
00:16:31,779 --> 00:16:33,579
你就能找到那個最好的方式了
403
00:16:33,579 --> 00:16:34,859
但是我現在不想那麼幹
404
00:16:34,859 --> 00:16:36,979
我想用這種遺傳算法 怎麼做呢
405
00:16:37,079 --> 00:16:38,880
我可以先設置一個種群
406
00:16:38,880 --> 00:16:40,880
比如說我先設置4個個體
407
00:16:40,880 --> 00:16:43,079
這4個個體其實就是4個路徑
408
00:16:43,079 --> 00:16:46,020
S₁等於比如1 2 3 4 5 6
409
00:16:46,039 --> 00:16:47,199
然後最後又回到1了
410
00:16:47,720 --> 00:16:51,680
第二個路徑是132654
411
00:16:51,939 --> 00:16:52,880
這也是一個路徑
412
00:16:53,279 --> 00:16:54,739
第三個路徑S₃
413
00:16:54,760 --> 00:16:58,100
比如說是什麼142635
414
00:16:58,439 --> 00:16:59,579
第四個路徑
415
00:16:59,600 --> 00:17:03,659
比如說是什麼162534
416
00:17:04,039 --> 00:17:06,560
不管 反正我們隨機的設這幾個路徑
417
00:17:06,579 --> 00:17:08,880
這就好像世界上的原始生命一樣
418
00:17:08,979 --> 00:17:10,699
然後我們就要計算它的個體適應度
419
00:17:10,699 --> 00:17:12,579
我們到底想考察什麼
420
00:17:12,579 --> 00:17:14,939
我們是想考察哪條路最短 對不對
421
00:17:14,939 --> 00:17:16,339
哪條路價格最便宜
422
00:17:16,339 --> 00:17:19,358
那麼我們把價格把它列出來
423
00:17:19,479 --> 00:17:23,859
價格 比如說第一條路價格是10元
424
00:17:24,239 --> 00:17:26,579
第二條路總票價是20
425
00:17:26,680 --> 00:17:28,880
第三條路總票價是20
426
00:17:28,880 --> 00:17:31,479
第四條路總票價是50
427
00:17:31,579 --> 00:17:34,640
我們看起來好像第一條路它價格是最低的
428
00:17:34,739 --> 00:17:37,340
但是你也不能確定它是不是最好的 對不對
429
00:17:37,340 --> 00:17:40,039
而且如果有一天兩個城市之間調了價格
430
00:17:40,060 --> 00:17:41,760
那第一條路很有可能變成最壞的
431
00:17:42,159 --> 00:17:45,100
那我們能不能去改進一下 找到更好的呢
432
00:17:45,340 --> 00:17:46,260
我們找它的適應度
433
00:17:46,439 --> 00:17:48,560
適應度就是價格越低越適應
434
00:17:49,020 --> 00:17:54,520
所以我們可以把這個適應度寫成f等於1/d
435
00:17:54,960 --> 00:17:57,840
我們把它叫做適應度 1/d
436
00:17:57,960 --> 00:17:59,760
就價格越低 適應度就越高
437
00:17:59,760 --> 00:18:01,260
所以第一個適應度是多少
438
00:18:01,279 --> 00:18:04,319
第一個路線適應度應該是0.1
439
00:18:04,319 --> 00:18:07,180
第二個適應度是0.05
440
00:18:07,319 --> 00:18:10,119
第三個適應度是0.05
441
00:18:10,220 --> 00:18:12,600
第四個適應度是0.02
442
00:18:13,180 --> 00:18:15,020
還是第一條路是最好的
443
00:18:15,340 --> 00:18:17,500
找到適應度之後下一步幹什麼呢
444
00:18:17,600 --> 00:18:19,079
根據遺傳學的規律
445
00:18:19,079 --> 00:18:22,960
適應自然界的就更有可能遺傳 對不對
446
00:18:22,960 --> 00:18:24,880
更有可能有下一代
447
00:18:24,960 --> 00:18:29,260
所以我們說適應度越高的越有可能會遺傳
448
00:18:29,520 --> 00:18:32,180
我們就讓它根據概率進行遺傳
449
00:18:32,340 --> 00:18:35,460
這個遺傳的概率怎麼算呢
450
00:18:35,840 --> 00:18:36,779
我們可以這樣算
451
00:18:36,779 --> 00:18:40,260
我們可以用每一個路徑的適應度
452
00:18:40,500 --> 00:18:43,399
再除以所有的適應度之和
453
00:18:43,600 --> 00:18:47,500
這就表示你的適應度在總體中所佔的比例
454
00:18:47,500 --> 00:18:50,119
你比例越高你就越有可能遺傳 對不對
455
00:18:50,119 --> 00:18:52,239
當然越有可能遺傳 他也不見得遺傳
456
00:18:52,640 --> 00:18:53,640
有很多優秀的人
457
00:18:53,640 --> 00:18:55,439
比如牛頓他就沒有後代 是不是
458
00:18:55,439 --> 00:18:56,260
這是有可能的
459
00:18:56,520 --> 00:18:58,159
那我們怎麼樣才能夠
460
00:18:58,260 --> 00:19:00,920
把這個問題用概率的觀點解釋一下呢
461
00:19:00,939 --> 00:19:01,840
我們可以這麼做
462
00:19:01,859 --> 00:19:04,239
畫一個圓盤
463
00:19:04,359 --> 00:19:06,340
在這個圓盤上標出一些區域
464
00:19:06,359 --> 00:19:09,260
比如說這個f₁這個概率是最大的
465
00:19:09,260 --> 00:19:10,180
適應度最高的
466
00:19:10,199 --> 00:19:12,619
那麼它的面積也就相應的是最大
467
00:19:13,079 --> 00:19:15,439
這個f₂和f₃的面積要小一點
468
00:19:15,439 --> 00:19:19,539
所以在這個盤子上 它的面積也就會小一些
469
00:19:19,659 --> 00:19:20,800
f₂和f₃
470
00:19:20,819 --> 00:19:22,720
這個f₄它是最小的
471
00:19:22,960 --> 00:19:25,039
所以在這個盤子上它的面積也是最小的
472
00:19:25,180 --> 00:19:27,319
然後我就用一個指針
473
00:19:27,420 --> 00:19:29,380
然後轉動這個指針
474
00:19:29,399 --> 00:19:31,100
讓這個指針在這個盤子上去轉
475
00:19:31,279 --> 00:19:34,699
轉的時候 一停下來 我就看它指向誰
476
00:19:34,779 --> 00:19:36,819
就是選擇誰進行遺傳
477
00:19:37,180 --> 00:19:38,979
指向誰就是選擇誰進行遺傳
478
00:19:39,000 --> 00:19:41,899
大家想一想那是不就是你的適應度越高
479
00:19:41,920 --> 00:19:43,579
你所佔的比例越大
480
00:19:43,680 --> 00:19:45,020
你越適合自然環境
481
00:19:45,020 --> 00:19:46,560
你就越有可能被選中
482
00:19:46,760 --> 00:19:48,140
當然這也不是百分百的
483
00:19:48,479 --> 00:19:49,859
像牛頓它就沒有後代
484
00:19:49,880 --> 00:19:51,380
像特斯拉它也沒有後代
485
00:19:51,840 --> 00:19:53,579
好 那麼我們假如說
486
00:19:53,760 --> 00:19:56,479
我第一次轉的時候我就選中了S₁
487
00:19:56,500 --> 00:20:00,079
那我選中了S₁ 選中了S₁
488
00:20:00,079 --> 00:20:01,539
我第二次又轉了一圈
489
00:20:01,560 --> 00:20:03,260
我就選中了s₂
490
00:20:03,279 --> 00:20:04,760
選完了之後怎麼樣呢
491
00:20:04,760 --> 00:20:05,840
進入下一個環節
492
00:20:05,840 --> 00:20:07,359
下一個環節叫變異
493
00:20:07,359 --> 00:20:08,920
我需要讓它進行變異
494
00:20:09,000 --> 00:20:10,000
變異分兩種
495
00:20:10,000 --> 00:20:12,260
第一種我們可以是交叉變異
496
00:20:12,279 --> 00:20:13,600
什麼叫交叉變異呢
497
00:20:13,600 --> 00:20:15,600
就是S₁和S₂這不是已經有了嗎
498
00:20:15,600 --> 00:20:17,359
相當於它的DNA片段
499
00:20:17,359 --> 00:20:19,539
我可以在中間某個部位我進行截斷
500
00:20:19,560 --> 00:20:22,119
比如說在中間3這個部位進行截斷
501
00:20:22,119 --> 00:20:25,479
然後讓它模仿摩爾根的這種基因互換
502
00:20:25,479 --> 00:20:27,680
讓這個片段和這個片段互換
503
00:20:27,760 --> 00:20:28,579
換完了之後
504
00:20:28,920 --> 00:20:32,939
這個 S₁'它就變成了123
505
00:20:32,960 --> 00:20:35,460
然後接下一段654
506
00:20:36,000 --> 00:20:38,960
然後S₂它就變成了什麼呢
507
00:20:39,180 --> 00:20:42,380
132 然後接上一段456
508
00:20:42,380 --> 00:20:45,020
這就是交叉變異
509
00:20:45,020 --> 00:20:47,699
當然了我們現在子代比親代少
510
00:20:47,720 --> 00:20:48,300
這個不行
511
00:20:48,520 --> 00:20:50,380
我們至少得保證子代和親代一樣多
512
00:20:50,399 --> 00:20:52,199
要不然傳幾代就沒人了 是不是
513
00:20:52,199 --> 00:20:53,720
所以我可能要再轉兩次
514
00:20:53,720 --> 00:20:55,239
比如說我又轉了兩次
515
00:20:55,239 --> 00:20:58,600
我們選出了S₁和S₄
516
00:20:58,600 --> 00:21:01,119
然後我們再進行交叉變異
517
00:21:01,199 --> 00:21:04,760
找到新的S₃'和S₄'
518
00:21:04,760 --> 00:21:06,840
當然在交叉變異的過程中
519
00:21:06,840 --> 00:21:07,779
有可能會有重複的
520
00:21:07,800 --> 00:21:08,840
我們要稍微處理一下
521
00:21:09,000 --> 00:21:10,220
具體過程我們就不講了
522
00:21:10,220 --> 00:21:12,760
所以我們通過這種辦法選出更加優秀的父母
523
00:21:12,760 --> 00:21:14,260
然後讓他們生出孩子
524
00:21:14,260 --> 00:21:16,779
而生出孩子之後還要進行基因的互換
525
00:21:17,220 --> 00:21:20,420
換完了之後我們再做一步就是變異
526
00:21:20,960 --> 00:21:21,960
變異是什麼呢
527
00:21:21,960 --> 00:21:24,039
就是模仿生物的DNA的變異
528
00:21:24,039 --> 00:21:25,220
我們可以舉個例子
529
00:21:25,279 --> 00:21:26,279
比如說這S₁'
530
00:21:26,479 --> 00:21:30,500
我們可以讓這個365我調個個
531
00:21:30,800 --> 00:21:31,699
讓它變成什麼呢
532
00:21:31,720 --> 00:21:36,260
S₁''變成12 然後5634
533
00:21:36,260 --> 00:21:38,260
就是把365這三個我調個個
534
00:21:38,500 --> 00:21:40,060
這是可以的一種變異方法
535
00:21:40,060 --> 00:21:41,140
還有什麼變異方法呢
536
00:21:41,140 --> 00:21:42,739
比如說我也可以讓兩個數交換
537
00:21:42,739 --> 00:21:44,300
比如說我讓3和6交換
538
00:21:44,800 --> 00:21:50,039
S₂''等於162453
539
00:21:50,239 --> 00:21:51,899
這也是一種方式交換
540
00:21:51,920 --> 00:21:53,220
或者是什麼其他的方式
541
00:21:53,239 --> 00:21:54,739
總而言之我做一點變異
542
00:21:54,880 --> 00:21:58,300
同樣S₃'' S₄''我們也做了
543
00:21:58,399 --> 00:22:01,319
這就是我們首先選擇了優秀的父母
544
00:22:01,319 --> 00:22:04,079
然後我們讓她生出的孩子進行一點變異
545
00:22:04,159 --> 00:22:06,359
變異完了之後變成什麼呢
546
00:22:06,359 --> 00:22:09,039
下一步重新計算個體適應度
547
00:22:09,039 --> 00:22:10,239
我要重新計算
548
00:22:10,239 --> 00:22:13,319
我得到的這些子代它的價格是多少
549
00:22:13,319 --> 00:22:14,800
以及它的適應度是多少
550
00:22:14,800 --> 00:22:18,220
然後我再進入這個輪盤重新進行迭代
551
00:22:18,220 --> 00:22:21,420
只要我最開始設置的種群數量足夠多
552
00:22:21,439 --> 00:22:23,340
我迭代的次數足夠多
553
00:22:23,340 --> 00:22:24,640
那麼我們就應該能找到
554
00:22:24,640 --> 00:22:26,600
那個接近於最優解的解了
555
00:22:26,600 --> 00:22:30,100
說到這大家是不是明白了我到底在講些什麼呢
556
00:22:30,180 --> 00:22:32,239
就是因為計算的資源是有限的
557
00:22:32,260 --> 00:22:33,960
所以對於這個旅行推銷員問題呢
558
00:22:33,979 --> 00:22:35,479
我們不可能暴力搜索
559
00:22:35,619 --> 00:22:38,239
所以我們就先隨機生成一些路徑
560
00:22:38,260 --> 00:22:39,800
然後通過計算適應度
561
00:22:39,819 --> 00:22:42,279
讓更好的路徑有更大的概率留存
562
00:22:42,359 --> 00:22:45,079
然後再通過適當的交叉變異一點點變化
563
00:22:45,079 --> 00:22:46,279
尋找更好的路徑
564
00:22:46,520 --> 00:22:48,319
相比於這個精確的暴力搜索
565
00:22:48,319 --> 00:22:49,920
這種算法效率要高得多
566
00:22:49,920 --> 00:22:51,560
而相比於這種貪心的算法
567
00:22:52,020 --> 00:22:53,840
這種方法的準確率又高得多
568
00:22:53,939 --> 00:22:56,560
最重要的事是即便是兩個城市之間
569
00:22:56,579 --> 00:22:58,000
機票價格發生了變化
570
00:22:58,020 --> 00:22:59,079
由於我有變異
571
00:22:59,100 --> 00:23:00,880
所以我還是能夠快速迭代
572
00:23:00,899 --> 00:23:01,960
找出更好的路線
573
00:23:01,979 --> 00:23:04,199
而不至於鎖死在某一條路徑上
574
00:23:04,279 --> 00:23:06,600
那麼這種算法具有自我更新的能力
575
00:23:06,600 --> 00:23:08,000
所以遺傳算法
576
00:23:08,000 --> 00:23:10,239
不僅僅是只能用在旅行者推銷問題上
577
00:23:10,239 --> 00:23:12,239
幾乎所有的多步驟複雜問題
578
00:23:12,239 --> 00:23:13,760
都是可以使用這種方法的
579
00:23:13,760 --> 00:23:15,359
我們回到生物學的問題上
580
00:23:15,439 --> 00:23:16,979
在地球剛剛形成的時候
581
00:23:17,079 --> 00:23:18,739
環境的變化是非常劇烈的
582
00:23:18,760 --> 00:23:21,819
自然界也不知道到底什麼樣的基因最適合環境
583
00:23:21,920 --> 00:23:25,239
於是自然界就設立了遺傳和變異的法則
584
00:23:25,239 --> 00:23:26,239
在這個法則下
585
00:23:26,399 --> 00:23:28,800
許多原始的生命在有限的自然資源下
586
00:23:28,800 --> 00:23:29,880
展開了競爭
587
00:23:29,979 --> 00:23:33,060
具有競爭優勢的基因就更容易遺傳 繁衍
588
00:23:33,060 --> 00:23:35,159
這就是物競天擇 適者生存
589
00:23:35,159 --> 00:23:36,699
當自然條件發生變化的時候
590
00:23:36,699 --> 00:23:37,979
多數生物會滅絕
591
00:23:37,979 --> 00:23:41,140
但是各種變異保證了生物體具有多樣性
592
00:23:41,140 --> 00:23:42,659
總會有少量的生物
593
00:23:42,659 --> 00:23:45,899
因為基因更適合環境而生存下來繼續繁衍
594
00:23:45,979 --> 00:23:46,899
病毒是這樣
595
00:23:46,899 --> 00:23:48,439
人類其實也是如此
596
00:23:48,539 --> 00:23:50,340
自然界正是通過這樣的方法
597
00:23:50,340 --> 00:23:52,380
才能保證生命的生生不息
598
00:23:52,659 --> 00:23:53,479
大家如果喜歡我的視頻
599
00:23:53,479 --> 00:23:55,319
可以在YouTube賬號李永樂老師裡訂閱我
600
00:23:55,319 --> 00:23:57,399
點擊小鈴鐺可以第一時間獲得更新信息
41925
