Facebook加入
LINE加入
2021/12/25
【獵雲網（）】6月25日報道
從古至今，「優化」一直是生產生活中重要的部分。運籌學作為優化演算法的重要根基，從第二次世界大戰時期就開始起源。二戰結束后，人們將運籌學引入各個領域，促進了經濟的加速發展。而如今，大數據和AI時代的來臨，又給運籌學帶來的新的生機。如何將大數據轉化為最優決策成為運籌學重點的課題。
昨天，獵雲網（）曾報道過的杉數科技在北京舉辦了一場AI論壇活動，杉數科技首席科學顧問葉蔭宇教授在活動上為在場聽眾帶來了題為《優化演算法的思想及其應用》的演講。葉蔭宇是斯坦福大學李國鼎講席教授，也是美國應用數學學會優化分會副主席，曾被評為美國科研成果最具影響力科學家之一，並曾獲得過美國運籌與管理學會馮•諾依曼理論獎。
在學習運籌學的應用之前，我們先來了解一下運籌學是什麼。
運籌學是一種尋找在滿足約束的條件下能夠最大化/最小化某一目標的最優決策。它有兩個關鍵步驟：1. 建模：將問題準確有效的通過數學形式表達；2. 求解：獲得最優化目標函數的決策。運籌學被廣泛應用在收益管理、路徑優化、選址問題、供應鏈優化、生產流程優化等問題方面。
具體在物流選址及路徑優化、庫存管理、投資組合優化三個問題上，葉蔭宇進行了詳細的闡述。
以下是葉蔭宇的演講全文，獵雲網編輯刪改：
我長期從事運籌學。我1982年剛到美國讀書的時候，AI非常熱，我就是差點那個時候搞AI了。但是AI那個時候年輕人不知道。那個時候就要搞所謂的「專家系統AI空間」。那個時候沒有很多數據，有些就總結不出來，AI就慢慢的冷下去了。我呢比較喜歡數學，就從事了運籌學。
運籌學是一種研究優化的學問，就是怎麼能夠在所有的實際生活中，把事情做到極值。不簡單是找一個可行的方案，而且是一定要找到最優的方案。
Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear. 那麼這種理論，也是基於自然形成，是在所謂的一個平衡態，也是能量函數，到了極值。
那麼說到運籌學，一個數學的學科怎麼能接地氣？怎麼落到實地？怎麼真正起到應用的對人們生活產生一些影響？於是數學家們就開始尋求這樣的方案。也有一些緊迫感，在二次大戰的時候，如何研究盟軍配置，還包括一些博弈問題，以前看過一個電影叫《Beautiful Man》，研究這個東西研究到博弈空間。
標誌性的結果就是1947年，George Dantzig提出線性優化，為優化中最經典的演算法。這就是里程碑的意義。之後用到經濟發展中，運籌學得到很快的發展，特別是計算機的高速發展。以前是結構問題，可能是要1小時，現在可能不到1秒就可以解出來。所以這個硬體的控制，也有演算法的提高。
運籌學比AI要老，但是AI和機器學習又提供了一種機會。很多頂層的東西都是要靠優化，不管是學習還是剛才講到的要用決策問題。
整個來說，所謂優化在滿足我們有很多要決策的，而且也都是需要比較量化的，滿足一定的約束條件下，使某一個函數最大，這就是優化問題。怎麼把一個問題變成這個東西，就需要建模。所以我們一般是從建模到求解，然後再到決策，然後我們就需要一套演算法來求解。
在這個裡面，把實際問題變成數學問題，再變成優化問題，然後來求解。
什麼叫大數據？有很多不同的這個解釋。數據大到一定程度以後，就可以量化了。那麼如果量化以後，我們可以用數學的方程、公式來描述它，然後來決策，讓它變成一個量化的決策問題。這個我覺得數據大再加上機器學習，把它刻畫的更加量化。
我1982年去美國中間經歷了AI，當時是最紅，後來冷下來，現在又熱起來了。有些當然是改變了，但是有些點我覺得沒變的。「優化」好像始終是不動點一樣。需要它，不管是你在各行各業，因為在這點上，也可以說起來像統計、數學還是一些機理。這裡面有很多演算法的問題，學習有很多深度的學習，MDP等等。
我個人認為，怎麼理解AI，特別是大數據時代的商務決策，各自所採取的作用，我們要用到很多計算機、信息學，包括機器學習，包括數據的搜集，然後我們要通過很多機器學習做一些規律性分析，然後就是建模、決策。
個人覺得這個過程有點像採集數據，然後搜集。從中醫的角度來說，有點像拉脈一樣，拉了脈以後老中醫有一個判決，什麼叫prescrptive，也就是決策，中醫來說就是開藥，開處方。在這個過程中，如何判斷準確，然後開什麼處方，開的好，這也是有區別的。
有些東西要用三錢有些東西要四錢。但是有些中醫搞的不好就是比較模糊，當歸少許這個就不清楚，我覺得日本人搞的比較好，就能夠把它刻畫出來，我到日本學習的時候，日本人教烹調非常非常的細緻，不是說少許，而是多鹽或者簡單說兩句。
所以這裡面是需要有一些量化、需求管理、規律性分析的。我覺得機器學習確實做的好。但是怎麼決策，這裡面都有一些很傳統的優化模型和運籌學的模型。
我給大家舉幾個簡單的例子，為什麼有些決策模型並不需要深刻的理解就可以得出來。
一、物流選址及路徑優化
比如說這個選址問題，尋求一個區域內最優的倉庫選擇，成本最少。我要建5個庫，建在什麼地方？那麼這裡面就要權衡很多。一次建設費多少？建設費之後我服務區域有多大？區域大了以後，人家很遠的地方跑過來，運輸成本就高了。
那麼這樣的問題怎麼選才好？以前的演算法，我就把它寫成一個整數規劃，就去算。現在不行。客戶的需求，好像有些演算法，像幾個月都算不出解來。現在很多東西，要隨時的，有些東西看成是網路，就要把這個點放在上面，進行隨時的調配，重新選址。
這個時候我的演算法就非常的快，然後就會有很多的近似演算法。這裡面我們也做過一些工作，這就是比較確定性的問題，這裡面的演算法，選址的問題，我們合作夥伴工作過程中有很多這樣的問題。
那麼有一個問題就稍微更複雜一點，不是選址，那麼選一個倉庫提供一個區域服務，但是這個是叫HUB的選址，有些不是從倉庫發到某一個顧客上，某一個是要經過中轉站，再到顧客上，比如說航班的調運問題。那麼這個中轉站怎麼選才好？有一部分有問題，這裡面就會有一些選擇。
通常我們把選址的問題，叫作戰略性的決策。一旦選了以後幾年都不會變。決策也分為戰略決策，戰術決策、operation 決策。而我這裡面是operation 決策。
我現在要送貨，送到這麼多的點上，如何都送出去然後回到出發點使整個距離最小？這叫什麼問題，旅行商問題。這個也是很經典的，很確定性的，比如物流公司物流公司都是在解決這個問題。
在整個地方因為又叫車輛調度問題，當然實際問題比這更複雜，一輛車不能跑可能幾千上萬輛車誰跑哪些地點，哪些區域，又怎麼選址，這裡面就非常非常複雜了，而且需要取貨，而且同時送貨，你取貨的話必須要保證某一個時間點上，或者時間窗口。這個就是運籌學比較擅長的問題。要非常實時的做這些問題。
這是一個簡單的解決方案，分而治之。我現在有5輛車，我要服務這個區域。首先就建立一個服務區的概念。怎麼把這個大的區域分成50份，每一個區域選擇一個分點，這個我們叫「區域選擇」，非常的大。
選了以後，我知道我在分這個區域的時候，每個區域的工作量都是什麼，盡量均勻，要不然我一個區域很大跑兩天跑不完，一個區域半天就跑完了。
這應用在實際問題中。大家看到了沒有，這裡面有50輛車，現在這個圖在做什麼？找路徑。這實際上是一個實際問題，原來是一個大的這個地理數據圖，那麼他的這個問題是每一個街道都要跑的。我再劃分這個區域的時候每個區域里街道的總長度是基本上相似的。
但是哪怕街道一樣，我要拿每一個顏色的這個就有這個車進去跑，我在跑這個區域的時候，怎麼跑到最大，把所有的街道都跑一趟，這個時候就有路徑問題。這個問題從優化、從運籌學說的時候，是研究很老的問題。要把每個街道都走一道，然後這各區域就完成了。這個主要是為了地圖公司。
美國有一個很有名的地圖公司，後來在諾基亞買的，我相信大家肯定用過GPS，是兩個核心技術，一個核心技術也就是衛星定位，經度緯度定位以後，所以的地理信息位置，都是搜集過來的。那麼街道的地理數據，城市在不斷的變，所以每次都要派一輛車或者用圖像的信息把街道的這個信息改變都要重新搜集進來，是要派一輛車把每個街道跑一道，上面就一個攝像頭，非常高效，然後全部搜起來，去做這個問題。
這個時候，每一個城市都要把這個街道跑一道的話，不可能跑一輛車可能50輛車，我們怎麼劃分這個車輛的區域，以前是用郵政編碼來分，由於城市的改變有些郵政編碼，有的會大好幾倍，這樣分就不合理，我們要根據這個瞬時情況進行分析。如何判斷有效，原來要用75輛車，現在60輛就夠了，原來用2天時間現在一天半，我們確實講25%到30%，這個技術被諾基亞還在用，全世界26個國家在使用。
我不知道大家剛才看到我在排序的過程中，在這個路徑過程當中大家也都沒有遇到，我原來認為我跑出來最後的路程最大，後來給我們提一個要求這裡面有多少是左轉多少的右轉，你能不能排路徑的時候，盡量向右轉。因為考慮的是要完成的時間，左轉所要花的時間，要比向右轉高5到10倍，因為有紅綠燈，所以我們用運籌學的辦法把這個解決掉。
再舉一個路徑優化的問題。大家都在搞所謂的無人倉。有一些小車搬運載有貨物的托盤到空閑工作台，然後小車搬運到托盤從工作台回到倉庫空儲位我們叫回庫。然後小車搬運空托盤從工作台到托盤迴收處，然後我們叫回收。這裡面都是一些貨櫃，怎麼拖起來怎麼用，又要路徑又要協調。
我覺得在我們國內研究機器人，研究的比較多提高每個機器人自身的能力。我覺得做的非常好。個人能力都非常好，但是我覺得我們國家，在很多問題上，缺少的通盤調配和安排。機器人那麼強，在一個團隊工作的時候是不是就很強了？
我們比較缺乏統籌的軟體決策系統，就像我們足球到個人能力很強，但是在一起就不行。很多情況下人都是這樣的。我們很注重個人能力的提高。人都不要輸在起跑線上。但是我覺得我們國家，長期缺乏一種集體的統籌，這樣決策的開發。或者能力的提高。
每個機器人都在瞎跑的話肯定不行，包括無人車。很多公司都在考慮無人車的技術多強，但是其實最主要的問題是什麼？反而是無人車之間的協調、調配和統一指揮。
比如說，這裡面是工作台，把某一個區域的這個貨，貨來了以後，然後我們來分擔。整個的這個貨品的分擔，這裡面有很多很多的問題。我們在研究過程中，比如說這裡面的路徑。我剛才說，是路徑有了以後，怎麼找路徑，從設計上來說，你是設計成單行線還是雙程線，這裡面有學問講的，如果設置單行線跑的距離要長，碰撞的可能性就少一些，這裡面都可以通過優化來進行解決。
例如我們和某電商合作夥伴進行物流倉統籌調配，其中也都是演算法算出來的。比如機器人怎麼配到貨櫃，怎麼收檢這個站，這個方法目前是用機器人去托盤，拖這個貨櫃，把整個的貨櫃用到旁邊的這個台上，然後又把這個拿下來，再把托盤送回去。
我們人就很喜歡把國外的東西搬過來，首先是機器人，把整個的貨櫃拖起來，可能那個貨櫃員就檢一個東西下來，那麼為什麼說貨櫃不動，而且貨源坐在機器人身上然後去檢貨呢，可能人需要多一點，但是貨櫃可以裝的更高了，空間利用率更高了。
我覺得我們大家可以想到一些更好的，但是這套技術可以用，而且人坐在這個機器上，不僅前後移動還可以升降貨櫃可以放更高，運行過程中形成三位的倉庫而不是平面的倉庫。這樣我們就可以計算出來，包括貨的這個密度，增加多少，倉庫的利用率可以增加多少，那麼對於像我們國家，人力相對比較便宜，但是房非常貴，是不是就更好一點，但是整個也是靠產品運輸來優化問題進行求解。
從優化的模型下，各種各樣的這個決策，還有演算法，我在國內跟工業界接觸也有一段時間。工業界總是覺得我們需要深度學習，需要機器學習，需要把預測的精度再提高1%。我覺得有時候忽略了一點，有個測不準定理，到一定時候不可能提高的。有一個不確定的這個規律在那。
如果你能100%，那預測股市，股票市場存在一兩百年，也沒有人預測股票市場怎麼樣，所以在測不準的情況下，在決策上是不是可以做點工作。在知道測不準，可能有不同的狀況出現的情況下，我的決策是不是可以調整一下。
從數據到決策，我們是不是也可以做一些工作。比如說，我可以保證我在期望值省時一些，但是我保證永遠不會破產，防備那些惡性大事件發生。所以這些模型在OR應用到很多的。
比如說路徑優化ponyplus，我把一個任務，今天要派10個單，給到一個送貨員，就搞一個輔助工具，怎麼去路徑最好，排了一個，這裡面都有這樣一些工具。
二、庫存管理
這裡面最典型的問題就是庫存。我怎麼能夠把局測做到最好，把庫存做到最好，以前早的時候還沒有深度學習。比如你是小零售商，你進貨進多少，進一個星期的貨，多的有多的損失，少的有少的損失。所以這個時候運籌學就有一套方法來處理這個問題。
最近大家是否聽說過沒有美聯航上面有一個人，因為機票賣多了，上了飛機被人拖下去，後來是賠了幾個億。為什麼說這是典型問題？是不確定環境下的決策。
飛機上座位是固定的300個，你事先只賣300張票，不會賣多，來的人都可以登記。問題是總有5%到10%的人，因為各種各樣的原因是不會來的。那麼你賣300張票，5%到10%是不會來，那麼那部分就會損失。所以航空公司一般都會多賣一點。
這個道理是一樣的，它也要權衡。它知道有些人不來，我怎麼多賣幾張，最好的是有些人不來，不來的人數正好是我多賣的人數。但是永遠是測不準的，也就出現美聯航的這個問題。
一般我們這個決策是什麼，業內通過拍賣的形式，你願意乘坐下一次航班，給你多少錢，美聯航說到600塊錢就不向上提，所以我們要找一個權衡，多賣幾張最好。
這點我們做過很多實際案例，特別是在我們國內比較大的電商里，幫他安排，通常周轉率在29天的，那麼現在降到16.5%。庫存的金額大家也都知道，零售商最怕的就是庫存周轉率太低。買了人家的東西自己又賣不出去，庫存金額降19.2%，現貨率提升了，GMV上升1.9%，而周轉天數下降到16.5%，就是說我們主要是降低了這部分人力，在不損失這兩個標準的情況下。大家比較容易理解。
還有一個辦法，根據某一個電商的特點，叫閃購，出一份貨賣一個星期就不賣了，那麼這個時候他們通常這個電商把那個星期的預測，需要備多少貨就決定下來。
我們採取兩階段的策略，首先我有一個總的估量，但是我發貨的時候是發3天的貨，通過第一天的銷量我再決定追不追貨。不知道大家聽懂了沒有，本來一周的需求量是100，我實際送到前沿倉庫送60件，頭一天的這個銷量是夠，我是否需要把這40件補上去就看第一天的銷量，第一天的銷量對後續的這個預測度就更高。
王曦也是我們斯坦福的學生，現在是杉數的這個產品經理。設計了一個叫stockgo，根據我們跟電商還有其他接觸的這個規律，我們覺得應該給每一個中小電商，至少提供一個可能的工具，觀察庫存的這個周轉來確定，幫助他決策。
這裡面有很多的功能，比如說對目前庫存狀態的量化評估，對高精度的銷量預測，高精度的補貨策略，供應鏈管理的智能化轉型，這裡面包括很多的機器學習的工具還有深度學習的工具，對你的庫存狀態進行評估，精確到每一個SKU。還有補貨策略，以及個性化的全雲端的解決方案，也可以直接把數據傳送到杉數，然後幫你進行診脈。
總的目的是，把這些OR的東西對經濟起大作用，這是已經在跟很多ERP的公司法給他們使用，通常周轉率會提高到50%，資金及人力成本降低，電商自動化庫存能力也都是在提高，這是一個小工具，到了時候這些所謂的東西能夠為廣大的小電商服務。你也可以自己調整，但是至少給了你一個可能性。
三、投資組合優化
最後我就講一講根據我講的東西，最近還研究一些投資組合，也就是防範風險。
這裡面很多情況有一個叫markowitz，叫現代投資前沿理論，這個markowitz也是在我們斯坦福工作過一段時間，把投資組合的問題寫成一個二代規劃，它的目標函數不是線性函數是二次函數，所有的約束也都是線性。如何解這個問題解的最快。
這個時候我們就有很多的問題，那麼這個模型為什麼出現了二次函數呢？大家知道在統計中，二次的X的平方通常描述你的變化量，通常我們需要波動不太大，這就是簡單的這個二次函數，實際上要解的也就是二次規劃，常見的軟體，barra、axioma、ITG、mosek，mosek等
那麼在交易過程當中，你的演算法你的求解器別人家快一些，我個人認為高頻交易的競賽也就是演算法速度的這個競賽。我知道國內有就有用到過這樣的模型，自己解需要解10秒鐘的時間。從10秒到0.04秒，這裡面有演算法的模型。
FICO也是二次規劃的問題，很多很多大數據公司，越來越重視優化，我個人認為美國最早的大數據公司就是產生FICO的一家公司，國內是叫徵信打分，就是最早的一個公司把個人所有的信息收集起來給這個人的信譽打一個分，我1982年去美國要租房子到銀行開款，人家就必要FICO，我說我是來的沒有，到美國租房要擔保首先就是看這個FICO，打這個分。
這個公司後來做的很好，大家都用他的FICO，也就提供這個服務，包括在網上查一查這個徵信也都要交錢，這是美國很早的大數據公司，收集很多公司對每個人也都有打分。就是我說的英國優化公司，就被這個FICO公司買下來，在大數據處理中需要優化，能力需要加強。
這裡面剛才我提到，我個人呢，也跟包括杉數我們也跟美國美國運通公司做了很多，信用卡消費什麼東西，你如果消費了什麼東西，把前期的這個還上，你沒什麼，要還不上就加利息，我總跟人家講運通公司是合法的高利貸公司。
國內有些高利貸公司可能就是比較野蠻。但是他是比較合法的，利率確實比較高。那麼他的資源是什麼，他的核心技術是什麼就是防範風險，希望你消費但又希望你不要還錢而且希望你還錢不要還得太快，但是又不希望你永遠不還。
當時在運通公司我們幫他工作的時候有一個專門的團隊就搞這個的。也是一個大數據公司，特別是個人的一些數據在那個時候沒有英特網的時候，有比信用卡交易紀錄的更多的數據，也都是這個數據來進行識別。具體項目我不清楚了。
有一個就是我們幫他搞了一個怎麼追債，運通公司信用卡如果三個月連續不還錢，人家不還錢不能雇殺手卸個脖子什麼的，所以必須要通過合理的方法，博弈、心理學，很複雜的過程。所以有一些和追債公司聯合起來一起搞。
很多是基於演算法的，國內公司搞的這個AI非常熱，趨勢跟隨很緊，在有些問題上結合特色進行研究和開發。我個人在AI革命過程中，我看到體制的這個優點。
為什麼呢，也就是說文化的優點，怎麼說呢，你過AI這個問題，說句實話，深度學習這一塊還是有很多理論依據，深度學習本身這個過程有點像我們中醫，有什麼問題它很有效，但是真正說出一個道道來還說不出來，有的時候也不是100%的準確，但是準確起來非常好，一個癌症病人吃了幾副葯好了，怎麼解釋，解釋不了，所以我覺得特別適合的這個文化，不問原由只看效果，西方在這塊反而比較保守的。
所以我就說相當來說數據公開比較自由，像美國大公司數據絕對不會給你的，所以我覺得為AI開闢了很多前途。
但是發展過程中忽略了演算法的力量，他們通常是以問題為根本，找了一些參考資料在開源軟體中找一個演算法進行試一試，這是要花非常大的這個功夫，確實是要耐得住寂寞，但是要用人家的開源軟體的話，人家不給源代碼的話永遠會被牽著鼻子走。我知道其實他們很需要線性規劃或者說其他的運營規劃。但是你要買人家，出於安全考慮也不行。
比如說CPLEX，mosek，現在有些大學，包括財經大學，包括藍老師，還有杉數科技，不光是做實際應用，也培養自己的演算法開發，這樣的話就比較有核心技術了。真正的成為技術公司而不是諮詢公司。
所以大家投資要是很有錢的話，要耐得住寂寞，要有核心的技術等等這樣的一些東西。
未來的話，我覺得真是AI、深度學習和機器學習提供了很多的支撐，模型規模也飛速增長，因為需要超大規模的優化演算法，以前我認為我就要搞出個萬能的演算法，解所有的線性規劃都要解得快，但是我後來反觀看AI人的思維他不是，他是非常定製的。
我可以什麼方法對某一類方法用的好就用那個方法，不是追求某一個統一的演算法，或者類別法。反而是比較定製化的，用化來講比較實用主義一些。不一定追求理論上的完美，有一個統一的演算法，所以這點上，我覺得反過來，AI對我們的這個東西有很大的促進，什麼問題需要什麼樣的演算法，本身需要學習的過程。
還有一個問題，我們以前比較重視凸划，大量的問題是非凸規劃。集群化，軟硬體結合，如何利用GPU實現并行運算，包括應用在智慧供應鏈、智能金融、健康管理等領域，我對我們國家的挂號系統，有很多很多的問題能不能採取更好的這個方法，這樣的話對大家都有好處，這個東西，我們在OR叫排序。
總的來說我是搞運籌因為也是搞優化的，1982年到現在也大半輩子看到學術研究的起伏變化，我原來比較重視理論，很多問題都是寫文章，證明一些東西，也小有成就，但是人到年紀大的時候維護自己工作利益所在我覺得最大的利益還是對一般人生活產生一些影響。誰也不知道那些理論證明的結果有什麼東西。
我仔細想，那些用ponyplus 的人，你證明不證明我可能還是用這個方法，這就是到一定年齡的時候，就追求鼓勵這些年輕人，不光是有一定的學術造詣，把自己的學術成果轉化成技術，對人的基本生活產生影響，這才是OR的本質。
OR是一個接地氣的科學，是一個落地的科學，怎麼落地不能雲里霧裡說了嚇死人，經過我們的試驗還有杉數這些年輕人都是從斯坦福回來的學生，像深度學習、機器學習確實對京東這些也都產生一些影響。
所以我就希望大家多支持我們推動使得的企業，從一個比較粗狂的形式進一步拓展依賴於大數據、國際技術來進行決策的環境裡面。
本文來自獵雲網，如若轉載，請註明出處：http://www.lieyunwang.com/archives/328653
熱門推薦
留言回覆
