以目標值增進為適合度函數的遺傳演算法之研究

Abstract

遺傳演算法是由物競天擇，適者生存所啟示的一種適應性搜尋法。遺傳演 算法藉由個體的目標函數值來決定其適合程度，即以目標值為適合度函數 。經由世代接著世代的繁殖，遺傳演算法所維持的族群中個體的比率會改 變，則達成了此適應性。但是當成熟的族群遭遇了長期收斂，此族群將含 有類似好的個體，則遺傳演算法的適應性將會因漸衰退的選擇壓力而失去 。我們提出了一個平移不影響的非遞增適合度函數來嘗試解決選擇壓力衰 退的問題。此新的適合度函數使用目標值增進來代替傳統遺傳演算法所使 用的目標值本身。增進值是由計算個體的新目標值和舊目標值的差異值所 獲得。因為每個子代個體是由２位親代個體所產生，我們使用此２位親代 個體目標值的平均值做為一個體的舊目標值。然後將這些增進值加上最小 增進值的負值以保証適合度函數是正值的。實驗結果顯示我們的方法成功 地解決選擇壓力衰退的問題。另外，此新適合度函數以非遞增的方式著手 於目標函數提供了不同的線索來輔助傳統的遺傳演算法。 Genetic algorithms are adaptive search techniques that are inspired from natural selection, i.e. survival of the fittest. A genetic algorithm determines how fit an individual is by its evaluation value of the objective function, i.e. a fitness function of objective values. With reproduction through generation after generation, the adaptiveness is achieved by means of the change in the proportions of individuals in a population. But when a population is subjected to long convergence in a mature run, the population will consist of similarly good individuals. Then the adaptiveness of a genetic algorithm will be lost due to the problem of declining selective pressure. We proposed a translation invariant and nonmonotonic fitness function to try to solve the problem of declining selective pressure. This new fitness function uses improvement of objective values in replace of using objective values themselves as in traditional genetic algorithms. The improvement is obtained by computing the difference of an individual's new objective value and its old objective value. Because every offspring is produced by two parents, we use the average of the two parents' objective values as an individual's old objective value. Then we translate the improvement by adding the negative value of the minimum improvement to guanrantee the positiveness of the fitness function. The empirical results showed that it succeeded in fighting the problem of declining selective pressure. In addition, the nonmonotonically way in which the new fitness function attacks an objective function provides different clues to complement the traditional genetic algorithms.