你玩過(guò)魔方嗎?
小小的正方體上布滿六種不同的顏色,看似旋轉(zhuǎn)翻飛眼花繚亂,卻總會(huì)在某個(gè)瞬間完成驚喜變身。魔方作為一種益智玩具,不僅老少皆宜,更是風(fēng)靡全球,實(shí)力堪稱指尖上的藝術(shù)。
但你知道嗎?現(xiàn)在不僅人類在玩,連AI機(jī)器人也加入了這個(gè)游戲陣營(yíng)。
看似簡(jiǎn)單的小小魔方,你知道它的顏色組合有多少種嗎?
4325 億億種
無(wú)論什么樣的顏色組合,最少需要多少次才能保證他們都能復(fù)原?
20次
大家可能也聽(tīng)說(shuō),玩得好的人都知道魔方的還原口訣(類似獨(dú)孤九劍的口訣)。據(jù)數(shù)學(xué)大神們說(shuō),世間所有的事物背后都有相應(yīng)的數(shù)學(xué)方程去表示或者控制,何況游戲!
其實(shí),魔方所涉及的基本數(shù)學(xué)理論就是組合最優(yōu)化。今天,我就給大家分享一下組合最優(yōu)化的基本知識(shí)及工程應(yīng)用。
01
什么是組合最優(yōu)化?
通俗地講,組合最優(yōu)化研究的問(wèn)題就是討論在眾多的組合方案中,什么樣的方案最優(yōu)以及如何找出最優(yōu)方案;
學(xué)術(shù)地講,組合最優(yōu)化是一個(gè)重要的數(shù)學(xué)分支,即通過(guò)對(duì)數(shù)學(xué)方法的研究去尋找事件的最優(yōu)編排,分組,次序或篩選等,其一般數(shù)學(xué)模型是:
其中f(X)是目標(biāo)函數(shù),g(X)是約束函數(shù),D是定義域。
02
抽象數(shù)學(xué)表達(dá)式具體化
組合最優(yōu)化領(lǐng)域有很多經(jīng)典的例子,它們通俗易懂,很適合鍛煉人的數(shù)學(xué)思維能力,好多奧數(shù)競(jìng)賽的題目就來(lái)源于他們。
比如說(shuō)“旅行商問(wèn)題”:一個(gè)商品推銷員要去若干個(gè)(n)城市推銷商品,該推銷員從一個(gè)城市出發(fā),需要經(jīng)過(guò)所有城市后,回到出發(fā)地,應(yīng)如何選擇行進(jìn)路線,才能使總的行程最短。初看起來(lái)很簡(jiǎn)單,窮舉所有可能性的路線,選擇最短的那個(gè),對(duì)于n很小的情況,小朋友都能夠理解,也很容易;但對(duì)于n比較大的情況,窮舉遍歷法就不可行了。
這是一個(gè)普通人都能秒懂的問(wèn)題,卻也是至今仍未被完全解決的數(shù)學(xué)和計(jì)算機(jī)界難題。除此之外,還有背包問(wèn)題,匹配問(wèn)題,排序問(wèn)題等等,如果誰(shuí)能夠想清楚這些問(wèn)題,那數(shù)學(xué)思維能力應(yīng)該是杠杠的。
03
組合最優(yōu)化——AI的引擎
AI是個(gè)很熱的話題。一方面,最優(yōu)化可以說(shuō)是AI的引擎,AI問(wèn)題幾乎都能轉(zhuǎn)化為求解能量/損失函數(shù)的優(yōu)化問(wèn)題,AI模型訓(xùn)練的過(guò)程就是以損失函數(shù)最小化為目標(biāo),采用梯度下降的方法不斷更新模型參數(shù)的過(guò)程;
另外一方面,AI深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)技術(shù)也為求解組合最優(yōu)化問(wèn)題提供了新思路,即組合最優(yōu)化的序列決策可以由深度學(xué)習(xí)或強(qiáng)化學(xué)習(xí)來(lái)替代,求解組合最優(yōu)化的經(jīng)典算法可以由強(qiáng)化學(xué)習(xí)幫助指導(dǎo)算法策略,甚至已經(jīng)有了專為組合最優(yōu)化求解而誕生的神經(jīng)網(wǎng)絡(luò)Pointer Network。
04
掌握組合最優(yōu)化,讓生活和工作乘風(fēng)破浪
組合最優(yōu)化是一門(mén)應(yīng)用廣泛、實(shí)用性很強(qiáng)的學(xué)科,也是一種可以改善生活、提高工作效率的有力工具。
例如,在理財(cái)投資中,如何進(jìn)行投資組合才可以實(shí)現(xiàn)收益最大化;在芯片設(shè)計(jì)過(guò)程中,一個(gè)計(jì)算機(jī)芯片需要多少層才能使得同一層的線路互不相交;在運(yùn)輸調(diào)度領(lǐng)域,采用什么樣的列車(chē)調(diào)度方案可以最大化整個(gè)鐵路系統(tǒng)的運(yùn)行效率;在城建規(guī)劃中,如何安排工廠、超市、住宅、學(xué)校、醫(yī)院等單位的布局,才能有利于城市的平衡發(fā)展;在生產(chǎn)計(jì)劃安排中,采用什么樣的方案才可以實(shí)現(xiàn)利潤(rùn)最大化。
大到國(guó)家政策,中到企業(yè)戰(zhàn)略,小到個(gè)人選擇都或多或少地涉及到組合最優(yōu)化。甚至可以說(shuō),我們的生活和工作一直在潛意識(shí)地進(jìn)行著最優(yōu)化組合求解,系統(tǒng)的學(xué)習(xí)和訓(xùn)練會(huì)讓這個(gè)過(guò)程更高效便捷。
05
我是一名工程師,在博世有哪些工程項(xiàng)目會(huì)用到組合最優(yōu)化?
目前博世正在如火如荼地進(jìn)行數(shù)字化轉(zhuǎn)型探索,生產(chǎn)部門(mén)有大量的場(chǎng)景和數(shù)據(jù)等待挖掘,比如產(chǎn)線合理排班,貼片機(jī)貼片順序等都有可能涉及到組合最優(yōu)化。
而工程部的業(yè)務(wù)主要是跟設(shè)計(jì)相關(guān)的,比如說(shuō)PCB的布局與布線設(shè)計(jì),機(jī)械結(jié)構(gòu)件的設(shè)計(jì)等等。這些設(shè)計(jì)工作嚴(yán)重依賴工程師的經(jīng)驗(yàn),似乎很難進(jìn)行數(shù)字化優(yōu)化。設(shè)計(jì)工作就是在滿足一定約束條件下,設(shè)計(jì)完成某些功能的過(guò)程,對(duì)這進(jìn)行高度抽象,不就是組合最優(yōu)化問(wèn)題嗎?
在PCB板設(shè)計(jì)結(jié)束后,要對(duì)板子上的某些元器件進(jìn)行保護(hù)層設(shè)計(jì)和保護(hù)層噴涂。目前設(shè)計(jì)依賴設(shè)計(jì)工程師的設(shè)計(jì)經(jīng)驗(yàn),噴涂路徑依賴產(chǎn)線工程師的經(jīng)驗(yàn)及其反復(fù)調(diào)試,其缺點(diǎn)是依賴專家經(jīng)驗(yàn),項(xiàng)目周期長(zhǎng)。
如果能根據(jù)組合最優(yōu)化原理開(kāi)發(fā)一種PCB元器件保護(hù)層自動(dòng)設(shè)計(jì)軟件,幫助設(shè)計(jì)工程師優(yōu)化保護(hù)層設(shè)計(jì),幫助產(chǎn)線工程師優(yōu)化噴涂路徑,提升工作效率,那將是極好的。
于是我們有了下圖設(shè)計(jì):
通過(guò)使用我們提供的自動(dòng)化設(shè)計(jì)軟件,項(xiàng)目的交付時(shí)間將縮短85%以上。這可以看作是數(shù)字化過(guò)程中典型的案例,利用組合最優(yōu)化技術(shù)極大地提升了設(shè)計(jì)人員的工作效率,也提升了噴涂的生產(chǎn)效率。
除此之外,還有PCB的設(shè)計(jì)工作,如何借助組合最優(yōu)化及AI技術(shù)幫助PCB設(shè)計(jì)工程師快速布線和布局是一個(gè)有意義但極具挑戰(zhàn)性的問(wèn)題,這也很值得探索。
總之,組合最優(yōu)化涉及到我們生活的各個(gè)方面,掌握組合最優(yōu)化不僅使我們能玩好魔方,而且能豐富我們的生活和工作的思路,更能直接提升工程師的工作效率。
-
工程師
+關(guān)注
關(guān)注
59文章
1587瀏覽量
69187 -
芯片設(shè)計(jì)
+關(guān)注
關(guān)注
15文章
1062瀏覽量
55444 -
AI
+關(guān)注
關(guān)注
87文章
34101瀏覽量
275206
原文標(biāo)題:揭秘組合最優(yōu)化——從魔方到工程設(shè)計(jì)
文章出處:【微信號(hào):AE_China_10,微信公眾號(hào):博世汽車(chē)電子事業(yè)部】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
VirtualLab Fusion應(yīng)用:參數(shù)優(yōu)化文檔介紹
如何優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)率
自動(dòng)排產(chǎn)系統(tǒng):如何實(shí)現(xiàn)生產(chǎn)計(jì)劃優(yōu)化的關(guān)鍵策略

繼電器組合及組合架的作用
25G/28G重定時(shí)器與轉(zhuǎn)接驅(qū)動(dòng)器在常見(jiàn)應(yīng)用中的最優(yōu)化實(shí)現(xiàn)

量子計(jì)算場(chǎng)景實(shí)用秘籍:開(kāi)物SDK之“高階函數(shù)降階”

多級(jí)運(yùn)放級(jí)聯(lián)如何安排運(yùn)放放大倍數(shù)才能讓信號(hào)質(zhì)量最優(yōu)噪聲小?
優(yōu)化 FPGA HLS 設(shè)計(jì)
組合邏輯電路的結(jié)構(gòu)特點(diǎn)是什么?
“本源悟空”真機(jī)應(yīng)用之金融科技領(lǐng)域——投資組合優(yōu)化應(yīng)用

評(píng)論