[Nonogram-solver] 2022년 5월 15일 일요일

오늘 한 것

• GA crossover, converge 메소드 등 기존 코드 분석

# 랜덤 생성한 solution 집합 P에서 적합도(확률) 높은 것들 뽑아서 새로운 solution 집합 PP 생성
def crossover(P, constraints):
    rules, nLines, nColumns, nPoints, nPopulation = constraints

    PP    = []
    # P는 여러 solution들이 담겨져 있는 list
    P = sorted(P, key = lambda s : (s.fitness, random.random()))   # 적합도 -> 랜덤 순으로 solution 오름차순 정렬
    n = (nPopulation*(nPopulation+1))/2   # solution 개수?
    prob=[i/n for i in range(1, nPopulation+1)]   # 각 solution별 확률 생성
    # solution 적합도에 따라 오름차순 정렬했으니까 적합도가 더 큰 게 뒤로 옴
    # -> solution별 확률 부여할 때 뒤로 갈 수록 i가 커져서 뒤 solution 더 큰 확률 부여받게 됨

    # 무작위로 부모 유전자 두 개 뽑아서 
    for _ in range(nPopulation):
        # 자손 유전자 생성
        child1Points = []
        child2Points = []
        parent1, parent2 = random.choice(P, p=prob, replace=False, size=2)   
        # 무작위 표본 추출
        # P: 모집단, p: 모집단 내 각 원소별로 표본으로 뽑힐 확률, replace=False: 비복원 추출(추출한 것을 제자리에 되돌리지 않고 다음 것을 추출. 즉 중복 추출 X), size=2: 두 개 추출
        # 확률이 높은 게 표본으로 뽑힐 것

        for i in range(nPoints):
            if random.random() <= 0.5:   # 랜덤값이 50% 이하면 그대로 넣고, 더 크면 교차해서 넣음
                child1Points += [parent1.points[i]]
                child2Points += [parent2.points[i]]
            else:
                child1Points += [parent2.points[i]]
                child2Points += [parent1.points[i]]

        PP    += [Solution(child1Points, constraints), Solution(child2Points, constraints)]   # 새로운 solution 집합 생성 (크기 두 배일 거 같은 ??)

    return PP

def converge(P, constraints):
    rules, nLines, nColumns, nPoints, nPopulation = constraints

    # 적합도가 0인 solution이 존재하면 GA 함수에 while문 빠져나옴
    for s in P:
        if s.fitness == 0:
            return True

    # 한 solution이 다음 solution과 다른 게 하나라도 있으면 False return
    for i in range(len(P)-1):
        if P[i].points != P[i+1].points:
            return False
    
    return True   # 한 solution과 다음 soultion이 다른 것이 하나도 없으면 True return

 

 

Python Numpy 강좌 : 제 10강 - 난수

[Python numpy] np.random.choice() 메소드로 임의표본 추출하기 (무작위, 확률 샘플링)

numpy.random.choice() 함수 사용하기

[ML] GA(Genetic Algorithm)