유전 알고리즘

유전 알고리즘(GA)은 자연 선택 과정에 의해 계발된 알고리즘으로 문제를 생성하는 고품질 해결 방안에 사용된다. 그렇지 않으면 이런 문제들은 해결하기 어려울 것이다.

여행 세일즈맨 문제

여행 세일즈맨 문제(TSP)는 악명 높은 문제로 여행 세일즈맨은 반드시 이미 알고 있는 거리의 각 도시를 여행하고 가능한 한 짧은 시간/경로 내에 출발 도시로 돌아가야 한다.
아래 그림에서 보듯이 모든 동그라미는 하나의 도시이고 푸른 선은 그것들을 참관하는 노선이다.

왜 폭력을 쓰지 않습니까?

좋아, 폭력으로 이 문제를 해결해 보자.
우선 5개 도시를 예로 들자. 즉, 우리는 5!개 노선, 즉 120개 노선을 계산해서 우리가 가장 짧은 경로를 확보해야 한다.
지금 우리가 50개 도시를 위해 이렇게 한다면,

5! = 120

10! = 3628800

15! = 1307674368000

20! = 2432902008176640000

50! = 30414093201713378043612608166064768844377641568960512000000000000

우리는 이곳에서 야만적으로 우리에게 전진을 강요하는 것이 얼마나 도움이 되지 않는지 볼 수 있다.

우리 한번 해보자.

따라서 우리는 Genetic Algorithm이 우리가 가장 짧은 경로를 찾을 수 있도록 어떻게 도와주는지 보게 될 것이다.
간단하게 말하면 유전 알고리즘의 작업 원리는 다음과 같다.

랜덤 초기 용액/염색체(Initial Population 또는 염색체라고 함)

선택

crossover(혼합 쌍둥이 염색체/용액을 통해 새로운 용액 또는 염색체 생성)

mutate(작은 솔루션 변경)

fitness(해결 방안이 유용하거나 우리의 요구를 충족시키는지 검사), 만약에 우리가 그것을 사용하여 새로운 후손(다음 세대의 부모)을 창설한다면 이 순환은 많은 세대가 우리가 원하는 것을 지속할 것이다.

그래서TSP과 관련하여 다음을 수행합니다.

생성 도시

function generate_cities(number_of_cities, map_limit)

    cities = []
    for city_counter in 1:number_of_cities
        push!(cities, 
            Dict(
                "id" => city_counter, 
                "x" => round(rand() * map_limit), 
                "y" => round(rand() * map_limit)
            )
        )
    end
    println("Cities Generated:", size(cities)[1])
    return cities
end
# calling generate_cities method to create cities
generate_cities(5,500)

우리는 이 도시를 사전으로 저장하고 있다.
도시당 id 및 (x,y) 위치

 ("id" => 1,"x" => 480.0,"y" => 157.0)
 ("id" => 2,"x" => 4.0,"y" => 465.0)
 ("id" => 3,"x" => 57.0,"y" => 25.0)
 ("id" => 4,"x" => 411.0,"y" => 322.0)
 ("id" => 5,"x" => 44.0,"y" => 460.0)

용액을 염색체로 표시하다.

우리 문제를 해결하는 방법은 한 도시에서 다른 도시로 가는 노선이다.우리는 그것을 하나의 정수 그룹으로 쓸 수 있는데, 그 중 모든 숫자는 하나의 도시 id를 대표한다.

[1,2,5,4,3,1]

그러므로 상술한 노선이나 염색체에 대해 우리는 도시 1->도시 2에서 시작하여 이와 같이 유추한다...드디어 도시 1로 돌아왔다.

교차 함수

여기서 우리는 두 개의 부염색체에서 값을 추출함으로써 새로운 염색체를 생성한다.
이 문제에 대해 우리는 유전자/도시 id가 중복되지 않고 새로운 염색체를 생성하는 것을 확보하기만 하면 된다.
여러 가지 방법으로 교차를 실현할 수 있다. 예를 들어 단점 교차, 다점 교차 등이다.
우리는 염색체에 있는 무작위 점을 선택하고 간단한 교환을 통해 새로운 염색체를 만들 것이다.

function crossover(parent_one_chromosome, parent_two_chromosome, crossover_point)
    offspring_part_one = parent_one_chromosome[1:crossover_point]
    for gene in offspring_part_one
        if gene in parent_two_chromosome
            gene_loc = findfirst(el -> el == gene, parent_two_chromosome)
            splice!(parent_two_chromosome, gene_loc)
        end
    end
    return vcat(offspring_part_one, parent_two_chromosome)
end

돌연변이 함수

간단하게 말하면 돌연변이는 염색체의 무작위 변화로 정의할 수 있다.
여기서 우리는 두 유전자의 위치를 간단하게 교환할 것이다.

function mutate(offspring)
    random_mutation_point1 = rand(1:length(offspring))
    random_mutation_point2 = rand(1:length(offspring))
    offspring[random_mutation_point1], offspring[random_mutation_point2] = offspring[random_mutation_point2], offspring[random_mutation_point1]
    return offspring
end

적응도 함수

적응도 함수의 직책은 모든 염색체의 점수를 계산하는 것이다. 그러면 우리는 그것을 사용할지 말지를 결정할 수 있다
염색체는 다음 세대에 있거나 버려진다.
우리의 문제에 있어서 점수는 노선/염색체를 정하는 여행 거리이다.여행 거리는 짧을수록 좋다.
여행 거리를 계산하기 위해서 우리는 간단하게 첫 번째 도시부터 다음 도시, 그리고 다음 도시로 간다. 그래서...그리고 출발 도시로 돌아와 우리가 주행하는 거리를 더하면 우리는 이 특정 노선의 점수를 얻게 된다.

function calculate_distance_between_two_points(point1, point2)
    return sqrt((((point2[1] - point1[1]))^2) + (((point2[2] - point1[2]))^2))
end

function calculate_chromosome_travel_distance(chromosome)
    travel_distance = 0
    chromosome = vcat(1, chromosome, 1)
    for geneId in 1:length(chromosome) - 1
        point1 = (
            cities[chromosome[geneId]]["x"],
            cities[chromosome[geneId]]["y"]
            )
        point2 = (
            cities[chromosome[geneId + 1]]["x"],
            cities[chromosome[geneId + 1]]["y"]
            )
        travel_distance += calculate_distance_between_two_points(point1, point2)
    end
    println("travel distance:", chromosome, " : ", travel_distance)
    return travel_distance
end

발생 초기 인구:

우리는 초기의 전체적인 함수를 생성할 수 있도록 정의할 것이다.

# We shuffle the chromosome here
function shuffle_chromosome(chromosome)
    for i in 1:size(chromosome)[1]
        random_point = rand(1:5, 1)[1]
        chromosome[i], chromosome[random_point] = chromosome[random_point], chromosome[i]
    end

    println("Created chromosome", chromosome)
    return chromosome
end


function generate_initial_population(initial_population_size)
    chromosomes = []
    for population_counter in 1:initial_population_size
        chromosome = shuffle_chromosome(copy(initial_chromosome))
        push!(chromosomes, 
            Dict(
                "chromosome" => chromosome,
                "distance" => calculate_chromosome_travel_distance(chromosome)
            )
        )
    end
    return chromosomes
end

[3, 9, 4, 8, 10, 5, 1, 2, 7, 6]
[8, 1, 6, 9, 10, 5, 2, 4, 3, 7]
[2, 9, 10, 8, 5, 4, 6, 1, 3, 7]
[5, 6, 10, 7, 4, 3, 1, 2, 8, 9]
[2, 10, 9, 4, 6, 5, 1, 3, 8, 7]

주요 부분

여기서 우리는 함수를 정의했다. 함수는 주어진 대수에서 GA를 실행하고, 세대마다 주어진 수량의 자대를 만들고, 그 적용성을 검사하며, 세대마다 계속 순환한다.

function evolve(generation_count, offsprings_count, crossover_point)
    for generation in 1:generation_count

        for offspring_count in 1:offsprings_count
            println("generation: ", generation, " offspring: ", offspring_count)
            random_parent_one_id = rand(1:size(chromosomes)[1])
            random_parent_two_id = rand(1:size(chromosomes)[1])
            random_parent_one = copy(chromosomes[random_parent_one_id]["chromosome"])
            random_parent_two = copy(chromosomes[random_parent_two_id]["chromosome"])
            offspring = crossover(random_parent_one, random_parent_two, crossover_point)
            offspring = mutate(offspring)
            push!(chromosomes, 
                Dict(
                    "chromosome" => offspring,
                    "distance" => calculate_chromosome_travel_distance(offspring)
                    )
            )
        end
        sort!(chromosomes, by=x -> x["distance"], rev=false)
        splice!(chromosomes, 6:size(chromosomes)[1])
    end
end

이제 GA를 실행하도록 하겠습니다.

# creating 10 cities randomly
cities = generate_cities(10, 500)
initial_chromosome = [2:length(cities);]
# generating 10 initial chromosomes
chromosomes = generate_initial_population(10)

# we are running GA for
# 5 generations
# 5 offsprings per generation
# random crossover point as 2
evolve(5, 5, 2)
println("--------------------------------------------------------")
println("Optimal route:", vcat(1, chromosomes[1]["chromosome"], 1))
println("travel_distance:", chromosomes[1]["distance"])

만약 우리가 실행한다면, 우리는 아래의 출력을 얻을 것이다.

출력:

generation: 1 offspring: 1
travel distance:[1, 3, 9, 10, 7, 5, 4, 6, 8, 2, 1] : 2780.551726305925
generation: 1 offspring: 2
travel distance:[1, 5, 10, 6, 9, 3, 2, 4, 7, 8, 1] : 2236.035984494435
generation: 1 offspring: 3
travel distance:[1, 10, 7, 3, 9, 5, 4, 6, 8, 2, 1] : 2627.3533869849102
generation: 1 offspring: 4
travel distance:[1, 7, 6, 4, 10, 3, 5, 2, 8, 9, 1] : 3078.2871083508203
generation: 1 offspring: 5
travel distance:[1, 3, 9, 10, 7, 2, 4, 5, 8, 6, 1] : 3074.581278954089
generation: 2 offspring: 1
travel distance:[1, 9, 8, 5, 10, 4, 3, 2, 6, 7, 1] : 2882.8847896850843
generation: 2 offspring: 2
travel distance:[1, 5, 10, 6, 2, 3, 9, 4, 7, 8, 1] : 1864.9566066991729
generation: 2 offspring: 3
travel distance:[1, 9, 8, 5, 10, 2, 3, 4, 6, 7, 1] : 2889.200659672017
generation: 2 offspring: 4
travel distance:[1, 4, 10, 6, 9, 3, 2, 5, 7, 8, 1] : 2520.4527035595024
generation: 2 offspring: 5
travel distance:[1, 9, 10, 6, 3, 5, 2, 4, 7, 8, 1] : 2443.441192706744
generation: 3 offspring: 1
travel distance:[1, 2, 10, 6, 9, 8, 5, 7, 4, 3, 1] : 2177.1886229349225
generation: 3 offspring: 2
travel distance:[1, 2, 10, 5, 6, 9, 8, 7, 4, 3, 1] : 1745.6328718972204
generation: 3 offspring: 3
travel distance:[1, 5, 4, 2, 6, 9, 8, 7, 10, 3, 1] : 2491.210252809206
generation: 3 offspring: 4
travel distance:[1, 7, 5, 6, 9, 3, 2, 4, 10, 8, 1] : 2867.790574182069
generation: 3 offspring: 5
travel distance:[1, 10, 6, 5, 9, 3, 2, 7, 4, 8, 1] : 2158.331962819929
generation: 4 offspring: 1
travel distance:[1, 4, 10, 6, 2, 3, 9, 5, 7, 8, 1] : 2375.395804596975
generation: 4 offspring: 2
travel distance:[1, 4, 10, 2, 6, 9, 8, 5, 7, 3, 1] : 2696.2819714580255
generation: 4 offspring: 3
travel distance:[1, 5, 3, 6, 9, 10, 2, 7, 4, 8, 1] : 2585.1841206421177
generation: 4 offspring: 4
travel distance:[1, 4, 6, 2, 9, 8, 5, 7, 10, 3, 1] : 2927.589295286965
generation: 4 offspring: 5
travel distance:[1, 5, 3, 10, 6, 9, 7, 2, 4, 8, 1] : 2610.376635133937
generation: 5 offspring: 1
travel distance:[1, 3, 10, 5, 6, 9, 8, 7, 4, 2, 1] : 1919.461172591361
generation: 5 offspring: 2
travel distance:[1, 10, 6, 8, 9, 3, 2, 7, 4, 5, 1] : 2488.399757690674
generation: 5 offspring: 3
travel distance:[1, 6, 10, 3, 5, 9, 8, 7, 4, 2, 1] : 1962.725547491429
generation: 5 offspring: 4
travel distance:[1, 10, 6, 8, 9, 4, 2, 7, 3, 5, 1] : 2626.455096698985
generation: 5 offspring: 5
travel distance:[1, 2, 6, 5, 10, 3, 9, 4, 7, 8, 1] : 1631.463753062698
--------------------------------------------------------
Optimal route:[1, 2, 6, 5, 10, 3, 9, 4, 7, 8, 1]
travel_distance:1631.463753062698

저는 Typescript로 TSP-GA 놀이공원을 만들었습니다. 놀고 싶으면 https://dillir07.github.io/Genetic-Algorithm-TSP/에 서명하세요.


Julia- 소스 코드는 Github에서 사용 가능
감사합니다.평론을 환영합니다.