病毒为何不停变异？旅行推销员问题和遗传算法
Вставка
- Опубліковано 21 лип 2024
- 【加入会员链接】 / @tchliyongle
【订阅频道链接】 / 李永乐老师
------------------------------------------------
视频内容：
病毒为何不停变异？生命是如何进化的？这个视频中，我通过一个经典的数学问题：旅行推销员问题，为大家介绍了遗传算法：通过保留优质基因，并附加一点点变异，求解一个复杂的数学问题。看完这个视频你一定会慨叹：大自然就像一个绝顶聪明的数学家，通过遗传与变异让各种生命能够适应不断变化的自然环境，生命如此生生不息。
------------------------------------------------
内容章节：
00:00 病毒变异
00:50 旅行的推销员
02:24 暴力搜索
06:25 贪心算法
09:00 遗传变异
15:15 遗传算法
22:27 内容总结
------------------------------------------------
相关视频推荐：
“冠状病毒”是什么？新型肺炎病毒是如何使人生病的？
• “冠状病毒”是什么？新型肺炎病毒是如何使人生病的？
正常夫妻为啥也能生色盲孩子？
• 正常夫妻为啥也能生色盲孩子？李永乐老师带你了...
什么是杂交？遗传学之父孟德尔和他的豌豆杂交实验
• 什么是杂交？遗传学之父孟德尔和他的豌豆杂交实验
------------------------------------------------
火热视频推荐：
如何才能摆脱贫穷？穷人和富人有什么差别？
• 如何才能摆脱贫穷？穷人和富人有什么差别？【2...
120万一针的抗癌神药为啥这么贵？
• 120万一针的抗癌神药为啥这么贵？免疫疗法C...
100亿美元造的詹姆斯·韦伯空间望远镜望到底能干啥？
• 100亿美元造的詹姆斯·韦伯空间望远镜望到底...
如何推翻相对论？广义相对论的建立和实验验证
• 如何推翻相对论？广义相对论的建立和实验验证
【经济泡沫1/4】一朵花换一栋楼？
• 【经济泡沫1/4】一朵花换一栋楼？疯狂的荷兰...
追剧买VIP会员去广告，值不值？
• 追剧买VIP会员去广告，值不值？李永乐老师讲...
神奇的鲁伯特之泪：子弹打不碎，一捏就爆炸
• 神奇的鲁伯特之泪：子弹打不碎，一捏就爆炸
千万不要用微波炉烧水！李永乐老师讲过热/过冷液体
• 千万不要用微波炉烧水！李永乐老师讲过热/过冷液体
5G到底是什么？它能成为创造未来的新科技吗？
• 5G到底是什么？它能成为创造未来的新科技吗？
如何才能长生不老？生命的时钟在哪里？
• 如何才能长生不老？生命的时钟在哪里？
------------------------------------------------
大家有什么想看的内容，可以在下方留言！ - Наука та технологія
这个时代的科技至少促进了更好的教育公平，感谢永乐老师!
老師真是全方位了不起！
“一个精致的利己主义者，不一定能得到一个成功的人生”--李老师牛逼，赞！
贊👍
太对了！
在影射上海吗
秦始皇不是成功了吗？
一定是成功率最大的
感谢李老师让我复习一下，大学时用代码实现过遗传算法，不过早就忘记了，记得正是由于变异的存在才会让结果不会陷入到局部最小值的，才会最后收敛到最小值
下学期正好要上遗传算法这门课！本来听上过这门课的同学说这课很难，还有点后怕。李老师讲得如此清晰，顿时有了信心👍🏻👍🏻
重复别人的成果，无有半点自己的东西，中国式的复读机器，不会有什么真贡献，为什么留在中国的都不是真正的人才，中美差距的原因大约在此，拿别人的东西来卖弄有什么好佩服的，李伪君子
李永樂老師還利用了旅行推銷員問題的解答演練方法，分別介紹了數學「階乘運算與符號 ！」「方程式 function , 與符號 f(x)」與概率 Probability 的數學計算方式。
備註：
如果選擇壓力過大，基因算法會過早收斂, 導致答案遠離最優解
如果變異程度過大, 算法會變為類似窮舉法, 靠運氣來找最優解
還有當路徑過多時，基因算法是無法準確找到最優解的, 通常會遠離最優解一些
相似的算法還有蟻群算法
它們和分組(K-Means)及神經算法是AI的入門介紹
又開眼界了！謝謝！
臥槽 我發現我比較笨 給您點讚 雖然我一點都不懂
不懂๑_๑
選擇壓力過大是指比例差距過大嗎?
能否麻烦解释什么是选择压力过大？
我還在李老師您的視頻裡，看到那種喜歡實事求是按部就班的求解答仔細慢慢做事情的態度的自己，卻總是因爲這種追求完美的牛步而影響了身邊很多講求效率用「貪心法」解決問題的同伴們產生衝突。所幸，您的遺傳變異概率演算法，為我提供了充滿希望的「最優解」！一個非常好的寓意！更優秀的下一代給我們無窮的愛、信心與盼望！願上帝大能聖潔慈愛的恩典，透過李永樂老師的工作，為人類社會的健康、自由、和平、真善美的社會，開拓一條福音滿滿，充滿信、望、愛正能量的道路。
李永樂老師的視頻內容總是以解答一個生活上會遇到的問題開始，用古聖先賢累積的人類智慧，從生物學、物理學、化學、音樂、文學、史學與美學等等思維架構中，用科技、經濟、實務經驗與數學原理原則綜合運算的方法，提出「最優解答」的教案建議。
这是我看过最好的旅行推销员解说
很精采的解说。到最后也离不开用‘’或然率probability‘’的过程出结果。这种(f=1/?)的加权方式，可再延伸和满足考虑更多的选择条件，除了提及的旅行价格，还有耗用时间和地区潜在风险，都可计算了。
李老师你真的幸亏没当科学家 我们大多人遇到的老师就是明明一样的知识 但讲出来也不清楚的 这就是您效用最大化的岗位 天选之师啊 西瓜的团队也是棒棒哒 强强联合效果翻倍
自然界的动植物大多不具备改造环境的能力，所以要靠适应环境和大量繁殖来增加生存概率。人类社会中，人不仅会适应环境和生育繁殖，更会创造环境，比如科学技术文化商业。像牛顿、特斯拉甚至达尔文本人，他们个体的繁殖力并不高，但他们的贡献提高了人类长期生存的机率。不能拿自然进化论的标准（比如适应力和繁殖力）来决定优劣。
他们都是工蚁，再牛逼的工蚁也是蚁皇的消耗品。。。🤣
人类不能叫改造环境，是叫破坏环境
旅行推销员，好怀念啊，瞬间回想起初中信息奥赛的日子。当时老师用这个问题讲过回溯和动态规划。
不愧是永乐大典啊，本科时期参加的数学建模比赛都不可避免地会用到遗传算法。
老師的影片一定要專心看。邊煮飯邊聽，等於沒聽😂
只聽到 吃飽了就想生孩子⋯😏
主婦的難處。
我也是邊切菜邊聽。
当然。边煮饭一边听的那是新闻。
太酷了 這次講到基因演算法 特別有感覺
這種在自然界中隱藏的數學 最早是誰想要這樣算的？
感谢李老师解说遗传算法，以前看过排课系统，对遗传算法一知半解，今天一听懂了一大半
看完您的视频，也喜欢看评论。愿老师健康，平安。
老师的这期视频干货满满👏👏
一个精致的利己主义者 不一定会获得一个成功的人生
但一个随波逐流 更容易被时代吞没
深有体会
但一定不是最悲惨的
@@junwang6791 从视频那个例子看来，还真可能是最惨的……
利有所不取，祸有所不避。
实际上普通最短路径问题是具有贪心完备性的，即局部最优可以推导整体最优，但是图算法稍微变一下就能完全颠覆算法内核，实在是太复杂了
太棒了，把复杂的问题简单化👍
从自然法则中获得灵感
李老师，我看了您的视频后，研究了一下旅行推销员问题，也在网上找了相关的论文，发现有一种矩阵删减算法可以有效地找出最优路线，自己也举例进行了计算，发现如果将这个思路用编程语言来实现，是可以自动找出最优解的
如果只以价格为衡量标准，C-D 之间距离是20， 可以以B为中介 C-B-D (7+6=13 < 20)
正確！但，尚有時間成本。
这次的课很有启发，暴力寻求极端最优解并不是好方法！而是因地制宜，不断寻求、更新、迭代更好的方案才是既能适应现实又能进取的办法！
如果暴力求解能在可接受时间范围内得出结果的话就是最优秀的办法。
@@zzzyyy5034 这个问题有确保得到最优，且比暴力快的多的算法。很少有问题是必须暴力求解的。
@@allenhu1744 TSP 是 NPC 的问题，现在即使有快一些的办法也不会比暴力好多少
@@CLEOOLD 还是好一些，纯暴力能算的规模还要小很多。
@@allenhu1744 我昨天解了一个NP Hard问题，可惜草稿弄丢了 😂
原来秘密都建立在海量随机试验，我们由于变量太多看不到的规律通过各个变量对最优解影响度的底层概率通过海量随机试验，规律都会浮出水面。多谢李永乐老师，这么抽象的跨界概念（数学，统计，生物，机器学习算法）讲得这么清楚。
立正敬禮！向李永樂老師致敬！李永樂老師實實在在的一位能傳道、授業、解惑的一等一的良師！您用一道旅行推銷員的問題，演練了「暴力法」、「貪心法」與「遺傳變異法」的過程，示範「正反合，三步解題最優方法學」，從能準確但實際運算速度太慢的「暴力法」與能很快給出未必準確答案的「貪心法」困境裡，用「遺傳變異學」來推論出能稍快的速度、找出最大概率的「最優解」。
李老师，交叉变异（重组）的规则是什么呢？具体来说如果S2（132654）与S3（142635）生孩子，假如选择中间进行截断，产生了子代142654。其中4重复了两次，应该怎么理解呢？
高中生物有“等位基因”这一概念，遗传算法是否也有对应的概念？
算法的自我更新能力。。。太完美了
感谢分享
李永乐老师厉害从运筹学讲到遗传学!
讲得非常好
感谢李老师
Travelling salesman Problem (TSP）是优化学（Optimization) 其中一类
“最重要的是即便两个城市之间机票价格发生了变化，…找出最好的路线，而不至于锁死在某一路径上”
又学习了，太爽啦
Traveling salesman is a CLASS of NP complete problem. We Engineer use Hopfield Networks to solve this type of problem
李老师加油，
偉大的李老師
能講一下變速箱AT，CVT，
雙離合原理嗎。
这个问题能够用遗传算法的基础是权值（机票价格）的分布某种程度上有相关性，如果是完全随机的且跳动幅度巨大，那么遗传算法也不会收敛。简单地说就是每一条路径的价格综合都完全随机（=n个随机数之和）。
謝謝老師
果然宇宙奥秘的表达是数学，而生物遗传变异为我等不懂数学的人举了个浅显生动的例子，让我了解了这个数学问题，甚至隐隐感受到宇宙运行的某些规律
李老师，请您讲讲元宇宙是什么概念，好嘛？最近很多公司口号喊的很大声，担心😔被忽悠，谢谢李老师！
其實就是VR版的我的世界，不過他最終目標是想做到真的一樣
不懂就不要参与就好了
第一个旅行推销员问题，如果机票重新定价，是否有可能重复走去过的城市反倒会总价更便宜？
感觉是不是还有更好的算法？虽然不太懂这个
已经知道所有路线的价格，还有这个组合是有规律的，每个数字只能出现一次（除了第一个），且每个路线的价格只会利用一次。
那就先把所有价格列出来，从低到高去找理论的最小值：
比如老师说的一、里面那个问题，所有价格分别是：3 5 6 7 10 20，理论上飞4次的最小值是21，然后他的序列是a-b a-d b-d b-c，能连起来的最多只有a-b b-d d-a（前后可互换），显然不符合我们的要求（连续走4地在返回）。
这样就再找下一个理论最小值：3+5+6+10=24，序列是a-b b-c b-d a-c，最多连是a-b b-c c-a，也不行。
下一个：3+5+7+10=25，也不行。
下一个：3+6+7+10=26，也不行。
下一个：5+6+7+10=28，a-d b-d a-c b-c，就可以连起来了：a-d d-b b-c c-a，结论是每个字母出现了2次。
这样一个模型放到计算机里，感觉可以比较快的算出来需要的多地连续旅行问题
李永乐老师，是真的牛人
李老师能否讲解一下 蛋白质折叠预测的原理
好谢谢
老師，能不能出一期證明矩形的視頻（上課沒聽懂）😂😂
弱弱地问一下，李老师在B站或者其他网站，有没有开讲？
谢谢老师!
如果变异后，父母节点位置的生物有意的帮助自己的子节点位置的生物呢？
我發現李老師的頭會向右傾斜，請老師注意，久一點後沒糾正，恐會造成脊椎側彎喔！
脊柱侧弯要是有小时候就有了 但是肩周炎什么的可能会40 50岁找上门
我懷疑你在論政，但是沒有證據
20:10 S1 和 S2 可以截断交叉变异，S2 和 S3 怎么怎么交叉变异呢？可以通过算法出 S2 的 _3__54 和 S3 的 _4__35 交叉变异，但不巧的是它们的其他片段都是 1_26__，所以没有效果。但我感觉一般情况下，染色体越长，出现这样可交换片段的几率越小，所以这个算法基因长了不一定有用。
需要去重，这一步操作我没有演示
李永乐老师写字定律：前几个字粉笔头基本要断一回
李老师，您能可以针对‘’人工免疫算法‘’录一个课吗？感谢！
老师厉害🎉
非常感谢，老师深入浅出，触类旁通的讲解。但遗传算法部分，没有讲解的很清楚。
你就暴力算法抽樣一千次找最優解就好，以現在在的算力找一萬次也都可以，該解就有足夠信心水準是真正最優解，即使存在更低成本路徑，遺傳變異算法也不會更有優勢，它是受限資源的小樣本大學習模式抽樣演算法。
生命科學本就是複雜科學，耗散系統下的負熵揀擇過程，為什麼物質自然走向熱寂均衡無所謂，生命卻非得指向生存最大化打死不退，這才是更高層次的問題。
李永乐老师，请问旅行者问题的核心是步步优化不能带来全局优化。请问这个思想可能被用来战胜AlphaGo吗？AlphaGo的核心就是每一步都取当前情况下的最优，也就是步步优化。有没有可能设计一个圈套，让AlphaGo中计，从而人类战胜AlphaGo呢？
赞赞赞，病毒和人类彼此共存，就是互相更适应环境而生存的最终自然法则。
前提是，这个病毒得是天然产生的
想到一個解法，Pij的意思為從節點i走向節點j的價格，X為無法通過的路徑
步驟：
1 從全域最高價格M1開始，將M1替換為X
2 以M1為中心的十字區域內，判斷是否只剩下一個空格不是X
2.1 如果是，將X恢復為M1後尋找次高價M2，繼續執行步驟1~2
2.2 如果否，尋找次高價格M2，繼續執行步驟1~2
3 執行步驟1~2，直到找不到最大價格(Mi)為止，即為最經濟路線的地圖
證明：
1.判斷是否只剩下一個空格不是X，是則恢復Mi，即在十字內產生唯二不是X的空格，也就是唯一的路徑
2.重複刪除全域最大值，可確保任一十字範圍空格的路徑和為最小值
唯一路徑，且路徑和為最小值，即為最優解
粗估此算法將N個節點的複雜度N!降為N^2
这个类似于用BFS做maxflow？ 我觉得套个算法把flow capacity从正数变成负数就行？
老師一開始的算法忽略了一種 就是可以先回到a以後再去別的 比如我一開始想的a b c a 之後再到d直接來回a 這樣也才30塊 也接近最優解 所以有可能其他路線的話這樣能找到更佳解
Abcada? 這不是和一開始的條件不一樣了嗎，，，
@@user-pj2iw7ui2x 怎麼說
一但回到A則路徑結束，你的思考完全錯誤，因為你的da 很明白地告訴大家你在d回到a，所以條件不合
自己搞不清楚前，別說什麼忽略這種笑話啊，，，
@@user-pj2iw7ui2x 但是前面老師沒規定只能在最後回到a 中途不可經過a 只問最便宜 若這樣有錯可能是老師條件沒說清楚
以前作業研究必學題目
這樣的方法帶入公式 跟當季的人工計算的代數與未知數的數據機內有倍數裕宮因屬的基數 不能夠為偶數的基因 來代表未知數 算出基本的最大公因數為誰的位置
充分说明，适应环境与是否优秀根本是两码事。一个人适应环境并不代表他有多优秀。所谓的进化只不过是适应环境的变异保存了下来。进化并不是那么神奇的词语。
@brian lee 不错。更加了解了。
有段时间没看李老师的视频，发现老师又帅了，字也更好看了。
老師好，
以下的問題，不單讓我愈想愈湖塗，甚至不知道應該歸類為邏輯問題還是地理問題。故此請教李老師或知道答案的高明。
1如果我人站在北極正中央的位置上，我的周圍還有沒有東南西北呢？
2假設還是在上述那位置上，隨便指出一個國家或城市，問在什麼方向，答案是否都是南方呢？如果是，那麼這些國家或城市，不都應該排列在一條直線上？可是事實並非如此嘛！那麼答案該是什麼呢？
謝謝。
1. 相对于你的位置来说，依旧有东南西北，若我们是以地球的正前方为参考系，则会认为你周围的方向有南，东南以及西南方。这单纯是一个视角问题，既是逻辑也有关系到地理。
2. 可以用1.的想法来解，这道题的关键在于选择参考系与视角，因为地球是椭球体，不能以常规的平面视角来解。
有没有这种可能性 存在一个N的系数 来确定贪心算法的步数 获得最优 比如 6个城市 算两步 20个城市算4步 来获得近似值
老师什么时候讲讲如何彻底消除病毒的问题
老師已經很委婉地說了：病毒無法被消滅
以后可以考虑使用light board
这个按概率抽取的步骤有点MCMC里面的Gibbs sampler的感觉
就是一样的东西吧 没看出区别
老師，聽完後，竟然腦補又觸類旁通了。
太厉害了👍
第一离李老师这么近
謝分享
老师开始讲计算机的算法了：）太牛了
nb，oi里有个算法叫随机化搜索，但我没有学过，不知道是不是就是这个？
我的硕士论文里面，设计极化码的frozen bit的位置就用到了genetic alg！李老师赞！
我感觉贪心算法跟极化码的listing解码算法有点像
这期有点跳跃啊，在我看来这个算法和遗传学完全没有关系，碰瓷啊，倒是有点像随机森林，谢谢李老师的科普。
随机森林是利用多个不可靠系统建立可靠系统，和这个差距还是很大的
旅行推销员问题在实际中考虑的多不是较少的旅资而是较少的旅行时间和途径，而随机变量也会被简化很多（试试？）
老师我错了，以后看视频不喝酒了。看时热血沸腾，饶有兴致；看完啥也不记得。
种豌豆的、养果蝇的，太会抓记忆点了哈哈哈哈
老师好👍👍👍
给硬核的李老师点赞
自然界真是人类最好的老师啊
惊了，我居然看李永乐老师讲程序员的算法了。这玩意之前还刷过LeetCode。😂
我怀疑Lee215是李永乐老师的leetcode账号
算法导论
李老師令我明白
李永乐老师瘦了一点感觉更加精神了
想起了以前学生时代的课
李老师说过 让子弹再飞一会儿，飞到何时啊？您何时出个视频解释一下到底拜登曲线符不符合原理？
全部生命體都自認有意識，仍然嘗試用維度來定義世界的位階，明明基礎力已經解答了命運軌跡這個概念，始終是物質層面，包括能量本身都是受限是原始單位的控制，極限一定會出現的，但是人還不承認知識所帶來的極限，依靠邏輯運作，創立新的概念來推動舊式定義，單道思維和多道思維的概念同等，卻是用道數來决定意識，還是仍為邏輯為必然，世界趨向穩定但同時物質是趨向極點到崩壞，相互的矛盾是在於相對角度而論，平衡世界和弦理論的概念都只不過是用他角度觀察，0至最大化能波觀察的角度所形成的邏輯會出現變化，但是同時唯一受着的是原始極限控制，所運行的路徑都是真理性相同，但是可以叫作另一維度，什至是宇宙，弦理論所講的0能量裂分上下單弦，形成能量態，構成物質概念一，只是使用0能波觀察，我們要追求的不是0能波，也不是上下弦的反弦，而是突破觀察極限啊，相對論所指出的一個重點是要突破可觀極限，只有基礎力和能量態是完全不成，反而是深陷極點，被意識知識論限制。
老師可以找王心冉一起錄幾集節目嗎 期待啊
这个遗传算法，什么时候能判断到底是不是最优解呢？还有说永远只能得到相对的最优解？
不同问题不同判断。如果是一个NP complete问题，那就可以通过一个polynomial run time algorithm 来算是否是最优解。如果是NP hard问题，那你不管用什么办法来判断最优解都不好使。
我当年的论文就有用到遗传算法，而且当年是把蚂蚁算法和遗传算法结合，组成了病毒蚂蚁，证明两种算法结合比单独的一种算法更优。
瑞士人威爾遜愛德華茲
爱德华先生，瑞士政府很担心你，请你快点前往大使馆一趟啊😋
请教一下，旅行推销员问题用最短路径算法有什么问题吗？
@@mapleafstoronto3862 这个问题本身并不复杂，难度来源于随着城市数量的增长，解决方案的数量呈现指数级增长，那么求问题最优解变的实际不可行，于是各种算法的目的就成为在一个合理的时间内找到近似最优解。
@@user-ul8iz2sf5q 搭日本鐵道前經常會先使用‘如何最最快到達’＝谷歌地圖走捷.
讲完算法最后附上代码就完美了
李老師真的是上知天文下知地理，講任何科目都可以講得這麼清晰！長知識了！
基因重组不能认为是进化，生物本来就具有的多样性，能根据不同的环境能显示出不同的性状。基因库里本来就有的，不是进化得来的。
看到6：00 我猜李永樂要講 「遺傳演算法」 GA