單一的進(jìn)化樹的數(shù)量會(huì)隨著分類群數(shù)量的增長而呈指數(shù)增長，從而變?yōu)橐粋�(gè)天文數(shù)字。由于計(jì)算能力的限制，現(xiàn)在一般只允許對(duì)很小一部分的可能的進(jìn)化樹進(jìn)行搜索。具體的數(shù)目主要依賴于分類群的數(shù)量、優(yōu)化標(biāo)準(zhǔn)、參數(shù)設(shè)定、數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)硬件以及計(jì)算機(jī)軟件。
有兩種搜索方法保證可以找到最優(yōu)化的進(jìn)化樹：窮舉法和樹枝 跳躍法（BB）。對(duì)于一個(gè)很大的數(shù)據(jù)集，這兩種方法都很不實(shí)用。對(duì)分類群數(shù)量的限制主要取決于數(shù)據(jù)結(jié)構(gòu)和計(jì)算機(jī)速度，但是對(duì)于超過20個(gè)分類群的數(shù)據(jù)集，BB方法很少會(huì)得到應(yīng)用。窮舉法要根據(jù)優(yōu)化標(biāo)準(zhǔn)，對(duì)每一個(gè)可能的進(jìn)化樹進(jìn)行評(píng)估。BB方法提供一個(gè)邏輯方法，以確定那些進(jìn)化樹值得評(píng)估，而另一些進(jìn)化樹可被簡單屏蔽。因此BB方法通常要比窮舉法快得多。
絕大多數(shù)分析方法都使用“啟發(fā)式”的搜索。啟發(fā)式現(xiàn)搜索出相近的次優(yōu)化的進(jìn)化樹家族（“島嶼”），然后從中得到優(yōu)化解（“山頂”）。不同的算法用不同程度的精確性搜索這些島嶼和山頂。最徹底也是最慢的程序（TBR，tree bisection-reconnection，進(jìn)化樹對(duì)分重接）先把進(jìn)化樹在每一個(gè)內(nèi)部樹枝處劈開，然后以任意方式將劈開的碎片重新組合起來。最快的算法只是檢查一下相鄰終端的不太重要的重新組合，因此傾向于找到最近的島嶼的山頂。
降低搜索代價(jià)的最好方法是對(duì)數(shù)據(jù)集進(jìn)行剪除。影響優(yōu)化搜索策略選擇的因素（數(shù)據(jù)量，數(shù)據(jù)結(jié)構(gòu)，時(shí)間量，硬件，分析目的）太復(fù)雜，無法推薦一個(gè)簡單可行的處方。因此進(jìn)行搜索的用戶必須對(duì)數(shù)據(jù)非常熟悉且有明確的目標(biāo)，了解各種各樣的搜索程序及自己硬件設(shè)備和軟件的能力。
除上述當(dāng)前應(yīng)用最廣的方法外，還有大量的建立和搜索進(jìn)化樹的其它方法。這些方法包括Wagner距離方法和親近方法（距離轉(zhuǎn)化方法）；Lake的不變式方法（一個(gè)基于特征符的方法，它選擇的拓?fù)浣Y(jié)構(gòu)包含一個(gè)意義重大的正數(shù)以支持顛換）；Hadamard結(jié)合方法（一個(gè)精細(xì)的代數(shù)方陣方法，對(duì)距離數(shù)據(jù)或者觀察到的特征符進(jìn)行修正）；裂解方法（這個(gè)方法決定在數(shù)據(jù)中應(yīng)該支持哪一個(gè)基于距離的可選的拓?fù)浣Y(jié)構(gòu)）；四重奏迷惑（Quartet puzzling）方法可以為ML建樹方法所應(yīng)用，這個(gè)算法相對(duì)而言是個(gè)較快的進(jìn)化樹搜索算法。