Генетический алгоритм. Кодирование. Целочисленное кодирование и декодирование. Задача минимизации функции. Реализация генетического алгоритма с кодированием на Go

February 3, 2019 02:10

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

Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Задание: найти максимум функции y(x) = 1/x, где х принадлежит [-4; 0).

Полная версия задания: скачать.

Для запуска программы использовать команду go build file.go. Необходимо наличие компилятора GoLang на используемой машине.

Параметры меняются в функции main программы:

  • population_size := 3 // размер популяции
  • generations_count := 500 // число поколений
  • p_crossover := 0.5 // вероятность кроссовера
  • p_mutation := 0.5 // мутации
  • capacity := 64 // вместимость 
  • target := func(x float64) float64 { return 1 / x } // функция 1/х
  • x_min, x_max := -4.0, 0.0 // и Х принадлежит этому промежутку

Результат работы программы (вывод программы):

  • последнее закодированное поколение;
  • закодированное лучшее решение;
  • раскодированное поколение;
  • раскодированное лучшее решение.

Пример работы программы (скриншот, нажать для увеличения):

Пример работы программы
Пример работы программы

Реализация на Go:

package main

import (
    "fmt"
    "math"
    "math/rand"
)

// методы, которые выполняют целочисленное кодирование 
func calc_r(g uint64, m, x_max, x_min float64) float64 { // декодирование
    return float64(g)*(x_max-x_min)/(math.Pow(2, m)-1) + x_min
}

func calc_g(r float64, m, x_max, x_min float64) uint64 {
    return uint64((r - x_min) * (math.Pow(2, m) - 1) / (x_max - x_min)) // кодирование
}

func crossover(male, female uint64) uint64 {
    point := uint(rand.Intn(64))
    return (male & (0xFFFFFFFFFFFFFFFF << point)) | (female & (0xFFFFFFFFFFFFFFFF >> point))
}

func mutation(gen *uint64, point uint) {
    *gen = *gen ^ (1 << point)
}

func fitness(p uint64, f func(float64) float64) float64 {
    r := calc_r(p, 64, 0, -4)
    return f(r)
}

func get_best_person(generation []uint64, target func(float64) float64) uint64 {
    best := generation[0]

    for _, person := range generation {
        if fitness(person, target) > fitness(best, target) {
            best = person
        }
    }

    return best
}

func main() {

    population_size := 3 // размер популяции
    generations_count := 500 // число поколений
    p_crossover := 0.5 // вероятность кроссовера
    p_mutation := 0.5 // мутации
    generations_delta := 0.5
    capacity := 64

    target := func(x float64) float64 { return 1 / x } // функция 1/х
    x_min, x_max := -4.0, 0.0 // и Х принадлежит этому промежутку

    genesis := make([]uint64, population_size)

    for i, _ := range genesis {
        genesis[i] = rand.Uint64()
    }

    k := 0

    for k < generations_count { // пока не превышен предел одинаковых поколений
        var generation []uint64

        for len(genesis) > 0 { // пока в генезисе есть особи

            if len(genesis) == 1 { // если осталась последняя
                generation = append(generation, genesis[0]) // перекидываем ее без изменений
                genesis = make([]uint64, 0)                 // очищаем генезис

            } else {
                male_i := rand.Intn(len(genesis)) // случайно выбираем мужскую особь
                male := genesis[male_i]
                genesis = append(genesis[:male_i], genesis[male_i+1:]...) // удаляем из генезиса

                female_i := rand.Intn(len(genesis)) // случайно выбираем женскую
                female := genesis[female_i]
                genesis = append(genesis[:female_i], genesis[female_i+1:]...) // удаляем из генезиса

                var child *uint64

                if rand.Float64() > p_crossover { // если сработало скрещивание
                    _child := crossover(male, female) // то ребенок это кроссовер мужской и женской 
                    child = &_child
                    for i := 0; i < capacity; i++ {
                        if rand.Float64() > p_mutation {
                            mutation(child, uint(i)) // после чего пытаемся сделать мутацию
                        }
                    }
                }

                if child != nil { // если появился потомок
                    // если потомок лучше чем мужская или женская особь
                    if fitness(*child, target) > fitness(male, target) || fitness(*child, target) > fitness(female, target) {
                        generation = append(generation, *child) // добавить потомка в следующее поколение

                        if fitness(male, target) > fitness(female, target) { // если мужская особь лучше женской
                            generation = append(generation, male) // добавить женскую особь в новое поколение
                        } else {
                            generation = append(generation, female) // добавить мужскую особь в новое поколение
                        }

                    } else { // если потомк не лучше - перебросить в новое поколение без изменений
                        generation = append(generation, male)
                        generation = append(generation, female)
                    }

                } else { // если потомка не было - перебросить в новое поколение без изменений
                    generation = append(generation, male)
                    generation = append(generation, female)
                }
            }
        }

        genesis = append(genesis, generation...)

        if (fitness(get_best_person(generation, target), target) - fitness(get_best_person(genesis, target), target)) < generations_delta {
            k += 1
        }
    }

    fmt.Println(genesis) // последнее закодированное поколение
    best_person := get_best_person(genesis, target)
    fmt.Println(best_person) // закодированное лучшее решение

    points := make([]float64, 0)

    for _, val := range genesis {
        points = append(points, calc_r(val, float64(capacity), x_max, x_min))
    }

    fmt.Println(points) // раскодированное поколение
    fmt.Println(calc_r(best_person, float64(capacity), x_max, x_min)) // раскодированное лучшее решение
}