1.1.3 進化規劃

1966年，美國的L. J. Fogel等人[17]在研究人工智能的過程中，為求解預測問題而提出了一種有限狀態機進化模型——進化規劃（EP）。他認為，智能計算要具有兩方面的能力，一方面是預測能力，另一方面是在一定目標指導下對環境做出合理響應的能力。他提出的思想與GA有很多相似之處，但GA更加注重父代與子代在遺傳細節上的聯系，而EP的側重點在于父代與子代的表現行為上的進步。在這個進化模型中，這些機器的狀態變換表通過在對應的離散、有界集上基于均勻隨機分布的規律來修改。EP根據被正確預測的符號數來度量適應值。通過變異，父輩群體中的每個機器產生一個子代，父輩和子代中最好的那一半被選擇而生存下來。1995年，L. J. Fogel與其兒子D. B.Fogel[18]在更進一步研究后，將EP拓展到求解實數空間中的優化問題，并在其變異操作中引入正態分布隨機數，從而使EP成為一種全局優化搜索方法，并用于人工神經網絡的結構學習，并在旅行商問題（Traveling Salesman Problem，TSP）中取得了比較成功的應用。個體的表示同ES，不同之處在于EP不用雜交算子，變異與選擇方式也與ES不同。候選解的變異仍按式（1-2）進行，但標準差為：

式中，F(x)為適應度函數，βj、γj為特定參數，一般取為1和0。從式（1-3）可以看出，EP的標準差是根據適應度函數的大小來調整的。

EP模擬生物種群層次上的進化，在進化過程中主要強調生物種群行為上的聯系，即強調種群層次上的行為進化而建立父、子代間的行為鏈，這意味著好的子代才有資格生存，而無論其父代如何，這樣做適于選擇子代。

EP算法的選擇策略采用的是q競爭機制，這也是與ES算法最大的不同，q競爭可以在選擇優質解的同時，以一定的隨機概率接受少數較差的解。將n個父代進化的n個子代放在一起，從中隨機選擇不重復的q個個體組成一個組，然后依次對2n個個體與隨機挑選出的群組的每個成員進行比較，相比為優的話，則對應的個體的分數加1，最后對分數進行排序，選擇分數最高的n個個體。

EP對環境的適應性很強，對于很多不同的優化問題基本都能收斂至較為優秀的解。EP主要有以下幾個有別于其他進化計算的顯著優點。

（1）GA和ES都有染色體的重組操作，GA以重組為主要的搜索方法，更加注重個體的成長，而EP以變異作為唯一的搜索方法。眾所周知，變異具有更強大的“勘探”能力，相對來說，EP更加注重整個群體的進化，與自然界中優勝劣汰的過程相對應。

（2）GA采取二進制編碼，而EP采用實數編碼，每個個體即代表待優化的一個解，省去了從二進制到十進制的譯碼過程，不會導致編碼位上小的變化卻給解帶來很大的改變的情況。

（3）EP采用q競爭選擇法，如果q選得比較小，則種群多樣性比較好，但較差個體以較大概率進入下一代，可能導致收斂速度變慢；而若q選取過大，就成了確定性選擇，較優個體全部進入下一代；若q選擇得當，則既能兼顧種群多樣性又能控制好收斂速度。

和其他進化算法一樣，EP存在易陷入局部極值、早熟收斂的缺點。因為雖然EP比較注重種群的整體生長，與生物優勝劣汰的競爭原則大致符合，但是適應度值較大的優勢個體以較大的概率進入下一次迭代，而適應度值較小的個體迅速減少，這樣一來，隨著迭代進化的發展，種群中的個體大多數都是適應度值較大的優勢個體，如果這個過程處理不當，可能導致個體之間近親繁殖使種群喪失多樣性，如此將使后面的迭代意義不大，浪費計算量，也使搜索陷入局部優化。

若要增強種群多樣性，可以增大種群大小，使個體盡可能地分散在可行域內，但加大種群無疑會付出計算量和算法運行時間成倍增加的代價；也可以增加變異幅度，使個體得以跳出局部極值點，但變異幅度增加會產生大量非法解，或者在迭代后期收斂速度變慢乃至于不收斂；還可以減小競爭選擇法則中q的大小來保持種群多樣性，但這樣一來，每次迭代后，進入下一次迭代的優勢個體較少，不能很好地指引種群成長，收斂速度就會相應減慢。