Python实现遗传算法求函数最值

Python实现遗传算法求函数最值

详细源代码：GA.py
1、算法过程图解

2、详细过程举例说明
（1）待求解方程

（2）确定编码方案
主要是确定编码长度：

    def segment_length(self):
        length = []
        precision =[]
        for i in self.variable_range:
            len = math.ceil(math.log((i[1] - i[0]) / self.theta, 2.0))
            length.append(len)
            precision.append((i[1] - i[0]) / (2.0 ** len))
        return length,precision

（3）初始化种群
本文采用的是二进制编码方式，即生成随机0、1序列。

    def species_origin(self, length):
        population = []
        for i in range(self.population_size):
            v = []
            for j in range(sum(length)):
                if random.random() < 0.5:
                    v.append(1)
                else:
                    v.append(0)
            population.append(v)
        return population

（4）计算个体适应度
把一个二进制串(b0,b1,…bn)转化为区间里面对应的实数值可以通过下面两个步骤：
1、将一个二进制串代表的二进制数转化为10进制数；

2、对应区间内的实数。

    def fitness(self,population, length, precision):
        fit = []
        for v in population:
            x = []
            I = 0
            for i in range(len(length)):
                s = 0
                for j in range(length[i]):
                    s = s + v[I + length[i] - 1 - j] * (2 ** j)
                I = I + length[i]
                x.append(s * precision[i] + self.variable_range[i][0])
            fit.append(function(x))
        return fit

（5）通过轮盘赌选择个体放入交叉池

    def rouette(self, population, N, length, precision):
        fit = self.fitness(population, length, precision)
        p = []
        f = 0
        sum_fit = sum(fit)
        for i in fit:
            f = f + i
            p.append(f / sum_fit)
        next_population = []
        for i in range(N):
            qa = random.random()
            for j in range(len(p)):
                if qa < p[j]:
                    next_population.append(population[j])
                    break
        return next_population

（6）交叉
采用两点交叉作为交叉算子：

    def crossover(self, population):
        chromosome_length = sum(self.segment_length()[0])
        next_population = self.population_copy(population)
        for i in range(int(len(next_population)/2)):
            if random.random() <= self.pc:
                a, b = random.randint(1, chromosome_length), random.randint(1, chromosome_length)
                index1 = min(a, b)
                index2 = max(a, b)
                cross = next_population[2 * i][index1:index2]
                next_population[2 * i][index1:index2] = next_population[2 * i + 1][index1:index2]
                next_population[2 * i + 1][index1:index2] = cross
        return next_population

（7）变异
采用单点变异作为遗传算子。

    def mutation(self, population):
        next_population = self.population_copy(population)
        n = sum(self.segment_length()[0])
        for i in range(len(next_population)):
            for j in range(n):
                if random.random() < self.pm:
                    next_population[i][j] = (next_population[i][j] + 1) % 2
        return next_population

（8）选择
计算所有后代个体的适应度， 选出最好的E个个体直接保留到下一代种群。然后，根据轮盘赌选择N-E个个体进入下一
代种群。

    def selection(self, population, length, precision):
        fit = self.fitness(population, length, precision)
        next_population = []
        for i in range(self.E):
            index = fit.index(max(fit))
            next_population.append(population.pop(index))
            fit.pop(index)
        next_population = next_population + self.rouette(population + next_population, self.population_size-self.E, length, precision)
        return next_population

详细源代码：GA.py