制造智能技術(shù)基礎(chǔ)FOUNDATION

OF

MANUFACTURINGINTELLIGENT

TECHNOLOGY第1章概論

第5章深度學(xué)習(xí)第2章智能優(yōu)化技術(shù)

第6章知識(shí)工程第3章模式與圖像識(shí)別

第7章商業(yè)智能第4章模糊控制

第8章總結(jié)與展望

第1章

概

論智能技術(shù)簡介1.1智能技術(shù)在智能制造中的應(yīng)用本章小結(jié)1.21.31.1.1智能技術(shù)的定義1.1.2人工智能的關(guān)鍵技術(shù)1.1.3智能技術(shù)的發(fā)展歷史1.1智能技術(shù)簡介

智能技術(shù)是在計(jì)算機(jī)科學(xué)、控制論、信息學(xué)、神經(jīng)心理學(xué)、哲學(xué)、語言學(xué)等多種學(xué)科研究的基礎(chǔ)上發(fā)展起來的一門綜合性的邊緣科學(xué)為了有效地達(dá)到某種預(yù)期的目的,利用知識(shí)所采用的各種方法和手段智能技術(shù)隸屬于通過現(xiàn)有計(jì)算過程來解釋和模擬人類智能活動(dòng)的研究領(lǐng)域人工智能致力于使機(jī)器智能化,智能化是衡量實(shí)體在特定環(huán)境中的反應(yīng)和判斷能力的定量指標(biāo)人工智能是計(jì)算機(jī)科學(xué)或智能科學(xué)中涉及研究、設(shè)計(jì)和應(yīng)用智能機(jī)器的一個(gè)分支,是用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)1.1.1智能技術(shù)的定義

智能技術(shù)主要包含智能優(yōu)化算法(問題求解、進(jìn)化計(jì)算、群智能計(jì)算、免疫計(jì)算等)模式與圖像識(shí)別(模式識(shí)別、計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)視覺、生物特征識(shí)別等)模糊控制(模糊計(jì)算)深度學(xué)習(xí)(神經(jīng)網(wǎng)絡(luò))知識(shí)工程(專家系統(tǒng)、知識(shí)圖譜等)商業(yè)智能(數(shù)據(jù)挖掘、信息檢索與推薦等)1.1.2人工智能的關(guān)鍵技術(shù)

1.智能優(yōu)化算法的發(fā)展智能優(yōu)化算法的共同點(diǎn):通過模擬生物群體的智能行為以及揭示某些自然界現(xiàn)象。模擬退火(simulated

annealing,SA)算法1953年提出。1983年,求解組合最優(yōu)化問題。遺傳算法(geneticalgorithm,GA)20世紀(jì)60年代提出,80年后,遺傳算法進(jìn)入實(shí)用階段。蟻群優(yōu)化算法(antcolonyoptimization,ACO)于20世紀(jì)90年代初期提出。1998年之后,高水平研究成果涌現(xiàn)。粒子群優(yōu)化(particleswarmoptimization,PSO)算法1995年提出，運(yùn)用到廣泛的領(lǐng)域。差分進(jìn)化(differential

evolution,DE)算法1995年提出,是解決復(fù)雜優(yōu)化問題的有效技術(shù)。近幾十年，智能優(yōu)化算法的發(fā)展已經(jīng)進(jìn)入了較為成熟的階段1.1.3智能技術(shù)的發(fā)展歷史

2.模式識(shí)別的發(fā)展1929年,G.Tauschck發(fā)明了能夠閱讀數(shù)字0~9的閱讀機(jī),就此拉開了模式識(shí)別的序幕。20世紀(jì)30年代Fisher提出統(tǒng)計(jì)分類理論,奠定了統(tǒng)計(jì)模式識(shí)別的基礎(chǔ)。Noam

Chemsky在1956年提出了語言描述理論;在1957年,ChowChi-Keung提出了用統(tǒng)計(jì)決策理論求解模式識(shí)別問題1962年,R.Narasimhan提出了一種基于基元關(guān)系的句法識(shí)別方法;美籍華人付京孫(K.S.Fu)提出了句法結(jié)構(gòu)模式識(shí)別,同時(shí),20世紀(jì)60年代,L.A.Zadeh提出了模糊集理論,模糊模式識(shí)別理論也得到了較廣泛的應(yīng)用。1973年,IEEE組織了第一次關(guān)于模式識(shí)別的國際會(huì)議(ICPR)20世紀(jì)80年代,Hopfield提出神經(jīng)元網(wǎng)絡(luò)模型,形成了模式識(shí)別的人工神經(jīng)元網(wǎng)絡(luò)方法的新學(xué)科方向。進(jìn)入20世紀(jì)90年代以來,新方法大量涌出,理論研究和應(yīng)用研究涌現(xiàn)。

1.1.3智能技術(shù)的發(fā)展歷史

3.模糊控制的發(fā)展模糊控制系統(tǒng)是以模糊集合論、模糊邏輯推理和模糊語言變量為基礎(chǔ)的一種計(jì)算機(jī)數(shù)字控制技術(shù)。1965年,美國自動(dòng)控制理論專家L.A.Zadeh創(chuàng)立了模糊集理論。1968年提出了模糊算法的概念,在1970年提出模糊決策,并在1971年提出了模糊排序。1973年,提出用模糊IF-THEN規(guī)則來量化人類知識(shí)。

1974年,模糊控制論的誕生。1976年之后，應(yīng)用模糊控制成功應(yīng)用。到了20世紀(jì)90年代初,市場上已經(jīng)出現(xiàn)了大量的模糊消費(fèi)產(chǎn)品。

1992年,首屆IEEE模糊系統(tǒng)國際會(huì)議召開；1993年創(chuàng)辦IEEE模糊系統(tǒng)會(huì)刊。模糊系統(tǒng)與模糊控制在20世紀(jì)90年代迅猛發(fā)展進(jìn)入21世紀(jì),模糊控制的應(yīng)用范圍向新領(lǐng)域擴(kuò)展,例如工業(yè)制造、自動(dòng)控制、汽車生產(chǎn)、控觸系統(tǒng)、醫(yī)藥、游戲理論等。1.1.3智能技術(shù)的發(fā)展歷史

4.深度學(xué)習(xí)的發(fā)展

深度學(xué)習(xí)是近十幾年來機(jī)器學(xué)習(xí)領(lǐng)域發(fā)展最快的一個(gè)分支。1943年,最早的神經(jīng)網(wǎng)絡(luò)數(shù)學(xué)模型：McCulloch-Pitts

Neuron結(jié)構(gòu)。1958年,前饋式人工神經(jīng)網(wǎng)絡(luò)“感知器”,引起了神經(jīng)網(wǎng)絡(luò)研究的第一次浪潮。1969年發(fā)現(xiàn)了感知器的缺陷,整個(gè)神經(jīng)網(wǎng)絡(luò)的研究進(jìn)入停滯期1986年,提出反向傳播算法—BP(back-propagation)算法，迎來了深度學(xué)習(xí)技術(shù)的第二次研究熱潮。2006年，提出了深度學(xué)習(xí)的概念,帶來了深度學(xué)習(xí)技術(shù)的第三次研究熱潮。2016年,AlphaGo以4∶1的比分戰(zhàn)勝了圍棋世界冠軍,深度學(xué)習(xí)的熱度一時(shí)無兩。1.1.3智能技術(shù)的發(fā)展歷史

5.知識(shí)工程的發(fā)展1956年通用問題求解器(general

problem

solver,GPS),可證明定理和進(jìn)行邏輯推理。1965年,Robinson提出了歸結(jié)原理,使定理證明向前邁進(jìn)一大步。1968年,Feigenbaum和Lederber合作,研制了世界上第一個(gè)專家系統(tǒng)DENDRAL。從20世紀(jì)70年代開始,通過“知識(shí)庫+推理機(jī)”實(shí)現(xiàn)機(jī)器智能。1974年,以Minsky提出的框架理論為代表的新知識(shí)表現(xiàn)形式理論廣泛流行1977年,提出了“知識(shí)工程”這一概念。20世紀(jì)80年代,具有應(yīng)用導(dǎo)向的專家系統(tǒng)集中出現(xiàn)并且逐步商業(yè)化。20世紀(jì)90年代以后,大量專家系統(tǒng)被廣泛應(yīng)用到各行業(yè)。例如，英文WordNet,Cyc常識(shí)知識(shí)庫,以及中文的HowNet。2006年開始,自動(dòng)構(gòu)建知識(shí)庫。當(dāng)前自動(dòng)構(gòu)建的知識(shí)庫已成為語義搜索、大數(shù)據(jù)分析、智能推薦的強(qiáng)大資產(chǎn),在各個(gè)領(lǐng)域中均得到廣泛使用1.1.3智能技術(shù)的發(fā)展歷史

6.商業(yè)智能的發(fā)展1958年,首次描述了商業(yè)智能的價(jià)值。1988年,在意大利羅馬舉辦的數(shù)據(jù)分析聯(lián)盟會(huì)議是商業(yè)智能的里程碑。1996年,高德納咨詢公司正式提出了商業(yè)智能的定義:根據(jù)準(zhǔn)確的最新信息制定合理的業(yè)務(wù)決策不僅僅需要直覺,關(guān)鍵在于利用數(shù)據(jù)倉庫、數(shù)據(jù)挖掘和在線分析等技術(shù)對(duì)經(jīng)營數(shù)據(jù)進(jìn)行分析研究從而合成有價(jià)值的信息,這些工具統(tǒng)統(tǒng)屬于商業(yè)智能類別。到了20世紀(jì)90年代末,商業(yè)智能包含兩個(gè)基本功能:生成數(shù)據(jù)和報(bào)告,并以可視化的方式展示。進(jìn)入21世紀(jì),時(shí)效性問題得以解決,進(jìn)而允依據(jù)最新的信息快速做出決策。到2010年年底,67%的一流公司都有某種形式的自助服務(wù)(self-service)商業(yè)智能。2010年以后,商業(yè)智能成為跨某著名企業(yè)業(yè)以及中小企業(yè)中所有人的標(biāo)配工具。目前商業(yè)智能已經(jīng)可以跨多個(gè)設(shè)備,并可以完成可交互式的分析推理。1.1.3智能技術(shù)的發(fā)展歷史

1.2智能技術(shù)在智能制造中的應(yīng)用1.2.1智能制造的特征

1.2.5深度學(xué)習(xí)

1.2.2智能優(yōu)化算法1.2.6知識(shí)工程1.2.3模式識(shí)別1.2.7商業(yè)智能1.2.4模糊控制1.2.8多種智能技術(shù)融合在智能制造中的應(yīng)用

工業(yè)和信息化部下發(fā)的《智能制造發(fā)展規(guī)劃(2016—2020年)》中將智能制造定義為:基于新一代信息通信技術(shù)與先進(jìn)制造技術(shù)深度融合,貫穿于設(shè)計(jì)、生產(chǎn)、管理、服務(wù)等制造活動(dòng)的各個(gè)環(huán)節(jié),具有自感知、自學(xué)習(xí)、自決策、自執(zhí)行、自適應(yīng)等功能的新型生產(chǎn)方式。工業(yè)界對(duì)制造智能技術(shù)日益關(guān)注的根源在于各種智能技術(shù)在工業(yè)界扮演著日益重要的、不可替代的角色,在某些領(lǐng)域智能技術(shù)的應(yīng)用已經(jīng)成為企業(yè)核心競爭力,例如基于智能優(yōu)化算法的優(yōu)化設(shè)計(jì),基于模式識(shí)別的故障識(shí)別、診斷,基于模糊控制的智能調(diào)節(jié)和控制,基于深度學(xué)習(xí)的智能檢測、故障診斷,基于類比推理、歸納學(xué)習(xí)與基于實(shí)例推理的知識(shí)系統(tǒng),基于商業(yè)智能的決策支持系統(tǒng),等等。1.2.1智能制造的特征

智能優(yōu)化算法在生產(chǎn)運(yùn)營管理、機(jī)械設(shè)計(jì)、制造系統(tǒng)規(guī)劃設(shè)計(jì)等領(lǐng)域具有大量研究成果和廣泛的實(shí)際應(yīng)用。例如：智能優(yōu)化算法在車間生產(chǎn)調(diào)度倉庫和物流優(yōu)化配置機(jī)械設(shè)計(jì)最佳加工性能綜合評(píng)估工業(yè)機(jī)器人的仿真選擇性維修決策M(jìn)RP......1.2.2智能優(yōu)化算法

模式識(shí)別是信息科學(xué)和人工智能的重要組成部分,主要被應(yīng)用于圖像分析與處理、語音識(shí)別、聲音分類、通信、計(jì)算機(jī)輔助診斷等方面。在制造行業(yè),模式識(shí)別技術(shù)大量應(yīng)用于產(chǎn)品檢驗(yàn)領(lǐng)域。產(chǎn)品質(zhì)量檢測產(chǎn)品缺陷檢測復(fù)合材料的分類定位物體檢測......1.2.3模式識(shí)別

模糊控制是以推理理論、模糊語言為基礎(chǔ),把專家的經(jīng)驗(yàn)當(dāng)作控制規(guī)則,實(shí)現(xiàn)智能化控制的一種控制方式。其本質(zhì)是采用基于模糊模型的模糊控制器,實(shí)現(xiàn)智能制造自動(dòng)化系統(tǒng)的控制過程。在實(shí)際應(yīng)用的過程中,根據(jù)模糊邏輯推理原則,利用計(jì)算機(jī)技術(shù),構(gòu)建自動(dòng)控制系統(tǒng),提高控制的效率。例如,自主循跡智能車的自適應(yīng)模糊控制器數(shù)控火焰切割機(jī)采用脈沖寬度調(diào)制(pulsewidthmodulation,PWM)控制技術(shù),設(shè)計(jì)基于模糊控制方法的自動(dòng)調(diào)高控制系統(tǒng)。在AGV小車調(diào)速控制系統(tǒng)......1.2.4模糊控制隨著數(shù)據(jù)爆炸式的增長,傳統(tǒng)的統(tǒng)計(jì)建模方式已經(jīng)難以處理高維度、非結(jié)構(gòu)化的數(shù)據(jù)。此時(shí),深度學(xué)習(xí)技術(shù)因其具備處理高維度、非線性數(shù)據(jù)模式的固有能力,開始登上歷史舞臺(tái)。深度學(xué)習(xí)技術(shù)可以輔助零部件和材料缺陷檢測工件定位(也就是工件在機(jī)械臂上的位置情況)工件精度測量工件裝配檢查生產(chǎn)能耗管理異常診斷......1.2.5深度學(xué)習(xí)知識(shí)工程是以知識(shí)為處理對(duì)象,為那些需要專家知識(shí)才能解決的應(yīng)用難題提供求解的手段,借用工程化的思想,對(duì)如何用人工智能的原理、方法、技術(shù)來設(shè)計(jì)、構(gòu)造和維護(hù)知識(shí)型系統(tǒng)的一門學(xué)科。促進(jìn)產(chǎn)品的創(chuàng)新性設(shè)計(jì)；產(chǎn)品設(shè)計(jì)變得更加靈活、高效和智能化；企業(yè)的知識(shí)積累規(guī)范化、制度化和軟件化等?；谥R(shí)工程的參數(shù)化設(shè)計(jì)基于知識(shí)工程技術(shù)的車身側(cè)圍設(shè)計(jì)軟件基于知識(shí)工程的船舶生產(chǎn)計(jì)劃與控制系統(tǒng)模型數(shù)字員工數(shù)字孿生......1.2.6知識(shí)工程智能轉(zhuǎn)型,離不開大數(shù)據(jù)分析平臺(tái)的構(gòu)建,離不開密切關(guān)聯(lián)的制造業(yè)商業(yè)智能(business

intelligence,BI)。通過幫助企業(yè)建立數(shù)據(jù)化運(yùn)營體系,真正實(shí)現(xiàn)數(shù)據(jù)驅(qū)動(dòng)決策。通過數(shù)據(jù)化運(yùn)營,業(yè)務(wù)人員將數(shù)據(jù)轉(zhuǎn)化成運(yùn)營策略,從而能夠判斷趨勢,展開有效行動(dòng),幫助自己發(fā)現(xiàn)問題,推動(dòng)創(chuàng)新或解決方案出現(xiàn)。應(yīng)用領(lǐng)域例如操作現(xiàn)場。實(shí)現(xiàn)技術(shù)流程與生產(chǎn)作業(yè)流程的有機(jī)結(jié)合。售后服務(wù)。應(yīng)用保修分析解決系統(tǒng),使工程師迅速判斷保修賠償率、是否需要特殊檢查等。決策支持。實(shí)現(xiàn)對(duì)數(shù)據(jù)、模型、知識(shí)、交互4個(gè)部件的系統(tǒng)集成決策。辦公系統(tǒng)。實(shí)現(xiàn)公司資源的高效利用,提高綜合統(tǒng)計(jì)、分析、處理數(shù)據(jù)和報(bào)表設(shè)計(jì)的效率。......1.2.7商業(yè)智能將多種智能技術(shù)融合應(yīng)用到實(shí)際的智能制造中,可為制造過程提供智能優(yōu)化決策系統(tǒng),從而減少制造成本,提高智能制造的精度和效率。例如,基于遺傳算法的徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)工裝軌跡控制改進(jìn)的遺傳算法用于反向傳播神經(jīng)網(wǎng)絡(luò)的訓(xùn)練,從而提高了折彎補(bǔ)償值的預(yù)測精度城軌列車運(yùn)行模糊模型,并建立了模糊專家系統(tǒng)。其中,利用遺傳算法求解確定約束下的列車運(yùn)行調(diào)整模型得到輸出變量的論域范圍。基于反向傳播神經(jīng)網(wǎng)絡(luò)和遺傳算法的控制器參數(shù)離線整定方法結(jié)合分層遺傳算法、模糊控制技術(shù),提出了一種自動(dòng)提取模糊控制器中所有模糊參數(shù)的方法。綜上,隨著智能理論和技術(shù)的發(fā)展,必將為制造行業(yè)的發(fā)展帶來新的機(jī)遇。通過制造智能技術(shù)的廣泛應(yīng)用,將助力我國制造業(yè)的升級(jí)換代。1.2.8多種智能技術(shù)融合在智能制造中的應(yīng)用1.3本章小結(jié)本章介紹了智能技術(shù)的基本概念和種類多種智能技術(shù)的發(fā)展歷史智能技術(shù)在智能制造中的應(yīng)用現(xiàn)狀第2章智能優(yōu)化技術(shù)

智能優(yōu)化概述2.1智能優(yōu)化方法的重要元素模擬退火算法2.22.3遺傳算法2.4蟻群優(yōu)化算法粒子群優(yōu)化算法超啟發(fā)式算法本章小結(jié)2.32.52.62.72.82.1智能優(yōu)化概述

2.1.1優(yōu)化的意義

2.1.2數(shù)學(xué)模型及常見優(yōu)化方法2.1.3傳統(tǒng)優(yōu)化方法的局限性2.1.4智能優(yōu)化方法的發(fā)展2.1.5智能優(yōu)化方法在制造業(yè)的應(yīng)用

智能優(yōu)化技術(shù)在生活和生產(chǎn)中都發(fā)揮了重要作用。最優(yōu)化問題可以分為:函數(shù)優(yōu)化問題：研究對(duì)象是一定區(qū)間內(nèi)的連續(xù)變量,研究解決的是連續(xù)性問題組合優(yōu)化問題：研究對(duì)象在解空間內(nèi)是離散狀態(tài),研究解決的是離散問題在工程實(shí)踐中,最優(yōu)化問題一般表述成選擇一組參數(shù),在一系列限制條件下,找到這些參數(shù)恰當(dāng)?shù)娜≈?使所求問題的目標(biāo)值達(dá)到最優(yōu)。在求解過程中,需將工程問題抽象表示成數(shù)學(xué)問題,再采用最優(yōu)化方法進(jìn)行求解。最優(yōu)化方法可以理解為基于某種思想或機(jī)制,尋找最優(yōu)解的一種搜索規(guī)則。2.1智能優(yōu)化概述優(yōu)化是在滿足限制條件的前提下,從眾多方案或參數(shù)值中找到最優(yōu)的那一個(gè),以使得問題或系統(tǒng)的某個(gè)或多個(gè)性能指標(biāo)達(dá)到現(xiàn)有條件下的最優(yōu)狀態(tài)。最優(yōu)化問題通常可以表示為以下形式。

2.1.1優(yōu)化的意義求解最優(yōu)化問題,就是將實(shí)際的工程問題轉(zhuǎn)化為數(shù)學(xué)問題,再采用特定算法進(jìn)行求解。這一轉(zhuǎn)化過程就是建立優(yōu)化問題的數(shù)學(xué)模型,又稱數(shù)學(xué)建模。數(shù)學(xué)模型是運(yùn)用數(shù)理邏輯和數(shù)學(xué)符號(hào)語言建構(gòu)的科學(xué)問題或工程問題的抽象模型。例如,某工廠有m種資源B1,B2,…,Bm,數(shù)量分別為b1,b2,…,bm,用這些資源生產(chǎn)n種產(chǎn)品A1,A2,…,An。每生產(chǎn)一個(gè)單位的Aj產(chǎn)品需要消耗資源Bi的量為aij,根據(jù)合同規(guī)定,產(chǎn)品Aj的產(chǎn)量不少于dj。再設(shè)Aj的單價(jià)為cj。那么怎樣安排生產(chǎn)計(jì)劃,才能既完成合同,又能使該工廠總收入最多呢?假設(shè)產(chǎn)品Aj的計(jì)劃產(chǎn)量為xj,根據(jù)問題中的信息,可以建立如下數(shù)學(xué)模型:

2.1.2數(shù)學(xué)模型及常見優(yōu)化方法

1.梯度下降法(gradient

descent)函數(shù)的梯度:對(duì)多元函數(shù)的參數(shù)求偏導(dǎo)數(shù),再寫成向量形式,就是。簡記為gradf(x,y)或者?f(x,y)。最速下降法：梯度表示函數(shù)在該點(diǎn)處沿著該方向變化最快,即對(duì)于函數(shù)f(x,y),在點(diǎn)(x0,y0)處,沿著梯度向(?f/?x,?f/?y)T的方向就是f(x,y)變化最快的方向。沿著梯度向量的方向,能夠更快地找到函數(shù)的最大值。反之,沿著梯度向量的相反方向,能夠更快地找到函數(shù)的最小值。這就是梯度下降法的優(yōu)化思想,即沿著當(dāng)前位置的負(fù)梯度方向,也就是下降最快的方向進(jìn)行搜索求解。當(dāng)目標(biāo)函數(shù)是凸函數(shù)時(shí),梯度下降法求得的解就是全局最優(yōu)解

2.1.2數(shù)學(xué)模型及常見優(yōu)化方法

2.1.2數(shù)學(xué)模型及常見優(yōu)化方法

2.牛頓法和擬牛頓法

1)牛頓法(Newton

method)

牛頓法是一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法。使用函數(shù)f(x)的泰勒級(jí)數(shù)展開式來尋找方程f(x)=0的根。牛頓法最大的特點(diǎn)是收斂速度很快。

首先,選擇一個(gè)接近函數(shù)f(x)零點(diǎn)的x0,計(jì)算相應(yīng)的f(x0)和切線斜率f'(x0)。然后計(jì)算穿過點(diǎn)(x0,f(x0))并且斜率為f'(x0)的直線和x軸交點(diǎn)的x坐標(biāo),也就是求如下方程的解:將新求得的點(diǎn)的x坐標(biāo)命名為x1,通常x1會(huì)比x0更接近方程f(x)=0的解。因此可以利用x1開始下一輪迭代。迭代公式可簡化為

已經(jīng)證明,如果f'(x)是連續(xù)的,并且待求的零點(diǎn)x是孤立的,那么在零點(diǎn)x周圍存在一個(gè)區(qū)域,只要初始值x0位于這個(gè)鄰近區(qū)域內(nèi),那么牛頓法必定收斂。2.1.2數(shù)學(xué)模型及常見優(yōu)化方法（2-7）

然后使用牛頓法求解minf(x)(x∈Rn)。設(shè)f(x)具有二階連續(xù)偏導(dǎo)數(shù),第k次迭代的值為x(k),將f(x)在x(k)處展成泰勒級(jí)數(shù),并取二階近似,有

其中,?f(x(k))

是f(x)在x(k)處梯度向量的值;?2f(x(k))是f(x)在x(k)處的Hessian矩陣H(x(k)):函數(shù)f(x)有極值的必要條件是在極值點(diǎn)處的一階導(dǎo)數(shù)為0,即梯度向量為0。特別的,當(dāng)H(x(k))是正定矩陣時(shí),函數(shù)f(x)的極值即為極小值。為求?'(x)的駐點(diǎn),令?'(x)=0,即設(shè)?2f

(x(k))可逆,由式(2-11)可得到牛頓法的迭代公式:這樣在已知x(k)后,就可以根據(jù)式(2-12)算出后繼點(diǎn)x(k+1)的值,令k=k+1,再根據(jù)式(2-12)算出后繼點(diǎn)x(k+1)的值,以此類推產(chǎn)生序列{x(k)},在特定情況下,序列{x(k)}收斂。

2.1.2數(shù)學(xué)模型及常見優(yōu)化方法（2-9）

2)擬牛頓法(quasi-Newtonmethod)擬牛頓法是求解非線性優(yōu)化問題最有效的方法之一。其優(yōu)化思想是改善牛頓法每次都需要求解復(fù)雜的Hessian矩陣的逆矩陣的缺陷,用正定矩陣來近似Hessian矩陣的逆,從而降低計(jì)算復(fù)雜度。根據(jù)牛頓法的迭代公式(2-12),擬牛頓法構(gòu)造了?2f(x(k))-1的近似矩陣Hk。將目標(biāo)函數(shù)f(x)在點(diǎn)x(k+1)展開為泰勒級(jí)數(shù),并取二階近似,得到因此,在點(diǎn)x(k+1)附近有

2.1.2數(shù)學(xué)模型及常見優(yōu)化方法（2-14）

2.1.2數(shù)學(xué)模型及常見優(yōu)化方法（2-14）

3.共軛梯度法共軛梯度法是介于梯度下降法與牛頓法之間的一個(gè)方法,其優(yōu)點(diǎn)是所需存儲(chǔ)量小,具有有限步收斂性,穩(wěn)定性高,而且不需要任何外來參數(shù)。這種方法既克服了梯度下降法收斂慢的缺點(diǎn),又避免了牛頓法需要存儲(chǔ)和計(jì)算Hessian矩陣并求逆的缺點(diǎn)。共軛梯度法不僅是解決大型線性方程組最有用的方法之一,也是求解大型非線性優(yōu)化問題最有效的算法之一,是一種非常重要的優(yōu)化方法。共軛梯度法是根據(jù)正定二次函數(shù)極小值問題推導(dǎo)出來的,后被推廣到求解一般形式的無約束問題。正定二次函數(shù)極小值問題是指形如下式的問題:2.1.2數(shù)學(xué)模型及常見優(yōu)化方法其中,A為n×n階的正定矩陣,X,B∈Rn

,c為常數(shù)。如果能構(gòu)造出A的共軛向量組P(1),P(2),…,P(n),并分別沿這n個(gè)方向進(jìn)行一維搜索,經(jīng)過n步即可求得問題的極小值。這就是共軛法的思想。共軛梯度法在每個(gè)搜索方向中加入負(fù)梯度方向的分量,并確保每個(gè)搜索方向之間都是A的共軛。算法步驟為:

第1步取初始點(diǎn)x1,精度為ε,k=1;

第2步若‖?f(xk)‖≤ε,則停止計(jì)算,xk

即為問題的最優(yōu)解;否則,令

第3步沿dk進(jìn)行一維搜索,求得步長λk,使xk+1=xk+λkdk;

第4步再令k=k+1,轉(zhuǎn)步驟第2步。2.1.2數(shù)學(xué)模型及常見優(yōu)化方法

4.爬山法爬山法,也稱直接搜索法,是求解多變量無約束優(yōu)化問題的一類方法。顧名思義,該方法求解最大化問題的過程就像爬山一樣,一直向比當(dāng)前位置高的地方走,但有時(shí)為了到達(dá)山頂,不得不先上矮山頂,然后再下來,這樣翻越一個(gè)個(gè)小山頭,直到最終達(dá)到山頂。爬山法是一種局部擇優(yōu)的貪心搜索算法。每次從當(dāng)前節(jié)點(diǎn)開始,與鄰接點(diǎn)進(jìn)行比較:若當(dāng)前節(jié)點(diǎn)是最大的,則返回當(dāng)前節(jié)點(diǎn),作為最大值;若當(dāng)前節(jié)點(diǎn)不是最大的,就用最高的鄰接點(diǎn)替換當(dāng)前節(jié)點(diǎn),從而實(shí)現(xiàn)向高處攀爬的目的。如此往復(fù),直至到達(dá)最高點(diǎn)。2.1.2數(shù)學(xué)模型及常見優(yōu)化方法該算法存在的主要問題是:局部最大,即某個(gè)節(jié)點(diǎn)會(huì)比周圍任何一個(gè)鄰接點(diǎn)都高,但只是局部最優(yōu)解,并非全局最優(yōu)解;高地問題,即搜索一旦到達(dá)高地,就無法確定搜索的最佳方向,會(huì)產(chǎn)生隨機(jī)走動(dòng),使搜索效率降低;山脊問題,即搜索可能會(huì)在山脊的兩面來回振蕩,前進(jìn)步伐很小。當(dāng)出現(xiàn)上述問題后,只能隨機(jī)重啟爬山算法來解決,如圖2-2所示。2.1.2數(shù)學(xué)模型及常見優(yōu)化方法圖2-2爬山法的直觀解釋優(yōu)點(diǎn)：以梯度為基礎(chǔ)的傳統(tǒng)優(yōu)化算法具有較高的計(jì)算效率、較強(qiáng)的可靠性、比較成熟等優(yōu)點(diǎn),是一類最重要的、應(yīng)用非常廣泛的優(yōu)化算法。實(shí)際優(yōu)化問題通常具有以下特點(diǎn):標(biāo)函數(shù)沒有明確的解析表達(dá)式;標(biāo)函數(shù)雖有明確的表達(dá)式,但無法恰當(dāng)估值;目標(biāo)函數(shù)為多峰函數(shù);目標(biāo)函數(shù)有多個(gè),即多目標(biāo)優(yōu)化,并且目標(biāo)函數(shù)或約束條件不連續(xù)、不可微、高度非線性,或者問題本身是困難的組合問題。傳統(tǒng)優(yōu)化方法在求解時(shí)要求目標(biāo)函數(shù)滿足凸函數(shù)、連續(xù)可微、可行域是凸集等條件,而且處理非確定性信息的能力較差。這使得傳統(tǒng)優(yōu)化方法在解決際問題時(shí)受到了限制。鑒于實(shí)際工程問題的復(fù)雜性、非線性、約束性以及建模困難等諸多特點(diǎn),尋求高效的優(yōu)化算法已成為相關(guān)學(xué)科的主要研究內(nèi)容之一。2.1.3傳統(tǒng)優(yōu)化方法的局限性目前常見的智能優(yōu)化算法多是建立在生物智能或物理現(xiàn)象基礎(chǔ)上的一類隨機(jī)搜索算法現(xiàn)階段在理論上還不如傳統(tǒng)優(yōu)化算法嚴(yán)謹(jǐn)和完善在實(shí)際求解中往往也不能求得最優(yōu)解,因而常常被視為只是一些元啟發(fā)式(metaheuristic)搜索方法但從實(shí)際應(yīng)用的觀點(diǎn)看,這類算法一般不要求目標(biāo)函數(shù)和約束條件的連續(xù)性與凸性,有時(shí)甚至不要求目標(biāo)函數(shù)有解析表達(dá)式,對(duì)計(jì)算中數(shù)據(jù)的不確定性也有很強(qiáng)的適應(yīng)能力,往往能夠提供在應(yīng)用場景下實(shí)際可接受的解2.1.4智能優(yōu)化方法的發(fā)展

在現(xiàn)代智能制造領(lǐng)域,智能優(yōu)化算法在車間生產(chǎn)調(diào)度、廠區(qū)內(nèi)自動(dòng)導(dǎo)航車路徑規(guī)劃、倉儲(chǔ)和物流優(yōu)化配置等問題的優(yōu)化求解中,都有著重要應(yīng)用。生產(chǎn)調(diào)度方面

物流及倉儲(chǔ)方面生產(chǎn)工藝優(yōu)化方面2.1.5智能優(yōu)化方法在制造業(yè)的應(yīng)用排定生產(chǎn)計(jì)劃。不同的零件需要不同的加工工序,每一道加工工序需要在不同的機(jī)器上耗費(fèi)一定的加工時(shí)間來完成。在上述約束條件下,確定恰當(dāng)?shù)纳a(chǎn)計(jì)劃,使得整個(gè)工廠或作業(yè)車間的生產(chǎn)效率最高。工廠布局設(shè)計(jì)。工廠布局是工業(yè)生產(chǎn)制造中的重要決策環(huán)節(jié)。如何設(shè)置車間內(nèi)各類生產(chǎn)設(shè)備的安放位置,才能把人員、設(shè)備、物料所需空間做到最適當(dāng)?shù)姆峙浜妥钣行У慕M合,從而盡量節(jié)省空間,降低生產(chǎn)過程某著名企業(yè)工件及人員所消耗的成本,獲取最大的生產(chǎn)經(jīng)濟(jì)效益。

工人指派問題。在工人總數(shù)有限的前提下,如何在生產(chǎn)線上配置工人,才能使得產(chǎn)品的生產(chǎn)效率最高,或者能夠最大化保證某些關(guān)鍵零部件的生產(chǎn),能夠優(yōu)先保證需要緊急交付的訂單的生產(chǎn)。并行機(jī)調(diào)度問題。使用若干臺(tái)同類機(jī)器并行生產(chǎn),共同完成所有的作業(yè),這是一類生產(chǎn)場景中常見的調(diào)度問題,涉及平衡各機(jī)器的生產(chǎn)負(fù)載,以達(dá)到最短的完工時(shí)間,并處理某臺(tái)機(jī)器出現(xiàn)隨機(jī)故障時(shí)對(duì)其他機(jī)器生產(chǎn)造成的干擾以及對(duì)整個(gè)生產(chǎn)計(jì)劃的影響等問題。2.1.5智能優(yōu)化方法在制造業(yè)的應(yīng)用1.生產(chǎn)調(diào)度方面

2.物流及倉儲(chǔ)方面

車輛路徑規(guī)劃問題。生產(chǎn)流程中需要以最低的成本,將原材料、半成品、零部件、成品等物料進(jìn)行從產(chǎn)地或倉庫到工廠的配送、倉庫儲(chǔ)存和調(diào)用。這一方面應(yīng)減少非增值活動(dòng),另一方面應(yīng)保證現(xiàn)場物料不堆積且生產(chǎn)線上不缺料。在物料的運(yùn)輸過程中,將產(chǎn)生車輛路徑規(guī)劃問題(vehicle

routing

problem)。機(jī)器人調(diào)度。在規(guī)模復(fù)雜應(yīng)用場景中,多個(gè)某著名企業(yè)機(jī)器人編隊(duì)的調(diào)度和控制,例如路徑規(guī)劃、任務(wù)分配等就成為了影響工廠工作效率的主要因素。港口調(diào)度問題。港口調(diào)度問題涉及眾多參數(shù)和約束條件,包括泊位的數(shù)量、不同的水深(可供停泊不同噸位的船只)、起重機(jī)械的數(shù)量和起重能力、貨物緩沖區(qū)的大小、港口內(nèi)轉(zhuǎn)運(yùn)車輛的運(yùn)載能力及運(yùn)輸路徑規(guī)劃、港口倉庫的大小等。2.1.5智能優(yōu)化方法在制造業(yè)的應(yīng)用

3.生產(chǎn)工藝優(yōu)化方面研究在一定的條件下,如何用最合適的生產(chǎn)路線和生產(chǎn)設(shè)備,以最節(jié)省的投資和操作費(fèi)用,設(shè)計(jì)最佳的工藝流程。對(duì)零件表面除銹、拋光等工序的處理,齒輪類零件、管類零件等不同形狀的零件的加工,其最適合的工藝流程不盡相同。通過對(duì)工藝流程的研究及優(yōu)化,能夠盡可能地挖掘出設(shè)備的潛能,找到生產(chǎn)瓶頸,尋求解決的途徑,以達(dá)到產(chǎn)量高、功耗低和效益高的生產(chǎn)目標(biāo)。2.1.5智能優(yōu)化方法在制造業(yè)的應(yīng)用2.2智能優(yōu)化方法的重要元素

2.2.1

智能優(yōu)化方法的分類

2.2.2

貪心算法與啟發(fā)式規(guī)則2.2.3局部搜索與群體智能2.2.4元啟發(fā)式算法與超啟發(fā)式算法優(yōu)化方法可以分為精確算法和近似算法兩大類。精確算法包括：分支定界法、割平面法和動(dòng)態(tài)規(guī)劃法等,計(jì)算復(fù)雜度一般比較大,只適合求解小規(guī)模問題近似算法（啟發(fā)式算法）包括一些專用算法和元啟發(fā)式算法。元啟發(fā)式算法又可進(jìn)一步分為基于個(gè)體行為的爬山法、模擬退火算法、禁忌搜索算法等,以及基于群體行為的進(jìn)化類算法和群智能算法等。智能優(yōu)化方法：模仿生物種群進(jìn)化機(jī)制的進(jìn)化類算法模仿生物群體行為社會(huì)性的群體智能算法模擬某些物理過程規(guī)律的算法2.2.1智能優(yōu)化方法的分類1.模仿生物種群進(jìn)化機(jī)制的進(jìn)化類算法遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的自適應(yīng)隨機(jī)全局搜索和優(yōu)化方法。算法操作的基本過程是在解決方案對(duì)應(yīng)的種群中逐次產(chǎn)生近似最優(yōu)解,稱為一代;在每一代中,根據(jù)個(gè)體在問題域中的適應(yīng)度和從自然遺傳學(xué)中借鑒來的再造方法進(jìn)行選擇,產(chǎn)生新一代的近似解,即下一代。新個(gè)體比原個(gè)體更適應(yīng)環(huán)境,即解更優(yōu)。差分進(jìn)化算法是通過群體內(nèi)個(gè)體間的合作與競爭產(chǎn)生的智能優(yōu)化搜索方法,采用一對(duì)一的競爭生存策略,同時(shí)具有記憶能力,可跟蹤搜索情況以調(diào)整搜索策略。免疫算法是模仿生物免疫機(jī)制,采用群體搜索策略并迭代計(jì)算;利用自身多樣性和維持機(jī)制,克服早熟問題,求解全局最優(yōu)。2.2.1智能優(yōu)化方法的分類2.模仿生物群體行為社會(huì)性的群體智能算法主要有蟻群優(yōu)化算法、粒子群優(yōu)化算法、人工蜂群優(yōu)化算法、人工魚群算法、杜鵑搜索算法、螢火蟲算法、狼群算法、混合蛙跳算法和菌群優(yōu)化算法等。蟻群優(yōu)化算法是通過模擬自然界中螞蟻集體尋徑行為而提出的基于種群智能行為的啟發(fā)式隨機(jī)搜索算法。粒子群優(yōu)化算法是一種基于群體智能的全局隨機(jī)搜索算法。2.2.1智能優(yōu)化方法的分類3.模擬某些物理過程規(guī)律的算法主要有模擬退火算法、煙花算法、禁忌搜索算法等。模擬退火算法是一種基于迭代求解策略的隨機(jī)尋優(yōu)算法,是局部搜索算法的擴(kuò)展其基本思想是以一定的概率選擇鄰域內(nèi)距離目標(biāo)值更遠(yuǎn)的狀態(tài)。

在設(shè)計(jì)算法求解優(yōu)化問題時(shí),貪心算法與啟發(fā)式規(guī)則是兩種常見的設(shè)計(jì)思想。1.貪心算法貪心算法的思想是總是做出在當(dāng)前看來最好的選擇,即總是選擇當(dāng)前的最大值或最小值,并不從整體最優(yōu)考慮。它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。貪心算法不能保證得到問題的全局最優(yōu)解,但在一些情況下,貪心算法能得到比較好的近似解。1)采用貪心算法的基本條件問題具備貪心選擇性質(zhì)。即所求問題的全局最優(yōu)解可以通過一系列局部最優(yōu)選擇,即貪心地選擇來達(dá)到。問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。指一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解。2.2.2貪心算法與啟發(fā)式規(guī)則2)貪心算法的基本思路從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo),以盡可能快地求得更好的解。當(dāng)達(dá)到算法中的某一步不能再繼續(xù)前進(jìn)時(shí),算法停止。其一般求解步驟為:對(duì)問題進(jìn)行數(shù)學(xué)建模;把要求解的問題分成若干個(gè)子問題;對(duì)每個(gè)子問題求解,得到子問題的局部最優(yōu)解;把子問題的局部最優(yōu)解合成為原來問題的一個(gè)解。3)貪心算法的主要問題貪心算法不能保證求得的最終解是最佳的,不能用來確定最大或最小解,只能求滿足某些約束條件的可行解的范圍。2.2.2貪心算法與啟發(fā)式規(guī)則2.啟發(fā)式規(guī)則啟發(fā)式算法是在可接受的計(jì)算成本(多指計(jì)算時(shí)間和存儲(chǔ)空間的開銷)內(nèi),求出問題每個(gè)實(shí)例的一個(gè)可行解,也就是在實(shí)際問題的背景下可被接受的解。并且該可行解與該問題的最優(yōu)解之間的偏離程度通常不可預(yù)計(jì)。例如,調(diào)度規(guī)則：SPTFCFSLPT2.2.2貪心算法與啟發(fā)式規(guī)則1.局部搜索局部搜索是一種以時(shí)間換精度的啟發(fā)式算法。局部搜索算法從一個(gè)初始解開始,通過鄰域動(dòng)作,產(chǎn)生其鄰居解,判斷鄰居解的質(zhì)量,根據(jù)某種策略來選擇鄰居解,重復(fù)上述過程,直至到達(dá)終止條件。不同局部搜索算法的區(qū)別在于鄰域動(dòng)作的定義和選擇鄰居解的策略,同時(shí)這也是決定算法好壞的關(guān)鍵。鄰域動(dòng)作是一個(gè)函數(shù),通過這個(gè)函數(shù),對(duì)當(dāng)前解s,產(chǎn)生其相應(yīng)的鄰居解集合。例如:對(duì)于一個(gè)bool(布爾)型問題,其當(dāng)前解為s=1001,將鄰域動(dòng)作定義為翻轉(zhuǎn)其中一個(gè)bit(位)時(shí),得到的鄰居解的集合N(s)={0001,1101,1011,1000},其中N(s)?S,S表示所有可行解的集合。將鄰域動(dòng)作定義為互換相鄰bit時(shí),得到的鄰居解的集合N(s)={0101,1001,1010}。2.2.3局部搜索與群體智能改進(jìn)的局部搜索算法迭代部搜索(iterated

local

search,ILS)迭代局部搜索是在局部搜索得到的局部最優(yōu)解上,加入擾動(dòng),再重新進(jìn)行局部搜索。其思想是:物以類聚,好的解之間會(huì)有一些共性,因此在局部最優(yōu)解上做擾動(dòng),比隨機(jī)地選擇一個(gè)初始解再進(jìn)行局部搜索效果更好。變鄰域搜索(variable

neighborhood

search,VNS)變鄰域搜索的主要思想是:采用多個(gè)不同的鄰域進(jìn)行系統(tǒng)搜索。先采用最小的鄰域搜索,當(dāng)無法改進(jìn)解的質(zhì)量時(shí),則切換到稍大一點(diǎn)的鄰域。如果能繼續(xù)改進(jìn)解,則退回到最小的鄰域,否則繼續(xù)切換到更大的鄰域。利用不同的動(dòng)作構(gòu)成的鄰域結(jié)構(gòu)進(jìn)行交替搜索,從而在集中性和疏散性之間達(dá)到很好的平衡。2.2.3局部搜索與群體智能2.群體智能

群體智能源于對(duì)以螞蟻、蜜蜂等為代表的社會(huì)性昆蟲群體行為的研究。群居性生物表現(xiàn)出來的智能行為被稱為群體智能。Millonas在1994年提出群體智能應(yīng)該遵循5條基本原則:鄰近原則(proximity

principle)———群體能夠進(jìn)行簡單的空間和時(shí)間計(jì)算;品質(zhì)原則(quality

principle)———群體能夠響應(yīng)環(huán)境中的品質(zhì)因子;多樣性反應(yīng)原則(principle

of

diverse

response)———群體的行動(dòng)范圍不應(yīng)該太窄;穩(wěn)定性原則(stabilityprinciple)———群體不應(yīng)在每次環(huán)境變化時(shí)都改變自身的行為;適應(yīng)性原則(adaptabilityprinciple)———在所需代價(jià)不太高的情況下,群體能夠在適當(dāng)?shù)臅r(shí)候改變自身的行為。群體智能的核心是由眾多簡單個(gè)體組成的群體能夠通過相互之間的簡單合作來實(shí)現(xiàn)某一功能,完成某一任務(wù)。2.2.3局部搜索與群體智能

群體智能具有以下特點(diǎn):較強(qiáng)的魯棒性。群體智能的控制是分布式的,不存在中心控制。即不會(huì)由于某一個(gè)或幾個(gè)個(gè)體出現(xiàn)故障而影響群體對(duì)整個(gè)問題的求解。較好的可擴(kuò)展性。群體中的每個(gè)個(gè)體都能夠改變環(huán)境。由于群體智能可以通過非直接通信的方式進(jìn)行信息的傳輸與合作,因而隨著個(gè)體數(shù)目的增加,通信開銷的增幅減小。簡單性。群體中每個(gè)個(gè)體的能力或遵循的行為規(guī)則非常簡單,因而群體智能的實(shí)現(xiàn)比較方便。自組織性。群體表現(xiàn)出來的復(fù)雜行為是通過簡單個(gè)體的交互過程突現(xiàn)出來的智能。2.2.3局部搜索與群體智能元啟發(fā)式算法：將隨機(jī)算法與局部搜索算法結(jié)合，優(yōu)化機(jī)理不過分依賴算法的組織結(jié)構(gòu)信息，廣泛地應(yīng)用到函數(shù)組合優(yōu)化和函數(shù)計(jì)算中。主要包括：模擬退火算法、遺傳算法、列表搜索算法、進(jìn)化規(guī)劃、進(jìn)化策略、蟻群優(yōu)化算法和人工神經(jīng)網(wǎng)絡(luò)等。不同算法在優(yōu)化機(jī)制方面存在一定的差異,但在優(yōu)化流程上卻具有較大的相似性：是一種鄰域搜索結(jié)構(gòu)。算法都是從一個(gè)(一組)初始解出發(fā),在算法關(guān)鍵參數(shù)的控制下通過鄰域函數(shù)產(chǎn)生若干鄰域解,按接受準(zhǔn)則(確定性、概率性或混沌方式)更新當(dāng)前狀態(tài),再按照關(guān)鍵參數(shù)修改準(zhǔn)則調(diào)整關(guān)鍵參數(shù)。如此重復(fù)上述搜索步驟,直到滿足算法的收斂準(zhǔn)則,最終得到問題的優(yōu)化結(jié)果。超啟發(fā)式算法(hyper-heuristic

algorithm)：一種高層啟發(fā)式方法，通過管理或操縱一系列低層的啟發(fā)式算法(low-level

heuristics,LLH)，以產(chǎn)生新的啟發(fā)式算法。超啟發(fā)式算法可以簡單闡述為尋找啟發(fā)式算法的啟發(fā)式算法,其求解的是一些啟發(fā)式算法的組合。2.2.4元啟發(fā)式算法與超啟發(fā)式算法2.3模擬退火算法

2.3.1

熱力學(xué)中的退火過程

2.3.2

模擬退火算法的構(gòu)造與流程2.3.3算法參數(shù)分析2.3.4制造業(yè)應(yīng)用案例基本思想：是基于蒙特卡羅迭代求解策略的一種隨機(jī)尋優(yōu)算法,其出發(fā)點(diǎn)是物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。算法流程：從某一較高初,伴隨數(shù)的不斷下降,以一定的概率拒絕局部最優(yōu)解,從而跳出局部極值點(diǎn)繼續(xù)搜索狀態(tài)空間的其他狀態(tài)解,進(jìn)而得到全局最優(yōu)解。算法特點(diǎn)：是一種通用的優(yōu)化算法,具有優(yōu)良的全局收斂特性和隱含的數(shù)據(jù)并行處理特性應(yīng)用案例：諸如超大規(guī)模集成電路(very

large

scale

integration,VLSI)設(shè)計(jì)、生產(chǎn)調(diào)度、控制工程、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域。2.3模擬退火算法(simulatedannealing,SA)物理退火：材料由高降處理過程。金屬物體退火可以從高能狀態(tài)轉(zhuǎn)化為低能的固體晶態(tài)，物體變得更為柔韌。退火過程的組成：加：目的是增強(qiáng)原子的熱運(yùn)動(dòng),使原子能夠偏離平衡位置。等：目的在于保證系統(tǒng)在每個(gè)都能達(dá)到平衡態(tài),最終達(dá)到低能有序的固體基態(tài)。冷卻過程：目的在于減弱原子的熱運(yùn)動(dòng)使其逐漸趨于有序。冷卻過程關(guān)鍵在于控制冷卻的速度2.3.1熱力學(xué)中的退火過程模擬退火算法求解組合優(yōu)化問題的過程與物理退火過程之間的對(duì)應(yīng)關(guān)系2.3.2模擬退火算法的構(gòu)造與流程表2-1模擬退火算法求解組合優(yōu)化問題與物理退火過程的對(duì)應(yīng)關(guān)系2.模擬退火算法的計(jì)算步驟算法模擬物理退火的過程,由一個(gè)給定的初始高,利用具有概率突跳特性的Metropolis抽樣策略在優(yōu)化問題的解空間內(nèi)隨機(jī)搜索,隨著斷下降,重復(fù)Metropolis抽樣過程,最終得到問題的全局最優(yōu)解。一個(gè)優(yōu)化問題可以描述為

其中,S是一個(gè)離散有限狀態(tài)空間;i表示狀態(tài);f(i)為目標(biāo)函數(shù)。對(duì)于這個(gè)優(yōu)化問題,模擬退火算法的計(jì)算步驟如下:2.3.2模擬退火算法的構(gòu)造與流程第1步初始化參數(shù)。任選初始解i∈S,給定初始T0和終止Tf,迭代指標(biāo)k=0,Tk=T0。第2步設(shè)定Tk的最大循環(huán)次數(shù)n(Tk),令n=0。第3步從i的鄰域N(i)中隨機(jī)生成一個(gè)鄰域解j∈N(i),n=n+1,計(jì)算目標(biāo)函數(shù)增量Δf=f(j)-f(i)。

第4步如果Δf<0,則接受狀態(tài)為當(dāng)前狀態(tài),令i=j;否則,計(jì)算p=exp(-Δf/Tk),ξ~U(0,1),如果p<ξ,則接受狀態(tài)j為當(dāng)前狀態(tài),令i=j。第5步如果達(dá)到熱平衡,即內(nèi)循環(huán)次數(shù)n>n(Tk),轉(zhuǎn)第6步,否則轉(zhuǎn)第3步。第6步令k=k+1,降低Tk,如果Tk<Tf,則算法停止,否則轉(zhuǎn)第2步。2.3.2模擬退火算法的構(gòu)造與流程1.初始設(shè)置初始T0要足夠大,以保證算法開始運(yùn)行時(shí)解的接受概率為1,模擬退火算法在開始時(shí)能處于一種平衡狀態(tài)。但初始高也會(huì)導(dǎo)致計(jì)算時(shí)間的增加,實(shí)際運(yùn)用中需要通過反復(fù)實(shí)驗(yàn)確定T0值。T0的經(jīng)驗(yàn)法則:選取一個(gè)大值作為T0的當(dāng)前值,然后進(jìn)行若干次搜索,如果接受率p小于預(yù)定的初始接受率p0,則將T0擴(kuò)大1倍,以新的T0值重復(fù)上述過程,直到獲得使p>p0

的T0值。2.狀態(tài)產(chǎn)生函數(shù)設(shè)計(jì)狀態(tài)產(chǎn)生函數(shù)應(yīng)保證生成的候選解盡可能遍布整個(gè)解空間,一般情況下狀態(tài)產(chǎn)生函數(shù)由兩部分組成,即生成候選解的方式和概率分布。生成候選解的方式主要由問題的性質(zhì)決定,不同問題需要設(shè)計(jì)不同的生成規(guī)則。生成候選解的概率分布決定了選擇不同候選解的概率,概率分布可以是均勻分布、正態(tài)分布和指數(shù)分布等。2.3.3算法參數(shù)分析3.狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)一般以概率形式給出,是模擬退火算法實(shí)現(xiàn)全局搜索的關(guān)鍵參數(shù),不同狀態(tài)接受函數(shù)的區(qū)別主要在于接受概率的形式不同。在一般情況下,設(shè)計(jì)狀態(tài)接受函數(shù)都采用Metropolis準(zhǔn)則,其內(nèi)容為:

在恒中,接受使目標(biāo)函數(shù)結(jié)果變好的候選解的概率應(yīng)大于使目標(biāo)函數(shù)結(jié)果變差的候選解的概率。

隨著降,接受使目標(biāo)函數(shù)結(jié)果變差的候選解概率應(yīng)逐漸減小。

在近于零時(shí),只接受使目標(biāo)函數(shù)結(jié)果變好的解。2.3.3算法參數(shù)分析4.降降是對(duì)行更新的函數(shù),用于在外循環(huán)中修改Tk,這是模擬退火算法的外循環(huán)過程。大小決定模擬退火算法對(duì)候選解的搜索方式:高時(shí),算法傾向于廣域搜索,當(dāng)前狀態(tài)i鄰域內(nèi)的較差解被接受的概率較大;低時(shí),算法傾向于局域搜索,當(dāng)前狀態(tài)i鄰域內(nèi)的較差解被接受的概率較小。如果降過快,算法將很快從廣域搜索切換為局域搜索,有可能過早地陷入局部最優(yōu);如果降過慢,則計(jì)算時(shí)間會(huì)大大增加。因此,選擇適當(dāng)?shù)慕挡拍鼙ＷC模擬退火算法的性能。常見的降有兩種:Tk+1=Tk×α,退火速率α∈0.95,0.99,α越大降得越慢。這種方法簡單,一步以相同比率下降。Tk+1=Tk-ΔT,ΔT是降的步長。這種方法可操作性強(qiáng),能預(yù)先控制降的步數(shù),即外循環(huán)次數(shù)。2.3.3算法參數(shù)分析5.熱平衡準(zhǔn)則熱平衡的到達(dá)相當(dāng)于物理退火的等,是指在一個(gè)給定Tk下,模擬退火算法基于Metropolis準(zhǔn)則在解空間內(nèi)進(jìn)行隨機(jī)搜索,最終達(dá)到平衡狀態(tài)的過程,這是模擬退火算法的內(nèi)循環(huán)過程。為了保證系統(tǒng)達(dá)到平衡狀態(tài),內(nèi)循環(huán)的次數(shù)需要足夠大,最常見的方法是設(shè)置為一個(gè)與問題實(shí)際規(guī)模相關(guān)的常數(shù)。6.退火結(jié)束準(zhǔn)則退火結(jié)束準(zhǔn)則用于決定算法什么時(shí)候停止。第一種方法是簡單地設(shè)置一個(gè)值Tf,當(dāng)Tk<Tf時(shí),算法結(jié)束。第二種方法是設(shè)置外循環(huán)的迭代次數(shù)K,如果循環(huán)次數(shù)達(dá)到K時(shí),算法結(jié)束。2.3.3算法參數(shù)分析1.問題描述n個(gè)工作需要由n個(gè)工人完成,一個(gè)工人最多只能完成一個(gè)工作,而一個(gè)工作只能由一個(gè)工人完成。cij表示第i個(gè)工人完成第j個(gè)工作的費(fèi)用,找出工作的分配方案,使得安排工人總的費(fèi)用達(dá)到最小。數(shù)學(xué)模型可以表示為其中,xij是決策變量,當(dāng)xij=1時(shí),表示第i個(gè)工人做第j個(gè)工作;否則,xij=0。2.3.4制造業(yè)應(yīng)用案例(2-21)(2-22)2.算法參數(shù)設(shè)置

1)解s的形式

n表示工人的數(shù)量,由于工作的數(shù)量等于工人的數(shù)量,可以使用順序編碼來表示一個(gè)解s,S為問題的解空間,索引i表示工人i,索引位置的值表示第i個(gè)工人所分配的工作。例如下面是一個(gè)長度n=4的解:

s=(2,1,3,4)

即表示工人1完成第2個(gè)工作,工人2完成第1個(gè)工作,以此類推。解的目標(biāo)值f(s)設(shè)置為當(dāng)前解s所需要花費(fèi)的費(fèi)用。 2)鄰域的生成這里采用兩兩交換的原則。假設(shè)給定一個(gè)當(dāng)前解s,然后任意交換解中兩個(gè)元素的位置,生成一個(gè)新的解s'。由以上方法生成的解s'所構(gòu)成的集合就是解s的鄰域N(s)。2.3.4制造業(yè)應(yīng)用案例

3)初始T0和降

初始T0=Kδ,其中δ=max{f(s)|s∈S},K是充分大的數(shù),可以取10,20,100等試驗(yàn)值。降采用Tk+1=Tk×α,α取0.96。

4)新解的接受與淘汰

采用Metropolis準(zhǔn)則作為狀態(tài)接受函數(shù),對(duì)候選解進(jìn)行接受和淘汰。

5)內(nèi)外循環(huán)終止條件

內(nèi)循環(huán)的次數(shù)采用固定步數(shù)X,因?yàn)橹概蓡栴}的鄰域大小為n(n-1)/2,所以設(shè)置X=n(n-1)/2。外循環(huán)給定一個(gè)比較小的正數(shù)ε,當(dāng)Tk<ε時(shí),外循環(huán)停止。2.3.4制造業(yè)應(yīng)用案例

3.算法流程初始化參數(shù)。任選初始解s∈S,設(shè)置最優(yōu)解s*=s。初始T0=Kδ,終止Tf=ε,迭代指標(biāo)X=0,Tk=T0。從s的鄰域N(s)中隨機(jī)生成一個(gè)鄰域解s'∈N(s),計(jì)算目標(biāo)函數(shù)增量Δf=f(s')-f(s),更新迭代指標(biāo)X=X+1。如果Δf<0,則接受狀態(tài)s'為當(dāng)前狀態(tài),令s=s',如果f(s*)-f(s)<0,更新s*=s;否則,計(jì)算p=exp(Δf/Tk),

ξ~U(0,1),

如果p<ξ,

則接受狀態(tài)s'為當(dāng)前狀態(tài),令s=s'。如果達(dá)到熱平衡,即內(nèi)循環(huán)次數(shù)X≥n(n-1)/2,轉(zhuǎn)第5步,否則轉(zhuǎn)第2步。Tk=Tk×α,如果Tk<Tf,則算法停止,輸出s*,否則x=0,轉(zhuǎn)第2步。

最后輸出的s*就是模擬退火算法求出的指派問題最優(yōu)解。2.3.4制造業(yè)應(yīng)用案例2.4遺傳算法

2.4.1

生物的遺傳與變異

2.4.2

遺傳算法的基本原理與流程2.4.3算法改進(jìn)2.4.4制造業(yè)應(yīng)用案例達(dá)爾文的自然選擇學(xué)說自然選擇:在生存斗爭中適者生存、不適者淘汰的過程。遺傳:生物的親代產(chǎn)生與自己相似的后代的現(xiàn)象。變異:親代與子代之間、子代個(gè)體之間,絕對(duì)不完全相同,總是或多或少地存在一定差異。2.4.1生物的遺傳與變異其基本思想:根據(jù)問題的目標(biāo)函數(shù)構(gòu)造適應(yīng)度函數(shù)(fitness

function);產(chǎn)生一個(gè)初始種群;根據(jù)適應(yīng)度函數(shù)的好壞,不斷選擇繁殖;經(jīng)過若干代后①得到適應(yīng)度函數(shù)最好的個(gè)體即最優(yōu)解。遺傳操作：選擇、交叉和變異核心內(nèi)容：參數(shù)編碼、初始種群設(shè)定、適應(yīng)度函數(shù)設(shè)計(jì)、遺傳操作設(shè)計(jì)和控制參數(shù)設(shè)定遺傳算法是模擬自然界生物進(jìn)化過程的計(jì)算模型2.4.2遺傳算法的基本原理與流程2.檢查算法收斂性檢查算法是否滿足收斂條件,控制算法是否結(jié)束。1.編碼和初始種群的生成N個(gè)初始染色體數(shù)據(jù),每個(gè)稱為一個(gè)個(gè)體,N個(gè)個(gè)體構(gòu)成了一個(gè)種群。

3.適應(yīng)度值評(píng)估檢測和選擇適應(yīng)度函數(shù)表明個(gè)體或解的優(yōu)劣性。從當(dāng)前種群中選出優(yōu)良的個(gè)體,使它們有機(jī)會(huì)作為父代繁殖下一代子孫。選擇實(shí)現(xiàn)了達(dá)爾文的適者生存原則2.4.2遺傳算法的基本原理與流程

4.交叉:按照交叉概率(Pc)進(jìn)行交叉交叉操作可以得到新一代個(gè)體,新個(gè)體組合了其父輩個(gè)體的特性。交叉體現(xiàn)了信息交換的思想。可以選定染色體上的一個(gè)點(diǎn)進(jìn)行互換、插入、逆序等交叉,也可以隨機(jī)選取幾個(gè)點(diǎn)進(jìn)行交叉。交叉概率如果太大,種群更新快,但是高適應(yīng)度的個(gè)體很容沒,概率小了搜索會(huì)停滯。一般設(shè)置Pc=0.9。

(1)單點(diǎn)交叉。隨機(jī)產(chǎn)生一個(gè)斷點(diǎn)(cutting

point),例如:

(2)雙點(diǎn)交叉(交換中間段),例如:

5.變異:按照變異概率(Pm)進(jìn)行變異變異首先在群體中隨機(jī)選擇一個(gè)個(gè)體,對(duì)于選中的個(gè)體以一定的概率隨機(jī)地改變?nèi)旧w數(shù)據(jù)中的某個(gè)值(基因)。遺傳算法中變異發(fā)生的概率很低。變異為新個(gè)體的產(chǎn)生提供了機(jī)會(huì)。變異可以防止有效基因的缺損造成的進(jìn)化停滯。比較低的變異概率就已經(jīng)可以讓基因不斷變更,太大會(huì)陷入隨機(jī)搜索。二進(jìn)制編碼情況下,選中的個(gè)體按變異概率Pm任選若干位基因改變位值0→1或1→0,Pm一般設(shè)定得比較小,在5%以下。2.4.2遺傳算法的基本原理與流程如圖2-6所示,將圓形輪盤按照每個(gè)個(gè)體的選擇概率Pi,劃分為n個(gè)扇形,第i個(gè)扇形的中心角為2πPi。設(shè)想每次轉(zhuǎn)動(dòng)輪盤,參考點(diǎn)停在第i個(gè)扇形內(nèi),則該次就選擇第i個(gè)個(gè)體。6.選擇策略常見的選擇策略有輪盤法、隨機(jī)遍歷抽樣法和錦標(biāo)賽法等。輪盤法的思想是適應(yīng)度值越好的個(gè)體被選中出現(xiàn)在下一代的概率也越大。首先根據(jù)個(gè)體的適應(yīng)度值計(jì)算出每個(gè)個(gè)體被選中的概率(即選擇概率),再按照此概率隨機(jī)選擇個(gè)體構(gòu)成子代種群。在選擇過程中,選擇概率越大的個(gè)體越有可能被選中。常用正比選擇方法(proportional

selection)計(jì)算個(gè)體的選擇概率:個(gè)體i的適應(yīng)度值為Fi,n為種群規(guī)模,則其選擇概率為

設(shè)第i個(gè)個(gè)體的累積概率并規(guī)定PP0=0。然后隨機(jī)產(chǎn)生一個(gè)在0~1服從均勻分布的隨機(jī)數(shù)ξk,ξk~U(0,1),當(dāng)PPi-1≤ξk<PPi時(shí),選擇個(gè)體i繁殖下一代個(gè)體。按上述方式轉(zhuǎn)動(dòng)輪盤n次,選出n個(gè)個(gè)體進(jìn)行下一代種群的繁殖,再進(jìn)行交叉、變異等操作。

7.停止準(zhǔn)則通常采用指定最大代數(shù)(number

of

max

generations,NG)的方式。就像自然界的變異適合任何物種一樣,對(duì)變量進(jìn)行了編碼的遺傳算法沒有考慮函數(shù)本身是否可導(dǎo)、是否連續(xù)等性質(zhì),所以適用性很強(qiáng)。并且,它開始就對(duì)一個(gè)種群進(jìn)行操作,隱含了并行性,也容全局最優(yōu)解。2.4.2遺傳算法的基本原理與流程

表2-2生物學(xué)中遺傳的有關(guān)概念與在遺傳算法中的作用的對(duì)應(yīng)關(guān)系2.4.2遺傳算法的基本原理與流程遺傳算法的變形和改進(jìn),其基本途徑主要有:①改變遺傳算法的組成成分或使用技術(shù),如選用優(yōu)化控制參數(shù)、適合問題特性的編碼技術(shù)等;②采用混合遺傳算法;③采用動(dòng)態(tài)自適應(yīng)技術(shù),在進(jìn)化過程中調(diào)整算法控制參數(shù)和編碼力度;④采用非標(biāo)準(zhǔn)的遺傳操作算子;⑤采用并行處理遺傳算法。2.4.3算法改進(jìn)1.分層遺傳算法對(duì)于一個(gè)問題,首先隨機(jī)生成N×n個(gè)樣本(n≥2,N≥2),即,將總樣本分成N個(gè)子種群,每個(gè)子種群包括n個(gè)樣本,對(duì)每個(gè)子種群獨(dú)立運(yùn)行各自的遺傳算法,記它們?yōu)镚Ai(i=1,2,…,N)。這N個(gè)遺傳算法最好在設(shè)置特性上有較大差異,這樣就可以為將來的高層遺傳算法產(chǎn)生更多種類的優(yōu)良模式。

在每個(gè)子種群的遺傳算法運(yùn)行到一定代數(shù)后,將N個(gè)遺傳算法的結(jié)果種群記錄到二維數(shù)組R[1,2,…,N,1,2,…,n]中,則R[i,j](i=1,2,…N,j=1,2,…,n)表示GAi的結(jié)果種群的第j個(gè)個(gè)體。同時(shí)將N個(gè)結(jié)果種群的平均適應(yīng)度值記錄到數(shù)組A[1,2,…,N]中,A[i]表示GAi的結(jié)果種群平均適應(yīng)度。高層遺傳算法與普通遺傳算法的操作相類似2.4.3算法改進(jìn)圖2-7分層遺傳算法流程圖2.CHC算法CHC算法是Eshelman于1991年提出的一種改進(jìn)遺傳算法第一個(gè)C指代跨世代精英選擇(cross

generational

elitist

selection)策略,H指代異物種重組(heterogeneous

r

bination),第二個(gè)C指代大變異(cataclysmic

mutation)。與基本遺傳算法的不同點(diǎn):基本遺傳算法的遺傳操作就是單純地實(shí)行并行處理;而CHC算法舍棄了這種單純性,來換取遺傳操作較好的效果,并強(qiáng)調(diào)優(yōu)良個(gè)體的保留。2.4.3算法改進(jìn)3.Messy遺傳算法是一種變長度染色體的遺傳算法。在實(shí)際應(yīng)用中,有時(shí)為了簡化描述問題的解,也會(huì)使用不同長度的編碼串。例如，用遺傳算法對(duì)模糊控制器規(guī)則庫進(jìn)行優(yōu)化設(shè)計(jì)時(shí),事先一般不知道規(guī)則數(shù)目,這時(shí)一個(gè)規(guī)則庫對(duì)應(yīng)一個(gè)個(gè)體,個(gè)體的染色體長度可以是變化的對(duì)人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行優(yōu)化設(shè)計(jì)時(shí),如果各層節(jié)點(diǎn)數(shù)是未知的,同樣可以將個(gè)體染色體長度描述為變化的。4.自適應(yīng)遺傳算法Pc和Pm能夠隨適應(yīng)度自動(dòng)改變:當(dāng)種群個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí),使Pc和Pm增大,反之減小。對(duì)于適應(yīng)度高于種群平均適應(yīng)度的個(gè)體,使Pc和Pm減小,反之增大。即好的個(gè)體盡量保持,差的個(gè)體盡快被淘汰。當(dāng)Pc和Pm適當(dāng)時(shí),自適應(yīng)遺傳算法能夠在保持種群多樣性的同時(shí)保證遺傳算法的收斂性。該算法公式：2.4.3算法改進(jìn)其中,fmax是種群中最大適應(yīng)度值;favg是每代種群的平均適應(yīng)度值;f'是要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值;f是要變異的個(gè)體的適應(yīng)度值。公式中參數(shù)的推薦值如下:Pc1=0.9,Pc2=0.6,Pm1=0.1,Pm2=0.001。5.基于小生境技術(shù)的遺傳算法小生境(niche)：是指特定環(huán)境中的一種組織功能。小生境技術(shù)：是將每一代個(gè)體劃分為若干類,每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群,再在種群中以及不同種群之間通過交叉、變異產(chǎn)生新一代種群。小生境技術(shù)特別適合于復(fù)雜多峰函數(shù)的優(yōu)化問題。小生境的模擬方法主要建立在對(duì)常規(guī)選擇操作的改進(jìn)基礎(chǔ)上預(yù)選擇機(jī)制的選擇策略：當(dāng)新產(chǎn)生的子代個(gè)體的適應(yīng)度超過其父代個(gè)體的適應(yīng)度時(shí),所產(chǎn)生的子代個(gè)體才能替代父代個(gè)體而遺傳到下一代個(gè)體中,否則父代個(gè)體仍保留在下一代種群中。排擠機(jī)制選擇策略：在一個(gè)有限的生存空間中,各種不同的生物為了能夠延續(xù)生存,它們之間必須相互競爭有限的資源,因此設(shè)計(jì)一個(gè)排擠因子CF(一般取2或3),從種群中隨機(jī)選擇1/CF個(gè)個(gè)體組成排擠成員,然后依據(jù)新產(chǎn)生的個(gè)體與排擠成員的相似性來排擠一些與排擠成員相類似的個(gè)體,個(gè)體之間的類似性由海明距離來度量。隨著排擠過程的進(jìn)行,群體中的個(gè)體逐漸被分類,從而形成多個(gè)小的生成環(huán)境,并維持群體的多樣性。2.4.3算法改進(jìn)2.4.3算法改進(jìn)6.混合遺傳算法混合遺傳算法體現(xiàn)在兩個(gè)方面:一是引入局部搜索過程,二是增加編碼變換操作過程。在構(gòu)成混合遺傳算法時(shí)的3個(gè)基本原則:盡量采用原遺傳算法的編碼方式;利用原有算法全局搜索的優(yōu)點(diǎn);改進(jìn)遺傳算子。例如,采用遺傳算法與神經(jīng)網(wǎng)絡(luò)相結(jié)合的算法,進(jìn)行時(shí)間序列分析,已成功應(yīng)用于財(cái)政預(yù)算計(jì)算領(lǐng)域。再如,遺傳算法還可以用于學(xué)習(xí)模糊控制規(guī)則和隸屬度函數(shù),從而更好地改善模糊系統(tǒng)的性能。7.并行遺傳算法并行遺傳算法可分為兩類:粗粒度的：主要研究的是群體間的并行性,如Cohoon分析了在并行計(jì)算機(jī)上求解圖劃分問題的多群體的性能;細(xì)粒度的：主要研究的是一個(gè)群體中的并行性,如Kosak應(yīng)用并行遺傳算法解決網(wǎng)絡(luò)圖設(shè)計(jì)問題。1.基于遺傳算法的離散車間雙向調(diào)度問題優(yōu)化[11]

離散制造通常指產(chǎn)品由若干個(gè)零件最終裝配而成,而每個(gè)零件都需要經(jīng)過多道不連續(xù)的工序加工,例如飛機(jī)、汽車、電子設(shè)備等。某些大型機(jī)械產(chǎn)品制造周期長,為了減輕庫存壓力、縮短制造周期,生產(chǎn)過程與裝配過程往往同時(shí)進(jìn)行。在裝配階段,期望同一道裝配工序所需全部零件能在同一時(shí)間完成加工并到達(dá)裝配車間,該批次零件的期望完工時(shí)間就是零件的進(jìn)裝點(diǎn)。本例以進(jìn)裝點(diǎn)為性能評(píng)價(jià)指標(biāo),衡量生產(chǎn)調(diào)度與裝配計(jì)劃是否能協(xié)調(diào)配合。

在交貨期定時(shí)交貨、減少在制品庫存量、縮短生產(chǎn)周期、降低加工成本等目標(biāo)要求下,綜合考慮裝配計(jì)劃的裝配時(shí)長、裝配序列要求,得到各零件的進(jìn)裝點(diǎn),在此基礎(chǔ)上考慮加工約束關(guān)系,確定各零件的加工順序,最終得到加工計(jì)劃。2.4.4制造業(yè)應(yīng)用案例

零件分為關(guān)鍵零件與通用零件,采用正向調(diào)度與反向調(diào)度相結(jié)合的雙向調(diào)度策略。正向調(diào)度是指從零件的第一道加工工序開始,從前往后安排生產(chǎn)計(jì)劃并分配到各機(jī)器上加工,只要生產(chǎn)能力足夠就盡早安排加工任務(wù),直到最后一道工序安排完畢,從而生成生產(chǎn)調(diào)度計(jì)劃,最后一道工序的完工時(shí)間就是零件交貨時(shí)間或者運(yùn)送去裝配的時(shí)間。反向調(diào)度則先為零件的最后一道工序分配加工資源,其完工時(shí)間就是零件的交貨期或進(jìn)裝點(diǎn),然后依次向前進(jìn)行調(diào)度,給前一道加工工序安排加工計(jì)劃,一直到第一道工序安排完畢。通常,對(duì)于關(guān)鍵零件的排產(chǎn)采用反向調(diào)度策略,使其能夠在進(jìn)裝點(diǎn)準(zhǔn)時(shí)完工,對(duì)于通用零件的排產(chǎn)采用正向調(diào)度策略,在不影響關(guān)鍵零件生產(chǎn)的前提下,盡早完工。雙向調(diào)度策略既滿足了車間按時(shí)完工進(jìn)入裝配的需求,又考慮了車間的生產(chǎn)能力。

綜上,該問題可描述為:n個(gè)零件在m臺(tái)機(jī)器上加工,每道工序加工機(jī)器和加工時(shí)長確定,而且每個(gè)零件都有確定的進(jìn)裝點(diǎn),在約束條件的約束下,為各零件排出合理的加工順序,同時(shí)優(yōu)化給定的性能指標(biāo)。假設(shè)生產(chǎn)過程滿足以下條件:

(1)所有加工設(shè)備在零時(shí)刻均處于空閑狀態(tài)。2.4.4制造業(yè)應(yīng)用案例

(2)不同零件相互獨(dú)立,各零件的工序間不需考慮加工先后順序。

(3)同一零件必須嚴(yán)格按照工藝路線進(jìn)行加工,一道工序加工完成后才能開始下一道工序的加工。

(4)同一道裝配工序的所有零件全部完成加工才能開始裝配。

(5)同一時(shí)刻,一臺(tái)機(jī)器只能加工一道工序。

(6)每個(gè)零件在同一時(shí)刻只能在一臺(tái)機(jī)器上加工。

(7)零件的準(zhǔn)備時(shí)間和運(yùn)輸時(shí)間全部被包含在加工時(shí)間內(nèi)。

(8)每個(gè)零件至少需要一道加工工序。根據(jù)上述要求,建立的優(yōu)化目標(biāo)函數(shù)如下2.4.4制造業(yè)應(yīng)用案例

其中,Ci為零件i的完工時(shí)間;Ebi為關(guān)鍵零件i的完工時(shí)間;di為關(guān)鍵零件i的進(jìn)裝點(diǎn);nb為關(guān)鍵零件數(shù);n為零件總數(shù);CTbli代表在進(jìn)裝點(diǎn)l裝配的關(guān)鍵零件i的完工時(shí)間;w代表進(jìn)裝點(diǎn)的數(shù)量,也就是裝配工序數(shù);wl代表在進(jìn)裝點(diǎn)l的進(jìn)行裝配的關(guān)鍵零件數(shù);α為關(guān)鍵零件完工時(shí)間與進(jìn)裝點(diǎn)差值總和的加權(quán)系數(shù);β為關(guān)鍵零件裝配同時(shí)度加權(quán)系數(shù)。

采用遺傳算法求解的具體操作步驟如下:

第1步參數(shù)設(shè)置。設(shè)置種群規(guī)模G、迭代次數(shù)I、交叉概率Pc、變異概率Pm等參數(shù)。

第2步初始化種群。產(chǎn)生遍布解空間的初始種群。

第3步計(jì)算種群所有染色體的適應(yīng)度。

第4步選擇操作。根據(jù)選擇策略選擇出染色體進(jìn)行后續(xù)遺傳操作。

第5步交叉操作。對(duì)經(jīng)過選擇操作選擇出的染色體按照交叉策略進(jìn)行操作,產(chǎn)生新一代子染色體。

第6步變異操作。對(duì)經(jīng)過選擇操作選擇出的染色體按照變異策略進(jìn)行操作,產(chǎn)生新一代子染色體。

第7步終止迭代。重復(fù)進(jìn)行第3~6步,直到滿足迭代次數(shù),輸出最優(yōu)解,并將其轉(zhuǎn)化為具體的車間調(diào)度。2.4.4制造業(yè)應(yīng)用案例2.遺傳算法在生產(chǎn)設(shè)備布局優(yōu)化中的應(yīng)用[12]

生產(chǎn)系統(tǒng)中的設(shè)施布局是影響系統(tǒng)物流成本的重要因素。隨著市場需求的多樣化,多品種、小批量的產(chǎn)品生產(chǎn)方式正在成為造生產(chǎn)企業(yè)的常態(tài),而傳統(tǒng)的大規(guī)模流水線式的生產(chǎn)設(shè)備布局顯然并不適用于這種生產(chǎn)模式。因此科學(xué)合理的設(shè)施布局可以加快生產(chǎn)系統(tǒng)內(nèi)產(chǎn)品和工人的流動(dòng),進(jìn)而縮短交貨期、降低成本、提高生產(chǎn)效率和訂單的響應(yīng)速度與柔性。

生產(chǎn)設(shè)備布局問題可以描述為在一個(gè)生產(chǎn)系統(tǒng)中有n個(gè)作業(yè)部門(可以是設(shè)備、車間或者部門)需要分配在n個(gè)位置,并且每個(gè)位置最多分配一個(gè)作業(yè)部門。求解設(shè)備布局問題的目的是使各作業(yè)部門間的物料或者人員某著名企業(yè)成本最小化。問題的求解模型可表示如下:2.4.4制造業(yè)應(yīng)用案例其中,式(2-27)表示目標(biāo)函數(shù),即物料或者人員某著名企業(yè)的總成本最小;式(2-28)表示某著名企業(yè)成本為某著名企業(yè)量與部門之間的距離的乘積,fik表示從部門i到部門k的某著名企業(yè)量,djh表示從位置j到位置h的距離;式(2-29)表示一個(gè)部門只能安排在一個(gè)位置;式(2-30)表示一個(gè)位置只能分配一個(gè)部門;式(2-31)表示如果部門i布置在位置j,則決策變量xij為1,否則為0。

采用遺傳算法求解該模型,主要計(jì)算步驟如下:

第1步隨機(jī)產(chǎn)生一個(gè)種群規(guī)模為N的初始種群;

第2步解碼并計(jì)算種群中每個(gè)染色體的適應(yīng)度值;

第3步判斷是否達(dá)到最大迭代次數(shù),如果滿足則轉(zhuǎn)第8步;否則轉(zhuǎn)第4步進(jìn)行遺傳迭代;

第4步采用輪盤法選擇適應(yīng)度值高的染色體作為父代個(gè)體形成父代個(gè)體池;

第5步隨機(jī)選擇父代個(gè)體池中的兩個(gè)父代個(gè)體,根據(jù)交叉概率和變異概率完成交叉和變異操作,產(chǎn)生種群規(guī)模為N的子代個(gè)體池;

第6步對(duì)產(chǎn)生的子代個(gè)體池中的染色體進(jìn)行解碼并計(jì)算適應(yīng)度;

第7步合并上次迭代得到的種群和子代個(gè)體池,選擇適應(yīng)度高的染色體組成新的種群,并保持種群規(guī)模為N;

第8步結(jié)束算法,輸出結(jié)果。2.4.4制造業(yè)應(yīng)用案例2.5蟻群優(yōu)化算法

2.5.1

蟻群覓食特性

2.5.2

基本蟻群優(yōu)化算法2.5.3改進(jìn)蟻群優(yōu)化算法2.5.4制造業(yè)應(yīng)用案例算法特點(diǎn)：采用了正反饋并行機(jī)制,優(yōu)點(diǎn)：魯棒性強(qiáng)、分布式計(jì)算、容他方法結(jié)合等缺點(diǎn)：搜索時(shí)間長、容局部最優(yōu)等算法對(duì)應(yīng)的生物學(xué)原理依賴于螞蟻?zhàn)陨矸置诘男畔⑺?pheromone)螞蟻個(gè)體會(huì)在其經(jīng)過的路徑上散播可揮發(fā)的信息素,并且通過頭上的觸角感知到路徑上信息素的濃度,每個(gè)螞蟻個(gè)體都更傾向于選擇信息素濃度較高的路徑作為行進(jìn)方向2.5.1蟻群覓食特性圖2-8自然界中的蟻群覓食行為2.5.2基本蟻群優(yōu)化算法1.基本蟻群優(yōu)化算法原理

圖2-9人工螞蟻搜索實(shí)例(a)人工蟻群搜索環(huán)境;(b)t=0時(shí)人工蟻群搜索情況;(c)t=1時(shí)人工蟻群搜索情況最終都會(huì)選擇較短路徑BFC

2.5.2基本蟻群優(yōu)化算法

螞蟻k(k=1,2,…,m)在運(yùn)動(dòng)的過程中,根據(jù)各個(gè)路徑上的信息素決定轉(zhuǎn)移方向。在搜索過程中,螞蟻根據(jù)各條路徑上的信息素剩余量以及路徑的啟發(fā)信息來計(jì)算狀態(tài)轉(zhuǎn)移概率。pkij(t)表示在t時(shí)刻螞蟻k從城市i轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率:式中,Jk(i)={C-tabuk}(k=1,2,…,m),表示螞蟻k下一步允的城市;tabuk(k=1,2,…,m)是一個(gè)禁忌表,用于記錄螞蟻k當(dāng)前走過的城市;α是信息啟發(fā)式因子,反映了信息素剩余量τij(t)在螞蟻運(yùn)動(dòng)時(shí)所起的作用;β為期望啟發(fā)式信息,反映了啟發(fā)式信息ηij(t)在螞蟻運(yùn)動(dòng)時(shí)所起的作用;ηij(t)為啟發(fā)式信息,表示螞蟻從城市i轉(zhuǎn)移到城市j的期望程度,用公式所示為對(duì)于螞蟻k來說,dij越小,ηij(t)越大,pkij(t)越大。2.5.2基本蟻群優(yōu)化算法2.5.2基本蟻群優(yōu)化算法在路徑i,j上的信息素殘留量的更新方式為

式(2-35)中,ρ表示信息素?fù)]發(fā)系數(shù),則1-ρ表示信息素殘留系數(shù)。為了防止信息素的無限累積,ρ的取值范圍為:ρ∈[0,1)。式(2-36)中的Δτij(t)表示本次迭代中在路徑i,j上的信息素增量,在初始時(shí)刻Δτij(0)=0。Δτkij(t)表示第k只螞蟻在本次迭代中在路徑i,j上的信息素增量。3種不同的基本蟻群優(yōu)化算法模型:蟻周系統(tǒng)(ant-cyclesystem)蟻量系統(tǒng)(ant-quantitysystem)蟻密系統(tǒng)(ant-density

system)這3種系統(tǒng)模型的區(qū)別就在于信息素更新的表達(dá)式Δτkij(t)不同。蟻周系統(tǒng)利用某次迭代中的整體信息來進(jìn)行信息素的更新,即其中,Lk代表螞蟻k在某次迭代中所走的路徑總長度;Q為常數(shù),代表螞蟻迭代一次或者一個(gè)過程在途中釋放的信息素總量。在蟻周系統(tǒng)中,螞蟻每走完一次迭代之后再更新其途徑路徑上的信息素。蟻量系統(tǒng)利用迭代中城市間距離dij這樣的局部信息來進(jìn)行信息素的更新,即蟻密系統(tǒng)只使用常量Q來進(jìn)行信息素的更新,即2.5.2基本蟻群優(yōu)化算法3.基本蟻群優(yōu)化算法實(shí)現(xiàn)以TSP問題為例,基本蟻群優(yōu)化算法的實(shí)現(xiàn)過程如下:初始化參數(shù),令時(shí)間t=0以及迭代次數(shù)Nc=0,將Nmax設(shè)置為最大迭代次數(shù),令路徑i,j的初始化信息量τij(t)=const,初始的時(shí)刻Δτij(0)=0;將m只螞蟻隨機(jī)放置在n個(gè)城市中;迭代次數(shù)Nc=Nc+1;令螞蟻禁忌表tabuk的索引k=1;令k=k+1;根據(jù)每個(gè)螞蟻個(gè)體計(jì)算的狀態(tài)轉(zhuǎn)移概率選擇城市j前進(jìn),j∈C-tabuk;修改禁忌表,將螞蟻選擇的城市加入禁忌表中;如果城市集合C中的城市元素沒有遍歷完,即k<m,則轉(zhuǎn)至(5),否則執(zhí)行(9);更新每條路徑的信息素殘留量;如果滿足結(jié)束條件,迭代結(jié)束并輸出程序結(jié)果,否則清空禁忌表并跳轉(zhuǎn)到(2)。2.5.2基本蟻群優(yōu)化算法2.5.3改進(jìn)蟻群優(yōu)化算法2.蟻群優(yōu)化系統(tǒng)蟻群優(yōu)化系統(tǒng)(ant

colony

system,ACS)解決了基本蟻群優(yōu)化算法在構(gòu)造解的過程中隨機(jī)選擇帶來的算法進(jìn)化速度慢的缺點(diǎn)。在ACS算法的每一次迭代中,只讓最短路徑上的信息素殘留量進(jìn)行更新,且使得信息素殘留量最大的路徑被選中的概率增大,增強(qiáng)全局最優(yōu)信息的正反饋。相比于基本蟻群優(yōu)化算法,ACS在狀