http://cafe.naver.com/gogoomas/323149


제가 만든 유전 알고리즘 모듈입니다. 사용법이 간단하니 쉽게 익힐 수 있습니다.

마방진이란?

ㅁ ㅁ ㅁ
ㅁ ㅁ ㅁ
ㅁ ㅁ ㅁ

3x3개의 칸에 1~9의 자연수를 집어넣어 한줄씩(대각선 포함) 더했을 때 각각 같은 수가 나왔다면 '마방진을 풀었다'라고 합니다.

[1,2,3,4,5,6,7,8,9] 이렇게 9개의 유전자를 갖는 개체를 1600마리 생성해서 그걸 세대라고 묶겠습니다.

gene = [[2,3,1,
          4,6,5,
          7,8,9], . . . . ]

자 이제 Generation 객체를 생성합시다.

generation = Generation.Generation(gene,mutchance=0.0,maxnum=9,minnum=1)

중복되는 숫자가 등장하면 안되니 돌연변이는 만들지 않습니다. 또한 1~9 사이의 수니 저렇게 설정해 줍니다.

이제 적합도 평가 함수를 만들어야 하는데요, 조금만 머리를 써본다면

ㅁㅁㅁ
ㅁㅁㅁ
ㅁㅁㅁ

가로선, 세로선, 대각선까지 총 8개의 선이 전부 같아야 완벽한 개체입니다. 이들이 서로 얼마나 다른지에 따라 적합도를 판별하면 되겠죠. 서로 차이가 덜 날수록 완벽한 개체에 가까워지니까요. 우리는 8개의 선을 모두 더한다음 8로 나눈 값을 average 변수에 담습니다.

def goodness(object):
    average = 2*sum(object) + object[0]+object[4]+object[8]+object[2]+object[4]+object[6]
    average = average/8

이제 이 average와 각각 8개의 선들을 모두 하나씩 대응해서, 그 차를 누적시키면 됩니다. 누적 값을 result에 담아보죠.

그런데, 이러면 차이가 클수록 적합도가 커지게 됩니다. 이러면 Generation 모듈이 제대로 작동하지 않습니다. 따라서 -1을 곱해줍니다. 그리고 result를 리턴하면, 차이가 적을수록 적합도가 커지는 평가 함수가 완성되었습니다.

def goodness(object):
    average = 2*sum(object) + object[0]+object[4]+object[8]+object[2]+object[4]+object[6]
    average = average/8
    result = 0
    k =0
    for i in range(3):
        k+=object[i]
    result+=abs(average-k)
    k=0
    for i in range(3,6):
        k+=object[i]
    result+=abs(average-k)
    k=0
    for i in range(6,9):
        k+=object[i]
    result+=abs(average-k)
    k=0

    result += abs(average-(object[0]+object[3]+object[6]))
    result += abs(average-(object[1]+object[4]+object[7]))
    result += abs(average-(object[2]+object[5]+object[8]))
    result += abs(average-(object[0]+object[4]+object[8]))
    result += abs(average-(object[2]+object[4]+object[6]))
    result *=-1
    return result


이제 진화만 시키면 됩니다. 개체수가 1600마리나 되니 부모도 한 128명 뽑아봅시다. 2천세대까지 진화시켜보죠.

for i in range(2000):
    generation.makeSon(goodness,128)
    if not iP0:print goodness(generation.Generation[0])

500세대마다 적합도를 출력하게 했습니다.

자 이제 연산을 시작해 봅시다.

>>-18
   0
   0
   0

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


500세대에 마방진이 완성되어 적합도가 0이 나왔군요. 그 후로 변동이 없는 모습입니다. 

완벽한 개체를 뽑아냈습니다. 가로 세로 대각선 모두 더해봐도 값이 전부 같음을 알 수 있습니다.



-------------------------
#CODE
import Generation, random, time

a = range(1,10)
gene = []
k = []
for i in range(1600):
    random.shuffle(a)
    for i in a:
        k.append(i)

    gene.append(k)
    k = []


def goodness(object):
    average = 2*sum(object) + object[0]+object[4]+object[8]+object[2]+object[4]+object[6]
    average = average/8
    result = 0
    k =0
    for i in range(3):
        k+=object[i]
    result+=abs(average-k)
    k=0
    for i in range(3,6):
        k+=object[i]
    result+=abs(average-k)
    k=0
    for i in range(6,9):
        k+=object[i]
    result+=abs(average-k)
    k=0

    result += abs(average-(object[0]+object[3]+object[6]))
    result += abs(average-(object[1]+object[4]+object[7]))
    result += abs(average-(object[2]+object[5]+object[8]))
    result += abs(average-(object[0]+object[4]+object[8]))
    result += abs(average-(object[2]+object[4]+object[6]))
    result *=-1
    return result

generation = Generation.Generation(gene,mutchance=0.0,maxnum=9,minnum=1)

for i in range(2000):
    generation.makeSon(goodness,128)
    if not iP0:print goodness(generation.Generation[0])

s = generation.Generation[0]

print s[:3]
print s[3:6]
print s[6:9]
s = raw_input()