What this program is trying to do (comments)
## GA Algorithm
# GA Cycle :
population (chromosome) -> reproduction (fitness) -> selection
-> genetic operation (crossover, mutation) -- new generation --> ......
# Algorithm :
begin
t <-- 0 (generation)
initialize P(t)
evaluate P(t)
while (not termination-condition) do
begin
t <-- t + 1
select P(t) from P(t-1)
alter P(t)
evaluation P(t)
end
end
# Example :
f(x) = x * sin(10 * pi * x) = 1.0
then, find x from the range [-1, 2] that maximizes the f(x)
-> adopt GA
Set 3,000,000 points from [-1, 2]
Map above decimal value into binary value ; 2**21 < 3,000,000 < 2**22 = 4,194,304
- Initial population -> population set as 100
: Create a population of chromosome with binary vector of 22 bits (randomly).
- Evaluation function
: eval(v) = f(x) = -1.0 + x * 3 / 4194304
- Genetic operator
: typical operators : mutation, crossover
1. mutation ; alters one or more genes
2. crossover ; crossover point can be randomly selected
-> judge whether the success of phenotype decreases or increases
Code
code written in python3
__author__ = "fatkitty"
import numpy as np
from random import randint
import random
def RandBi():
bi_X = "" # binary string
bi_X_arr = np.random.randint(2, size = 22)
for i in bi_X_arr:
bi_X += str(i)
return bi_X
def Decimal(k): #binary -> decimal
return int(k, 2)
def Eval(k):
return (-1.0 + k * 3 / 4194304)
bi_Dict = {} # [binary code, evaluation] for each chromosomes
sorted_Dict = {} # eval_Dict sorted by value [binary code, evaluation] in a descending order
selected_Dict = {} # the top chromosomes selected
randomV = []
# Population - 100 sets of chromosomes
for i in range(100):
globals()['v{}'.format(i)] = RandBi()
globals()['eval_v{}'.format(i)] = Eval(Decimal(globals()['v{}'.format(i)]))
bi_Dict['v%d'%(i + 1)] = [globals()['v{}'.format(i)], globals()['eval_v{}'.format(i)]]
print("v%d = "%(i + 1), bi_Dict['v%d'%(i + 1)][0], " -> eval(v%d) ="%(i + 1), bi_Dict['v%d'%(i + 1)][1])
# initial sequence
sorted_Dict = sorted(bi_Dict.items(), key=lambda t : t[1], reverse = True) # for selection of top 50
# Selection - 50 of the fittest
# - select the subset with the best fitness values in order to act as parents for the next generation
def Selection():
for i in range(100):
selected_Dict[sorted_Dict[i][0]] = [sorted_Dict[i][1][0], sorted_Dict[i][1][1]]
print ("\n----- 50 suitable chromosomes selected -----")
def RandomV(): # select 2 random chromosomes for crossover
# to avoid overlapping
ranlist = list(selected_Dict)
ran_num = random.sample(ranlist, 2)
return ran_num
# Crossover - 50 sets and 1 child / 25 sets and 2 children
# - merge pairs from the selected parents to generate new offspring child solution
def Crossover(sel_r1, sel_r2, c): # start the crossover starting from index of (crossover point + 1)
i = randint(0, 21) # crossover point
sel_r1_cross = sel_r1[:i] + sel_r2[i:]
sel_r2_cross = sel_r2[:i] + sel_r1[i:]
# Mutation - very small probability
# - child can have a feature that was not inherited from the parents
# Here, we have set the mutation probability as 1%
probR1 = randint(0, 100)
probR2 = randint(0, 100)
print("\n**-- crossover point :", i, "--**\n")
if (probR1 == 0):
print(randomV[0] + "* generate 1% mutation")
m = randint(0, 21) # mutation point
result = (int(sel_r1_cross[m]) + 1) % 2
# if sel_r1_cross[m] was originally 0, result = (0+1)%2, if it was 1 then result = (1+1)%2
sel_r1_cross = sel_r1_cross[:m] + str(result) + sel_r1_cross[(m + 1):]
print("**-- mutation point :", m, "--** " + sel_r1_cross)
if (probR2 == 0):
print(randomV[1] + "* generate 1% mutation")
m = randint(0, 21) # mutation point
result = (int(sel_r2_cross[m]) + 1) % 2
sel_r2_cross = sel_r2_cross[:m] + str(result) + sel_r2_cross[(m + 1):]
print("**-- mutation point :", m, "--** " + sel_r2_cross)
# evaluation of sel_r1_cross and sel_r2_cross
eval_r1 = Eval(Decimal(sel_r1_cross))
eval_r2 = Eval(Decimal(sel_r2_cross))
globals()['v{}'.format(c)] = sel_r1_cross
globals()['eval_v{}'.format(c)] = eval_r1
bi_Dict['v%d'%(c+ 1)] = [globals()['v{}'.format(c)], globals()['eval_v{}'.format(c)]]
c += 1
globals()['v{}'.format(c)] = sel_r2_cross
globals()['eval_v{}'.format(c)] = eval_r2
bi_Dict['v%d'%(c + 1)] = [globals()['v{}'.format(c)], globals()['eval_v{}'.format(c)]]
print (randomV[0]+"*", " : ", sel_r1_cross, " -> eval("+randomV[0]+'*) =', eval_r1)
print (randomV[1]+"*", " : ", sel_r2_cross, " -> eval("+randomV[1]+'*) =', eval_r2)
# decrease or increase
if (Eval(Decimal(sel_r1)) > eval_r1):
print ("=> ", randomV[0], "fitness decreased")
elif (eval_r1 > Eval(Decimal(sel_r1))):
print ("=> ", randomV[0], "fitness increased")
elif (eval_r1 == Eval(Decimal(sel_r1))):
print ("=> ", randomV[0], "fitness stays the same")
if (Eval(Decimal(sel_r2)) > eval_r2):
print (" ", randomV[1], "fitness decreased")
elif (eval_r2 > Eval(Decimal(sel_r2))):
print (" ", randomV[1], "fitness increased")
elif (eval_r2 == Eval(Decimal(sel_r2))):
print (" ", randomV[1], "fitness stays the same")
def sort_child(): # sort the selected_Dict again in every generation
sorted_Dict = sorted(bi_Dict.items(), key=lambda t : t[1], reverse = True)
if __name__ == "__main__":
generation = 1 # initial population is the first generation
while (generation < 6): # terminate when generation hits 5
print ("\n============== %d th generation =============="%generation)
if (generation > 1):
for i in range(100):
# Override the top 50 in bi_Dict[0]~[49].
#If not, then only the last 50 would keep being overridden by new children,
# and the top 50 would stay the same throughout every generation.
globals()['v{}'.format(i)] = sorted_Dict[i][1][0]
globals()['eval_v{}'.format(i)] = sorted_Dict[i][1][1]
bi_Dict['v%d'%(i + 1)] = [globals()['v{}'.format(i)], globals()['eval_v{}'.format(i)]]
Selection()
check = 50
while (check < 99):
randomV = RandomV() # 2 sets of chromosomes for Crossover
# repeat crossover 25 times (25 * 2)
Crossover(bi_Dict[randomV[0]][0], bi_Dict[randomV[1]][0], check)
check += 2
sort_child()
print("\n")
for i in range(100):
print("v%d = "%(i + 1), bi_Dict['v%d'%(i + 1)][0], " -> eval(v%d) ="%(i + 1), bi_Dict['v%d'%(i + 1)][1])
generation += 1
Result
초기 1세대부터 마지막 5세대에 이르기까지의 과정이 모두 출력됨.
아래는 random 결과의 마지막 세대에 관해 출력된 정보.
============== 5 th generation ==============
----- 50 suitable chromosomes selected -----
**-- crossover point : 1 --**
v69* : 0101111110110101111111 -> eval(v69*) = 0.1216118335723877
v18* : 1100011101110100101111 -> eval(v18*) = 1.3373749256134033
=> v69 fitness increased
v18 fitness decreased
**-- crossover point : 6 --**
v97* : 0000110000101111010101 -> eval(v97*) = -0.8572084903717041
v45* : 1001000101101100100011 -> eval(v45*) = 0.7041876316070557
=> v97 fitness decreased
v45 fitness increased
**-- crossover point : 9 --**
v14* : 1110011010111001111000 -> eval(v14*) = 1.7038211822509766
v48* : 1000011101111000010100 -> eval(v48*) = 0.5875387191772461
=> v14 fitness decreased
v48 fitness increased
**-- crossover point : 14 --**
v98* : 0000010011100010110100 -> eval(v98*) = -0.9427423477172852
v46* : 1000110010100000100001 -> eval(v46*) = 0.647972822189331
=> v98 fitness increased
v46 fitness decreased
**-- crossover point : 21 --**
v82* : 0010101110011010001001 -> eval(v82*) = -0.48903775215148926
v31* : 1100000111000101001001 -> eval(v31*) = 1.2707431316375732
=> v82 fitness stays the same
v31 fitness stays the same
**-- crossover point : 10 --**
v47* : 1000101100101000001011 -> eval(v47*) = 0.6307451725006104
v77* : 0011110110110100110111 -> eval(v77*) = -0.27687716484069824
=> v47 fitness decreased
v77 fitness increased
**-- crossover point : 10 --**
v32* : 1011111111000011110101 -> eval(v32*) = 1.2472455501556396
v49* : 1000000110010001110001 -> eval(v49*) = 0.5183913707733154
=> v32 fitness decreased
v49 fitness increased
**-- crossover point : 3 --**
v47* : 1000011011011010011101 -> eval(v47*) = 0.5803124904632568
v70* : 0100101100110100110111 -> eval(v70*) = -0.11867403984069824
=> v47 fitness decreased
v70 fitness increased
**-- crossover point : 1 --**
v49* : 1111010000110100001011 -> eval(v49*) = 1.8617632389068604
v5* : 1000000110000011110101 -> eval(v5*) = 0.5177533626556396
=> v49 fitness increased
v5 fitness decreased
**-- crossover point : 4 --**
v53* : 0000100011111010010000 -> eval(v53*) = -0.8947944641113281
v83* : 0010110000101111010101 -> eval(v83*) = -0.4822084903717041
=> v53 fitness decreased
v83 fitness increased
**-- crossover point : 0 --**
v58* : 1110101001101100101000 -> eval(v58*) = 1.7471599578857422
v8* : 1000110010100000100001 -> eval(v8*) = 0.647972822189331
=> v58 fitness increased
v8 fitness decreased
**-- crossover point : 12 --**
v39* : 1010000111000100110111 -> eval(v39*) = 0.8957302570343018
v47* : 1000101100110110000100 -> eval(v47*) = 0.6313810348510742
=> v39 fitness decreased
v47 fitness increased
**-- crossover point : 5 --**
v61* : 1000110100011001101000 -> eval(v61*) = 0.6535167694091797
v16* : 1110001100101000001011 -> eval(v16*) = 1.6619951725006104
=> v61 fitness increased
v16 fitness decreased
**-- crossover point : 16 --**
v84* generate 1% mutation
**-- mutation point : 8 --** 0010011110101100011001
v1* : 1111110110111101111110 -> eval(v1*) = 1.9735398292541504
v84* : 0010011110101100011001 -> eval(v84*) = -0.5350773334503174
=> v1 fitness increased
v84 fitness increased
**-- crossover point : 18 --**
v18* : 1101111110110101110001 -> eval(v18*) = 1.6216018199920654
v72* : 1000110010100000101111 -> eval(v72*) = 0.6479828357696533
=> v18 fitness decreased
v72 fitness increased
**-- crossover point : 3 --**
v93* : 0001010000110100001011 -> eval(v93*) = -0.7632367610931396
v5* : 1111100111101111100111 -> eval(v5*) = 1.9289371967315674
=> v93 fitness decreased
v5 fitness increased
**-- crossover point : 5 --**
v27* : 1100110011100010110100 -> eval(v27*) = 1.4010076522827148
v57* : 0000000011100011110111 -> eval(v57*) = -0.9895694255828857
=> v27 fitness increased
v57 fitness decreased
**-- crossover point : 11 --**
v60* : 1100000111001111100111 -> eval(v60*) = 1.2712223529815674
v82* : 1111100111100101001001 -> eval(v82*) = 1.9284579753875732
=> v60 fitness increased
v82 fitness decreased
**-- crossover point : 0 --**
v45* : 1001100001011101101111 -> eval(v45*) = 0.7855408191680908
v42* : 1001000000101111010101 -> eval(v42*) = 0.6896665096282959
=> v45 fitness increased
v42 fitness decreased
**-- crossover point : 4 --**
v14* : 1110111111000001101001 -> eval(v14*) = 1.809645414352417
v90* : 0001011011111000010100 -> eval(v90*) = -0.7308206558227539
=> v14 fitness increased
v90 fitness decreased
**-- crossover point : 6 --**
v37* : 1010111100110100110111 -> eval(v37*) = 1.0532009601593018
v47* : 1000100001101001101010 -> eval(v47*) = 0.5985865592956543
=> v37 fitness increased
v47 fitness decreased
**-- crossover point : 2 --**
v90* : 0010001000000011111000 -> eval(v90*) = -0.6013851165771484
v17* : 1101011011111000010100 -> eval(v17*) = 1.519179344177246
=> v90 fitness increased
v17 fitness decreased
**-- crossover point : 5 --**
v67* : 1111001100111101010000 -> eval(v67*) = 1.8504600524902344
v35* : 1011010000110100001011 -> eval(v35*) = 1.1117632389068604
=> v67 fitness decreased
v35 fitness increased
**-- crossover point : 11 --**
v22* : 1101001100111011000010 -> eval(v22*) = 1.475358486175537
v2* : 1111110101110110111010 -> eval(v2*) = 1.9702868461608887
=> v22 fitness increased
v2 fitness decreased
**-- crossover point : 6 --**
v44* : 1001001100110100110111 -> eval(v44*) = 0.7250759601593018
v47* : 1000100110010000110101 -> eval(v47*) = 0.6120984554290771
=> v44 fitness increased
v47 fitness decreased
v1 = 1111110110111101011001 -> eval(v1) = 1.9735133647918701
v2 = 1111110101111011000010 -> eval(v2) = 1.970475673675537
v3 = 1111100100101101110111 -> eval(v3) = 1.9200680255889893
v4 = 1111011011111111011011 -> eval(v4) = 1.8945047855377197
v5 = 1111010000110100001011 -> eval(v5) = 1.8617632389068604
v6 = 1110110010101010001011 -> eval(v6) = 1.7734148502349854
v7 = 1110101010010010001111 -> eval(v7) = 1.7488815784454346
v8 = 1110101001101100101000 -> eval(v8) = 1.7471599578857422
v9 = 1110101001101010000010 -> eval(v9) = 1.7470412254333496
v10 = 1110100111011001000110 -> eval(v10) = 1.7404065132141113
v11 = 1110100000010101100110 -> eval(v11) = 1.719738483428955
v12 = 1110011101111010001010 -> eval(v12) = 1.712623119354248
v13 = 1110011101011000011000 -> eval(v13) = 1.7110767364501953
v14 = 1110011011111000010100 -> eval(v14) = 1.706679344177246
v15 = 1110010100100111111101 -> eval(v15) = 1.685422658920288
v16 = 1110010100011001101000 -> eval(v16) = 1.6847667694091797
v17 = 1110001000000011111000 -> eval(v17) = 1.6486148834228516
v18 = 1101111110110101111111 -> eval(v18) = 1.6216118335723877
v19 = 1101110000101001001100 -> eval(v19) = 1.5800104141235352
v20 = 1101100111011101010110 -> eval(v20) = 1.5531010627746582
v21 = 1101010001000101111100 -> eval(v21) = 1.4875764846801758
v22 = 1101001100110110111010 -> eval(v22) = 1.4751696586608887
v23 = 1101000100010100000110 -> eval(v23) = 1.4501385688781738
v24 = 1100111101001000000111 -> eval(v24) = 1.4290821552276611
v25 = 1100101110100100101100 -> eval(v25) = 1.3864450454711914
v26 = 1100101101101011101100 -> eval(v26) = 1.383835792541504
v27 = 1100100011100011110111 -> eval(v27) = 1.3541805744171143
v28 = 1100100010011010010111 -> eval(v28) = 1.350816011428833
v29 = 1100010011111011111100 -> eval(v29) = 1.3084077835083008
v30 = 1100001101111010010110 -> eval(v30) = 1.2907567024230957
v31 = 1100000111000101001001 -> eval(v31) = 1.2707431316375732
v32 = 1011111111010001110001 -> eval(v32) = 1.2478835582733154
v33 = 1011111110000101111111 -> eval(v33) = 1.2444145679473877
v34 = 1011111101101111111000 -> eval(v34) = 1.2434024810791016
v35 = 1011001100111101010000 -> eval(v35) = 1.1004600524902344
v36 = 1011001100010000111111 -> eval(v36) = 1.0984337329864502
v37 = 1010110001101001101010 -> eval(v37) = 1.0204615592956543
v38 = 1010011101101101110010 -> eval(v38) = 0.9620566368103027
v39 = 1010000111000110000100 -> eval(v39) = 0.8957853317260742
v40 = 1010000011110010001101 -> eval(v40) = 0.88608717918396
v41 = 1001110010001101001011 -> eval(v41) = 0.8345873355865479
v42 = 1001100001011101101111 -> eval(v42) = 0.7855408191680908
v43 = 1001000111111101000101 -> eval(v43) = 0.710803747177124
v44 = 1001000110010000110101 -> eval(v44) = 0.7058484554290771
v45 = 1001000000101111010101 -> eval(v45) = 0.6896665096282959
v46 = 1000110010100010110100 -> eval(v46) = 0.6480779647827148
v47 = 1000101100110100110111 -> eval(v47) = 0.6313259601593018
v48 = 1000011100111001111000 -> eval(v48) = 0.5846805572509766
v49 = 1000000110000011110101 -> eval(v49) = 0.5177533626556396
v50 = 0111110000101001010100 -> eval(v50) = 0.4550161361694336
v51 = 0101111110110101111111 -> eval(v51) = 0.1216118335723877
v52 = 1100011101110100101111 -> eval(v52) = 1.3373749256134033
v53 = 0000110000101111010101 -> eval(v53) = -0.8572084903717041
v54 = 1001000101101100100011 -> eval(v54) = 0.7041876316070557
v55 = 1110011010111001111000 -> eval(v55) = 1.7038211822509766
v56 = 1000011101111000010100 -> eval(v56) = 0.5875387191772461
v57 = 0000010011100010110100 -> eval(v57) = -0.9427423477172852
v58 = 1000110010100000100001 -> eval(v58) = 0.647972822189331
v59 = 0010101110011010001001 -> eval(v59) = -0.48903775215148926
v60 = 1100000111000101001001 -> eval(v60) = 1.2707431316375732
v61 = 1000101100101000001011 -> eval(v61) = 0.6307451725006104
v62 = 0011110110110100110111 -> eval(v62) = -0.27687716484069824
v63 = 1011111111000011110101 -> eval(v63) = 1.2472455501556396
v64 = 1000000110010001110001 -> eval(v64) = 0.5183913707733154
v65 = 1000011011011010011101 -> eval(v65) = 0.5803124904632568
v66 = 0100101100110100110111 -> eval(v66) = -0.11867403984069824
v67 = 1111010000110100001011 -> eval(v67) = 1.8617632389068604
v68 = 1000000110000011110101 -> eval(v68) = 0.5177533626556396
v69 = 0000100011111010010000 -> eval(v69) = -0.8947944641113281
v70 = 0010110000101111010101 -> eval(v70) = -0.4822084903717041
v71 = 1110101001101100101000 -> eval(v71) = 1.7471599578857422
v72 = 1000110010100000100001 -> eval(v72) = 0.647972822189331
v73 = 1010000111000100110111 -> eval(v73) = 0.8957302570343018
v74 = 1000101100110110000100 -> eval(v74) = 0.6313810348510742
v75 = 1000110100011001101000 -> eval(v75) = 0.6535167694091797
v76 = 1110001100101000001011 -> eval(v76) = 1.6619951725006104
v77 = 1111110110111101111110 -> eval(v77) = 1.9735398292541504
v78 = 0010011110101100011001 -> eval(v78) = -0.5350773334503174
v79 = 1101111110110101110001 -> eval(v79) = 1.6216018199920654
v80 = 1000110010100000101111 -> eval(v80) = 0.6479828357696533
v81 = 0001010000110100001011 -> eval(v81) = -0.7632367610931396
v82 = 1111100111101111100111 -> eval(v82) = 1.9289371967315674
v83 = 1100110011100010110100 -> eval(v83) = 1.4010076522827148
v84 = 0000000011100011110111 -> eval(v84) = -0.9895694255828857
v85 = 1100000111001111100111 -> eval(v85) = 1.2712223529815674
v86 = 1111100111100101001001 -> eval(v86) = 1.9284579753875732
v87 = 1001100001011101101111 -> eval(v87) = 0.7855408191680908
v88 = 1001000000101111010101 -> eval(v88) = 0.6896665096282959
v89 = 1110111111000001101001 -> eval(v89) = 1.809645414352417
v90 = 0001011011111000010100 -> eval(v90) = -0.7308206558227539
v91 = 1010111100110100110111 -> eval(v91) = 1.0532009601593018
v92 = 1000100001101001101010 -> eval(v92) = 0.5985865592956543
v93 = 0010001000000011111000 -> eval(v93) = -0.6013851165771484
v94 = 1101011011111000010100 -> eval(v94) = 1.519179344177246
v95 = 1111001100111101010000 -> eval(v95) = 1.8504600524902344
v96 = 1011010000110100001011 -> eval(v96) = 1.1117632389068604
v97 = 1101001100111011000010 -> eval(v97) = 1.475358486175537
v98 = 1111110101110110111010 -> eval(v98) = 1.9702868461608887
v99 = 1001001100110100110111 -> eval(v99) = 0.7250759601593018
v100 = 1000100110010000110101 -> eval(v100) = 0.6120984554290771
점수 100/100
'archive. > Schoolwork' 카테고리의 다른 글
| [C++] 자료구조 1주차 과제1 (0) | 2020.08.05 |
|---|---|
| [C++] 문제해결기법 과제 4: 가장 큰 수 (0) | 2020.08.05 |
| [C++] 문제해결기법 과제 3: 칸 채우기 (0) | 2020.08.05 |
| [C++] 문제해결기법 과제 2: 포로 수용소 - Convex Hull 응용 (0) | 2020.08.05 |
| [C++] 문제해결기법 과제 1 - Flow Network 응용 (0) | 2020.08.05 |