Генетическая оптимизация на Python

пример поиска экстремума функции двух переменных

генетический алгоритм Python

Генетические алгоритмы — сравнительно новый комплекс подходов в мире вычислений. Они представляют собой алгоритмы направленного поиска, организация которых выполнена во многом по аналогии с биологическими процессами репродукции и формирования популяций. В качестве цели при этом могут выступать различные свойства систем или их структуры. Это весьма широкий круг задач, начиная от определения экстремумов функций многих переменных, и заканчивая поиском оптимальных структур организации сложных систем.

Генетический поиск может использоваться и для численного упрощения символьных выражений или нахождения альтернативных их представлений. Например, имеется функция \(\cos(x)\); требуется найти тождественное ей выражение, используя суперпозицию элементарных арифметических операций \(\{\times, /, -, +, \sqrt \}\) и функции \(\sin\). Зная основное тригонометрическое тождество \(\sin^2(x) + \cos^2(x) = 1\) мы легко можем предложить такую запись \(\cos(x)=\sqrt{1-\sin^2(x)}\); но это простая задача, а если речь идет об оптимизации сложного выражения или обнаружения неизвестного тождества. Здесь на помощь могут прийти подходы направленного поиска. Критерием при реализации генетического поиска при этом может выступать невязка значений текущего и целевого выражений, вычисленная не некотором наборе точек.  Поиск тождественного представления символьного выражения, например, вполне бы мог закончиться следующими вариантами решений:

  • \(\cos(x) = \sqrt{(\frac{x}{x}-\sin^2(x))}\)
  • \(\cos(x) = \sqrt{(1-\sin^2(x) - \sin(\sin(\sin(\ldots \sin(\frac{x}{x})))))}\)

Не очень красивые, правда?! Но они вполне возможны, если не предусмотреть дополнительную процедуру упрощения структуры выражения. 

Тема символьного поиска — весьма интересный раздел, задачи которого вполне могут решаться на базе генетических подходов.

Здесь, однако, мы рассмотрим реализацию на языке Python простейшей задачи генетического поиска — нахождения минимума функции двух переменных.

Пошагово генетическая оптимизация функции выглядит следующим образом:

  1. На первом этапе строится начальная популяция приближений искомого решения; ее можно формировать случайным образом; применительно  к задаче оптимизации функции двух переменных  популяция — это набор векторов \((x_{11}, x_{12}), (x_{21}, x_{22}),\ldots, (x_{n1}, x_{n2}),\) , где n – размер популяции.
  2. Выбирается пара решений, каждое значение с определенной вероятностью мутирует на какое-либо маленькое значение, и, наконец, формируется новый член популяции – так, что часть его компонент взяты от одного родительского элемента, а часть от другого. Если \((x_1, x_2)\)  и \((y_1, y_2)\) —  родительские элементы, то они продуцируют нового члена популяции вида: \((x_1+\Delta_1, y_2+\Delta_2 )\), где \(\Delta_1, \Delta_2\) — некоторые маленькие случайные значения, характеризующие степень мутации.
  3. Предыдущий шаг повторяется некоторое определенное число раз, в результате — популяция увеличивается на данное число новых членов.
  4. Далее происходит шаг "естественного" отбора — для каждого члена популяции вычисляется соответствующее значение оптимизируемой функции. Этот массив значений упорядочивается по возрастанию и в следующую популяцию переходит только определенный процент членов, приведших к наименьшим значениям функции.
  5. Процедура повторяется с шага 2 и заканчивается, например, по прошествии 1000 подобных повторений (эпох).

Этот простейший вариант эволюционного поиска минимума функции двух переменных был реализован на Python:

#coding: utf8
import numpy as np 
from itertools import combinations 
import copy

# функция для оптимизации
func = lambda x, y: (x-5) ** 2 + (y-1) ** 2


class GeneticEvolution:
    '''Генетическая оптимизация функции двух переменных'''
    
    def __init__(self, func, mut_prob=0.8, kill_portion=0.2, max_pairs=1000):
        self.func = func
        self.population = [] # Current symbolic expression
        self.mutation_probability = mut_prob
        self.portion = kill_portion
        self.max_pairs = max_pairs
    
    # начальная случайная популяция
    def generate_random_population(self, size=100):
        self.population = np.random.rand(100, 2).tolist()
    
    # инициализация поиска
    def initialize(self):
        self.generate_random_population()
    
    # основная функция "генетического" поиска
    def evolute(self, n_steps=1000):
        n = 0
        while n < n_steps:
            print 'Шаг:', n
            n += 1
            ind = 0
            newpopulation = copy.copy(self.population) 
            for comb in combinations(range(len(self.population)), 2):
                ind += 1
                if ind > self.max_pairs:
                    break
                a = self.mutate(self.population[comb[0]])
                b = self.mutate(self.population[comb[1]])
                newitem = self.crossover(a, b)
                newpopulation.append(newitem)
            self.population = self.killing(newpopulation) 
        return np.min([func(x,y) for x, y in self.population])

    def killing(self, population):
        res = np.argsort([self.func(*item) for item in population])
        res = res[:np.random.poisson(int(len(population) * self.portion))]
        return np.array(population)[res].tolist()
                
    # обмен значениями (кроссинговер), происходит с вероятностью 0.5 по умолчанию
    def crossover(self, a, b, prob=0.5):
        if np.random.rand() >  prob:
            return [a[0], b[1]]
        else:
            return [b[0], a[1]]

    # мутация значений происходит с определенной вероятностью (0.8 - по умолчанию) 
    def mutate(self, a):
        if np.random.rand() < self.mutation_probability:
            newa = a + (np.random.rand(2) - 0.5)*0.05
        else:
            newa = a
        return newa
        
g = GeneticEvolution(func=func)
g.initialize()
res = g.evolute()
print 'Результат оптимизации:', res

Поиск из исходной популяции равномерно распределенных точек на единичном квадрате \([0,1]\times[0,1]\) за 1000 шагов эволюции приводит к следующему результату:

Результат оптимизации: 5.17201057012e-14

Интересно также проследить процесс эволюции и естественного отбора точек:

Python: генетическая оптимизация функции

blog comments powered by Disqus