遗传算法：改进方向之自适应策略

发布于：2018-10-25 | 分类：numeric calculation

前文基于经典遗传算法的基本原理，使用Python的Numpy模块实现了求解单目标无约束优化问题的程序。但是，针对二元函数最小值的求解结果表明其精度有待提高，本文将根据自适应遗传算法（Adaptive Genetic Algorithm，AGA）的原理改进之前的代码。

自适应遗传算法的改进点在于 自适应调整遗传参数，使得保持群体多样性的同时，保证了算法的收敛性。例如对于基本遗传算法，交叉、变异的概率是固定的，自适应策略则要求在进化过程中进行自适应调整：开始阶段选取较大交叉、变异概率，这样的粗略搜索过程有利于保持种群多样性，后期则调整为较小值以进行细致搜索，防止破化最优解，加快收敛速度。

自适应交叉概率

本文采用的自适应策略为根据参与交叉操作的两个个体a、b的适应度f_a, f_b调整交叉概率：适应度越大交叉概率越小，反之同理。首先设定交叉概率区间[P_{min}, P_{max}]，然后计算种群个体适应度f_i，及平均适应度f_{avg}、最大适应度f_{max}，那么交叉概率P由下式确定：

\begin{align*} P &= P_{max}\,\,\,(f < f_{avg})\\\ P &= P_{max} - (P_{max}-P_{min}) \frac{f-f_{avg}}{f_{max}-f_{avg}} \,\,\,(f \geq f_{avg}) \end{align*}

其中，f=max(f_a, f_b)为参与交叉操作的两个个体中适应度较大者。

得益于之前程序的非耦合性，只需修改GAOperators模块的Crossover类即可。

#----------------------------------------------------------
# GAOperators.py: Selection, Crossover, Mmutation
#----------------------------------------------------------
# ... ...
class Crossover:
    def __init__(self, rate=0.8, alpha=0.5):
        '''
        crossover operation:
            rate: propability of crossover. adaptive rate when it is a list, e.g. [0.6,0.9]
                    if f<f_avg then rate = range_max
                    if f>=f_avg then rate = range_max-(range_max-range_min)*(f-f_avg)/(f_max-f_avg)
                    where f=max(individual_a, individual_b)
            alpha: factor for crossing two chroms, [0,1]
        '''
        # parameters check is skipped
        self.rate = rate
        self.alpha = alpha      

    @staticmethod
    def cross_individuals(individual_a, individual_b, alpha):
        '''
        generate two child individuals based on parent individuals:
        new values are calculated at random positions
        alpha: linear ratio to cross two genes, exchange two genes if alpha is 0.0
        '''
        # random positions to be crossed
        pos = np.random.rand(individual_a.dimension) <= 0.5

        # cross value
        temp = (individual_b.solution-individual_a.solution)*pos*(1-alpha)
        new_value_a = individual_a.solution + temp
        new_value_b = individual_b.solution - temp

        # return new individuals
        new_individual_a = Individual(individual_a.ranges)
        new_individual_b = Individual(individual_b.ranges)

        new_individual_a.solution = new_value_a
        new_individual_b.solution = new_value_b

        return new_individual_a, new_individual_b

    def cross(self, population):

        adaptive = isinstance(self.rate, list)
        # adaptive rate
        if adaptive:
            fitness = [I.fitness for I in population.individuals]
            fit_max, fit_avg = np.max(fitness), np.mean(fitness)

        new_individuals = []        
        random_population = np.random.permutation(population.individuals) # random order
        num = int(population.size/2.0)+1

        for individual_a, individual_b in zip(population.individuals[0:num+1], random_population[0:num+1]):         
            # adaptive rate
            if adaptive:
                fit = max(individual_a.fitness, individual_b.fitness)
                if fit_max-fit_avg:
                    i_rate = self.rate[1] if fit<fit_avg else self.rate[1] - (self.rate[1]-self.rate[0])*(fit-fit_avg)/(fit_max-fit_avg)
                else:
                    i_rate = (self.rate[0]+self.rate[1])/2.0
            else:
                i_rate = self.rate

            # crossover
            if np.random.rand() <= i_rate:
                child_individuals = self.cross_individuals(individual_a, individual_b, self.alpha)
                new_individuals.extend(child_individuals)
            else:
                new_individuals.append(individual_a)
                new_individuals.append(individual_b)

        population.individuals = np.array(new_individuals[0:population.size+1])


if __name__ == '__main__':
    # 普通Crossover实例创建方式
    C = Crossover(0.9, 0.75)

    # 自适应Crossover实例创建方式
    C = Crossover([0.5, 0.9], 0.75)

自适应变异程度

前文的变异操作由变异概率和变异程度（下式中的\alpha）共同决定：

\begin{align*} g &= g - (g-L)\alpha\,\,\,(rand() \leq 0.5)\\\ g &= g + (U-g)\alpha\,\,\,(rand()>0.5) \end{align*}

为了使种群在进化的后期趋于稳定，应减小变异作用。相应措施为减小变异概率或者变异程度，本文采用与进化代数负相关的变异程度值，即设置\alpha与进化代数n，总代数N的关系为：

\alpha = 1.0 - rand()^{1.0-\frac{n}{N}}

相应地，仅需修改GA模块遗传算法类GA的run()函数：

#----------------------------------------------------------
# GA.py: Simple Genetic Algorithm
#----------------------------------------------------------
# ... ...

# # mutation
# self.mutation.mutate(self.population, np.random.rand())

# mutation
rate = 1.0 - np.random.rand()**(1.0-n/gen)
self.mutation.mutate(self.population, rate)

测试

依然采用二元函数Schaffer_N4进行测试，最小值点f(0,1.25313)=0.292579。

f(x,y) = 0.5 + \frac{\cos^2 \left[\sin\left(|x^2-y^2| \right) \right] -0.5}{\left[1+0.001\left(x^2+y^2\right)\right]^2} \,\,\,\, \left(-10 \leq (x,y) \leq 10\right) 

#----------------------------------------------------------
# test.py
#----------------------------------------------------------
from GAComponents import Individual, Population
from GAOperators import RouletteWheelSelection, Crossover, Mutation

# schaffer-N4
# sol: x=[0,1.25313], min=0.292579
schaffer_n4 = lambda x: 0.5 + (np.cos(np.sin(abs(x[0]**2-x[1]**2)))**2-0.5) / (1.0+0.001*(x[0]**2+x[1]**2))**2  

I = Individual([(-10,10)]*2)
P = Population(I, 50)
S = RouletteWheelSelection()
C = Crossover([0.5, 0.9], 0.75)  # 设定自适应交叉概率区间
M = Mutation(0.2)
g = GA(P, S, C, M)

res = []
for i in range(10):
    res.append(g.run(schaffer_n4, 500).evaluation)

val = schaffer_n4([0,1.25313])
val_ga = sum(res)/len(res)

print('the minimum: {0}'.format(val))
print('the GA minimum: {0}'.format(val_ga))
print('error: {:<3f} %'.format((val_ga/val-1.0)*100))

#----------------------------------------------------------
# output:
#----------------------------------------------------------
the minimum: 0.29257863204552975
the GA minimum: 0.29304050741946297
error: 0.1578636726489835 %

经过自适应交叉和变异策略的改进，该算法求解二元函数Schaffer_N4最小值的平均误差度由3%下降至0.2%左右。