글로벌 또는 로컬 최적점을 찾기 위해 사용하는 알고리즘
자연선택설에서 아이디어를 빌려온 알고리즘
생물이 환경에 적합하면 살아남아 서로의 유전 형질을 이어 받은 자식을 남긴다.
또한 가끔씩 돌연변이가 발생한다.
세대가 지나감에 따라 자연선택설에 의해 환경에서 가장 적합한 자식이 살아남든다.
이 자식이 가장 글로벌 최적값에 가깝다 라는 가정
예를 들어보자
한종의 여러 객체들이 존재한다. 그리고 특징을 각인덱스의 숫자라고 할때
s1, s2.... sn
[1,2,3,5,6,8],[4,5,6,7,8,9]....
생물이 환경에 적합성을 평가하는 공식 을 e()라고 하자(적합할수록 높은 점수)
각 객체들을 e(s1)에 집어 넣은 후 정렬하여 탑 10을뽑는다.
이후 살아남은 객체 들중 교배
[1,2,3,5,6,8],[4,5,6,7,8,9] -> [1,2,3,7,8,9]= 부모1 중 앞에꺼 3개 부모2중 뒤에꺼 3개
확률에 의해서 가끔 돌연변이
[1,2,3,5,6,8] -> [0,2,3,5,6,8] 맨앞의 특성이 조금 변화함
이가 발생하고 세대가 지나가면
위를 계속반복함
세대가 지나감에 따라 가장 환경에 적합한 객체만 생존한다.
def geneticoptimize(domain,costf,popsize=50,step=1, mutprod=0.2,elite=0.2,maxiter=100):
# Mutation Operation
def mutate(vec):
i=random.randint(0,len(domain)-1)
if random.random()<0.5 and vec[i]>domain[i][0]:
return vec[0:i]+[vec[i]-step]+vec[i+1:]
elif vec[i]<domain[i][1]:
return vec[0:i]+[vec[i]+step]+vec[i+1:]
# Crossover Operation
def crossover(r1,r2):
i=random.randint(1,len(domain)-2)
return r1[0:i]+r2[i:]
# Build the initial population
pop=[]
for i in range(popsize):
vec=[random.randint(domain[i][0],domain[i][1])
for i in range(len(domain))]
pop.append(vec)
# How many winners from each generation?
topelite=int(elite*popsize)
# Main loop
for i in range(maxiter):
scores=[(costf(v),v) for v in pop] scores.sort( )
ranked=[v for (s,v) in scores]
# Start with the pure winners
pop=ranked[0:topelite]
# Add mutated and bred forms of the winners
while len(pop)<popsize:
if random.random()<mutprob:
# Mutation
c=random.randint(0,topelite)
pop.append(mutate(ranked[c]))
else:
# Crossover
c1=random.randint(0,topelite)
c2=random.randint(0,topelite)
pop.append(crossover(ranked[c1],ranked[c2]))
# Print current best score
print scores[0][0]
return scores[0][1]
