조합(Combination)은 서로 다른 n개의 원소를 가지는 어떤 집합 (사실, 집합은 서로 다른 원소의 모임으로 정의된다.)에서 순서에 상관없이 r개의 원소를 선택하는 것이며, (즉, 선택의 순서와 상관없이 같은 원소들이 선택되었다면 같은 조합이며 다른 원소들이 선택되었다면 다른 조합이다.) 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것 혹은 찾는 것과 같다.
이때 n개의 조합에서 r개의 부분집합을 고르는 조합의 경우의 수는 다음과 같다.
< nCr 공식 >
하지만 그 경우의 수들을 전부 보고 싶다면 어떻게 해야 할까?
단순히 중첩 반복문으로 구현하는 생각을 할 수 있겠지만, r의 값이 달라짐에 따라 r 중 반복문을 구현해야 하므로 어려워진다.
< 우리가 원하는 조합을 보는 방법 >
여기서 필자는 2진수에서 비트를 올림 하는 것처럼 숫자를 하나하나 다음 자리로 올려 주는 방법을 생각했다.
< 조합 알고리즘 설명 >
다음은 5C3을 구현하는 알고리즘의 일부이다.
1을 끝자리로 갈 때까지 다음 자리로 옮겨 주며(시프트), 만약 끝자리로 이동하면 그다음 1을 옮기며, 이때 그 뒤에 있는 1은 옮긴 1 뒤로 옮겨 준다(초기화).
# Combination 수동 구현
import math
n, r = map(int, input().split())
select = [1] * r + [0] * (n - r)
cnt = 0
for i in range(math.factorial(n) // (math.factorial(n - r) * math.factorial(r))):
cnt += 1
print(select, cnt)
for j in range(n - 2, -1, -1): # n-2는 끝에서 두 번째 자리부터 시작한다는 뜻.
if select[j]: # 현재 칸에 1이 있을 경우 다음 칸에 1이 없으면 시프트. 마지막 칸은 가지 않으니 괜찮음(이래서 n-2에서 시작)
if select[j + 1] == 0: # 시프트
select[j] = 0
select[j + 1] = 1
if j + 2 <= n - 1 and 1 in select[j+2:]: # 리스트 길이 검사, 길이 넘는다 해도 두 번째 조건은 건너뜀.
l = select[j+2:].count(1) # 초기화 전 저장
select[j+2:] = [0] * len(select[j+2:]) # 뒷 자리 초기화(시프트 한 자리 바로 앞으로 이동시킴)
for k in range(l): # 뒤에 있는 1의 개수만큼 1 넣어줌
select[j+2+k] = 1
break
완성된 프로그램을 이용한 예시는 다음과 같다.
< 7C3을 계산한 결과 >
추가사항 및 제작시 어려웠던 점)
- 팩토리얼을 구현하기 위해 math 라이브러리를 사용했다.
- 시프트를 할 때 마지막 자리가 넘어가지 않도록 n-2번째에서부터 앞 칸으로 반복한다.
- 처음에는 시프트를 하고 나서 그 뒤의 1들을 시프트 한 1 앞으로 옮겨야 한다는 걸 잊어버려 구현이 안 되던 버그가 있었다.
- j+1 자리로 시프트를 한 다음, 초기화를 위해 j+2번째 자리부터 1이 있는지 검사해야 하는데 이때 리스트의 길이를 넘지 않기 위해 미리 j+2 <= n-1을 검사한다. 파이썬은 앞 조건이 틀리면 and연산자에서는 뒷 조건을 보지 않아 길이를 넘었다 해도 오류가 뜨진 않는다.
- 뒷 자리 초기화 시 뒷자리에 있는 1의 위치를 받아 그 자리만 0으로 바꿔주기보다 그냥 뒷자리를 통째로 0으로 초기화하고 1을 시프트 자리 뒤에 붙이는 게 더 간단할 것 같아 그렇게 했다.
사진과 같이 최고 적합도는 크게 올라가지 않는 모습을 보여준다. 여기서 필자는 교차 및 돌연변이 방법에 문제가 있다고 생각해 해당 방법을 고민하던 중, 해당 프로그램을 보던 한 친구가 구간의 길이를 줄여보자는 아이디어를 건의했다. 현재 유전 알고리즘은 가로 5π, 세로 10인 공간 속에서 돌아간다.
< 사이클로이드 곡선 >
필자는 가로 구간을 10개로 나눠 사이클로이드를 유도하려 하였다. 그런데 실제 사이클로이드는 곡선이다. 직선을 이어 아무리 최단 강하 곡선을 만들어도 그 한계가 있는 것이다. 그래서 구간의 크기를 줄여 구간의 수를 늘리면 훨씬 적합도가 올라갈 여지가 있는 것이다.
또한, 이 책에서는 '룰렛 휠 방식'을 사용해 다음 세대로 이동될 유전자를 선택하는데, 이 과정에서 특이한 적합도 함수를 사용한다.
초보자들이 유전 알고리즘을 처음 구현하면서 흔히 범하는 실수는 위와 같이 k 를 사용해서 적합도를 조정하지 않고 주어진 문제에서의 해의 품질을 그대로 적합도로 사용하는 것이다. 이렇게 하면 대부분의 경우 해 집단에서 가장 좋은 해와 가장 나쁜 해의 품질이 너무 차이가 나서, 적합도에 비례해서 선택 기회를 갖게 되면 나쁜 해 들은 거의 선택될 기회를 잃게 된다. 결과적으로 엄청나게 큰 선택압을 주어 해의 다양성을 급속히 떨어뜨리는 결과를 부르게 된다.
필자는 현재 (T/t)^2을 적합도 함수로 사용하는데(T : 최소 시간, t : 실제 걸린 시간), 해당 방법은 적합도 차이를 '매우 크게' 부각하는 방법이라 개선이 필요할 것 같았다.
그런데 해당 함수가 이해가 되지 않아 다른 식을 생각해 보기로 하였다.
고민을 해 보다, 지수 함수 형태의 식이 적당하다 판단하였고, 마침 필자의 친구가 시그모이드 함수를 얘기해 주어 해당 함수를 적용해보려 하였다.
처음엔 꽤 잘 나오는 것 같았다. 그래서 범위를 늘려 보자
< Sigmoid in Python >
실수부를 처리하지 못해 수렴하는 모습을 보인다. 표기되는 소수 자리를 늘리는 방법을 찾을 수도 있겠지만, 시간이 없어 다음에 하도록 하자.
유전 알고리즘을 만들기 위한 조건은 간단하다. 우리가 구하고 싶은 해를 염색체의 모양으로 표현할 수 있어야 한다.
위의 그래프를 구간별로 자른 다음, 구간별로 기울기가 일정한 직선을 놓고, 그 기울기의 배열을 알고리즘의 해로 설정하면 유전 알고리즘을 적용할 수 있다.
&lt; 처음 실험을 설계할 때 그래프 / 화질이 안 좋은 것은 그냥 넘어가자... &gt;
또한, 등가속도 운동 공식을 이용, 구간의 길이와 처음 속도, 구간 가속도를 이용해 나중 속도와 걸린 시간을 구할 수 있다.
&lt; 실험 설계 과정 &gt;
(나중에 알게 된 사실인데, 에너지 보존을 이용하여 나중 속도를 구하면 구간의 길이를 따로 구하지 않아도 걸린 시간을 구할 수 있다.)
&lt; E보존을 이용하여 나중 속도를 구하는 방법 &gt;
따라서 걸린 시간은 다음과 같다.
우리는 기울기를 알고 있으므로, 직각삼각형 또는 삼각함수를 사용해 빗면의 가속도를 구할 수 있다.
&lt; 기울기 구하는 과정,&nbsp; &gt;
## 주의
이때 기울기가 양수여야 나중 속도를 증가시킬 수 있으므로 해당 기울기에 절댓값을 해줘야 한다.
이때, 걸리는 시간을 정리해서 나타내면 다음과 같다.
&lt; 근호 안의 수는 양수여야 하므로, 절댓값을 씌워 주는게 맞다&gt;
코드상에서는 구간별로 걸리는 시간을 먼저 구한 다음, 시간을 비용이라 생각하여 적합도를 판단한다.
유전 알고리즘에서 가장 핵심적인 요소인 적합도를 어떻게 표현할지 고민하다, 사이클로이드 공식을 이용해 구한 최소 시간을 현재 도출된 시간으로 나누고, 이를 제곱하였다.(적합도 차이가 두드러지도록)
def fitness(t): #arr : sum_time입력받음 #별로 차이가 나지 않아 제곱을 해 주는 것이 좋을 것 같음 f = (T/t)**2 * 100 return f
실험을 구상할 때 가장 고민했던 것이 돌연변이를 일으키면 기울기의 합이 달라지는데, 기울기합 × 구간 길이 = 총 구간의 높이인데 이게 달라지면 바닥을 뚫고 내려가거나, 끝까지 내려오지 않을 수 있다.
구간을 정하고, 이 구간을 따라 내려가는 곡선을 구하는데, 이때 가다가 구간을 넘어버리면 아무 소용이 없지 않은가...
그래서 이 기울기 합을 일정하게 맞춰주기 위해 몇 가지 방법을 생각해봤다.
기울기의 합을 구하고, 이를 구간의 높이와 비교한 다음, 차이나는 만큼의 비율의 역수를 각각 기울기에 곱해주는 것.
마찬가지로 기울기 합을 구한 다음, 차이를 구하고, 이 차이를 구간의 개수만큼 나눠 각각 기울기에 빼주는 것.
곡선이 바닥을 뚫고 내려가면 그 뚫고 내려간 다음 지점부터 직선 운동하도록 만드는 것.
짝수/홀수 번째 기울기만 이를 변경시켜주는 값으로 삼는 것
양 끝 값만 이를 보완해 주는 값으로 삼는 것
여기서 3. 은 구현이 어려워 일단 미뤄 놨고, 4. 5. 는 각각의 기울기가 변화하는 값이 너무 클 것 같아 제외했다. 1. 과 2. 를 고민하던 중, 결국은 결과가 같다는 것을 깨닫고, 구현이 간단한 1.로 채택했다.
앞으로 이를 정규화(Generalization)로 부르자.
곡선을 정규화를 시켜 주면, 총구간의 높이에 맞춰 곡선을 조정해준다. 따라서 곡선이 설정한 범위를 이탈할 걱정은 하지 않아도 된다.
하지만, 역시 문제는 남아 있는데, 하나의 기울기에서 돌연변이가 발생해도, 전체 값들에 영향을 준다는 것이다. 필자는 아직 해당 문제를 완벽히 해결하지 못했고, 아마 3. 또는 5. 가 더 좋은 최적해를 구하는데 도움을 줄 수 있을지도 모르겠다. (좋은 방법이 있다면 댓글로 알려주세요)
또한, 기울기가 양수 범위에서 설정될 수 있다면, 기울기가 너무 커져 못 올라가는 경우가 생길 수 있으므로, 음수 또는 0의 값만 가질 수 있도록 했다.
2. 실험 진행
실험을 진행하기에 앞서, 먼저 0세대를 만든다. 0세대는 완전 무작위로 생성되며, 매 세대마다 우수한 10% 유전자를 다음 세대로 유전시킨다.
&lt; 반영 비율 &gt;
이전 세대에서 유전된 10%의 유전자를 이용해 위 비율대로 교차, 돌연변이를 일으켜 다음 세대로 유전시킨다. 돌연변이가 일어날 확률과 돌연변이 시 바뀔 수 있는 최대 비율을 설정하고, 이를 통해 돌연변이를 일으킨다. 돌연변이를 일으키는 이유는, 지역 최적해에 갇히는 것을 방지하기 위함이다.
gen : 1368 max fitness : 93.00250925477336 여기서 gen은 해당 그래프가 도출된 세대를 의미한다. 1368이면 비교적 처음 부분에 속한다. 즉 상위 10% 유전자를 유전시키던 도중, 지역 최적해(local minimum)에 갇힌 상황이라고 볼 수 있다.
gen : 639 max fitness : 92.6552349926282 그리 효과가 없는 듯하다.
여기서 mut_chance와 mut_rate, 즉 돌연변이가 일어날 확률이나 돌연변이율을 올린다면 평균 적합도가 요동치는 것을 알 수 있다. 유전적 다양성이 높아지는 것이다. 평균 적합도가 이렇게 요동치는 대에는 무작위 10%의 힘이 큰 것 같다. 하지만 최종 적합도를 올리는 데에는 별로 기여를 하지는 못했다.(상위 10%만 선택) 룰렛 휠 방식을 사용해 무작위 유전자와 교차시키는 방법을 고려해 봐야겠다.
mut_rate를 0.2, mut_rate = 0.4로 해 보았다.
gen : 4173 max fitness : 92.75082693395207
mut_chance = 0.6 mut_rate = 0.2로 설정했을 때이다. 마찬가지로 처음보다는 평균 및 최저 적합도가 요동친다.
gen : 8838 max fitness : 92.7141370571032 그러나, 모두 최대 적합도 94%를 넘기지 못했다. 93. 대에서 머무르고 있다. 그리고, 두 번째 경우에 비해 최고 적합도가 후반부에서 나온 것으로 보아, 최적해에 다가가는 속도가 느린 것 같다.
아마 유전자를 교차시키는 방법을 수정하는 것에서 해결책이 나올 것 같다.
4. 느낀 점
영상으로 볼 때는 쉬워 보였는데, 막상 해보니까 아니었다. 시간은 총 4일 정도 소요되었고, 그리 만족할만한 결과도 도출되지 못했다.
이번 프로젝트를 진행하며 얻은 점은,
1. 최적화 프로그램에서는 지역 최적해에 갇히는 것을 해결하는 것이 중요하다. 이를 해결하는 다양한 방법이 현재 AI의 최적화 함수에 사용된다. 대표적인 최적화 함수로는 바로 그 Adam이 있다.
2. python을 이용하여 그래프를 그리는 matplot.lib을 사용하는 법을 알게 되었다. 실제로 공을 떨어뜨려 내려오는 것을 보여주는 프로그램을 이용할 수 있었다면 좋았겠지만, 아쉽게도 찾지 못해 그냥 그래프로 만족했다.
3. 자녀 수와 세대를 줄여도 첫 세대에서 적합도 90%를 넘기는 자손은 거의 무조건 한 마리 이상 나온다. 이를 통해 어느 집단이나 1등은 뛰어나다는 것을 알게 되었다.
4. 자손의 '분포'가 일정한지 아닌지도 영향을 미친다는 것을 알게 되었다.
#무작위 생성 for j in range(x_size): theta = rand(atan(min_m), 0) #-2 이상 0 미만 실수값 입력, 단위 라디안 #10개 숫자 평균적 합이 10이 되도록 맞춰줌 randM = tan(theta) #randM = rand(-2, 0) # 기울기 자체를 랜덤값으로 결정
코드에서는 무작위로 자손을 생성할 때, θ값을 무작위로 생성하고, 이를 기울기로 변환하는 방법을 사용한다. 기울기를 바로 생성하는 방법도 있지만, θ를 무작위로 분포시키는 것과 기울기를 분포시키는 방법을 사용하는 것이 적합도 분포에서 다른 결과를 가져올 수도 있다는 점에서 착안하였다. (실제로는 영향이 그렇게 크지 않다.... 0세대에서 10%만 걸러내서 그런 것 같다.)
여러 번 사건을 시행하면 그 확률은 대수적 확률에 수렴한다는 '대수의 법칙'에 기반하여 해당 프로젝트는 설계되었기 때문에, 이 분포에도 신경을 썼다. (더 나은 방법이 있다면 댓글로 알려주세요)
5. 직접 프로젝트를 설계하고 진행하며 멘탈관리도 중요하다는 점을 알게 되었다. 그리고 중간중간 느낀 점이 있다면 바로바로 문서화를 하는 것이 더 편하다는 것을 알게 되었다. 또한 다른 선행 연구를 참고하며 프로젝트를 진행하였는데, 역시나 선행 연구의 중요성을 알게 되었다.
