遺傳特性算法

1、遺 傳 算 法,Genetic Algorithms,太原理工大學(xué) 數(shù)學(xué)學(xué)院 劉曉峰,數(shù)學(xué)建模一般的步驟和方法,層次分析法量綱分析法圖論法微分方程蒙特卡洛法差值擬合法回歸分析法數(shù)學(xué)規(guī)劃,2024/4/1,2,概率統(tǒng)計(jì)數(shù)值分析,運(yùn)籌學(xué)機(jī)器學(xué)習(xí),GA與計(jì)算機(jī)其余相關(guān)學(xué)科的關(guān)系,,2024/4/1,3,生物在自然界中的生存繁衍，顯示出了其對(duì)自然環(huán)境的自適應(yīng)能力。受其啟發(fā)，學(xué)者致力于對(duì)生物各種生存特性的機(jī)理研究

2、和行為進(jìn)行模擬。 遺傳算法(Genetic Algorithms，GA)就是這種生物行為的計(jì)算機(jī)模擬中令人矚目的重要成果(人工免疫/人工神經(jīng)網(wǎng)絡(luò))。 基于對(duì)生物遺傳和進(jìn)化過(guò)程的計(jì)算機(jī)模擬，遺傳算法使得各種人工系統(tǒng)具有優(yōu)良的自適應(yīng)能力和優(yōu)化能力；它是模擬達(dá)爾文生物進(jìn)化論的自然選擇和孟德?tīng)栠z傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。 遺傳算法所借鑒的生物學(xué)基礎(chǔ)就是

3、生物的遺傳和進(jìn)化。,遺傳算法的起源,最早由美國(guó)密西根大學(xué)的J.Holland教授提出，起源于60年代對(duì)自然和人工自適應(yīng)系統(tǒng)的研究 1967年，Bagley發(fā)表了關(guān)于遺傳算法應(yīng)用的論文，在其論文中首次使用“遺傳算法（ Genetic Algorithm）”一詞 70年代 De Jong基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)

4、 在一系列研究工作的基礎(chǔ)上，80年代由Goldberg進(jìn)行歸納總結(jié)，形成了遺傳算法的基本框架,遺傳算法發(fā)展,1. 復(fù)制 生物的主要遺傳方式是復(fù)制。遺傳過(guò)程中，父代的遺傳物質(zhì)DNA被復(fù)制到子代。即細(xì)胞在分裂時(shí)，遺傳物質(zhì) DNA 通過(guò)復(fù)制而轉(zhuǎn)移到新生的細(xì)胞中，新細(xì)胞就繼承了舊細(xì)胞的基因。 2. 交叉 有性生殖生物在繁殖下一代時(shí)，兩個(gè)同源染色體之間通過(guò)交叉(Crossover) 而重

5、組，即在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合而形成兩個(gè)新的染色體。 3. 變異 在進(jìn)行細(xì)胞復(fù)制時(shí)，雖然概率很小，僅僅有可能產(chǎn)生某些復(fù)制差錯(cuò)，從而使 DNA 發(fā)生某種變異 (Mutation)，產(chǎn)生出新的染色體。這些新的染色體表現(xiàn)出新的性狀。 如此這般，遺傳基因(或染色體)在遺傳的過(guò)程中由于各種各樣的原因而發(fā)生變化。,生物的遺傳方式,遺傳算法的進(jìn)化形式和單位,生物的進(jìn)化是以集團(tuán)的形式共同進(jìn)

6、行的，這樣的一個(gè)團(tuán)體稱為群體/種群(Population)組成群體的單個(gè)生物體稱為個(gè)體(Individual)/染色體(Chromosome)，每一個(gè)個(gè)體對(duì)其生存環(huán)境都有不同的適應(yīng)能力，這種適應(yīng)能力稱為個(gè)體的適應(yīng)度(Fitness) ———— 物競(jìng)天擇個(gè)體的基因(Gene)是遺傳的基本單位遺傳基因在染色體中所占據(jù)的位置稱為基因座同一基因座可能有的全部基因稱為等位基因(Allele),2024/4/1,遺傳算法的簡(jiǎn)單原理,遺傳算法

7、將問(wèn)題域中的可能解看做是群體的一個(gè)個(gè)體或染色體，并將所有個(gè)體編碼成符號(hào)串形式模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程，對(duì)群體反復(fù)進(jìn)行基于遺傳學(xué)的操作（選擇、交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià)依據(jù)適者生存、優(yōu)勝劣汰的進(jìn)化規(guī)則，不斷得到更優(yōu)的群體，同時(shí)以全局并行搜索方式來(lái)搜索優(yōu)化群體中的最優(yōu)個(gè)體，求得滿足要求的最優(yōu)解,2024/4/1,8,遺傳算法是模擬生物在自然環(huán)境下的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化

8、概率搜索方法。,袋鼠與珠穆朗瑪峰的假想實(shí)驗(yàn),在遺傳算法中，假設(shè)將很多只袋鼠降落到喜馬拉雅山脈的任意地方，這些袋鼠并不知道它們被設(shè)想尋找珠穆朗瑪峰，休閑地活著。但每過(guò)幾年，就在海拔較低的一些地方射殺一些袋鼠，并希望存活下來(lái)的那些是多產(chǎn)的，并在那里生兒育女。這個(gè)實(shí)驗(yàn)進(jìn)行N年之后……,2024/4/1,9,,,2024/4/1,10,對(duì)求函數(shù)最大值的優(yōu)化問(wèn)題（或最小值），可描述為下述數(shù)學(xué)規(guī)劃模型：

9、 max f(X) (1-1) s.t. X?R (1-2) R?U (1-3) 其中： X＝[x1,x2,…,xn]T為決策變量， f(X)為目標(biāo)函數(shù)， 式(1-2)、(1-3)為約束條件，

10、 U是基本空間， R是U的一個(gè)子集。 滿足約束條件的解X稱為可行解；集合R表示由所有滿足約束條件的解所組成的一個(gè)集合，叫做可行解集合。,,優(yōu)化問(wèn)題,遺傳算法在函數(shù)優(yōu)化中的應(yīng)用,例：利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值，x為自然數(shù)。將每一個(gè)自然數(shù)看成一個(gè)生命體，通過(guò)進(jìn)化，看誰(shuí)能生存下來(lái)，誰(shuí)就是所尋找的數(shù)字，即問(wèn)題的解。,y=x2,,31 X,Y,,,,0,2024/4/1

11、,12,求解過(guò)程,將每一個(gè)數(shù)作為一個(gè)生命體，就必須給其賦予一定的基因，這個(gè)過(guò)程叫做編碼?？梢詫⒆兞縳編碼成5位長(zhǎng)的二進(jìn)制無(wú)符號(hào)整數(shù)表達(dá)形式，例如：x=13 (01101), 即數(shù)13的基因?yàn)?01101。,編碼,,1,,2,2024/4/1,13,解的編碼,2024/4/1,14,求解過(guò)程,將每一個(gè)數(shù)作為一個(gè)生命體，就必須給其賦予一定的基因，這個(gè)過(guò)程叫做編碼。可以將變量x編碼成5位長(zhǎng)的二進(jìn)制無(wú)符號(hào)整數(shù)表達(dá)形式，例如：x=13 (0110

12、1), 即數(shù)13的基因?yàn)?01101。 由于遺傳的需要，必須設(shè)定一些初始的生物群體，讓其作為生物繁殖的第一代。為了保證生物的多樣性和競(jìng)爭(zhēng)的公平性，初始種群的所有個(gè)體都是通過(guò)隨機(jī)方法產(chǎn)生的。,編碼,,1,,,,2,初始種群的生成,2024/4/1,15,,,2024/4/1,16,,生物的進(jìn)化服從適者生存、優(yōu)勝劣汰的規(guī)則。因此必須規(guī)定什么樣的基因是“優(yōu)”的，什么樣的基因是“劣”的，稱為適應(yīng)度函數(shù)。顯然，定義

13、 為適應(yīng)度函數(shù)，然后計(jì)算所有個(gè)體的適應(yīng)度值。,適應(yīng)度計(jì)算,,,3,4,2024/4/1,17,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,解碼,計(jì)算適應(yīng)度,2024/4/1,18,,生物的進(jìn)化服從適者生存、優(yōu)勝劣汰的規(guī)則。因此必須規(guī)定什么樣的基因是“優(yōu)”的，什么樣的基因是“劣”的，稱為適應(yīng)度函數(shù)。顯然，定義 為適應(yīng)度函數(shù)，然后計(jì)算

14、所有個(gè)體的適應(yīng)度值。 選擇運(yùn)算就是優(yōu)勝劣汰的過(guò)程，把當(dāng)前群體中適應(yīng)度較高的個(gè)體按某種規(guī)則或模型遺傳到下一代群體中，一般適應(yīng)度較高的個(gè)體將有更多的機(jī)會(huì)遺傳到下一代群體中。 選擇是一個(gè)概率選擇的過(guò)程，基因差的不一定會(huì)被淘汰。,適應(yīng)度計(jì)算,,,選擇,,3,,4,2024/4/1,19,,為了產(chǎn)生新的個(gè)體，種群中進(jìn)行交叉繁殖。以某一概率選出兩個(gè)個(gè)體，相互交換一部分基因，就形成了兩個(gè)新的個(gè)體。,交叉,,5,,2024/4/1,20,,,

15、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,交叉位,Pcross,cross,父代個(gè)體,,,,,,,,,,,,,,,,,,,,,,,,,,,,,子代個(gè)體,,交叉概率,,,,,,,,,,,連續(xù)改變個(gè)體多個(gè)基因位上的遺傳信息,1,2,1,2,2024/4/1,21,,為了產(chǎn)生新的個(gè)體，種群中進(jìn)行交叉繁殖。以某一概率選出兩個(gè)個(gè)體，相互交換一部分基因，就形成了兩個(gè)新的個(gè)體。 變異運(yùn)算是將個(gè)體基因中的某一位以一定的小概率發(fā)

16、生變化，也可以產(chǎn)生新的個(gè)體。,交叉,,5,,,,6,變異,2024/4/1,22,,,,,,,,,,,,,,,,,變異位,Pmutate,mutate,父代個(gè)體,,,,,,,,,,,,,,,子代個(gè)體,變異概率,,,,,2024/4/1,23,,為了產(chǎn)生新的個(gè)體，種群中進(jìn)行交叉繁殖。以某一概率選出兩個(gè)個(gè)體，相互交換一部分基因，就形成了兩個(gè)新的個(gè)體。 變異運(yùn)算是將個(gè)體基因中的某一位以一定的小概率發(fā)生變化，也可以產(chǎn)生新的個(gè)體。,交叉

17、,,5,,,,6,變異,,這樣就經(jīng)過(guò)了一代進(jìn)化，通過(guò)上述步驟不斷地循環(huán)進(jìn)化，種群中的個(gè)體基因便逐漸地趨向最優(yōu)。,2024/4/1,24,,,,Y,,,,,,2024/4/1,25,,,,遺傳算法流程圖,2024/4/1,26,步1 在搜索空間U上定義一個(gè)適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc 和變異率Pm，代數(shù)T；,基本遺傳算法步驟,步2 隨機(jī)產(chǎn)生U中的N個(gè)個(gè)體s1, s2, …, sN，組成初始種群S={s1, s2, …,

18、sN}，置代數(shù)計(jì)數(shù)器 t=1；　 步3 計(jì)算S 中每個(gè)個(gè)體的適應(yīng)度 f( ) ；　　步4 若終止條件滿足，則取S中適應(yīng)度最大的個(gè)體作為所求結(jié)果，算法結(jié)束。,步5 否則，按選擇概率P(xi)所決定的選中機(jī)會(huì)，每次從S 中隨機(jī)選定1個(gè)個(gè)體并將其染色體復(fù)制，共做 N 次，然后將復(fù)制所得的 N 個(gè)染色體組成群體 S1 ；,步7 按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個(gè)染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，

19、得群體S3；　　步8 將群體S3作為新一代種群，即用S3代替S，t = t+1，轉(zhuǎn)步3。,步6 按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c 個(gè)染色體，配對(duì)進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體 S2 ；,基本遺傳算法步驟,基本遺傳算法的運(yùn)行參數(shù),M：群體大小，群體規(guī)模POP，即群體中所含個(gè)體的數(shù)量，一般取為20-100T：遺傳運(yùn)算的終止進(jìn)化代數(shù)，一般取為100-500pc：交叉概率(crosso

20、ver rate)，就是參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例，記為Pc，一般取為0.5-0.9pm：變異概率(mutation rate)，是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，一般取為 0.0001-0.1[說(shuō)明]：這4個(gè)運(yùn)行參數(shù)對(duì)遺傳算法的求解結(jié)果和求解效率都有一定的影響，但目前尚無(wú)合理選擇它們的理論依據(jù)。在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過(guò)多次試算后才能確定出這些參數(shù)合理的取值大小或取值范

21、圍。,適應(yīng)度收斂曲線,,遺傳算法工具箱,遺傳算法的工具箱有很多種：Genetic Algorithm Tool 簡(jiǎn)稱GATOOL->GADS Genetic Algorithm Optimization Tool 簡(jiǎn)稱GAOT Genetic Algorithm Toolbox 簡(jiǎn)稱GATBX Simple Genetic Algorithm 1002 簡(jiǎn)稱SGA1002 …………Main functio

22、n Comparation Of Genetic Algorithm Toolbox base Matlab,gatbx工具箱版本查看,>> v=ver('gatbx')v = Name: 'Genetic Algorithm Toolbox' Version: '1.2' Release: '' Da

23、te: '15-Apr-94',遺傳算法與直接搜索工具箱GADS,GADS工具箱是一系列函數(shù)的集合，它們擴(kuò)展了優(yōu)化工具箱和MATLAB數(shù)值計(jì)算環(huán)境的性能。使得用戶能夠求解那些標(biāo)準(zhǔn)優(yōu)化工具箱范圍之外的各種優(yōu)化問(wèn)題。,所有的工具箱函數(shù)都是m文件，可以使用 type function name 查看函數(shù)代碼 也可以通過(guò)編寫(xiě)自己的m文件來(lái)實(shí)現(xiàn)和擴(kuò)展GAD

24、S工具箱的性能。遺傳算法、直接搜索工具箱和優(yōu)化工具箱是緊密結(jié)合在一起的。用戶可以用GADS工具箱來(lái)尋找最佳起始點(diǎn)，然后利用優(yōu)化工具箱或其它程序來(lái)進(jìn)一步尋找最優(yōu)解。,Matlab自帶遺傳算法工具箱GADS,工具箱具有兩種使用方式：(1)以命令行方式調(diào)用遺傳算法函數(shù)ga。(2)通過(guò)圖形用戶界面使用遺傳算法工具箱。,命令行方式：[x fval]=ga(@fitnessfun, nvars, options)@fitnessfun是求最

25、小值的適應(yīng)度函數(shù)句柄；nvars是適應(yīng)度函數(shù)的獨(dú)立變量的個(gè)數(shù)；options是一個(gè)包含遺傳算法選項(xiàng)設(shè)置、屬性參數(shù)的結(jié)構(gòu)，如果沒(méi)有特別改寫(xiě)，則ga使用它本身的默認(rèn)選項(xiàng)值；可以通過(guò)函數(shù)gaoptimset修改設(shè)置； x—最終值到達(dá)的點(diǎn)； fval—適應(yīng)度函數(shù)的最終值,Rastrigin函數(shù),測(cè)試函數(shù)： Rastrigin 定義為： Ras(x)=20+x1*x1+x2*x2- 10(cos(2*pi*x1)+(cos(2*pi*x

26、2)) -5.12<=x1,x2<=5.12,圖形顯示具有多個(gè)局部最小值和一個(gè)全局最小值，出現(xiàn)在點(diǎn)[0,0]處，函數(shù)值為0。在任何不同于[0,0]的局部最小點(diǎn)處，Rastrigin函數(shù)的值均大于0。局部最小處距原點(diǎn)越遠(yuǎn)，該點(diǎn)處Rastrigin函數(shù)的值越大。 之所以選它為測(cè)試函數(shù)，因?yàn)樗性S多局部最小點(diǎn)，具有很強(qiáng)的欺騙性，使得用標(biāo)準(zhǔn)的、基于梯度的查找全局最小的方法十分困難。,命令行方式調(diào)用遺傳

27、算法函數(shù)ga,句柄為@rastriginsfcn 有2個(gè)變量>> [x fval]=ga(@rastriginsfcn,2)Optimization terminated: average change in the fitness value less than options.FunctionTolerance.x = 0.0015 -0.0166fval = 0.0553,遺傳算

28、法求解函數(shù)ga的一般用法,函數(shù)gaoptimset的語(yǔ)法格式為options=gaoptimset('PropertyName1','PropertyValue1','PropertyName 2',' PropertyValue2','PropertyName3','PropertyValue3'......)gaoptimset實(shí)現(xiàn)

29、功能為設(shè)置遺傳算法的參數(shù)和句柄函數(shù)由于遺傳算法本質(zhì)上是一種啟發(fā)式的隨機(jī)運(yùn)算，算法程序經(jīng)常重復(fù)運(yùn)行多次才能得到理想結(jié)果。鑒于此，可以將前一次運(yùn)行得到的最后種群作為下一次運(yùn)行的初始種群，如此操作會(huì)得到更好的結(jié)果。,遺傳算法求解函數(shù)ga的一般用法,[x,fval,reason,output,final_pop]=ga(@fitnessfun,nvars,options);reason為算法停止原因；最后一個(gè)輸出變量final_pop返回的

30、就是本次運(yùn)行得到的最后種群，再將final_pop作為ga的初始種群，語(yǔ)法格式為：options=gaoptimset（'InitialPopulation',final_pop);[x,fval,reason,output,final_pop2]=ga(@fitnessfun,nvars,options);,函數(shù)ga處理自變量范圍問(wèn)題,如果有約束條件（包括自變量的取值范圍），對(duì)于求解函數(shù)的最小值問(wèn)題，可以使用如下

31、語(yǔ)法格式：function f=fitnessfcn(x) if(x3) % x3 %表示有約束x>-1和x<=3，其他約束條件類推 f=inf; else f=f(x); end,遺傳算法函數(shù)ga——帶約束條件,[x,fval]=ga(@fitnessfun,nvars,A,b,Aeq,beq,LB,UB,@nonlcon,options)

32、其中，A是不等式約束AX<=b的系數(shù)矩陣；b是不等式約束AX<=b的常數(shù)項(xiàng)；Aeq是等式約束AeqX=beq的系數(shù)矩陣；beq是等式約束AeqX=beq的常數(shù)項(xiàng)；LB是X的下限;UB是X的上限；@nonlcon是非線性約束函數(shù)。,函數(shù)ga——帶線性約束條件,適應(yīng)度函數(shù)另存為：fun_1.m在當(dāng)前目錄function y=fun_1(x); %x為自變量行向量c=[2 4 6]; % c為目標(biāo)函數(shù)系數(shù)y=c*x‘

33、 % y為適應(yīng)度函數(shù)值，求兩向量的數(shù)量積,函數(shù)ga——帶線性約束條件,A=[1 0 -1;-1 -2 0;-1 0 0]; % A為AX<=b的系數(shù)矩陣 b=[10;-1;0]; % b為AX<=b的常數(shù)項(xiàng) Aeq=[0 1 1]; %AeqX=beq的系數(shù)矩陣beq=12; %

34、AeqX=beq的常數(shù)項(xiàng),函數(shù)ga——帶線性約束條件,>> [x,y]=ga(@fun_1,3,A,b,Aeq,beq,[],[]);>> [x,y]=ga(@fun_1,3,A,b,Aeq,beq); % 或,x = -0.0010 22.0010 -10.0020y = 27.9900,函數(shù)ga——帶非線性約束條件,適應(yīng)度函數(shù)另存為：fun_2.m在當(dāng)前目錄function y=

35、fun_1(x); %x為自變量行向量temp=[1 2 5]*x'+[3 0 1]*x'.^2;y=-temp; % 轉(zhuǎn)換為求最小值,function [budengshi,dengshi]=yueshu(x);%非線性約束 budengshi=[4*x(1)^2+2*x(2)^2+x(3)-46; x(1)+x(1)^2+x(2)^2-5*x(3)-34; 3*

36、x(1)+2*x(1)^2+x(2)+3*x(3)-67];dengshi=x(1)+x(3)^2-13;,函數(shù)ga——帶非線性約束條件,A=[-2 -4 -6; -1 0 0; 0 1 0]; % A為AX<=b的系數(shù)矩陣 b=[-10; 0; 10]; % b為AX<=b的常數(shù)項(xiàng),函數(shù)ga——帶非線性約束條件,>>[x,y]=ga(@fun_2,3,

37、A,b,[],[],[],[],@yueshu)>>y=-y,x = 2.5310 2.9274 3.2356y = -54.2512y = 54.2512,函數(shù)ga——帶非線性約束條件,通過(guò)GUI方式使用遺傳算法,圖形用戶界面打開(kāi)命令：gatool,,,,,,,注意事項(xiàng),遺傳算法工具箱眾多，如不了解選GADS即可。遺傳算法的參數(shù)不少，如不了解選默認(rèn)即可。運(yùn)行遺傳算法時(shí)，因?yàn)槭鞘褂秒S機(jī)

38、數(shù)據(jù)來(lái)進(jìn)行初始化和搜索，所以每一次運(yùn)行后所得到的結(jié)果可能會(huì)稍微不同。為了得到遺傳算法的最好結(jié)果，一般需要以不同的參數(shù)試驗(yàn)，通過(guò)不斷試驗(yàn)，選擇針對(duì)問(wèn)題的最佳參數(shù)，或者對(duì)結(jié)果取加權(quán)平均處理。針對(duì)某些具體模型問(wèn)題，無(wú)法直接使用工具箱，必須自己動(dòng)手編寫(xiě)程序。,2024/4/1,53,遺傳算法的特點(diǎn),遺傳算法是一種自適應(yīng)全局優(yōu)化概率搜索方法區(qū)別于傳統(tǒng)的搜索方式，模擬自然界生物進(jìn)化過(guò)程，采用人工進(jìn)化的方式對(duì)目標(biāo)空間進(jìn)行隨機(jī)化搜索其主要特點(diǎn)是

39、群體搜索策略和群體中個(gè)體之間的信息交換，搜索不依賴于梯度信息，搜索不依賴于初始點(diǎn)，基本上不用搜索空間的知識(shí)或其它輔助信息，不與求解空間有緊密關(guān)系，也就是說(shuō)具有通用性,2024/4/1,54,推薦教材,作者：雷英杰、張善文、李續(xù)武、周創(chuàng)明 出版社：西安電子科技大學(xué)出版社,www.ilovematlab.cn,http://www.madio.net/forum.php?gid=716,2013B 碎紙片的拼接復(fù)原,2024/4/1,58

40、,破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開(kāi)發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。請(qǐng)討論以下問(wèn)題：1.對(duì)于給定的來(lái)自同一頁(yè)印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對(duì)附件1、附件2給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)

41、行拼接復(fù)原。如果復(fù)原過(guò)程需要人工干預(yù)，請(qǐng)寫(xiě)出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果以圖片形式及表格形式表達(dá)。,2013B 碎紙片的拼接復(fù)原,2024/4/1,59,2.對(duì)于碎紙機(jī)既縱切又橫切的情形，請(qǐng)?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型和算法，并針對(duì)附件3、附件4給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過(guò)程需要人工干預(yù)，請(qǐng)寫(xiě)出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果表達(dá)要求同上。3.上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實(shí)情形出發(fā)，還可能有雙