[Local Search Algorithms - Meta Heuristic Algorithm] Genetic Algorithm

1. Genetic Algorithm

생물체가 환경에 적응해 나가면서 진화하는 모습(적자생존)을 모방하여 최적의 value를 찾는 알고리즘이다. 

 

적자생존

- 환경에 적합한 개체는 살아남는다.

- 살아남은 개체는 자손을 낳는다. 

- 이때 자손은 부모의 유전자를 받고, 때때로는 돌연변이가 나타난다.

 

위 알고리즘을 모방한 것이 Genetic Algorithm이다.

 

1) 초기 염색체 집합을 생성

2) 초기 염색체들에 대한 적합도 계산

while :

    3) 자손 염색체 생성

    4) 자손 염색체들에 대한 적합도 계산

    5) 부모 염색체와 자손 염색체 적합도 비교

 

XR = 0.1
mR = 0.9
popSize = 100
limitEval = 100000
resolution = 10
DELTA = 0.01
numEval = 0


def geneticAlgorithm(p):
    # Population 생성
    pop = initializePop(popSize, p)
    # Population 중 최적해 찾기
    best = evalAndFindBest(pop, p)
    
    whenBestFound = numEval
    # limitEval 까지 [다음세대 생성–평가] 반복
    while numEval < limitEval:
        newPop = []
        I = 0
        # 다음 세대 생성; start
        while I < popSize:
            par1, par2 = selectParents(pop)
            ch1, ch2 = crossover(par1, par2, XR)
            newPop.extend([ch1, ch2])
            I += 2
        newPop = [mutation(ind, mR) for ind in newPop]
        pop = newPop
        # 다음 세대 생성; end
        # 다음 세대 값 평가 및 best 업데이트
        newBest = evalAndFindBest(pop, p)

        if newBest[0] < best[0]:
            best = newBest
            whenBestFound = numEval
    whenBestFound = whenBestFound
    bestSolution = indToSol(best, p)
    
    return bestSolution, best[0]

 

random하게 초기를 설정하여 계속하여 자손을 생성하면서 좋은 value를 찾는 방법이다.

2. Numeric

1) initializePop : 초기 염색체 집합을 생성

def initializePop(size, p):
    """ 
    size : 100
    p : [expr, [varNames, up, low]]
    """
    pop = []
    for i in range(size):
        chromosome = randBinStr(p)
        pop.append([0, chromosome])
    return pop # 100 * 50


def randBinStr(p):
    k = len(p[1][0] * resolution) # k : 50 = 5 * 10(resolution)
    chromosome = []
    for i in range(k):
        allele = random.randint(0, 1)
        chromosome.append(allele)
    return chromosome # [1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0]

 

initializePop을 통해 가장 초기 염색체를 생성한다.

 

초기 염색체는 1과 0으로 구성된 bin형태이며 100 * 50 matrix로 구성된다.

 

 

pop 출력


[[0, [1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0]], 
[0, [0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]], 
[0, [0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]], 
...]

 

 

2) evalAndFindBest :  초기 염색체들에 대한 적합도 계산

def evalAndFindBest(pop, p):
    best = pop[0]
    evalInd(best, p)
    bestValue = best[0]
    for i in range(1, len(pop)):
        evalInd(pop[i], p)
        newValue = pop[i][0]
        if newValue < bestValue:
            best = pop[i]
            bestValue = newValue
            
    return best

 

pop[0]을 best로 가정하고 evalInd를 통해 적합도를 계산한다.

 

def evalInd(ind, p):
    ind[0] = evaluate(decode(ind[1], p), p)

 

적합도는 ind[0] 위치에 저장한다.

def decode(chromosome, p):
    r = resolution
    low = p[1][1]
    up = p[1][2]
    genotype = chromosome[:]
    phenotype = []
    start = 0
    end = r
    for var in range(len(p[1][0])):
        value = binaryToDecimal(genotype[start:end], low[var], up[var])
        phenotype.append(value)
        start += r
        end += r
    return phenotype

 

염색체를 decode한다.

 

def binaryToDecimal(binCode, l, u):
    # 이진 코드를 10진수로 변환
    length = len(binCode)
    decimalValue = 0
    for i in range(length):
        decimalValue += binCode[i] * (2 ** (length - 1 - i))
    
    scaledValue = l + ((u - l) * decimalValue / (2 ** length))
    return scaledValue

 

이진 코드르 10진수로 변환한다.

 

3) 자손 염색체 생성

while I < popSize:
    par1, par2 = selectParents(pop)
    ch1, ch2 = crossover(par1, par2, XR)
    newPop.extend([ch1, ch2])
    I += 2
newPop = [mutation(ind, mR) for ind in newPop]

pop = newPop

 

3-1) selectParents

def selectParents(pop):
    ind1, ind2 = selectTwo(pop)
    par1 = binaryTournament(ind1, ind2)
    ind1, ind2 = selectTwo(pop)
    par2 = binaryTournament(ind1, ind2)
    return par1, par2

def selectTwo(pop):
    # pop에서 random하게 2개의 individuals 선택해서 반환
    popCopy = pop[:]
    random.shuffle(popCopy)
    return popCopy[0], popCopy[1]

def binaryTournament(ind1, ind2):
    # 2개의 individuals 중 더 좋은 ind 선택해서 반환
    if ind1[0] < ind2[0]:
        return ind1  # ind1이 더 나은 경우
    else:
        return ind2  # ind2가 더 나은 경우

 

부모를 결정하는 부분이다.

 

3-2) crossover

def crossover(ind1, ind2, uXp):
    chr1, chr2 = uXover(ind1[1], ind2[1], uXp)
    return [0, chr1], [0, chr2]

def uXover(chrInd1, chrInd2, uXp): # uniform crossover
    # chrInd1, chrInd2의 각 원소를 확률적(uXp)으로 crossover
    chr1 = chrInd1[:] # Make copies
    chr2 = chrInd2[:]
    # implement
    for i in range(len(chr1)):
        if random.uniform(0, 1) < uXp:
            chr1[i], chr2[i] = chr2[i], chr1[i]
    return chr1, chr2

 

crossover를 통해 확률적으로 자손을 만든다.

 

 

3-3) mutation

def mutation(ind, mrF): # bit-flip mutation
    # mrF * (1/ lnegth of individual) 확률로 ind의 개별 원소 bit-flip
    child = ind[:] # Make copy
    
    n = len(ind[1])
    for i in range(n):
        if random.uniform(0, 1) < mrF * (1 / n):
            child[1][i] = 1 - child[1][i]
    return child

 

이때 확률적으로 돌연변이가 나타난다.

 

ex) 1 0 0 1 0 - > 1 1 0 0 0

 

4) 자손 염색체들에 대한 적합도 계산

3)에서 구한 pop을 2)를 통해 계산한다.

 

5) 부모 염색체와 자손 염색체 적합도 비교

 

if newBest[0] < best[0]:
    best = newBest
    whenBestFound = numEval

 

newBest의 적합도가 더 좋으면 update한다.

 

 

6) ind를 solutino형태로 decode

def indToSol(ind, p):
    return decode(ind[1], p)

 

7) 실행결과

 

- Convex

 

 

- Griewank

 

- Ackley

---

한줄요약

Genetic Algorithm : 적자생존과 같은 유전적인 방법을 활용하여 램덤하게 초기화된 값에서 자손을 만들어나가면서 좋은 value를 찾는 알고리즘